1 module collections.linkedmap; 2 3 import std.functional : binaryFun; 4 public import collections.commons; 5 6 /** 7 * Implements a linked map datastructure. 8 * Similar to TreeMap, but instead relies on the equals function, which can mean it can compare keys much easier, 9 * meaning much bigger data can be compared easily without hashing. Also it doesn't need to rebalance a tree, which 10 * lowers insertion complexity at the cost of higher theoretical access times (n). 11 * This linked map has the behavior of putting new elements at the back, resulting in an ordered map similar to 12 * what PHP and YAML also has. 13 * `ovrwrtBhvr` changes the overwrite behavior when keymatches are found. If true, then if a key is already existing, 14 * then it'll overwrite it at the given position. If false, then the matching key will be first deleted, then the 15 * new one will be always put in the end. 16 */ 17 18 public struct LinkedMap(K, E, bool nogcIndexing = true, alias equal = "a == b", bool ovrwrtBhvr = true) { 19 private struct Node { 20 K key; ///Identifier key 21 E elem; ///Element stored within the node 22 Node* next; ///Next node, null if none exists 23 Node* prev; ///Previous node, null if none exists 24 25 ///Keturns a string representation of the node. 26 string toString() const { 27 import std.conv : to; 28 string result = "key: " ~ to!string(key) ~ " ; elem: " ~ to!string(elem); 29 if (next) result ~= " ; next: [" ~ next.toString ~ "]"; 30 return result; 31 } 32 } 33 protected Node* root; ///Root element. 34 protected Node* last; ///Last element. 35 protected size_t _length;///N. of currently stored elements 36 /** 37 * opApply override for foreach. 38 */ 39 int opApply(scope int delegate(ref E) dg) { 40 Node* crnt = root; 41 while (crnt) { 42 if (dg(crnt.elem)) return 1; 43 crnt = crnt.next; 44 } 45 return 0; 46 } 47 /** 48 * opApply override for foreach. 49 */ 50 int opApply(scope int delegate(K, ref E) dg) { 51 Node* crnt = root; 52 while (crnt) { 53 if (dg(crnt.key, crnt.elem)) return 1; 54 crnt = crnt.next; 55 } 56 return 0; 57 } 58 /** 59 * opApplyReverse override for foreach. 60 */ 61 int opApplyReverse(scope int delegate(ref E) dg) { 62 Node* crnt = last; 63 while (crnt) { 64 if (dg(crnt.elem)) return 1; 65 crnt = crnt.prev; 66 } 67 return 0; 68 } 69 /** 70 * opApplyReverse override for foreach. 71 */ 72 int opApplyReverse(scope int delegate(K, ref E) dg) { 73 Node* crnt = last; 74 while (crnt) { 75 if (dg(crnt.key, crnt.elem)) return 1; 76 crnt = crnt.prev; 77 } 78 return 0; 79 } 80 package static string makeFunc() { 81 string makeFuncIndiv(string args) { 82 return ` 83 int opApply(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 84 Node* crnt = root; 85 while (crnt) { 86 if (dg(crnt.elem)) return 1; 87 crnt = crnt.next; 88 } 89 return 0; 90 } 91 int opApply(scope int delegate(K, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 92 Node* crnt = root; 93 while (crnt) { 94 if (dg(crnt.key, crnt.elem)) return 1; 95 crnt = crnt.next; 96 } 97 return 0; 98 } 99 int opApplyReverse(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 100 Node* crnt = last; 101 while (crnt) { 102 if (dg(crnt.elem)) return 1; 103 crnt = crnt.prev; 104 } 105 return 0; 106 } 107 int opApplyReverse(scope int delegate(K, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 108 Node* crnt = last; 109 while (crnt) { 110 if (dg(crnt.key, crnt.elem)) return 1; 111 crnt = crnt.prev; 112 } 113 return 0; 114 }`; 115 } 116 string result; 117 foreach (attr; attrList) { 118 result ~= makeFuncIndiv(attr); 119 } 120 return result; 121 } 122 mixin(makeFunc); 123 static if(nogcIndexing) { 124 /** 125 * Returns the element with the given key. 126 * Returns E.init if not found. 127 */ 128 E opIndex(K key) @nogc @safe pure nothrow { 129 Node* crnt = root; 130 while (crnt) { 131 if (binaryFun!equal(crnt.key, key)) return crnt.elem; 132 crnt = crnt.next; 133 } 134 return E.init; 135 } 136 /** 137 * Returns the pointer of the element with the given key. 138 * Returns null if not found. 139 */ 140 E* ptrOf(K key) @nogc @safe pure nothrow { 141 Node* crnt = root; 142 while (crnt) { 143 if (binaryFun!equal(crnt.key, key)) return &crnt.elem; 144 crnt = crnt.next; 145 } 146 return null; 147 } 148 } else { 149 /** 150 * Returns the element with the given key. 151 * Returns E.init if not found. 152 */ 153 ref E opIndex(K key) @safe pure { 154 Node* crnt = root; 155 while (crnt) { 156 if (binaryFun!equal(crnt.key, key)) return crnt.elem; 157 crnt = crnt.next; 158 } 159 throw new ElementNotFoundException("Key not found!"); 160 } 161 } 162 /** 163 * Assigns a value to the given key. 164 */ 165 auto opIndexAssign(E value, K key) @safe pure nothrow { 166 Node** crnt = &root; 167 while (*crnt) { 168 static if (ovrwrtBhvr) { 169 if (binaryFun!equal((*crnt).key, key)) { 170 return (*crnt).elem = value; 171 } 172 } else { 173 if (binaryFun!equal((*crnt).key, key)) { 174 if ((*crnt).next) (*crnt).next.prev = (*crnt).prev; 175 crnt = &(*crnt).next; 176 _length--; 177 } 178 } 179 //prev = crnt; 180 crnt = &(*crnt).next; 181 } 182 //prev.next = new Node(key, value, null); 183 *crnt = new Node(key, value, null, *crnt); 184 last = *crnt; 185 _length++; 186 return value; 187 } 188 /** 189 * Removes a value with the given key and returns it. 190 */ 191 E remove(K key) @safe pure nothrow { 192 Node** crnt = &root; 193 while (*crnt) { 194 if (binaryFun!equal((*crnt).key, key)) { 195 E result = (*crnt).elem; 196 //if ((*crnt).prev) (*crnt).prev.next = (*crnt).next; 197 if ((*crnt).next is null) last = (*crnt).prev; 198 else (*crnt).next.prev = (*crnt).prev; 199 *crnt = (*crnt).next; 200 _length--; 201 return result; 202 } 203 crnt = &(*crnt).next; 204 } 205 return E.init; 206 } 207 /** 208 * Returns true if key is found. 209 */ 210 bool has(K key) @nogc @safe pure nothrow { 211 Node* crnt = root; 212 while (crnt) { 213 if (binaryFun!equal(crnt.key, key)) return true; 214 crnt = crnt.next; 215 } 216 return false; 217 } 218 /** 219 * Returns the number of elements in the LinkedMap. 220 */ 221 @property size_t length() @nogc @safe pure nothrow const { 222 return _length; 223 } 224 ///Returns the string representation of this container format 225 string toString() const { 226 if (root) return root.toString; 227 else return "empty"; 228 } 229 } 230 231 unittest { 232 import std.random : uniform; 233 import std.exception : assertThrown; 234 import std.stdio : writeln; 235 { 236 alias IntMap = LinkedMap!(int, int); 237 IntMap test0, test1; 238 test0[0] = 0; 239 test0[0] = 1; 240 test0[1] = 1; 241 test0[2] = 1; 242 test0[3] = 1; 243 test0[4] = 1; 244 assert(test0.length == 5, "length mismatch!"); 245 test0.remove(3); 246 assert(test0.length == 4, "item deletion error!"); 247 assert(test0.ptrOf(0), "pointer error!"); 248 assert(!test0.ptrOf(10), "pointer error!"); 249 250 for(int i ; i < 256 ; i++) 251 test1[i] = uniform(0, 65_536); 252 assert(test1.length == 256, "length mismatch!"); 253 foreach(elem ; test1) { 254 255 } 256 foreach(key, elem ; test1) { 257 258 } 259 foreach_reverse(elem ; test1) { 260 261 } 262 foreach_reverse(key, elem ; test1) { 263 264 } 265 } 266 { 267 alias IntMap = LinkedMap!(int, int, false); 268 IntMap test2; 269 test2[0] = 1; 270 test2[1] = 1; 271 test2[2] = 1; 272 test2[3] = 1; 273 test2[4] = 1; 274 assertThrown!ElementNotFoundException(test2[8]); 275 } 276 //test FIFO behavior 277 { 278 alias IntMap = LinkedMap!(int, int, true, "a == b", true); 279 IntMap test3; 280 test3[0] = 0; 281 writeln(test3); 282 test3[1] = 1; 283 writeln(test3); 284 test3[2] = 2; 285 writeln(test3); 286 test3[3] = 3; 287 writeln(test3); 288 test3[4] = 4; 289 writeln(test3); 290 //overwriting key 3 should not distrupt the order 291 test3[3] = 5; 292 writeln(test3); 293 } 294 { 295 alias IntMap = LinkedMap!(int, int, true, "a == b", false); 296 IntMap test3; 297 test3[0] = 0; 298 writeln(test3); 299 test3[1] = 1; 300 writeln(test3); 301 test3[2] = 2; 302 writeln(test3); 303 test3[3] = 3; 304 writeln(test3); 305 test3[4] = 4; 306 writeln(test3); 307 //overwriting key 3 should put key 3 at the end 308 test3[3] = 5; 309 writeln(test3); 310 } 311 }