vector.h

// SPDX-License-Identifier: MIT
// Copyright (c) 2021 Michael Bäck <mhcoma@gmail.com>

#ifndef __CCTL_VECTOR_H__
#define __CCTL_VECTOR_H__

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#include "cctl.h"

// Vector Iterator

/// `vector_iterator(T)` ⇒ `T_vector_iterator`
/// 
/// Generates the iterator type name for `vector(T)`.
#define vector_iterator(T) cctl_join(T, vector_iterator)

/// `vector_iterator_func(FUNC, T)` ⇒ `T_vector_iterator_FUNC`
/// 
/// Generates a mangled function identifier for `vector_iterator(T)`.
#define vector_iterator_func(FUNC, T) cctl_join(vector_iterator(T), FUNC)

/// `vector_iterator_struct(T)` ⇒ `struct T_vector_iterator_struct`
/// 
/// Generates the underlying structure tag for `vector_iterator(T)`.
#define vector_iterator_struct(T) cctl_join(vector_iterator(T), struct)

/// ```c
/// T* vector_iterator_get(T, vector_iterator(T)* p_it)
/// ```
/// Returns a pointer to the element currently referenced by the iterator.
/// 
/// `p_it` is a pointer to the iterator instance.
#define vector_iterator_get(T, p_it) ((p_it)->p_v->p_data + (p_it)->index)

/// ```c
/// bool vector_iterator_is_valid(T, vector_iterator(T)* p_it)
/// ```
/// Checks whether the iterator currently points to a valid element.
/// 
/// Returns `true` if the iterator is valid and within bounds, `false` otherwise.
#define vector_iterator_is_valid(T, p_it) ((p_it)->p_v && (p_it)->index < (p_it)->p_v->size)

/// ```c
/// bool vector_iterator_is_equal(T, vector_iterator(T)* p_it1, vector_iterator(T)* p_it2)
/// ```
/// Checks whether two iterators point to the same vector and index.
#define vector_iterator_is_equal(T, p_it1, p_it2) ((p_it1)->p_v == (p_it2)->p_v && (p_it1)->index == (p_it2)->index)

/// ```c
/// void vector_iterator_next(T, vector_iterator(T)* p_it)
/// ```
/// Advances the iterator forward to the next element.
#define vector_iterator_next(T, p_it) ((p_it)->index++)

/// ```c
/// void vector_iterator_prev(T, vector_iterator(T)* p_it)
/// ```
/// Moves the iterator backward to the previous element.
#define vector_iterator_prev(T, p_it) ((p_it)->index--)

/// ```c
/// bool vector_iterator_insert_after(T, vector_iterator(T)* p_it, T item)
/// ```
/// Inserts `item` immediately after the current iterator position.
/// 
/// Returns `true` on successful insertion, or `false` on allocation failure or invalid iterator.
#define vector_iterator_insert_after(T, p_it, item) vector_iterator_func(insert_after, T)(p_it, item)

/// ```c
/// bool vector_iterator_insert_before(T, vector_iterator(T)* p_it, T item)
/// ```
/// Inserts `item` immediately before the current iterator position.
/// 
/// Returns `true` on successful insertion, or `false` on allocation failure or invalid iterator.
#define vector_iterator_insert_before(T, p_it, item) vector_iterator_func(insert_before, T)(p_it, item)

/// ```c
/// bool vector_iterator_remove(T, vector_iterator(T)* p_it)
/// ```
/// Removes the element at the current iterator position.
/// 
/// Returns `true` on successful removal, or `false` if the iterator is invalid.
#define vector_iterator_remove(T, p_it) vector_iterator_func(remove, T)(p_it)

/// Declares iterator struct and function prototypes in a header file.
#define vector_iterator_imp_h(T) \
	typedef struct vector_iterator_struct(T) vector_iterator(T); \
	struct vector_iterator_struct(T) { \
		vector(T)* p_v; \
		size_t index; \
	}; \
	\
	bool vector_iterator_func(insert_after, T)(vector_iterator(T)* p_it, T item); \
	bool vector_iterator_func(insert_before, T)(vector_iterator(T)* p_it, T item); \
	bool vector_iterator_func(remove, T)(vector_iterator(T)* p_it);

/// Implements iterator functions in a source file.
#define vector_iterator_imp_c(T) \
	bool vector_iterator_func(insert_after, T)(vector_iterator(T)* p_it, T item) { \
		if (!p_it || !vector_iterator_is_valid(T, p_it)) return false; \
		if (!vector_func(resize, T)(p_it->p_v, p_it->p_v->size + 1)) return false; \
		if (p_it->index + 1 < p_it->p_v->size - 1) { \
			memmove( \
				p_it->p_v->p_data + p_it->index + 2, \
				p_it->p_v->p_data + p_it->index + 1, \
				(p_it->p_v->size - 2 - p_it->index) * sizeof(T) \
			); \
		} \
		*(p_it->p_v->p_data + p_it->index + 1) = item; \
		return true; \
	} \
	\
	bool vector_iterator_func(insert_before, T)(vector_iterator(T)* p_it, T item) { \
		if (!p_it || !vector_iterator_is_valid(T, p_it)) return false; \
		if (!vector_func(resize, T)(p_it->p_v, p_it->p_v->size + 1)) return false; \
		memmove( \
			p_it->p_v->p_data + p_it->index + 1, \
			p_it->p_v->p_data + p_it->index, \
			(p_it->p_v->size - 1 - p_it->index) * sizeof(T) \
		); \
		*(p_it->p_v->p_data + p_it->index) = item; \
		p_it->index++; \
		return true; \
	} \
	\
	bool vector_iterator_func(remove, T)(vector_iterator(T)* p_it) { \
		if (!p_it || !vector_iterator_is_valid(T, p_it)) return false; \
		if (p_it->index < p_it->p_v->size - 1) { \
			memmove( \
				p_it->p_v->p_data + p_it->index, \
				p_it->p_v->p_data + p_it->index + 1, \
				(p_it->p_v->size - 1 - p_it->index) * sizeof(T) \
			); \
		} \
		p_it->p_v->size--; \
		return true; \
	}


// Vector

/// `vector(T)` ⇒ `T_vector`
/// 
/// Generates the vector container type name for `T`.
#define vector(T) cctl_join(T, vector)

/// `vector_func(FUNC, T)` ⇒ `T_vector_FUNC`
/// 
/// Generates a mangled function identifier for `vector(T)`.
#define vector_func(FUNC, T) cctl_join(vector(T), FUNC)

/// `vector_struct(T)` ⇒ `struct T_vector_struct`
/// 
/// Generates the underlying structure tag for `vector(T)`.
#define vector_struct(T) cctl_join(vector(T), struct)

/// ```c
/// void vector_init(T, vector(T)* p_v)
/// ```
/// Initializes the vector to an empty state.
/// 
/// `p_v` is a pointer to the vector instance. Must be called before any other operations.
#define vector_init(T, p_v) vector_func(init, T)(p_v)

#define vector_new_1(T) vector_func(new, T)(0)
#define vector_new_2(T, size) vector_func(new, T)(size)

/// ```c
/// vector(T) vector_new(T, [size_t size])
/// ```
/// Constructs and returns an initialized vector, optionally pre-allocated and zero-initialized with `size` elements.
#define vector_new(...) cctl_dispatch(vector_new, __VA_ARGS__)(__VA_ARGS__)

/// ```c
/// vector(T) vector_from_items(T, ...)
/// ```
/// Constructs and returns an initialized vector containing all items provided in `...`.
#define vector_from_items(T, ...) \
	vector_func(from_items, T)((const T[]) { __VA_ARGS__ }, sizeof((const T[]) { __VA_ARGS__ }) / sizeof(T))

/// ```c
/// bool vector_extend_items(T, vector(T)* p_v, ...)
/// ```
/// Appends multiple items provided in `...` to the end of the vector.
#define vector_extend_items(T, p_v, ...) \
	vector_func(extend_items, T)(p_v, (const T[]) { __VA_ARGS__ }, sizeof((const T[]) { __VA_ARGS__ }) / sizeof(T))

/// ```c
/// void vector_free(T, vector(T)* p_v)
/// ```
/// Frees all dynamically allocated memory of the vector and reinitializes it.
#define vector_free(T, p_v) vector_func(free, T)(p_v)

/// ```c
/// void vector_clear(T, vector(T)* p_v)
/// ```
/// Clears all elements from the vector without deallocating internal buffer memory.
#define vector_clear(T, p_v) vector_func(clear, T)(p_v)

/// ```c
/// bool vector_reserve(T, vector(T)* p_v, size_t capacity)
/// ```
/// Ensures that the vector has enough capacity to hold at least `capacity` elements.
/// 
/// Returns `true` on success, or `false` on allocation failure.
#define vector_reserve(T, p_v, capacity) vector_func(reserve, T)(p_v, capacity)

/// ```c
/// bool vector_resize(T, vector(T)* p_v, size_t size)
/// ```
/// Resizes the vector to contain `size` elements.
/// 
/// Newly allocated memory is zero-initialized. Returns `true` on success, `false` on allocation failure.
#define vector_resize(T, p_v, size) vector_func(resize, T)(p_v, size)

/// ```c
/// bool vector_push_back(T, vector(T)* p_v, T item)
/// ```
/// Appends `item` to the end of the vector.
/// 
/// Automatically grows capacity if needed. Returns `true` on success, `false` on allocation failure.
#define vector_push_back(T, p_v, item) vector_func(push_back, T)(p_v, item)

/// ```c
/// bool vector_pop_back(T, vector(T)* p_v)
/// ```
/// Removes the last element from the vector.
/// 
/// Returns `true` on success, or `false` if the vector is already empty.
#define vector_pop_back(T, p_v) vector_func(pop_back, T)(p_v)

/// ```c
/// bool vector_swap_remove(T, vector(T)* p_v, size_t index)
/// ```
/// Removes the element at `index` in O(1) time by swapping it with the last element and popping back.
/// 
/// Returns `true` on success, or `false` if `index` is out of bounds.
#define vector_swap_remove(T, p_v, index) vector_func(swap_remove, T)(p_v, index)

/// ```c
/// bool vector_shrink_to_fit(T, vector(T)* p_v)
/// ```
/// Reduces vector memory capacity to fit its current size.
/// 
/// Returns `true` on success, or `false` on reallocation failure.
#define vector_shrink_to_fit(T, p_v) vector_func(shrink_to_fit, T)(p_v)

/// ```c
/// T* vector_at(T, vector(T)* p_v, size_t index)
/// ```
/// Returns a pointer to the element at the specified `index`, or `NULL` if out of bounds.
#define vector_at(T, p_v, index) \
	(((index) < (p_v)->size) ? ((p_v)->p_data + (index)) : NULL)

/// ```c
/// T* vector_front(T, vector(T)* p_v)
/// ```
/// Returns a pointer to the first element in the vector, or `NULL` if empty.
#define vector_front(T, p_v) \
	(((p_v)->size > 0) ? (p_v)->p_data : NULL)

/// ```c
/// T* vector_back(T, vector(T)* p_v)
/// ```
/// Returns a pointer to the last element in the vector, or `NULL` if empty.
#define vector_back(T, p_v) \
	(((p_v)->size > 0) ? ((p_v)->p_data + (p_v)->size - 1) : NULL)

/// ```c
/// bool vector_is_empty(T, vector(T)* p_v)
/// ```
/// Checks whether the vector contains no elements.
#define vector_is_empty(T, p_v) ((p_v)->size == 0)

/// ```c
/// size_t vector_size(T, vector(T)* p_v)
/// ```
/// Returns the current number of elements in the vector as a read-only rvalue.
#define vector_size(T, p_v) ((size_t)((p_v)->size))

/// ```c
/// size_t vector_capacity(T, vector(T)* p_v)
/// ```
/// Returns the allocated capacity of the vector as a read-only rvalue.
#define vector_capacity(T, p_v) ((size_t)((p_v)->capacity))

/// ```c
/// vector_iterator(T) vector_begin(T, vector(T)* p_v)
/// ```
/// Returns an iterator pointing to the first element in the vector.
#define vector_begin(T, p_v) vector_func(begin, T)(p_v)

/// ```c
/// vector_iterator(T) vector_end(T, vector(T)* p_v)
/// ```
/// Returns an iterator pointing past the last element in the vector.
#define vector_end(T, p_v) vector_func(end, T)(p_v)

/// ```c
/// vector_iterator(T) vector_rbegin(T, vector(T)* p_v)
/// ```
/// Returns a reverse iterator pointing to the last element in the vector.
#define vector_rbegin(T, p_v) vector_func(rbegin, T)(p_v)

/// ```c
/// vector_iterator(T) vector_rend(T, vector(T)* p_v)
/// ```
/// Returns a reverse iterator pointing before the first element in the vector.
#define vector_rend(T, p_v) vector_func(rend, T)(p_v)

/// ```c
/// vector_iterator(T) vector_seek(T, vector(T)* p_v, size_t index)
/// ```
/// Returns an iterator pointing to the element at `index`.
#define vector_seek(T, p_v, index) vector_func(seek, T)(p_v, index)

/// ```c
/// vector_foreach(T, vector(T)* p_v, IT_NAME)
/// ```
/// Iterates over all elements in the vector in forward order.
#define vector_foreach(T, p_v, it) for (vector_iterator(T) it = vector_begin(T, p_v); vector_iterator_is_valid(T, &it); vector_iterator_next(T, &it))

/// ```c
/// vector_rforeach(T, vector(T)* p_v, IT_NAME)
/// ```
/// Iterates over all elements in the vector in reverse order.
#define vector_rforeach(T, p_v, it) for (vector_iterator(T) it = vector_rbegin(T, p_v); vector_iterator_is_valid(T, &it); vector_iterator_prev(T, &it))

/// Forward declares the `vector(T)` container type for prior references.
#define vector_fd(T) \
	typedef struct vector_struct(T) vector(T);

/// Declares vector struct and function prototypes in a header file.
#define vector_imp_h(T) \
	vector_iterator_imp_h(T); \
	struct vector_struct(T) { \
		T* p_data; \
		size_t size; \
		size_t capacity; \
	}; \
	void vector_func(init, T)(vector(T)* p_v); \
	vector(T) vector_func(new, T)(size_t size); \
	vector(T) vector_func(from_items, T)(const T* p_items, size_t count); \
	bool vector_func(extend_items, T)(vector(T)* p_v, const T* p_items, size_t count); \
	void vector_func(free, T)(vector(T)* p_v); \
	void vector_func(clear, T)(vector(T)* p_v); \
	bool vector_func(reserve, T)(vector(T)* p_v, size_t capacity); \
	bool vector_func(resize, T)(vector(T)* p_v, size_t size); \
	bool vector_func(push_back, T)(vector(T)* p_v, T item); \
	bool vector_func(pop_back, T)(vector(T)* p_v); \
	bool vector_func(swap_remove, T)(vector(T)* p_v, size_t index); \
	bool vector_func(shrink_to_fit, T)(vector(T)* p_v); \
	vector_iterator(T) vector_func(begin, T)(vector(T)* p_v); \
	vector_iterator(T) vector_func(end, T)(vector(T)* p_v); \
	vector_iterator(T) vector_func(rbegin, T)(vector(T)* p_v); \
	vector_iterator(T) vector_func(rend, T)(vector(T)* p_v); \
	vector_iterator(T) vector_func(seek, T)(vector(T)* p_v, size_t index);

/// Implements vector functions in a source file.
#define vector_imp_c(T) \
	vector_iterator_imp_c(T); \
	\
	void vector_func(init, T)(vector(T)* p_v) { \
		p_v->p_data = NULL; \
		p_v->size = 0; \
		p_v->capacity = 0; \
		return; \
	} \
	\
	vector(T) vector_func(new, T)(size_t size) { \
		vector(T) v; \
		vector_func(init, T)(&v); \
		if (size > 0) { \
			if (!vector_func(resize, T)(&v, size)) { \
				vector_func(free, T)(&v); \
			} \
		} \
		return v; \
	} \
	\
	vector(T) vector_func(from_items, T)(const T* p_items, size_t count) { \
		vector(T) v; \
		vector_func(init, T)(&v); \
		if (p_items && count > 0) { \
			if (!vector_func(extend_items, T)(&v, p_items, count)) { \
				vector_func(free, T)(&v); \
			} \
		} \
		return v; \
	} \
	\
	bool vector_func(extend_items, T)(vector(T)* p_v, const T* p_items, size_t count) { \
		if (!p_v || !p_items || count == 0) return true; \
		if (!vector_func(reserve, T)(p_v, p_v->size + count)) return false; \
		for (size_t i = 0; i < count; i++) { \
			*(p_v->p_data + p_v->size + i) = p_items[i]; \
		} \
		p_v->size += count; \
		return true; \
	} \
	\
	void vector_func(free, T)(vector(T)* p_v) { \
		if (p_v) { \
			vector_func(clear, T)(p_v); \
			free(p_v->p_data); \
			vector_func(init, T)(p_v); \
			return; \
		} \
	} \
	\
	void vector_func(clear, T)(vector(T)* p_v) { \
		memset(p_v->p_data, 0, p_v->size * sizeof(T)); \
		p_v->size = 0; \
		return; \
	} \
	\
	bool vector_func(reserve, T)(vector(T)* p_v, size_t capacity) { \
		if (p_v->capacity >= capacity) return true; \
		size_t new_capacity = 1; \
		if (capacity > 0) while (new_capacity <= capacity) new_capacity <<= 1; \
		if (p_v->capacity < capacity) { \
			if (p_v->capacity) { \
				if (!(p_v->p_data = (T*) realloc(p_v->p_data, new_capacity * sizeof(T)))) return false; \
				memset(p_v->p_data + p_v->size, 0, (new_capacity - p_v->size) * sizeof(T)); \
			} \
			else { \
				if (!(p_v->p_data = (T*) calloc(new_capacity, sizeof(T)))) return false; \
			} \
			p_v->capacity = new_capacity; \
		} \
		return true; \
	} \
	\
	bool vector_func(resize, T)(vector(T)* p_v, size_t size) { \
		if (vector_func(reserve, T)(p_v, size)) { \
			p_v->size = size; \
			return true; \
		} \
		return false; \
	} \
	\
	bool vector_func(push_back, T)(vector(T)* p_v, T item) { \
		if (vector_func(resize, T)(p_v, p_v->size + 1)) { \
			*(p_v->p_data + p_v->size - 1) = item; \
			return true; \
		} \
		return false; \
	} \
	\
	bool vector_func(pop_back, T)(vector(T)* p_v) { \
		if (p_v->size == 0) return false; \
		memset(p_v->p_data + p_v->size - 1, 0, sizeof(T)); \
		p_v->size--; \
		return true; \
	} \
	\
	bool vector_func(swap_remove, T)(vector(T)* p_v, size_t index) { \
		if (!p_v || index >= p_v->size) return false; \
		if (index != p_v->size - 1) { \
			*(p_v->p_data + index) = *(p_v->p_data + p_v->size - 1); \
		} \
		return vector_func(pop_back, T)(p_v); \
	} \
	\
	bool vector_func(shrink_to_fit, T)(vector(T)* p_v) { \
		if (!p_v) return false; \
		if (p_v->size == p_v->capacity) return true; \
		if (p_v->size == 0) { \
			free(p_v->p_data); \
			p_v->p_data = NULL; \
			p_v->capacity = 0; \
			return true; \
		} \
		T* p_new_data = (T*) realloc(p_v->p_data, p_v->size * sizeof(T)); \
		if (!p_new_data) return false; \
		p_v->p_data = p_new_data; \
		p_v->capacity = p_v->size; \
		return true; \
	} \
	\
	vector_iterator(T) vector_func(begin, T)(vector(T)* p_v) { \
		vector_iterator(T) it = { p_v, 0 }; \
		return it; \
	} \
	\
	vector_iterator(T) vector_func(end, T)(vector(T)* p_v) { \
		vector_iterator(T) it = { p_v, p_v ? p_v->size : 0 }; \
		return it; \
	} \
	\
	vector_iterator(T) vector_func(rbegin, T)(vector(T)* p_v) { \
		vector_iterator(T) it = { p_v, (p_v && p_v->size > 0) ? p_v->size - 1 : (size_t)-1 }; \
		return it; \
	} \
	\
	vector_iterator(T) vector_func(rend, T)(vector(T)* p_v) { \
		vector_iterator(T) it = { p_v, (size_t)-1 }; \
		return it; \
	} \
	\
	vector_iterator(T) vector_func(seek, T)(vector(T)* p_v, size_t index) { \
		vector_iterator(T) it = { p_v, (p_v && index < p_v->size) ? index : (size_t)-1 }; \
		return it; \
	}

#endif