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<