digitalmars.D - O(1) dictionaries

mandel (26/26) Nov 13 2007 Hi,

Tim Keating (15/37) Nov 14 2007 Why does the array literal have to be in mixed order? You can just do

mandel (9/51) Nov 14 2007 You named the reason, it won't line up.

Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= (20/57) Nov 14 2007 That's no good excuse to not use templates :P :

Robert Fraser (2/66) Nov 14 2007 IMHO, CTFE produces cleaner code, too, and there are no worries about sy...
mandel (11/21) Nov 15 2007 Your template looks like it does it's jobs quite nicely - thx.

Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= (9/40) Nov 15 2007 I hope you use CTFE instead in a "production code" since the templates h...

mandel (4/8) Nov 15 2007 Despite all benefits, it doesn't make the code easier to understand.
renoX (8/41) Nov 17 2007 Quite some times ago, there was a thread on 'reflective enums' where

mandel <oh no.es> writes:

Hi,

I have made a dictionary that way:
enum Word { Hello, Bye };
char[][Word] dict;

static this()
{
   dict = [
     Word.Hello : "Hello",
     Word.Bye : "Bye"
   ];
}

Now there are two problems I have with this:

- the dict is an AA, but an array would be much faster,
  but it is not possible to assign it via an array literal
  with a mixed order and supplied keys.
char[][Word.max] dict = [Word.Hello : "Hello", ...]

- in place initialisation with a literal is not possible.
  Instead, the use of "static this" makes the code look long winded.

Does anyone have some nice workaround for these limitations?

The current solution is long winded (ok, I can make the name shorter),
but a literal would be nicer much.
static this()
{
    english_dictionary[ Word.Hello] = "Hello";
    //[...]
}

Nov 13 2007

Tim Keating <holyspamster gmail.com> writes:

mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

Why does the array literal have to be in mixed order? You can just do 
the enum and the array in the same order:

enum Word { Hello, Bye };
char[] dict = [ "Hello", "Bye" ];

The only complication there is that for a dictionary of any meaningful 
length, it won't line up quite as nicely. Ensuring each enum value 
matches its correct word will be a real pain. In this situation, I might 
use code generation.

 - in place initialisation with a literal is not possible.
   Instead, the use of "static this" makes the code look long winded.

It seems from what you say above that you already know its, but that's 
not true anymore. Array literals were recently added to the language 
(see the "expressions" section of the language spec).

However, if you think _that's_ long-winded, consider how you would do 
that initialization in C++ . . .

TK

Nov 14 2007

mandel <oh no.es> writes:

Tim Keating Wrote:

 mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

 
 Why does the array literal have to be in mixed order? You can just do 
 the enum and the array in the same order:
 
 enum Word { Hello, Bye };
 char[] dict = [ "Hello", "Bye" ];
 
 The only complication there is that for a dictionary of any meaningful 
 length, it won't line up quite as nicely. Ensuring each enum value 
 matches its correct word will be a real pain. In this situation, I might 
 use code generation.

You named the reason, it won't line up.
The dict may also change order when words are added and quite possibly
regrouped.
The entire alignment will be hard to maintain.

 
 - in place initialisation with a literal is not possible.
   Instead, the use of "static this" makes the code look long winded.

 
 It seems from what you say above that you already know its, but that's 
 not true anymore. Array literals were recently added to the language 
 (see the "expressions" section of the language spec).

From the specs I see that I should have said that statically initialization
is not possible with AAs. The use of "static this" for this causes the binary
to abort execution immediately because of "cyclic dependencies" (In cases of
multiple static this in different modules).
And a custom init function also doesn't look that nice.

 
 However, if you think _that's_ long-winded, consider how you would do 
 that initialization in C++ . . .

I know...
But imho it could be done even better in D. :P

Nov 14 2007

Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:

mandel wrote:

 Tim Keating Wrote:
 
 mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

 
 Why does the array literal have to be in mixed order? You can just do
 the enum and the array in the same order:
 
 enum Word { Hello, Bye };
 char[] dict = [ "Hello", "Bye" ];
 
 The only complication there is that for a dictionary of any meaningful
 length, it won't line up quite as nicely. Ensuring each enum value
 matches its correct word will be a real pain. In this situation, I might
 use code generation.

 You named the reason, it won't line up.
 The dict may also change order when words are added and quite possibly
 regrouped. The entire alignment will be hard to maintain.

That's no good excuse to not use templates :P :

template _E(T...) {
  static if (T.length>1)
    const _E = T[0] ~ "," ~ _E!(T[1..$]);
  else
    const _E = T[0] ~ "};";
}

template _A(T...) {
  static if (T.length>1)
    const _A = `"` ~ T[0] ~ `"[],` ~ _A!(T[1..$]);
  else
    const _A = `"` ~ T[0] ~ `"[]];`;
}

template RealEnum(char[] aName, char[] eName, T...) {
  const RealEnum = "enum " ~ eName ~ "{" ~ _E!(T) ~
                   "char[][] " ~ aName ~ "=[" ~ _A!(T);
}

mixin(RealEnum!("Word", "dict", "Hello", "Bye"));

CTFE would produce smaller binaries though.

Nov 14 2007

Robert Fraser <fraserofthenight gmail.com> writes:

Jari-Matti M�kel� Wrote:

 mandel wrote:
 
 Tim Keating Wrote:
 
 mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

 
 Why does the array literal have to be in mixed order? You can just do
 the enum and the array in the same order:
 
 enum Word { Hello, Bye };
 char[] dict = [ "Hello", "Bye" ];
 
 The only complication there is that for a dictionary of any meaningful
 length, it won't line up quite as nicely. Ensuring each enum value
 matches its correct word will be a real pain. In this situation, I might
 use code generation.

 You named the reason, it won't line up.
 The dict may also change order when words are added and quite possibly
 regrouped. The entire alignment will be hard to maintain.

 
 That's no good excuse to not use templates :P :
 
 template _E(T...) {
   static if (T.length>1)
     const _E = T[0] ~ "," ~ _E!(T[1..$]);
   else
     const _E = T[0] ~ "};";
 }
 
 template _A(T...) {
   static if (T.length>1)
     const _A = `"` ~ T[0] ~ `"[],` ~ _A!(T[1..$]);
   else
     const _A = `"` ~ T[0] ~ `"[]];`;
 }
 
 template RealEnum(char[] aName, char[] eName, T...) {
   const RealEnum = "enum " ~ eName ~ "{" ~ _E!(T) ~
                    "char[][] " ~ aName ~ "=[" ~ _A!(T);
 }
 
 mixin(RealEnum!("Word", "dict", "Hello", "Bye"));
 
 CTFE would produce smaller binaries though.

IMHO, CTFE produces cleaner code, too, and there are no worries about symbol
length.

Nov 14 2007

mandel <oh no.es> writes:

Jari-Matti M�kel� Wrote:

 mandel wrote:
 The dict may also change order when words are added and quite possibly
 regrouped. The entire alignment will be hard to maintain.

 
 That's no good excuse to not use templates :P :
 

[temlate kungfu]
 
 mixin(RealEnum!("Word", "dict", "Hello", "Bye"));
 
 CTFE would produce smaller binaries though.

Your template looks like it does it's jobs quite nicely - thx.

The reason I try to avoid templates is that they often look like
an entry for an obfuscation competition. ;>

Templates in D (in even much more in C++) are hard to understand,
they don't look like just compile time D code but like a new language.
(well, I guess the D compilers may need an integrated scripting engine to
execute D code at compile time).

And as many developers, I try to avoid code templates if there is no real
benefit or if they stay simple enough for other devs to understand at first
sight.

I only use hackish code in speed critical sections (not like NASA, but critical
in the sense of overall program speed).
well, dictionaries in my applications may fit in this role. :}

Nov 15 2007

Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:

mandel wrote:

 Jari-Matti M�kel� Wrote:
 
 mandel wrote:
 The dict may also change order when words are added and quite possibly
 regrouped. The entire alignment will be hard to maintain.

 
 That's no good excuse to not use templates :P :
 

 [temlate kungfu]
 
 mixin(RealEnum!("Word", "dict", "Hello", "Bye"));
 
 CTFE would produce smaller binaries though.

 
 Your template looks like it does it's jobs quite nicely - thx.
 
 The reason I try to avoid templates is that they often look like
 an entry for an obfuscation competition. ;>

Hide them in __dontlookhere.d :)

 
 Templates in D (in even much more in C++) are hard to understand,
 they don't look like just compile time D code but like a new language.
 (well, I guess the D compilers may need an integrated scripting engine to
 execute D code at compile time).

I hope you use CTFE instead in a "production code" since the templates have
typename limitations and bloat the executable. I pasted some old since I
wasn't sure if CTFE supports varargs now and happened to have the old code
around.

 
 And as many developers, I try to avoid code templates if there is no real
 benefit or if they stay simple enough for other devs to understand at
 first sight.
 
 I only use hackish code in speed critical sections (not like NASA, but
 critical in the sense of overall program speed). well, dictionaries in my
 applications may fit in this role. :}

I agree mixins would be cleaner if you could do macro like stuff on a bit
higher level than now and if they worked in more places (for example inside
switches).

Nov 15 2007

mandel <oh no.es> writes:

Jari-Matti M�kel� Wrote:

 I hope you use CTFE instead in a "production code" since the templates have
 typename limitations and bloat the executable. I pasted some old since I
 wasn't sure if CTFE supports varargs now and happened to have the old code
 around.

Despite all benefits, it doesn't make the code easier to understand.
That's a big issue.

I guess I will try to bite the bullet.

Nov 15 2007

renoX <renosky free.fr> writes:

mandel a �crit :
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]
 
 - in place initialisation with a literal is not possible.
   Instead, the use of "static this" makes the code look long winded.
 
 Does anyone have some nice workaround for these limitations?
 
 The current solution is long winded (ok, I can make the name shorter),
 but a literal would be nicer much.
 static this()
 {
     english_dictionary[ Word.Hello] = "Hello";
     //[...]
 }

Quite some times ago, there was a thread on 'reflective enums' where 
Kevin Bealer, I and other tried to make better enums, you could use the 
code as a basis of your work.

Note that I don't think much of the results: D isn't flexible enough for 
this .. at least currently.

Regards,
renoX

Nov 17 2007

D Programming

C/C++ Programming

Other

digitalmars.D - O(1) dictionaries