I allways wanted to create std::map but in compile time.

The problem:
I want to write smth like:
int[int] x = {3:3,2:2,1:1}

But compiler will generate the following:
int[int] x = {1:1,2:2,3:3}

Thus I can use binary search on x.

Is it possible to do in D ?
Thanx.

NN wrote:
> I allways wanted to create std::map but in compile time.
> 
> The problem:
> I want to write smth like:
> int[int] x = {3:3,2:2,1:1}
> 
> But compiler will generate the following:
> int[int] x = {1:1,2:2,3:3}
> 
> Thus I can use binary search on x.
> 
> Is it possible to do in D ?
> Thanx.

Well, in case you didn't notice, DMD 1.014 now includes hash literals. Assigning static hashes aren't yet supported directly, but you can do simple cases like

  int val = ([1:11,2:22,3:33][1]);

Why does it need extra parenthesis - don't ask me.

Don and BCS showed how you can simulate assignment to a static variable with

  char[][uint] symTable() { return [2u:"he",4:"ho",6:"hi"]; }

and

  char[][uint] symTable;
  static this() { symTable=[2u:"he",4:"ho",6:"hi"]; }

They both have some limitations.

Jari-Matti Mäkelä Wrote:

> NN wrote:
> > I allways wanted to create std::map but in compile time.
> > 
> > The problem:
> > I want to write smth like:
> > int[int] x = {3:3,2:2,1:1}
> > 
> > But compiler will generate the following:
> > int[int] x = {1:1,2:2,3:3}
> > 
> > Thus I can use binary search on x.
> > 
> > Is it possible to do in D ?
> > Thanx.
> 
> Well, in case you didn't notice, DMD 1.014 now includes hash literals. Assigning static hashes aren't yet supported directly, but you can do simple cases like
> 
>   int val = ([1:11,2:22,3:33][1]);
> 
> Why does it need extra parenthesis - don't ask me.
> 
> Don and BCS showed how you can simulate assignment to a static variable with
> 
>   char[][uint] symTable() { return [2u:"he",4:"ho",6:"hi"]; }
> 
> and
> 
>   char[][uint] symTable;
>   static this() { symTable=[2u:"he",4:"ho",6:"hi"]; }
> 
> They both have some limitations.
But it does not do what I want.
I want to rearange the values in compile time.

NN wrote:
> Jari-Matti Mäkelä Wrote:
>> NN wrote:
>> > I allways wanted to create std::map but in compile time.
>> > 
>> > The problem:
>> > I want to write smth like:
>> > int[int] x = {3:3,2:2,1:1}
>> > 
>> > But compiler will generate the following:
>> > int[int] x = {1:1,2:2,3:3}
>> > 
>> > Thus I can use binary search on x.
>> > 
>> > Is it possible to do in D ?
>> > Thanx.
>> 
>> Well, in case you didn't notice, DMD 1.014 now includes hash literals. Assigning static hashes aren't yet supported directly, but you can do simple cases like
>> 
>>   int val = ([1:11,2:22,3:33][1]);
>> 

> But it does not do what I want.
> I want to rearange the values in compile time.

Oh, sorry. If you just want to rearrange the array contents on compile time, you can do it with a CTFE function or with tuples, then assign the resulting tuple into an array.

Jari-Matti Mäkelä Wrote:

> NN wrote:
> > Jari-Matti Mäkelä Wrote:
> >> NN wrote:
> >> > I allways wanted to create std::map but in compile time.
> >> > 
> >> > The problem:
> >> > I want to write smth like:
> >> > int[int] x = {3:3,2:2,1:1}
> >> > 
> >> > But compiler will generate the following:
> >> > int[int] x = {1:1,2:2,3:3}
> >> > 
> >> > Thus I can use binary search on x.
> >> > 
> >> > Is it possible to do in D ?
> >> > Thanx.
> >> 
> >> Well, in case you didn't notice, DMD 1.014 now includes hash literals. Assigning static hashes aren't yet supported directly, but you can do simple cases like
> >> 
> >>   int val = ([1:11,2:22,3:33][1]);
> >> 
> 
> > But it does not do what I want.
> > I want to rearange the values in compile time.
> 
> Oh, sorry. If you just want to rearrange the array contents on compile time, you can do it with a CTFE function or with tuples, then assign the resulting tuple into an array.

OK.
If i would write:
int[int] a = f([2:2, 1:1, 3:3]);

Won't it create [2:2, 1:1, 3:3] and [1:1, 2:2, 3:3] ?
Or the compiler will remove the first array ?

NN wrote:

> Jari-Matti Mäkelä Wrote:
> 
>> NN wrote:
>> > Jari-Matti Mäkelä Wrote:
>> >> NN wrote:
>> >> > I allways wanted to create std::map but in compile time.
>> >> > 
>> >> > The problem:
>> >> > I want to write smth like:
>> >> > int[int] x = {3:3,2:2,1:1}
>> >> > 
>> >> > But compiler will generate the following:
>> >> > int[int] x = {1:1,2:2,3:3}
>> >> > 
>> >> > Thus I can use binary search on x.
>> >> > 
>> >> > Is it possible to do in D ?
>> >> > Thanx.
>> >> 
>> >> Well, in case you didn't notice, DMD 1.014 now includes hash literals. Assigning static hashes aren't yet supported directly, but you can do simple cases like
>> >> 
>> >>   int val = ([1:11,2:22,3:33][1]);
>> >> 
>> 
>> > But it does not do what I want.
>> > I want to rearange the values in compile time.
>> 
>> Oh, sorry. If you just want to rearrange the array contents on compile time, you can do it with a CTFE function or with tuples, then assign the resulting tuple into an array.
> 
> OK.
> If i would write:
> int[int] a = f([2:2, 1:1, 3:3]);
> 
> Won't it create [2:2, 1:1, 3:3] and [1:1, 2:2, 3:3] ?
> Or the compiler will remove the first array ?

Can you please show some use cases. I'm not really sure what you are trying to do here. :) Do you need to be able to add new keys at runtime? The builtin associative array uses quite optimal data structures so don't need to worry about them unless you need extreme performance.

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 ?

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 since the latest dmd release this is not hard to do, but only when using array literals of course. This crappy sort method works in compile time, pretty amazing how easy it is to do such things!

T[] selectionSort(T)(T[] array)
{
	T temp;
	for(int i = 0; i < array.length; ++i)
	{
		int min = i;
		for(int j = i + 1; j < array.length; ++j)
			if (array[j] < array[min])
				min = j;
		temp = array[i];
		array[i] = array[min];
		array[min] = temp;
	}
	return array;
}

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 ?

I haven't been able to test this yet since I haven't updated to DMD 1.014 yet.  Also, YES I know it's not exactly an efficient sort, but it's at compile time, and if *this* works, getting quicksort to work shouldn't be too hard.

T[] compile_time_sort(T)(T[] arr)
{
    if( arr.length == 0 || arr.length == 1 )
        return arr;
    else
        return insert_into(arr[0], compile_time_sort(arr[1..$]));
}

T[] insert_into(T)(T v, T[] arr)
{
    if( arr.length == 0 )
        return [v];
    else
    {
        if( v <= arr[0] )
            return [v] ~ arr;
        else
            return arr[0..1] ~ insert_into(v, arr[1..$]);
    }
}

int[] sorted_array = compile_time_sort([3,2,1]);

import std.stdio;

void main()
{
    writefln("%s", sorted_array);
}

-- 
int getRandomNumber()
{
    return 4; // chosen by fair dice roll.
              // guaranteed to be random.
}

http://xkcd.com/

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/

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?