1 module collections.linkedhashset;
2 
3 import collections.commons;
4 import collections.linkedlist;
5 import std.traits : ReturnType, hasFunctionAttributes;
6 
7 /**
8  * Implements linked hashset with a linked set as a backend.
9  * Uses an equal method for comparison, meaning it can use complex keys.
10  * Has poorer access times compared to the hashset with a binary search tree as a backend, but less costly insertion.
11  * Elements cannot be accessed directly, instead it can check whether an element is within it or not.
12  * Backend's foreach capability is exposed to iterate over hashcodes.
13  */
14 public struct LinkedHashSet(K, alias hashFunc = defaultHash128!(K), alias equal = "a == b") {
15     static enum bool nogcIndexing = hasFunctionAttributes!(hashFunc, "@nogc");
16 	alias HashType = ReturnType!hashFunc;
17     private LinkedList!(HashType, false, equal) backend;
18     /**
19 	 * Creates a LinkedHashSet from a compatible range.
20 	 */
21 	public this(R)(R range) @safe pure nothrow {
22 		foreach(K key; range) put(key);
23 	}
24     /**
25 	 * Puts an item into the hash set, then returns the generated hashcode.
26 	 */
27     HashType put(K key) @safe pure nothrow {
28 		return backend.put(hashFunc(key));
29 	}
30     /**
31 	 * Puts a hashcode into the hash set.
32 	 */
33 	private HashType put(HashType key) @safe pure nothrow {
34 		return backend.put(key);
35 	}
36 	/**
37 	 * Returns true if the element exists within the set, false otherwise.
38 	 */
39 	bool has(K key) @safe pure nothrow {
40 		return backend.has(hashFunc(key));
41 	}
42 	/**
43 	 * Returns the amount of elements found in the set.
44 	 */
45 	size_t hasRange(R)(R range) @safe pure nothrow {
46 		size_t result;
47 		foreach (key; range) {
48 			if(has(key)) result++;
49 		}
50 		return result;
51 	}
52     /**
53 	 * Removes an element by match.
54 	 * Returns the hashcode if found, or uint.init if not.
55 	 */
56 	HashType removeByElem(K key) @safe pure nothrow {
57 		return backend.removeByElem(hashFunc(key));
58 	}
59 	/**
60 	 * Removes an element by hashcode.
61 	 */
62 	HashType removeByElem(HashType key) @safe pure nothrow {
63 		return backend.removeByElem(key);
64 	}
65 	alias remove = removeByElem;
66     /**
67 	 * Set operators.
68 	 * Enables math operations on sets, like unions and intersections.
69 	 * Could work on ranges in general as long as they implement some basic functions, like iteration.
70 	 */
71 	LinkedHashSet!(K, hashFunc, equal) opBinary(string op, R)(R rhs) {
72 		static if(op == "|" || op == "~") {//Union
73 			LinkedHashSet!(K, hashFunc, equal) result;
74 			foreach(e ; backend)
75 				result.put(e);
76 			foreach(e ; rhs) 
77 				result.put(e);
78 			return result;
79 		} else static if(op == "&" || op == "*") {//Intersection
80 			LinkedHashSet!(K, hashFunc, equal) result;
81 			foreach(e ; rhs){
82 				if(backend.has(e)) result.put(e);
83 			}
84 			return result;
85 		} else static if(op == "-" || op == "/") {//Complement
86 			LinkedHashSet!(K, hashFunc, equal) result;
87 			foreach(e ; backend)
88 				result.put(e);
89 			foreach(e ; rhs){
90 				result.removeByElem(e);
91 			}
92 			return result;
93 		} else static if(op == "^"){//Difference
94 			LinkedHashSet!(K, hashFunc, equal) result = this | rhs;
95 			LinkedHashSet!(K, hashFunc, equal) common = this & rhs;
96 			foreach(e ; common){
97 				result.removeByElem(e);
98 			}
99 			return result;
100 		} else static assert(0, "Operator " ~ op ~ "not supported");
101 	}
102 	/**
103 	 * Set operators.
104 	 */
105 	LinkedHashSet!(K, hashFunc, equal) opOpAssign(string op)(E value) {
106 		static if(op == "~=") {//Append
107 			put(value);
108 		} else static if(op == "-=" || op == "/=") {
109 			removeByElem(value);
110 		} else static assert(0, "Operator " ~ op ~ "not supported");
111 		return this;
112 	}
113 	/**
114 	 * Set operators.
115 	 */
116 	LinkedHashSet!(K, hashFunc, equal) opOpAssign(string op, R)(R range) {
117 		static if(op == "~=" || op == "|=") {//Append
118 			foreach(val; range)
119 				put(val);
120 		} else static if(op == "-=" || op == "/=") {
121 			foreach(val; range)
122 				removeByElem(val);
123 		} else static assert(0, "Operator " ~ op ~ "not supported");
124 		return this;
125 	}
126 	/**
127 	 * Returns the element at the front.
128 	 */
129 	@property HashType front() @nogc @safe nothrow pure {
130 		return backend.front;
131 	}
132     /**
133 	 * Returns the element at begin and increments the position by one.
134 	 */
135 	HashType moveFront() @nogc @safe nothrow pure {
136 		return backend.moveFront;
137 	}
138 	/**
139 	 * Increments the front iteration position by one
140 	 */
141 	void popFront() @nogc @safe nothrow pure {
142 		backend.popFront();
143 	}
144     /**
145 	 * Returns true when the end of the list have been reached.
146 	 */
147 	@property bool empty() @nogc @safe nothrow pure {
148 		return backend.empty;
149 	}
150     /**
151 	 * Returns a copy of this struct.
152 	 */
153 	@property auto save() @nogc @safe nothrow pure {
154 		return this;
155 	}
156 }
157 
158 unittest {
159 	alias MatchFinder = LinkedHashSet!(string);
160 	MatchFinder set = MatchFinder(["AAAAAA","BBBBBB","CCCCCC","DDDDDD"]);
161 	assert(set.has("AAAAAA"));
162 	assert(set.has("BBBBBB"));
163 	assert(set.has("CCCCCC"));
164 	assert(set.has("DDDDDD"));
165 	assert(!set.has("000000"));
166 }
167 
168 unittest {	///Test set operators
169 	alias MatchFinder = LinkedHashSet!(string);
170 	MatchFinder a = MatchFinder(["AAAA", "BBBB", "CCCC", "DDDD", "EEEE"]), b = MatchFinder(["DDDD", "EEEE", "FFFF", "GGGG"]);
171 	MatchFinder c = MatchFinder(["BBBB", "CCCC", "EEEE", "GGGG"]), d = MatchFinder(["AAAA", "EEEE", "BBBB", "GGGG"]);
172 	MatchFinder union_ab = a | b, union_ad = a | d;
173 	assert(union_ab.hasRange(["AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "FFFF", "GGGG"]) == 7);
174 	assert(union_ad.hasRange(["AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "GGGG"]) == 6);
175 	MatchFinder intrsctn_ab = a & b, intrsctn_cd = c & d, intrsctn_ac = a & c;
176 	MatchFinder diff_ab = a ^ b;
177 	MatchFinder comp_ab = a - b;
178 	assert(intrsctn_ab.hasRange(["DDDD", "EEEE"]) == 2);
179 	assert(intrsctn_ac.hasRange(["BBBB", "CCCC", "EEEE"]) == 3);
180 	assert(intrsctn_cd.hasRange(["BBBB", "GGGG"]) == 2);
181 	assert(diff_ab.hasRange(["AAAA", "BBBB", "CCCC", "FFFF", "GGGG"]) == 5);
182 	assert(comp_ab.hasRange(["AAAA", "BBBB", "CCCC"]) == 3);
183 }