www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - AA insertion order iteration

reply spir <denis.spir gmail.com> writes:
Hello,

How would you wrap an AA to allow memorising insertion order, and be able to
use it
for iteration?

* Indeed, one could store keys in a // (ordered) array. But this means
iteration requires a series of lookups by key.
* A slightly better method would be to store hash values, which anyway are
computed at insertion time, and pass them to whatever internal routine is used
to
fetch an item.
* Even better, store an array of pointers to the items.

Typically, items in hash tables are kinds of cells in the "bucket" storing
pairs which "modulo-ed" hash values are equal. If I know the internal
representation of such cells, then I can get (key,value) pairs. I've read once
such buckets are now linked lists, which can only make things simpler.
The issue for last 2 solutions is I need to catch some info at insertion time. 
The second one even requires calling an internal routine.
Any chance? In any case, a pointer to current implementation of D AAs is
welcome.

Other ideas?

Thank you,
Denis
-- 
_________________
vita es estrany
spir.wikidot.com
Feb 14 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 14 Feb 2011 06:31:25 -0500, spir <denis.spir gmail.com> wrote:


 Hello,

 How would you wrap an AA to allow memorising insertion order, and be  
 able to use it
 for iteration?

 * Indeed, one could store keys in a // (ordered) array. But this means
 iteration requires a series of lookups by key.
 * A slightly better method would be to store hash values, which anyway  
 are
 computed at insertion time, and pass them to whatever internal routine  
 is used to
 fetch an item.
 * Even better, store an array of pointers to the items.

 Typically, items in hash tables are kinds of cells in the "bucket"  
 storing
 pairs which "modulo-ed" hash values are equal. If I know the internal
 representation of such cells, then I can get (key,value) pairs. I've  
 read once
 such buckets are now linked lists, which can only make things simpler.
 The issue for last 2 solutions is I need to catch some info at insertion  
 time. The second one even requires calling an internal routine.
 Any chance? In any case, a pointer to current implementation of D AAs is  
 welcome.


Here is the main struct which calls the implementation functions:

https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L2461

Hopefully the functions that it calls are clues as to where to find the  
implementations (all in druntime).  I warn you, they are based fully on  
runtime information, so they are going to be ugly.

-Steve
Feb 14 2011
parent reply spir <denis.spir gmail.com> writes:
On 02/14/2011 03:27 PM, Steven Schveighoffer wrote:

 On Mon, 14 Feb 2011 06:31:25 -0500, spir <denis.spir gmail.com> wrote:


 Hello,

 How would you wrap an AA to allow memorising insertion order, and be able to
 use it
 for iteration?

 * Indeed, one could store keys in a // (ordered) array. But this means
 iteration requires a series of lookups by key.
 * A slightly better method would be to store hash values, which anyway are
 computed at insertion time, and pass them to whatever internal routine is
 used to
 fetch an item.
 * Even better, store an array of pointers to the items.

 Typically, items in hash tables are kinds of cells in the "bucket" storing
 pairs which "modulo-ed" hash values are equal. If I know the internal
 representation of such cells, then I can get (key,value) pairs. I've read once
 such buckets are now linked lists, which can only make things simpler.
 The issue for last 2 solutions is I need to catch some info at insertion
 time. The second one even requires calling an internal routine.
 Any chance? In any case, a pointer to current implementation of D AAs is
 welcome.


 Here is the main struct which calls the implementation functions:

 https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L2461

 Hopefully the functions that it calls are clues as to where to find the
 implementations (all in druntime). I warn you, they are based fully on runtime
 information, so they are going to be ugly.

 -Steve


Thank you Steve. Would be a bit too complicated for me now, because this struct 
does not expose what I need (internal operation of insertion), only what 
corresponds to ordinary D lang operations. I'm not ready for messing with lower 
level code (yet).

denis
-- 
_________________
vita es estrany
spir.wikidot.com
Feb 14 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 14 Feb 2011 16:39:24 -0500, spir <denis.spir gmail.com> wrote:


 On 02/14/2011 03:27 PM, Steven Schveighoffer wrote:

 On Mon, 14 Feb 2011 06:31:25 -0500, spir <denis.spir gmail.com> wrote:


 Hello,

 How would you wrap an AA to allow memorising insertion order, and be  
 able to
 use it
 for iteration?

 * Indeed, one could store keys in a // (ordered) array. But this means
 iteration requires a series of lookups by key.
 * A slightly better method would be to store hash values, which anyway  
 are
 computed at insertion time, and pass them to whatever internal routine  
 is
 used to
 fetch an item.
 * Even better, store an array of pointers to the items.

 Typically, items in hash tables are kinds of cells in the "bucket"  
 storing
 pairs which "modulo-ed" hash values are equal. If I know the internal
 representation of such cells, then I can get (key,value) pairs. I've  
 read once
 such buckets are now linked lists, which can only make things simpler.
 The issue for last 2 solutions is I need to catch some info at  
 insertion
 time. The second one even requires calling an internal routine.
 Any chance? In any case, a pointer to current implementation of D AAs  
 is
 welcome.


 Here is the main struct which calls the implementation functions:

 https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L2461

 Hopefully the functions that it calls are clues as to where to find the
 implementations (all in druntime). I warn you, they are based fully on  
 runtime
 information, so they are going to be ugly.

 -Steve


 Thank you Steve. Would be a bit too complicated for me now, because this  
 struct does not expose what I need (internal operation of insertion),  
 only what corresponds to ordinary D lang operations. I'm not ready for  
 messing with lower level code (yet).


It's not that low level.  The functions are basically C binded functions  
 from druntime.  Do a tree-search for those symbols and you'll find the  
implementations.  The only ugly part is how it uses runtime information  
for things like comparing two instances.

-Steve
Feb 14 2011