diff options
Diffstat (limited to 'stdlib/source/lux/data/collection/dictionary.lux')
| -rw-r--r-- | stdlib/source/lux/data/collection/dictionary.lux | 48 |
1 files changed, 24 insertions, 24 deletions
diff --git a/stdlib/source/lux/data/collection/dictionary.lux b/stdlib/source/lux/data/collection/dictionary.lux index 49465c123..64c577946 100644 --- a/stdlib/source/lux/data/collection/dictionary.lux +++ b/stdlib/source/lux/data/collection/dictionary.lux @@ -41,7 +41,7 @@ ## the appropriate multiple of the branching-exponent. ## A shift of 0 means root level. ## A shift of (* branching-exponent 1) means level 2. -## A shift of (* branching-exponent N) means level N+1. +## A shift of (* branching-exponent N) means level N|1. (type: Level Nat) ## Nodes for the tree data-structure that organizes the data inside @@ -75,7 +75,7 @@ ## Which is 32 zeroes, since the branching factor is 32. (def: clean-bitmap BitMap - +0) + |0) ## Bitmap position (while looking inside #Base nodes) is determined by ## getting 5 bits from a hash of the key being looked up and using @@ -88,35 +88,35 @@ ## shift in the shallowest node on the tree, which is the root node). (def: root-level Level - +0) + |0) ## The exponent to which 2 must be elevated, to reach the branching ## factor of the data-structure. (def: branching-exponent Nat - +5) + |5) ## The threshold on which #Hierarchy nodes are demoted to #Base nodes, ## which is 1/4 of the branching factor (or a left-shift 2). (def: demotion-threshold Nat - (i64.left-shift (n/- +2 branching-exponent) +1)) + (i64.left-shift (n/- |2 branching-exponent) |1)) ## The threshold on which #Base nodes are promoted to #Hierarchy nodes, ## which is 1/2 of the branching factor (or a left-shift 1). (def: promotion-threshold Nat - (i64.left-shift (n/- +1 branching-exponent) +1)) + (i64.left-shift (n/- |1 branching-exponent) |1)) ## The size of hierarchy-nodes, which is 2^(branching-exponent). (def: hierarchy-nodes-size Nat - (i64.left-shift branching-exponent +1)) + (i64.left-shift branching-exponent |1)) ## The cannonical empty node, which is just an empty #Base node. (def: empty Node - (#Base clean-bitmap (array.new +0))) + (#Base clean-bitmap (array.new |0))) ## Expands a copy of the array, to have 1 extra slot, which is used ## for storing the value. @@ -124,7 +124,7 @@ (All [a] (-> Index a (Array a) (Array a))) (let [old-size (array.size old-array)] (|> (array.new (inc old-size)) - (array.copy idx +0 old-array +0) + (array.copy idx |0 old-array |0) (array.write idx value) (array.copy (n/- idx old-size) idx old-array (inc idx))))) @@ -143,13 +143,13 @@ (All [a] (-> Index (Array a) (Array a))) (let [new-size (dec (array.size array))] (|> (array.new new-size) - (array.copy idx +0 array +0) + (array.copy idx |0 array |0) (array.copy (n/- idx new-size) (inc idx) array idx)))) ## Given a top-limit for indices, produces all indices in [0, R). (def: indices-for (-> Nat (List Index)) - (|>> dec (list.n/range +0))) + (|>> dec (list.n/range |0))) ## Increases the level-shift by the branching-exponent, to explore ## levels further down the tree. @@ -169,7 +169,7 @@ ## A mechanism to go from indices to bit-positions. (def: (->bit-position index) (-> Index BitPosition) - (i64.left-shift index +1)) + (i64.left-shift index |1)) ## The bit-position within a base that a given hash-code would have. (def: (bit-position level hash) @@ -234,7 +234,7 @@ [(set-bit-position (->bit-position idx) bitmap) (array.write insertion-idx (#.Left sub-node) base)]]) ))) - [+0 [clean-bitmap + [|0 [clean-bitmap (array.new (dec h-size))]] (list.indices (array.size h-array))))) @@ -264,7 +264,7 @@ #.None (undefined))] default)) - [+0 + [|0 (array.new hierarchy-nodes-size)] hierarchy-indices))) @@ -326,9 +326,9 @@ ## the same, a new ## #Collisions node ## is added. - (#Collisions hash (|> (array.new +2) - (array.write +0 [key' val']) - (array.write +1 [key val]))) + (#Collisions hash (|> (array.new |2) + (array.write |0 [key' val']) + (array.write |1 [key val]))) ## Otherwise, I can ## just keep using ## #Base nodes, so I @@ -371,8 +371,8 @@ ## If the hashes are not equal, I create a new #Base node that ## contains the old #Collisions node, plus the new KV-pair. (|> (#Base (bit-position level _hash) - (|> (array.new +1) - (array.write +0 (#.Left node)))) + (|> (array.new |1) + (array.write |0 (#.Left node)))) (put' level hash key val Hash<k>))) )) @@ -460,7 +460,7 @@ ## But if so, then check the size of the collisions list. (#.Some idx) - (if (n/= +1 (array.size _colls)) + (if (n/= |1 (array.size _colls)) ## If there's only one left, then removing it leaves us with ## an empty node. empty @@ -505,13 +505,13 @@ (All [k v] (-> (Node k v) Nat)) (case node (#Hierarchy _size hierarchy) - (array/fold n/+ +0 (array/map size' hierarchy)) + (array/fold n/+ |0 (array/map size' hierarchy)) (#Base _ base) - (array/fold n/+ +0 (array/map (function (_ sub-node') + (array/fold n/+ |0 (array/map (function (_ sub-node') (case sub-node' (#.Left sub-node) (size' sub-node) - (#.Right _) +1)) + (#.Right _) |1)) base)) (#Collisions hash colls) @@ -605,7 +605,7 @@ (def: #export empty? (All [k v] (-> (Dictionary k v) Bit)) - (|>> size (n/= +0))) + (|>> size (n/= |0))) (def: #export (entries dict) (All [k v] (-> (Dictionary k v) (List [k v]))) |