envzn
0.8 · beta · not released

Library / Collections / Dictionaries / RedBlackTreeDictionary

CLASSIMPLEMENTS Dictionary<K, V, H>

RedBlackTreeDictionary

An ORDERED Dictionary[K, V, H] backed by a left-leaning red-black tree (Sedgewick LLRB), ARENA form. Guaranteed O(log n) lookup / insert / remove; iteration yields keys in Comparable order.

Fields 3

int64 rootIdx
int64 count
int64 freeHead

Constructors 4

INIT()
INIT(Hasher[K] h)
INIT(GrowthHint hint, int64 initialCapacity)
INIT(Hasher[K] h, GrowthHint hint, int64 initialCapacity)

Methods 13

MODIFY METHOD insert(K key, V value) RETURNS STATUS
modifies
MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS
modifies
METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V
reads
METHOD lookupFast(REFERENCE K key) RETURNS boolean
reads

Dictionary.lookupFast — the same descent as lookup, without the STATUS that lookup must allocate on a miss.

MODIFY METHOD remove(REFERENCE K key) RETURNS | K
modifies

Remove — hands back the STORED key and value (not the probe key, which is what the old key-only remove returned).

Like the SoA dictionaries and unlike ChainedHashDictionary, the halves are cloned rather than moved: the arena node is reached by index and a subscript read clones by rule (stmt_assign.py:149), and the LLRB delete rebalances the tree, so the node cannot simply be evicted first. Census pins this at one DUPLICATE per half.

METHOD contains(REFERENCE K key) RETURNS boolean
reads
METHOD isEmpty() RETURNS boolean
reads
METHOD size() RETURNS int64
reads

Number of key-value pairs currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void
modifies
METHOD keys() RETURNS LinkedList[K]
reads
METHOD iterator() RETURNS ReferenceIterator[K]
reads
METHOD clone() RETURNS Dictionary[K, V, H]
reads
METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS boolean
reads

for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.