AvlMap

Ordered key-value container implemented as an AVL tree.

Known issue: constructing an AVLMap fails compilation with «copy», Name was not found. The module also uses unavailable names isMoved and move in insert, recursive in clear, ASSIGN, debugPrint, and each, times in debugPrint, and print and printList in debugPrint without importing them; the API remains unavailable until the module is repaired. Its clear implementation frees node storage without destroying stored key and value objects (AvlMap.mpl:331-346); repair that cleanup before using managed keys or values.

Construct with key and value schemas in front of AVLMap: Int32 Int32 AVLMap.

Fields

AVL_MAP: virtual map marker field.
keyType: virtual Ref to the key schema.
valueType: virtual Ref to the value schema.
nodeType: virtual Ref to the node Dict with fields value, key, balance, left, and right; asNode interprets a node address as a Ref to this node.
root: root-node address stored as Natx; this is the only field with run-time storage.

Public methods

INIT (--): initializes an empty map.
find (key -- result): returns the lookup result for one key.
insert (key value --): inserts one new key-value pair.
erase (key --): removes the pair at one key.
clear (--): removes all pairs and resets the root.
ASSIGN (other --): replaces the map contents with a cloned copy of other.
DIE (--): calls clear; it frees node storage without destroying stored key and value objects.
debugPrint (--): prints one debug view of the tree.

Ordering and key semantics

Keys are compared through = and <.
insert requires an absent key; erase requires a present key. The source checks these preconditions with assert; run-time checks are disabled by -ndebug, so callers must not rely on rejection in that mode.
debugPrint visits the stored pairs in ascending key order.
The module has no size field or method.
A newly initialized map stores 0nx in root and therefore has no nodes.

Storage and lifetime

Each valid insert allocates one new node; insert is unavailable in the current module, so see the known issue for its unresolved names.
erase destroys and frees exactly one stored node.
clear frees every stored node's storage without destroying the stored key and value objects (their DIE is not run) and resets root to the empty state; DIE and ASSIGN use clear.
ASSIGN deep-clones the whole tree. The new map does not share node storage with the source map.

find result and returned refs

success: reports whether the key was found.
value: Ref to the stored value when success is TRUE; the Ref is mutable only through a mutable map path such as @m (through m it is immutable), and when mutable, writing through it replaces the stored value.
When success is FALSE, value is a nil ref of valueType.
Value refs remain valid across insert and erase of another key. Erasing the referenced pair invalidates its ref; clear, ASSIGN, and DIE invalidate all value refs.

each `(source body --)`

Pops a map (or a view of it) and a body and calls the body once per stored pair in ascending key order; the tree structure is unchanged, but the body may replace stored values only through a mutable source map.

source must provide the AVL_MAP marker field.
The body receives one record with fields key and value.
key is an immutable borrowed Ref to the stored key, not a copy.
value is a Ref to the stored value; the Ref is mutable only through a mutable map path such as @m (through m it is immutable), and when mutable, writing through it replaces the stored value.
Value refs remain valid across insert and erase of another key. Erasing the referenced pair invalidates its ref; clear, ASSIGN, and DIE invalidate all value refs.

AVLMap