Compile-Time std::map

[Frits van Bommel]

NN wrote:
> Ok, from the beginning :)
> While writing I think all problems are solved, but I'm not sure.
> 
> I want to do binary search on any array:
> 
> int[] sorted_array = {1,2,3};
> binary_search(sorted_array, 1); // complexity O(log N)
> 
> But i can do it only if array is sorted.
> I want to write any array and sort it in compile time:
> 
> int[] sorted_array = compile_time_sort({3,2,1});
> 
> Is it possible ?

Yes it is. Compile-time quicksort:
---
T[] ctfe_split(T)(T[] arr, T pivot, bool low) {
	if (arr.length == 0) return arr;
	
	if ((arr[0] < pivot) == low) {
		T[] rest = ctfe_split(arr[1 .. $], pivot, low);
		rest ~= arr[0];
		return rest;
	} else {
		return ctfe_split(arr[1 .. $], pivot, low);
	}
}

T[] ctfe_sort(T)(T[] arr) {
	if (arr.length < 2) return arr;
	
	T pivot = arr[0];
	
	T[] left = ctfe_split(arr[1 .. $], pivot, true);
	left = ctfe_sort(left);
	
	T[] right = ctfe_split(arr[1 .. $], pivot, false);
	right = ctfe_sort(right);
	
	return left ~ pivot ~ right;
}

//
// Usage example:
//
import std.stdio;

int[] sorted_arr = ctfe_sort([5,10,1,2,3,5,7,13,17,11,2]);

void main() {
	writefln(sorted_arr);
}
---
(These functions probably allocate too much to be very efficient at run 
time, but I had to work around some stuff that apparently doesn't work 
at compile time)


For some reason this doesn't compile on GDC 0.23 though. Perhaps some 
CTFE improvements were made since DMD 1.007 (on which that GDC is based) 
that will (hopefully) be in the next release?