1 /******************************************************************************* 2 3 Serializable data structure that maps Range!(hash_t) keys 4 to corresponding values 5 6 This has been designed to work with the (de)serialization functionality 7 in ocean.util.serialize.contiguous 8 9 Copyright: 10 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 11 All rights reserved. 12 13 License: 14 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 15 Alternatively, this file may be distributed under the terms of the Tango 16 3-Clause BSD License (see LICENSE_BSD.txt for details). 17 18 *******************************************************************************/ 19 20 module ocean.util.container.HashRangeMap; 21 22 23 24 import ocean.core.Enforce; 25 import ocean.math.Range; 26 27 import ocean.meta.types.Qualifiers; 28 29 version (unittest) 30 { 31 import ocean.core.Test; 32 } 33 34 35 /******************************************************************************* 36 37 Helper alias for range of hash_t 38 39 *******************************************************************************/ 40 41 public alias Range!(hash_t) HashRange; 42 43 44 /******************************************************************************* 45 46 Provides a mapping from HashRange to the specified type 47 48 Note: Unittests for `put`, `remove` and `opopBinaryRight!"in"` are not 49 placed directly in this struct as they depend on the assumption that type 50 `Value` (the template argument) has a meaningful equality operator 51 (opEquals). Instead, private external functions exist to test these methods. 52 These are then called on HashRangeMaps with various different types of 53 Value, in a unittest block outside the struct. 54 55 Params: 56 Value = type to store in values of map 57 58 *******************************************************************************/ 59 60 public struct HashRangeMap ( Value ) 61 { 62 import ocean.core.Array; 63 64 65 /*************************************************************************** 66 67 Array of HashRange that should be sorted in ascending order 68 at all times. 69 70 It always has the same length as values (see below), 71 also to each ranges[i] corresponds to values[i] 72 73 Note: the design with two separate arrays (ranges and values) was 74 chosen in order to allow easy use of methods from ocean.math.Range 75 (e.g. `hasGap`). 76 77 ***************************************************************************/ 78 79 private HashRange[] ranges; 80 81 82 /*************************************************************************** 83 84 Array of Value that should corresponds to range (see above) 85 86 ***************************************************************************/ 87 88 private Value[] values; 89 90 91 invariant() 92 { 93 assert(this.ranges.length == this.values.length, 94 "HashRangeMap: length mismatch between ranges and values"); 95 } 96 97 98 /*************************************************************************** 99 100 Tells whether the HashRangeMap is empty. 101 102 Returns: 103 true if the HashRangeMap is empty 104 105 ***************************************************************************/ 106 107 public bool empty ( ) 108 { 109 return this.length == 0; 110 } 111 112 unittest 113 { 114 // In order to make notation shorter 115 alias HashRange R; 116 117 { 118 HashRangeMap hrm; 119 120 test(hrm.empty, "HashRangeMap with no data should be reported as empty"); 121 } 122 123 { 124 HashRangeMap hrm; 125 hrm.ranges = [R(1, 2), R(3, 15), R(10, 12)]; 126 hrm.values = [Value.init, Value.init, Value.init]; 127 128 test(!hrm.empty, "HashRangeMap with data can't be reported as empty"); 129 } 130 } 131 132 133 /*************************************************************************** 134 135 Returns: 136 number of range-value pairs stored in the HashRangeMap 137 138 ***************************************************************************/ 139 140 public size_t length ( ) 141 { 142 return this.ranges.length; 143 } 144 145 unittest 146 { 147 // In order to make notation shorter 148 alias HashRange R; 149 150 { 151 HashRangeMap hrm; 152 153 test!("==")(hrm.length, 0); 154 } 155 156 { 157 HashRangeMap hrm; 158 hrm.ranges = [R(1, 2), R(3, 15), R(10, 12)]; 159 hrm.values = [Value.init, Value.init, Value.init]; 160 161 test!("==")(hrm.length, 3); 162 } 163 } 164 165 166 /*************************************************************************** 167 168 Looks up the mapping for non-empty range or adds one if not found 169 170 Params: 171 range = HashRange to look up or add mapping for; should be non-empty 172 added = set to true if the mapping did not exist but was added 173 174 Returns: 175 the pointer to value mapped to by the specified range. If output 176 value `added` is true, the value is unspecified and the caller 177 should set the value as desired. 178 179 Out: 180 The returned pointer is never null. 181 182 ***************************************************************************/ 183 184 public Value* put ( HashRange range, out bool added ) 185 out (result) 186 { 187 assert(result !is null); 188 } 189 do 190 { 191 enforce(!range.is_empty, "An empty range can't be put in HashRangeMap"); 192 193 size_t insert_place; 194 added = !bsearch(this.ranges, range, insert_place); 195 196 if (added) 197 { 198 insertShift(this.ranges, insert_place); 199 this.ranges[insert_place] = range; 200 insertShift(this.values, insert_place); 201 } 202 203 return &this.values[insert_place]; 204 } 205 206 207 /*************************************************************************** 208 209 Removes the mapping for the specified range 210 211 Params: 212 range = HashRange to remove mapping for 213 214 Returns: 215 true if range was found in the map or false if not 216 217 ***************************************************************************/ 218 219 public bool remove ( HashRange range ) 220 { 221 size_t remove_place; 222 bool result = bsearch(this.ranges, range, remove_place); 223 224 if (result) 225 { 226 removeShift(this.ranges, remove_place); 227 removeShift(this.values, remove_place); 228 } 229 230 return result; 231 } 232 233 234 /*************************************************************************** 235 236 Clear entirely the HashRangeMap 237 238 ***************************************************************************/ 239 240 public void clear () 241 { 242 this.ranges.length = 0; 243 assumeSafeAppend(this.ranges); 244 245 this.values.length = 0; 246 assumeSafeAppend(this.values); 247 } 248 249 unittest 250 { 251 // In order to make notation shorter 252 alias HashRange R; 253 254 HashRangeMap hrm; 255 hrm.ranges = [R(1, 2), R(3, 15), R(10, 12)]; 256 hrm.values = [Value.init, Value.init, Value.init]; 257 258 hrm.clear(); 259 test!("==")(hrm.ranges.length, 0); 260 test!("==")(hrm.values.length, 0); 261 } 262 263 264 /*************************************************************************** 265 266 'in' operator: looks up the value mapped by a given HashRange 267 268 Params: 269 range = hash range to check 270 271 Returns: 272 pointer to the value mapped by range, or null if range is 273 not in the HashRangeMap 274 275 ***************************************************************************/ 276 277 public Value* opBinaryRight (string op : "in") ( HashRange range ) 278 { 279 size_t insert_place; 280 if (!bsearch(this.ranges, range, insert_place)) 281 return null; 282 283 return &this.values[insert_place]; 284 } 285 286 287 /*************************************************************************** 288 289 foreach iterator over ranges and corresponding values. This iterator 290 prevents true ref iteration over the keys of the internal map 291 by passing a copy of the range to the iteration delegate. 292 293 ***************************************************************************/ 294 295 public int opApply ( scope int delegate ( ref HashRange r, ref Value v ) dg ) 296 { 297 int result = 0; 298 foreach (i, range; this.ranges) 299 { 300 result = dg(range, this.values[i]); 301 302 if(result) 303 break; 304 } 305 306 return result; 307 } 308 309 310 /*************************************************************************** 311 312 Check if the hash ranges in the map have neither gaps nor overlaps and 313 cover the whole space of hash_t values. 314 315 Returns: 316 true if there are no gaps and overlaps, and the whole hash_t values 317 are covered with the ranges in map, 318 false otherwise 319 320 ***************************************************************************/ 321 322 public bool isTessellated () 323 { 324 return HashRange(hash_t.min, hash_t.max).isTessellatedBy(this.ranges); 325 } 326 327 unittest 328 { 329 alias HashRange.makeRange makeRange; 330 331 // tesselation 332 { 333 HashRangeMap hrm; 334 hrm.ranges = [makeRange!("[)")(0, 300), 335 makeRange!("[)")(300, 7773), 336 makeRange!("[)")(7773, 169144), 337 makeRange!("[]")(169144, hash_t.max)]; 338 hrm.values = [Value.init, Value.init, Value.init, Value.init]; 339 test(hrm.isTessellated(), 340 "tessellation of hash_t should form tessellated HashRangeMap"); 341 } 342 343 // overlap 344 { 345 HashRangeMap hrm; 346 hrm.ranges = [makeRange!("[)")(0, 300), 347 makeRange!("[]")(300, 7773), 348 makeRange!("[)")(7773, 169144), 349 makeRange!("[]")(169144, hash_t.max)]; 350 hrm.values = [Value.init, Value.init, Value.init, Value.init]; 351 test(!hrm.isTessellated(), 352 "HashRangeMap with overlap in ranges haven't tessellation"); 353 } 354 355 // gap 356 { 357 HashRangeMap hrm; 358 hrm.ranges = [makeRange!("[)")(0, 300), 359 makeRange!("[)")(300, 7773), 360 makeRange!("()")(7773, 169144), 361 makeRange!("[]")(169144, hash_t.max)]; 362 hrm.values = [Value.init, Value.init, Value.init, Value.init]; 363 test(!hrm.isTessellated(), 364 "HashRangeMap with gap in ranges haven't tessellation"); 365 } 366 367 // no coverage 368 { 369 HashRangeMap hrm; 370 hrm.ranges = [makeRange!("[)")(20, 300), 371 makeRange!("[)")(300, 7773), 372 makeRange!("[)")(7773, 169144), 373 makeRange!("[]")(169144, hash_t.max)]; 374 hrm.values = [Value.init, Value.init, Value.init, Value.init]; 375 test(!hrm.isTessellated(), 376 "HashRangeMap without coverage the whole hash_t haven't tessellation"); 377 } 378 379 { 380 HashRangeMap hrm; 381 hrm.ranges = [makeRange!("[)")(0, 300), 382 makeRange!("[)")(300, 7773), 383 makeRange!("[)")(7773, 169144), 384 makeRange!("[]")(169144, hash_t.max - 34)]; 385 hrm.values = [Value.init, Value.init, Value.init, Value.init]; 386 test(!hrm.isTessellated(), 387 "HashRangeMap without coverage the whole hash_t haven't tessellation"); 388 } 389 } 390 391 392 /*************************************************************************** 393 394 Check if the hash ranges in the map have any gaps between them or 395 boundaries of hash_t type. 396 397 Returns: 398 true if any gaps exist between the ranges in the map, 399 false otherwise 400 401 ***************************************************************************/ 402 403 public bool hasGap () 404 { 405 return extent(this.ranges) != HashRange(hash_t.min, hash_t.max) 406 || ocean.math.Range.hasGap(this.ranges); 407 } 408 409 unittest 410 { 411 // In order to make notation shorter 412 alias HashRange R; 413 414 // gap 415 { 416 HashRangeMap hrm; 417 hrm.ranges = [R(hash_t.min, 2), R(3, 15), R(20, hash_t.max)]; 418 hrm.values = [Value.init, Value.init, Value.init]; 419 test(hrm.hasGap(), "This HashRangeMap has gap"); 420 } 421 422 // no coverage 423 { 424 HashRangeMap hrm; 425 hrm.ranges = [R(1, 2), R(3, 10), R(11, hash_t.max)]; 426 hrm.values = [Value.init, Value.init, Value.init]; 427 test(hrm.hasGap(), "This HashRangeMap has gap"); 428 } 429 430 // no coverage 431 { 432 HashRangeMap hrm; 433 hrm.ranges = [R(hash_t.min, 2), R(3, 10), R(11, 40)]; 434 hrm.values = [Value.init, Value.init, Value.init]; 435 test(hrm.hasGap(), "This HashRangeMap has gap"); 436 } 437 438 // overlap 439 { 440 HashRangeMap hrm; 441 hrm.ranges = [R(hash_t.min, 2), R(3, 15), R(10, hash_t.max)]; 442 hrm.values = [Value.init, Value.init, Value.init]; 443 test(!hrm.hasGap(), "This HashRangeMap shouldn't have gaps"); 444 } 445 446 // contiguous 447 { 448 HashRangeMap hrm; 449 hrm.ranges = [R(hash_t.min, 2), R(3, 15), R(16, hash_t.max)]; 450 hrm.values = [Value.init, Value.init, Value.init]; 451 test(!hrm.hasGap(), "This HashRangeMap shouldn't have gaps"); 452 } 453 } 454 455 456 /*************************************************************************** 457 458 Check if there is any overlap between the hash ranges in the map 459 460 Returns: 461 true if at least one pair of ranges in the map overlap, 462 false otherwise 463 464 ***************************************************************************/ 465 466 public bool hasOverlap () 467 { 468 return ocean.math.Range.hasOverlap(this.ranges); 469 } 470 471 unittest 472 { 473 // In order to make notation shorter 474 alias HashRange R; 475 476 // gap 477 { 478 HashRangeMap hrm; 479 hrm.ranges = [R(1, 2), R(3, 15), R(20, 27)]; 480 hrm.values = [Value.init, Value.init, Value.init]; 481 test(!hrm.hasOverlap(), "This HashRangeMap shouldn't have overlaps"); 482 } 483 484 // overlap 485 { 486 HashRangeMap hrm; 487 hrm.ranges = [R(1, 2), R(3, 15), R(10, 12)]; 488 hrm.values = [Value.init, Value.init, Value.init]; 489 test(hrm.hasOverlap(), "This HashRangeMap has overlap"); 490 } 491 492 // contiguous 493 { 494 HashRangeMap hrm; 495 hrm.ranges = [R(1, 2), R(3, 15), R(16, 21)]; 496 hrm.values = [Value.init, Value.init, Value.init]; 497 test(!hrm.hasOverlap(), "This HashRangeMap shouldn't have overlaps"); 498 } 499 } 500 } 501 502 503 /******************************************************************************* 504 505 test instantiation with int 506 507 *******************************************************************************/ 508 509 unittest 510 { 511 HashRangeMap!(int) ihrm; 512 513 testPut([1, 2, 3, 4, 5, 6, 7, 8][]); 514 testRemove([1, 2, 3, 4, 5][]); 515 testOpInR([1, 2, 3, 4, 5][]); 516 testOpApply([1, 2, 3, 4, 5][]); 517 } 518 519 520 /******************************************************************************* 521 522 test instantiation with ulong 523 524 *******************************************************************************/ 525 526 unittest 527 { 528 HashRangeMap!(ulong) uhrm; 529 530 testPut([1UL, 2UL, 3UL, 4UL, 5UL, 6UL, 7UL, 8UL]); 531 testRemove([1UL, 2UL, 3UL, 4UL, 5UL]); 532 testOpInR([1UL, 2UL, 3UL, 4UL, 5UL]); 533 testOpApply([1UL, 2UL, 3UL, 4UL, 5UL]); 534 } 535 536 537 /******************************************************************************* 538 539 test instantiation with float 540 541 *******************************************************************************/ 542 543 unittest 544 { 545 HashRangeMap!(float) fhrm; 546 547 testPut([1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 7.0f, 8.0f]); 548 testRemove([1.0f, 2.0f, 3.0f, 4.0f, 5.0f]); 549 testOpInR([1.0f, 2.0f, 3.0f, 4.0f, 5.0f]); 550 testOpApply([1.0f, 2.0f, 3.0f, 4.0f, 5.0f]); 551 } 552 553 554 /******************************************************************************* 555 556 test instantiation with pointer 557 558 *******************************************************************************/ 559 560 unittest 561 { 562 int v1, v2, v3, v4, v5, v6, v7, v8; 563 HashRangeMap!(int*) phrm; 564 565 testPut([&v1, &v2, &v3, &v4, &v5, &v6, &v7, &v8]); 566 testRemove([&v1, &v2, &v3, &v4, &v5]); 567 testOpInR([&v1, &v2, &v3, &v4, &v5]); 568 testOpApply([&v1, &v2, &v3, &v4, &v5]); 569 } 570 571 572 /******************************************************************************* 573 574 test instantiation with arbitrary struct that supports `opEquals` 575 576 *******************************************************************************/ 577 578 unittest 579 { 580 static struct S 581 { 582 import ocean.util.Convert; 583 584 int x; 585 586 static S opCall(int x) 587 { 588 S s; 589 s.x = x; 590 return s; 591 } 592 593 equals_t opEquals(S other) 594 { 595 return this.x == other.x; 596 } 597 598 istring toString() 599 { 600 return "S(" ~ to!(istring)(this.x) ~ ")"; 601 } 602 } 603 604 HashRangeMap!(S) shrm; 605 606 testPut([S(1), S(2), S(3), S(4), S(5), S(6), S(7), S(8)]); 607 testRemove([S(1), S(2), S(3), S(4), S(5)]); 608 testOpInR([S(1), S(2), S(3), S(4), S(5)]); 609 testOpApply([S(1), S(2), S(3), S(4), S(5)]); 610 } 611 612 613 /******************************************************************************* 614 615 test instantiation with array 616 617 *******************************************************************************/ 618 619 unittest 620 { 621 HashRangeMap!(int[]) arhrm; 622 623 testPut([[1], [2, 1], [3, 1, 2], [4], [5], [6], [7], [8]]); 624 testRemove([[1], [2, 1], [3, 1, 2], [4], [5]]); 625 testOpInR([[1], [2, 1], [3, 1, 2], [4], [5]]); 626 testOpApply([[1], [2, 1], [3, 1, 2], [4], [5]]); 627 } 628 629 630 version (unittest) 631 { 632 import ocean.meta.traits.Basic; 633 import ocean.meta.types.Arrays; 634 import ocean.core.Verify; 635 636 private template hasAtomicEquality ( T ) 637 { 638 static if (is(T == struct) || is(T == class) || is(T == interface)) 639 { 640 static immutable hasAtomicEquality = is(typeof(T.opEquals)); 641 } 642 else 643 { 644 static immutable hasAtomicEquality = isPrimitiveType!(T) || isPointerType!(T); 645 } 646 } 647 648 649 private template hasEquality ( T ) 650 { 651 static if (isArrayType!(T)) 652 { 653 static immutable hasEquality = hasAtomicEquality!(StripAllArrays!(T)); 654 } 655 else 656 { 657 static immutable hasEquality = hasAtomicEquality!(T); 658 } 659 } 660 661 662 // Unittest function for put(). 663 private void testPut (Value) ( Value[] v ) 664 { 665 verify(v.length == 8, "You should provide an array of 8 different values"); 666 static assert(hasEquality!(Value), 667 "Value has to support equality check to run this test function"); 668 // In order to make notation shorter 669 alias HashRange R; 670 671 HashRangeMap!(Value) hrm; 672 bool added; 673 Value* ret; 674 675 // impossible to add an empty range 676 testThrown!(Exception)(hrm.put(R.init, added)); 677 678 // first addition 679 *(ret = hrm.put(R(3, 15), added)) = v[0]; 680 test!("==")(*ret, v[0]); 681 test(added, "This case should rise added flag"); 682 test!("==")(hrm.ranges, 683 [R(3, 15)][]); 684 test!("==")(hrm.values, [v[0]][]); 685 686 // addition to the end 687 *(ret = hrm.put(R(19, 25), added)) = v[1]; 688 test!("==")(*ret, v[1]); 689 test(added, "This case should rise added flag"); 690 test!("==")(hrm.ranges, 691 [R(3, 15), R(19, 25)][]); 692 test!("==")(hrm.values, [v[0], v[1]][]); 693 694 // addition to the middle 695 *(ret = hrm.put(R(16, 18), added)) = v[2]; 696 test!("==")(*ret, v[2]); 697 test(added, "This case should rise added flag"); 698 test!("==")(hrm.ranges, 699 [R(3, 15), R(16, 18), R(19, 25)][]); 700 test!("==")(hrm.values, [v[0], v[2], v[1]][]); 701 702 // addition to the middle; min of new HashRange is within existing range 703 *(ret = hrm.put(R(10, 20), added)) = v[3]; 704 test!("==")(*ret, v[3]); 705 test(added, "This case should rise added flag"); 706 test!("==")(hrm.ranges, 707 [R(3, 15), R(10, 20), R(16, 18), R(19, 25)][]); 708 test!("==")(hrm.values, [v[0], v[3], v[2], v[1]][]); 709 710 // addition to the middle; min of new HashRange is the same with one 711 // of the range 712 *(ret = hrm.put(R(10, 12), added)) = v[4]; 713 test!("==")(*ret, v[4]); 714 test(added, "This case should rise added flag"); 715 test!("==")(hrm.ranges, 716 [R(3, 15), R(10, 12), R(10, 20), R(16, 18), R(19, 25)][]); 717 test!("==")(hrm.values, [v[0], v[4], v[3], v[2], v[1]][]); 718 719 // added existing range 720 *(ret = hrm.put(R(10, 12), added)) = v[5]; 721 test!("==")(*ret, v[5]); 722 test(!added, "In this case a range already exists"); 723 test!("==")(hrm.ranges, 724 [R(3, 15), R(10, 12), R(10, 20), R(16, 18), R(19, 25)][]); 725 test!("==")(hrm.values, [v[0], v[5], v[3], v[2], v[1]][]); 726 727 // addition to the begin 728 *(ret = hrm.put(R(1, 2), added)) = v[6]; 729 test!("==")(*ret, v[6]); 730 test(added, "This case should rise added flag"); 731 test!("==")(hrm.ranges, 732 [R(1, 2), R(3, 15), R(10, 12), R(10, 20), R(16, 18), R(19, 25)][]); 733 test!("==")(hrm.values, [v[6], v[0], v[5], v[3], v[2], v[1]][]); 734 735 // addition to the end with gap 736 *(ret = hrm.put(R(30, 33), added)) = v[7]; 737 test!("==")(*ret, v[7]); 738 test(added, "This case should rise added flag"); 739 test!("==")(hrm.ranges, 740 [R(1, 2), R(3, 15), R(10, 12), R(10, 20), R(16, 18), R(19, 25), R(30, 33)][]); 741 test!("==")(hrm.values, [v[6], v[0], v[5], v[3], v[2], v[1], v[7]][]); 742 } 743 744 private void testOpApply ( Value ) ( Value[] values) 745 { 746 alias HashRange R; 747 748 auto ranges = [R(1, 2), R(3, 15), R(10, 12), R(10, 20), R(16, 18)]; 749 750 HashRangeMap!(Value) hrm; 751 hrm.ranges = ranges.dup; 752 hrm.values = values.dup; 753 754 uint i = 0; 755 756 foreach (r, v; hrm) 757 { 758 test!("==")(r, ranges[i]); 759 test!("==")(v, values[i]); 760 ++i; 761 } 762 } 763 764 // Unittest function for remove(). 765 private void testRemove ( Value ) ( Value[] v) 766 { 767 verify(v.length == 5, "You should provide an array of 5 different values"); 768 static assert(hasEquality!(Value), 769 "Value has to support equality check to run this test function"); 770 771 // In order to make notation shorter 772 alias HashRange R; 773 774 HashRangeMap!(Value) hrm; 775 hrm.ranges = [R(1, 2), R(3, 15), R(10, 12), R(10, 20), R(16, 18)]; 776 hrm.values = v.dup; 777 778 // remove existent key 779 test(hrm.remove(HashRange(10, 12)), "This range should exist"); 780 test!("==")(hrm.ranges, 781 [R(1, 2), R(3, 15), R(10, 20), R(16, 18)][]); 782 test!("==")(hrm.values, [v[0], v[1], v[3], v[4]][]); 783 784 // remove nonexistent key 785 test(!hrm.remove(HashRange(10, 12)), "This range should be deleted already"); 786 test!("==")(hrm.ranges, 787 [R(1, 2), R(3, 15), R(10, 20), R(16, 18)][]); 788 test!("==")(hrm.values, [v[0], v[1], v[3], v[4]][]); 789 } 790 791 // Unittest function for opBinaryRight!"in". 792 private void testOpInR ( Value ) ( Value[] v ) 793 { 794 verify(v.length == 5, "You should provide an array of 5 different values"); 795 static assert(hasEquality!(Value), 796 "Value has to support equality check to run this test function"); 797 798 // In order to make notation shorter 799 alias HashRange R; 800 801 HashRangeMap!(Value) hrm; 802 hrm.ranges = [R(1, 2), R(3, 15), R(10, 12), R(10, 20), R(16, 18)]; 803 hrm.values = v.dup; 804 805 // not existent range 806 test!("==")(R(3, 12) in hrm, null); 807 808 // existent range 809 for(size_t i = 0; i < hrm.ranges.length; ++i) 810 test!("==")(*(hrm.ranges[i] in hrm), v[i]); 811 } 812 }