1 module collections.hashset;
2 
3 import collections.treemap;
4 import collections.linkedlist;
5 import std.traits;
6 //import std.digest.murmurhash;
7 public import collections.commons;
8 /**
9  * Implements a hashset, either using collections.treemap or collections.linkedlist as a set for backend.
10  * Cannot be accessed directly, instead it can check whether an element is within it or not.
11  * Backend's foreach capability is exposed to iterate over hashcodes.
12  */
13 public struct HashSet(K, alias hashFunc = defaultHash!K, alias less = "a < b") {
14 	alias HashType = ReturnType!hashFunc;
15 	alias Backend = TreeMap!(HashType, void, true, less);
16 	private Backend			backend;
17 	/**
18 	 * Creates a HashSet from a compatible range.
19 	 */
20 	public this(R)(R range) @safe pure nothrow {
21 		foreach(K key; range) put(key);
22 	}
23 	/**
24 	 * Puts an item into the hash set, then returns the generated hashcode.
25 	 */
26 	HashType put(K key) @safe pure nothrow {
27 		return backend.put(hashFunc(key));
28 	}
29 	/**
30 	 * Puts a hashcode into the hash set.
31 	 */
32 	private HashType put(HashType key) @safe pure nothrow {
33 		return backend.put(key);
34 	}
35 	/**
36 	 * Returns true if the element exists within the set, false otherwise.
37 	 */
38 	bool has(K key) @safe pure nothrow {
39 		return backend.has(hashFunc(key));
40 	}
41 	/**
42 	 * Returns the amount of elements found in the set.
43 	 */
44 	size_t hasRange(R)(R range) @safe pure nothrow {
45 		size_t result;
46 		foreach (key; range) {
47 			if(has(key)) result++;
48 		}
49 		return result;
50 	}
51 	/**
52 	 * Removes an element by match.
53 	 * Returns the hashcode if found, or uint.init if not.
54 	 */
55 	HashType removeByElem(K key) @safe pure nothrow {
56 		return backend.removeByElem(hashFunc(key));
57 	}
58 	/**
59 	 * Removes an element by hashcode.
60 	 */
61 	HashType removeByElem(HashType key) @safe pure nothrow {
62 		return backend.removeByElem(key);
63 	}
64 	alias remove = removeByElem;
65 	/**
66 	 * Set operators.
67 	 * Enables math operations on sets, like unions and intersections.
68 	 * Could work on ranges in general as long as they implement some basic functions, like iteration.
69 	 */
70 	HashSet!(K, hashFunc, less) opBinary(string op, R)(R rhs) {
71 		static if(op == "|" || op == "~") {//Union
72 			HashSet!(K, hashFunc, less) result;
73 			foreach(e ; backend)
74 				result.put(e);
75 			foreach(e ; rhs) 
76 				result.put(e);
77 			return result;
78 		} else static if(op == "&" || op == "*") {//Intersection
79 			HashSet!(K, hashFunc, less) result;
80 			foreach(e ; rhs){
81 				if(backend.has(e)) result.put(e);
82 			}
83 			return result;
84 		} else static if(op == "-" || op == "/") {//Complement
85 			HashSet!(K, hashFunc, less) result;
86 			foreach(e ; backend)
87 				result.put(e);
88 			foreach(e ; rhs){
89 				result.removeByElem(e);
90 			}
91 			return result;
92 		} else static if(op == "^"){//Difference
93 			HashSet!(K, hashFunc, less) result = this | rhs;
94 			HashSet!(K, hashFunc, less) common = this & rhs;
95 			foreach(e ; common){
96 				result.removeByElem(e);
97 			}
98 			return result;
99 		} else static assert(0, "Operator " ~ op ~ "not supported");
100 	}
101 	/**
102 	 * Set operators.
103 	 */
104 	HashSet!(K, hashFunc, less) opOpAssign(string op)(E value) {
105 		static if(op == "~=") {//Append
106 			put(value);
107 		} else static if(op == "-=" || op == "/=") {
108 			removeByElem(value);
109 		} else static assert(0, "Operator " ~ op ~ "not supported");
110 		return this;
111 	}
112 	/**
113 	 * Set operators.
114 	 */
115 	HashSet!(K, hashFunc, less) opOpAssign(string op, R)(R range) {
116 		static if(op == "~=" || op == "|=") {//Append
117 			foreach(val; range)
118 				put(val);
119 		} else static if(op == "-=" || op == "/=") {
120 			foreach(val; range)
121 				removeByElem(val);
122 		} else static assert(0, "Operator " ~ op ~ "not supported");
123 		return this;
124 	}
125 	private int opApply(scope int delegate(HashType) dg) {
126 		return backend.opApply(dg);
127 	}
128 }
129 
130 unittest {
131 	alias MatchFinder = HashSet!(string);
132 	MatchFinder set = MatchFinder(["AAAAAA","BBBBBB","CCCCCC","DDDDDD"]);
133 	assert(set.has("AAAAAA"));
134 	assert(set.has("BBBBBB"));
135 	assert(set.has("CCCCCC"));
136 	assert(set.has("DDDDDD"));
137 	assert(!set.has("000000"));
138 }
139 
140 unittest {	///Test set operators
141 	alias MatchFinder = HashSet!(string);
142 	MatchFinder a = MatchFinder(["AAAA", "BBBB", "CCCC", "DDDD", "EEEE"]), b = MatchFinder(["DDDD", "EEEE", "FFFF", "GGGG"]);
143 	MatchFinder c = MatchFinder(["BBBB", "CCCC", "EEEE", "GGGG"]), d = MatchFinder(["AAAA", "EEEE", "BBBB", "GGGG"]);
144 	MatchFinder union_ab = a | b, union_ad = a | d;
145 	assert(union_ab.hasRange(["AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "FFFF", "GGGG"]) == 7);
146 	assert(union_ad.hasRange(["AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "GGGG"]) == 6);
147 	MatchFinder intrsctn_ab = a & b, intrsctn_cd = c & d, intrsctn_ac = a & c;
148 	MatchFinder diff_ab = a ^ b;
149 	MatchFinder comp_ab = a - b;
150 	assert(intrsctn_ab.hasRange(["DDDD", "EEEE"]) == 2);
151 	assert(intrsctn_ac.hasRange(["BBBB", "CCCC", "EEEE"]) == 3);
152 	assert(intrsctn_cd.hasRange(["BBBB", "GGGG"]) == 2);
153 	assert(diff_ab.hasRange(["AAAA", "BBBB", "CCCC", "FFFF", "GGGG"]) == 5);
154 	assert(comp_ab.hasRange(["AAAA", "BBBB", "CCCC"]) == 3);
155 }