• w0rp (70/70) May 25 2014 I've been updating a git repository which is like my dumping
• FG (4/6) May 25 2014 get and setDefault are nice, but can be easily done as small UFCS wrappe...
• w0rp (6/18) May 25 2014 My main blocker was that byKey and byValue functions on
• w0rp (8/8) May 26 2014 I just added @nogc support to the map and graph types, with

"w0rp" <devw0rp gmail.com> writes:

I've been updating a git repository which is like my dumping 
ground for data structures, etc. I write for fun. I think for as 
long as I have been using D, as a lover of graph theory and also 
all of D's function qualifiers, I have been wanting graph types 
which can be used in  safe pure nothrow functions. The big 
blocker on this was what associative arrays could offer.

The current associative array implementation couldn't get me all 
the way there, so I wrote my own hashmap type.

Documentation: https://w0rp.com/project/dstruct/dstruct/map/
Source: 
https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d

I wrote a little benchmark for my hashmaps and the standard 
associative arrays. As with all my benchmarks, I'm sure I 
probably made a glaring error which shows how if you do something 
different your computer will explode.

Benchmark: https://gist.github.com/anonymous/4a060b8f65684eb0586c

It produced this output on my modern machine, with times on the 
left representing associative arrays, and the right representing 
my new HashMap, with just 'rdmd test.d'.

AddAndRemove: 163ms -> 111ms
AddAndFetch: 112ms -> 108ms
AddAndGet: 108ms -> 109ms
AddAndIn: 103ms -> 108ms

So, about the same performance. This hashmap now has 'keys,' 
'values,' and 'items' functions for creating ranges through the 
maps which can be mutable, tail-const, tail-immutable, const, or 
immutable, return by reference from the maps, and are all usable 
in  safe pure nothrow functions.  nogc is probably possible for 
all of these too in future.

I also added setDefault methods to my HashMap type which lets you 
get a value from a map or lazily set a new value and then get 
that back. It's pretty much 'setdefault' from Python, only a bit 
more lazy, and it only computes a hash once per call. So I can do 
this in my graph implementation.

// Get a currency adjacency list or create a new one.
Vertex[] adjacencyList = map.setDefault(vertex);

My graph types make use of the hashmap I wrote so the graphs can 
be implemented in terms of adjacency lists, where an edge is 
stored by a vertex mapping to a list of vertices with the 
outgoing vertices for the edge. This is not the best 
implementation for all scenarios, but it is probably the best way 
I know of for representing graphs with any type of vertex in the 
majority of scenarios.

Documentation: https://w0rp.com/project/dstruct/dstruct/graph/
Source: 
https://github.com/w0rp/dstruct/blob/master/source/dstruct/graph.d

So when you put everything all together, it means that you can 
now write this code.

import dstruct.graph;

 safe pure nothrow
auto someEdgesIDunno() {
     Digraph!string graph;

     graph.addEdge("a", "b");
     graph.addEdge("b", "c");

     return graph.edges;
}

void main(string[] argv) {
     import std.stdio;

     /*
      a -> b
      b -> c
     */
     foreach(edge; someEdgesIDunno()) {
         writefln("%s -> %s", edge.from, edge.to);
     }
}

There you have it. The hardest part recently I posted on d.learn 
about, which was trying to figure out a way to write ranges which 
propagate 'constness' nicely. This is a whole other topic...

Destroy.

FG <home fgda.pl> writes:

On 2014-05-25 16:39, w0rp wrote:
 I have been wanting graph types which can be used in  safe pure nothrow
functions. The big blocker on this was what associative arrays could offer.
 The current associative array implementation couldn't get me all the way
there, so I wrote my own hashmap type.

get and setDefault are nice, but can be easily done as small UFCS wrappers
around the "element in array" expression.
What was blocking you in the current implementation of associative arrays?
Can't it be fixed without having to come up with a custom map type?

"w0rp" <devw0rp gmail.com> writes:

On Sunday, 25 May 2014 at 17:30:52 UTC, FG wrote:
 On 2014-05-25 16:39, w0rp wrote:
 I have been wanting graph types which can be used in  safe 
 pure nothrow functions. The big blocker on this was what 
 associative arrays could offer.
 The current associative array implementation couldn't get me 
 all the way there, so I wrote my own hashmap type.

 get and setDefault are nice, but can be easily done as small 
 UFCS wrappers around the "element in array" expression.
 What was blocking you in the current implementation of 
 associative arrays?
 Can't it be fixed without having to come up with a custom map 
 type?

My main blocker was that byKey and byValue functions on 
associative arrays weren't usable in  safe pure nothrow 
functions. So implementing my own gave me ranges I could use for 
doing the right things. The setDefault implementation is just 
kind of an added bonus.

"w0rp" <devw0rp gmail.com> writes:

I just added  nogc support to the map and graph types, with 
fallback behaviour for older D compiler versions. I used this.

static if(__VERSION__ < 2066) { enum nogc = 1; }

So as long as I write  nogc left of other attributes, it will 
compile the library on both DMD 2.065 and DMD 2.066.

Now every range, get, and remove function on the maps and graphs 
can be used in  nogc functions, because these functions never 
allocate more memory on the garbage collected heap.