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

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

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

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