Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

root/trunk/tango/util/container/Slink.d

Revision 5421, 15.8 kB (checked in by kris, 5 years ago)

added support for retaining the key hash-value (via a -version=HashCache? in the interim)

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