Functions | |
| cuoo_type_t | cuex_anode_type () |
| cuex_t | cuex_atree_empty () |
| cu_bool_t | cuex_atree_is_empty (cuex_t tree) |
| cuex_t | cuex_atree_singleton (cuex_t e) |
| cu_bool_t | cuex_atree_is_singleton (cuex_t tree) |
| cu_bool_t | cuex_atree_is_empty_or_singleton (cuex_t tree) |
| cuex_t | cuex_atree_find (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree, cu_word_t key) |
| size_t | cuex_atree_find_index (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree, cu_word_t key) |
| cuex_t | cuex_atree_insert (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree, cuex_t value) |
| cuex_t | cuex_atree_replace (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree, cuex_t value) |
| cuex_t | cuex_atree_deep_insert (cu_clop(get_key, cu_word_t, cuex_t leaf), cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1), cuex_t tree, cuex_t value) |
| cuex_t | cuex_atree_erase (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree, cu_word_t erase_key) |
| cuex_t | cuex_atree_find_erase (cu_clop(get_key, cu_word_t, cuex_t), cuex_t *tree, cu_word_t erase_key) |
| cuex_t | cuex_atree_left_union (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cuex_t | cuex_atree_disjoint_union (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cuex_t | cuex_atree_deep_union (cu_clop(get_key, cu_word_t, cuex_t), cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1), cuex_t tree0, cuex_t tree1) |
| cuex_t | cuex_atree_left_isecn (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cuex_t | cuex_atree_deep_isecn (cu_clop(get_key, cu_word_t, cuex_t), cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1), cuex_t tree0, cuex_t tree1) |
| cu_bool_t | cuex_atree_subseteq (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cu_bool_t | cuex_atree_deep_subseteq (cu_clop(get_key, cu_word_t, cuex_t), cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cu_order_t | cuex_atree_order (cu_clop(get_key, cu_word_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cu_order_t | cuex_atree_deep_order (cu_clop(get_key, cu_word_t, cuex_t), cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t), cu_clop(value_order, cu_order_t, cuex_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| void | cuex_atree_iter (cuex_t tree, cu_clop(f, void, cuex_t leaf)) |
| cu_bool_t | cuex_atree_conj (cuex_t tree, cu_clop(f, cu_bool_t, cuex_t leaf)) |
| cuex_t | cuex_atree_image (cuex_t tree, cu_clop(f, cuex_t, cuex_t), cu_clop(get_key, cu_word_t, cuex_t leaf)) |
| cuex_t | cuex_atree_isokey_image (cuex_t tree, cu_clop(f, cuex_t, cuex_t leaf)) |
| int | cuex_atree_depth (cuex_t tree) |
| size_t | cuex_atree_card (cuex_t tree) |
Iterator Support | |
The following can be used to implement iterators for expression types defined in terms of associated trees. | |
| size_t | cuex_atree_itr_size (cuex_t tree) |
| void | cuex_atree_itr_init (void *itr, cuex_t tree) |
| cuex_t | cuex_atree_itr_get (void *itr) |
| cuex_t | cuex_atree_itr_get_at_1 (void *itr) |
Specialisations Acting on a Certain Operand of the Members | |
The following functions are specialised variants of the corresponding functions from the primary API, where the leafs are assumed to be operations of sufficient arity, and callbacks acting on leaves are replaced by callbacks acting on a given operand of the leaves. The caller is responsible of ensuring that all leafs have the proper form. | |
| cuex_t | cuex_atree_deep_insert_iv (cu_clop(get_key, cu_word_t, cuex_t), cu_rank_t merge_index, cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1), cuex_t tree, cuex_t value) |
| cuex_t | cuex_atree_deep_union_iv (cu_clop(get_key, cu_word_t, cuex_t), cu_rank_t merge_index, cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1), cuex_t tree0, cuex_t tree1) |
| cuex_t | cuex_atree_deep_isecn_iv (cu_clop(get_key, cu_word_t, cuex_t), cu_rank_t merge_index, cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1), cuex_t tree0, cuex_t tree1) |
| cu_order_t | cuex_atree_deep_order_iv (cu_clop(get_key, cu_word_t, cuex_t), cu_rank_t value_index, cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t), cu_clop(value_order, cu_order_t, cuex_t, cuex_t), cuex_t tree0, cuex_t tree1) |
| cu_bool_t | cuex_atree_conj_iv (cuex_t tree, cu_rank_t value_index, cu_clop(f, cu_bool_t, cuex_t val)) |
| cuex_t | cuex_atree_isokey_image_iv (cuex_t tree, cu_rank_t value_index, cu_clop(f, cuex_t, cuex_t val)) |
Specialisations for Key-Value Formed Members | |
The following functions are specialised variants of the corresponding functions from the primary API, where the leafs are assumed to be binary operations where the first operand serves as a key and the second operand serves as a value. Callbacks generally receive the key as the first argument and one or two values as the next arguments. | |
| cuex_t | cuex_atree_deep_insert_kv (cu_clop(merge, cuex_t, cuex_t key, cuex_t val0, cuex_t val1), cuex_t tree, cuex_t value) |
| cuex_t | cuex_atree_deep_union_kv (cu_clop(merge, cuex_t, cuex_t key, cuex_t val0, cuex_t val1), cuex_t tree0, cuex_t tree1) |
| cuex_t | cuex_atree_deep_isecn_kv (cu_clop(merge, cuex_t, cuex_t key, cuex_t val0, cuex_t val1), cuex_t tree0, cuex_t tree1) |
| cu_order_t | cuex_atree_deep_order_kv (cu_clop(value_subseteq, cu_bool_t, cuex_t key, cuex_t val0, cuex_t val1), cu_clop(value_order, cu_order_t, cuex_t key, cuex_t val0, cuex_t val1), cuex_t tree0, cuex_t tree1) |
| cu_bool_t | cuex_atree_conj_kv (cuex_t tree, cu_clop(f, cu_bool_t, cuex_t key, cuex_t val)) |
| cuex_t | cuex_atree_isokey_image_kv (cuex_t tree, cu_clop(f, cuex_t, cuex_t key, cuex_t val)) |
This is a low-level interface for implementing semi-lattices, sets, maps, and other collections of expressions which are keyed on a machine word computed form the expressions.
The internal structure of the tree is hidden. The leafs of the tree are the inserted expressions. Most of the functions below takes a get_key argument, which when passed a leaf node shall compute a cu_word_t typed key. Since cu_word_t is at least the size of pointers, to implement a set of hash-consed objects, cast the leaf value pointer to cu_word_t, and to implement a map, use a binary operation as leafs, and cast the first operand to cu_word_t. The same get_key must be used consistently when operating on the same tree, which also means that union and intersections can only be used on trees of the same get_key. A high-level interface will typically embed these trees in a top-level node and either use a fixed get_key or one stored on the top-level node.
| size_t cuex_atree_card | ( | cuex_t | tree | ) |
Cardinality (number of elements) of tree. Note that the complexity of this call is linear in the cardinality of tree.
Returns the conjunction af f applied to all keys in tree. Stops as soon as f returns false.
| cu_bool_t cuex_atree_conj_iv | ( | cuex_t | tree, | |
| cu_rank_t | value_index, | |||
| cu_clop(f, cu_bool_t, cuex_t val) | ||||
| ) |
A variant of cuex_atree_conj which expects elements to be operations of at least value_index + 1 operands, and calls f with operand value_index.
A variant of cuex_atree_conj which expects that elements are operations of at least 2 operands, and calls back f with the first two operands of the elements. This specialisation applies to implementations of map-like types such as labellings.
| cuex_t cuex_atree_deep_insert | ( | cu_clop(get_key, cu_word_t, cuex_t leaf) | , | |
| cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1) | , | |||
| cuex_t | tree, | |||
| cuex_t | value | |||
| ) |
As cuex_atree_insert, but if a key-equal element e is present in tree, replace it with merge_values(e, value).
| cuex_t cuex_atree_deep_insert_iv | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_rank_t | merge_index, | |||
| cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1) | , | |||
| cuex_t | tree, | |||
| cuex_t | value | |||
| ) |
As cuex_atree_deep_insert, but merge only operand merge_index of values.
| cuex_t cuex_atree_deep_insert_kv | ( | cu_clop(merge, cuex_t, cuex_t key, cuex_t val0, cuex_t val1) | , | |
| cuex_t | tree, | |||
| cuex_t | value | |||
| ) |
As cuex_atree_deep_insert, but assume leafs are key-value binary operations. merge receives the common first operand (key) and each of the second operands (values) and shall return the merged value.
| cuex_t cuex_atree_deep_isecn | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_left_isecn, but merge intersecting elements from tree0 and tree1 using merge_values.
| cuex_t cuex_atree_deep_isecn_iv | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_rank_t | merge_index, | |||
| cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_deep_isecn, but merge_fn only merges operand merge_index.
| cuex_t cuex_atree_deep_isecn_kv | ( | cu_clop(merge, cuex_t, cuex_t key, cuex_t val0, cuex_t val1) | , | |
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_deep_isecn, except it assumes the first operand of leaves are keys and the second oprand are values. merge receives the common keys and the two values to be merged.
| cu_order_t cuex_atree_deep_order | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t) | , | |||
| cu_clop(value_order, cu_order_t, cuex_t, cuex_t) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
A variant of cuex_atree_order which also takes into account value ordering. Whenever the keys of two elements are equal, either value_subseteq or value_order is used to determine their ordering. The latter function is used when one of the two possible orderings of the trees have been excluded. The use of two ordering callbacks is purely an optimisation which may be hidden by a high-level interface; either callback can be implemented in terms of the other.
| cu_order_t cuex_atree_deep_order_iv | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_rank_t | value_index, | |||
| cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t) | , | |||
| cu_clop(value_order, cu_order_t, cuex_t, cuex_t) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_deep_order, but only pass operand value_index of the leaves to the ordering functions.
| cu_order_t cuex_atree_deep_order_kv | ( | cu_clop(value_subseteq, cu_bool_t, cuex_t key, cuex_t val0, cuex_t val1) | , | |
| cu_clop(value_order, cu_order_t, cuex_t key, cuex_t val0, cuex_t val1) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_deep_order, but assume leafs are operations where the first operand are keys and the second are values. The common key and the values to compare are passed to the ordering functions.
| cu_bool_t cuex_atree_deep_subseteq | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_subseteq, except for any pair (e0, e1) of elements of (tree0, tree1) with equal keys, return false unless value_subseteq(e0, e1) returns true.
| cuex_t cuex_atree_deep_union | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_left_union, except merge any duplicate element with merge_values. If merge at some point returns NULL, the algorithm terminates and returns NULL.
| cuex_t cuex_atree_deep_union_iv | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cu_rank_t | merge_index, | |||
| cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1) | , | |||
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_deep_union, except that merge_fn only acts on operand merge_index of the leaves.
| cuex_t cuex_atree_deep_union_kv | ( | cu_clop(merge, cuex_t, cuex_t key, cuex_t val0, cuex_t val1) | , | |
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_deep_union, except that merge_fn only acts on the second operand of leafs and also receives the first operand (the key).
| int cuex_atree_depth | ( | cuex_t | tree | ) |
The depth of the deepest tree node of tree. The empty tree and singletons have depth 0. A tree node has depth one plus the maximum of the depths of its branches.
| cuex_t cuex_atree_disjoint_union | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
As cuex_atree_left_union except NULL is returned in case tree0 and tree1 coincides on any of their keys.
| cuex_t cuex_atree_empty | ( | ) |
An empty container.
If erase_key is in tree, returns tree with the value corresponding to erase_key erased, otherwise returns tree.
Find find_key in tree, assuming tree is keyed by get_key. Returns the matching element, i.e. the element e such that cu_call(get_key, e) equals find_key. Returns NULL if no such element exists.
| cuex_t cuex_atree_find_erase | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cuex_t * | tree, | |||
| cu_word_t | erase_key | |||
| ) |
If *tree has a node where get_key returns erase_key, updates *tree by removing this node and returns the node, otherwise returns NULL.
As cuex_atree_find, but returns the index of key, or (size_t)-1 if not found. Note that the complexity of this call is linear in the cardinality of tree.
| cuex_t cuex_atree_image | ( | cuex_t | tree, | |
| cu_clop(f, cuex_t, cuex_t) | , | |||
| cu_clop(get_key, cu_word_t, cuex_t leaf) | ||||
| ) |
Returns the image of tree under f. Note that get_key is only used for building the result, and may in fact be different from the get_key which was used to build tree (thus its order in the argument list). If f leaves the key of its argument unchanged, see cuex_atree_isokey_image for a faster alternative.
If the key of value is not already in tree, returns the result of inserting value into tree, else returns tree.
True iff tree is te empty tree or a singleton.
Returns the image of tree under f assuming f does not change the key of it's argument. The key referred to is the result of the get_key used to build the container cuex_atree_insert, so the condition is that get_key(f(e)) = get_key(e) for all elements e in tree. If this condition is not met see cuex_atree_image.
| cuex_t cuex_atree_isokey_image_iv | ( | cuex_t | tree, | |
| cu_rank_t | value_index, | |||
| cu_clop(f, cuex_t, cuex_t val) | ||||
| ) |
A variant of cuex_atree_isokey_image which assumes that elements are operations of arity at least value_index + 1, and transforms only operand value_index of the elements. This specialisation applies to map-like types with inert keys, such as labellings.
A variant of cuex_atree_isokey_image which assumes elements to be operations of arity at least 2, and transforms the second operand. Both the first and second operands are passed to f in order. This is suited for map-like types where the first operand is an inert key and the second operand is a transformable value.
| cuex_t cuex_atree_itr_get | ( | void * | itr | ) |
Pop off and return the next subtree from itr, or return NULL if itr is empty.
| cuex_t cuex_atree_itr_get_at_1 | ( | void * | itr | ) |
Pop off the next subtree from itr and return cucon_opn_at(subtree, 1), or return NULL if itr is empty.
| void cuex_atree_itr_init | ( | void * | itr, | |
| cuex_t | tree | |||
| ) |
Initialise an itr as an iterator over all elements of tree, where itr points to memory of at least cuex_atree_itr_size(tree) bytes.
| size_t cuex_atree_itr_size | ( | cuex_t | tree | ) |
The size required by an iterator over tree.
Returns the intersection of tree0 and tree1, considering two elements equal if the corresponding values returned by get_key are equal. The nodes from tree0 are used in the result.
Returns the union of tree0 and tree1, considering two elements equal if the corresponding values returned by get_key are equal. For common nodes, those from tree0 are used in the result.
| cu_order_t cuex_atree_order | ( | cu_clop(get_key, cu_word_t, cuex_t) | , | |
| cuex_t | tree0, | |||
| cuex_t | tree1 | |||
| ) |
Returns the ordering of tree0 and tree1, where elements are considered equal iff their get_key values are equal.
If the key of value is in tree, then replace the element with value, otherwise insert value.