1 module collections.sortedlist; 2 3 import collections.commons; 4 import std.functional : binaryFun; 5 6 /** 7 * Implements a sorted list of type T. 8 * The container ensures that all of it's elements are ordered after any insertion. 9 * Has some optimization to stop searching after a given value has passed. 10 * `cmp` can set both the direction of the array, and what parameters should be tested. 11 * If `allowDuplicates` set false, the collection will act like a sorted set over an array, and won't allow any 12 * insertion of preexisting values. 13 */ 14 public struct SortedList(E, alias cmp = "a < b", bool allowDuplicates = true, alias equal = "a == b") { 15 private E[] _array; ///The array where the elements are stored. 16 private size_t begin; ///The position of the current front iteration. 17 private size_t end; ///The position of the current back iteration. 18 /** 19 * Constructs a sorted list out from an array. 20 */ 21 public this(E[] _array) @safe nothrow pure { 22 this._array.reserve = _array.length; 23 foreach (E key; _array) { 24 put(key); 25 } 26 assert(this._array.length == _array.length); 27 assert(this._array.length == end); 28 } 29 /** 30 * Constructs a sorted list out from a range. 31 */ 32 public this(Range)(Range src) { 33 foreach (E key; src) { 34 put(key); 35 } 36 //assert(this._array.length == _array.length); 37 assert(this._array.length == end); 38 } 39 /** 40 * Adds a new element while keeping the order intact. 41 * 42 * TO DO: Maybe even more optimizations? Maybe look where the element would fit, then shift that position? 43 */ 44 E put(E a) @safe nothrow pure { 45 static if(!allowDuplicates){ 46 if(has(a)) return E.init; 47 } 48 _array.length = _array.length + 1; 49 for(sizediff_t i = _array.length - 2 ; i >= 0 ; i--) { 50 E b = _array[i]; 51 if(binaryFun!cmp(a, b)) { //first position found 52 _array[i + 1] = a; 53 end++; 54 return a; 55 } else { 56 _array[i + 1] = b; 57 } 58 } 59 _array[0] = a; 60 end++; 61 return a; 62 } 63 /** 64 * Removes the n-th element while keeping the order intact. 65 * Returns the removed element. 66 */ 67 E remove(size_t n) @safe nothrow pure { 68 E result = _array[n]; 69 if(n != _array.length) { 70 for ( ; n < _array.length - 1 ; n++) { 71 _array[n] = _array[n + 1]; 72 } 73 } 74 _array.length = _array.length - 1; 75 end--; 76 return result; 77 } 78 static if(!allowDuplicates) { 79 /** 80 * Removes the element which is equal with the given one if the template is set to not allow duplicates. 81 * Returns the removed element, or E.init if not found. 82 */ 83 E removeByElem(E a) @safe nothrow pure { 84 foreach_reverse(i, b; _array) { 85 if(binaryFun!equal(a, b)) return this.remove(i); 86 else if(binaryFun!cmp(a, b)) break; 87 } 88 return E.init; 89 } 90 /** 91 * Removes the element which is equal with the given one if the template is set to not allow duplicates. 92 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal 93 * functions's overrides. 94 * Returns the removed element, or E.init if not found. 95 */ 96 E removeBy(T)(T a) @safe nothrow pure { 97 foreach_reverse(i, b; _array) { 98 if(binaryFun!equal(a, b)) return this.remove(i); 99 else if(binaryFun!cmp(a, b)) break; 100 } 101 return E.init; 102 } 103 /** 104 * Looks up value `a` in the list, then returns the element equal with it. Returns E.init if not found. 105 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal 106 * functions's overrides. 107 */ 108 E searchBy(T)(T a) @nogc @safe pure nothrow { 109 foreach_reverse(b; _array) { 110 if(binaryFun!equal(a, b)) return b; 111 else if(binaryFun!cmp(a, b)) break; 112 } 113 return E.init; 114 } 115 /** 116 * Looks up value `a` in the list, then returns a reference to the element equal with it. Throws an exception 117 * if not found. 118 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal 119 * functions's overrides. 120 */ 121 E searchByRef(T)(T a) @safe pure { 122 foreach_reverse(ref E b; _array) { 123 if(binaryFun!equal(a, b)) return b; 124 else if(binaryFun!cmp(a, b)) break; 125 } 126 throw new ElementNotFoundException("Element not found!"); 127 } 128 /** 129 * Looks up value `a` in the list, then returns the element equal with it. Returns null if not found. 130 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal 131 * functions's overrides. 132 */ 133 E* searchByPtr(T)(T a) @nogc pure nothrow { 134 foreach_reverse(ref E b; _array) { 135 if(binaryFun!equal(a, b)) return &b; 136 else if(binaryFun!cmp(a, b)) break; 137 } 138 return null; 139 } 140 /** 141 * Returns whether the set has the given element. 142 */ 143 bool has(const E a) @nogc @safe nothrow pure const { 144 foreach_reverse(b; _array) { 145 if(binaryFun!equal(a, b)) return true; 146 else if(binaryFun!cmp(a, b)) break; 147 } 148 return false; 149 } 150 /** 151 * Returns whether the set has the given element. 152 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal 153 * functions's overrides. 154 */ 155 bool has(T)(const T a) @nogc @safe nothrow pure const { 156 foreach_reverse(b; _array) { 157 if(binaryFun!equal(a, b)) return true; 158 else if(binaryFun!cmp(a, b)) break; 159 } 160 return false; 161 } 162 auto opBinaryRight(string op, L)(const L lhs) const { 163 static if (op == "in") { 164 return has(lhs); 165 } else static assert(0, "Operator not supported!"); 166 } 167 /** 168 * Returns the amount of elements found in the set. 169 */ 170 size_t hasRange(R)(R range) @nogc @safe pure nothrow { 171 size_t result; 172 foreach (key; range) { 173 if(has(key)) result++; 174 } 175 return result; 176 } 177 /** 178 * Returns the index of the given element, or throws an ElementNotFoundException if not found. 179 */ 180 size_t which(E a) @safe pure { 181 foreach_reverse(i, b; _array) { 182 if(binaryFun!equal(a, b)) return i; 183 else if(binaryFun!cmp(a, b)) break; 184 } 185 throw new ElementNotFoundException("Element not found!"); 186 } 187 /** 188 * Returns a slice from the list, but the slicing is done by element. 189 * Search is done in a way that if either cmp or equals is true to an element, its position will be chosen 190 * for the slice. 191 */ 192 SortedList!(E, cmp, allowDuplicates, equal) sliceByElem(E from, E to) @safe pure { 193 size_t f, t = _array.length; 194 E a = from; 195 foreach_reverse(size_t i ,E b; _array) { 196 if(binaryFun!cmp(a, b) || binaryFun!equal(a, b)){ 197 f = i; 198 break; 199 } 200 } 201 a = to; 202 foreach_reverse(size_t i ,E b; _array) { 203 if(binaryFun!cmp(a, b) || binaryFun!equal(a, b)){ 204 t = i; 205 break; 206 } 207 } 208 return opSlice(f, t); 209 } 210 /** 211 * Set operators. 212 * Enables math operations on sets, like unions and intersections. 213 * Could work on ranges in general as long as they implement some basic functions, like iteration. 214 */ 215 SortedList!(E, cmp, allowDuplicates, equal) opBinary(string op, R)(R rhs) { 216 static if(op == "|" || op == "~") {//Union 217 SortedList!(E, cmp, allowDuplicates, equal) result; 218 result.end = this.end; 219 result._array = this._array.dup; 220 foreach(e ; rhs){ 221 result.put(e); 222 } 223 return result; 224 } else static if(op == "&" || op == "*") {//Intersection 225 SortedList!(E, cmp, allowDuplicates, equal) result; 226 foreach(e ; rhs){ 227 if(this.has(e)) result.put(e); 228 } 229 return result; 230 } else static if(op == "-" || op == "/") {//Complement 231 SortedList!(E, cmp, allowDuplicates, equal) result = SortedList!(E, cmp, allowDuplicates, equal)(this); 232 foreach(e ; rhs){ 233 result.removeByElem(e); 234 } 235 return result; 236 } else static if(op == "^"){//Difference 237 SortedList!(E, cmp, allowDuplicates, equal) result = this | rhs; 238 SortedList!(E, cmp, allowDuplicates, equal) common = this & rhs; 239 foreach(e ; common){ 240 result.removeByElem(e); 241 } 242 return result; 243 } else static assert(0, "Operator " ~ op ~ "not supported"); 244 } 245 /** 246 * Set operators. 247 */ 248 SortedList!(E, cmp, allowDuplicates, equal) opOpAssign(string op)(E value) { 249 static if(op == "~=") {//Append 250 put(value); 251 } else static if(op == "-=" || op == "/=") { 252 removeByElem(value); 253 } else static assert(0, "Operator " ~ op ~ "not supported"); 254 return this; 255 } 256 /** 257 * Set operators. 258 */ 259 SortedList!(E, cmp, allowDuplicates, equal) opOpAssign(string op, R)(R range) { 260 static if(op == "~=" || op == "|=") {//Append 261 foreach(val; range) 262 put(val); 263 } else static if(op == "-=" || op == "/=") { 264 foreach(val; range) 265 removeByElem(val); 266 } else static assert(0, "Operator " ~ op ~ "not supported"); 267 return this; 268 } 269 } 270 /** 271 * Returns a copy of this struct. 272 */ 273 @property auto save() @nogc @safe nothrow pure { 274 return this; 275 } 276 /** 277 * Returns the element at the front. 278 */ 279 @property E front() @nogc @safe nothrow pure { 280 return _array[begin]; 281 } 282 /** 283 * Returns the element at the front. 284 * Note: This is recommended for elements ordered by a key, which is not modified through this function. Failure of 285 * doing so will ruin the sortedness of the array. 286 */ 287 @property ref E frontRef() @nogc @safe nothrow pure { 288 return _array[begin]; 289 } 290 /** 291 * Returns the element at the back. 292 */ 293 @property E back() @nogc @safe nothrow pure { 294 return _array[end - 1]; 295 } 296 /** 297 * Returns the element at the back. 298 * Note: This is recommended for elements ordered by a key, which is not modified through this function. Failure of 299 * doing so will ruin the sortedness of the array. 300 */ 301 @property ref E backRef() @nogc @safe nothrow pure { 302 return _array[end - 1]; 303 } 304 /** 305 * Returns the element at begin and increments the position by one. 306 */ 307 E moveFront() @nogc @safe nothrow pure { 308 E result = _array[begin]; 309 popFront(); 310 return result; 311 } 312 /** 313 * Increments the front iteration position by one 314 */ 315 void popFront() @nogc @safe nothrow pure { 316 if(begin < end) begin++; 317 } 318 /** 319 * Decrements the back iteration position by one 320 */ 321 void popBack() @nogc @safe nothrow pure { 322 if(begin < end) end--; 323 } 324 /** 325 * Returns true when the end of the list have been reached. 326 */ 327 @property bool empty() @nogc @safe nothrow pure { 328 return begin == end; 329 } 330 /** 331 * Returns the n-th element. 332 */ 333 E opIndex(size_t n) @nogc @safe nothrow pure { 334 return _array[n]; 335 } 336 /** 337 * Moves to the n-th position and returns the element of that position. 338 */ 339 E moveAt(size_t n) @nogc @safe nothrow pure { 340 begin = n; 341 return _array[begin]; 342 } 343 /** 344 * Returns the length of the list. 345 */ 346 @property size_t length() @nogc @safe nothrow pure { 347 return _array.length; 348 } 349 alias opDollar = length; 350 /** 351 * Sets the reserve of the underlying array and returns the current reserve. 352 */ 353 @property size_t reserve(size_t amount) @safe pure nothrow { 354 return _array.reserve(amount); 355 } 356 /** 357 * Returns a slice from the list. 358 */ 359 SortedList!(E, cmp, allowDuplicates, equal) opSlice(size_t i0, size_t i1) @safe nothrow pure { 360 return SortedList!(E, cmp, allowDuplicates, equal)(_array[i0..i1]); 361 } 362 /** 363 * Returns a copy of the underlying array. 364 */ 365 @property const(E)[] arrayOf() @safe nothrow pure const { 366 const(E)[] result; 367 result.reserve = _array.length; 368 foreach (const E key; _array) { 369 result ~= key; 370 } 371 return result; 372 } 373 374 375 string toString() { 376 import std.conv : to; 377 return to!string(_array); 378 } 379 } 380 381 @safe unittest { 382 import std.stdio : writeln; 383 alias SortedIntList = SortedList!(int, "a < b", true); 384 alias SortedIntSet = SortedList!(int, "a < b", false); 385 SortedIntList sil; 386 sil.put(5); 387 assert(sil.arrayOf == [5], sil.toString); 388 sil.put(3); 389 assert(sil.arrayOf == [5, 3], sil.toString); 390 sil.put(7); 391 assert(sil.arrayOf == [7, 5, 3], sil.toString); 392 sil.put(-1); 393 assert(sil.arrayOf == [7, 5, 3, -1], sil.toString); 394 sil.remove(2); 395 assert(sil.arrayOf == [7, 5, -1], sil.toString); 396 sil.put(2); 397 assert(sil.arrayOf == [7 ,5, 2, -1], sil.toString); 398 SortedIntSet sis; 399 sis.put(5); 400 assert(sis.arrayOf == [5], sis.toString); 401 sis.put(5); 402 assert(sis.arrayOf == [5], sis.toString); 403 sis.put(3); 404 assert(sis.arrayOf == [5, 3], sis.toString); 405 sis.put(3); 406 assert(sis.arrayOf == [5, 3], sis.toString); 407 sis.put(7); 408 assert(sis.arrayOf == [7, 5, 3], sis.toString); 409 sis.put(7); 410 assert(sis.arrayOf == [7, 5, 3], sis.toString); 411 sis.put(-2); 412 assert(sis.arrayOf == [7, 5, 3, -2], sis.toString); 413 sis.put(11); 414 assert(sis.arrayOf == [11, 7, 5, 3, -2], sis.toString); 415 assert(!sis.has(12), sis.toString); 416 assert(sis.has(11), sis.toString); 417 sis.remove(0); 418 assert(!sis.has(11), sis.toString); 419 assert(sis.arrayOf == [7, 5, 3, -2], sis.toString); 420 sis.put(1); 421 assert(sis.arrayOf == [7, 5, 3, 1, -2], sis.toString); 422 sis.put(1); 423 assert(sis.arrayOf == [7, 5, 3, 1, -2], sis.toString); 424 foreach(e; sil) { 425 writeln(e); 426 } 427 foreach(e; sis) { 428 writeln(e); 429 } 430 SortedIntList a = SortedIntList([0]); 431 a.remove(0); 432 assert(a.length == 0); 433 } 434 435 @safe unittest { 436 import std.stdio : writeln; 437 alias SortedIntList = SortedList!(int, "a > b", true); 438 alias SortedIntSet = SortedList!(int, "a > b", false); 439 SortedIntList sil; 440 sil.put(5); 441 assert(sil.arrayOf == [5], sil.toString); 442 sil.put(3); 443 assert(sil.arrayOf == [3, 5], sil.toString); 444 sil.put(7); 445 assert(sil.arrayOf == [3, 5, 7], sil.toString); 446 sil.put(-1); 447 assert(sil.arrayOf == [-1, 3, 5, 7], sil.toString); 448 sil.remove(2); 449 assert(sil.arrayOf == [-1, 3, 7], sil.toString); 450 sil.put(2); 451 assert(sil.arrayOf == [-1,2, 3, 7], sil.toString); 452 SortedIntSet sis; 453 sis.put(5); 454 assert(sis.arrayOf == [5], sis.toString); 455 sis.put(5); 456 assert(sis.arrayOf == [5], sis.toString); 457 sis.put(3); 458 assert(sis.arrayOf == [3, 5], sis.toString); 459 sis.put(3); 460 assert(sis.arrayOf == [3, 5], sis.toString); 461 sis.put(7); 462 assert(sis.arrayOf == [3, 5, 7], sis.toString); 463 sis.put(7); 464 assert(sis.arrayOf == [3, 5, 7], sis.toString); 465 sis.put(-2); 466 assert(sis.arrayOf == [-2, 3, 5, 7], sis.toString); 467 sis.put(11); 468 assert(sis.arrayOf == [-2, 3, 5, 7, 11], sis.toString); 469 assert(!sis.has(12), sis.toString); 470 assert(sis.has(11), sis.toString); 471 sis.remove(0); 472 assert(!sis.has(-2), sis.toString); 473 assert(sis.arrayOf == [3, 5, 7, 11], sis.toString); 474 sis.put(1); 475 assert(sis.arrayOf == [1, 3, 5, 7, 11], sis.toString); 476 sis.put(1); 477 assert(sis.arrayOf == [1, 3, 5, 7, 11], sis.toString); 478 foreach(e; sil) { 479 writeln(e); 480 } 481 foreach(e; sis) { 482 writeln(e); 483 } 484 } 485 486 unittest { 487 //test set operators 488 alias IntSet = SortedList!(int, "a > b", false, "a == b"); 489 IntSet a = IntSet([1, 3, 5, 7, 9]), b = IntSet([1, 5, 9]), c = IntSet([3, 7]); 490 IntSet union_ab = a | b, union_ac = a | c, union_bc = b | c; 491 IntSet intrsctn_ab = a & b, intrsctn_ac = a & c; 492 IntSet cmplmnt_ab = a - b, cmplmnt_ac = a - c; 493 IntSet diff_ab = a ^ b, diff_ac = a ^ c, diff_bc = b ^ c; 494 assert(union_ab.hasRange([1, 3, 5, 7, 9]) == 5); 495 assert(union_ac.hasRange([1, 3, 5, 7, 9]) == 5); 496 assert(union_bc.hasRange([1, 3, 5, 7, 9]) == 5); 497 assert(intrsctn_ab.hasRange([1, 5, 9]) == 3); 498 assert(intrsctn_ac.hasRange([3, 7]) == 2); 499 assert(cmplmnt_ab.hasRange([3, 7]) == 2); 500 assert(cmplmnt_ac.hasRange([1, 5, 9]) == 3); 501 assert(diff_ab.hasRange([3, 7]) == 2); 502 assert(diff_ac.hasRange([1, 5, 9]) == 3); 503 assert(diff_bc.hasRange([1, 3, 5, 7, 9]) == 5); 504 assert(5 in diff_bc); 505 } 506 507 //test key functions 508 unittest { 509 import std.exception; 510 import std.conv : to; 511 alias TestSet = SortedList!(TestStructWithKey, "a > b", false, "a == b"); 512 TestSet a; 513 a.put(TestStructWithKey(0, null, null)); 514 a.put(TestStructWithKey(1, null, null)); 515 a.put(TestStructWithKey(4, null, null)); 516 assert(a.has(0), a.arrayOf.to!string); 517 assert(a.has(1), a.arrayOf.to!string); 518 assert(!a.has(2), a.arrayOf.to!string); 519 assert(!a.has(3), a.arrayOf.to!string); 520 assert(a.has(4), a.arrayOf.to!string); 521 assert(a.searchBy(4).key == 4, a.arrayOf.to!string); 522 assert(a.searchByPtr(3) == null, a.arrayOf.to!string); 523 assertThrown(a.searchByRef(5)); 524 assert(a.removeBy(4).key == 4, a.arrayOf.to!string); 525 assert(!a.has(4), a.arrayOf.to!string); 526 }