This is the hashmap implementation I wrote a while ago, using separate
chaining, and using J's OO functionality. Bear in mind I am not a J expert, and
when I wrote this I knew even less J.
I am pretty sure others have written better implementations, but anyway, this
may be useful as a reference for writing your own. The hash function is
pretty crummy, I was going to attempt to implement murmurhash in J, but never
got around to doing it. Also there is no verb to output the map as json, or
import json.
I lost a little interest in this after realizing J' OO has no introspection
ability. So putting one hashmap inside another (as in embedding a json
dictionary in another json dictionary)
leads to a loss of information, as you have to remember that the value is a J
object , and not a boxed literal.
coclass 'HashMap'
entries=: ''
count=: ''
MAX=: 20
NB. Initialize and create buckets
create=: monad define
for_j. i. MAX do.
entries=: entries, (conew 'Entry')
end.
)
NB. Gets the size of the hashmap,
NB. number of key/value pairs.
size=: monad define
count=. 0
for_j. i. MAX do.
ent=. j{entries
if. isSet__ent do. count=. count + get_size__ent ''
end.
end.
count
)
NB. set a new key value pair.
NB. Should be boxed pair (key;value)
set=: monad define
rk=. >0{y NB. raw key
hk=. hash rk NB. hashed key
val=. >1{y NB. value
i=. conew 'Entry'
create__i rk;hk;val
hk append i
''
)
NB. Returns list of all key value pairs
NB. in an arbitrary order.
enumerate=: monad define
result=. ''
for_j. i. MAX do.
ent=. j{entries
if. isSet__ent do.
result=. result, (enumerate__ent '')
end.
end.
result
)
NB. Append the new Entry to the hashmap.
append=: dyad define
ent=. x { entries
newent=. y
NB. if empty slot, put new item in it.
if. 0 = isSet__ent do.
entries=: y x} entries
NB. if not empty, but raw keys are identical, refill.
elseif. rawKey__ent -: rawKey__newent do.
entries=: newent x} entries
NB. else append to the last in linkedlist
elseif. 1 do.
append_to_last__ent y
end.
)
NB. Get the value for the given key.
get=: monad define
ky=. y
hk=. hash ky
ent=. hk{entries
if. 0 = isSet__ent do. 'ERROR' return.
elseif. key__ent -: hk do.
matches__ent ky
end.
)
NB. Removes a single entry form the hashmap, if
NB. the given key matches the key of the entry.
remove=: monad define
ky=. y
hk=. hash ky
ent=. hk{entries
NB. if no entry, then return.
if. 0 = isSet__ent do. 0
NB. keys match...
elseif. key__ent -: hk do.
NB. check if raw keys match...
if. ky -: rawKey__ent do.
NB. linked list is 0 so remove this item.
if. 0 = # next__ent do.
reset__ent ''
1
NB. linked list has elements so put
NB. next element in bucket (becomes head of list).
else. entries=: next__ent hk} entries
reset__ent ''
1
end.
NB. raw keys do not match, check next element.
else.
nextent=. next__ent
ent remove_from_list__nextent y
end.
end.
)
NB. Returns 1 if vey value pair exists for the
NB. given key, otherwise returns 0.
contains_value=: monad define
ky=. y
hk=. hash ky
ent=. hk{entries
if. 0 = isSet__ent do. 0
elseif. key__ent = hk do.
contains__ent ky
end.
)
NB. Hash the key.
hash=: monad define
h=. a.i.": y
h=. +/h
h1=. 3 (33 b.) h
h2=. 13 (33 b.) h
h=. h XOR h1 XOR h2
h=. h XOR (7 ( 33 b.) h)
MAX | h
)
destroy=: codestroy
NB. =============== ENTRY CLASS =============
NB. Entry class contains key value pair and "pointer"
NB. to potential next entry in LinkedList fashion.
coclass 'Entry'
key=: '' NB. The key (hashed)
value=: '' NB. The value
next=: '' NB. The next value, if any
rawKey=: '' NB. The raw, unhashed, key
isSet=: 0 NB. flag for instantiated or not.
NB. Instantiate the Entry object.
create=: 3 : 0
rawKey=: >0{y
key=: >1{y
value=: 2}.y NB. strip the first two
isSet=: 1
)
NB. Returns 1 if this Entry contains the key
NB. value pair for the given key.
contains=: monad define
rk=: y
if. isSet = 0 do. 0
elseif. (<rawKey) = <rk do.
1
elseif. 0 = # next do. 0
elseif. 1 do.
contains__next y
end.
)
NB. Returns this key value pair and the
NB. list of key value pairs of the tail of the
NB. linked list.
enumerate=: monad define
if. 0 = # next do.
<(rawKey; value)
else.
(<(rawKey;value)),( enumerate__next '')
end.
)
NB. Tests if the key matches and if so returns the value,
NB. else sends key to the next item in linkedlist.
matches=: monad define
rk=. y
rk =. ($rawKey) $ rk
if. isSet = 0 do. 'ERROR' return.
elseif. (rawKey) -: (rk) do.
value
elseif. 1 do.
matches__next y
end.
)
NB. Removes this item from the current linked list.
remove_from_list=: dyad define
rk=. y NB. a raw key
last=. x NB. the last entry in this list
if. rk -: rawKey do.
next__last=: next NB. relink the last/next items.
reset ''
1
elseif. 0 = # next do. 0
elseif. 1 do. next__last remove_from_list__next y end.
)
get_size=: monad define
if. 0 = # next do. 1
else. 1 + get_size__next ''
end.
)
append_to_last=: monad define
if. 0 = # next do.
next=: y
else.
append_to_last__next y
end.
)
NB. Resets this item.
reset=: monad define
isSet=: 0
key=: ''
value=: ''
next=: ''
rawKey=: ''
)
destroy=: codestroy
NB. usage
H=: '' conew 'HashMap'
set__H 'key';'value'
set__H 'another key'; 4
remove__H 'key'
get__H 'another key'
enumerate__H '' NB. list all key-value-pairs
--------------------------------------------
On Mon, 12/4/17, Andrew Dabrowski <[email protected]> wrote:
Subject: Re: [Jprogramming] delete item; ass. lists
To: [email protected]
Date: Monday, December 4, 2017, 10:18 AM
Can you locate your code?
On 12/03/2017
06:52 PM, Henry Rich wrote:
> Yes;
I've done that before. It might be worth seeing how
well we
> could make such an addon
perform before making changes to the JE.
>
> Henry Rich
>
> On 12/3/2017 6:47 PM,
bill lam wrote:
>> Can this be
implemented using j script addon?
>>
>> On Dec 4,
2017 5:26 AM, "Henry Rich" <[email protected]>
wrote:
>>
>>>
Perhaps we shouldn't try to make a full datatype for
associative
>>> arrays,
>>> but just a set of functions
(foreigns, or (m h.) ) that do what's
>>> needed.
>>>
>>> We
would need to decide what's needed.
>>>
>>>
hashtable =: keys create values
>>>
indexes =: hashtable lookup keys (like i.)
>>> values =: hashtable fetch
indexes (like {)
>>> hashtable
=: hashtable add keys;values
>>>
hashtable =: hashtable delete indexes
>>>
>>> That
would not be the hardest thing to implement; perhaps we
should
>>> start
>>> a strawman in
Interpreter/Requests.
>>>
>>> Henry Rich
>>>
>>>
>>> On 12/3/2017 4:06 PM, Marshall
Lochbaum wrote:
>>>
>>>> The associative lists that
Andrew is talking about (also called
>>>> maps or
>>>> dictionaries) are essentially
the same as JSON objects (more
>>>> precisely,
>>>> JSON objects are maps whose
keys are strings). There's no need for
>>>> them
>>>> to be used in a particularly
low-level way, although the primitives
>>>> used
>>>> to manipulate them would have
to be different from J's array
>>>> primitives.
>>>> Examples might be combining
two maps but giving preference to one of
>>>> them when they conflict, or
inverting a map by swapping keys and
>>>> values.
>>>>
>>>> Lisp stands for "list
processing", and its fundamental datatype is the
>>>> linked list, composed of
value-reference pairs. These aren't
>>>> related to
>>>> associative arrays, at least
not any more than they are related to any
>>>> other datatype.
>>>>
>>>> I feel pretty strongly that an
associative array type is missing in J,
>>>> but it's understandable
given how hard such a type would be to specify
>>>> and implement. That
doesn't make it any easier to live without them,
>>>> though.
>>>>
>>>> Marshall
>>>>
>>>> On Sun, Dec 03, 2017 at
01:50:43PM -0500, Raul Miller wrote:
>>>>
>>>>> <<< means
"box three times"
>>>>>
>>>>> <2
>>>>> ┌─┐
>>>>> │2│
>>>>> └─┘
>>>>> <<2
>>>>> ┌───┐
>>>>> │┌─┐│
>>>>> ││2││
>>>>> │└─┘│
>>>>> └───┘
>>>>> <<<2
>>>>> ┌─────┐
>>>>> │┌───┐│
>>>>> ││┌─┐││
>>>>> │││2│││
>>>>> ││└─┘││
>>>>> │└───┘│
>>>>> └─────┘
>>>>>
>>>>> See also the documentation
on the index operation (Henry gave you a
>>>>> reference for that).
>>>>>
>>>>> Also, as I understand it,
JSON has only a loose relationship with
>>>>> a-lists. My understanding
of them is that they are the fundamental
>>>>> datatype provided by the
lisp / scheme / .. family of languages.
>>>>> Basically, you're
working with pointer chasing. In J, you can use
>>>>> indices or names as
references, if you want to build a workalike -
>>>>> but
>>>>> usually it's just not
worth the bother.
>>>>>
>>>>> And that
"encode" method is building a name based on an
arbitrary
>>>>> string. You
should probably think of it as a hash function. But
>>>>> there's a typo - there
should be a space after the v in inv. But this
>>>>> suggests also that
rosettacode is having bitrot issues with its
>>>>> storage system, and that
has all sorts of unpleasant implications.
>>>>> Basically, you are not
going to be able to use rosettacode
>>>>> implementations - in the
general case - unless you are prepared to
>>>>> debug them (which kind of
defeats the purpose of having the site in
>>>>> the first place.) ...
wait, no.. when I go to that rosettacode
>>>>> page, I
>>>>> see a space after the
'inv' keyword. Well.. it could still be bitrot,
>>>>> but perhaps at the
cloudfront level rather than on the site itself...
>>>>>
>>>>> Thanks,
>>>>>
>>>>> --
>>>>> Raul
>>>>>
>>>>>
>>>>>
>>>>> On Sun, Dec 3, 2017 at
1:24 PM, Andrew Dabrowski
>>>>> <[email protected]>
>>>>> wrote:
>>>>>
>>>>>> 1. Yes, I should been
more specific: I wanted to know the
>>>>>> idiomatic way
>>>>>> to
>>>>>> delete the nth item of
a list, so I think <<< is what I was
>>>>>> looking for.
>>>>>>
>>>>>> What is <<<
called and where is it documented?
>>>>>>
>>>>>> 2. Not sure what you
mean by "Their focus is on micromanaging the
>>>>>> sequence
>>>>>> of operations."
A-lists are built into just about every other
>>>>>> modern
>>>>>> language because
they're so useful at managing information. Does
>>>>>> J not
>>>>>> support JSON for web
interoperability?
>>>>>>
>>>>>> One example is using
an a-list as a structured object, without
>>>>>> having
>>>>>> to get
>>>>>> into full-blown OO.
I could represent the state of a model using an
>>>>>> a-list
>>>>>> and then update the
values over time.
>>>>>>
>>>>>> I saw that using
classes is one alternative
>>>>>> (https://rosettacode.org/wiki/Associative_array/Creation#J).
>>>>>>
>>>>>>
coclass'assocArray'
>>>>>>
encode=:'z',(a.{~;48 65 97(+ i.)&.>10
26 26) {~62x
>>>>>>
#.inv256x #.
>>>>>>
a.&i.
>>>>>>
get=: ".@encode
>>>>>> has=:0
<: nc@<@encode
>>>>>> set=:4
:'(encode x)=:y'
>>>>>>
>>>>>> I have absolutely no
idea what is going on in the encode function. I
>>>>>> hope
>>>>>> there are other
options.
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 12/03/2017 12:59
PM, Raul Miller wrote:
>>>>>>
>>>>>>> Why do you want to
delete an item from a list? This is *not* a
>>>>>>> rhetorical
question - we have a variety of ways of removing
>>>>>>> items from
>>>>>>> lists and to pick
the correct mechanism we need to understand
>>>>>>> what you
>>>>>>> are trying to
accomplish.
>>>>>>>
>>>>>>> To illustrate,
here are a few examples:
>>>>>>>
>>>>>>> list=: 2 3 4 5 7 8
9 10
>>>>>>>
>>>>>>> NB.
delete specific elements
>>>>>>> list -.
3 5 7
>>>>>>> 2 4 8 9
10
>>>>>>>
>>>>>>> NB.
delete based on a computation
>>>>>>>
(0=1&p: list)#list
>>>>>>> 4 8 9 10
>>>>>>>
>>>>>>> NB.
delete based on a range of indices
>>>>>>>
(3&{.,6&}.) list
>>>>>>> 2 3 4 9 10
>>>>>>>
>>>>>>> NB.
delete values at certain indices
>>>>>>>
(<<<3 5 6){ list
>>>>>>> 2 3 4 7 10
>>>>>>>
>>>>>>> And then
there's operations (like outfix) which offer regular
>>>>>>> abstractions:
>>>>>>> 3 ]\.
list
>>>>>>> 5 7 8 9
10
>>>>>>> 2 7 8 9
10
>>>>>>> 2 3 8 9
10
>>>>>>> 2 3 4 9
10
>>>>>>> 2 3 4 5
10
>>>>>>> 2 3 4 5
7
>>>>>>>
>>>>>>> Note that
"delete from a list" is a dual of "select
from a list" -
>>>>>>> maybe a shift in
perspective can help?
>>>>>>>
>>>>>>> As for the lack of
"a-lists" - again, why do you want them?
>>>>>>> Depending
>>>>>>> on what you are
trying to do, there's a lot of options. Their
>>>>>>> focus is
>>>>>>> on micromanaging
the sequence of operations, though, so you
>>>>>>> should not
>>>>>>> expect the
language to make most of your decisions for you, there
>>>>>>> (unless of course
you are working with a language which was
>>>>>>> specifically
designed with an "everything should be an
a-list"
>>>>>>>
mentality - but that's not J).
>>>>>>>
>>>>>>> Thanks,
>>>>>>>
>>>>>>>
----------------------------------------------------------------------
>>>>>>>
>>>>>> For information about
J forums see
>>>>>> http://www.jsoftware.com/forums.htm
>>>>>>
>>>>>
----------------------------------------------------------------------
>>>>>
>>>>> For information about J
forums see
>>>>> http://www.jsoftware.com/forums.htm
>>>>>
>>>>
----------------------------------------------------------------------
>>>> For information about J forums
see http://www.jsoftware.com/forums.htm
>>>>
>>>
>>>
---
>>> This email has been checked
for viruses by AVG.
>>> http://www.avg.com
>>>
>>>
----------------------------------------------------------------------
>>> For information about J forums see
http://www.jsoftware.com/forums.htm
>>
----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
