diff options
Diffstat (limited to 'stdlib/source/lux/data/struct/dict.lux')
| -rw-r--r-- | stdlib/source/lux/data/struct/dict.lux | 76 |
1 files changed, 38 insertions, 38 deletions
diff --git a/stdlib/source/lux/data/struct/dict.lux b/stdlib/source/lux/data/struct/dict.lux index a10e30dca..d4cbaa7ec 100644 --- a/stdlib/source/lux/data/struct/dict.lux +++ b/stdlib/source/lux/data/struct/dict.lux @@ -103,13 +103,13 @@ ## which is 1/4 of the branching factor (or a left-shift 2). (def: demotion-threshold Nat - (bit;<< (-+ +2 branching-exponent) +1)) + (bit;<< (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 - (bit;<< (-+ +1 branching-exponent) +1)) + (bit;<< (n.- +1 branching-exponent) +1)) ## The size of hierarchy-nodes, which is 2^(branching-exponent). (def: hierarchy-nodes-size @@ -126,11 +126,11 @@ (def: (insert! idx value old-array) (All [a] (-> Index a (Array a) (Array a))) (let [old-size (array;size old-array)] - (|> (: (Array ($ 0)) - (array;new (inc+ old-size))) + (|> (: (Array ($ +0)) + (array;new (n.inc old-size))) (array;copy idx +0 old-array +0) (array;put idx value) - (array;copy (-+ idx old-size) idx old-array (inc+ idx))))) + (array;copy (n.- idx old-size) idx old-array (n.inc idx))))) ## Creates a copy of an array with an index set to a particular value. (def: (update! idx value array) @@ -145,23 +145,23 @@ ## Shrinks a copy of the array by removing the space at index. (def: (remove! idx array) (All [a] (-> Index (Array a) (Array a))) - (let [new-size (dec+ (array;size array))] + (let [new-size (n.dec (array;size array))] (|> (array;new new-size) (array;copy idx +0 array +0) - (array;copy (-+ idx new-size) (inc+ idx) array idx)))) + (array;copy (n.- idx new-size) (n.inc idx) array idx)))) ## Given a top-limit for indices, produces all indices in [0, R). (def: indices-for (-> Nat (List Index)) - (|>. dec+ (list;range+ +0))) + (|>. n.dec (list;n.range +0))) ## Increases the level-shift by the branching-exponent, to explore ## levels further down the tree. (def: level-up (-> Level Level) - (++ branching-exponent)) + (n.+ branching-exponent)) -(def: hierarchy-mask BitMap (dec+ hierarchy-nodes-size)) +(def: hierarchy-mask BitMap (n.dec hierarchy-nodes-size)) ## Gets the branching-factor sized section of the hash corresponding ## to a particular level, and uses that as an index into the array. @@ -182,12 +182,12 @@ (def: (bit-position-is-set? bit bitmap) (-> BitPosition BitMap Bool) - (not (=+ clean-bitmap (bit;& bit bitmap)))) + (not (n.= clean-bitmap (bit;& bit bitmap)))) ## Figures out whether a bitmap only contains a single bit-position. (def: only-bit-position? (-> BitPosition BitMap Bool) - =+) + n.=) (def: (set-bit-position bit bitmap) (-> BitPosition BitMap BitMap) @@ -208,7 +208,7 @@ ## associated with it. (def: bit-position-mask (-> BitPosition BitMap) - dec+) + n.dec) ## The index on the base array, based on it's bit-position. (def: (base-index bit-position bitmap) @@ -231,14 +231,14 @@ (List/fold (lambda [idx (^@ node [bitmap base])] (case (array;get idx h-array) #;None node - (#;Some sub-node) (if (=+ except-idx idx) + (#;Some sub-node) (if (n.= except-idx idx) node [(set-bit-position (->bit-position idx) bitmap) (array;put idx (#;Left sub-node) base)]) )) [clean-bitmap - (: (Base ($ 0) ($ 1)) - (array;new (dec+ h-size)))] + (: (Base ($ +0) ($ +1)) + (array;new (n.dec h-size)))] (list;indices (array;size h-array)))) ## When #Base nodes grow too large, they're promoted to #Hierarchy to @@ -252,7 +252,7 @@ (product;right (List/fold (lambda [hierarchy-idx (^@ default [base-idx h-array])] (if (bit-position-is-set? (->bit-position hierarchy-idx) bitmap) - [(inc+ base-idx) + [(n.inc base-idx) (case (array;get base-idx base) (#;Some (#;Left sub-node)) (array;put hierarchy-idx sub-node h-array) @@ -266,7 +266,7 @@ (undefined))] default)) [+0 - (: (Array (Node ($ 0) ($ 1))) + (: (Array (Node ($ +0) ($ +1))) (array;new hierarchy-nodes-size))] (indices-for hierarchy-nodes-size)))) @@ -289,13 +289,13 @@ ## a sub-node. If impossible, I introduced a new singleton sub-node. (#Hierarchy _size hierarchy) (let [idx (level-index level hash) - [_size' sub-node] (: [Nat (Node ($ 0) ($ 1))] + [_size' sub-node] (: [Nat (Node ($ +0) ($ +1))] (case (array;get idx hierarchy) (#;Some sub-node) [_size sub-node] _ - [(inc+ _size) empty]))] + [(n.inc _size) empty]))] (#Hierarchy _size' (update! idx (put' (level-up level) hash key val Hash<K> sub-node) hierarchy))) @@ -324,12 +324,12 @@ ## Otherwise, I compare the hashes of the keys. (#Base bitmap (update! idx (#;Left (let [hash' (:: Hash<K> hash key')] - (if (=+ hash hash') + (if (n.= hash hash') ## If the hashes are ## the same, a new ## #Collisions node ## is added. - (#Collisions hash (|> (: (Array [($ 0) ($ 1)]) + (#Collisions hash (|> (: (Array [($ +0) ($ +1)]) (array;new +2)) (array;put +0 [key' val']) (array;put +1 [key val]))) @@ -346,10 +346,10 @@ ## However, if the BitPosition has not been used yet, I check ## whether this #Base node is ready for a promotion. (let [base-count (bitmap-size bitmap)] - (if (>=+ promotion-threshold base-count) + (if (n.>= promotion-threshold base-count) ## If so, I promote it to a #Hierarchy node, and add the new ## KV-pair as a singleton node to it. - (#Hierarchy (inc+ base-count) + (#Hierarchy (n.inc base-count) (|> (promote-base put' Hash<K> level bitmap base) (array;put (level-index level hash) (put' (level-up level) hash key val Hash<K> empty)))) @@ -360,7 +360,7 @@ ## For #Collisions nodes, I compare the hashes. (#Collisions _hash _colls) - (if (=+ hash _hash) + (if (n.= hash _hash) ## If they're equal, that means the new KV contributes to the ## collisions. (case (collision-index Hash<K> key _colls) @@ -375,7 +375,7 @@ ## 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) - (|> (: (Base ($ 0) ($ 1)) + (|> (: (Base ($ +0) ($ +1)) (array;new +1)) (array;put +0 (#;Left node)))) (put' level hash key val Hash<K>))) @@ -403,11 +403,11 @@ ## But if the sub-removal yielded an empty sub-node... (if (empty?' sub-node') ## Check if it's due time for a demotion. - (if (<=+ demotion-threshold h-size) + (if (n.<= demotion-threshold h-size) ## If so, perform it. (#Base (demote-hierarchy idx [h-size h-array])) ## Otherwise, just clear the space. - (#Hierarchy (dec+ h-size) (vacant! idx h-array))) + (#Hierarchy (n.dec h-size) (vacant! idx h-array))) ## But if the sub-removal yielded a non-empty node, then ## just update the hiearchy branch. (#Hierarchy h-size (update! idx sub-node' h-array))))))) @@ -465,7 +465,7 @@ ## But if so, then check the size of the collisions list. (#;Some idx) - (if (=+ +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 @@ -510,14 +510,14 @@ (All [K V] (-> (Node K V) Nat)) (case node (#Hierarchy _size hierarchy) - (Array/fold ++ +0 (Array/map size' hierarchy)) + (Array/fold n.+ +0 (Array/map size' hierarchy)) (#Base _ base) - (Array/fold ++ +0 (Array/map (lambda [sub-node'] - (case sub-node' - (#;Left sub-node) (size' sub-node) - (#;Right _) +1)) - base)) + (Array/fold n.+ +0 (Array/map (lambda [sub-node'] + (case sub-node' + (#;Left sub-node) (size' sub-node) + (#;Right _) +1)) + base)) (#Collisions hash colls) (array;size colls) @@ -599,7 +599,7 @@ (def: #export empty? (All [K V] (-> (Dict K V) Bool)) - (|>. size (=+ +0))) + (|>. size (n.= +0))) (def: #export (entries dict) (All [K V] (-> (Dict K V) (List [K V]))) @@ -663,8 +663,8 @@ ## [Structures] (struct: #export (Eq<Dict> Eq<v>) (All [k v] (-> (Eq v) (Eq (Dict k v)))) (def: (= test subject) - (and (=+ (size test) - (size subject)) + (and (n.= (size test) + (size subject)) (list;every? (lambda [k] (case [(get k test) (get k subject)] [(#;Some tk) (#;Some sk)] |