Did you know ... Search Documentation:
Pack genutils -- prolog/rbutils.pl
PublicShow source

Re-exported predicates

The following predicates are exported from this file while their implementation is defined in imported modules or non-module files loaded by this module.

 rb_new(-Tree) is det
Create a new Red-Black tree Tree.
deprecated
- Use rb_empty/1.
 rb_empty(?Tree) is semidet
Succeeds if Tree is an empty Red-Black tree.
 rb_lookup(+Key, -Value, +Tree) is semidet
True when Value is associated with Key in the Red-Black tree Tree. The given Key may include variables, in which case the RB tree is searched for a key with equivalent variables (using (==)/2). Time complexity is O(log N) in the number of elements in the tree.
See also
- rb_in/3 for backtracking over keys.
 rb_min(+Tree, -Key, -Value) is semidet
Key is the minimum key in Tree, and is associated with Val.
 rb_max(+Tree, -Key, -Value) is semidet
Key is the maximal key in Tree, and is associated with Val.
 rb_next(+Tree, +Key, -Next, -Value) is semidet
Next is the next element after Key in Tree, and is associated with Val. Fails if Key isn't in Tree or if Key is the maximum key.
 rb_previous(+Tree, +Key, -Previous, -Value) is semidet
Previous is the previous element after Key in Tree, and is associated with Val. Fails if Key isn't in Tree or if Key is the minimum key.
 rb_update(+Tree, +Key, ?NewVal, -NewTree) is semidet
Tree NewTree is tree Tree, but with value for Key associated with NewVal. Fails if Key is not in Tree (using (==)/2). This predicate may fail or give unexpected results if Key is not sufficiently instantiated.
See also
- rb_in/3 for backtracking over keys.
 rb_update(+Tree, +Key, -OldVal, ?NewVal, -NewTree) is semidet
Same as rb_update(Tree, Key, NewVal, NewTree) but also unifies OldVal with the value associated with Key in Tree.
 rb_apply(+Tree, +Key, :G, -NewTree) is semidet
If the value associated with key Key is Val0 in Tree, and if call(G,Val0,ValF) holds, then NewTree differs from Tree only in that Key is associated with value ValF in tree NewTree. Fails if it cannot find Key in Tree, or if call(G,Val0,ValF) is not satisfiable.
 rb_in(?Key, ?Value, +Tree) is nondet
True when Key-Value is a key-value pair in red-black tree Tree. Same as below, but does not materialize the pairs.
rb_visit(Tree, Pairs), member(Key-Value, Pairs)

Leaves a choicepoint even if Key is instantiated; to avoid a choicepoint, use rb_lookup/3.

 rb_insert(+Tree, +Key, ?Value, -NewTree) is det
Add an element with key Key and Value to the tree Tree creating a new red-black tree NewTree. If Key is a key in Tree, the associated value is replaced by Value. See also rb_insert_new/4. Does not validate that Key is sufficiently instantiated to ensure the tree remains valid if a key is further instantiated.
 rb_insert_new(+Tree, +Key, ?Value, -NewTree) is semidet
Add a new element with key Key and Value to the tree Tree creating a new red-black tree NewTree. Fails if Key is a key in Tree. Does not validate that Key is sufficiently instantiated to ensure the tree remains valid if a key is further instantiated.
 rb_delete(+Tree, +Key, -NewTree)
Delete element with key Key from the tree Tree, returning the value Val associated with the key and a new tree NewTree. Fails if Key is not in Tree (using (==)/2).
See also
- rb_in/3 for backtracking over keys.
 rb_delete(+Tree, +Key, -Val, -NewTree)
Same as rb_delete(Tree, Key, NewTree), but also unifies Val with the value associated with Key in Tree.
 rb_del_min(+Tree, -Key, -Val, -NewTree)
Delete the least element from the tree Tree, returning the key Key, the value Val associated with the key and a new tree NewTree. Fails if Tree is empty.
 rb_del_max(+Tree, -Key, -Val, -NewTree)
Delete the largest element from the tree Tree, returning the key Key, the value Val associated with the key and a new tree NewTree. Fails if Tree is empty.
 rb_visit(+Tree, -Pairs) is det
Pairs is an infix visit of tree Tree, where each element of Pairs is of the form Key-Value.
 rb_map(+T, :Goal) is semidet
True if call(Goal, Value) is true for all nodes in T.
 rb_map(+Tree, :G, -NewTree) is semidet
For all nodes Key in the tree Tree, if the value associated with key Key is Val0 in tree Tree, and if call(G,Val0,ValF) holds, then the value associated with Key in NewTree is ValF. Fails if call(G,Val0,ValF) is not satisfiable for all Val0. If G is non-deterministic, rb_map/3 will backtrack over all possible values from call(G,Val0,ValF). You should not depend on the order of tree traversal (currently: key order).
 rb_fold(:Goal, +Tree, +State0, -State)
Fold the given predicate over all the key-value pairs in Tree, starting with initial state State0 and returning the final state State. Pred is called as
call(Pred, Key-Value, State1, State2)

Determinism depends on Goal.

 rb_fold(:Goal, +Tree, +State0, -State)
Fold the given predicate over all the key-value pairs in Tree, starting with initial state State0 and returning the final state State. Pred is called as
call(Pred, Key-Value, State1, State2)

Determinism depends on Goal.

 rb_clone(+TreeIn, -TreeOut, -Pairs) is det
`Clone' the red-back tree TreeIn into a new tree TreeOut with the same keys as the original but with all values set to unbound values. Pairs is a list containing all new nodes as pairs K-V.
 rb_partial_map(+Tree, +Keys, :G, -NewTree)
For all nodes Key in Keys, if the value associated with key Key is Val0 in tree Tree, and if call(G,Val0,ValF) holds, then the value associated with Key in NewTree is ValF, otherwise it is the value associated with the key in Tree. Fails if Key isn't in Tree or if call(G,Val0,ValF) is not satisfiable for all Val0 in Keys. Assumes keys are sorted and not repeated (fails if this is not true).
 rb_keys(+Tree, -Keys) is det
Keys is unified with an ordered list of all keys in the Red-Black tree Tree.
 list_to_rbtree(+List, -Tree) is det
Tree is the red-black tree corresponding to the mapping in List, which should be a list of Key-Value pairs. List should not contain more than one entry for each distinct key, but this is not validated by list_to_rbtree/2.
 ord_list_to_rbtree(+List, -Tree) is det
Tree is the red-black tree corresponding to the mapping in list List, which should be a list of Key-Value pairs. List should not contain more than one entry for each distinct key, but this is not validated by ord_list_to_rbtree/2. List is assumed to be sorted according to the standard order of terms.
 rb_size(+Tree, -Size) is det
Size is the number of elements in Tree.
 is_rbtree(@Term) is semidet
True if Term is a valid Red-Black tree. Processes the entire tree, checking the coloring of the nodes, the balance and the ordering of keys. Does not validate that keys are sufficiently instantiated to ensure the tree remains valid if a key is further instantiated.

Undocumented predicates

The following predicates are exported, but not or incorrectly documented.

 rb_get(Arg1, Arg2, Arg3, Arg4)
 rb_upd(Arg1, Arg2, Arg3, Arg4, Arg5)
 rb_app(Arg1, Arg2, Arg3, Arg4)
 rb_add(Arg1, Arg2, Arg3, Arg4)
 rb_upd_or_ins(Arg1, Arg2, Arg3, Arg4)
 rb_app_or_new(Arg1, Arg2, Arg3, Arg4, Arg5)