<commit_before>#ifndef RDESTL_RADIX_SORTER_H
#define RDESTL_RADIX_SORTER_H

#include "rdestl/vector.h"

namespace rde
{
template<typename T>
class radix_sorter
{
public:
	static const size_t kHistogramSize	= 256;

	enum data_type
	{
		data_unsigned = false,
		data_signed,
	};

	template<data_type TDataType, typename TFunc>
	void sort(T* src, int num, const TFunc& func)
	{
		if (num == 0)
			return;
		if (num > m_dst.size())
			resize(num);

		uint32_t histogram[kHistogramSize * 4];
		Sys::MemSet(histogram, 0, sizeof(histogram));

		uint32_t* h1 = &histogram[0] + kHistogramSize;
		uint32_t* h2 = h1 + kHistogramSize;
		uint32_t* h3 = h2 + kHistogramSize;

		bool alreadySorted(true);
		uint32_t prevValue = func(src[0]);

		int k(0);
		for (int i = 0; i < num; ++i)
		{
			k = i;
			const uint32_t x = func(src[i]);
			if (alreadySorted && x < prevValue)
			{
				alreadySorted = false;
				break;
			}
			const uint8_t* px = (const uint8_t*)&x;

			++histogram[*px];
			++h1[px[1]];
			++h2[px[2]];
			++h3[px[3]];

			prevValue = x;
		}
		if (alreadySorted)
			return;

		for (; k < num; ++k)
		{
			const uint32_t x = func(src[k]);
			const uint8_t* px = (const uint8_t*)&x;

			++histogram[*px];
			++h1[px[1]];
			++h2[px[2]];
			++h3[px[3]];
		}

		// 3rd byte == 0
		const bool canBreakAfter16Bits = (h2[0] == (uint32_t)num && h3[0] == (uint32_t)num);
		(void)canBreakAfter16Bits;

		if (TDataType == data_signed)
			calculate_offsets_signed(histogram);
		else
			calculate_offsets(histogram);

		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = func(src[i]) & 0xFF;
			m_dst[histogram[pos]++] = src[i];
		}
		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = (func(m_dst[i]) >> 8) & 0xFF;
			src[h1[pos]++] = m_dst[i];
		}
		if (TDataType == data_unsigned && canBreakAfter16Bits)
			return;
		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = (func(src[i]) >> 16) & 0xFF;
			m_dst[h2[pos]++] = src[i];
		}
		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = (func(m_dst[i]) >> 24) & 0xFF;
			src[h3[pos]++] = m_dst[i];
		}
	}		

private:
	void resize(int num)
	{
		m_dst.resize(num);
	}
	void calculate_offsets(uint32_t* histogram)
	{<commit_msg>Added sort() method that uses external temporary buffer for intermediate data<commit_after>#ifndef RDESTL_RADIX_SORTER_H
#define RDESTL_RADIX_SORTER_H

#include "rdestl/vector.h"

namespace rde
{
template<typename T>
class radix_sorter
{
public:
	static const size_t kHistogramSize	= 256;

	enum data_type
	{
		data_unsigned = false,
		data_signed,
	};

	// User-provided temporary buffer for intermediate operations.
	// It has to be at least 'num' elements big.
	template<data_type TDataType, typename TFunc>
	void sort(T* src, int num, const TFunc& func, T* help_buffer)
	{
		if (num == 0)
			return;

		uint32_t histogram[kHistogramSize * 4];
		Sys::MemSet(histogram, 0, sizeof(histogram));

		uint32_t* h1 = &histogram[0] + kHistogramSize;
		uint32_t* h2 = h1 + kHistogramSize;
		uint32_t* h3 = h2 + kHistogramSize;

		bool alreadySorted(true);
		uint32_t prevValue = func(src[0]);

		int k(0);
		for (int i = 0; i < num; ++i)
		{
			k = i;
			const uint32_t x = func(src[i]);
			if (alreadySorted && x < prevValue)
			{
				alreadySorted = false;
				break;
			}
			const uint8_t* px = (const uint8_t*)&x;

			++histogram[*px];
			++h1[px[1]];
			++h2[px[2]];
			++h3[px[3]];

			prevValue = x;
		}
		if (alreadySorted)
			return;

		for (; k < num; ++k)
		{
			const uint32_t x = func(src[k]);
			const uint8_t* px = (const uint8_t*)&x;

			++histogram[*px];
			++h1[px[1]];
			++h2[px[2]];
			++h3[px[3]];
		}

		// 3rd byte == 0
		const bool canBreakAfter16Bits = (h2[0] == (uint32_t)num && h3[0] == (uint32_t)num);
		(void)canBreakAfter16Bits;

		if (TDataType == data_signed)
			calculate_offsets_signed(histogram);
		else
			calculate_offsets(histogram);

		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = func(src[i]) & 0xFF;
			help_buffer[histogram[pos]++] = src[i];
		}
		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = (func(m_dst[i]) >> 8) & 0xFF;
			src[h1[pos]++] = help_buffer[i];
		}
		if (TDataType == data_unsigned && canBreakAfter16Bits)
			return;
		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = (func(src[i]) >> 16) & 0xFF;
			help_buffer[h2[pos]++] = src[i];
		}
		for (int i = 0; i < num; ++i)
		{
			const uint32_t pos = (func(m_dst[i]) >> 24) & 0xFF;
			src[h3[pos]++] = help_buffer[i];
		}
	}

	// Version that uses internal buffer.
	template<data_type TDataType, typename TFunc>
	void sort(T* src, int num, const TFunc& func)
	{
		if (num > m_dst.size())
			resize(num);
		sort<TDataType, TFunc>(src, num, func, m_dst.begin());
	}		

private:
	void resize(int num)
	{
		m_dst.resize(num);
	}
	void calculate_offsets(uint32_t* histogram)
	{
{'fraction_non_alphanumeric': 0.16614550760892224, 'fraction_numerical': 0.03627267041901188, 'mean_word_length': 3.450834879406308, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 23, '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': '7507176', 'n_tokens_mistral': 2392, 'n_tokens_neox': 2045, 'n_words': 465}