SortedMap.d

Revision 4008, 35.3 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.SortedMap;
18
19	public import tango.util.container.Container;
20
21	private import tango.util.container.RedBlack;
22
23	private import tango.util.container.model.IContainer;
24
25	private import tango.core.Exception : NoSuchElementException;
26
27	/*******************************************************************************
28
29	RedBlack trees of (key, value) pairs
30
31	---
32	Iterator iterator (bool forward)
33	Iterator iterator (K key, bool forward)
34	int opApply (int delegate (ref V value) dg)
35	int opApply (int delegate (ref K key, ref V value) dg)
36
37	bool contains (V value)
38	bool containsKey (K key)
39	bool containsPair (K key, V value)
40	bool keyOf (V value, ref K key)
41	bool get (K key, ref V value)
42
43	bool take (ref V v)
44	bool take (K key, ref V v)
45	bool removeKey (K key)
46	uint remove (V value, bool all)
47	uint remove (IContainer!(V) e, bool all)
48
49	bool add (K key, V value)
50	uint replace (V oldElement, V newElement, bool all)
51	bool replacePair (K key, V oldElement, V newElement)
52	bool opIndexAssign (V element, K key)
53	K nearbyKey (K key, bool greater)
54	V opIndex (K key)
55	V* opIn_r (K key)
56
57	uint size ()
58	bool isEmpty ()
59	V[] toArray (V[] dst)
60	SortedMap dup ()
61	SortedMap clear ()
62	SortedMap reset ()
63	SortedMap comparator (Comparator c)
64	---
65
66	*******************************************************************************/
67
68	class SortedMap (K, V, alias Reap = Container.reap,
69	alias Heap = Container.Collect)
70	: IContainer!(V)
71	{
72	// use this type for Allocator configuration
73	public alias RedBlack!(K, V) Type;
74	private alias Type *Ref;
75
76	private alias Heap!(Type) Alloc;
77	private alias Compare!(K) Comparator;
78
79	// root of the tree. Null if empty.
80	package Ref tree;
81
82	// configured heap manager
83	private Alloc heap;
84
85	// Comparators used for ordering
86	private Comparator cmp;
87	private Compare!(V) cmpElem;
88
89	private int count,
90	mutation;
91
92
93	/***********************************************************************
94
95	Make an empty tree, using given Comparator for ordering
96
97	***********************************************************************/
98
99	public this (Comparator c = null)
100	{
101	this (c, 0);
102	}
103
104	/***********************************************************************
105
106	Special version of constructor needed by dup()
107
108	***********************************************************************/
109
110	private this (Comparator c, int n)
111	{
112	count = n;
113	cmpElem = &compareElem;
114	cmp = (c is null) ? &compareKey : c;
115	}
116
117	/***********************************************************************
118
119	Clean up when deleted
120
121	***********************************************************************/
122
123	~this ()
124	{
125	reset;
126	}
127
128	/***********************************************************************
129
130	Return the configured allocator
131
132	***********************************************************************/
133
134	final Alloc allocator ()
135	{
136	return heap;
137	}
138
139	/***********************************************************************
140
141	Return a generic iterator for contained elements
142
143	***********************************************************************/
144
145	final Iterator iterator (bool forward = true)
146	{
147	Iterator i = void;
148	i.node = count ? (forward ? tree.leftmost : tree.rightmost) : null;
149	i.bump = forward ? &Iterator.fore : &Iterator.back;
150	i.mutation = mutation;
151	i.owner = this;
152	i.prior = null;
153	return i;
154	}
155
156	/***********************************************************************
157
158	Return an iterator which return all elements matching
159	or greater/lesser than the key in argument. The second
160	argument dictates traversal direction.
161
162	Return a generic iterator for contained elements
163
164	***********************************************************************/
165
166	final Iterator iterator (K key, bool forward)
167	{
168	Iterator i = iterator (forward);
169	i.node = count ? tree.findFirst(key, cmp, forward) : null;
170	return i;
171	}
172
173	/***********************************************************************
174
175	Return the number of elements contained
176
177	***********************************************************************/
178
179	final uint size ()
180	{
181	return count;
182	}
183
184	/***********************************************************************
185
186	Create an independent copy. Does not clone elements
187
188	***********************************************************************/
189
190	final SortedMap dup ()
191	{
192	auto clone = new SortedMap!(K, V, Reap, Heap) (cmp, count);
193	if (count)
194	clone.tree = tree.copyTree (&clone.heap.allocate);
195
196	return clone;
197	}
198
199	/***********************************************************************
200
201	Time complexity: O(log n)
202
203	***********************************************************************/
204
205	final bool contains (V value)
206	{
207	if (count is 0)
208	return false;
209	return tree.findAttribute (value, cmpElem) !is null;
210	}
211
212	/***********************************************************************
213
214	***********************************************************************/
215
216	final int opApply (int delegate (ref V value) dg)
217	{
218	return iterator.opApply ((ref K k, ref V v) {return dg(v);});
219	}
220
221
222	/***********************************************************************
223
224	***********************************************************************/
225
226	final int opApply (int delegate (ref K key, ref V value) dg)
227	{
228	return iterator.opApply (dg);
229	}
230
231	/***********************************************************************
232
233	Use a new Comparator. Causes a reorganization
234
235	***********************************************************************/
236
237	final SortedMap comparator (Comparator c)
238	{
239	if (cmp !is c)
240	{
241	cmp = (c is null) ? &compareKey : c;
242
243	if (count !is 0)
244	{
245	// must rebuild tree!
246	mutate;
247	auto t = tree.leftmost;
248	tree = null;
249	count = 0;
250
251	while (t)
252	{
253	add_ (t.value, t.attribute, false);
254	t = t.successor;
255	}
256	}
257	}
258	return this;
259	}
260
261	/***********************************************************************
262
263	Time complexity: O(log n)
264
265	***********************************************************************/
266
267	final bool containsKey (K key)
268	{
269	if (count is 0)
270	return false;
271
272	return tree.find (key, cmp) !is null;
273	}
274
275	/***********************************************************************
276
277	Time complexity: O(n)
278
279	***********************************************************************/
280
281	final bool containsPair (K key, V value)
282	{
283	if (count is 0)
284	return false;
285
286	return tree.find (key, value, cmp) !is null;
287	}
288
289	/***********************************************************************
290
291	Return the value associated with Key key.
292
293	param: key a key
294	Returns: whether the key is contained or not
295
296	***********************************************************************/
297
298	final bool get (K key, ref V value)
299	{
300	if (count)
301	{
302	auto p = tree.find (key, cmp);
303	if (p)
304	{
305	value = p.attribute;
306	return true;
307	}
308	}
309	return false;
310	}
311
312	/***********************************************************************
313
314	Return the value of the key exactly matching the provided
315	key or, if none, the key just after/before it based on the
316	setting of the second argument
317
318	param: key a key
319	param: after indicates whether to look beyond or before
320	the given key, where there is no exact match
321	throws: NoSuchElementException if none found
322	returns: a pointer to the value, or null if not present
323
324	***********************************************************************/
325
326	K nearbyKey (K key, bool after)
327	{
328	if (count)
329	{
330	auto p = tree.findFirst (key, cmp, after);
331	if (p)
332	return p.value;
333	}
334
335	noSuchElement ("no such key");
336	assert (0);
337	}
338
339	/***********************************************************************
340
341	Return the first key of the map
342
343	throws: NoSuchElementException where the map is empty
344
345	***********************************************************************/
346
347	K firstKey ()
348	{
349	if (count)
350	return tree.leftmost.value;
351
352	noSuchElement ("no such key");
353	assert (0);
354	}
355
356	/***********************************************************************
357
358	Return the last key of the map
359
360	throws: NoSuchElementException where the map is empty
361
362	***********************************************************************/
363
364	K lastKey ()
365	{
366	if (count)
367	return tree.rightmost.value;
368
369	noSuchElement ("no such key");
370	assert (0);
371	}
372
373	/***********************************************************************
374
375	Return the value associated with Key key.
376
377	param: key a key
378	Returns: a pointer to the value, or null if not present
379
380	***********************************************************************/
381
382	final V* opIn_r (K key)
383	{
384	if (count)
385	{
386	auto p = tree.find (key, cmp);
387	if (p)
388	return &p.attribute;
389	}
390	return null;
391	}
392
393	/***********************************************************************
394
395	Time complexity: O(n)
396
397	***********************************************************************/
398
399	final bool keyOf (V value, ref K key)
400	{
401	if (count is 0)
402	return false;
403
404	auto p = tree.findAttribute (value, cmpElem);
405	if (p is null)
406	return false;
407
408	key = p.value;
409	return true;
410	}
411
412	/***********************************************************************
413
414	Time complexity: O(n)
415
416	***********************************************************************/
417
418	final SortedMap clear ()
419	{
420	return clear (false);
421	}
422
423	/***********************************************************************
424
425	Reset the SortedMap contents. This releases more memory
426	than clear() does
427
428	Time complexity: O(n)
429
430	***********************************************************************/
431
432	final SortedMap reset ()
433	{
434	return clear (true);
435	}
436
437	/***********************************************************************
438
439	************************************************************************/
440
441	final uint remove (IContainer!(V) e, bool all)
442	{
443	auto c = count;
444	foreach (v; e)
445	remove (v, all);
446	return c - count;
447	}
448
449	/***********************************************************************
450
451	Time complexity: O(n
452
453	***********************************************************************/
454
455	final uint remove (V value, bool all = false)
456	{
457	uint i = count;
458	if (count)
459	{
460	auto p = tree.findAttribute (value, cmpElem);
461	while (p)
462	{
463	tree = p.remove (tree);
464	decrement (p);
465	if (!all \|\| count is 0)
466	break;
467	p = tree.findAttribute (value, cmpElem);
468	}
469	}
470	return i - count;
471	}
472
473	/***********************************************************************
474
475	Time complexity: O(n)
476
477	***********************************************************************/
478
479	final uint replace (V oldElement, V newElement, bool all = false)
480	{
481	uint c;
482
483	if (count)
484	{
485	auto p = tree.findAttribute (oldElement, cmpElem);
486	while (p)
487	{
488	++c;
489	mutate;
490	p.attribute = newElement;
491	if (!all)
492	break;
493	p = tree.findAttribute (oldElement, cmpElem);
494	}
495	}
496	return c;
497	}
498
499	/***********************************************************************
500
501	Time complexity: O(log n)
502
503	Takes the value associated with the least key.
504
505	***********************************************************************/
506
507	final bool take (ref V v)
508	{
509	if (count)
510	{
511	auto p = tree.leftmost;
512	v = p.attribute;
513	tree = p.remove (tree);
514	decrement (p);
515	return true;
516	}
517	return false;
518	}
519
520	/***********************************************************************
521
522	Time complexity: O(log n)
523
524	***********************************************************************/
525
526	final bool take (K key, ref V value)
527	{
528	if (count)
529	{
530	auto p = tree.find (key, cmp);
531	if (p)
532	{
533	value = p.attribute;
534	tree = p.remove (tree);
535	decrement (p);
536	return true;
537	}
538	}
539	return false;
540	}
541
542	/***********************************************************************
543
544	Time complexity: O(log n)
545
546	Returns true if inserted, false where an existing key
547	exists and was updated instead
548
549	***********************************************************************/
550
551	final bool add (K key, V value)
552	{
553	return add_ (key, value, true);
554	}
555
556	/***********************************************************************
557
558	Time complexity: O(log n)
559
560	Returns true if inserted, false where an existing key
561	exists and was updated instead
562
563	***********************************************************************/
564
565	final bool opIndexAssign (V element, K key)
566	{
567	return add (key, element);
568	}
569
570	/***********************************************************************
571
572	Operator retreival function
573
574	Throws NoSuchElementException where key is missing
575
576	***********************************************************************/
577
578	final V opIndex (K key)
579	{
580	auto p = opIn_r (key);
581	if (p)
582	return *p;
583
584	noSuchElement ("missing or invalid key");
585	assert (0);
586	}
587
588	/***********************************************************************
589
590	Time complexity: O(log n)
591
592	***********************************************************************/
593
594	final bool removeKey (K key)
595	{
596	V value;
597
598	return take (key, value);
599	}
600
601	/***********************************************************************
602
603	Time complexity: O(log n)
604
605	***********************************************************************/
606
607	final bool replacePair (K key, V oldElement, V newElement)
608	{
609	if (count)
610	{
611	auto p = tree.find (key, oldElement, cmp);
612	if (p)
613	{
614	p.attribute = newElement;
615	mutate;
616	return true;
617	}
618	}
619	return false;
620	}
621
622	/***********************************************************************
623
624	Copy and return the contained set of values in an array,
625	using the optional dst as a recipient (which is resized
626	as necessary).
627
628	Returns a slice of dst representing the container values.
629
630	Time complexity: O(n)
631
632	***********************************************************************/
633
634	final V[] toArray (V[] dst = null)
635	{
636	if (dst.length < count)
637	dst.length = count;
638
639	int i = 0;
640	foreach (k, v; this)
641	dst[i++] = v;
642	return dst [0 .. count];
643	}
644
645	/***********************************************************************
646
647	Is this container empty?
648
649	Time complexity: O(1)
650
651	***********************************************************************/
652
653	final bool isEmpty ()
654	{
655	return count is 0;
656	}
657
658	/***********************************************************************
659
660
661	***********************************************************************/
662
663	final SortedMap check ()
664	{
665	assert(cmp !is null);
666	assert(((count is 0) is (tree is null)));
667	assert((tree is null \|\| tree.size() is count));
668
669	if (tree)
670	{
671	tree.checkImplementation;
672	auto t = tree.leftmost;
673	K last = K.init;
674
675	while (t)
676	{
677	auto v = t.value;
678	assert((last is K.init \|\| cmp(last, v) <= 0));
679	last = v;
680	t = t.successor;
681	}
682	}
683	return this;
684	}
685
686
687	/***********************************************************************
688
689
690	***********************************************************************/
691
692	private void noSuchElement (char[] msg)
693	{
694	throw new NoSuchElementException (msg);
695	}
696