www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Find if keys are in two dimensional associative array

reply Michal Minich <michal.minich gmail.com> writes:
if one has double indexed aa, how to find that it contains value under 
keys 'a' and 123

float[int][char] aa;

aa['a'][123] = 4.56;

I had to make following helper function. Is there more elegant way / 
built in into D?

float* isIn = doubleIn(123, 'a');

float* doubleIn (int i, char ch) {

    float[int]* first = ch in aa;

    if (first is null)
        return null;
    else
        return i in *first;
}
Jan 17 2010
next sibling parent reply Mike Wey <mike-wey example.com> writes:
On 01/17/2010 01:23 PM, Michal Minich wrote:

 if one has double indexed aa, how to find that it contains value under
 keys 'a' and 123

 float[int][char] aa;

 aa['a'][123] = 4.56;

 I had to make following helper function. Is there more elegant way /
 built in into D?

 float* isIn = doubleIn(123, 'a');

 float* doubleIn (int i, char ch) {

      float[int]* first = ch in aa;

      if (first is null)
          return null;
      else
          return i in *first;
 }


This should work.

float[int][char] aa;

aa['a'][123] = 4.56;

if ( 123 in aa['a'] )
	writeln(true);
else
	writeln(false);

-- 
Mike Wey
Jan 17 2010
parent Michal Minich <michal.minich gmail.com> writes:
On Sun, 17 Jan 2010 15:08:08 +0100, Mike Wey wrote:


 This should work.
 
 float[int][char] aa;
 
 aa['a'][123] = 4.56;
 
 if ( 123 in aa['a'] )
 	writeln(true);
 else
 	writeln(false);



if 'a' is not there then "aa['a'] will either return null, or exception 
(I don't know exactly). This is not good in any case, because then asking 
"123 in null" will crash always...
Jan 17 2010
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Michal Minich:

 float[int][char] aa;


Is something like this good for you (but I don't remember if Tuples define a
toHash)?
float[Tuple!(char, int)] aa;

Bye,
bearophile
Jan 17 2010
parent reply Michal Minich <michal.minich gmail.com> writes:
On Sun, 17 Jan 2010 09:11:06 -0500, bearophile wrote:


 Michal Minich:

 float[int][char] aa;


 
 Is something like this good for you (but I don't remember if Tuples
 define a toHash)? float[Tuple!(char, int)] aa;
 
 Bye,
 bearophile


if I have more lookups based on int than on char like:

tmp = ch in aa;
foreach ...
	i in tmp

then I think this would be more effective than always searching by both 
values in tuple.

Anyway the tuple is struct. I think struct equality is defined by 
equality of all fields, then it should work in AA...
Jan 17 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Michal Minich:

 Anyway the tuple is struct. I think struct equality is defined by 
 equality of all fields, then it should work in AA...


In D the built in AAs require an equality test and/or cmp, plus opHash. (The
collisions are resolved with an ordered search tree (maybe AVL, I don't
remember, probably not a ternary tree)). Normal structs don't define all that.
I don't remember if Tuple of D2 define all that. See the docs. (My Record
struct can be used just fine as AA keys).

Bye,
bearophile
Jan 17 2010
parent reply Michal Minich <michal.minich gmail.com> writes:
On Sun, 17 Jan 2010 11:28:49 -0500, bearophile wrote:


 In D the built in AAs require an equality test and/or cmp, plus opHash.
 (The collisions are resolved with an ordered search tree (maybe AVL, I
 don't remember, probably not a ternary tree)). Normal structs don't
 define all that. I don't remember if Tuple of D2 define all that. See
 the docs. (My Record struct can be used just fine as AA keys).


Why should AAs require opCmp. What if object is not logically sortable, 
(like Guid, DbConnection, ...). Equality & Hash should be enough...
Is the opCmp here to optimize lookup? Because opCmp may be quite slow, 
which may affect appending performance...
Jan 17 2010
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
Michal Minich wrote:

 On Sun, 17 Jan 2010 11:28:49 -0500, bearophile wrote:


 In D the built in AAs require an equality test and/or cmp, plus opHash.




AAs require all three for classes: opEquals, opCmp, and toHash. Further, 
opEquals and opCmp must be consistent: when opEquals returns true, opCmp 
must return 0, and when opCmp returns non-zero, opEquals must return false.

toHash is optional for structs.


 Why should AAs require opCmp. What if object is not logically sortable,
 (like Guid, DbConnection, ...). Equality & Hash should be enough...
 Is the opCmp here to optimize lookup? Because opCmp may be quite slow,
 which may affect appending performance...


I don't know the answer, but the spec says so at

   http://digitalmars.com/d/2.0/arrays.html

<quote>
The implementation may use either opEquals or opCmp or both. Care should 
be taken so that the results of opEquals and opCmp are consistent with 
each other when the class objects are the same or not.
</quote>

Ali
Jan 17 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Ali Çehreli:

 I don't know the answer, but the spec says so at


I have already given the answer, the hash collisions are resolved with an
ordered search tree.

Bye,
bearophile
Jan 18 2010
prev sibling next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Michal Minich <michal.minich gmail.com> wrote:


 Is there more elegant way / built in into D?


As far as I know, there is no built-in way. A more general solution than  
yours can be created with templates, however:

template elementTypeOfDepth( T : V[ K ], int depth, V, K ) {
     static if ( depth == 0 ) {
         alias V elementTypeOfDepth;
     } else {
         alias elementTypeOfDepth!( V, depth -1 )  elementTypeOfDepth;
     }
}

elementTypeOfDepth!( T, U.length )* isIn( T : V[ K ], V, K, U... )( T arr,  
K key, U index ) {
     auto p = key in arr;
     static if ( U.length > 0 ) {
         if ( p ) {
             return isIn( *p, index );
         } else {
             return null;
         }
     } else {
         return p;
     }
}

Usage:

int[char][int][char] foo;

if ( isIn( foo, 'a', 3, 'b' ) ) {
     writeln( "Excelsior!" );
}

-- 
Simen
Jan 17 2010
parent reply Michal Minich <michal.minich gmail.com> writes:
On Sun, 17 Jan 2010 18:02:00 +0100, Simen kjaeraas wrote:


 Michal Minich <michal.minich gmail.com> wrote:
 

 Is there more elegant way / built in into D?


 
 As far as I know, there is no built-in way. A more general solution than
 yours can be created with templates, however:
 
 template elementTypeOfDepth( T : V[ K ], int depth, V, K ) {
      static if ( depth == 0 ) {
          alias V elementTypeOfDepth;
      } else {
          alias elementTypeOfDepth!( V, depth -1 )  elementTypeOfDepth;
      }
 }
 
 elementTypeOfDepth!( T, U.length )* isIn( T : V[ K ], V, K, U... )( T
 arr, K key, U index ) {
      auto p = key in arr;
      static if ( U.length > 0 ) {
          if ( p ) {
              return isIn( *p, index );
          } else {
              return null;
          }
      } else {
          return p;
      }
 }
 
 Usage:
 
 int[char][int][char] foo;
 
 if ( isIn( foo, 'a', 3, 'b' ) ) {
      writeln( "Excelsior!" );
 }


This is great! I was thinking such generic template would be good, but I 
did not have need for it right now.

This should be definitely posted to bugzilla as enhancement for Phobos, 
and also for Tango.

I was thinking this also may be solved by modification in language:

the problem with statement "123 in *('a' in aa)" is that if "('a' in 
aa')" returns null, then next check will fail: (123 in null) -> null 
reference error.

if D simply check if the second part of InExpression is null, and if yes, 
return null, otherwise evaluate as is currently done.
Jan 17 2010
parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Michal Minich <michal.minich gmail.com> wrote:


 This is great! I was thinking such generic template would be good, but I
 did not have need for it right now.

 This should be definitely posted to bugzilla as enhancement for Phobos,
 and also for Tango.


Thank you. I have now improved the code to also work for normal arrays:


template elementTypeOfDepth( T : V[ K ], int depth, V, K ) {
     static if ( depth == 0 ) {
         alias V elementTypeOfDepth;
     } else {
         alias elementTypeOfDepth!( V, depth -1 )  elementTypeOfDepth;
     }
}

template elementTypeOfDepth( T : V[ ], int depth, V ) {
     static if ( depth == 0 ) {
         alias V elementTypeOfDepth;
     } else {
         alias elementTypeOfDepth!( V, depth -1 )  elementTypeOfDepth;
     }
}

elementTypeOfDepth!( T, U.length )* isIn( T : V[ ], V, U... )( T arr,  
size_t key, U index ) {
     if ( key < arr.length ) {
         auto p = arr[ key ];
         static if ( U.length > 0 ) {
             if ( p ) {
                 return isIn( p, index );
             } else {
                 return null;
             }
         } else {
             return p;
         }
     } else {
         return null;
     }
}

elementTypeOfDepth!( T, U.length )* isIn( T : V[ K ], V, K, U... )( T arr,  
K key, U index ) {
     auto p = key in arr;
     static if ( U.length > 0 ) {
         if ( p ) {
             return isIn( *p, index );
         } else {
             return null;
         }
     } else {
         return p;
     }
}

Usage:
int[char][][int] foo;
if ( isIn( foo, 3, 87, 'a' ) ) {
     writeln( "Excelsior!" );
}


 I was thinking this also may be solved by modification in language:

 the problem with statement "123 in *('a' in aa)" is that if "('a' in
 aa')" returns null, then next check will fail: (123 in null) -> null
 reference error.

 if D simply check if the second part of InExpression is null, and if yes,
 return null, otherwise evaluate as is currently done.


This sounds good. Put it in Bugzilla.

-- 
Simen
Jan 17 2010
prev sibling next sibling parent BCS <none anon.com> writes:
Hello Michal,


 if one has double indexed aa, how to find that it contains value under
 keys 'a' and 123
 
 float[int][char] aa;
 
 aa['a'][123] = 4.56;
 
 I had to make following helper function. Is there more elegant way /
 built in into D?
 
 float* isIn = doubleIn(123, 'a');
 
 float* doubleIn (int i, char ch) {
 
 float[int]* first = ch in aa;
 
 if (first is null)
 return null;
 else
 return i in *first;
 }


That's how I'd do it, more or less. However I'd skip the function (or go 
with the more general case as shown by Simen).

float* isIn = null;
if(auto a = 'a' in aa) b = 123 in *a;
Jan 17 2010
prev sibling parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
Michal Minich wrote:


 if one has double indexed aa, how to find that it contains value under 
 keys 'a' and 123

 float[int][char] aa;

 aa['a'][123] = 4.56;

 I had to make following helper function. Is there more elegant way / 
 built in into D?

 float* isIn = doubleIn(123, 'a');

 float* doubleIn (int i, char ch) {

     float[int]* first = ch in aa;

     if (first is null)
         return null;
     else
         return i in *first;
 }


Don't know if this would have any affect on what you want, but there is
this bugzilla: "Associative array of associative arrays gets confused"

http://d.puremagic.com/issues/show_bug.cgi?id=3709
Jan 18 2010
parent Michal Minich <michal.minich gmail.com> writes:
Hello Jesse,


 Don't know if this would have any affect on what you want, but there
 is this bugzilla: "Associative array of associative arrays gets
 confused"
 
 http://d.puremagic.com/issues/show_bug.cgi?id=3709



Thank you, but it is some other issue. I posted enhacement request already 
http://d.puremagic.com/issues/show_bug.cgi?id=3718
Jan 19 2010