cuex/ltree.h: Left-Packed Trees (Low-Level API)
[cuex: Expressions]

Data Structures
struct	cuex_ltree_node
struct	cuex_ltree_itr
Defines
#define	CUEX_LTREE_LOG2_FANOUT   2
#define	CUEX_LTREE_FANOUT   (1 << CUEX_LTREE_LOG2_FANOUT)
#define	CUEX_LTREE_FANOUT_MASK   (CUEX_LTREE_FANOUT - 1)
#define	CUEXP_OXR_LTREE(depth, arity)   (CUEXP_OR_LTREE(arity) | CUEXP_OA_LTREE_DEPTH(depth))
#define	CUEXP_OA_LTREE_DEPTH_MAXP   (1 << CUEXP_OA_LTREE_DEPTH_WIDTH)
#define	CUEX_LTREE_END   PTRDIFF_MAX
Typedefs
typedef struct cuex_ltree_itr	cuex_ltree_itr_t
Functions
cu_bool_t	cuex_is_oR_ltree (cuex_meta_t opr)
cuex_t	cuex_ltree_empty ()
cu_bool_t	cuex_ltree_is_empty (cuex_t tree)
cu_bool_t	cuex_ltree_is_singleton (cuex_t tree)
cu_bool_t	cuex_ltree_is_composite (cuex_t tree)
cu_bool_t	cuexP_is_ltree_node (cuex_t tree)
cuex_t	cuex_ltree_at (cuex_t tree, ptrdiff_t i)
cuex_t	cuex_ltree_last (cuex_t tree)
cuex_t	cuex_ltree_concat (cuex_t tree0, cuex_t tree1)
cuex_t	cuex_ltree_slice (cuex_t tree, ptrdiff_t start, ptrdiff_t end)
size_t	cuex_ltree_size (cuex_t tree)
cu_bool_t	cuex_ltree_forall (cu_clop(f, cu_bool_t, cuex_t), cuex_t tree)
void	cuex_ltree_itr_init_full (cuex_ltree_itr_t *itr, cuex_t tree)
void	cuex_ltree_itr_init_slice (cuex_ltree_itr_t *itr, cuex_t tree, ptrdiff_t start, ptrdiff_t end)
cu_bool_t	cuex_ltree_itr_is_end (cuex_ltree_itr_t *itr)
cuex_t	cuex_ltree_itr_get (cuex_ltree_itr_t *itr)
cu_ptr_source_t	cuex_ltree_full_source (cuex_t x)
cu_ptr_source_t	cuex_ltree_slice_source (cuex_t x, ptrdiff_t i, ptrdiff_t j)
cuex_t	cuex_ltree_from_valist (va_list vl)
cuex_t	cuex_ltree_from_source (cu_ptr_source_t source)
cuex_t	cuex_ltree_from_array (cuex_t *elt_array, size_t elt_count)
cuex_t	cuex_ltree_append_from_source (cuex_t tree0, cu_ptr_source_t source1)
cuex_t	cuex_ltree_append_from_array (cuex_t tree0, cuex_t *arr, size_t cnt)
void	cuex_ltree_fprint (FILE *out, cuex_t ltree, char const *fmt_init, char const *fmt_cont)
void	cuex_ltree_foprint (cufo_stream_t fos, cuex_t ltree, char const *fmt_init, char const *fmt_cont)

---

Detailed Description

This header implements a tree-based hash-consed container of expressions representing an sequence of elements. It is used to implement monoid expressions.

See also:

cuex/monoid.h: Monoid Operations

cuex/tmonoid.h: Monoid Operations with Tagged Generators

---

Define Documentation

#define CUEX_LTREE_END   PTRDIFF_MAX

Special value to indicate no end limit in slice functions.

---

Function Documentation

cuex_t cuex_ltree_at	(	cuex_t	tree,
		ptrdiff_t	i
	)

Returns element number i of tree.

Precondition:

tree must be non-empty and i must be within its range.

cuex_t cuex_ltree_concat	(	cuex_t	tree0,
		cuex_t	tree1
	)

Returns the concatenation of tree0 and tree1.

cuex_t cuex_ltree_empty

(

)

The empty tree.

cu_bool_t cuex_ltree_forall	(	cu_clop(f, cu_bool_t, cuex_t)	,
		cuex_t	tree
	)

Calls f on each element of tree sequentially as long as the result is true, and returns true iff f mapped all elements to true.

cu_bool_t cuex_ltree_is_empty

(

cuex_t

tree

)

True iff tree is the empty tree.

cuex_t cuex_ltree_itr_get

(

cuex_ltree_itr_t *

itr

)

If itr is at its end, returns NULL, else returns the next element of the sequence.

void cuex_ltree_itr_init_full	(	cuex_ltree_itr_t *	itr,
		cuex_t	tree
	)

Construct itr to iterate over all elements of tree.

void cuex_ltree_itr_init_slice	(	cuex_ltree_itr_t *	itr,
		cuex_t	tree,
		ptrdiff_t	start,
		ptrdiff_t	end
	)

Construct itr to iterate over elements start to end of tree. Relative indices are taken to be relative to the end.

cu_bool_t cuex_ltree_itr_is_end

(

cuex_ltree_itr_t *

itr

)

True iff itr is at the end of its range.

cuex_t cuex_ltree_last

(

cuex_t

tree

)

Returns the last element of tree.

Precondition:

tree must be non-empty.

size_t cuex_ltree_size

(

cuex_t

tree

)

Return the number of elements in tree.

cuex_t cuex_ltree_slice	(	cuex_t	tree,
		ptrdiff_t	start,
		ptrdiff_t	end
	)

Returns the slice of tree for indices [start, end). Negative indices are taken to be relative to the end.