lazy dictionary creation

dictionary.ijs

coclass 'jdictionary'

SIZE_GROWTH_GEOMETRIC_STEP =: 2

create =: {{)m
if. 'literal' -: datatype y do.
  index_type =: y                 NB. made non-local as it needs to persist after create returns for running createdict. 
  creation_parameters =. ''
else.
  index_type          =: {.y      NB. Split so index_type is non-local, while creation_parameters are.
  creation_parameters =. {:y
end.
NB. Default values of params.
NB.  keytype =: 4
NB.  keyshape =: i. 0
NB.  valuetype =: 4
NB.  valueshape =: i. 0
keyhash =: 16!:0`''
keycompare =: 16!:0`''
initsize =: 100
name =: ''

if. (-: (index_type {.~ -@#)) 'concurrent' do.
  singlethreaded =: 0            NB. non-local so createdict works.
  index_type     =: (- # ' concurrent') }. index_type
else.
  singlethreaded =: 1
end.
NB. parse parameters already here, to ensure key/value type/shape set if given.
parse^:(*@#) creation_parameters
if. -. _1 e. 4!:0 <;._1 ' keytype keyshape valuetype valueshape' do.
  NB. All present, create dictionary as 
  createdict''
else. NB. Proposal: lazy dictionary; infer key/value type/shape from first insert.
  if. name -: '' do. prefix =. suffix =. '' else. 'prefix suffix' =. (,{:)&.>/\. split_name name end.

  (prefix , 'put' , suffix) =: {{ NB. Place-holder for lazy creation of dictionary.
  NB. No values provided, set key type shape from first insert keys (and values if provided)
  NB. Note 0: This overwrites any previously set key/val type/shape.
  NB.     Alternatively: check for compliance with ones that did get set upon creation.
  NB. Note 1: This proposal chooses to use items of both keys and values as items in the dictionary. Alternatively, one could consider both a single item
  NB.    Either case, if not specified explicitly, one or the other behaviour should be chosen.
  'keytype keyshape' =: (3!:0 ; }.@$) y
  if. x-:'' do.
    valuetype  =: 4     NB. No values provided, set default type/shape
    valueshape =: 0
  else.
    'valuetype valueshape' =: (3!:0 ; }.@$) x
  end.
  createdict''
  x put y
}}
  NB. Other methods
  (prefix , 'get' , suffix)   =: (err =. 'dict not active; put first entry before use'&assert@:0:) f. NB. Others just error.
  (prefix , 'del' , suffix)   =: 0"_1 NB. Sensible defaults for del/has/count for empty dict.
  (prefix , 'has' , suffix)   =: 0"_1
  (prefix , 'count' , suffix) =: 0:
  if. index_type -: 'tree' do. (prefix , 'mget' , suffix) =: err f. end.  NB. getkv only on rb trees
end.
EMPTY
}}
  
createdict =: {{       NB. split off actual dictionary noun creation.
  select. index_type   NB. set up params for create, based on map type
  case. 'hash' do.
    itype =: 0  NB. index type 0 is hash
    occupancy =: 0.5   NB. default for occupancy
    NB. Parse params and update above attributes.
    internal_parameters =. (0 , initsize , <. initsize % occupancy) ; singlethreaded ; (keytype ; keyshape) ; < (valuetype ; valueshape)
  case. 'tree' do.
    itype =: 1  NB. index type 1 is tree
    NB. Parse params and update above attributes.
    if. 0 <: 4!:0 < 'occupancy' do.
       13!:8 (3) [ 'Parameter not supported in tree dictionary: occupancy'
    end.
    internal_parameters =. (0 , initsize) ; singlethreaded ; (keytype ; keyshape) ; < (valuetype ; valueshape)
  case. do.
    13!:8 (3) [ 'Incorrect index type'
  end.

  NB. Create the map, which remains as dict.  dict is marked nondisplayable because 1 {:: dict is.
  NB. If 1 {:: dict (keys) is an indirect type, it is death to touch or display any part of 1 {:: dict that is on the empty list.
  NB. It might be better not to assign dict, to make it impossible to access 1 {:: dict from console level.  But we have to be able to run 16!:_5 on it - make 16!:_5 an adverb
  if. keyhash -: keycompare do. keyfn =. keyhash `: 6 else. keyfn =. keyhash `: 6 : (keycompare `: 6) end.
  size =: initsize
  dict =: keyfn f. (16!:_1) internal_parameters

  NB. Assign names, depending on whether key/value type/shape have been set.
  if. name -: '' do. prefix =. suffix =. '' else. 'prefix suffix' =. (,{:)&.>/\. split_name name end.
  (prefix , 'get' , suffix) =: dict 16!:_2
  (prefix , 'put' , suffix) =: dict 16!:_3
  (prefix , 'del' , suffix) =: dict 16!:_4
  (prefix , 'has' , suffix) =: dict 16!:_12
  (prefix , 'count' , suffix) =: 0&(16!:_8)@dict
  if. index_type -: 'tree' do. (prefix , 'mget' , suffix) =: dict 16!:_6 end.  NB. getkv only on rb trees
  EMPTY
}}

destroy =: {{
(1) 16!:_5 dict  NB. clear the empty chain in the keys to avoid errors freeing it
codestroy y  NB. destroy the locale, freeing everything
}}

NB. Resize operation.  Nilad.  Allocate a larger/smaller dictionary and repopulate its keys
NB. We have a lock on (dict) during this entire operation
resize =: {{)m
size =: SIZE_GROWTH_GEOMETRIC_STEP * size
NB. We allocate a new DIC block of the correct size.  This is a temp whose contents, when filled, will be exchanged into (dict)
NB. This also allocates new areas for the keys, vals, and hash/tree
select. itype
case. 0 do.
  newdict =. dict (16!:_1) 0 , size , <. size * % occupancy  NB. allocate new DIC (hashed)
NB. for hashing: call (newdict 16!:_3) to rehash all the keys.  Limit the number of kvs per install to reduce temp space needed.
NB. Install the kvs from dict into newdict.  (e =. 1&(16!:_5) dict) (1) returns the list of empty key indexes; (2) erase the empty chains
NB. to allow the key block to be freed.  Then (<<<e) { keys/vals gives the kvs:
  empties =. (1) 16!:_5 dict   NB. get list of empties in dict, then erase the empty chains.  Prevents free error when releasing dict
  (newdict 16!:_3)&((<<<empties)&{)&:>/ 2 1 { dict  NB. Install all keys from dict into newdict
case. 1 do.
  newdict =. dict (16!:_1) 0 , size  NB. allocate new DIC (tree)
  NB. for red/black: copying the keys, vals, and tree from dict to newdict is done in JE when we return
end.
newdict  NB. Return the new block.  Its contents will be swapped with the old block so that the EPILOG for the resize will free the old keys/vals/hash
}}

NB. Utils.
NB. Gives type ID (e.g. 4) from type name (e.g. integer).
typeid_from_typename =: {{)m
n =. 1 2 4 8 16 32 64 128 1024 2048 4096 8192 16384 32768 65536 131072 262144
n =. n , 5 6 7 9 10 11
n =. n , _1 NB. _1 if y is not a name of any type.
t =. '/boolean/literal/integer/floating/complex/boxed/extended/rational'
t =. t , '/sparse boolean/sparse literal/sparse integer/sparse floating'
t =. t , '/sparse complex/sparse boxed/symbol/unicode/unicode4'
t =. t , '/integer1/integer2/integer4/floating2/floating4/floating16'
n {~ (<;._1 t) i. < y
}}

NB. Parse attribute and set its value.
parse =: {{)m
'attribute value' =: y
if. ('literal' -: datatype value) *. (attribute -: 'keytype') +. attribute -: 'valuetype' do.
  value =. typeid_from_typename value
end.
(attribute) =: value
EMPTY
}}"1

NB. y is string representing a name with possibly specified locale. Returns two boxes: name ; suffix with locale.
NB. Right part of hook.
NB. If '_' is the last character of y then the name has explicitly specified locale, so get the indexes of '_'.
NB. Left part of hook.
NB. Use the indexes to split the name or if the number of indexes is less than 2 then suppose name is from base.
NB. Note that number of indexes may be smaller then number of '_' e.g. 0 when condition from right part of the hook was false.
split_name =: ('__' ,~&< [)`(({. ,&< }.)~ _2&{)@.(2 <: #@])  ''"_`([: I. '_'&=)@.('_' -: {:)