A graph data structure usable in @safe pure nothrow functions

[w0rp via Digitalmars-d]

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.