object

`two3tree`

2-3 tree implementation.

Availability:

logtalk_load(dictionaries(loader))

Author: Michael T. Richter
Version: 1:0:0
Date: 2026-04-04

Compilation flags:

static, context_switching_calls

Implements:

public dictionaryp

Extends:

public term

Uses:

list

Remarks:

(none)

Public predicates 

`union/3`

Computes the union of two dictionaries. If a key appears in both, the value from the larger dictionary is kept.

Compilation flags:

static

Template:

union(Tree1,Tree2,Union)

Mode and number of proofs:

union(+two3tree,+two3tree,-two3tree) - zero_or_one

Protected predicates 

(no local declarations; see entity ancestors if any)

Private predicates 

`union_impl/3`

Inserts all key-value pairs of the smaller tree into the larger tree to compute the union.

Compilation flags:

static

Mode and number of proofs:

union_impl(+two3tree,+two3tree,-two3tree) - zero_or_one

`union_impl_list/3`

Inserts a list of key-value pairs into a dictionary one by one.

Compilation flags:

static

Mode and number of proofs:

union_impl_list(+list(pair),+two3tree,-two3tree) - zero_or_one

`clone_impl/3`

Recursively clones a tree, leaving all values unbound and collecting the pairs of the clone.

Compilation flags:

static

Mode and number of proofs:

clone_impl(+two3tree,-two3tree,-list(pair)) - one

`clone_impl2/4`

Recursively clones a tree, returning both the original pairs and the clone pairs.

Compilation flags:

static

Mode and number of proofs:

clone_impl2(+two3tree,-two3tree,-list(pair),-list(pair)) - one

`handle_root_underflow/2`

After a deletion, if the root has become a 2-node with a single child, replace it by that child; otherwise keep the root.

Compilation flags:

static

Mode and number of proofs:

handle_root_underflow(+term,-term) - one

`delete_impl/5`

Recursive deletion that returns the resulting tree and a flag indicating whether an underflow has occurred at the current node.

Compilation flags:

static

Mode and number of proofs:

delete_impl(+term,+term,?term,-term,-boolean) - zero_or_one

`fix_node2_left_underflow/6`

Repairs an underflow after a deletion in the left subtree of a node2.

Compilation flags:

static

Mode and number of proofs:

fix_node2_left_underflow(+term,+term,+term,+term,-term,-boolean) - one

`fix_node2_right_underflow/6`

Repairs an underflow after a deletion in the right subtree of a node2.

Compilation flags:

static

Mode and number of proofs:

fix_node2_right_underflow(+term,+term,+term,+term,-term,-boolean) - one

`fix_node3_left_underflow/9`

Repairs an underflow after a deletion in the left subtree of a node3.

Compilation flags:

static

Mode and number of proofs:

fix_node3_left_underflow(+term,+term,+term,+term,+term,+term,+term,-term,-boolean) - one

`fix_node3_middle_underflow/9`

Repairs an underflow after a deletion in the middle subtree of a node3.

Compilation flags:

static

Mode and number of proofs:

fix_node3_middle_underflow(+term,+term,+term,+term,+term,+term,+term,-term,-boolean) - one

`fix_node3_right_underflow/9`

Repairs an underflow after a deletion in the right subtree of a node3.

Compilation flags:

static

Mode and number of proofs:

fix_node3_right_underflow(+term,+term,+term,+term,+term,+term,+term,-term,-boolean) - one

`as_curly_bracketed_impl/2`

Builds a curly-bracketed term from a list of key-value pairs.

Compilation flags:

static

Mode and number of proofs:

as_curly_bracketed_impl(+list(pairs),-term) - one

`as_curly_bracketed_impl/3`

Helper that accumulates a comma-separated list inside curly braces.

Compilation flags:

static

Mode and number of proofs:

as_curly_bracketed_impl(+list(pairs),+pair,-term) - one

`insert_impl/4`

Recursive insertion that may return a node4 on the way up.

Compilation flags:

static

Mode and number of proofs:

insert_impl(+term,+term,+term,-term) - one

`insert_empty/4`

Inserts into an empty tree.

Compilation flags:

static

Mode and number of proofs:

insert_empty(+empty,+term,+term,-term) - one

`insert_node2_2/4`

Inserts a key-value pair into a leaf 2-node, creating a leaf 3-node.

Compilation flags:

static

Mode and number of proofs:

insert_node2_2(+term,+term,+term,-term) - one

`insert_node2_4/4`

Inserts into a non-leaf 2-node, possibly splitting a child 4-node.

Compilation flags:

static

Mode and number of proofs:

insert_node2_4(+term,+term,+term,-term) - one

`insert_node3_4/4`

Inserts a key-value pair into a leaf 3-node, creating a leaf 4-node.

Compilation flags:

static

Mode and number of proofs:

insert_node3_4(+term,+term,+term,-term) - one

`insert_node3_7/4`

Inserts into a non-leaf 3-node, possibly splitting a child 4-node.

Compilation flags:

static

Mode and number of proofs:

insert_node3_7(+term,+term,+term,-term) - one

`intersection_impl/4`

Computes the intersection of a list of key-value pairs with a tree, inserting common pairs into an accumulator.

Compilation flags:

static

Mode and number of proofs:

intersection_impl(+list(pair),+two3tree,+list(pair),-list(pair)) - zero_or_one

`is_node4/1`

True if the term is a 4-node (temporary representation).

Compilation flags:

static

Mode and number of proofs:

is_node4(+term) - zero_or_one

`map_impl/2`

Traverses the tree and applies a closure to each key-value pair.

Compilation flags:

static

Meta-predicate template:

map_impl(*,1)

Mode and number of proofs:

map_impl(+two3tree,@callable) - zero_or_more

`map_impl/3`

Traverses the tree, applies a closure to each key-value pair, and builds a new tree with the results.

Compilation flags:

static

Meta-predicate template:

map_impl(*,2,*)

Mode and number of proofs:

map_impl(+two3tree,@callable,-two3tree) - zero_or_more

`next_impl/5`

Recursively finds the next key-value pair after a given key.

Compilation flags:

static

Mode and number of proofs:

next_impl(+two3tree,+key,-key,-value,+term) - zero_or_one

`previous_impl/5`

Recursively finds the previous key-value pair before a given key.

Compilation flags:

static

Mode and number of proofs:

previous_impl(+two3tree,+key,-key,-value,+term) - zero_or_one

`node2_from_node4/2`

Converts a 4-node (temporary) into a balanced 2-node with two 2-node children.

Compilation flags:

static

Mode and number of proofs:

node2_from_node4(+term,-term) - one

`update_impl/3`

Updates a dictionary with a list of key-value pairs sequentially.

Compilation flags:

static

Mode and number of proofs:

update_impl(@list(pair),+two3tree,-two3tree) - zero_or_one

`collect/4`

In-order traversal accumulating selected projections of nodes.

Compilation flags:

static

Template:

collect(Tree,Selector,Accumulator,ReversedResult)

Mode and number of proofs:

collect(+two3tree,+selector,+list(term),-list(term)) - one

`select/4`

Projects a key-value pair according to the selector.

Compilation flags:

static

Template:

select(Selector,Key,Value,Element)

Mode and number of proofs:

select(+selector,+key,+value,-term) - one

Operators 

(none)

two3tree

`two3tree`