<commit_before>#ifndef TURBO_CONTAINER_EMPLACING_SKIPLIST_HXX
#define TURBO_CONTAINER_EMPLACING_SKIPLIST_HXX

#include <turbo/container/emplacing_skiplist.hpp>
#include <cmath>
#include <chrono>
#include <random>
#include <turbo/container/emplacing_list.hxx>
#include <turbo/toolset/extension.hpp>

namespace turbo {
namespace container {

template <class k, class v, class a, class c>
emplacing_skiplist<k, v, a, c>::emplacing_skiplist(
	typed_allocator_type& allocator)
    :
	emplacing_skiplist(allocator, 2U)
{ }

template <class k, class v, class a, class c>
emplacing_skiplist<k, v, a, c>::emplacing_skiplist(
	typed_allocator_type& allocator,
	std::uint16_t height_log_base)
    :
	allocator_(allocator),
	height_log_base_(height_log_base),
	store_(allocator_),
	tower_(allocator_)
{ }

template <class k, class v, class a, class c>
typename emplacing_skiplist<k, v, a, c>::iterator emplacing_skiplist<k, v, a, c>::find(
	const key_type& key)
{
    iterator target;
    std::tie(target, std::ignore) = search(key);
    if (target != store_.end() && compare_func()(target->key, key) && compare_func()(key, target->key))
    {
	return target;
    }
    else
    {
	return store_.end();
    }
}

template <class k, class v, class a, class c>
template <class key_arg_t, class... value_args_t>
std::tuple<typename emplacing_skiplist<k, v, a, c>::iterator, bool> emplacing_skiplist<k, v, a, c>::emplace(
	const key_arg_t& key_arg,
	value_args_t&&... value_args)
{
    return emplace(chose_height(), std::forward<decltype(key_arg)>(key_arg), std::forward<value_args_t>(value_args)...);
}

template <class k, class v, class a, class c>
template <class key_arg_t, class... value_args_t>
std::tuple<typename emplacing_skiplist<k, v, a, c>::iterator, bool> emplacing_skiplist<k, v, a, c>::emplace(
	std::int64_t chosen_height,
	const key_arg_t& key_arg,
	value_args_t&&... value_args)
{
    if (0 <= chosen_height)
    {
	grow_tower(chosen_height);
    }
    const key_type key(key_arg);
    const typename floor::iterator empty;
    std::vector<trace> tower_trace(trace_tower(key, trace_depth::all_matches));
    typename store::iterator nearest_record;
    typename store::iterator next_record;
    if (tower_trace.size() == 0U || tower_trace.back().nearest == empty)
    {
	// tower is empty or all keys in the tower are greater than the requested key
	std::tie(nearest_record, next_record) = search_store(key, store_.begin());
    }
    else
    {
	nearest_record = tower_trace.back().nearest->bottom.lock();
	std::tie(nearest_record, next_record) = search_store(key, nearest_record);
    }
    if (nearest_record != store_.end() && compare_func()(nearest_record->key, key) && compare_func()(key, nearest_record->key))
    {
	// record already exists
	return std::make_tuple(nearest_record, false);
    }
    else
    {
	iterator target = store_.emplace(next_record, key_arg, std::forward<value_args_t>(value_args)...);
	if (chosen_height < 0)
	{
	    return std::make_tuple(target, true);
	}
	std::weak_ptr<typename store::iterator::node_type> bottom_ptr(target.share());
	std::weak_ptr<typename floor::iterator::node_type> down_ptr;
	for (auto iter = tower_trace.rbegin(); iter != tower_trace.rend() && iter->id <= chosen_height; ++iter)
	{
	    if (iter->nearest != empty && compare_func()(iter->nearest->key, key) && compare_func()(key, iter->nearest->key))
	    {
		// room with requested key already exists
		down_ptr = iter->nearest.share();
	    }
	    else
	    {
		down_ptr = iter->floor->emplace(iter->next, key, bottom_ptr, down_ptr).share();
	    }
	}
	return std::make_tuple(target, true);
    }
}

template <class k, class v, class a, class c>
typename emplacing_skiplist<k, v, a, c>::iterator emplacing_skiplist<k, v, a, c>::erase(
	const key_type& key)
{
    const typename floor::iterator empty;
    std::vector<trace> tower_trace(trace_tower(key, trace_depth::all_matches));
    typename store::iterator nearest_record;
    if (0U < tower_trace.size() && tower_trace.rbegin().nearest != empty && !tower_trace.rbegin()->bottom.expired())
    {
	nearest_record = tower_trace.rbegin()->bottom.lock();
    }
    else
    {
	// tower is empty or all keys in the tower are greater than the requested key
	nearest_record = store_.begin();
    }
    // erase the rooms in the tower associated with the key
    for (auto iter = tower_trace.begin(); iter != tower_trace.end(); ++iter)
    {
	if (iter->nearest != empty && compare_func()(iter->nearest->key, key) && compare_func()(key, iter->nearest->key))
	{
	    iter->floor.erase(iter->nearest);
	}
    }
    std::tie(nearest_record, std::ignore) = search_store(key, nearest_record);
    if (nearest_record != store_.end() && compare_func()(nearest_record->key, key) && compare_func()(key, nearest_record->key))
    {
	return store_.erase(nearest_record);
    }
    else
    {
	return store_.end();
    }
}

template <class key_t, class value_t, class allocator_t, class compare_f>
typename emplacing_skiplist<key_t, value_t, allocator_t, compare_f>::store_region emplacing_skiplist<key_t, value_t, allocator_t, compare_f>::search(
	const key_type& key)
{
    const typename floor::iterator empty;
    std::vector<trace> tower_trace(trace_tower(key, trace_depth::first_match));
    // TODO: in concurrent skiplist bottom might be expired
    if (tower_trace.size() == 0U || tower_trace.back().nearest == empty)<commit_msg>* fixed some bugs in the utilisation of the trace vector iterator * added an extra check to make sure the floor in the trace is valid before using it<commit_after>#ifndef TURBO_CONTAINER_EMPLACING_SKIPLIST_HXX
#define TURBO_CONTAINER_EMPLACING_SKIPLIST_HXX

#include <turbo/container/emplacing_skiplist.hpp>
#include <cmath>
#include <chrono>
#include <random>
#include <turbo/container/emplacing_list.hxx>
#include <turbo/toolset/extension.hpp>

namespace turbo {
namespace container {

template <class k, class v, class a, class c>
emplacing_skiplist<k, v, a, c>::emplacing_skiplist(
	typed_allocator_type& allocator)
    :
	emplacing_skiplist(allocator, 2U)
{ }

template <class k, class v, class a, class c>
emplacing_skiplist<k, v, a, c>::emplacing_skiplist(
	typed_allocator_type& allocator,
	std::uint16_t height_log_base)
    :
	allocator_(allocator),
	height_log_base_(height_log_base),
	store_(allocator_),
	tower_(allocator_)
{ }

template <class k, class v, class a, class c>
typename emplacing_skiplist<k, v, a, c>::iterator emplacing_skiplist<k, v, a, c>::find(
	const key_type& key)
{
    iterator target;
    std::tie(target, std::ignore) = search(key);
    if (target != store_.end() && compare_func()(target->key, key) && compare_func()(key, target->key))
    {
	return target;
    }
    else
    {
	return store_.end();
    }
}

template <class k, class v, class a, class c>
template <class key_arg_t, class... value_args_t>
std::tuple<typename emplacing_skiplist<k, v, a, c>::iterator, bool> emplacing_skiplist<k, v, a, c>::emplace(
	const key_arg_t& key_arg,
	value_args_t&&... value_args)
{
    return emplace(chose_height(), std::forward<decltype(key_arg)>(key_arg), std::forward<value_args_t>(value_args)...);
}

template <class k, class v, class a, class c>
template <class key_arg_t, class... value_args_t>
std::tuple<typename emplacing_skiplist<k, v, a, c>::iterator, bool> emplacing_skiplist<k, v, a, c>::emplace(
	std::int64_t chosen_height,
	const key_arg_t& key_arg,
	value_args_t&&... value_args)
{
    if (0 <= chosen_height)
    {
	grow_tower(chosen_height);
    }
    const key_type key(key_arg);
    const typename floor::iterator empty;
    std::vector<trace> tower_trace(trace_tower(key, trace_depth::all_matches));
    typename store::iterator nearest_record;
    typename store::iterator next_record;
    if (tower_trace.size() == 0U || tower_trace.back().nearest == empty)
    {
	// tower is empty or all keys in the tower are greater than the requested key
	std::tie(nearest_record, next_record) = search_store(key, store_.begin());
    }
    else
    {
	nearest_record = tower_trace.back().nearest->bottom.lock();
	std::tie(nearest_record, next_record) = search_store(key, nearest_record);
    }
    if (nearest_record != store_.end() && compare_func()(nearest_record->key, key) && compare_func()(key, nearest_record->key))
    {
	// record already exists
	return std::make_tuple(nearest_record, false);
    }
    else
    {
	iterator target = store_.emplace(next_record, key_arg, std::forward<value_args_t>(value_args)...);
	if (chosen_height < 0)
	{
	    return std::make_tuple(target, true);
	}
	std::weak_ptr<typename store::iterator::node_type> bottom_ptr(target.share());
	std::weak_ptr<typename floor::iterator::node_type> down_ptr;
	for (auto iter = tower_trace.rbegin(); iter != tower_trace.rend() && iter->id <= chosen_height; ++iter)
	{
	    if (iter->nearest != empty && compare_func()(iter->nearest->key, key) && compare_func()(key, iter->nearest->key))
	    {
		// room with requested key already exists
		down_ptr = iter->nearest.share();
	    }
	    else
	    {
		down_ptr = iter->floor->emplace(iter->next, key, bottom_ptr, down_ptr).share();
	    }
	}
	return std::make_tuple(target, true);
    }
}

template <class k, class v, class a, class c>
typename emplacing_skiplist<k, v, a, c>::iterator emplacing_skiplist<k, v, a, c>::erase(
	const key_type& key)
{
    const typename floor::iterator empty;
    std::vector<trace> tower_trace(trace_tower(key, trace_depth::all_matches));
    typename store::iterator nearest_record;
    if (0U < tower_trace.size() && tower_trace.rbegin()->nearest != empty && !tower_trace.rbegin()->nearest->bottom.expired())
    {
	nearest_record = tower_trace.rbegin()->nearest->bottom.lock();
    }
    else
    {
	// tower is empty or all keys in the tower are greater than the requested key
	nearest_record = store_.begin();
    }
    // erase the rooms in the tower associated with the key
    for (auto iter = tower_trace.begin(); iter != tower_trace.end(); ++iter)
    {
	if (iter->nearest != empty
		&& iter->floor != tower_.rend()
		&& compare_func()(iter->nearest->key, key)
		&& compare_func()(key, iter->nearest->key))
	{
	    iter->floor->erase(iter->nearest);
	}
    }
    std::tie(nearest_record, std::ignore) = search_store(key, nearest_record);
    if (nearest_record != store_.end() && compare_func()(nearest_record->key, key) && compare_func()(key, nearest_record->key))
    {
	return store_.erase(nearest_record);
    }
    else
    {
	return store_.end();
    }
}

template <class key_t, class value_t, class allocator_t, class compare_f>
typename emplacing_skiplist<key_t, value_t, allocator_t, compare_f>::store_region emplacing_skiplist<key_t, value_t, allocator_t, compare_f>::search(
	const key_type& key)
{
    const typename floor::iterator empty;
    std::vector<trace> tower_trace(trace_tower(key, trace_depth::first_match));
    // TODO: in concurrent skiplist bottom might be expired
    if (tower_trace.size() == 0U || tower_trace.back().nearest == empty)
{'fraction_non_alphanumeric': 0.14333941605839415, 'fraction_numerical': 0.0018248175182481751, 'mean_word_length': 4.762881177707676, 'pattern_counts': {'":': 0, '<': 85, '<?xml version=': 0, '>': 134, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3936144', 'n_tokens_mistral': 3921, 'n_tokens_neox': 3822, 'n_words': 857}