digitalmars.D - Compile-Time std::map
- NN (9/9) Apr 27 2007 I allways wanted to create std::map but in compile time.
- =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= (13/26) Apr 27 2007 Well, in case you didn't notice, DMD 1.014 now includes hash literals.
- NN (3/37) Apr 28 2007 But it does not do what I want.
- Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= (4/28) Apr 28 2007 Oh, sorry. If you just want to rearrange the array contents on compile t...
- NN (6/36) Apr 28 2007 OK.
- Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= (5/44) Apr 28 2007 Can you please show some use cases. I'm not really sure what you are try...
- NN (9/9) Apr 28 2007 Ok, from the beginning :)
- Lutger (19/33) Apr 28 2007 Yes since the latest dmd release this is not hard to do, but only when
- Daniel Keep (39/53) Apr 28 2007 I haven't been able to test this yet since I haven't updated to DMD
- Frits van Bommel (42/56) Apr 28 2007 Yes it is. Compile-time quicksort:
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
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
Jari-Matti Mäkelä Wrote:NN wrote:But it does not do what I want. I want to rearange the values in compile time.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 28 2007
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
Jari-Matti Mäkelä Wrote:NN wrote: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 ?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
NN wrote:Jari-Matti Mäkelä Wrote: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.NN wrote: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 ?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
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
Lutger <lutger.blijdestijn gmail.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 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
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
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