1 /******************************************************************************* 2 3 copyright: Copyright (c) 2008 Kris Bell. All rights reserved 4 5 license: BSD style: $(LICENSE) 6 7 version: Apr 2008: Initial release 8 9 authors: Kris 10 11 Since: 0.99.7 12 13 Based upon Doug Lea's Java collection package 14 15 *******************************************************************************/ 16 17 module tango.util.container.CircularList; 18 19 private import tango.util.container.Clink; 20 21 public import tango.util.container.Container; 22 23 private import tango.util.container.model.IContainer; 24 25 /******************************************************************************* 26 27 Circular linked list 28 29 --- 30 Iterator iterator () 31 int opApply (scope int delegate(ref V value) dg) 32 33 CircularList add (V element) 34 CircularList addAt (size_t index, V element) 35 CircularList append (V element) 36 CircularList prepend (V element) 37 size_t addAt (size_t index, IContainer!(V) e) 38 size_t append (IContainer!(V) e) 39 size_t prepend (IContainer!(V) e) 40 41 bool take (ref V v) 42 bool contains (V element) 43 V get (size_t index) 44 size_t first (V element, size_t startingIndex = 0) 45 size_t last (V element, size_t startingIndex = 0) 46 47 V head () 48 V tail () 49 V head (V element) 50 V tail (V element) 51 V removeHead () 52 V removeTail () 53 54 bool removeAt (size_t index) 55 size_t remove (V element, bool all) 56 size_t removeRange (size_t fromIndex, size_t toIndex) 57 58 size_t replace (V oldElement, V newElement, bool all) 59 bool replaceAt (size_t index, V element) 60 61 size_t size () 62 bool isEmpty () 63 V[] toArray (V[] dst) 64 CircularList dup () 65 CircularList subset (size_t from, size_t length) 66 CircularList clear () 67 CircularList reset () 68 CircularList check () 69 --- 70 71 *******************************************************************************/ 72 73 class CircularList (V, alias Reap = Container.reap, 74 alias Heap = Container.DefaultCollect) 75 : IContainer!(V) 76 { 77 // use this type for Allocator configuration 78 public alias Clink!(V) Type; 79 80 private alias Type *Ref; 81 82 private alias Heap!(Type) Alloc; 83 84 // number of elements contained 85 private size_t count; 86 87 // configured heap manager 88 private Alloc heap; 89 90 // mutation tag updates on each change 91 private size_t mutation; 92 93 // head of the list. Null if empty 94 private Ref list; 95 96 97 /*********************************************************************** 98 99 Make an empty list 100 101 ***********************************************************************/ 102 103 this () 104 { 105 this (null, 0); 106 } 107 108 /*********************************************************************** 109 110 Make an configured list 111 112 ***********************************************************************/ 113 114 protected this (Ref h, size_t c) 115 { 116 list = h; 117 count = c; 118 } 119 120 /*********************************************************************** 121 122 Clean up when deleted 123 124 ***********************************************************************/ 125 126 ~this () 127 { 128 reset(); 129 } 130 131 /*********************************************************************** 132 133 Return a generic iterator for contained elements 134 135 ***********************************************************************/ 136 137 @property final Iterator iterator () 138 { 139 // used to be Iterator i = void, but that doesn't initialize 140 // fields that are not initialized here. 141 Iterator i; 142 i.owner = this; 143 i.mutation = mutation; 144 i.cell = i.head = list; 145 i.count = count; 146 i.index = 0; 147 return i; 148 } 149 150 /*********************************************************************** 151 152 Configure the assigned allocator with the size of each 153 allocation block (number of nodes allocated at one time) 154 and the number of nodes to pre-populate the cache with. 155 156 Time complexity: O(n) 157 158 ***********************************************************************/ 159 160 final CircularList cache (size_t chunk, size_t count=0) 161 { 162 heap.config (chunk, count); 163 return this; 164 } 165 166 /*********************************************************************** 167 168 169 ***********************************************************************/ 170 171 final int opApply (scope int delegate(ref V value) dg) 172 { 173 return iterator.opApply (dg); 174 } 175 176 /*********************************************************************** 177 178 Return the number of elements contained 179 180 ***********************************************************************/ 181 182 @property final const size_t size () 183 { 184 return count; 185 } 186 187 /*********************************************************************** 188 189 Make an independent copy of the list. Elements themselves 190 are not cloned 191 192 ***********************************************************************/ 193 194 @property final CircularList dup () 195 { 196 return new CircularList!(V, Reap, Heap) (list ? list.copyList(&heap.allocate) : null, count); 197 } 198 199 /*********************************************************************** 200 201 Time complexity: O(n) 202 203 ***********************************************************************/ 204 205 final bool contains (V element) 206 { 207 if (list) 208 return list.find (element) !is null; 209 return false; 210 } 211 212 /*********************************************************************** 213 214 Time complexity: O(1) 215 216 ***********************************************************************/ 217 218 final V head () 219 { 220 return firstCell().value; 221 } 222 223 /*********************************************************************** 224 225 Time complexity: O(1) 226 227 ***********************************************************************/ 228 229 final V tail () 230 { 231 return lastCell().value; 232 } 233 234 /*********************************************************************** 235 236 Time complexity: O(n) 237 238 ***********************************************************************/ 239 240 final V get (size_t index) 241 { 242 return cellAt(index).value; 243 } 244 245 /*********************************************************************** 246 247 Time complexity: O(n) 248 Returns size_t.max if no element found. 249 250 ***********************************************************************/ 251 252 final size_t first (V element, size_t startingIndex = 0) 253 { 254 if (startingIndex < 0) 255 startingIndex = 0; 256 257 auto p = list; 258 if (p is null) 259 return size_t.max; 260 261 for (size_t i = 0; true; ++i) 262 { 263 if (i >= startingIndex && element == p.value) 264 return i; 265 266 p = p.next; 267 if (p is list) 268 break; 269 } 270 return size_t.max; 271 } 272 273 /*********************************************************************** 274 275 Time complexity: O(n) 276 Returns size_t.max if no element found. 277 278 ***********************************************************************/ 279 280 final size_t last (V element, size_t startingIndex = 0) 281 { 282 if (count is 0) 283 return size_t.max; 284 285 if (startingIndex >= count) 286 startingIndex = count - 1; 287 288 if (startingIndex < 0) 289 startingIndex = 0; 290 291 auto p = cellAt (startingIndex); 292 size_t i = startingIndex; 293 for (;;) 294 { 295 if (element == p.value) 296 return i; 297 else 298 if (p is list) 299 break; 300 else 301 { 302 p = p.prev; 303 --i; 304 } 305 } 306 return size_t.max; 307 } 308 309 /*********************************************************************** 310 311 Time complexity: O(length) 312 313 ***********************************************************************/ 314 315 final CircularList subset (size_t from, size_t length) 316 { 317 Ref newlist = null; 318 319 if (length > 0) 320 { 321 checkIndex (from); 322 auto p = cellAt (from); 323 auto current = newlist = heap.allocate().set (p.value); 324 325 for (size_t i = 1; i < length; ++i) 326 { 327 p = p.next; 328 if (p is null) 329 length = i; 330 else 331 { 332 current.addNext (p.value, &heap.allocate); 333 current = current.next; 334 } 335 } 336 } 337 338 return new CircularList (newlist, length); 339 } 340 341 /*********************************************************************** 342 343 Time complexity: O(1) 344 345 ***********************************************************************/ 346 347 final CircularList clear () 348 { 349 return clear (false); 350 } 351 352 /*********************************************************************** 353 354 Reset the HashMap contents and optionally configure a new 355 heap manager. This releases more memory than clear() does 356 357 Time complexity: O(n) 358 359 ***********************************************************************/ 360 361 final CircularList reset () 362 { 363 return clear (true); 364 } 365 366 /*********************************************************************** 367 368 Time complexity: O(n) 369 370 Takes the last element on the list 371 372 ***********************************************************************/ 373 374 final bool take (ref V v) 375 { 376 if (count) 377 { 378 v = tail(); 379 removeTail (); 380 return true; 381 } 382 return false; 383 } 384 385 /*********************************************************************** 386 387 Time complexity: O(1) 388 389 ***********************************************************************/ 390 391 final CircularList prepend (V element) 392 { 393 if (list is null) 394 list = heap.allocate().set (element); 395 else 396 list = list.addPrev (element, &heap.allocate); 397 increment(); 398 return this; 399 } 400 401 /*********************************************************************** 402 403 Time complexity: O(1) 404 405 ***********************************************************************/ 406 407 final V head (V element) 408 { 409 auto p = firstCell(); 410 auto v = p.value; 411 p.value = element; 412 mutate(); 413 return v; 414 } 415 416 /*********************************************************************** 417 418 Time complexity: O(1) 419 420 ***********************************************************************/ 421 422 final V removeHead () 423 { 424 auto p = firstCell(); 425 if (p.singleton) 426 list = null; 427 else 428 { 429 auto n = p.next; 430 p.unlink(); 431 list = n; 432 } 433 434 auto v = p.value; 435 decrement (p); 436 return v; 437 } 438 439 /*********************************************************************** 440 441 Time complexity: O(1) 442 443 ***********************************************************************/ 444 445 final CircularList add (V element) 446 { 447 return append (element); 448 } 449 450 /*********************************************************************** 451 452 Time complexity: O(1) 453 454 ***********************************************************************/ 455 456 final CircularList append (V element) 457 { 458 if (list is null) 459 prepend (element); 460 else 461 { 462 list.prev.addNext (element, &heap.allocate); 463 increment(); 464 } 465 return this; 466 } 467 468 /*********************************************************************** 469 470 Time complexity: O(1) 471 472 ***********************************************************************/ 473 474 final V tail (V element) 475 { 476 auto p = lastCell(); 477 auto v = p.value; 478 p.value = element; 479 mutate(); 480 return v; 481 } 482 483 /*********************************************************************** 484 485 Time complexity: O(1) 486 487 ***********************************************************************/ 488 489 final V removeTail () 490 { 491 auto p = lastCell(); 492 if (p is list) 493 list = null; 494 else 495 p.unlink(); 496 497 auto v = p.value; 498 decrement (p); 499 return v; 500 } 501 502 /*********************************************************************** 503 504 Time complexity: O(n) 505 506 ***********************************************************************/ 507 508 final CircularList addAt (size_t index, V element) 509 { 510 if (index is 0) 511 prepend (element); 512 else 513 { 514 cellAt(index - 1).addNext(element, &heap.allocate); 515 increment(); 516 } 517 return this; 518 } 519 520 /*********************************************************************** 521 522 Time complexity: O(n) 523 524 ***********************************************************************/ 525 526 final CircularList replaceAt (size_t index, V element) 527 { 528 cellAt(index).value = element; 529 mutate(); 530 return this; 531 } 532 533 /*********************************************************************** 534 535 Time complexity: O(n) 536 537 ***********************************************************************/ 538 539 final CircularList removeAt (size_t index) 540 { 541 if (index is 0) 542 removeHead(); 543 else 544 { 545 auto p = cellAt(index); 546 p.unlink(); 547 decrement (p); 548 } 549 return this; 550 } 551 552 /*********************************************************************** 553 554 Time complexity: O(n) 555 556 ***********************************************************************/ 557 558 final size_t remove (V element, bool all) 559 { 560 auto c = count; 561 if (list) 562 { 563 auto p = list; 564 for (;;) 565 { 566 auto n = p.next; 567 if (element == p.value) 568 { 569 p.unlink(); 570 decrement (p); 571 if (p is list) 572 { 573 if (p is n) 574 { 575 list = null; 576 break; 577 } 578 else 579 list = n; 580 } 581 582 if (! all) 583 break; 584 else 585 p = n; 586 } 587 else 588 if (n is list) 589 break; 590 else 591 p = n; 592 } 593 } 594 return c - count; 595 } 596 597 /*********************************************************************** 598 599 Time complexity: O(n) 600 601 ***********************************************************************/ 602 603 final size_t replace (V oldElement, V newElement, bool all) 604 { 605 size_t c; 606 if (list) 607 { 608 auto p = list; 609 do { 610 if (oldElement == p.value) 611 { 612 ++c; 613 mutate(); 614 p.value = newElement; 615 if (! all) 616 break; 617 } 618 p = p.next; 619 } while (p !is list); 620 } 621 return c; 622 } 623 624 /*********************************************************************** 625 626 Time complexity: O(number of elements in e) 627 628 ***********************************************************************/ 629 630 final size_t prepend (IContainer!(V) e) 631 { 632 Ref hd = null; 633 Ref current = null; 634 auto c = count; 635 636 foreach (element; e) 637 { 638 increment(); 639 640 if (hd is null) 641 { 642 hd = heap.allocate().set(element); 643 current = hd; 644 } 645 else 646 { 647 current.addNext (element, &heap.allocate); 648 current = current.next; 649 } 650 } 651 652 if (list is null) 653 list = hd; 654 else 655 if (hd) 656 { 657 auto tl = list.prev; 658 current.next = list; 659 list.prev = current; 660 tl.next = hd; 661 hd.prev = tl; 662 list = hd; 663 } 664 return count - c; 665 } 666 667 /*********************************************************************** 668 669 Time complexity: O(number of elements in e) 670 671 ***********************************************************************/ 672 673 final size_t append (IContainer!(V) e) 674 { 675 auto c = count; 676 if (list is null) 677 prepend (e); 678 else 679 { 680 auto current = list.prev; 681 foreach (element; e) 682 { 683 increment(); 684 current.addNext (element, &heap.allocate); 685 current = current.next; 686 } 687 } 688 return count - c; 689 } 690 691 /*********************************************************************** 692 693 Time complexity: O(size() + number of elements in e) 694 695 ***********************************************************************/ 696 697 final size_t addAt (size_t index, IContainer!(V) e) 698 { 699 auto c = count; 700 if (list is null || index is 0) 701 prepend (e); 702 else 703 { 704 auto current = cellAt (index - 1); 705 foreach (element; e) 706 { 707 increment(); 708 current.addNext (element, &heap.allocate); 709 current = current.next; 710 } 711 } 712 return count - c; 713 } 714 715 /*********************************************************************** 716 717 Time complexity: O(n) 718 719 ***********************************************************************/ 720 721 final size_t removeRange (size_t fromIndex, size_t toIndex) 722 { 723 auto p = cellAt (fromIndex); 724 auto last = list.prev; 725 auto c = count; 726 for (size_t i = fromIndex; i <= toIndex; ++i) 727 { 728 auto n = p.next; 729 p.unlink(); 730 decrement (p); 731 if (p is list) 732 { 733 if (p is last) 734 { 735 list = null; 736 break; 737 } 738 else 739 list = n; 740 } 741 p = n; 742 } 743 return c - count; 744 } 745 746 /*********************************************************************** 747 748 Copy and return the contained set of values in an array, 749 using the optional dst as a recipient (which is resized 750 as necessary). 751 752 Returns a slice of dst representing the container values. 753 754 Time complexity: O(n) 755 756 ***********************************************************************/ 757 758 final V[] toArray (V[] dst = null) 759 { 760 if (dst.length < count) 761 dst.length = count; 762 763 size_t i = 0; 764 foreach (v; this) 765 dst[i++] = v; 766 return dst [0 .. count]; 767 } 768 769 /*********************************************************************** 770 771 Is this container empty? 772 773 Time complexity: O(1) 774 775 ***********************************************************************/ 776 777 final const bool isEmpty () 778 { 779 return count is 0; 780 } 781 782 /*********************************************************************** 783 784 785 ***********************************************************************/ 786 787 final CircularList check() 788 { 789 assert(((count is 0) is (list is null))); 790 assert((list is null || list.size is count)); 791 792 if (list) 793 { 794 size_t c = 0; 795 auto p = list; 796 do { 797 assert(p.prev.next is p); 798 assert(p.next.prev is p); 799 assert(instances(p.value) > 0); 800 assert(contains(p.value)); 801 p = p.next; 802 ++c; 803 } while (p !is list); 804 assert(c is size); 805 } 806 return this; 807 } 808 809 /*********************************************************************** 810 811 Time complexity: O(n) 812 813 ***********************************************************************/ 814 815 private size_t instances (V element) 816 { 817 if (list) 818 return list.count (element); 819 return 0; 820 } 821 822 /*********************************************************************** 823 824 825 ***********************************************************************/ 826 827 private void checkIndex (size_t i) 828 { 829 if (i >= count) 830 throw new Exception ("out of range"); 831 } 832 833 /*********************************************************************** 834 835 return the first cell, or throw exception if empty 836 837 ***********************************************************************/ 838 839 private Ref firstCell () 840 { 841 checkIndex (0); 842 return list; 843 } 844 845 /*********************************************************************** 846 847 return the last cell, or throw exception if empty 848 849 ***********************************************************************/ 850 851 private Ref lastCell () 852 { 853 checkIndex (0); 854 return list.prev; 855 } 856 857 /*********************************************************************** 858 859 return the index'th cell, or throw exception if bad index 860 861 ***********************************************************************/ 862 863 private Ref cellAt (size_t index) 864 { 865 checkIndex (index); 866 return list.nth (index); 867 } 868 869 /*********************************************************************** 870 871 Time complexity: O(1) 872 873 ***********************************************************************/ 874 875 private CircularList clear (bool all) 876 { 877 mutate(); 878 879 // collect each node if we can't collect all at once 880 if (heap.collect(all) is false && count) 881 { 882 auto p = list; 883 do { 884 auto n = p.next; 885 decrement (p); 886 p = n; 887 } while (p != list); 888 } 889 890 list = null; 891 count = 0; 892 return this; 893 } 894 895 /*********************************************************************** 896 897 new element was added 898 899 ***********************************************************************/ 900 901 private void increment () 902 { 903 ++mutation; 904 ++count; 905 } 906 907 /*********************************************************************** 908 909 element was removed 910 911 ***********************************************************************/ 912 913 private void decrement (Ref p) 914 { 915 Reap (p.value); 916 heap.collect (p); 917 ++mutation; 918 --count; 919 } 920 921 /*********************************************************************** 922 923 set was changed 924 925 ***********************************************************************/ 926 927 private void mutate () 928 { 929 ++mutation; 930 } 931 932 /*********************************************************************** 933 934 Iterator with no filtering 935 936 ***********************************************************************/ 937 938 private struct Iterator 939 { 940 bool rev; 941 Ref cell, 942 head, 943 prior; 944 CircularList owner; 945 size_t index, 946 count; 947 size_t mutation; 948 949 /*************************************************************** 950 951 Did the container change underneath us? 952 953 ***************************************************************/ 954 955 bool valid () 956 { 957 return owner.mutation is mutation; 958 } 959 960 /*************************************************************** 961 962 Accesses the next value, and returns false when 963 there are no further values to traverse 964 965 ***************************************************************/ 966 967 @property bool next (ref V v) 968 { 969 auto n = next; 970 return (n) ? v = *n, true : false; 971 } 972 973 /*************************************************************** 974 975 Return a pointer to the next value, or null when 976 there are no further values to traverse 977 978 ***************************************************************/ 979 980 @property V* next () 981 { 982 V* r; 983 984 if (index < count) 985 { 986 ++index; 987 prior = cell; 988 r = &cell.value; 989 cell = (rev ? cell.prev : cell.next); 990 } 991 else 992 cell = null; 993 return r; 994 } 995 996 /*************************************************************** 997 998 Foreach support 999 1000 ***************************************************************/ 1001 1002 int opApply (scope int delegate(ref V value) dg) 1003 { 1004 int result; 1005 auto c = cell; 1006 1007 while (index < count) 1008 { 1009 ++index; 1010 prior = c; 1011 c = (rev ? c.prev : c.next); 1012 if ((result = dg(prior.value)) != 0) 1013 break; 1014 } 1015 cell = null; 1016 return result; 1017 } 1018 1019 /*************************************************************** 1020 1021 Remove value that was just iterated. 1022 1023 ***************************************************************/ 1024 1025 bool remove () 1026 { 1027 if (prior) 1028 { 1029 auto next = (rev ? prior.prev : prior.next); 1030 if (prior is head) 1031 { 1032 if (prior is next) 1033 owner.list = null; 1034 else 1035 head = owner.list = next; 1036 } 1037 1038 prior.unlink(); 1039 owner.decrement (prior); 1040 prior = null; 1041 1042 --count; 1043 // ignore this change 1044 ++mutation; 1045 return true; 1046 } 1047 return false; 1048 } 1049 1050 /*************************************************************** 1051 1052 Insert a new value before the node about to be 1053 iterated (or after the node that was just iterated). 1054 1055 Returns: a copy of this iterator for chaining. 1056 1057 ***************************************************************/ 1058 1059 Iterator insert (V value) 1060 { 1061 // Note: this needs some attention, not sure how 1062 // to handle when iterator is in reverse. 1063 if (cell is null) 1064 prior.addNext (value, &owner.heap.allocate); 1065 else 1066 cell.addPrev (value, &owner.heap.allocate); 1067 owner.increment(); 1068 1069 ++count; 1070 // ignore this change 1071 ++mutation; 1072 return this; 1073 } 1074 1075 /*************************************************************** 1076 1077 Flip the direction of next() and opApply(), and 1078 reset the termination point such that we can do 1079 another full traversal. 1080 1081 ***************************************************************/ 1082 1083 Iterator reverse () 1084 { 1085 rev ^= true; 1086 next; 1087 index = 0; 1088 return this; 1089 } 1090 } 1091 } 1092 1093 /******************************************************************************* 1094 1095 *******************************************************************************/ 1096 1097 debug (UnitTest) 1098 { 1099 unittest 1100 { 1101 auto list = new CircularList!(int); 1102 list.add(1); 1103 list.add(2); 1104 list.add(3); 1105 1106 int i = 1; 1107 foreach(v; list) 1108 { 1109 assert(v == i); 1110 i++; 1111 } 1112 1113 auto iter = list.iterator; 1114 iter.next(); 1115 iter.remove(); // delete the first item 1116 1117 i = 2; 1118 foreach(v; list) 1119 { 1120 assert(v == i); 1121 i++; 1122 } 1123 1124 // test insert functionality 1125 iter = list.iterator; 1126 iter.next; 1127 iter.insert(4); 1128 1129 int[] compareto = [2, 4, 3]; 1130 i = 0; 1131 foreach(v; list) 1132 { 1133 assert(v == compareto[i++]); 1134 } 1135 } 1136 } 1137 1138 /******************************************************************************* 1139 1140 *******************************************************************************/ 1141 1142 debug (CircularList) 1143 { 1144 import tango.io.Stdout; 1145 import tango.core.Thread; 1146 import tango.time.StopWatch; 1147 1148 void main() 1149 { 1150 // usage examples ... 1151 auto list = new CircularList!(char[]); 1152 foreach (value; list) 1153 Stdout (value).newline; 1154 1155 list.add ("foo"); 1156 list.add ("bar"); 1157 list.add ("wumpus"); 1158 1159 // implicit generic iteration 1160 foreach (value; list) 1161 Stdout (value).newline; 1162 1163 // explicit generic iteration 1164 foreach (value; list.iterator.reverse) 1165 Stdout.formatln ("> {}", value); 1166 1167 // generic iteration with optional remove 1168 auto s = list.iterator; 1169 foreach (value; s) 1170 {} //s.remove; 1171 1172 // incremental iteration, with optional remove 1173 char[] v; 1174 auto iterator = list.iterator; 1175 while (iterator.next(v)) 1176 {}//iterator.remove; 1177 1178 // incremental iteration, with optional failfast 1179 auto it = list.iterator; 1180 while (it.valid && it.next(v)) 1181 {} 1182 1183 // remove specific element 1184 list.remove ("wumpus", false); 1185 1186 // remove first element ... 1187 while (list.take(v)) 1188 Stdout.formatln ("taking {}, {} left", v, list.size); 1189 1190 1191 // setup for benchmark, with a set of integers. We 1192 // use a chunk allocator, and presize the bucket[] 1193 auto test = new CircularList!(uint, Container.reap, Container.Chunk); 1194 test.cache (1000, 1_000_000); 1195 const count = 1_000_000; 1196 StopWatch w; 1197 1198 // benchmark adding 1199 w.start; 1200 for (uint i=count; i--;) 1201 test.add(i); 1202 Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop); 1203 1204 // benchmark adding without allocation overhead 1205 test.clear; 1206 w.start; 1207 for (uint i=count; i--;) 1208 test.add(i); 1209 Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop); 1210 1211 // benchmark duplication 1212 w.start; 1213 auto dup = test.dup; 1214 Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop); 1215 1216 // benchmark iteration 1217 w.start; 1218 foreach (value; test) {} 1219 Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop); 1220 1221 test.check; 1222 } 1223 }