linearmap.h

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

#ifndef __CCTL_LINEARMAP_H__
#define __CCTL_LINEARMAP_H__

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

#include "cctl.h"
#include "utils.h"
#include "vector.h"

// LinearMap Pair

/// `linearmap_pair(K, V)` ⇒ `K_V_linearmap_pair`
/// 
/// Generates the key-value pair type name for `linearmap(K, V)`.
#define linearmap_pair(K, V) cctl_join3(K, V, linearmap_pair)

/// `linearmap_pair_struct(K, V)` ⇒ `struct K_V_linearmap_pair_struct`
/// 
/// Generates the underlying structure tag for `linearmap_pair(K, V)`.
#define linearmap_pair_struct(K, V) cctl_join(linearmap_pair(K, V), struct)

/// `linearmap_vector(K, V)` ⇒ `K_V_linearmap_pair_vector`
/// 
/// Generates the underlying vector container type name for `linearmap(K, V)`.
#define linearmap_vector(K, V) vector(linearmap_pair(K, V))


// LinearMap Iterator

/// `linearmap_iterator(K, V)` ⇒ `K_V_linearmap_iterator`
/// 
/// Generates the iterator type name for `linearmap(K, V)`.
#define linearmap_iterator(K, V) cctl_join3(K, V, linearmap_iterator)

/// `linearmap_iterator_func(FUNC, K, V)` ⇒ `K_V_linearmap_iterator_FUNC`
/// 
/// Generates a mangled function identifier for `linearmap_iterator(K, V)`.
#define linearmap_iterator_func(FUNC, K, V) cctl_join(linearmap_iterator(K, V), FUNC)

/// `linearmap_iterator_struct(K, V)` ⇒ `struct K_V_linearmap_iterator_struct`
/// 
/// Generates the underlying structure tag for `linearmap_iterator(K, V)`.
#define linearmap_iterator_struct(K, V) cctl_join(linearmap_iterator(K, V), struct)

/// ```c
/// V* linearmap_iterator_get_value(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Returns a mutable pointer to the value at the current iterator position, or `NULL` if invalid.
#define linearmap_iterator_get_value(K, V, p_it) \
	(((p_it)->p_lm && (p_it)->index < (p_it)->p_lm->vec.size) ? &((p_it)->p_lm->vec.p_data[(p_it)->index].value) : NULL)

/// ```c
/// V* linearmap_iterator_get(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Short alias for `linearmap_iterator_get_value`.
#define linearmap_iterator_get(K, V, p_it) linearmap_iterator_get_value(K, V, p_it)

/// ```c
/// const K* linearmap_iterator_get_key_ref(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Returns a direct read-only pointer to the key at the current iterator position, or `NULL` if invalid.
#define linearmap_iterator_get_key_ref(K, V, p_it) \
	(((p_it)->p_lm && (p_it)->index < (p_it)->p_lm->vec.size) ? &((p_it)->p_lm->vec.p_data[(p_it)->index].key) : NULL)

/// ```c
/// K* linearmap_iterator_get_key(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Returns a newly allocated pointer containing a deep copy of the key at the current iterator position.
/// The caller is responsible for freeing this pointer.
#define linearmap_iterator_get_key(K, V, p_it) linearmap_iterator_func(get_key, K, V)(p_it)

/// ```c
/// bool linearmap_iterator_is_valid(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Checks whether the iterator currently points to a valid element within bounds.
#define linearmap_iterator_is_valid(K, V, p_it) \
	((p_it)->p_lm && (p_it)->index < (p_it)->p_lm->vec.size)

/// ```c
/// bool linearmap_iterator_is_equal(K, V, linearmap_iterator(K, V)* p_it1, linearmap_iterator(K, V)* p_it2)
/// ```
/// Checks whether two iterators point to the same linearmap and index.
#define linearmap_iterator_is_equal(K, V, p_it1, p_it2) \
	((p_it1)->p_lm == (p_it2)->p_lm && (p_it1)->index == (p_it2)->index)

/// ```c
/// void linearmap_iterator_next(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Advances the iterator forward to the next element.
#define linearmap_iterator_next(K, V, p_it) ((p_it)->index++)

/// ```c
/// void linearmap_iterator_prev(K, V, linearmap_iterator(K, V)* p_it)
/// ```
/// Moves the iterator backward to the previous element.
#define linearmap_iterator_prev(K, V, p_it) ((p_it)->index--)

/// Declares linearmap iterator struct and function prototypes in a header file.
#define linearmap_iterator_imp_h(K, V) \
	typedef struct linearmap_iterator_struct(K, V) linearmap_iterator(K, V); \
	struct linearmap_iterator_struct(K, V) { \
		linearmap(K, V)* p_lm; \
		size_t index; \
	}; \
	\
	K* linearmap_iterator_func(get_key, K, V)(linearmap_iterator(K, V)* p_it);

/// Implements linearmap iterator functions in a source file.
#define linearmap_iterator_imp_c(K, V) \
	K* linearmap_iterator_func(get_key, K, V)(linearmap_iterator(K, V)* p_it) { \
		if (!linearmap_iterator_is_valid(K, V, p_it)) return NULL; \
		K* p_key = (K*) malloc(sizeof(K)); \
		if (!p_key) return NULL; \
		*p_key = (p_it)->p_lm->fp_copy_func ? (p_it)->p_lm->fp_copy_func((p_it)->p_lm->vec.p_data[(p_it)->index].key) : (p_it)->p_lm->vec.p_data[(p_it)->index].key; \
		return p_key; \
	}


// LinearMap

/// `linearmap(K, V)` ⇒ `K_V_linearmap`
/// 
/// Generates the insertion-order vector-backed key-value multi-map container type name for `K` and `V`.
#define linearmap(K, V) cctl_join3(K, V, linearmap)

/// `linearmap_func(FUNC, K, V)` ⇒ `K_V_linearmap_FUNC`
/// 
/// Generates a mangled function identifier for `linearmap(K, V)`.
#define linearmap_func(FUNC, K, V) cctl_join(linearmap(K, V), FUNC)

/// `linearmap_struct(K, V)` ⇒ `struct K_V_linearmap_struct`
/// 
/// Generates the underlying structure tag for `linearmap(K, V)`.
#define linearmap_struct(K, V) cctl_join(linearmap(K, V), struct)

/// ```c
/// void linearmap_init(K, V, linearmap(K, V)* p_lm)
/// ```
/// Initializes the linearmap into an empty state and binds default generic callback hooks.
#define linearmap_init(K, V, p_lm) linearmap_func(init, K, V)(p_lm)

/// ```c
/// linearmap(K, V) linearmap_new(K, V)
/// ```
/// Value-returning constructor creating an empty linearmap.
#define linearmap_new(K, V) linearmap_func(new, K, V)()

/// ```c
/// linearmap(K, V) linearmap_from_items(K, V, ...)
/// ```
/// Creates a linearmap populated with the provided key-value pairs in the specified order.
#define linearmap_from_items(K, V, ...) \
	linearmap_func(from_items, K, V)( \
		(const linearmap_pair(K, V)[]) { __VA_ARGS__ }, \
		sizeof((const linearmap_pair(K, V)[]) { __VA_ARGS__ }) / sizeof(linearmap_pair(K, V)) \
	)

/// ```c
/// bool linearmap_extend_items(K, V, linearmap(K, V)* p_lm, ...)
/// ```
/// Appends multiple key-value pairs to the linearmap.
#define linearmap_extend_items(K, V, p_lm, ...) \
	linearmap_func(extend_items, K, V)( \
		p_lm, \
		(const linearmap_pair(K, V)[]) { __VA_ARGS__ }, \
		sizeof((const linearmap_pair(K, V)[]) { __VA_ARGS__ }) / sizeof(linearmap_pair(K, V)) \
	)

/// ```c
/// void linearmap_free(K, V, linearmap(K, V)* p_lm)
/// ```
/// Frees all keys, internal storage, and resets the linearmap to an empty state.
#define linearmap_free(K, V, p_lm) linearmap_func(free, K, V)(p_lm)

/// ```c
/// void linearmap_clear(K, V, linearmap(K, V)* p_lm)
/// ```
/// Removes and frees all keys, clearing the linearmap while preserving capacity.
#define linearmap_clear(K, V, p_lm) linearmap_func(clear, K, V)(p_lm)

/// ```c
/// bool linearmap_reserve(K, V, linearmap(K, V)* p_lm, size_t capacity)
/// ```
/// Pre-allocates memory to hold at least `capacity` elements.
#define linearmap_reserve(K, V, p_lm, capacity) linearmap_func(reserve, K, V)(p_lm, capacity)

/// ```c
/// bool linearmap_shrink_to_fit(K, V, linearmap(K, V)* p_lm)
/// ```
/// Shrinks internal capacity to match the current number of elements.
#define linearmap_shrink_to_fit(K, V, p_lm) linearmap_func(shrink_to_fit, K, V)(p_lm)

/// ```c
/// bool linearmap_is_empty(K, V, linearmap(K, V)* p_lm)
/// ```
/// Checks whether the linearmap contains no elements.
#define linearmap_is_empty(K, V, p_lm) ((p_lm)->vec.size == 0)

/// ```c
/// size_t linearmap_size(K, V, linearmap(K, V)* p_lm)
/// ```
/// Returns the number of key-value pairs in the linearmap.
#define linearmap_size(K, V, p_lm) ((size_t)((p_lm)->vec.size))

/// ```c
/// size_t linearmap_capacity(K, V, linearmap(K, V)* p_lm)
/// ```
/// Returns the allocated capacity of the linearmap.
#define linearmap_capacity(K, V, p_lm) ((size_t)((p_lm)->vec.capacity))

/// ```c
/// void linearmap_set_compare_func(K, V, linearmap(K, V)* p_lm, int (*fp_comp_func)(K, K))
/// ```
/// Registers a custom key comparison function.
#define linearmap_set_compare_func(K, V, p_lm, fp_comp_func) ((p_lm)->fp_compare_func = (fp_comp_func))

/// ```c
/// void linearmap_set_copy_func(K, V, linearmap(K, V)* p_lm, K (*fp_copy_func)(K))
/// ```
/// Registers a custom key deep copy function.
#define linearmap_set_copy_func(K, V, p_lm, fp_copy_func) ((p_lm)->fp_copy_func = (fp_copy_func))

/// ```c
/// void linearmap_set_free_func(K, V, linearmap(K, V)* p_lm, void (*fp_free_func)(K))
/// ```
/// Registers a custom key destruction/free callback.
#define linearmap_set_free_func(K, V, p_lm, fp_free_func) ((p_lm)->fp_free_func = (fp_free_func))

/// ```c
/// bool linearmap_insert(K, V, linearmap(K, V)* p_lm, K key, V value)
/// ```
/// Appends `key` and `value` to the end of the linearmap in O(1) amortized time.
/// Duplicate keys are allowed (multi-map behavior).
#define linearmap_insert(K, V, p_lm, key, value) linearmap_func(insert, K, V)(p_lm, key, value)

/// ```c
/// bool linearmap_remove(K, V, linearmap(K, V)* p_lm, K key)
/// ```
/// Removes the first occurrence of `key` from the front. Returns `true` if found and removed.
#define linearmap_remove(K, V, p_lm, key) linearmap_func(remove, K, V)(p_lm, key)

/// ```c
/// bool linearmap_rremove(K, V, linearmap(K, V)* p_lm, K key)
/// ```
/// Removes the latest occurrence of `key` from the back. Returns `true` if found and removed.
#define linearmap_rremove(K, V, p_lm, key) linearmap_func(rremove, K, V)(p_lm, key)

/// ```c
/// bool linearmap_contains(K, V, linearmap(K, V)* p_lm, K key)
/// ```
/// Checks whether `key` exists in the linearmap.
#define linearmap_contains(K, V, p_lm, key) (linearmap_find(K, V, p_lm, key) != NULL)

/// ```c
/// V* linearmap_find(K, V, linearmap(K, V)* p_lm, K key)
/// ```
/// Searches forward for `key`. Returns a pointer to the first value, or `NULL` if not found.
#define linearmap_find(K, V, p_lm, key) linearmap_func(find, K, V)(p_lm, key)

/// ```c
/// V* linearmap_rfind(K, V, linearmap(K, V)* p_lm, K key)
/// ```
/// Searches backward for `key`. Returns a pointer to the most recently inserted value, or `NULL` if not found.
#define linearmap_rfind(K, V, p_lm, key) linearmap_func(rfind, K, V)(p_lm, key)

/// ```c
/// linearmap_iterator(K, V) linearmap_rfind_iterator(K, V, linearmap(K, V)* p_lm, K key)
/// ```
/// Searches backward for `key` and returns an iterator pointing to the match, or end iterator if not found.
#define linearmap_rfind_iterator(K, V, p_lm, key) linearmap_func(rfind_iterator, K, V)(p_lm, key)

/// ```c
/// V linearmap_get_or_default(K, V, linearmap(K, V)* p_lm, K key, V default_value)
/// ```
/// Returns the first value mapped to `key`, or `default_value` if not found.
#define linearmap_get_or_default(K, V, p_lm, key, default_value) \
	linearmap_func(get_or_default, K, V)(p_lm, key, default_value)

/// ```c
/// K* linearmap_min_key(K, V, linearmap(K, V)* p_lm)
/// ```
/// Scans the map in O(N) to find and deep copy the smallest key. Caller must free the pointer.
#define linearmap_min_key(K, V, p_lm) linearmap_func(min_key, K, V)(p_lm)

/// ```c
/// const K* linearmap_min_key_ref(K, V, linearmap(K, V)* p_lm)
/// ```
/// Scans the map in O(N) to return a read-only pointer to the smallest key.
#define linearmap_min_key_ref(K, V, p_lm) linearmap_func(min_key_ref, K, V)(p_lm)

/// ```c
/// K* linearmap_max_key(K, V, linearmap(K, V)* p_lm)
/// ```
/// Scans the map in O(N) to find and deep copy the largest key. Caller must free the pointer.
#define linearmap_max_key(K, V, p_lm) linearmap_func(max_key, K, V)(p_lm)

/// ```c
/// const K* linearmap_max_key_ref(K, V, linearmap(K, V)* p_lm)
/// ```
/// Scans the map in O(N) to return a read-only pointer to the largest key.
#define linearmap_max_key_ref(K, V, p_lm) linearmap_func(max_key_ref, K, V)(p_lm)

/// ```c
/// linearmap_iterator(K, V) linearmap_begin(K, V, linearmap(K, V)* p_lm)
/// ```
/// Returns an iterator pointing to the first element in insertion order.
#define linearmap_begin(K, V, p_lm) linearmap_func(begin, K, V)(p_lm)

/// ```c
/// linearmap_iterator(K, V) linearmap_end(K, V, linearmap(K, V)* p_lm)
/// ```
/// Returns an iterator pointing past the last element in the linearmap.
#define linearmap_end(K, V, p_lm) linearmap_func(end, K, V)(p_lm)

/// ```c
/// linearmap_iterator(K, V) linearmap_rbegin(K, V, linearmap(K, V)* p_lm)
/// ```
/// Returns a reverse iterator pointing to the last inserted element in the linearmap.
#define linearmap_rbegin(K, V, p_lm) linearmap_func(rbegin, K, V)(p_lm)

/// ```c
/// linearmap_iterator(K, V) linearmap_rend(K, V, linearmap(K, V)* p_lm)
/// ```
/// Returns a reverse iterator pointing before the first element in the linearmap.
#define linearmap_rend(K, V, p_lm) linearmap_func(rend, K, V)(p_lm)

/// ```c
/// linearmap_iterator(K, V) linearmap_seek(K, V, linearmap(K, V)* p_lm, size_t index)
/// ```
/// Returns an O(1) iterator pointing to the element at insertion index `index`.
#define linearmap_seek(K, V, p_lm, index) linearmap_func(seek, K, V)(p_lm, index)

/// ```c
/// linearmap_foreach(K, V, linearmap(K, V)* p_lm, IT_NAME)
/// ```
/// Iterates over all key-value pairs in insertion order.
#define linearmap_foreach(K, V, p_lm, it) \
	for (linearmap_iterator(K, V) it = linearmap_begin(K, V, p_lm); linearmap_iterator_is_valid(K, V, &it); linearmap_iterator_next(K, V, &it))

/// ```c
/// linearmap_rforeach(K, V, linearmap(K, V)* p_lm, IT_NAME)
/// ```
/// Iterates over all key-value pairs in reverse insertion order.
#define linearmap_rforeach(K, V, p_lm, it) \
	for (linearmap_iterator(K, V) it = linearmap_rbegin(K, V, p_lm); linearmap_iterator_is_valid(K, V, &it); linearmap_iterator_prev(K, V, &it))

/// Forward declares the `linearmap(K, V)` container type for prior references.
#define linearmap_fd(K, V) \
	typedef struct linearmap_pair_struct(K, V) linearmap_pair(K, V); \
	vector_fd(linearmap_pair(K, V)); \
	typedef struct linearmap_iterator_struct(K, V) linearmap_iterator(K, V); \
	typedef struct linearmap_struct(K, V) linearmap(K, V);

/// Declares linearmap struct and function prototypes in a header file.
#define linearmap_imp_h(K, V) \
	struct linearmap_pair_struct(K, V) { \
		K key; \
		V value; \
	}; \
	\
	vector_imp_h(linearmap_pair(K, V)); \
	linearmap_iterator_imp_h(K, V); \
	\
	struct linearmap_struct(K, V) { \
		linearmap_vector(K, V) vec; \
		int (*fp_compare_func)(K, K); \
		K (*fp_copy_func)(K); \
		void (*fp_free_func)(K); \
	}; \
	\
	void linearmap_func(init, K, V)(linearmap(K, V)* p_lm); \
	linearmap(K, V) linearmap_func(new, K, V)(void); \
	linearmap(K, V) linearmap_func(from_items, K, V)(const linearmap_pair(K, V)* p_items, size_t count); \
	bool linearmap_func(extend_items, K, V)(linearmap(K, V)* p_lm, const linearmap_pair(K, V)* p_items, size_t count); \
	void linearmap_func(free, K, V)(linearmap(K, V)* p_lm); \
	void linearmap_func(clear, K, V)(linearmap(K, V)* p_lm); \
	bool linearmap_func(reserve, K, V)(linearmap(K, V)* p_lm, size_t capacity); \
	bool linearmap_func(shrink_to_fit, K, V)(linearmap(K, V)* p_lm); \
	bool linearmap_func(insert, K, V)(linearmap(K, V)* p_lm, K key, V value); \
	bool linearmap_func(remove, K, V)(linearmap(K, V)* p_lm, K key); \
	bool linearmap_func(rremove, K, V)(linearmap(K, V)* p_lm, K key); \
	V* linearmap_func(find, K, V)(linearmap(K, V)* p_lm, K key); \
	V* linearmap_func(rfind, K, V)(linearmap(K, V)* p_lm, K key); \
	linearmap_iterator(K, V) linearmap_func(rfind_iterator, K, V)(linearmap(K, V)* p_lm, K key); \
	V linearmap_func(get_or_default, K, V)(linearmap(K, V)* p_lm, K key, V default_value); \
	K* linearmap_func(min_key, K, V)(linearmap(K, V)* p_lm); \
	const K* linearmap_func(min_key_ref, K, V)(linearmap(K, V)* p_lm); \
	K* linearmap_func(max_key, K, V)(linearmap(K, V)* p_lm); \
	const K* linearmap_func(max_key_ref, K, V)(linearmap(K, V)* p_lm); \
	linearmap_iterator(K, V) linearmap_func(begin, K, V)(linearmap(K, V)* p_lm); \
	linearmap_iterator(K, V) linearmap_func(end, K, V)(linearmap(K, V)* p_lm); \
	linearmap_iterator(K, V) linearmap_func(rbegin, K, V)(linearmap(K, V)* p_lm); \
	linearmap_iterator(K, V) linearmap_func(rend, K, V)(linearmap(K, V)* p_lm); \
	linearmap_iterator(K, V) linearmap_func(seek, K, V)(linearmap(K, V)* p_lm, size_t index);

/// Implements linearmap functions in a source file.
#define linearmap_imp_c(K, V) \
	vector_imp_c(linearmap_pair(K, V)); \
	linearmap_iterator_imp_c(K, V); \
	\
	void linearmap_func(init, K, V)(linearmap(K, V)* p_lm) { \
		if (!p_lm) return; \
		vector_func(init, linearmap_pair(K, V))(&p_lm->vec); \
		p_lm->fp_compare_func = cctl_get_default_compare_func(K); \
		p_lm->fp_copy_func = cctl_get_default_copy_func(K); \
		p_lm->fp_free_func = cctl_get_default_free_func(K); \
	} \
	\
	linearmap(K, V) linearmap_func(new, K, V)(void) { \
		linearmap(K, V) lm; \
		linearmap_func(init, K, V)(&lm); \
		return lm; \
	} \
	\
	linearmap(K, V) linearmap_func(from_items, K, V)(const linearmap_pair(K, V)* p_items, size_t count) { \
		linearmap(K, V) lm; \
		linearmap_func(init, K, V)(&lm); \
		if (p_items && count > 0) { \
			if (!linearmap_func(extend_items, K, V)(&lm, p_items, count)) { \
				linearmap_func(free, K, V)(&lm); \
			} \
		} \
		return lm; \
	} \
	\
	bool linearmap_func(extend_items, K, V)(linearmap(K, V)* p_lm, const linearmap_pair(K, V)* p_items, size_t count) { \
		if (!p_lm || !p_items || count == 0) return true; \
		for (size_t i = 0; i < count; i++) { \
			if (!linearmap_func(insert, K, V)(p_lm, p_items[i].key, p_items[i].value)) return false; \
		} \
		return true; \
	} \
	\
	void linearmap_func(clear, K, V)(linearmap(K, V)* p_lm) { \
		if (!p_lm) return; \
		if (p_lm->fp_free_func) { \
			for (size_t i = 0; i < p_lm->vec.size; i++) { \
				p_lm->fp_free_func(p_lm->vec.p_data[i].key); \
			} \
		} \
		vector_func(clear, linearmap_pair(K, V))(&p_lm->vec); \
	} \
	\
	void linearmap_func(free, K, V)(linearmap(K, V)* p_lm) { \
		if (!p_lm) return; \
		linearmap_func(clear, K, V)(p_lm); \
		vector_func(free, linearmap_pair(K, V))(&p_lm->vec); \
		linearmap_func(init, K, V)(p_lm); \
	} \
	\
	bool linearmap_func(reserve, K, V)(linearmap(K, V)* p_lm, size_t capacity) { \
		if (!p_lm) return false; \
		return vector_func(reserve, linearmap_pair(K, V))(&p_lm->vec, capacity); \
	} \
	\
	bool linearmap_func(shrink_to_fit, K, V)(linearmap(K, V)* p_lm) { \
		if (!p_lm) return false; \
		return vector_func(shrink_to_fit, linearmap_pair(K, V))(&p_lm->vec); \
	} \
	\
	bool linearmap_func(insert, K, V)(linearmap(K, V)* p_lm, K key, V value) { \
		if (!p_lm) return false; \
		K copied_key = p_lm->fp_copy_func ? p_lm->fp_copy_func(key) : key; \
		linearmap_pair(K, V) item = { copied_key, value }; \
		if (!vector_func(push_back, linearmap_pair(K, V))(&p_lm->vec, item)) { \
			if (p_lm->fp_free_func) p_lm->fp_free_func(copied_key); \
			return false; \
		} \
		return true; \
	} \
	\
	bool linearmap_func(remove, K, V)(linearmap(K, V)* p_lm, K key) { \
		if (!p_lm || p_lm->vec.size == 0) return false; \
		for (size_t i = 0; i < p_lm->vec.size; i++) { \
			if (p_lm->fp_compare_func(p_lm->vec.p_data[i].key, key) == 0) { \
				if (p_lm->fp_free_func) { \
					p_lm->fp_free_func(p_lm->vec.p_data[i].key); \
				} \
				if (i < p_lm->vec.size - 1) { \
					memmove( \
						p_lm->vec.p_data + i, \
						p_lm->vec.p_data + i + 1, \
						(p_lm->vec.size - 1 - i) * sizeof(linearmap_pair(K, V)) \
					); \
				} \
				p_lm->vec.size--; \
				return true; \
			} \
		} \
		return false; \
	} \
	\
	bool linearmap_func(rremove, K, V)(linearmap(K, V)* p_lm, K key) { \
		if (!p_lm || p_lm->vec.size == 0) return false; \
		for (size_t i = p_lm->vec.size; i > 0; i--) { \
			if (p_lm->fp_compare_func(p_lm->vec.p_data[i - 1].key, key) == 0) { \
				size_t index = i - 1; \
				if (p_lm->fp_free_func) { \
					p_lm->fp_free_func(p_lm->vec.p_data[index].key); \
				} \
				if (index < p_lm->vec.size - 1) { \
					memmove( \
						p_lm->vec.p_data + index, \
						p_lm->vec.p_data + index + 1, \
						(p_lm->vec.size - 1 - index) * sizeof(linearmap_pair(K, V)) \
					); \
				} \
				p_lm->vec.size--; \
				return true; \
			} \
		} \
		return false; \
	} \
	\
	V* linearmap_func(find, K, V)(linearmap(K, V)* p_lm, K key) { \
		if (!p_lm || p_lm->vec.size == 0) return NULL; \
		for (size_t i = 0; i < p_lm->vec.size; i++) { \
			if (p_lm->fp_compare_func(p_lm->vec.p_data[i].key, key) == 0) { \
				return &p_lm->vec.p_data[i].value; \
			} \
		} \
		return NULL; \
	} \
	\
	V* linearmap_func(rfind, K, V)(linearmap(K, V)* p_lm, K key) { \
		if (!p_lm || p_lm->vec.size == 0) return NULL; \
		for (size_t i = p_lm->vec.size; i > 0; i--) { \
			if (p_lm->fp_compare_func(p_lm->vec.p_data[i - 1].key, key) == 0) { \
				return &p_lm->vec.p_data[i - 1].value; \
			} \
		} \
		return NULL; \
	} \
	\
	linearmap_iterator(K, V) linearmap_func(rfind_iterator, K, V)(linearmap(K, V)* p_lm, K key) { \
		if (p_lm && p_lm->vec.size > 0) { \
			for (size_t i = p_lm->vec.size; i > 0; i--) { \
				if (p_lm->fp_compare_func(p_lm->vec.p_data[i - 1].key, key) == 0) { \
					linearmap_iterator(K, V) it = { p_lm, i - 1 }; \
					return it; \
				} \
			} \
		} \
		linearmap_iterator(K, V) it_end = { p_lm, p_lm ? p_lm->vec.size : 0 }; \
		return it_end; \
	} \
	\
	V linearmap_func(get_or_default, K, V)(linearmap(K, V)* p_lm, K key, V default_value) { \
		V* p_val = linearmap_func(find, K, V)(p_lm, key); \
		return p_val ? *p_val : default_value; \
	} \
	\
	const K* linearmap_func(min_key_ref, K, V)(linearmap(K, V)* p_lm) { \
		if (!p_lm || p_lm->vec.size == 0) return NULL; \
		size_t min_idx = 0; \
		for (size_t i = 1; i < p_lm->vec.size; i++) { \
			if (p_lm->fp_compare_func(p_lm->vec.p_data[i].key, p_lm->vec.p_data[min_idx].key) < 0) { \
				min_idx = i; \
			} \
		} \
		return &p_lm->vec.p_data[min_idx].key; \
	} \
	\
	K* linearmap_func(min_key, K, V)(linearmap(K, V)* p_lm) { \
		const K* p_ref = linearmap_func(min_key_ref, K, V)(p_lm); \
		if (!p_ref) return NULL; \
		K* p_key = (K*) malloc(sizeof(K)); \
		if (!p_key) return NULL; \
		*p_key = p_lm->fp_copy_func ? p_lm->fp_copy_func(*p_ref) : *p_ref; \
		return p_key; \
	} \
	\
	const K* linearmap_func(max_key_ref, K, V)(linearmap(K, V)* p_lm) { \
		if (!p_lm || p_lm->vec.size == 0) return NULL; \
		size_t max_idx = 0; \
		for (size_t i = 1; i < p_lm->vec.size; i++) { \
			if (p_lm->fp_compare_func(p_lm->vec.p_data[i].key, p_lm->vec.p_data[max_idx].key) > 0) { \
				max_idx = i; \
			} \
		} \
		return &p_lm->vec.p_data[max_idx].key; \
	} \
	\
	K* linearmap_func(max_key, K, V)(linearmap(K, V)* p_lm) { \
		const K* p_ref = linearmap_func(max_key_ref, K, V)(p_lm); \
		if (!p_ref) return NULL; \
		K* p_key = (K*) malloc(sizeof(K)); \
		if (!p_key) return NULL; \
		*p_key = p_lm->fp_copy_func ? p_lm->fp_copy_func(*p_ref) : *p_ref; \
		return p_key; \
	} \
	\
	linearmap_iterator(K, V) linearmap_func(begin, K, V)(linearmap(K, V)* p_lm) { \
		linearmap_iterator(K, V) it = { p_lm, 0 }; \
		return it; \
	} \
	\
	linearmap_iterator(K, V) linearmap_func(end, K, V)(linearmap(K, V)* p_lm) { \
		linearmap_iterator(K, V) it = { p_lm, p_lm ? p_lm->vec.size : 0 }; \
		return it; \
	} \
	\
	linearmap_iterator(K, V) linearmap_func(rbegin, K, V)(linearmap(K, V)* p_lm) { \
		linearmap_iterator(K, V) it = { p_lm, (p_lm && p_lm->vec.size > 0) ? (p_lm->vec.size - 1) : (size_t)-1 }; \
		return it; \
	} \
	\
	linearmap_iterator(K, V) linearmap_func(rend, K, V)(linearmap(K, V)* p_lm) { \
		linearmap_iterator(K, V) it = { p_lm, (size_t)-1 }; \
		return it; \
	} \
	\
	linearmap_iterator(K, V) linearmap_func(seek, K, V)(linearmap(K, V)* p_lm, size_t index) { \
		linearmap_iterator(K, V) it = { p_lm, index }; \
		return it; \
	}

#endif