26 #ifndef CDCONTAINERS_INCLUDE_CDCONTAINERS_TREAP_H 27 #define CDCONTAINERS_INCLUDE_CDCONTAINERS_TREAP_H 398 return it->
prev != NULL;
459 #ifdef CDC_USE_SHORT_NAMES 462 typedef struct cdc_pair_treap_iter pair_treap_iter_t;
466 #define treap_ctor(...) cdc_treap_ctor(__VA_ARGS__) 467 #define treap_ctorv(...) cdc_treap_ctorv(__VA_ARGS__) 468 #define treap_ctorl(...) cdc_treap_ctorl(__VA_ARGS__) 469 #define treap_ctor1(...) cdc_treap_ctor1(__VA_ARGS__) 470 #define treap_ctorv1(...) cdc_treap_ctorv1(__VA_ARGS__) 471 #define treap_ctorl1(...) cdc_treap_ctorl1(__VA_ARGS__) 472 #define treap_dtor(...) cdc_treap_dtor(__VA_ARGS__) 475 #define treap_get(...) cdc_treap_get(__VA_ARGS__) 476 #define treap_count(...) cdc_treap_count(__VA_ARGS__) 477 #define treap_find(...) cdc_treap_find(__VA_ARGS__) 480 #define treap_size(...) cdc_treap_size(__VA_ARGS__) 481 #define treap_empty(...) cdc_treap_empty(__VA_ARGS__) 484 #define treap_clear(...) cdc_treap_clear(__VA_ARGS__) 485 #define treap_insert(...) cdc_treap_insert(__VA_ARGS__) 486 #define treap_insert1(...) cdc_treap_insert1(__VA_ARGS__) 487 #define treap_insert_or_assign(...) cdc_treap_insert_or_assign(__VA_ARGS__) 488 #define treap_insert_or_assign1(...) cdc_treap_insert_or_assign1(__VA_ARGS__) 489 #define treap_erase(...) cdc_treap_erase(__VA_ARGS__) 490 #define treap_swap(...) cdc_treap_swap(__VA_ARGS__) 493 #define treap_begin(...) cdc_treap_begin(__VA_ARGS__) 494 #define treap_end(...) cdc_treap_end(__VA_ARGS__) 497 #define treap_iter_next(...) cdc_treap_iter_next(__VA_ARGS__) 498 #define treap_iter_has_next(...) cdc_treap_iter_has_next(__VA_ARGS__) 499 #define treap_iter_key(...) cdc_treap_iter_key(__VA_ARGS__) 500 #define treap_iter_value(...) cdc_treap_iter_value(__VA_ARGS__) 501 #define treap_iter_key_value(...) cdc_treap_iter_key_value(__VA_ARGS__) 502 #define treap_iter_is_eq(...) cdc_treap_iter_is_eq(__VA_ARGS__) 505 #endif // CDSTRUCTURES_INCLUDE_CDCONTAINERS_VECTOR_H void cdc_treap_end(struct cdc_treap *t, struct cdc_treap_iter *it)
Initializes the iterator to the end.
enum cdc_stat cdc_treap_insert(struct cdc_treap *t, void *key, void *value, struct cdc_pair_treap_iter_bool *ret)
Inserts an element into the container, if the container doesn't already contain an element with an eq...
void * key
Definition: treap.h:53
cdc_priority_fn_t prior
Definition: treap.h:66
bool second
Definition: treap.h:83
struct cdc_data_info * dinfo
Definition: treap.h:67
enum cdc_stat cdc_treap_get(struct cdc_treap *t, void *key, void **value)
Returns a value that is mapped to a key. If the key does not exist, then NULL will return...
void cdc_treap_dtor(struct cdc_treap *t)
Destroys the treap.
enum cdc_stat cdc_treap_ctorl(struct cdc_treap **t, struct cdc_data_info *info,...)
Constructs a treap, initialized by an variable number of pointers on cdc_pair's(first - key...
static struct cdc_pair cdc_treap_iter_key_value(struct cdc_treap_iter *it)
Returns a pair, where first - key, second - value.
Definition: treap.h:430
static void * cdc_treap_iter_key(struct cdc_treap_iter *it)
Returns an item's key.
Definition: treap.h:406
void cdc_treap_swap(struct cdc_treap *a, struct cdc_treap *b)
Swaps treaps a and b. This operation is very fast and never fails.
struct cdc_treap_node * parent
Definition: treap.h:50
enum cdc_stat cdc_treap_ctorv(struct cdc_treap **t, struct cdc_data_info *info, va_list args)
Constructs a treap, initialized by args. The last item must be CDC_END.
static bool cdc_treap_iter_has_next(struct cdc_treap_iter *it)
Returns true if there is at least one element ahead of the iterator, i.e. the iterator is not at the ...
Definition: treap.h:380
The cdc_treap is service struct.
Definition: treap.h:63
static bool cdc_treap_iter_has_prev(struct cdc_treap_iter *it)
Returns true if there is at least one element behind the iterator, i.e. the iterator is not at the fr...
Definition: treap.h:394
struct cdc_treap_node * current
Definition: treap.h:78
size_t cdc_treap_erase(struct cdc_treap *t, void *key)
Removes the element (if one exists) with the key equivalent to key.
void cdc_treap_begin(struct cdc_treap *t, struct cdc_treap_iter *it)
Initializes the iterator to the beginning.
The cdc_treap_iter is service struct.
Definition: treap.h:75
enum cdc_stat cdc_treap_insert_or_assign1(struct cdc_treap *t, void *key, void *value, struct cdc_treap_iter *it, bool *inserted)
Inserts an element or assigns to the current element if the key already exists.
struct cdc_treap_node * root
Definition: treap.h:64
size_t size
Definition: treap.h:65
struct cdc_treap_node * left
Definition: treap.h:51
cdc_stat
Definition: status.h:24
void cdc_treap_iter_prev(struct cdc_treap_iter *it)
Advances the iterator to the previous element in the treap.
void cdc_treap_clear(struct cdc_treap *t)
Removes all the elements from the treap.
void cdc_treap_iter_next(struct cdc_treap_iter *it)
Advances the iterator to the next element in the treap.
void cdc_treap_find(struct cdc_treap *t, void *key, struct cdc_treap_iter *it)
Finds an element with key equivalent to key.
enum cdc_stat cdc_treap_ctorl1(struct cdc_treap **t, struct cdc_data_info *info, cdc_priority_fn_t prior,...)
Constructs a treap, initialized by an variable number of pointers on cdc_pair's(first - key...
int priority
Definition: treap.h:55
static bool cdc_treap_empty(struct cdc_treap *t)
Checks if the treap has no elements.
Definition: treap.h:235
static size_t cdc_treap_size(struct cdc_treap *t)
Returns the number of items in the treap.
Definition: treap.h:223
The cdc_treap_node is service struct.
Definition: treap.h:49
static void * cdc_treap_iter_value(struct cdc_treap_iter *it)
Returns an item's value.
Definition: treap.h:418
struct cdc_treap_node * prev
Definition: treap.h:77
enum cdc_stat cdc_treap_insert_or_assign(struct cdc_treap *t, void *key, void *value, struct cdc_pair_treap_iter_bool *ret)
Inserts an element or assigns to the current element if the key already exists.
enum cdc_stat cdc_treap_ctor1(struct cdc_treap **t, struct cdc_data_info *info, cdc_priority_fn_t prior)
Constructs an empty treap.
void * value
Definition: treap.h:54
static bool cdc_treap_iter_is_eq(struct cdc_treap_iter *it1, struct cdc_treap_iter *it2)
Returns false if the iterator |it1| equal to the iterator |it2|, otherwise returns false...
Definition: treap.h:447
struct cdc_treap * container
Definition: treap.h:76
enum cdc_stat cdc_treap_ctorv1(struct cdc_treap **t, struct cdc_data_info *info, cdc_priority_fn_t prior, va_list args)
Constructs a treap, initialized by args. The last item must be CDC_END.
The cdc_data_info struct used to initialize contaners.
Definition: common.h:71
enum cdc_stat cdc_treap_ctor(struct cdc_treap **t, struct cdc_data_info *info)
Constructs an empty treap.
struct cdc_treap_node * right
Definition: treap.h:52
enum cdc_stat cdc_treap_insert1(struct cdc_treap *t, void *key, void *value, struct cdc_treap_iter *it, bool *inserted)
Inserts an element into the container, if the container doesn't already contain an element with an eq...
size_t cdc_treap_count(struct cdc_treap *t, void *key)
Returns the number of elements with key that compares equal to the specified argument key...
int(* cdc_priority_fn_t)(void *)
Definition: treap.h:42