#include "btree.h"

void BTreeBase::traverse(TraverseCallback* callback, void* const arg) const
{
	const uint16_t num_nodes = data_at<uint16_t>(table_data_, sizeof(uint32_t));
	const void* node_data = advance_pointer(table_data_, sizeof(uint32_t) + sizeof(num_nodes));
	for (uint32_t i = 0; i < num_nodes; ++i) {
		const uint32_t num_keys = extract_twelve_bits(node_data, 0) & 0x7FF;
		const uint32_t next_node_data_offset = extract_twelve_bits(node_data, num_keys + 1);
		for (uint32_t j = 0; j < num_keys; ++j) {
			const uint32_t node_offset = extract_twelve_bits(node_data, j + 1);
			const void* node = advance_pointer(node_data, node_offset);
			if (callback) {
				if ((*callback)(node, arg) < 0)
					return;
			}
		}
		node_data = advance_pointer(node_data, next_node_data_offset);
	}
}

const void* BTreeBase::search(const uint32_t index) const
{
	const uint32_t num_child_nodes = data_at<uint8_t>(table_data_, 0);
	uint32_t node_data_offset = data_at<uint32_t>(table_data_, 0) & 0xFFFFFF;
	const void* node_data = advance_pointer(table_data_, node_data_offset);
	uint32_t key_index_start = 0;
	bool found = false;
	for (uint32_t i = num_child_nodes; i != 0 && !found; --i) {
		const void* node = nullptr;
		const uint32_t num_keys = extract_twelve_bits(node_data, 0) & 0x7FF;
		for (uint32_t j = 0; j < num_keys; ++j) {
			const uint32_t node_offset = extract_twelve_bits(node_data, j + 1);
			node = advance_pointer(node_data, node_offset);
			const uint32_t next_key_index = extract_value_and_advance(&node);
			if (index < next_key_index) {
				found = true;
				break;
			}
			key_index_start = next_key_index;
		}
		if (!node)
			break;
		node = skip_node_data(node);
		node_data_offset = extract_value_and_advance(&node);
		node_data = advance_pointer(table_data_, node_data_offset);
	}
	if (true /* found */) { // FIXME: check this
		const uint32_t num_keys = extract_twelve_bits(node_data, 0) & 0x7FF;
		const uint32_t node_offset = extract_twelve_bits(node_data, (index - key_index_start) + 1);
		const void* const node = advance_pointer(node_data, node_offset);
		return node;
	}
	return nullptr;
}

const void* BTreeBase::search(const void* const key, uint32_t* const index) const
{
	uint32_t lower_bound = 0;
	uint32_t upper_bound = 0;
	uint32_t max_key_index = 0;

	const uint32_t num_child_nodes = data_at<uint8_t>(table_data_, 0);
	uint32_t node_data_offset = data_at<uint32_t>(table_data_, 0) & 0xFFFFFF;
	const void* node_data = advance_pointer(table_data_, node_data_offset);
	for (uint32_t i = num_child_nodes; i != 0; --i) {
		const void* node = search_with_cmp(node_data, key, less_than_op_, &lower_bound, &upper_bound, true);
		if (!node) {
			if (lower_bound != upper_bound) {
				const uint32_t node_offset = extract_twelve_bits(node_data, lower_bound + 1);
				node = advance_pointer(node_data, node_offset);
			}
			if (!node)
				return nullptr;
		}
		max_key_index = extract_value_and_advance(&node);
		node = skip_node_data(node);
		node_data_offset = extract_value_and_advance(&node);
		node_data = advance_pointer(table_data_, node_data_offset);
	}

	const void* const node = search_with_cmp(node_data, key, equal_op_, &lower_bound, &upper_bound, false);
	if (index) {
		if (!num_child_nodes)
			upper_bound = 0;
		*index = node ? (max_key_index - upper_bound + lower_bound) : kINVALID_INDEX;
	}

	return node;
}

//    С помощью бинарного поиска по таблице смещений находим то, какое указывает на наш ключ
// и возвращаем его индекс.
//    Индексы каждого идут последовательно, начиная с 0, high указывает на индекс, находящийся за
// последним, т.е.:
//      high-low=num_indices или high=num_indices, т.к. low=0 или high=last_index+1
//    Данные последующего узла (а именно - таблица смещений и сами ключи) идут сразу за предыдущим
// узлом, кроме того, индексы в новом узле начинаются со значения high (или last_index+1) в предыдущем.
//    max_key_index для последующего узла  высчитывается по формуле: max_key_index=prev_high+(high-low),
//  т.е. как сумма значения индекса, следующего за последним элементом прошлого узла, и разницы
//  между таким же индексом и стартовым нового узла.
//    Допустим, что имеются два узла с индексами 0-9 и 10-15 соответственно.
//    Для первого узла получим значения: low=0, high=10, для второго узла: low=0, high=7.
//    Таким образом, max_key_index второго узла будет равен: max_key_index=10+(7-0)=17.
//    Каждое смещение занимает 12 бит, после последнего смещения на ключ идет смещение к следующему
// узлу. Все смещения задаются относительного начало данных блока, который в данный момент обрабатываем.
//    Первое смещение в шапке файла указывает на начало данных корневого узла, в шапке которого
// записано количество дочерних узлов и смещение к данным самого корневого узла. !!![Далее расположены
// данные дочерних узлов, в начале которых опять идет число дочерних узлов и смещение к данным этого
// узла, после чего опять данные дочерних узлов и т.д.]!!!
const void* BTreeBase::search_with_cmp(const void* const node_data, const void* const key, KeyComparsionOp* const op, uint32_t* const lower_bound, uint32_t* const upper_bound, const bool is_internal) const
{
	uint32_t low = 0;
	uint32_t high = extract_twelve_bits(node_data, 0) & 0x7FF;

 	*upper_bound = high;
	if (high != 0) {
		do {
			const uint32_t mid = low + (high - low) / 2;
			const uint32_t node_offset = extract_twelve_bits(node_data, mid + 1);
			const void* const node = advance_pointer(node_data, node_offset);
			int cmp = (*op)(key, node);
			if (!cmp) {
				*lower_bound = mid;
				return node;
			} else if (cmp < 0) {
				high = mid;
			} else if (cmp > 0) {
				low = mid + 1;
			}
		} while (low < high);
	}
	*lower_bound = low;

	return nullptr;
}

uint32_t extract_value_and_advance(const void** const ptr)
{
	const uint8_t* p = static_cast<const uint8_t*>(*ptr);
	uint32_t value = *p++;
	if ((value & 0x80) != 0) {
		uint32_t mask = 0x80;
		do {
			value = ((value - mask) << 8) + *p++;
			mask = mask << 7;
		} while ((value & mask) != 0);
	}
	*ptr = p;
	return value;
}
