1 /******************************************************************************* 2 3 Based upon Doug Lea's Java collection package 4 5 Copyright: 6 Copyright (c) 2008 Kris Bell. 7 Some parts copyright (c) 2009-2016 dunnhumby Germany GmbH. 8 All rights reserved. 9 10 License: 11 Tango Dual License: 3-Clause BSD License / Academic Free License v3.0. 12 See LICENSE_TANGO.txt for details. 13 14 Version: Apr 2008: Initial release 15 16 Authors: Kris 17 18 *******************************************************************************/ 19 20 module ocean.util.container.Slink; 21 22 import ocean.core.Enforce; 23 24 import ocean.transition; 25 26 import ocean.util.container.model.IContainer; 27 28 /******************************************************************************* 29 30 Slink instances provide standard linked list next-fields, and 31 support standard operations upon them. Slink structures are pure 32 implementation tools, and perform no argument checking, no result 33 screening, and no synchronization. They rely on user-level classes 34 (see HashSet, for example) to do such things. 35 36 Still, Slink is made `public' so that you can use it to build other 37 kinds of containers 38 39 Note that when K is specified, support for keys are enabled. When 40 Identity is stipulated as 'true', those keys are compared using an 41 identity-comparison instead of equality (using 'is'). Similarly, if 42 HashCache is set true, an additional attribute is create in order to 43 retain the hash of K 44 45 *******************************************************************************/ 46 47 private 48 { 49 mixin(Typedef!(int, "KeyDummy")); 50 } 51 52 struct Slink (V, K=KeyDummy, bool Identity = false, bool HashCache = false) 53 { 54 alias Slink!(V, K, Identity, HashCache) Type; 55 alias Type *Ref; 56 alias Compare!(V) Comparator; 57 58 Ref next; // pointer to next 59 V value; // element value 60 61 static if (HashCache == true) 62 { 63 hash_t cache; // retain hash value? 64 } 65 66 /*********************************************************************** 67 68 add support for keys also? 69 70 ***********************************************************************/ 71 72 static if (!is(typeof(K) == KeyDummy)) 73 { 74 K key; 75 76 final Ref set (K k, V v, Ref n) 77 { 78 key = k; 79 return set (v, n); 80 } 81 82 final hash_t hash() 83 { 84 return typeid(K).getHash(&key); 85 } 86 87 final Ref findKey (K key) 88 { 89 static if (Identity == true) 90 { 91 for (auto p=(&this); p; p = p.next) 92 if (key is p.key) 93 return p; 94 } 95 else 96 { 97 for (auto p=(&this); p; p = p.next) 98 if (key == p.key) 99 return p; 100 } 101 return null; 102 } 103 104 final Ref findPair (K key, V value) 105 { 106 static if (Identity == true) 107 { 108 for (auto p=(&this); p; p = p.next) 109 if (key is p.key && value == p.value) 110 return p; 111 } 112 else 113 { 114 for (auto p=(&this); p; p = p.next) 115 if (key == p.key && value == p.value) 116 return p; 117 } 118 return null; 119 } 120 121 final int indexKey (K key) 122 { 123 int i = 0; 124 static if (Identity == true) 125 { 126 for (auto p=(&this); p; p = p.next, ++i) 127 if (key is p.key) 128 return i; 129 } 130 else 131 { 132 for (auto p=(&this); p; p = p.next, ++i) 133 if (key == p.key) 134 return i; 135 } 136 return -1; 137 } 138 139 final int indexPair (K key, V value) 140 { 141 int i = 0; 142 static if (Identity == true) 143 { 144 for (auto p=(&this); p; p = p.next, ++i) 145 if (key is p.key && value == p.value) 146 return i; 147 } 148 else 149 { 150 for (auto p=(&this); p; p = p.next, ++i) 151 if (key == p.key && value == p.value) 152 return i; 153 } 154 return -1; 155 } 156 157 final int countKey (K key) 158 { 159 int c = 0; 160 static if (Identity == true) 161 { 162 for (auto p=(&this); p; p = p.next) 163 if (key is p.key) 164 ++c; 165 } 166 else 167 { 168 for (auto p=(&this); p; p = p.next) 169 if (key == p.key) 170 ++c; 171 } 172 return c; 173 } 174 175 final int countPair (K key, V value) 176 { 177 int c = 0; 178 static if (Identity == true) 179 { 180 for (auto p=(&this); p; p = p.next) 181 if (key is p.key && value == p.value) 182 ++c; 183 } 184 else 185 { 186 for (auto p=(&this); p; p = p.next) 187 if (key == p.key && value == p.value) 188 ++c; 189 } 190 return c; 191 } 192 } 193 194 /*********************************************************************** 195 196 Set to point to n as next cell 197 198 param: n, the new next cell 199 200 ***********************************************************************/ 201 202 final Ref set (V v, Ref n) 203 { 204 next = n; 205 value = v; 206 return (&this); 207 } 208 209 /*********************************************************************** 210 211 Splice in p between current cell and whatever it was 212 previously pointing to 213 214 param: p, the cell to splice 215 216 ***********************************************************************/ 217 218 final void attach (Ref p) 219 { 220 if (p) 221 p.next = next; 222 next = p; 223 } 224 225 /*********************************************************************** 226 227 Cause current cell to skip over the current next() one, 228 effectively removing the next element from the list 229 230 ***********************************************************************/ 231 232 final void detachNext() 233 { 234 if (next) 235 next = next.next; 236 } 237 238 /*********************************************************************** 239 240 Linear search down the list looking for element 241 242 param: element to look for 243 Returns: the cell containing element, or null if no such 244 245 ***********************************************************************/ 246 247 final Ref find (V element) 248 { 249 for (auto p = (&this); p; p = p.next) 250 if (element == p.value) 251 return p; 252 return null; 253 } 254 255 /*********************************************************************** 256 257 Return the number of cells traversed to find first occurrence 258 of a cell with element() element, or -1 if not present 259 260 ***********************************************************************/ 261 262 final int index (V element) 263 { 264 int i; 265 for (auto p = (&this); p; p = p.next, ++i) 266 if (element == p.value) 267 return i; 268 269 return -1; 270 } 271 272 /*********************************************************************** 273 274 Count the number of occurrences of element in list 275 276 ***********************************************************************/ 277 278 final int count (V element) 279 { 280 int c; 281 for (auto p = (&this); p; p = p.next) 282 if (element == p.value) 283 ++c; 284 return c; 285 } 286 287 /*********************************************************************** 288 289 Return the number of cells in the list 290 291 ***********************************************************************/ 292 293 final int count () 294 { 295 int c; 296 for (auto p = (&this); p; p = p.next) 297 ++c; 298 return c; 299 } 300 301 /*********************************************************************** 302 303 Return the cell representing the last element of the list 304 (i.e., the one whose next() is null 305 306 ***********************************************************************/ 307 308 final Ref tail () 309 { 310 auto p = (&this); 311 while (p.next) 312 p = p.next; 313 return p; 314 } 315 316 /*********************************************************************** 317 318 Return the nth cell of the list, or null if no such 319 320 ***********************************************************************/ 321 322 final Ref nth (long n) 323 { 324 enforce(n >= 0); 325 326 auto p = (&this); 327 for (long i; i < n && p; ++i) 328 p = p.next; 329 return p; 330 } 331 332 /*********************************************************************** 333 334 Make a copy of the list; i.e., a new list containing new cells 335 but including the same elements in the same order 336 337 ***********************************************************************/ 338 339 final Ref copy (scope Ref delegate() alloc) 340 { 341 auto newlist = dup (alloc); 342 auto current = newlist; 343 344 for (auto p = next; p; p = p.next) 345 { 346 current.next = p.dup (alloc); 347 current = current.next; 348 } 349 current.next = null; 350 return newlist; 351 } 352 353 /*********************************************************************** 354 355 dup is shallow; i.e., just makes a copy of the current cell 356 357 ***********************************************************************/ 358 359 private Ref dup (scope Ref delegate() alloc) 360 { 361 auto ret = alloc(); 362 static if (is(typeof(K) == KeyDummy)) 363 ret.set (value, next); 364 else 365 ret.set (key, value, next); 366 return ret; 367 } 368 369 /*********************************************************************** 370 371 Basic linkedlist merge algorithm. 372 Merges the lists head by fst and snd with respect to cmp 373 374 param: fst head of the first list 375 param: snd head of the second list 376 param: cmp a Comparator used to compare elements 377 Returns: the merged ordered list 378 379 ***********************************************************************/ 380 381 static Ref merge (Ref fst, Ref snd, Comparator cmp) 382 { 383 auto a = fst; 384 auto b = snd; 385 Ref hd = null; 386 Ref current = null; 387 388 for (;;) 389 { 390 if (a is null) 391 { 392 if (hd is null) 393 hd = b; 394 else 395 current.next = b; 396 return hd; 397 } 398 else 399 if (b is null) 400 { 401 if (hd is null) 402 hd = a; 403 else 404 current.next = a; 405 return hd; 406 } 407 408 int diff = cmp (a.value, b.value); 409 if (diff <= 0) 410 { 411 if (hd is null) 412 hd = a; 413 else 414 current.next = a; 415 current = a; 416 a = a.next; 417 } 418 else 419 { 420 if (hd is null) 421 hd = b; 422 else 423 current.next = b; 424 current = b; 425 b = b.next; 426 } 427 } 428 } 429 430 /*********************************************************************** 431 432 Standard list splitter, used by sort. 433 Splits the list in half. Returns the head of the second half 434 435 param: s the head of the list 436 Returns: the head of the second half 437 438 ***********************************************************************/ 439 440 static Ref split (Ref s) 441 { 442 auto fast = s; 443 auto slow = s; 444 445 if (fast is null || fast.next is null) 446 return null; 447 448 while (fast) 449 { 450 fast = fast.next; 451 if (fast && fast.next) 452 { 453 fast = fast.next; 454 slow = slow.next; 455 } 456 } 457 458 auto r = slow.next; 459 slow.next = null; 460 return r; 461 462 } 463 464 /*********************************************************************** 465 466 Standard merge sort algorithm 467 468 param: s the list to sort 469 param: cmp, the comparator to use for ordering 470 Returns: the head of the sorted list 471 472 ***********************************************************************/ 473 474 static Ref sort (Ref s, Comparator cmp) 475 { 476 if (s is null || s.next is null) 477 return s; 478 else 479 { 480 auto right = split (s); 481 auto left = s; 482 left = sort (left, cmp); 483 right = sort (right, cmp); 484 return merge (left, right, cmp); 485 } 486 } 487 488 } 489 490 version (UnitTest) 491 { 492 import ocean.core.Test : NamedTest; 493 } 494 495 unittest 496 { 497 auto t = new NamedTest("Test nth() with an index out of bounds"); 498 499 static immutable total_items = 11; 500 static immutable index_out_of_bounds = total_items * 2; 501 502 auto slink = new Slink!(int); 503 t.test!("==")(slink.nth(0).value, 0); 504 t.test!("==")(slink.count(), 1); 505 506 auto tail = slink; 507 for (int i = 1; i < total_items; ++i) 508 { 509 auto item = new Slink!(int); 510 item.value = tail.value + 1; 511 tail.set(tail.value, item); 512 tail = item; 513 } 514 515 // Self-verification 516 t.test!("==")(slink.count(), total_items); 517 for (int i = 0; i < total_items; ++i) 518 { 519 t.test!("==")(slink.nth(i).value, i); 520 } 521 522 t.test!("==")(slink.nth(total_items), null); 523 t.test!("==")(slink.nth(index_out_of_bounds), null); 524 }