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 }