jive.map source code

1 /**
2 License: public domain
3 Authors: Simon Bürger
4 */
5 module jive.map;
6 
7 private import std.range;
8 private import std.algorithm;
9 private import jive.set;
10 
11 /**
12  * An (unordered map), based on jive.set.
13  * Similar to builtin 'V[Key]', but with value-semantics.
14  */
15 struct Map(Key, V)
16 {
17 	private Set!Entry entries;
18 
19 	private static struct Entry
20 	{
21 		Key key;
22 		V value;
23 
24 		size_t toHash() const @safe /*pure*/ nothrow
25 		{
26 			return typeid(Key).getHash(&key);
27 		}
28 
29 		bool opEquals(const(Entry) b) const @safe pure nothrow
30 		{
31 			return key == b.key;
32 		}
33 
34 		bool opEquals(ref const(Entry) b) const @safe pure nothrow
35 		{
36 			return key == b.key;
37 		}
38 
39 		bool opEquals(const(Key) b) const @safe pure nothrow
40 		{
41 			return key == b;
42 		}
43 
44 		bool opEquals(ref const(Key) b) const @safe pure nothrow
45 		{
46 			return key == b;
47 		}
48 	}
49 
50 	/** returns: true if set is empty */
51 	bool empty() const pure nothrow @safe
52 	{
53 		return entries.empty;
54 	}
55 
56 	/** returns: number of elements in the set */
57 	size_t length() const pure nothrow @safe
58 	{
59 		return entries.length;
60 	}
61 
62 	/** returns: true if key is found in the map */
63 	bool opIn_r(T)(auto ref const(T) key) const
64 		if(is(typeof(T.init == Key.init)))
65 	{
66 		return entries.opIn_r(key);
67 	}
68 
69 	/**
70 	 * Lookup a key and return the stored value.
71 	 * If the key does not currently exist, it is created and its
72 	 * value set to V.init.
73 	 */
74 	ref V opIndex(T)(auto ref const(T) key)
75 		if(is(typeof(T.init < Key.init)))
76 	{
77 		auto r = entries.find(key);
78 
79 		if(r is null)
80 		{
81 			entries.add(Entry(key, V.init));
82 			r = entries.find(key);
83 		}
84 
85 		assert(r !is null);
86 		return r.value;
87 	}
88 
89 	/**
90 	 * Remove a key and associated value from the map.
91 	 * returns: true if removed, false if not found
92 	 */
93 	bool remove(T)(auto ref const(T) k)
94 		if(is(typeof(T.init < Key.init)))
95 	{
96 		return entries.remove(k);
97 	}
98 
99 	/**
100 	 * Traverse all entries using foreach.
101 	 * TODO: turn this into ranges
102 	 */
103 	int opApply(int delegate(ref Key) dg)
104 	{
105 		int r = 0;
106 		foreach(ref e; entries[])
107 			if((r = dg(e.key)) != 0)
108 				break;
109 		return r;
110 	}
111 
112 	/**
113 	 * ditto
114 	 */
115 	int opApply(int delegate(ref Key, ref V) dg)
116 	{
117 		int r = 0;
118 		foreach(ref e; entries[])
119 			if((r = dg(e.key, e.value)) != 0)
120 				break;
121 		return r;
122 	}
123 }
124 
125 unittest
126 {
127 	Map!(int,int) a;
128 	a[1] = 1;
129 	a[2] = 2;
130 	a[1] = 3;
131 	a.remove(2);
132 
133 	assert(1 in a);
134 	assert(2 !in a);
135 	assert(a.length == 1);
136 	assert(a[1] == 3);
137 }