[Issue 10733] New: Add a druntime function to find the pointer to a key of a built-in associative array given the pointer to a value

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=10733

           Summary: Add a druntime function to find the pointer to a key
                    of a built-in associative array given the pointer to a
                    value
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: druntime
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2013-07-31 08:59:51 PDT ---
Associative arrays are handy, but beside sets and bags there's a common desire
for ordered dictionaries. They are not ordered in the sense an AVL is ordered,
it's not the order of the keys that matters for them, but the insertion order
of the key-value pairs. So they are hash-based, unlike a search tree. The
Python standard library has such data structure:

http://docs.python.org/2/library/collections.html#collections.OrderedDict

An OrderedDict has some of the advantages of an array (it keeps the insertion
order, its printing and its iteration is deterministic, it can be iterated
backwards too), and it can have a popLast or popHead member function.

There are several ways to implement an OrderedDict in library code. One of the
simplest is to wrap a built-in D hash based associative array. 

Let's say the implementation is like:


final class OrderedAA(KeyType, ValType) {
    static struct MyValue {
        ValType item;
        typeof(this)* pred, succ;
    }
    private MyValue[KeyType] data;
    ...
}


Each value is a struct that beside the original value 'item' also contains a
pointer to the precedent and successive MV, in a circular doubly linked list.

The member functions of OrderedAA that add or remove items from the associative
array manage the linked list of values. The iteration is a range that follows
the linked list. But this way you only scan the values.

To also implement byKey or to scan the keys in a foreach, or the key-value
pairs, you find the pointer to the key given the pointer to a value MyValue.

There a way to find the pointer to an AA key given the pointer to its value,
but it's not portable and it's undocumented.

So perhaps it's worth adding to the standard object module of druntime a
portable way to find that pointer, to allow a simple library-based
implementation of a hash-based ordered associative array. Such function must
work in O(1), it's meant only for access the key in read mode, and it's
probably short and simple to write. The disadvantage it that such function
works on the inner representation of the D associative arrays, so it can
potentially constraint future implementations of such associative arrays. But
it's not easy to invent AA implementations that make it hard to implement that
function in O(1).

Alternative or better solutions/ideas are welcome.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------