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

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

Revision 4008, 37.9 kB (checked in by larsivi, 1 month ago)

Fixed eol style for container package, refs #1303

  • 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.HashMap;
18
19 private import tango.util.container.Slink;
20
21 public  import tango.util.container.Container;
22
23 private import tango.util.container.model.IContainer;
24
25 private import tango.core.Exception : NoSuchElementException;
26
27 /*******************************************************************************
28
29         Hash table implementation of a Map
30
31         ---
32         Iterator iterator ()
33         int opApply (int delegate(ref V value) dg)
34         int opApply (int delegate(ref K key, ref V value) dg)
35
36         bool get (K key, ref V element)
37         bool keyOf (V value, ref K key)
38         bool contains (V element)
39         bool containsPair (K key, V element)
40
41         bool removeKey (K key)
42         bool take (ref V element)
43         bool take (K key, ref V element)
44         uint remove (V element, bool all)
45         uint remove (IContainer!(V) e, bool all)
46         uint replace (V oldElement, V newElement, bool all)
47         bool replacePair (K key, V oldElement, V newElement)
48
49         bool add (K key, V element)
50         bool opIndexAssign (V element, K key)
51         V    opIndex (K key)
52         V*   opIn_r (K key)
53
54         uint size ()
55         bool isEmpty ()
56         V[] toArray (V[] dst)
57         HashMap dup ()
58         HashMap clear ()
59         HashMap reset ()
60         uint buckets ()
61         float threshold ()
62         void buckets (uint cap)
63         void threshold (float desired)
64         Allocator allocator()
65         ---
66
67 *******************************************************************************/
68
69 class HashMap (K, V, alias Hash = Container.hash,
70                      alias Reap = Container.reap,
71                      alias Heap = Container.Collect)
72                      : IContainer!(V)
73 {
74         // bucket types
75         private alias Slink!(V, K) Type;
76         private alias Type         *Ref;
77
78         // allocator type
79         private alias Heap!(Type)  Alloc;
80
81         // each table entry is a linked list, or null
82         private Ref                table[];
83        
84         // number of elements contained
85         private uint               count;
86
87         // the threshold load factor
88         private float              loadFactor;
89
90         // configured heap manager
91         private Alloc              heap;
92        
93         // mutation tag updates on each change
94         private uint               mutation;
95
96         /***********************************************************************
97
98                 Construct a HashMap instance
99
100         ***********************************************************************/
101
102         this (float f = Container.defaultLoadFactor)
103         {
104                 loadFactor = f;
105         }
106
107         /***********************************************************************
108
109                 Clean up when deleted
110
111         ***********************************************************************/
112
113         ~this ()
114         {
115                 reset;
116         }
117
118         /***********************************************************************
119
120                 Return the configured allocator
121                 
122         ***********************************************************************/
123
124         final Alloc allocator ()
125         {
126                 return heap;
127         }
128
129         /***********************************************************************
130
131                 Return a generic iterator for contained elements
132                 
133         ***********************************************************************/
134
135         final Iterator iterator ()
136         {
137                 Iterator i = void;
138                 i.mutation = mutation;
139                 i.table = table;
140                 i.owner = this;
141                 i.cell = null;
142                 i.row = 0;
143                 return i;
144         }
145
146         /***********************************************************************
147
148
149         ***********************************************************************/
150
151         final int opApply (int delegate(ref K key, ref V value) dg)
152         {
153                 return iterator.opApply (dg);
154         }
155
156         /***********************************************************************
157
158
159         ***********************************************************************/
160
161         final int opApply (int delegate(ref V value) dg)
162         {
163                 return iterator.opApply ((ref K k, ref V v) {return dg(v);});
164         }
165
166         /***********************************************************************
167
168                 Return the number of elements contained
169                 
170         ***********************************************************************/
171
172         final uint size ()
173         {
174                 return count;
175         }
176        
177         /***********************************************************************
178
179                 Add a new element to the set. Does not add if there is an
180                 equivalent already present. Returns true where an element
181                 is added, false where it already exists (and was possibly
182                 updated).
183                 
184                 Time complexity: O(1) average; O(n) worst.
185                 
186         ***********************************************************************/
187
188         final bool add (K key, V element)
189         {
190                 if (table is null)
191                     resize (Container.defaultInitialBuckets);
192
193                 auto hd = &table [Hash (key, table.length)];
194                 auto node = *hd;
195                
196                 if (node is null)
197                    {
198                    *hd = heap.allocate.set (key, element, null);
199                    increment;
200                    }
201                 else
202                    {
203                    auto p = node.findKey (key);
204                    if (p)
205                       {
206                       if (element != p.value)
207                          {
208                          p.value = element;
209                          mutate;
210                          }
211                       return false;
212                       }
213                    else
214                       {
215                       *hd = heap.allocate.set (key, element, node);
216                       increment;
217
218                       // we only check load factor on add to nonempty bin
219                       checkLoad;
220                       }
221                    }
222                 return true;
223         }
224
225         /***********************************************************************
226
227                 Return the element associated with key
228
229                 param: a key
230                 param: a value reference (where returned value will reside)
231                 Returns: whether the key is contained or not
232         
233         ************************************************************************/
234
235         final bool get (K key, ref V element)
236         {
237                 if (count)
238                    {
239                    auto p = table [Hash (key, table.length)];
240                    if (p && (p = p.findKey(key)) !is null)
241                       {
242                       element = p.value;
243                       return true;
244                       }
245                    }
246                 return false;
247         }
248
249         /***********************************************************************
250
251                 Return the element associated with key
252
253                 param: a key
254                 Returns: a pointer to the located value, or null if not found
255         
256         ************************************************************************/
257
258         final V* opIn_r (K key)
259         {
260                 if (count)
261                    {
262                    auto p = table [Hash (key, table.length)];
263                    if (p && (p = p.findKey(key)) !is null)
264                        return &p.value;
265                    }
266                 return null;
267         }
268
269         /***********************************************************************
270
271                 Does this set contain the given element?
272         
273                 Time complexity: O(1) average; O(n) worst
274                 
275         ***********************************************************************/
276
277         final bool contains (V element)
278         {
279                 return instances (element) > 0;
280         }
281
282         /***********************************************************************
283
284                 Time complexity: O(n).
285         
286         ************************************************************************/
287        
288         final bool keyOf (V value, ref K key)
289         {
290                 if (count)
291                     foreach (list; table)
292                             if (list)
293                                {
294                                auto p = list.find (value);
295                                if (p)
296                                   {
297                                   key = p.key;
298                                   return true;
299                                   }
300                                }
301                 return false;
302         }
303
304         /***********************************************************************
305
306                 Time complexity: O(1) average; O(n) worst.
307                 
308         ***********************************************************************/
309        
310         final bool containsKey (K key)
311         {
312                 if (count)
313                    {
314                    auto p = table[Hash (key, table.length)];
315                    if (p && p.findKey(key))
316                        return true;
317                    }
318                 return false;
319         }
320
321         /***********************************************************************
322
323                 Time complexity: O(1) average; O(n) worst.
324         
325         ***********************************************************************/
326        
327         final bool containsPair (K key, V element)
328         {
329                 if (count)
330                    {                   
331                    auto p = table[Hash (key, table.length)];
332                    if (p && p.findPair (key, element))
333                        return true;
334                    }
335                 return false;
336         }
337
338         /***********************************************************************
339
340                 Make an independent copy of the container. Does not clone
341                 elements
342                 
343                 Time complexity: O(n)
344                 
345         ***********************************************************************/
346
347         final HashMap dup ()
348         {
349                 auto clone = new HashMap!(K, V, Hash, Reap, Heap) (loadFactor);
350
351                 if (count)
352                    {
353                    clone.buckets (buckets);
354
355                    foreach (key, value; iterator)
356                             clone.add (key, value);
357                    }
358                 return clone;
359         }
360
361         /***********************************************************************
362
363                 Time complexity: O(1) average; O(n) worst.
364         
365         ***********************************************************************/
366        
367         final bool removeKey (K key)
368         {
369                 V value;
370
371                 return take (key, value);
372         }
373
374         /***********************************************************************
375
376                 Time complexity: O(1) average; O(n) worst.
377         
378         ***********************************************************************/
379        
380         final bool replaceKey (K key, K replace)
381         {
382                 if (count)
383                    {
384                    auto h = Hash (key, table.length);
385                    auto hd = table[h];
386                    auto trail = hd;
387                    auto p = hd;
388
389                    while (p)
390                          {
391                          auto n = p.next;
392                          if (key == p.key)
393                             {
394                             if (p is hd)
395                                 table[h] = n;
396                             else
397                                trail.detachNext;
398                            
399                             // inject into new location
400                             h = Hash (replace, table.length);
401                             table[h] = p.set (replace, p.value, table[h]);
402                             return true;
403                             }
404                          else
405                             {
406                             trail = p;
407                             p = n;
408                             }
409                          }
410                    }
411                 return false;
412         }
413
414         /***********************************************************************
415
416                 Time complexity: O(1) average; O(n) worst.
417         
418         ***********************************************************************/
419        
420         final bool replacePair (K key, V oldElement, V newElement)
421         {
422                 if (count)
423                    {
424                    auto p = table [Hash (key, table.length)];
425                    if (p)
426                       {
427                       auto c = p.findPair (key, oldElement);
428                       if (c)
429                          {
430                          c.value = newElement;
431                          mutate;
432                          return true;
433                          }
434                       }
435                    }
436                 return false;
437         }
438
439         /***********************************************************************
440
441                 Remove and expose the first element. Returns false when no
442                 more elements are contained
443         
444                 Time complexity: O(n)
445
446         ***********************************************************************/
447
448         final bool take (ref V element)
449         {
450                 if (count)
451                     foreach (ref list; table)
452                              if (list)
453                                 {
454                                 auto p = list;
455                                 element = p.value;
456                                 list = p.next;
457                                 decrement (p);
458                                 return true;
459                                 }
460                 return false;
461         }
462
463         /***********************************************************************
464
465                 Remove and expose the element associated with key
466
467                 param: a key
468                 param: a value reference (where returned value will reside)
469                 Returns: whether the key is contained or not
470         
471                 Time complexity: O(1) average, O(n) worst
472
473         ***********************************************************************/
474        
475         final bool take (K key, ref V value)
476         {
477                 if (count)
478                    {
479                    auto p = &table [Hash (key, table.length)];
480                    auto n = *p;
481
482                    while ((n = *p) !is null)
483                            if (key == n.key)
484                               {
485                               *p = n.next;
486                               value = n.value;
487                               decrement (n);
488                               return true;
489                               }
490                            else
491                               p = &n.next;
492                    }
493                 return false;
494         }
495
496         /***********************************************************************
497
498                 Operator shortcut for assignment
499
500         ***********************************************************************/
501
502         final bool opIndexAssign (V element, K key)
503         {
504                 return add (key, element);
505         }
506
507         /***********************************************************************
508
509                 Operator retreival function
510
511                 Throws NoSuchElementException where key is missing
512
513         ***********************************************************************/
514
515         final V opIndex (K key)
516         {
517                 auto p = opIn_r (key);
518                 if (p)
519                     return *p;
520                 throw new NoSuchElementException ("missing or invalid key");
521         }
522
523         /***********************************************************************
524
525                 Remove a set of values
526
527         ************************************************************************/
528
529         final uint remove (IContainer!(V) e, bool all = false)
530         {
531                 int i = count;
532                 foreach (value; e)
533                          remove (value, all);
534                 return i - count;
535         }
536
537         /***********************************************************************
538
539                 Removes element instances, and returns the number of elements
540                 removed
541                 
542                 Time complexity: O(1) average; O(n) worst
543         
544         ************************************************************************/
545
546         final uint remove (V element, bool all = false)
547         {
548                 auto i = count;
549                
550                 if (i)
551                     foreach (ref node; table)
552                             {                         
553                             auto p = node;
554                             auto trail = node;
555
556                             while (p)
557                                   {     
558                                   auto n = p.next;
559                                   if (element == p.value)
560                                      {
561                                      decrement (p);
562                                      if (p is node)
563                                         {
564                                         node = n;
565                                         trail = n;
566                                         }
567                                      else
568                                         trail.next = n;
569
570                                      if (! all)
571                                            return i - count;
572                                      else
573                                         p = n;
574                                      }
575                                   else
576                                      {
577                                      trail = p;
578                                      p = n;
579                                      }
580                                   }
581                             }
582
583                 return i - count;
584         }
585
586         /***********************************************************************
587
588                 Replace instances of oldElement with newElement, and returns
589                 the number of replacements
590
591                 Time complexity: O(n).
592                 
593         ************************************************************************/
594
595         final uint replace (V oldElement, V newElement, bool all = false)
596         {
597                 uint i;
598                
599                 if (count && oldElement != newElement)
600                     foreach (node; table)
601                              while (node && (node = node.find(oldElement)) !is null)
602                                    {
603                                    ++i;
604                                    mutate;
605                                    node.value = newElement;
606                                    if (! all)
607                                          return i;
608                                    }
609                 return i;
610         }
611        
612         /***********************************************************************
613
614                 Clears the HashMap contents. Various attributes are
615                 retained, such as the internal table itself. Invoke
616                 reset() to drop everything.
617
618                 Time complexity: O(n)
619                 
620         ***********************************************************************/
621
622         final HashMap clear ()
623         {
624                 return clear (false);
625         }
626
627         /***********************************************************************
628
629                 Reset the HashMap contents. This releases more memory
630                 than clear() does
631
632                 Time complexity: O(n)
633                 
634         ***********************************************************************/
635
636         final HashMap reset ()
637         {
638                 clear (true);
639                 heap.collect (table);
640                 table = null;
641                 return this;
642         }
643
644         /***********************************************************************
645
646                 Return the number of buckets
647
648                 Time complexity: O(1)
649
650         ***********************************************************************/
651
652         final uint buckets ()
653         {
654                 return table ? table.length : 0;
655         }
656
657         /***********************************************************************
658
659                 Set the desired number of buckets in the hash table. Any
660                 value greater than or equal to one is OK.
661
662                 If different than current buckets, causes a version change
663                 
664                 Time complexity: O(n)
665
666         ***********************************************************************/
667
668         final void buckets (uint cap)
669         {
670                 if (cap < Container.defaultInitialBuckets)
671                     cap = Container<