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 moduleocean.util.container.Slink;
21 22 importocean.core.Enforce;
23 24 importocean.transition;
25 26 importocean.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 private48 {
49 mixin(Typedef!(int, "KeyDummy"));
50 }
51 52 structSlink (V, K=KeyDummy, boolIdentity = false, boolHashCache = false)
53 {
54 aliasSlink!(V, K, Identity, HashCache) Type;
55 aliasType *Ref;
56 aliasCompare!(V) Comparator;
57 58 Refnext; // pointer to next59 Vvalue; // element value60 61 staticif (HashCache == true)
62 {
63 hash_tcache; // retain hash value?64 }
65 66 /***********************************************************************
67 68 add support for keys also?
69 70 ***********************************************************************/71 72 staticif (!is(typeof(K) == KeyDummy))
73 {
74 Kkey;
75 76 finalRefset (Kk, Vv, Refn)
77 {
78 key = k;
79 returnset (v, n);
80 }
81 82 finalhash_thash()
83 {
84 returntypeid(K).getHash(&key);
85 }
86 87 finalReffindKey (Kkey)
88 {
89 staticif (Identity == true)
90 {
91 for (autop=(&this); p; p = p.next)
92 if (keyisp.key)
93 returnp;
94 }
95 else96 {
97 for (autop=(&this); p; p = p.next)
98 if (key == p.key)
99 returnp;
100 }
101 returnnull;
102 }
103 104 finalReffindPair (Kkey, Vvalue)
105 {
106 staticif (Identity == true)
107 {
108 for (autop=(&this); p; p = p.next)
109 if (keyisp.key && value == p.value)
110 returnp;
111 }
112 else113 {
114 for (autop=(&this); p; p = p.next)
115 if (key == p.key && value == p.value)
116 returnp;
117 }
118 returnnull;
119 }
120 121 finalintindexKey (Kkey)
122 {
123 inti = 0;
124 staticif (Identity == true)
125 {
126 for (autop=(&this); p; p = p.next, ++i)
127 if (keyisp.key)
128 returni;
129 }
130 else131 {
132 for (autop=(&this); p; p = p.next, ++i)
133 if (key == p.key)
134 returni;
135 }
136 return -1;
137 }
138 139 finalintindexPair (Kkey, Vvalue)
140 {
141 inti = 0;
142 staticif (Identity == true)
143 {
144 for (autop=(&this); p; p = p.next, ++i)
145 if (keyisp.key && value == p.value)
146 returni;
147 }
148 else149 {
150 for (autop=(&this); p; p = p.next, ++i)
151 if (key == p.key && value == p.value)
152 returni;
153 }
154 return -1;
155 }
156 157 finalintcountKey (Kkey)
158 {
159 intc = 0;
160 staticif (Identity == true)
161 {
162 for (autop=(&this); p; p = p.next)
163 if (keyisp.key)
164 ++c;
165 }
166 else167 {
168 for (autop=(&this); p; p = p.next)
169 if (key == p.key)
170 ++c;
171 }
172 returnc;
173 }
174 175 finalintcountPair (Kkey, Vvalue)
176 {
177 intc = 0;
178 staticif (Identity == true)
179 {
180 for (autop=(&this); p; p = p.next)
181 if (keyisp.key && value == p.value)
182 ++c;
183 }
184 else185 {
186 for (autop=(&this); p; p = p.next)
187 if (key == p.key && value == p.value)
188 ++c;
189 }
190 returnc;
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 finalRefset (Vv, Refn)
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 finalvoidattach (Refp)
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 finalvoiddetachNext()
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 finalReffind (Velement)
248 {
249 for (autop = (&this); p; p = p.next)
250 if (element == p.value)
251 returnp;
252 returnnull;
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 finalintindex (Velement)
263 {
264 inti;
265 for (autop = (&this); p; p = p.next, ++i)
266 if (element == p.value)
267 returni;
268 269 return -1;
270 }
271 272 /***********************************************************************
273 274 Count the number of occurrences of element in list
275 276 ***********************************************************************/277 278 finalintcount (Velement)
279 {
280 intc;
281 for (autop = (&this); p; p = p.next)
282 if (element == p.value)
283 ++c;
284 returnc;
285 }
286 287 /***********************************************************************
288 289 Return the number of cells in the list
290 291 ***********************************************************************/292 293 finalintcount ()
294 {
295 intc;
296 for (autop = (&this); p; p = p.next)
297 ++c;
298 returnc;
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 finalReftail ()
309 {
310 autop = (&this);
311 while (p.next)
312 p = p.next;
313 returnp;
314 }
315 316 /***********************************************************************
317 318 Return the nth cell of the list, or null if no such
319 320 ***********************************************************************/321 322 finalRefnth (longn)
323 {
324 enforce(n >= 0);
325 326 autop = (&this);
327 for (longi; i < n && p; ++i)
328 p = p.next;
329 returnp;
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 finalRefcopy (scopeRefdelegate() alloc)
340 {
341 autonewlist = dup (alloc);
342 autocurrent = newlist;
343 344 for (autop = next; p; p = p.next)
345 {
346 current.next = p.dup (alloc);
347 current = current.next;
348 }
349 current.next = null;
350 returnnewlist;
351 }
352 353 /***********************************************************************
354 355 dup is shallow; i.e., just makes a copy of the current cell
356 357 ***********************************************************************/358 359 privateRefdup (scopeRefdelegate() alloc)
360 {
361 autoret = alloc();
362 staticif (is(typeof(K) == KeyDummy))
363 ret.set (value, next);
364 else365 ret.set (key, value, next);
366 returnret;
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 staticRefmerge (Reffst, Refsnd, Comparatorcmp)
382 {
383 autoa = fst;
384 autob = snd;
385 Refhd = null;
386 Refcurrent = null;
387 388 for (;;)
389 {
390 if (aisnull)
391 {
392 if (hdisnull)
393 hd = b;
394 else395 current.next = b;
396 returnhd;
397 }
398 else399 if (bisnull)
400 {
401 if (hdisnull)
402 hd = a;
403 else404 current.next = a;
405 returnhd;
406 }
407 408 intdiff = cmp (a.value, b.value);
409 if (diff <= 0)
410 {
411 if (hdisnull)
412 hd = a;
413 else414 current.next = a;
415 current = a;
416 a = a.next;
417 }
418 else419 {
420 if (hdisnull)
421 hd = b;
422 else423 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 staticRefsplit (Refs)
441 {
442 autofast = s;
443 autoslow = s;
444 445 if (fastisnull || fast.nextisnull)
446 returnnull;
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 autor = slow.next;
459 slow.next = null;
460 returnr;
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 staticRefsort (Refs, Comparatorcmp)
475 {
476 if (sisnull || s.nextisnull)
477 returns;
478 else479 {
480 autoright = split (s);
481 autoleft = s;
482 left = sort (left, cmp);
483 right = sort (right, cmp);
484 returnmerge (left, right, cmp);
485 }
486 }
487 488 }
489 490 version (UnitTest)
491 {
492 importocean.core.Test : NamedTest;
493 }
494 495 unittest496 {
497 autot = newNamedTest("Test nth() with an index out of bounds");
498 499 staticimmutabletotal_items = 11;
500 staticimmutableindex_out_of_bounds = total_items * 2;
501 502 autoslink = newSlink!(int);
503 t.test!("==")(slink.nth(0).value, 0);
504 t.test!("==")(slink.count(), 1);
505 506 autotail = slink;
507 for (inti = 1; i < total_items; ++i)
508 {
509 autoitem = newSlink!(int);
510 item.value = tail.value + 1;
511 tail.set(tail.value, item);
512 tail = item;
513 }
514 515 // Self-verification516 t.test!("==")(slink.count(), total_items);
517 for (inti = 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 }