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 	auto opIndex(this This)(K key) const
34 	{
35 		alias CET = ContainerElementType!(This, V);
36 		auto tme = TreeMapElement(key);
37 		return cast(CET) tree.equalRange(tme).front.value;
38 	}
39 
40 	/**
41 	 * Removes the key→value mapping for the given key.
42 	 * Params: key = the key to remove
43 	 * Returns: true if the key existed in the map
44 	 */
45 	bool remove(K key)
46 	{
47 		auto tme = TreeMapElement(key);
48 		return tree.remove(tme);
49 	}
50 
51 	/// Returns: true if the mapping contains the given key
52 	bool containsKey(K key)
53 	{
54 		auto tme = TreeMapElement(key);
55 		return tree.contains(tme);
56 	}
57 
58 	/// Returns: true if the mapping is empty
59 	bool empty() const pure nothrow @property @safe @nogc
60 	{
61 		return tree.empty;
62 	}
63 
64 	/// Returns: the number of key→value pairs in the map
65 	size_t length() const pure nothrow @property @safe @nogc
66 	{
67 		return tree.length;
68 	}
69 
70 	/// Supports $(B foreach(k, v; treeMap)) syntax.
71 	int opApply(this This)(int delegate(ref K, ref V) loopBody)
72 	{
73 		int result;
74 		foreach (ref tme; tree[])
75 		{
76 			result = loopBody(tme.key, tme.value);
77 			if (result)
78 				break;
79 		}
80 		return result;
81 	}
82 
83 private:
84 
85 	import containers.ttree : TTree;
86 	import containers.internal.storage_type : ContainerStorageType;
87 	import containers.internal.element_type : ContainerElementType;
88 
89 	static struct TreeMapElement
90 	{
91 		ContainerStorageType!K key;
92 		ContainerStorageType!V value;
93 		int opCmp(ref const TreeMapElement other) const
94 		{
95 			import std.functional : binaryFun;
96 			return binaryFun!less(key, other.key);
97 		}
98 	}
99 	TTree!(TreeMapElement, false, "a.opCmp(b) > 0", supportGC, cacheLineSize) tree;
100 }
101 
102 unittest
103 {
104 	TreeMap!(string, string) tm;
105 	tm["test1"] = "hello";
106 	tm["test2"] = "world";
107 	tm.remove("test1");
108 	tm.remove("test2");
109 }