cuex/atree.h: Associative Trees of Expressions
[cuex: Expressions]

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))

Detailed Description

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.


Function Documentation

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.

cu_bool_t cuex_atree_conj ( cuex_t  tree,
cu_clop(f, cu_bool_t, cuex_t leaf)   
)

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.

cu_bool_t cuex_atree_conj_kv ( cuex_t  tree,
cu_clop(f, cu_bool_t, cuex_t key, cuex_t val)   
)

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.

cuex_t cuex_atree_erase ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree,
cu_word_t  erase_key 
)

If erase_key is in tree, returns tree with the value corresponding to erase_key erased, otherwise returns tree.

cuex_t cuex_atree_find ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree,
cu_word_t  key 
)

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.

size_t cuex_atree_find_index ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree,
cu_word_t  key 
)

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.

cuex_t cuex_atree_insert ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree,
cuex_t  value 
)

If the key of value is not already in tree, returns the result of inserting value into tree, else returns tree.

cu_bool_t cuex_atree_is_empty ( cuex_t  tree  ) 

True iff tree is the empty container.

cu_bool_t cuex_atree_is_empty_or_singleton ( cuex_t  tree  ) 

True iff tree is te empty tree or a singleton.

cu_bool_t cuex_atree_is_singleton ( cuex_t  tree  ) 

True iff tree is a singleton.

cuex_t cuex_atree_isokey_image ( cuex_t  tree,
cu_clop(f, cuex_t, cuex_t leaf)   
)

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.

cuex_t cuex_atree_isokey_image_kv ( cuex_t  tree,
cu_clop(f, cuex_t, cuex_t key, cuex_t val)   
)

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.

void cuex_atree_iter ( cuex_t  tree,
cu_clop(f, void, cuex_t leaf)   
)

Call f with each value in tree.

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.

cuex_t cuex_atree_left_isecn ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree0,
cuex_t  tree1 
)

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.

cuex_t cuex_atree_left_union ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree0,
cuex_t  tree1 
)

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.

cuex_t cuex_atree_replace ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree,
cuex_t  value 
)

If the key of value is in tree, then replace the element with value, otherwise insert value.

cu_bool_t cuex_atree_subseteq ( cu_clop(get_key, cu_word_t, cuex_t ,
cuex_t  tree0,
cuex_t  tree1 
)

True iff tree0tree1 where elements are considered equal iff their get_key values are equal.

Generated 2009-11-23 for culibs-0.25 using Doxygen. Maintained by Petter Urkedal.