libds/include/sprs.h

#ifndef LIBDS_SPRS_HEADER
#define LIBDS_SPRS_HEADER

#include <stddef.h>
#include "libds.h"

/**
 * Sparse set implementation with the capacity to store data.
 * Sparse sets are initially defined as having two arrays of integers,
 * one "dense" array, into which new elements are added sequentially, and another
 * "sparse" array into which the elements' indexes in the dense array are put at
 * their index.
 *
 * For instance, after adding the elements 1, 0, and 3 to a sparse array,
 * it may look like:
 *           (Size)    (Capacity)
 *             |           |
 * [1 ][0 ][3 ][..][..][..] (Dense)
 * [1 ][0 ][..][2 ][..][..] (Sparse)
 * As seen in the above representation, the element in the dense array at index 0 is 1,
 * and the element at index 1 in the sparse array points to its location in the dense array.
 * It's very quick to check whether an element is part of this sparse set:
 * if sparse[element] < size && dense[sparse[element]] == element.
 * Iteration is also O(n), thanks to the dense array, and no initial memory clearing is required.
 *
 * The below implementation adds an additional piece of data to the sparse array, a void* so that an item
 * can be associated with an integer index and stored / retrieved / ismember'ed together with it.
 */

/**
 * A single element in a sparse array.
 */
struct sprs_element_s {
  /**
   * The index of this element in the dense array.
   */
  size_t index;
  /**
   * A piece of data (optional) associated with this index.
   */
  void* data;
};

/**
 * A sparse array / set.
 */
struct sprs_s {
  /**
   * The maximum size of the set. This is the limit for integer indices.
   */
  size_t capacity;
  /**
   * The current size of the sparse set, and the next available index in the dense array.
   */
  size_t size;

  /**
   * The dense array.
   * This is a pointer so that an array of a certain size can be allocated as needed.
   */
  size_t* dense;
  /**
   * The sparse array.
   * This is a pointer so that an array of a certain size can be allocated as needed.
   */
  struct sprs_element_s* sparse;
};

typedef struct sprs_s sprs;

/**
 * Initializes a sparse set with default values.
 * This does not allocate any memory for the arrays.
 * @param sprs the sparse set / array to initialize.
 */
void sprs_init(sprs* sprs);
/**
 * Allocates the necessary memory for a sparse set's
 * dense and sparse arrays.
 * @param sprs the sparse set for which memory should be allocated.
 * @param size the maximum capacity of the sparse set to use.
 * @return LIBDS_SUCCESS if all goes well, or LIBDS_MALLOC if an allocation failed.
 */
libds_result sprs_setup(sprs* sprs, size_t size);
/**
 * Frees memory allocated by the sparse set, and resets its capacity and size.
 * @param sprs the sparse set to free.
 */
void sprs_free(sprs* sprs);

/**
 * Stores a value in the sparse set under a given index.
 * @param sprs the sparse set into which to store the value.
 * @param index the index at which to store the value
 * @param data the value to store.
 */
void sprs_put(sprs* sprs, size_t index, void* data);
/**
 * Stores a value in the sparse set under a given index.
 * If the capacity of the sparse set is smaller than the given index,
 * this grows the sparse set by doubling its size.
 * @param sprs the sparse set into which to store the value.
 * @param index the index at which to store the value.
 * @param data the value to store.
 * @return LIBDS_SUCCESS if all goes well, or LIBDS_MALLOC if the growing failed.
 */
libds_result sprs_put_grow(sprs* sprs, size_t index, void* data);
/**
 * Checks if the sparse set contains data under a given index.
 * @param sprs the sparse set to check.
 * @param index the index for which to check.
 * @return 1 if the index exists, 0 if not.
 */
int sprs_contains(const sprs* sprs, size_t index);
/**
 * Gets the value stored under the given sparse set index.
 * This will check for whether the index is in the sparse set first,
 * and return NULL if it's not.
 * Please not that this exhibit the !exact same! behavior if a NULL was stored
 * under the index or if the index was never populated. use sprs_contains to
 * check whether the index is populated if this is important.
 * @param sprs the sparse set to check.
 * @param index the index from under which to retrieve the value.
 * @return the value stored under the index, or NULL if there is nothing there.
 */
void* sprs_get(const sprs* sprs, size_t index);

/**
 * Runs through every element in the sparse set, and compares it against the
 * given data using the given comparison function. If the comparison function returns
 * true, returns the element that was passed to it. If the comparison function returns
 * true for no element, returns NULL.
 * @param sprs the sparse set to iterate through.
 * @param data the data to compare elements against
 * @param compare the comparison function
 * @return the first element that is matched by the comparison function, or NULL if none are matched.
 */
void* sprs_find(const sprs* sprs, void* data, compare_func compare);
/**
 * Runs through every element in the sparse set, and compares it against the
 * given data using the given comparison function. If the comparison function returns
 * true, calls the foreach function, passing it the element and the variable argument list.
 * Stops if any foreach function returns a nonzero code.
 * @param sprs the sparse set to perform the operation on
 * @param data the data to pass the comparison function
 * @param compare the comparison function operating on the data and each element in the list.
 * @param foreach the function to be called on every element recognized by the comparison function
 * @param ... variable arguments to be passed on to the foreach function
 * @return 0 if all goes well, or the first nonzero code returned by foreach.
 */
int sprs_foreach(const sprs* sprs, void* data, compare_func compare, foreach_func foreach, ...);

#endif