diff options
Diffstat (limited to 'src/splist.h')
-rw-r--r-- | src/splist.h | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/src/splist.h b/src/splist.h new file mode 100644 index 0000000..e6be624 --- /dev/null +++ b/src/splist.h @@ -0,0 +1,36 @@ +#ifndef SPLIST_H +#define SPLIST_H +#include "util.h" +#include "list.h" + +/* A sparse list is a list with its "inverse list". This can be used + to determine if a number belongs to a sparse list at constant + time. */ + +typedef struct splist_s splist; + +splist *new_splist(); + +/* A sparse list is of fixed size. */ +unsigned char init_splist(splist *s, NUM size); + +P_ATTR NUM splist_len(CCR_MOD(splist *) s); + +/* NOTE: The returned list is owned by the original splist, so don't + destroy that list or do anything that should not be done. */ +P_ATTR List *splist_ls(CCR_MOD(splist *) s); + +/* We assume that elements of a sparse list are of type NUM. */ +unsigned char add_to_splist(splist *s, NUM element); + +/* resetting a sparse list means to set its length to 0 */ +void reset_splist(splist *s); + +/* Constant time operation */ +unsigned char splist_is_member(splist *s, NUM element); + +void print_splist(splist *s); + +void destroy_splist(splist *s); + +#endif |