Vector

Types

typedef struct UVec_T UVec_T: Generic vector type.

Note

This is a placeholder for documentation purposes. You should use the UVec(T) macro to reference a specific vector type.

UVec(T)

References a specific vector type.

Parameters:

T – Vector type.

uvec_decl(T)

Vector type forward declaration.

Parameters:

T – symbol Vector type.

enum uvec_ret

Return codes.

Values:

enumerator UVEC_ERR

The operation failed due to an error.

As of right now, it can only happen if memory cannot be allocated.

enumerator UVEC_OK: The operation succeeded.

enumerator UVEC_NO: The operation could not be completed.

Builtin types

typedef struct UVec_char UVec_char: UVec(T) of char elements.

typedef struct UVec_ulib_byte UVec_ulib_byte: UVec(T) of ulib_byte elements.

typedef struct UVec_ulib_int UVec_ulib_int: UVec(T) of ulib_int elements.

typedef struct UVec_ulib_uint UVec_ulib_uint: UVec(T) of ulib_uint elements.

typedef struct UVec_ulib_float UVec_ulib_float: UVec(T) of ulib_float elements.

typedef struct UVec_ulib_ptr UVec_ulib_ptr: UVec(T) of ulib_ptr elements.

typedef struct UVec_UString UVec_UString: UVec(T) of UString elements.

Constants

UVEC_CACHE_LINE_SIZE: Cache line size (B).

UVEC_SORT_STACK_SIZE: Quicksort stack size.

Note

When the stack overflows, sorting falls back to insertion sort.

UVEC_SORT_INSERTION_THRESH: Switch to insertion sort below this many elements.

Note

Applies to both entire vectors and quicksort partitions.

UVEC_INDEX_OF_THRESH: Use ulib_mem_mem() in uvec_index_of() above this many elements.

Note

Only affects vectors of scalar types.

UVEC_BINARY_SEARCH_THRESH: Switch from binary to linear search below this many elements.

Defining new vector types

UVEC_DECL(T)

Declares a new vector type.

Parameters:

T – symbol Vector type.

UVEC_DECL_SPEC(T, SPEC)

Declares a new vector type, prepending a specifier to the generated declarations.

Parameters:

T – symbol Vector type.
SPEC – specifier Specifier.

UVEC_DECL_EQUATABLE(T)

Declares a new equatable vector type.

Parameters:

T – symbol Vector type.

UVEC_DECL_EQUATABLE_SPEC(T, SPEC)

Declares a new equatable vector type, prepending a specifier to the generated declarations.

Parameters:

T – symbol Vector type.
SPEC – specifier Specifier.

UVEC_DECL_COMPARABLE(T)

Declares a new comparable vector type.

Parameters:

T – symbol Vector type.

UVEC_DECL_COMPARABLE_SPEC(T, SPEC)

Declares a new comparable vector type, prepending a specifier to the generated declarations.

Parameters:

T – symbol Vector type.
SPEC – specifier Specifier.

UVEC_IMPL(T)

Implements a previously declared vector type.

Parameters:

T – symbol Vector type.

UVEC_IMPL_EQUATABLE(T, equal_func)

Implements a previously declared equatable vector type.

Elements of an equatable vector can be checked for equality via equal_func.

Parameters:

T – symbol Vector type.
equal_func – (T, T) -> bool Equality function.

UVEC_IMPL_COMPARABLE(T, equal_func, compare_func)

Implements a previously declared comparable vector type.

Elements of a comparable vector can be checked for equality via equal_func and ordered via compare_func.

Parameters:

T – symbol Vector type.
equal_func – (T, T) -> bool Equality function.
compare_func – (T, T) -> bool Comparison function (a < b).

UVEC_IMPL_IDENTIFIABLE(T)

Implements a previously declared comparable vector type whose elements can be checked for equality via == and compared via <.

Parameters:

T – symbol Vector type.

UVEC_INIT(T)

Defines a new static vector type.

Parameters:

T – symbol Vector type.

UVEC_INIT_EQUATABLE(T, equal_func)

Defines a new static equatable vector type.

Parameters:

T – symbol Vector type.
equal_func – (T, T) -> bool Equality function.

UVEC_INIT_COMPARABLE(T, equal_func, compare_func)

Defines a new static comparable vector type.

Parameters:

T – symbol Vector type.
equal_func – (T, T) -> bool Equality function.
compare_func – (T, T) -> bool Comparison function (a < b).

UVEC_INIT_IDENTIFIABLE(T)

Defines a new static comparable vector type whose elements can be checked for equality via == and compared via <.

Parameters:

T – symbol Vector type.

Common vector operations

UVec_T uvec(symbol T)

Initializes a new vector.

Note

The returned object must be destroyed by calling uvec_deinit().

Parameters:

T – Vector type.

Returns:

Initialized vector instance.

UVec_T uvec_assign(symbol T, T *array, ulib_uint count)

Initializes a new vector by taking ownership of the specified array, which must have been dynamically allocated.

Note

The returned object must be destroyed by calling uvec_deinit().

Note

Due to the internals of UVec(T), you must not attempt to access the buffer after calling this function as it may have been deallocated.

Parameters:

T – Vector type.
array – Array.
count – Number of elements in the array.

Returns:

Initialized vector.

UVec_T uvec_wrap(symbol T, T *array, ulib_uint count)

Initializes a new vector by wrapping the specified array.

Note

If the array has been dynamically allocated, you are responsible for its deallocation.

Note

You must not call uvec_deinit() on a vector initialized with this function.

Note

The array will never be resized, and it is assumed it can contain any number of elements. This is also reflected by uvec_size() returning ULIB_UINT_MAX for vectors initialized with this function. It is up to you to avoid overflowing the underlying buffer.

Parameters:

T – Vector type.
array – Array.
count – Number of elements in the array.

Returns:

Initialized vector.

void uvec_deinit(symbol T, UVec_T *vec)

De-initializes a vector previously initialized via uvec().

Parameters:

T – Vector type.
vec – Vector to de-initialize.

UVec_T uvec_move(symbol T, UVec_T *vec)

Invalidates the vector and returns its storage.

Note

The returned object must be destroyed by calling uvec_deinit().

Parameters:

T – Vector type.
vec – Vector whose storage should be returned.

Returns:

Vector storage.

uvec_ret uvec_copy(symbol T, UVec_T const *src, UVec_T *dest)

Copies the specified vector.

Parameters:

T – Vector type.
src – Vector to copy.
dest – Vector to copy into.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

void uvec_copy_to_array(symbol T, UVec_T const *vec, T *array)

Copies the elements of the specified vector into the given array.

Note

The array must be sufficiently large to hold all the elements.

Parameters:

T – Vector type.
vec – Vector to copy.
array – Array to copy the elements into.

uvec_ret uvec_reserve(symbol T, UVec_T vec, ulib_uint size)

Ensures the specified vector can hold at least as many elements as size.

Parameters:

T – Vector type.
vec – Vector instance.
size – Number of elements the vector should be able to hold.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

uvec_ret uvec_expand(symbol T, UVec_T *vec, ulib_uint size)

Expands the specified vector so that it can contain additional size elements.

Parameters:

T – Vector type.
vec – Vector to expand.
size – Number of additional elements the vector should be able to hold.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

uvec_ret uvec_shrink(symbol T, UVec_T *vec)

Shrinks the specified vector so that its allocated size is just large enough to hold the elements it currently contains.

Parameters:

T – Vector type.
vec – Vector to shrink.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

T *uvec_data(symbol T, UVec_T const *vec)

Returns the raw array backing the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

Pointer to the first element of the raw array.

T uvec_get(symbol T, UVec_T const *vec, ulib_uint idx)

Retrieves the element at the specified index.

Parameters:

T – Vector type.
vec – Vector instance.
idx – Index.

Returns:

Element at the specified index.

void uvec_set(symbol T, UVec_T *vec, ulib_uint idx, T item)

Replaces the element at the specified index.

Parameters:

T – Vector type.
vec – Vector instance.
idx – Index.
item – Replacement element.

T uvec_first(symbol T, UVec_T const *vec)

Returns the first element in the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

First element.

T uvec_last(symbol T, UVec_T const *vec)

Returns the last element in the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

Last element.

ulib_uint uvec_count(symbol T, UVec_T const *vec)

Returns the number of elements in the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

Number of elements.

ulib_uint uvec_size(symbol T, UVec_T const *vec)

Returns the maximum number of elements that can be held by the raw array backing the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

Capacity.

bool uvec_index_is_valid(symbol T, UVec_T const *vec, ulib_uint idx)

Checks if the specified index is valid.

Parameters:

T – Vector type.
vec – Vector instance.
idx – Index.

Returns:

True if the index is valid, false otherwise.

uvec_ret uvec_push(symbol T, UVec_T *vec, T item)

Pushes the specified element to the top of the vector (last element).

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to push.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

bool uvec_pop(symbol T, UVec_T *vec, T *item)

Removes and returns the element at the top of the vector (last element).

Parameters:

T – Vector type.
vec – Vector instance.
item – [out] Removed element.

Returns:

True if an element was removed, false if the vector was empty.

void uvec_remove_at(symbol T, UVec_T *vec, ulib_uint idx)

Removes the element at the specified index.

Parameters:

T – Vector type.
vec – Vector instance.
idx – Index of the element to remove.

uvec_ret uvec_insert_at(symbol T, UVec_T *vec, ulib_uint idx, T item)

Inserts an element at the specified index.

Parameters:

T – Vector type.
vec – Vector instance.
idx – Index at which the element should be inserted.
item – Element to insert.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

void uvec_remove_range(symbol T, UVec_T *vec, ulib_uint start, ulib_uint n)

Removes the elements in the specified range.

Parameters:

T – Vector type.
vec – Vector instance.
start – Range start index.
n – Range length.

uvec_ret uvec_insert_range(symbol T, UVec_T *vec, T const *array, ulib_uint start, ulib_uint n)

Inserts the elements contained in an array at the specified index.

Parameters:

T – Vector type.
vec – Vector instance.
array – Array containing the items.
start – Range start index.
n – Number of elements in the array.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

void uvec_remove_all(symbol T, UVec_T *vec)

Removes all the elements in the vector.

Parameters:

T – Vector type.
vec – Vector instance.

uvec_ret uvec_append(symbol T, UVec_T *vec, UVec_T const *src)

Appends a vector to another.

Parameters:

T – Vector type.
vec – Vector instance.
src – Vector to append.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

uvec_ret uvec_append_array(symbol T, UVec_T *vec, T const *array, ulib_uint n)

Appends an array to the specified vector.

Parameters:

T – Vector type.
vec – Vector instance.
array – Array to append.
n – Number of elements to append.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

UVec_T uvec_view(symbol T, UVec_T const *vec, ulib_uint start, ulib_uint len)

Returns a view over a section of the specified vector.

Note

Views are affected by the same limitations as vectors created via uvec_wrap().

Parameters:

T – Vector type.
vec – Vector instance.
start – Start index of the view.
len – Length of the view.

Returns:

View.

UVec_T uvec_view_from(symbol T, UVec_T const *vec, ulib_uint start)

Returns a view over a section of the specified vector.

Note

Views are affected by the same limitations as vectors created via uvec_wrap().

Parameters:

T – Vector type.
vec – Vector instance.
start – Start index of the view.

Returns:

View.

UVec_T uvec_view_to(symbol T, UVec_T const *vec, ulib_uint len)

Returns a view over a section of the specified vector.

Note

Views are affected by the same limitations as vectors created via uvec_wrap().

Parameters:

T – Vector type.
vec – Vector instance.
len – Length of the view.

Returns:

View.

uvec_ret uvec_set_range(symbol T, UVec_T *vec, T const *array, ulib_uint start, ulib_uint n)

Sets items in the specified range to those contained in an array.

Parameters:

T – Vector type.
vec – Vector instance.
array – Array containing the items.
start – Range start index.
n – Number of elements in the array.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

void uvec_reverse(symbol T, UVec_T *vec)

Reverses the vector.

Parameters:

T – Vector type.
vec – Vector instance.

void uvec_shuffle(symbol T, UVec_T *vec)

Randomly shuffles the elements of the vector.

Parameters:

T – Vector type.
vec – Vector instance.

uvec_foreach(T, vec, enum_name)

Iterates over the vector, executing the specified code block for each element.

Usage example:

uvec_foreach (ulib_int, vec, entry) {
    ulib_uint index = entry.i;
    ulib_int item = *entry.item;
    ...
}

Parameters:

T – symbol Vector type.
vec – UVec(T) * Vector instance.
enum_name – symbol Name of the variable holding the current item and its index.

uvec_foreach_reverse(T, vec, enum_name)

Iterates over the vector in reverse order, executing the specified code block for each element.

Usage example:

uvec_foreach_reverse (ulib_int, vec, entry) {
    ulib_uint index = entry.i;
    ulib_int item = *entry.item;
    ...
}

Parameters:

T – symbol Vector type.
vec – UVec(T) * Vector instance.
enum_name – symbol Name of the variable holding the current item and its index.

Equatable vectors

ulib_uint uvec_index_of(symbol T, UVec_T const *vec, T item)

Returns the index of the first occurrence of the specified element.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to search.

Returns:

Index of the found element, or an invalid index if the element cannot be found.

ulib_uint uvec_index_of_reverse(symbol T, UVec_T const *vec, T item)

Returns the index of the last occurrence of the specified element.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to search.

Returns:

Index of the found element, or an invalid index if the element cannot be found.

bool uvec_contains(symbol T, UVec_T const *vec, T item)

Checks whether the vector contains the specified element.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to search.

Returns:

True if the vector contains the specified element, false otherwise.

bool uvec_remove(symbol T, UVec_T const *vec, T item)

Removes the specified element.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to remove.

Returns:

True if the element was found and removed, false otherwise.

bool uvec_equals(symbol T, UVec_T const *vec_a, UVec_T const *vec_b)

Checks whether the two vectors are equal.

Two vectors are considered equal if they contain the same elements in the same order.

Parameters:

T – Vector type.
vec_a – First vector.
vec_b – Second vector.

Returns:

True if the vectors are equal, false otherwise.

uvec_ret uvec_push_unique(symbol T, UVec_T *vec, T item)

Pushes the specified element to the top of the vector if it does not already contain it.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to push.

Returns:

UVEC_OK if the element was pushed, UVEC_NO if the element was already present, otherwise UVEC_ERR.

Comparable vectors

ulib_uint uvec_index_of_min(symbol T, UVec_T const *vec)

Returns the index of the minimum element in the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

Index of the minimum element.

ulib_uint uvec_index_of_max(symbol T, UVec_T const *vec)

Returns the index of the maximum element in the vector.

Parameters:

T – Vector type.
vec – Vector instance.

Returns:

Index of the maximum element.

void uvec_sort(symbol T, UVec_T *vec)

Sorts the vector.

Average performance: O(n log n)

Parameters:

T – Vector type.
vec – Vector instance.

void uvec_sort_range(symbol T, UVec_T *vec, ulib_uint start, ulib_uint len)

Sorts the elements in the specified range.

Average performance: O(n log n)

Parameters:

T – Vector type.
vec – Vector instance.
start – Range start index.
len – Range length.

ulib_uint uvec_insertion_index_sorted(symbol T, UVec_T const *vec, T item)

Finds the insertion index for the specified item in a sorted vector.

Average performance: O(log n)

Parameters:

T – Vector type.
vec – Vector instance.
item – Element whose insertion index should be found.

Returns:

Insertion index.

ulib_uint uvec_index_of_sorted(symbol T, UVec_T const *vec, T item)

Returns the index of the specified element in a sorted vector.

Average performance: O(log n)

Note

The returned index is not necessarily the first occurrence of the item.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to search.

Returns:

Index of the found element, or an invalid index.

bool uvec_contains_sorted(symbol T, UVec_T const *vec, T item)

Checks whether a sorted vector contains the specified element.

Average performance: O(log n)

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to search.

Returns:

True if the vector contains the specified element, false otherwise.

uvec_ret uvec_insert_sorted(symbol T, UVec_T *vec, T item, ulib_uint *idx)

Inserts the specified element in a sorted vector.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to insert.
idx – [out] Index of the inserted element.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

uvec_ret uvec_insert_sorted_unique(symbol T, UVec_T *vec, T item, ulib_uint *idx)

Inserts the specified element in a sorted vector only if it does not already contain it.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to insert.
idx – [out] Index of the inserted (or that of the already present) element.

Returns:

UVEC_OK if the element was inserted, UVEC_NO if the element was already present, otherwise UVEC_ERR.

bool uvec_remove_sorted(symbol T, UVec_T *vec, T item)

Removes the specified element from a sorted vector.

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to remove.

Returns:

True if the element was found and removed, false otherwise.

Priority queues

void uvec_max_heapq_make(symbol T, UVec_T *vec)

Makes the specified vector a max heap queue.

Note

All functions named uvec_max_heapq_* require either:

an empty vector;
a non-empty vector that has been mutated by uvec_max_heapq_* functions only;
any non-empty vector that has been transformed into a heap through this function.

Parameters:

T – Vector type.
vec – Vector instance.

uvec_ret uvec_max_heapq_push(symbol T, UVec_T *vec, T item)

Pushes the specified item into the max heap queue.

See also

uvec_max_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to push.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

bool uvec_max_heapq_pop(symbol T, UVec_T *vec, T *item)

Removes and returns the maximum element from the queue.

See also

uvec_max_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
item – [out] Removed element.

Returns:

True if the maximum was removed, false if the queue was empty.

void uvec_max_heapq_push_pop(symbol T, UVec_T *vec, T in, T *out)

Pushes in into the queue, and pops the maximum.

Equivalent to push followed by pop, but with better performance.

See also

uvec_max_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
in – Element to push.
out – [out] Removed element.

bool uvec_max_heapq_replace(symbol T, UVec_T *vec, T in, T *out)

Pops the maximum, and pushes in into the queue.

Similar to pop followed by push, but with better performance.

See also

uvec_max_heapq_make()

Note

If the queue is empty, in is not pushed.

Parameters:

T – Vector type.
vec – Vector instance.
in – Element to push.
out – [out] Removed element.

Returns:

True if the operation succeeded, false if the queue was empty.

bool uvec_max_heapq_remove(symbol T, UVec_T *vec, T item)

Removes the specified item from the queue.

See also

uvec_max_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to remove.

Returns:

True if the element was found and removed, false otherwise.

void uvec_min_heapq_make(symbol T, UVec_T *vec)

Makes the specified vector a min heap queue.

Note

All functions named uvec_min_heapq_* require either:

an empty vector;
a non-empty vector that has been mutated by uvec_min_heapq_* functions only;
any non-empty vector that has been transformed into a heap through this function.

Parameters:

T – Vector type.
vec – Vector instance.

uvec_ret uvec_min_heapq_push(symbol T, UVec_T *vec, T item)

Pushes the specified item into the min heap queue.

See also

uvec_min_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to push.

Returns:

UVEC_OK on success, otherwise UVEC_ERR.

bool uvec_min_heapq_pop(symbol T, UVec_T *vec, T *item)

Removes and returns the minimum element from the queue.

See also

uvec_min_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
item – [out] Removed element.

Returns:

True if the minimum was removed, false if the queue was empty.

void uvec_min_heapq_push_pop(symbol T, UVec_T *vec, T in, T *out)

Pushes in into the queue, and pops the minimum.

Equivalent to push followed by pop, but with better performance.

See also

uvec_min_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
in – Element to push.
out – [out] Removed element.

bool uvec_min_heapq_replace(symbol T, UVec_T *vec, T in, T *out)

Pops the minimum, and pushes in into the queue.

Similar to pop followed by push, but with better performance.

See also

uvec_min_heapq_make()

Note

If the queue is empty, in is not pushed.

Parameters:

T – Vector type.
vec – Vector instance.
in – Element to push.
out – [out] Removed element.

Returns:

True if the operation succeeded, false if the queue was empty.

bool uvec_min_heapq_remove(symbol T, UVec_T *vec, T item)

Removes the specified item from the queue.

See also

uvec_min_heapq_make()

Parameters:

T – Vector type.
vec – Vector instance.
item – Element to remove.

Returns:

True if the element was found and removed, false otherwise.