containers.treemap source code

1 /**
2  * Tree Map
3  * Copyright: © 2014 Economic Modeling Specialists, Intl.
4  * Authors: Brian Schott
5  * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
6  */
7 
8 module containers.treemap;
9 
10 /**
11  * A key→value mapping where the keys are guaranteed to be sorted.
12  * Params:
13  *     K = the key type
14  *     V = the value type
15  *     less = the key comparison function to use
16  *     supportGC = true to support storing GC-allocated objects, false otherwise
17  *     cacheLineSize = the size of the internal nodes in bytes
18  */
19 struct TreeMap(K, V, alias less = "a < b", bool supportGC = true,
20 	size_t cacheLineSize = 64)
21 {
22 
23 	this(this) @disable;
24 
25 	/// Supports $(B treeMap[key] = value;) syntax.
26 	void opIndexAssign(V value, K key)
27 	{
28 		auto tme = TreeMapElement(key, value);
29 		tree.insert(tme);
30 	}
31 
32 	/// Supports $(B treeMap[key]) syntax.
33 	V opIndex(K key) const
34 	{
35 		auto tme = TreeMapElement(key);
36 		return tree.equalRange(tme).front.value;
37 	}
38 
39 	/**
40 	 * Removes the key→value mapping for the given key.
41 	 * Params: key = the key to remove
42 	 * Returns: true if the key existed in the map
43 	 */
44 	bool remove(K key)
45 	{
46 		auto tme = TreeMapElement(key);
47 		return tree.remove(tme);
48 	}
49 
50 	/// Returns: true if the mapping contains the given key
51 	bool containsKey(K key)
52 	{
53 		auto tme = TreeMapElement(key);
54 		return tree.contains(tme);
55 	}
56 
57 	/// Returns: true if the mapping is empty
58 	bool empty() const pure nothrow @property @safe @nogc
59 	{
60 		return tree.empty;
61 	}
62 
63 	/// Returns: the number of key→value pairs in the map
64 	size_t length() const pure nothrow @property @safe @nogc
65 	{
66 		return tree.length;
67 	}
68 
69 	/// Supports $(B foreach(k, v; treeMap)) syntax.
70 	int opApply(int delegate(ref K, ref V) loopBody)
71 	{
72 		int result;
73 		foreach (ref tme; tree[])
74 		{
75 			result = loopBody(tme.key, tme.value);
76 			if (result)
77 				break;
78 		}
79 		return result;
80 	}
81 
82 private:
83 
84 	import containers.ttree : TTree;
85 
86 	static struct TreeMapElement
87 	{
88 		K key;
89 		V value;
90 		int opCmp(ref const TreeMapElement other) const
91 		{
92 			import std.functional : binaryFun;
93 			return binaryFun!less(key, other.key);
94 		}
95 	}
96 	TTree!(TreeMapElement, false, "a.opCmp(b) > 0", supportGC, cacheLineSize) tree;
97 }
98 
99 unittest
100 {
101 	TreeMap!(string, string) tm;
102 	tm["test1"] = "hello";
103 	tm["test2"] = "world";
104 	tm.remove("test1");
105 	tm.remove("test2");
106 }