<commit_before>/*
 gcc -o WikiSort.x WikiSort.c -O3
 ./WikiSort.x
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdarg.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <time.h>
#include <limits.h>


/* various #defines for the C code */
/* (apologies for throwing everything into one file; the original code used a framework which had to be partially reimplemented) */
#ifndef true
	#define true 1
	#define false 0
	typedef uint8_t bool;
#endif

#define Var(name, value)				__typeof__(value) name = value
#define Allocate(type, count)				(type *)malloc((count) * sizeof(type))
#define Seconds()					(clock() * 1.0/CLOCKS_PER_SEC)

long Min(long a, long b) {
	if (a < b) return a;
	return b;
}

long Max(long a, long b) {
	if (a > b) return a;
	return b;
}


/* structure to test stable sorting (index will contain its original index in the array, to make sure it doesn't switch places with other items) */
typedef struct {
	int value;
	int index;
} Test;

bool TestCompare(Test item1, Test item2) { return (item1.value < item2.value); }

typedef bool (*Comparison)(Test, Test);




/* structure to represent ranges within the array */
typedef struct {
	long start;
	long length;
} Range;

Range MakeRange(long start, long length) {
	Range range;
	range.start = start;
	range.length = length;
	return range;
}

Range RangeBetween(long start, long end) {
	return MakeRange(start, end - start);
}

Range ZeroRange() {
	return MakeRange(0, 0);
}




/* toolbox functions used by the sorter */

/* swap value1 and value2 */
#define Swap(value1, value2) { \
	Var(a, &(value1)); \
	Var(b, &(value2)); \
	\
	Var(c, *a); \
	*a = *b; \
	*b = c; \
}

/* if your language does not support bitwise operations for some reason, you can use (floor(value/2) * 2 == value) */
bool IsEven(long value) { return ((value & 0x1) == 0x0); }

/* 63 -> 32, 64 -> 64, etc. */
/* apparently this comes from Hacker's Delight? */
long FloorPowerOfTwo (long x) {
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
#if __LP64__
	x = x | (x >> 32);
#endif
	return x - (x >> 1);
}

/* find the index of the first value within the range that is equal to array[index] */
long BinaryFirst(Test array[], long index, Range range, Comparison compare) {
	long start = range.start, end = range.start + range.length - 1;
	while (start < end) {
		long mid = start + (end - start)/2;
		if (compare(array[mid], array[index]))
			start = mid + 1;
		else
			end = mid;
	}
	if (start == range.start + range.length - 1 && compare(array[start], array[index])) start++;
	return start;
}

/* find the index of the last value within the range that is equal to array[index], plus 1 */
long BinaryLast(Test array[], long index, Range range, Comparison compare) {
	long start = range.start, end = range.start + range.length - 1;
	while (start < end) {
		long mid = start + (end - start)/2;
		if (!compare(array[index], array[mid]))
			start = mid + 1;
		else
			end = mid;
	}
	if (start == range.start + range.length - 1 && !compare(array[index], array[start])) start++;
	return start;
}

/* n^2 sorting algorithm used to sort tiny chunks of the full array */
void InsertionSort(Test array[], Range range, Comparison compare) {
	long i, j;
	for (i = range.start + 1; i < range.start + range.length; i++) {
		Test temp = array[i];
		for (j = i; j > range.start && compare(temp, array[j - 1]); j--)
			array[j] = array[j - 1];
		array[j] = temp;
	}
}

/* reverse a range within the array */
void Reverse(Test array[], Range range) {
	long index;
	for (index = range.length/2 - 1; index >= 0; index--)
		Swap(array[range.start + index], array[range.start + range.length - index - 1]);
}

/* swap a series of values in the array */
void BlockSwap(Test array[], long start1, long start2, long block_size) {
	long index;
	for (index = 0; index < block_size; index++) Swap(array[start1 + index], array[start2 + index]);
}

/* rotate the values in an array ([0 1 2 3] becomes [3 0 1 2] if we rotate by +1) */
void Rotate(Test array[], long amount, Range range, Test cache[], const long cache_size) {
	Range range1, range2;
	
	if (range.length == 0) return;
	
	if (amount >= 0) amount = range.start + (amount % range.length);
	else amount = range.start + range.length - ((-amount) % range.length);
	
	range1 = RangeBetween(range.start, amount);
	range2 = RangeBetween(amount, range.start + range.length);
	
	/* if the smaller of the two ranges fits into the cache, it's *slightly* faster copying it there and shifting the elements over */
	if (range1.length <= range2.length) {
		if (range1.length <= cache_size) {
			memcpy(&cache[0], &array[range1.start], range1.length * sizeof(array[0]));
			memmove(&array[range1.start], &array[range2.start], range2.length * sizeof(array[0]));
			memcpy(&array[range1.start + range2.length], &cache[0], range1.length * sizeof(array[0]));
			return;
		}
	} else {
		if (range2.length <= cache_size) {
			memcpy(&cache[0], &array[range2.start], range2.length * sizeof(array[0]));
			memmove(&array[range2.start + range2.length - range1.length], &array[range1.start], range1.length * sizeof(array[0]));
			memcpy(&array[range1.start], &cache[0], range2.length * sizeof(array[0]));
			return;
		}<commit_msg>Fixed comment about how Rotate() works<commit_after>/*
 gcc -o WikiSort.x WikiSort.c -O3
 ./WikiSort.x
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdarg.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <time.h>
#include <limits.h>


/* various #defines for the C code */
/* (apologies for throwing everything into one file; the original code used a framework which had to be partially reimplemented) */
#ifndef true
	#define true 1
	#define false 0
	typedef uint8_t bool;
#endif

#define Var(name, value)				__typeof__(value) name = value
#define Allocate(type, count)				(type *)malloc((count) * sizeof(type))
#define Seconds()					(clock() * 1.0/CLOCKS_PER_SEC)

long Min(long a, long b) {
	if (a < b) return a;
	return b;
}

long Max(long a, long b) {
	if (a > b) return a;
	return b;
}


/* structure to test stable sorting (index will contain its original index in the array, to make sure it doesn't switch places with other items) */
typedef struct {
	int value;
	int index;
} Test;

bool TestCompare(Test item1, Test item2) { return (item1.value < item2.value); }

typedef bool (*Comparison)(Test, Test);




/* structure to represent ranges within the array */
typedef struct {
	long start;
	long length;
} Range;

Range MakeRange(long start, long length) {
	Range range;
	range.start = start;
	range.length = length;
	return range;
}

Range RangeBetween(long start, long end) {
	return MakeRange(start, end - start);
}

Range ZeroRange() {
	return MakeRange(0, 0);
}




/* toolbox functions used by the sorter */

/* swap value1 and value2 */
#define Swap(value1, value2) { \
	Var(a, &(value1)); \
	Var(b, &(value2)); \
	\
	Var(c, *a); \
	*a = *b; \
	*b = c; \
}

/* if your language does not support bitwise operations for some reason, you can use (floor(value/2) * 2 == value) */
bool IsEven(long value) { return ((value & 0x1) == 0x0); }

/* 63 -> 32, 64 -> 64, etc. */
/* apparently this comes from Hacker's Delight? */
long FloorPowerOfTwo (long x) {
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
#if __LP64__
	x = x | (x >> 32);
#endif
	return x - (x >> 1);
}

/* find the index of the first value within the range that is equal to array[index] */
long BinaryFirst(Test array[], long index, Range range, Comparison compare) {
	long start = range.start, end = range.start + range.length - 1;
	while (start < end) {
		long mid = start + (end - start)/2;
		if (compare(array[mid], array[index]))
			start = mid + 1;
		else
			end = mid;
	}
	if (start == range.start + range.length - 1 && compare(array[start], array[index])) start++;
	return start;
}

/* find the index of the last value within the range that is equal to array[index], plus 1 */
long BinaryLast(Test array[], long index, Range range, Comparison compare) {
	long start = range.start, end = range.start + range.length - 1;
	while (start < end) {
		long mid = start + (end - start)/2;
		if (!compare(array[index], array[mid]))
			start = mid + 1;
		else
			end = mid;
	}
	if (start == range.start + range.length - 1 && !compare(array[index], array[start])) start++;
	return start;
}

/* n^2 sorting algorithm used to sort tiny chunks of the full array */
void InsertionSort(Test array[], Range range, Comparison compare) {
	long i, j;
	for (i = range.start + 1; i < range.start + range.length; i++) {
		Test temp = array[i];
		for (j = i; j > range.start && compare(temp, array[j - 1]); j--)
			array[j] = array[j - 1];
		array[j] = temp;
	}
}

/* reverse a range within the array */
void Reverse(Test array[], Range range) {
	long index;
	for (index = range.length/2 - 1; index >= 0; index--)
		Swap(array[range.start + index], array[range.start + range.length - index - 1]);
}

/* swap a series of values in the array */
void BlockSwap(Test array[], long start1, long start2, long block_size) {
	long index;
	for (index = 0; index < block_size; index++) Swap(array[start1 + index], array[start2 + index]);
}

/* rotate the values in an array ([0 1 2 3] becomes [1 2 3 0] if we rotate by 1) */
void Rotate(Test array[], long amount, Range range, Test cache[], const long cache_size) {
	Range range1, range2;
	
	if (range.length == 0) return;
	
	if (amount >= 0) amount = range.start + (amount % range.length);
	else amount = range.start + range.length - ((-amount) % range.length);
	
	range1 = RangeBetween(range.start, amount);
	range2 = RangeBetween(amount, range.start + range.length);
	
	/* if the smaller of the two ranges fits into the cache, it's *slightly* faster copying it there and shifting the elements over */
	if (range1.length <= range2.length) {
		if (range1.length <= cache_size) {
			memcpy(&cache[0], &array[range1.start], range1.length * sizeof(array[0]));
			memmove(&array[range1.start], &array[range2.start], range2.length * sizeof(array[0]));
			memcpy(&array[range1.start + range2.length], &cache[0], range1.length * sizeof(array[0]));
			return;
		}
	} else {
		if (range2.length <= cache_size) {
			memcpy(&cache[0], &array[range2.start], range2.length * sizeof(array[0]));
			memmove(&array[range2.start + range2.length - range1.length], &array[range1.start], range1.length * sizeof(array[0]));
			memcpy(&array[range1.start], &cache[0], range2.length * sizeof(array[0]));
			return;
		}
{'fraction_non_alphanumeric': 0.15685346459674365, 'fraction_numerical': 0.021014767133661492, 'mean_word_length': 3.666519434628975, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 61, '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': '3036796', 'n_tokens_mistral': 3882, 'n_tokens_neox': 3613, 'n_words': 1243}