www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Compile-Time std::map

reply NN <nn-mail bk.ru> writes:
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.
Apr 27 2007
parent reply =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
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.
Apr 27 2007
parent reply NN <nn-mail bk.ru> writes:
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.

I want to rearange the values in compile time.
Apr 28 2007
parent reply Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
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.
Apr 28 2007
parent reply NN <nn-mail bk.ru> writes:
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 ?
Apr 28 2007
parent reply Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
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.
Apr 28 2007
parent reply NN <nn-mail bk.ru> writes:
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 ?
Apr 28 2007
next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
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; }
Apr 28 2007
prev sibling next sibling parent Daniel Keep <daniel.keep.lists gmail.com> writes:
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/
Apr 28 2007
prev sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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?
Apr 28 2007