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 }