flatmap.h

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

#ifndef __CCTL_FLATMAP_H__
#define __CCTL_FLATMAP_H__

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

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

// FlatMap Pair

/// `flatmap_pair(K, V)` ⇒ `K_V_flatmap_pair`
/// 
/// Generates the key-value pair type name for `flatmap(K, V)`.
#define flatmap_pair(K, V) cctl_join3(K, V, flatmap_pair)

/// `flatmap_pair_struct(K, V)` ⇒ `struct K_V_flatmap_pair_struct`
/// 
/// Generates the underlying structure tag for `flatmap_pair(K, V)`.
#define flatmap_pair_struct(K, V) cctl_join(flatmap_pair(K, V), struct)

/// `flatmap_vector(K, V)` ⇒ `K_V_flatmap_pair_vector`
/// 
/// Generates the underlying vector container type name for `flatmap(K, V)`.
#define flatmap_vector(K, V) vector(flatmap_pair(K, V))


// FlatMap Iterator

/// `flatmap_iterator(K, V)` ⇒ `K_V_flatmap_iterator`
/// 
/// Generates the iterator type name for `flatmap(K, V)`.
#define flatmap_iterator(K, V) cctl_join3(K, V, flatmap_iterator)

/// `flatmap_iterator_func(FUNC, K, V)` ⇒ `K_V_flatmap_iterator_FUNC`
/// 
/// Generates a mangled function identifier for `flatmap_iterator(K, V)`.
#define flatmap_iterator_func(FUNC, K, V) cctl_join(flatmap_iterator(K, V), FUNC)

/// `flatmap_iterator_struct(K, V)` ⇒ `struct K_V_flatmap_iterator_struct`
/// 
/// Generates the underlying structure tag for `flatmap_iterator(K, V)`.
#define flatmap_iterator_struct(K, V) cctl_join(flatmap_iterator(K, V), struct)

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

/// ```c
/// V* flatmap_iterator_get(K, V, flatmap_iterator(K, V)* p_it)
/// ```
/// Short alias for `flatmap_iterator_get_value`.
#define flatmap_iterator_get(K, V, p_it) flatmap_iterator_get_value(K, V, p_it)

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

/// ```c
/// K* flatmap_iterator_get_key(K, V, flatmap_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 flatmap_iterator_get_key(K, V, p_it) flatmap_iterator_func(get_key, K, V)(p_it)

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

/// ```c
/// bool flatmap_iterator_is_equal(K, V, flatmap_iterator(K, V)* p_it1, flatmap_iterator(K, V)* p_it2)
/// ```
/// Checks whether two iterators point to the same flatmap and index.
#define flatmap_iterator_is_equal(K, V, p_it1, p_it2) \
	((p_it1)->p_fm == (p_it2)->p_fm && (p_it1)->index == (p_it2)->index)

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

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

/// Declares flatmap iterator struct and function prototypes in a header file.
#define flatmap_iterator_imp_h(K, V) \
	typedef struct flatmap_iterator_struct(K, V) flatmap_iterator(K, V); \
	struct flatmap_iterator_struct(K, V) { \
		flatmap(K, V)* p_fm; \
		size_t index; \
	}; \
	\
	K* flatmap_iterator_func(get_key, K, V)(flatmap_iterator(K, V)* p_it);

/// Implements flatmap iterator functions in a source file.
#define flatmap_iterator_imp_c(K, V) \
	K* flatmap_iterator_func(get_key, K, V)(flatmap_iterator(K, V)* p_it) { \
		if (!flatmap_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_fm->fp_copy_func ? (p_it)->p_fm->fp_copy_func((p_it)->p_fm->vec.p_data[(p_it)->index].key) : (p_it)->p_fm->vec.p_data[(p_it)->index].key; \
		return p_key; \
	}


// FlatMap

/// `flatmap(K, V)` ⇒ `K_V_flatmap`
/// 
/// Generates the sorted vector-backed key-value map container type name for `K` and `V`.
#define flatmap(K, V) cctl_join3(K, V, flatmap)

/// `flatmap_func(FUNC, K, V)` ⇒ `K_V_flatmap_FUNC`
/// 
/// Generates a mangled function identifier for `flatmap(K, V)`.
#define flatmap_func(FUNC, K, V) cctl_join(flatmap(K, V), FUNC)

/// `flatmap_struct(K, V)` ⇒ `struct K_V_flatmap_struct`
/// 
/// Generates the underlying structure tag for `flatmap(K, V)`.
#define flatmap_struct(K, V) cctl_join(flatmap(K, V), struct)

/// ```c
/// void flatmap_init(K, V, flatmap(K, V)* p_fm)
/// ```
/// Initializes the flatmap into an empty state and binds default generic callback hooks.
#define flatmap_init(K, V, p_fm) flatmap_func(init, K, V)(p_fm)

/// ```c
/// flatmap(K, V) flatmap_new(K, V)
/// ```
/// Value-returning constructor creating an empty flatmap.
#define flatmap_new(K, V) flatmap_func(new, K, V)()

/// ```c
/// flatmap(K, V) flatmap_from_items(K, V, ...)
/// ```
/// Creates a flatmap populated with the provided key-value pairs.
#define flatmap_from_items(K, V, ...) \
	flatmap_func(from_items, K, V)( \
		(const flatmap_pair(K, V)[]) { __VA_ARGS__ }, \
		sizeof((const flatmap_pair(K, V)[]) { __VA_ARGS__ }) / sizeof(flatmap_pair(K, V)) \
	)

/// ```c
/// bool flatmap_extend_items(K, V, flatmap(K, V)* p_fm, ...)
/// ```
/// Bulk-inserts multiple key-value pairs into the flatmap.
#define flatmap_extend_items(K, V, p_fm, ...) \
	flatmap_func(extend_items, K, V)( \
		p_fm, \
		(const flatmap_pair(K, V)[]) { __VA_ARGS__ }, \
		sizeof((const flatmap_pair(K, V)[]) { __VA_ARGS__ }) / sizeof(flatmap_pair(K, V)) \
	)

/// ```c
/// void flatmap_free(K, V, flatmap(K, V)* p_fm)
/// ```
/// Frees all keys, internal storage, and resets the flatmap to an empty state.
#define flatmap_free(K, V, p_fm) flatmap_func(free, K, V)(p_fm)

/// ```c
/// void flatmap_clear(K, V, flatmap(K, V)* p_fm)
/// ```
/// Removes and frees all keys, clearing the flatmap while preserving capacity.
#define flatmap_clear(K, V, p_fm) flatmap_func(clear, K, V)(p_fm)

/// ```c
/// bool flatmap_reserve(K, V, flatmap(K, V)* p_fm, size_t capacity)
/// ```
/// Pre-allocates memory to hold at least `capacity` elements.
#define flatmap_reserve(K, V, p_fm, capacity) flatmap_func(reserve, K, V)(p_fm, capacity)

/// ```c
/// bool flatmap_shrink_to_fit(K, V, flatmap(K, V)* p_fm)
/// ```
/// Shrinks internal capacity to match the current number of elements.
#define flatmap_shrink_to_fit(K, V, p_fm) flatmap_func(shrink_to_fit, K, V)(p_fm)

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

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

/// ```c
/// size_t flatmap_capacity(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns the allocated capacity of the flatmap.
#define flatmap_capacity(K, V, p_fm) ((size_t)((p_fm)->vec.capacity))

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

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

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

/// ```c
/// bool flatmap_insert(K, V, flatmap(K, V)* p_fm, K key, V value)
/// ```
/// Inserts `key` and `value` into the flatmap in sorted position. If `key` exists, updates its value.
#define flatmap_insert(K, V, p_fm, key, value) flatmap_func(insert, K, V)(p_fm, key, value)

/// ```c
/// bool flatmap_remove(K, V, flatmap(K, V)* p_fm, K key)
/// ```
/// Removes `key` and frees its resources. Returns `true` if found and removed, `false` otherwise.
#define flatmap_remove(K, V, p_fm, key) flatmap_func(remove, K, V)(p_fm, key)

/// ```c
/// bool flatmap_contains(K, V, flatmap(K, V)* p_fm, K key)
/// ```
/// Checks whether `key` exists in the flatmap.
#define flatmap_contains(K, V, p_fm, key) (flatmap_find(K, V, p_fm, key) != NULL)

/// ```c
/// V* flatmap_find(K, V, flatmap(K, V)* p_fm, K key)
/// ```
/// Searches for `key` via binary search. Returns a mutable pointer to the value, or `NULL` if not found.
#define flatmap_find(K, V, p_fm, key) flatmap_func(find, K, V)(p_fm, key)

/// ```c
/// V flatmap_get_or_default(K, V, flatmap(K, V)* p_fm, K key, V default_value)
/// ```
/// Returns the value mapped to `key`, or `default_value` if not found.
#define flatmap_get_or_default(K, V, p_fm, key, default_value) \
	flatmap_func(get_or_default, K, V)(p_fm, key, default_value)

/// ```c
/// K* flatmap_min_key(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns a deep copy of the smallest key in the flatmap. Caller must free the pointer.
#define flatmap_min_key(K, V, p_fm) flatmap_func(min_key, K, V)(p_fm)

/// ```c
/// const K* flatmap_min_key_ref(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns an O(1) direct read-only pointer to the smallest key in the flatmap.
#define flatmap_min_key_ref(K, V, p_fm) (((p_fm)->vec.size > 0) ? &((p_fm)->vec.p_data[0].key) : NULL)

/// ```c
/// K* flatmap_max_key(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns a deep copy of the largest key in the flatmap. Caller must free the pointer.
#define flatmap_max_key(K, V, p_fm) flatmap_func(max_key, K, V)(p_fm)

/// ```c
/// const K* flatmap_max_key_ref(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns an O(1) direct read-only pointer to the largest key in the flatmap.
#define flatmap_max_key_ref(K, V, p_fm) (((p_fm)->vec.size > 0) ? &((p_fm)->vec.p_data[(p_fm)->vec.size - 1].key) : NULL)

/// ```c
/// flatmap_iterator(K, V) flatmap_lower_bound(K, V, flatmap(K, V)* p_fm, K key)
/// ```
/// Returns an iterator pointing to the first element with key >= `key`.
#define flatmap_lower_bound(K, V, p_fm, key) flatmap_func(lower_bound, K, V)(p_fm, key)

/// ```c
/// flatmap_iterator(K, V) flatmap_upper_bound(K, V, flatmap(K, V)* p_fm, K key)
/// ```
/// Returns an iterator pointing to the first element with key > `key`.
#define flatmap_upper_bound(K, V, p_fm, key) flatmap_func(upper_bound, K, V)(p_fm, key)

/// ```c
/// flatmap_iterator(K, V) flatmap_begin(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns an iterator pointing to the first element in the flatmap.
#define flatmap_begin(K, V, p_fm) flatmap_func(begin, K, V)(p_fm)

/// ```c
/// flatmap_iterator(K, V) flatmap_end(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns an iterator pointing past the last element in the flatmap.
#define flatmap_end(K, V, p_fm) flatmap_func(end, K, V)(p_fm)

/// ```c
/// flatmap_iterator(K, V) flatmap_rbegin(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns a reverse iterator pointing to the last element in the flatmap.
#define flatmap_rbegin(K, V, p_fm) flatmap_func(rbegin, K, V)(p_fm)

/// ```c
/// flatmap_iterator(K, V) flatmap_rend(K, V, flatmap(K, V)* p_fm)
/// ```
/// Returns a reverse iterator pointing before the first element in the flatmap.
#define flatmap_rend(K, V, p_fm) flatmap_func(rend, K, V)(p_fm)

/// ```c
/// flatmap_iterator(K, V) flatmap_seek(K, V, flatmap(K, V)* p_fm, size_t index)
/// ```
/// Returns an O(1) iterator pointing to the element at `index`.
/// In a flatmap, this gives the k-th smallest element in O(1) time (Order Statistics).
#define flatmap_seek(K, V, p_fm, index) flatmap_func(seek, K, V)(p_fm, index)

/// ```c
/// flatmap_foreach(K, V, flatmap(K, V)* p_fm, IT_NAME)
/// ```
/// Iterates over all key-value pairs in ascending key order.
#define flatmap_foreach(K, V, p_fm, it) \
	for (flatmap_iterator(K, V) it = flatmap_begin(K, V, p_fm); flatmap_iterator_is_valid(K, V, &it); flatmap_iterator_next(K, V, &it))

/// ```c
/// flatmap_rforeach(K, V, flatmap(K, V)* p_fm, IT_NAME)
/// ```
/// Iterates over all key-value pairs in descending key order.
#define flatmap_rforeach(K, V, p_fm, it) \
	for (flatmap_iterator(K, V) it = flatmap_rbegin(K, V, p_fm); flatmap_iterator_is_valid(K, V, &it); flatmap_iterator_prev(K, V, &it))

/// Forward declares the `flatmap(K, V)` container type for prior references.
#define flatmap_fd(K, V) \
	typedef struct flatmap_pair_struct(K, V) flatmap_pair(K, V); \
	vector_fd(flatmap_pair(K, V)); \
	typedef struct flatmap_iterator_struct(K, V) flatmap_iterator(K, V); \
	typedef struct flatmap_struct(K, V) flatmap(K, V);

/// Declares flatmap struct and function prototypes in a header file.
#define flatmap_imp_h(K, V) \
	struct flatmap_pair_struct(K, V) { \
		K key; \
		V value; \
	}; \
	\
	vector_imp_h(flatmap_pair(K, V)); \
	flatmap_iterator_imp_h(K, V); \
	\
	struct flatmap_struct(K, V) { \
		flatmap_vector(K, V) vec; \
		int (*fp_compare_func)(K, K); \
		K (*fp_copy_func)(K); \
		void (*fp_free_func)(K); \
	}; \
	\
	void flatmap_func(init, K, V)(flatmap(K, V)* p_fm); \
	flatmap(K, V) flatmap_func(new, K, V)(void); \
	flatmap(K, V) flatmap_func(from_items, K, V)(const flatmap_pair(K, V)* p_items, size_t count); \
	bool flatmap_func(extend_items, K, V)(flatmap(K, V)* p_fm, const flatmap_pair(K, V)* p_items, size_t count); \
	void flatmap_func(free, K, V)(flatmap(K, V)* p_fm); \
	void flatmap_func(clear, K, V)(flatmap(K, V)* p_fm); \
	bool flatmap_func(reserve, K, V)(flatmap(K, V)* p_fm, size_t capacity); \
	bool flatmap_func(shrink_to_fit, K, V)(flatmap(K, V)* p_fm); \
	bool flatmap_func(insert, K, V)(flatmap(K, V)* p_fm, K key, V value); \
	bool flatmap_func(remove, K, V)(flatmap(K, V)* p_fm, K key); \
	V* flatmap_func(find, K, V)(flatmap(K, V)* p_fm, K key); \
	V flatmap_func(get_or_default, K, V)(flatmap(K, V)* p_fm, K key, V default_value); \
	K* flatmap_func(min_key, K, V)(flatmap(K, V)* p_fm); \
	K* flatmap_func(max_key, K, V)(flatmap(K, V)* p_fm); \
	flatmap_iterator(K, V) flatmap_func(lower_bound, K, V)(flatmap(K, V)* p_fm, K key); \
	flatmap_iterator(K, V) flatmap_func(upper_bound, K, V)(flatmap(K, V)* p_fm, K key); \
	flatmap_iterator(K, V) flatmap_func(begin, K, V)(flatmap(K, V)* p_fm); \
	flatmap_iterator(K, V) flatmap_func(end, K, V)(flatmap(K, V)* p_fm); \
	flatmap_iterator(K, V) flatmap_func(rbegin, K, V)(flatmap(K, V)* p_fm); \
	flatmap_iterator(K, V) flatmap_func(rend, K, V)(flatmap(K, V)* p_fm); \
	flatmap_iterator(K, V) flatmap_func(seek, K, V)(flatmap(K, V)* p_fm, size_t index);

/// Implements flatmap functions in a source file.
#define flatmap_imp_c(K, V) \
	vector_imp_c(flatmap_pair(K, V)); \
	flatmap_iterator_imp_c(K, V); \
	\
	void flatmap_func(init, K, V)(flatmap(K, V)* p_fm) { \
		if (!p_fm) return; \
		vector_func(init, flatmap_pair(K, V))(&p_fm->vec); \
		p_fm->fp_compare_func = cctl_get_default_compare_func(K); \
		p_fm->fp_copy_func = cctl_get_default_copy_func(K); \
		p_fm->fp_free_func = cctl_get_default_free_func(K); \
	} \
	\
	flatmap(K, V) flatmap_func(new, K, V)(void) { \
		flatmap(K, V) fm; \
		flatmap_func(init, K, V)(&fm); \
		return fm; \
	} \
	\
	flatmap(K, V) flatmap_func(from_items, K, V)(const flatmap_pair(K, V)* p_items, size_t count) { \
		flatmap(K, V) fm; \
		flatmap_func(init, K, V)(&fm); \
		if (p_items && count > 0) { \
			if (!flatmap_func(extend_items, K, V)(&fm, p_items, count)) { \
				flatmap_func(free, K, V)(&fm); \
			} \
		} \
		return fm; \
	} \
	\
	bool flatmap_func(extend_items, K, V)(flatmap(K, V)* p_fm, const flatmap_pair(K, V)* p_items, size_t count) { \
		if (!p_fm || !p_items || count == 0) return true; \
		for (size_t i = 0; i < count; i++) { \
			if (!flatmap_func(insert, K, V)(p_fm, p_items[i].key, p_items[i].value)) return false; \
		} \
		return true; \
	} \
	\
	void flatmap_func(clear, K, V)(flatmap(K, V)* p_fm) { \
		if (!p_fm) return; \
		if (p_fm->fp_free_func) { \
			for (size_t i = 0; i < p_fm->vec.size; i++) { \
				p_fm->fp_free_func(p_fm->vec.p_data[i].key); \
			} \
		} \
		vector_func(clear, flatmap_pair(K, V))(&p_fm->vec); \
	} \
	\
	void flatmap_func(free, K, V)(flatmap(K, V)* p_fm) { \
		if (!p_fm) return; \
		flatmap_func(clear, K, V)(p_fm); \
		vector_func(free, flatmap_pair(K, V))(&p_fm->vec); \
		flatmap_func(init, K, V)(p_fm); \
	} \
	\
	bool flatmap_func(reserve, K, V)(flatmap(K, V)* p_fm, size_t capacity) { \
		if (!p_fm) return false; \
		return vector_func(reserve, flatmap_pair(K, V))(&p_fm->vec, capacity); \
	} \
	\
	bool flatmap_func(shrink_to_fit, K, V)(flatmap(K, V)* p_fm) { \
		if (!p_fm) return false; \
		return vector_func(shrink_to_fit, flatmap_pair(K, V))(&p_fm->vec); \
	} \
	\
	static size_t cctl_join3(flatmap_internal_lower_bound, K, V)(flatmap(K, V)* p_fm, K key) { \
		size_t low = 0; \
		size_t high = p_fm->vec.size; \
		while (low < high) { \
			size_t mid = low + (high - low) / 2; \
			if (p_fm->fp_compare_func(p_fm->vec.p_data[mid].key, key) < 0) { \
				low = mid + 1; \
			} else { \
				high = mid; \
			} \
		} \
		return low; \
	} \
	\
	static size_t cctl_join3(flatmap_internal_upper_bound, K, V)(flatmap(K, V)* p_fm, K key) { \
		size_t low = 0; \
		size_t high = p_fm->vec.size; \
		while (low < high) { \
			size_t mid = low + (high - low) / 2; \
			if (p_fm->fp_compare_func(p_fm->vec.p_data[mid].key, key) <= 0) { \
				low = mid + 1; \
			} else { \
				high = mid; \
			} \
		} \
		return low; \
	} \
	\
	bool flatmap_func(insert, K, V)(flatmap(K, V)* p_fm, K key, V value) { \
		if (!p_fm) return false; \
		size_t index = cctl_join3(flatmap_internal_lower_bound, K, V)(p_fm, key); \
		if (index < p_fm->vec.size && p_fm->fp_compare_func(p_fm->vec.p_data[index].key, key) == 0) { \
			p_fm->vec.p_data[index].value = value; \
			return true; \
		} \
		K copied_key = p_fm->fp_copy_func ? p_fm->fp_copy_func(key) : key; \
		flatmap_pair(K, V) item = { copied_key, value }; \
		if (index == p_fm->vec.size) { \
			if (!vector_func(push_back, flatmap_pair(K, V))(&p_fm->vec, item)) { \
				if (p_fm->fp_free_func) p_fm->fp_free_func(copied_key); \
				return false; \
			} \
		} else { \
			if (!vector_func(resize, flatmap_pair(K, V))(&p_fm->vec, p_fm->vec.size + 1)) { \
				if (p_fm->fp_free_func) p_fm->fp_free_func(copied_key); \
				return false; \
			} \
			memmove( \
				p_fm->vec.p_data + index + 1, \
				p_fm->vec.p_data + index, \
				(p_fm->vec.size - 1 - index) * sizeof(flatmap_pair(K, V)) \
			); \
			p_fm->vec.p_data[index] = item; \
		} \
		return true; \
	} \
	\
	bool flatmap_func(remove, K, V)(flatmap(K, V)* p_fm, K key) { \
		if (!p_fm || p_fm->vec.size == 0) return false; \
		size_t index = cctl_join3(flatmap_internal_lower_bound, K, V)(p_fm, key); \
		if (index >= p_fm->vec.size || p_fm->fp_compare_func(p_fm->vec.p_data[index].key, key) != 0) { \
			return false; \
		} \
		if (p_fm->fp_free_func) { \
			p_fm->fp_free_func(p_fm->vec.p_data[index].key); \
		} \
		if (index < p_fm->vec.size - 1) { \
			memmove( \
				p_fm->vec.p_data + index, \
				p_fm->vec.p_data + index + 1, \
				(p_fm->vec.size - 1 - index) * sizeof(flatmap_pair(K, V)) \
			); \
		} \
		p_fm->vec.size--; \
		return true; \
	} \
	\
	V* flatmap_func(find, K, V)(flatmap(K, V)* p_fm, K key) { \
		if (!p_fm || p_fm->vec.size == 0) return NULL; \
		size_t index = cctl_join3(flatmap_internal_lower_bound, K, V)(p_fm, key); \
		if (index < p_fm->vec.size && p_fm->fp_compare_func(p_fm->vec.p_data[index].key, key) == 0) { \
			return &p_fm->vec.p_data[index].value; \
		} \
		return NULL; \
	} \
	\
	V flatmap_func(get_or_default, K, V)(flatmap(K, V)* p_fm, K key, V default_value) { \
		V* p_val = flatmap_func(find, K, V)(p_fm, key); \
		return p_val ? *p_val : default_value; \
	} \
	\
	K* flatmap_func(min_key, K, V)(flatmap(K, V)* p_fm) { \
		if (!p_fm || p_fm->vec.size == 0) return NULL; \
		K* p_key = (K*) malloc(sizeof(K)); \
		if (!p_key) return NULL; \
		*p_key = p_fm->fp_copy_func ? p_fm->fp_copy_func(p_fm->vec.p_data[0].key) : p_fm->vec.p_data[0].key; \
		return p_key; \
	} \
	\
	K* flatmap_func(max_key, K, V)(flatmap(K, V)* p_fm) { \
		if (!p_fm || p_fm->vec.size == 0) return NULL; \
		K* p_key = (K*) malloc(sizeof(K)); \
		if (!p_key) return NULL; \
		*p_key = p_fm->fp_copy_func ? p_fm->fp_copy_func(p_fm->vec.p_data[p_fm->vec.size - 1].key) : p_fm->vec.p_data[p_fm->vec.size - 1].key; \
		return p_key; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(lower_bound, K, V)(flatmap(K, V)* p_fm, K key) { \
		flatmap_iterator(K, V) it = { p_fm, 0 }; \
		if (!p_fm) return it; \
		it.index = cctl_join3(flatmap_internal_lower_bound, K, V)(p_fm, key); \
		return it; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(upper_bound, K, V)(flatmap(K, V)* p_fm, K key) { \
		flatmap_iterator(K, V) it = { p_fm, 0 }; \
		if (!p_fm) return it; \
		it.index = cctl_join3(flatmap_internal_upper_bound, K, V)(p_fm, key); \
		return it; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(begin, K, V)(flatmap(K, V)* p_fm) { \
		flatmap_iterator(K, V) it = { p_fm, 0 }; \
		return it; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(end, K, V)(flatmap(K, V)* p_fm) { \
		flatmap_iterator(K, V) it = { p_fm, p_fm ? p_fm->vec.size : 0 }; \
		return it; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(rbegin, K, V)(flatmap(K, V)* p_fm) { \
		flatmap_iterator(K, V) it = { p_fm, (p_fm && p_fm->vec.size > 0) ? (p_fm->vec.size - 1) : (size_t)-1 }; \
		return it; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(rend, K, V)(flatmap(K, V)* p_fm) { \
		flatmap_iterator(K, V) it = { p_fm, (size_t)-1 }; \
		return it; \
	} \
	\
	flatmap_iterator(K, V) flatmap_func(seek, K, V)(flatmap(K, V)* p_fm, size_t index) { \
		flatmap_iterator(K, V) it = { p_fm, index }; \
		return it; \
	}

#endif