cucon/ucset.h: Constructive Integer Sets
[Associative Containers (trees, maps, sets)]

Data Structures
struct	cucon_ucset_itr
Functions
cu_bool_t	cucon_ucset_eq (cucon_ucset_t set0, cucon_ucset_t set1)
cu_bool_t	cucon_ucset_subeq (cucon_ucset_t set0, cucon_ucset_t set1)
cu_bool_t	cucon_ucset_disjoint (cucon_ucset_t set0, cucon_ucset_t set1)
cucon_ucset_t	cucon_ucset_empty (void)
cu_bool_t	cucon_ucset_is_empty (cucon_ucset_t set)
cucon_ucset_t	cucon_ucset_singleton (uintptr_t key)
cu_bool_t	cucon_ucset_is_singleton (cucon_ucset_t set)
cucon_ucset_t	cucon_ucset_insert (cucon_ucset_t set, uintptr_t key)
cucon_ucset_t	cucon_ucset_erase (cucon_ucset_t set, uintptr_t key)
cucon_ucset_t	cucon_ucset_union (cucon_ucset_t set0, cucon_ucset_t set1)
cucon_ucset_t	cucon_ucset_isecn (cucon_ucset_t set0, cucon_ucset_t set1)
cucon_ucset_t	cucon_ucset_compl (cucon_ucset_t set0, cucon_ucset_t set1)
cu_bool_t	cucon_ucset_find (cucon_ucset_t set, uintptr_t key)
cu_bool_t	cucon_ucset_conj (cucon_ucset_t set, cu_clop(cb, cu_bool_t, uintptr_t key))
void	cucon_ucset_iter (cucon_ucset_t set, cu_clop(f, void, uintptr_t))
size_t	cucon_ucset_card (cucon_ucset_t set)
uintptr_t	cucon_ucset_umin (cucon_ucset_t set)
uintptr_t	cucon_ucset_umax (cucon_ucset_t set)
intptr_t	cucon_ucset_smin (cucon_ucset_t set)
intptr_t	cucon_ucset_smax (cucon_ucset_t set)
cucon_ucset_t	cucon_ucset_filter (cucon_ucset_t set, cu_clop(f, cu_bool_t, uintptr_t))
cucon_ucset_t	cucon_ucset_image (cucon_ucset_t set, cu_clop(f, uintptr_t, uintptr_t))
cucon_ucset_t	cucon_ucset_filter_image (cucon_ucset_t set, cu_clop(f, cu_bool_t, uintptr_t *))
cucon_ucset_t	cucon_ucset_uclip (cucon_ucset_t set, uintptr_t clip_min, uintptr_t clip_max)
cucon_ucset_t	cucon_ucset_sclip (cucon_ucset_t set, intptr_t clip_min, intptr_t clip_max)
cucon_ucset_t	cucon_ucset_translate_uclip (cucon_ucset_t set, intptr_t diff, uintptr_t clip_min, uintptr_t clip_max)
cucon_ucset_t	cucon_ucset_translate_sclip (cucon_ucset_t set, intptr_t diff, intptr_t clip_min, intptr_t clip_max)
cucon_ucset_t	cucon_ucset_translate (cucon_ucset_t set, intptr_t diff)
void	cucon_ucset_fprint_uintptr (cucon_ucset_t set, FILE *out)
void	cucon_ucset_fprint_intptr (cucon_ucset_t set, FILE *out)
void	cucon_ucset_dump (cucon_ucset_t set, FILE *out)
size_t	cucon_ucset_itr_size (cucon_ucset_t set)
void	cucon_ucset_itr_init (cucon_ucset_itr_t itr, cucon_ucset_t set)
cucon_ucset_itr_t	cucon_ucset_itr_new (cucon_ucset_t set)
cu_bool_t	cucon_ucset_itr_at_end (cucon_ucset_itr_t itr)
uintptr_t	cucon_ucset_itr_get (cucon_ucset_itr_t itr)

---

Detailed Description

This provides constructive tests of integers, implemented as a trie of bitsets. It is thus suitable to represent both sparse and dense sets. The main features are

• O(1) copy since modifications are non-destructive
• Search and insert complexity ranges from O(log n) on avarage for containers of n random numbers, to O(n) for some patological cases like of containers with n powers of two. The patological cases are limited by the range of integers. For instance, on a 32 bit platform, n ≤ 32 - log₂ 64 = 26. (log₂ 64 comes from the 64-element bitsets at the leaves.)

See also:

cucon/ucmap.h: Maps with a similar implementation.

cucon/pmap.h: This hash map can also be used as a set.

---

Function Documentation

size_t cucon_ucset_card

(

cucon_ucset_t

set

)

Returns the cardinality of set.

cucon_ucset_t cucon_ucset_compl	(	cucon_ucset_t	set0,
		cucon_ucset_t	set1
	)

Returns set0 ∖ set1.

cu_bool_t cucon_ucset_conj	(	cucon_ucset_t	set,
		cu_clop(cb, cu_bool_t, uintptr_t key)
	)

Sequential conjunction over elements in increasing order.

cu_bool_t cucon_ucset_disjoint	(	cucon_ucset_t	set0,
		cucon_ucset_t	set1
	)

True iff set0 ∩ set1 = ∅.

void cucon_ucset_dump	(	cucon_ucset_t	set,
		FILE *	out
	)

Debug dump of set.

cucon_ucset_t cucon_ucset_empty

(

void

)

Returs the empty set (NULL).

cu_bool_t cucon_ucset_eq	(	cucon_ucset_t	set0,
		cucon_ucset_t	set1
	)

True iff set0 and set1 contains exactly the same elements.

cucon_ucset_t cucon_ucset_erase	(	cucon_ucset_t	set,
		uintptr_t	key
	)

Returns set ∖ {key}.

cucon_ucset_t cucon_ucset_filter	(	cucon_ucset_t	set,
		cu_clop(f, cu_bool_t, uintptr_t)
	)

Returns {x | x ∈ set ∧ f(x)}.

cucon_ucset_t cucon_ucset_filter_image	(	cucon_ucset_t	set,
		cu_clop(f, cu_bool_t, uintptr_t *)
	)

Combines cucon_ucset_filter and cucon_ucset_image in one operation. f is passed a pointer to each key in set. If it returns false, the element is skipped, otherwise the key at the pointer passed to f, which may be modified by f, is included in the result.

cu_bool_t cucon_ucset_find	(	cucon_ucset_t	set,
		uintptr_t	key
	)

True iff key ∈ set.

void cucon_ucset_fprint_intptr	(	cucon_ucset_t	set,
		FILE *	out
	)

Print set to out as a set of signed integers using normal set notation.

void cucon_ucset_fprint_uintptr	(	cucon_ucset_t	set,
		FILE *	out
	)

Print set to out as a set of unsigend integers using normal set notation.

cucon_ucset_t cucon_ucset_image	(	cucon_ucset_t	set,
		cu_clop(f, uintptr_t, uintptr_t)
	)

Returns {f(x) | x ∈ set}.

cucon_ucset_t cucon_ucset_insert	(	cucon_ucset_t	set,
		uintptr_t	key
	)

Return set with key inserted.

cu_bool_t cucon_ucset_is_empty

(

cucon_ucset_t

set

)

True iff set is the empty set.

cu_bool_t cucon_ucset_is_singleton

(

cucon_ucset_t

set

)

True iff set is a singleton set.

cucon_ucset_t cucon_ucset_isecn	(	cucon_ucset_t	set0,
		cucon_ucset_t	set1
	)

Returns set0 ∩ set1.

void cucon_ucset_iter	(	cucon_ucset_t	set,
		cu_clop(f, void, uintptr_t)
	)

Calls f for each element of set.

cu_bool_t cucon_ucset_itr_at_end

(

cucon_ucset_itr_t

itr

)

True iff itr is past the last element.

uintptr_t cucon_ucset_itr_get

(

cucon_ucset_itr_t

itr

)

Returns and advances over the next element of itr.

void cucon_ucset_itr_init	(	cucon_ucset_itr_t	itr,
		cucon_ucset_t	set
	)

Initialises itr for iteration over set. The memory at itr must be at least the size reported by cucon_ucset_itr_size(set).

cucon_ucset_itr_t cucon_ucset_itr_new

(

cucon_ucset_t

set

)

Returns an iterator over the elements of set.

size_t cucon_ucset_itr_size

(

cucon_ucset_t

set

)

Returns the size needed and interator over the elements of set.

cucon_ucset_t cucon_ucset_sclip	(	cucon_ucset_t	set,
		intptr_t	clip_min,
		intptr_t	clip_max
	)

Returns set ∩ [clip_min, clip_max], using signed comparison.

cucon_ucset_t cucon_ucset_singleton

(

uintptr_t

key

)

Returns the singleton set {key}.

intptr_t cucon_ucset_smax

(

cucon_ucset_t

set

)

Returns the maximum element of set, using signed comparison.

intptr_t cucon_ucset_smin

(

cucon_ucset_t

set

)

Returns the minimum element of set, using signed comparison.

cu_bool_t cucon_ucset_subeq	(	cucon_ucset_t	set0,
		cucon_ucset_t	set1
	)

True iff set0 ⊆ set1.

cucon_ucset_t cucon_ucset_translate	(	cucon_ucset_t	set,
		intptr_t	diff
	)

Returns the set {x + diff | x ∈ set}.

cucon_ucset_t cucon_ucset_translate_sclip	(	cucon_ucset_t	set,
		intptr_t	diff,
		intptr_t	clip_min,
		intptr_t	clip_max
	)

Returns the set {x + diff | x ∈ set ∧ clip_min ≤ x ≤ clip_max}.

cucon_ucset_t cucon_ucset_translate_uclip	(	cucon_ucset_t	set,
		intptr_t	diff,
		uintptr_t	clip_min,
		uintptr_t	clip_max
	)

Returns the set {x + diff | x ∈ set ∧ clip_min ≤ x ≤ clip_max}.

cucon_ucset_t cucon_ucset_uclip	(	cucon_ucset_t	set,
		uintptr_t	clip_min,
		uintptr_t	clip_max
	)

Returns set ∩ [clip_min, clip_max], using unsigned comparison.

uintptr_t cucon_ucset_umax

(

cucon_ucset_t

set

)

Returns the maximum element of set, using unsigned comparison.

uintptr_t cucon_ucset_umin

(

cucon_ucset_t

set

)

Returns the minimum element of set, using unsigned comparison.

cucon_ucset_t cucon_ucset_union	(	cucon_ucset_t	set0,
		cucon_ucset_t	set1
	)

Returns set0 ∪ set1.