interval_set.h File Reference

Go to the source code of this file.

Data Structures
struct	cvx_container
struct	interval_set_vtabv
struct	interval_set_entry
struct	interval_set
struct	interval_set_iter

Typedefs
typedef struct cvx_container	cvx_container

Enumerations
enum	cvx_flags {   CVX_FLAG_OK = 0 , CVX_FLAG_VTAB = 1 , CVX_FLAG_WRONG_TAG = 2 , CVX_FLAG_ALLOC = 3 ,   CVX_FLAG_EMPTY = 4 , CVX_FLAG_FULL = 5 , CVX_FLAG_RANGE = 6 , CVX_FLAG_NOT_FOUND = 7 ,   CVX_FLAG_INVALID = 8 , CVX_FLAG_DUPLICATE = 9 , CVX_FLAG_ERROR = 10 }
	interval_set.h More...
enum	cvx_heap_order { CVX_MAX_HEAP = 1 , CVX_MIN_HEAP = -1 }
	enum cvx_heap_order More...

Functions
void	is_init (struct interval_set *self, struct interval_set_vtabv *vtabv)
	IMPLEMENTATIONS.
void	is_clone (struct interval_set *orig, struct interval_set *clone)
void	is_drop (struct interval_set *_self_)
enum cvx_flags	is_flag (struct interval_set *_self_)
size_t	is_count (struct interval_set *_self_)
_Bool	is_empty (struct interval_set *_self_)
void	is_add (struct interval_set *_self_, TVal _lo_, TVal _hi_)
void	is_remove (struct interval_set *_self_, TVal _lo_, TVal _hi_)
_Bool	is_contains (struct interval_set *_self_, TVal _val_)
	Returns true if val is covered by any interval in the set, i.e.
_Bool	is_contains_interval (struct interval_set *_self_, TVal _lo_, TVal _hi_)
	Returns true if the interval [lo, hi) is fully covered by a single stored interval, i.e.
_Bool	is_overlaps (struct interval_set *_self_, TVal _lo_, TVal _hi_)
	Returns true if [lo, hi) has a non-empty intersection with any interval in the set.
struct interval_set *	is_union (struct interval_set *_left_, struct interval_set *_right_)
	Returns a new set containing all intervals from left and right (A ∪ B).
struct interval_set *	is_intersect (struct interval_set *_left_, struct interval_set *_right_)
	Returns a new set containing only intervals covered by both left and right (A ∩ B).
struct interval_set *	is_diff (struct interval_set *_left_, struct interval_set *_right_)
	Returns a new set of intervals in left that are not covered by right (A \ B).
struct interval_set *	is_symdiff (struct interval_set *_left_, struct interval_set *_right_)
	Returns a new set of intervals covered by exactly one of left or right ((A \ B) ∪ (B \ A)).
struct interval_set *	is_compl (struct interval_set *_self_, TVal _lo_, TVal _hi_)
	Returns a new set representing the complement of self within the universe [lo, hi).
struct interval_set_iter	is_iter_init_start (struct interval_set *_target_)
	ITERATOR.
struct interval_set_iter	is_iter_init_end (struct interval_set *_target_)
struct interval_set_iter *	is_iter_start (struct interval_set *_target_)
struct interval_set_iter *	is_iter_end (struct interval_set *_target_)
void	is_iter_drop (struct interval_set_iter *_iter_)
_Bool	is_iter_at_start (struct interval_set_iter *_iter_)
_Bool	is_iter_at_end (struct interval_set_iter *_iter_)
size_t	is_iter_count (struct interval_set_iter *_iter_)
void	is_iter_to_start (struct interval_set_iter *_iter_)
void	is_iter_to_end (struct interval_set_iter *_iter_)
void	is_iter_next (struct interval_set_iter *_iter_)
void	is_iter_prev (struct interval_set_iter *_iter_)
void	is_iter_forward (struct interval_set_iter *_iter_, size_t _steps_)
void	is_iter_backward (struct interval_set_iter *_iter_, size_t _steps_)
struct interval_set_entry	is_iter_entry (struct interval_set_iter *_iter_)
TVal	is_iter_value_lo (struct interval_set_iter *_iter_)
TVal	is_iter_value_hi (struct interval_set_iter *_iter_)
size_t	is_iter_index (struct interval_set_iter *_iter_)
_Bool	is__assert_capacity (struct interval_set *_self_)
	PRIVATE FUNCTIONS.
size_t	is__lower_bound (struct interval_set *_self_, TVal _lo_)
_Bool	is__append (struct interval_set *_self_, TVal _lo_, TVal _hi_)
void	is__proxy_clone (cvx_container *_orig_, cvx_container *_clone_)
	PROXIES.
void	is__proxy_drop (cvx_container *_col_)
size_t	is__proxy_count (cvx_container *_col_)
_Bool	is__proxy_empty (cvx_container *_col_)
void	is__proxy_add (cvx_container *_col_, TVal _lo_, TVal _hi_)
void	is__proxy_remove (cvx_container *_col_, TVal _lo_, TVal _hi_)
_Bool	is__proxy_contains (cvx_container *_col_, TVal _val_)
_Bool	is__proxy_contains_interval (cvx_container *_col_, TVal _lo_, TVal _hi_)
_Bool	is__proxy_overlaps (cvx_container *_col_, TVal _lo_, TVal _hi_)
cvx_container *	is__proxy_union (cvx_container *_l_, cvx_container *_r_)
cvx_container *	is__proxy_intersect (cvx_container *_l_, cvx_container *_r_)
cvx_container *	is__proxy_diff (cvx_container *_l_, cvx_container *_r_)
cvx_container *	is__proxy_symdiff (cvx_container *_l_, cvx_container *_r_)
cvx_container *	is__proxy_compl (cvx_container *_col_, TVal _lo_, TVal _hi_)
cvx_container *	is__proxy_iter_start (cvx_container *_col_)
cvx_container *	is__proxy_iter_end (cvx_container *_col_)
void	is__proxy_iter_drop (cvx_container *_col_)
_Bool	is__proxy_iter_at_start (cvx_container *_col_)
_Bool	is__proxy_iter_at_end (cvx_container *_col_)
size_t	is__proxy_iter_count (cvx_container *_col_)
void	is__proxy_iter_to_start (cvx_container *_col_)
void	is__proxy_iter_to_end (cvx_container *_col_)
void	is__proxy_iter_next (cvx_container *_col_)
void	is__proxy_iter_prev (cvx_container *_col_)
void	is__proxy_iter_forward (cvx_container *_col_, size_t _steps_)
void	is__proxy_iter_backward (cvx_container *_col_, size_t _steps_)
struct interval_set_entry	is__proxy_iter_entry (cvx_container *_col_)
TVal	is__proxy_iter_value_lo (cvx_container *_col_)
TVal	is__proxy_iter_value_hi (cvx_container *_col_)
size_t	is__proxy_iter_index (cvx_container *_col_)

Typedef Documentation

cvx_container

typedef struct cvx_container cvx_container

Enumeration Type Documentation

cvx_flags

enum cvx_flags

interval_set.h

Status

[x] concept [ ] v1 [ ] tests [ ] refine [ ] stabilize

Interval set with right-open intervals [lo, hi).

Status and error flags for the CVX library.

Error Handling

Enumerator
CVX_FLAG_OK	No errors.
CVX_FLAG_VTAB	Required vtab function was not provided.
CVX_FLAG_WRONG_TAG	Tags are checked so you don't pass the wrong struct to a function.
CVX_FLAG_ALLOC	Allocation failed.
CVX_FLAG_EMPTY	Operation can not proceed because the container is empty.
CVX_FLAG_FULL	When a container that doesn't resize is full.
CVX_FLAG_RANGE	Index out of range.
CVX_FLAG_NOT_FOUND	Key or value not found.
CVX_FLAG_INVALID	Invalid argument or operation.
CVX_FLAG_DUPLICATE	Duplicate key or value.
CVX_FLAG_ERROR	Generic error, or unknown error.

cvx_heap_order

enum cvx_heap_order

enum cvx_heap_order

Defines the two possible heaps:

• Max Heap has the greatest element at the top
• Min Heap has the smallest element at the top

Enumerator
CVX_MAX_HEAP
CVX_MIN_HEAP

Function Documentation

is__append()

_Bool is__append	(	struct interval_set *	_self_,
		TVal	_lo_,
		TVal	_hi_
	)

is__assert_capacity()

_Bool is__assert_capacity

(

struct interval_set *

_self_

)

PRIVATE FUNCTIONS.

is__lower_bound()

size_t is__lower_bound	(	struct interval_set *	_self_,
		TVal	_lo_
	)

is__proxy_add()

void is__proxy_add	(	cvx_container *	_col_,
		TVal	_lo_,
		TVal	_hi_
	)

is__proxy_clone()

void is__proxy_clone	(	cvx_container *	_orig_,
		cvx_container *	_clone_
	)

PROXIES.

is__proxy_compl()

cvx_container * is__proxy_compl	(	cvx_container *	_col_,
		TVal	_lo_,
		TVal	_hi_
	)

is__proxy_contains()

_Bool is__proxy_contains	(	cvx_container *	_col_,
		TVal	_val_
	)

is__proxy_contains_interval()

_Bool is__proxy_contains_interval	(	cvx_container *	_col_,
		TVal	_lo_,
		TVal	_hi_
	)

is__proxy_count()

size_t is__proxy_count

(

cvx_container *

_col_

)

is__proxy_diff()

cvx_container * is__proxy_diff	(	cvx_container *	_l_,
		cvx_container *	_r_
	)

is__proxy_drop()

void is__proxy_drop

(

cvx_container *

_col_

)

is__proxy_empty()

_Bool is__proxy_empty

(

cvx_container *

_col_

)

is__proxy_intersect()

cvx_container * is__proxy_intersect	(	cvx_container *	_l_,
		cvx_container *	_r_
	)

is__proxy_iter_at_end()

_Bool is__proxy_iter_at_end

(

cvx_container *

_col_

)

is__proxy_iter_at_start()

_Bool is__proxy_iter_at_start

(

cvx_container *

_col_

)

is__proxy_iter_backward()

void is__proxy_iter_backward	(	cvx_container *	_col_,
		size_t	_steps_
	)

is__proxy_iter_count()

size_t is__proxy_iter_count

(

cvx_container *

_col_

)

is__proxy_iter_drop()

void is__proxy_iter_drop

(

cvx_container *

_col_

)

is__proxy_iter_end()

cvx_container * is__proxy_iter_end

(

cvx_container *

_col_

)

is__proxy_iter_entry()

struct interval_set_entry is__proxy_iter_entry

(

cvx_container *

_col_

)

is__proxy_iter_forward()

void is__proxy_iter_forward	(	cvx_container *	_col_,
		size_t	_steps_
	)

is__proxy_iter_index()

size_t is__proxy_iter_index

(

cvx_container *

_col_

)

is__proxy_iter_next()

void is__proxy_iter_next

(

cvx_container *

_col_

)

is__proxy_iter_prev()

void is__proxy_iter_prev

(

cvx_container *

_col_

)

is__proxy_iter_start()

cvx_container * is__proxy_iter_start

(

cvx_container *

_col_

)

is__proxy_iter_to_end()

void is__proxy_iter_to_end

(

cvx_container *

_col_

)

is__proxy_iter_to_start()

void is__proxy_iter_to_start

(

cvx_container *

_col_

)

is__proxy_iter_value_hi()

TVal is__proxy_iter_value_hi

(

cvx_container *

_col_

)

is__proxy_iter_value_lo()

TVal is__proxy_iter_value_lo

(

cvx_container *

_col_

)

is__proxy_overlaps()

_Bool is__proxy_overlaps	(	cvx_container *	_col_,
		TVal	_lo_,
		TVal	_hi_
	)

is__proxy_remove()

void is__proxy_remove	(	cvx_container *	_col_,
		TVal	_lo_,
		TVal	_hi_
	)

is__proxy_symdiff()

cvx_container * is__proxy_symdiff	(	cvx_container *	_l_,
		cvx_container *	_r_
	)

is__proxy_union()

cvx_container * is__proxy_union	(	cvx_container *	_l_,
		cvx_container *	_r_
	)

is_add()

void is_add	(	struct interval_set *	_self_,
		TVal	_lo_,
		TVal	_hi_
	)

is_clone()

void is_clone	(	struct interval_set *	orig,
		struct interval_set *	clone
	)

is_compl()

struct interval_set * is_compl	(	struct interval_set *	_self_,
		TVal	_lo_,
		TVal	_hi_
	)

Returns a new set representing the complement of self within the universe [lo, hi).

self is left unchanged. Returns NULL on allocation failure. Returns an empty set if lo >= hi.

is_contains()

_Bool is_contains	(	struct interval_set *	_self_,
		TVal	_val_
	)

Returns true if val is covered by any interval in the set, i.e.

there exists [lo, hi) such that lo <= val < hi. The hi endpoint is excluded (right-open). Sets flag to CVX_FLAG_OK on success.

is_contains_interval()

_Bool is_contains_interval	(	struct interval_set *	_self_,
		TVal	_lo_,
		TVal	_hi_
	)

Returns true if the interval [lo, hi) is fully covered by a single stored interval, i.e.

there exists [a, b) such that a <= lo and hi <= b. Returns false for an empty query interval (lo >= hi). Sets flag to CVX_FLAG_OK on success.

is_count()

size_t is_count

(

struct interval_set *

_self_

)

is_diff()

struct interval_set * is_diff	(	struct interval_set *	_left_,
		struct interval_set *	_right_
	)

Returns a new set of intervals in left that are not covered by right (A \ B).

Both operands are left unchanged. Returns NULL on allocation failure.

is_drop()

void is_drop

(

struct interval_set *

_self_

)

is_empty()

_Bool is_empty

(

struct interval_set *

_self_

)

is_flag()

enum cvx_flags is_flag

(

struct interval_set *

_self_

)

is_init()

void is_init	(	struct interval_set *	self,
		struct interval_set_vtabv *	vtabv
	)

IMPLEMENTATIONS.

is_intersect()

struct interval_set * is_intersect	(	struct interval_set *	_left_,
		struct interval_set *	_right_
	)

Returns a new set containing only intervals covered by both left and right (A ∩ B).

Both operands are left unchanged. Returns NULL on allocation failure.

is_iter_at_end()

_Bool is_iter_at_end

(

struct interval_set_iter *

_iter_

)

is_iter_at_start()

_Bool is_iter_at_start

(

struct interval_set_iter *

_iter_

)

is_iter_backward()

void is_iter_backward	(	struct interval_set_iter *	_iter_,
		size_t	_steps_
	)

is_iter_count()

size_t is_iter_count

(

struct interval_set_iter *

_iter_

)

is_iter_drop()

void is_iter_drop

(

struct interval_set_iter *

_iter_

)

is_iter_end()

struct interval_set_iter * is_iter_end

(

struct interval_set *

_target_

)

is_iter_entry()

struct interval_set_entry is_iter_entry

(

struct interval_set_iter *

_iter_

)

is_iter_forward()

void is_iter_forward	(	struct interval_set_iter *	_iter_,
		size_t	_steps_
	)

is_iter_index()

size_t is_iter_index

(

struct interval_set_iter *

_iter_

)

is_iter_init_end()

struct interval_set_iter is_iter_init_end

(

struct interval_set *

_target_

)

is_iter_init_start()

struct interval_set_iter is_iter_init_start

(

struct interval_set *

_target_

)

ITERATOR.

is_iter_next()

void is_iter_next

(

struct interval_set_iter *

_iter_

)

is_iter_prev()

void is_iter_prev

(

struct interval_set_iter *

_iter_

)

is_iter_start()

struct interval_set_iter * is_iter_start

(

struct interval_set *

_target_

)

is_iter_to_end()

void is_iter_to_end

(

struct interval_set_iter *

_iter_

)

is_iter_to_start()

void is_iter_to_start

(

struct interval_set_iter *

_iter_

)

is_iter_value_hi()

TVal is_iter_value_hi

(

struct interval_set_iter *

_iter_

)

is_iter_value_lo()

TVal is_iter_value_lo

(

struct interval_set_iter *

_iter_

)

is_overlaps()

_Bool is_overlaps	(	struct interval_set *	_self_,
		TVal	_lo_,
		TVal	_hi_
	)

Returns true if [lo, hi) has a non-empty intersection with any interval in the set.

Touching intervals (hi of stored == lo of query, or vice-versa) do NOT count as overlapping under right-open semantics. Returns false for an empty query interval (lo >= hi). Sets flag to CVX_FLAG_OK on success.

is_remove()

void is_remove	(	struct interval_set *	_self_,
		TVal	_lo_,
		TVal	_hi_
	)

is_symdiff()

struct interval_set * is_symdiff	(	struct interval_set *	_left_,
		struct interval_set *	_right_
	)

Returns a new set of intervals covered by exactly one of left or right ((A \ B) ∪ (B \ A)).

Both operands are left unchanged. Returns NULL on allocation failure.

is_union()

struct interval_set * is_union	(	struct interval_set *	_left_,
		struct interval_set *	_right_
	)

Returns a new set containing all intervals from left and right (A ∪ B).

Both operands are left unchanged. Returns NULL on allocation failure.