Ticket #323: TreeMap.d

File TreeMap.d, 21.2 kB (added by Ansible, 2 years ago)
TreeMap? with exceptions

Line
1	/*
2	File: TreeMap.d
3
4	Originally written by Doug Lea and released into the public domain.
5	Thanks for the assistance and support of Sun Microsystems Labs, Agorics
6	Inc, Loral, and everyone contributing, testing, and using this code.
7
8	History:
9	Date Who What
10	24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file
11	13Oct95 dl Changed protection statuses
12
13	*/
14
15
16	module tango.util.collection.TreeMap;
17
18	private import tango.core.Exception;
19
20	private import tango.util.collection.model.Comparator,
21	tango.util.collection.model.SortedKeys,
22	tango.util.collection.model.GuardIterator;
23
24	private import tango.util.collection.impl.RBPair,
25	tango.util.collection.impl.RBCell,
26	tango.util.collection.impl.MapCollection,
27	tango.util.collection.impl.AbstractIterator,
28	tango.util.collection.impl.DefaultComparator;
29
30
31	/**
32	*
33	*
34	* RedBlack Trees of (key, element) pairs
35	*
36	author: Doug Lea
37	* @version 0.93
38	*
39	* <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
40	**/
41
42
43	public class TreeMap(K, T) : MapCollection!(K, T), SortedKeys!(K, T)
44	{
45	alias RBCell!(T) RBCellT;
46	alias RBPair!(K, T) RBPairT;
47	alias Comparator!(K) ComparatorT;
48	alias GuardIterator!(T) GuardIteratorT;
49
50	alias MapCollection!(K, T).remove remove;
51	alias MapCollection!(K, T).removeAll removeAll;
52
53
54	// instance variables
55
56	/**
57	* The root of the tree. Null if empty.
58	**/
59
60	package RBPairT tree;
61
62	/**
63	* The Comparator to use for ordering
64	**/
65
66	protected ComparatorT cmp;
67	protected Comparator!(T) cmpElem;
68
69	/**
70	* Make an empty tree, using DefaultComparator for ordering
71	**/
72
73	public this ()
74	{
75	this (null, null, null, 0);
76	}
77
78
79	/**
80	* Make an empty tree, using given screener for screening elements (not keys)
81	**/
82	public this (Predicate screener)
83	{
84	this(screener, null, null, 0);
85	}
86
87	/**
88	* Make an empty tree, using given Comparator for ordering
89	**/
90	public this (ComparatorT c)
91	{
92	this(null, c, null, 0);
93	}
94
95	/**
96	* Make an empty tree, using given screener and Comparator.
97	**/
98	public this (Predicate s, ComparatorT c)
99	{
100	this(s, c, null, 0);
101	}
102
103	/**
104	* Special version of constructor needed by clone()
105	**/
106
107	protected this (Predicate s, ComparatorT c, RBPairT t, int n)
108	{
109	super(s);
110	count = n;
111	tree = t;
112	cmp = (c is null) ? new DefaultComparator!(K) : c;
113	cmpElem = new DefaultComparator!(T);
114	}
115
116	/**
117	* Create an independent copy. Does not clone elements.
118	**/
119
120	public TreeMap duplicate()
121	{
122	if (count is 0)
123	return new TreeMap!(K, T)(screener, cmp);
124	else
125	return new TreeMap!(K, T)(screener, cmp, cast(RBPairT)(tree.copyTree()), count);
126	}
127
128
129	// Collection methods
130
131	/**
132	* Implements tango.util.collection.impl.Collection.Collection.contains
133	* Time complexity: O(log n).
134	* See_Also: tango.util.collection.impl.Collection.Collection.contains
135	**/
136	public final bool contains(T element)
137	{
138	if (!isValidArg(element) \|\| count is 0)
139	return false;
140	return tree.find(element, cmpElem) !is null;
141	}
142
143	/**
144	* Implements tango.util.collection.impl.Collection.Collection.instances
145	* Time complexity: O(log n).
146	* See_Also: tango.util.collection.impl.Collection.Collection.instances
147	**/
148	public final uint instances(T element)
149	{
150	if (!isValidArg(element) \|\| count is 0)
151	return 0;
152	return tree.count(element, cmpElem);
153	}
154
155	/**
156	* Implements tango.util.collection.impl.Collection.Collection.elements
157	* Time complexity: O(1).
158	* See_Also: tango.util.collection.impl.Collection.Collection.elements
159	**/
160	public final GuardIterator!(T) elements()
161	{
162	return keys();
163	}
164
165	/***********************************************************************
166
167	Implements tango.util.collection.model.View.View.opApply
168	Time complexity: O(n)
169
170	See_Also: tango.util.collection.model.View.View.opApply
171
172	************************************************************************/
173
174	int opApply (int delegate (inout T value) dg)
175	{
176	auto scope iterator = new MapIterator!(K, T)(this);
177	return iterator.opApply (dg);
178	}
179
180
181	/***********************************************************************
182
183	Implements tango.util.collection.MapView.opApply
184	Time complexity: O(n)
185
186	See_Also: tango.util.collection.MapView.opApply
187
188	************************************************************************/
189
190	int opApply (int delegate (inout K key, inout T value) dg)
191	{
192	auto scope iterator = new MapIterator!(K, T)(this);
193	return iterator.opApply (dg);
194	}
195
196	// KeySortedCollection methods
197
198	/**
199	* Implements tango.util.collection.KeySortedCollection.comparator
200	* Time complexity: O(1).
201	* See_Also: tango.util.collection.KeySortedCollection.comparator
202	**/
203	public final ComparatorT comparator()
204	{
205	return cmp;
206	}
207
208	/**
209	* Use a new Comparator. Causes a reorganization
210	**/
211
212	public final void comparator (ComparatorT c)
213	{
214	if (cmp !is c)
215	{
216	cmp = (c is null) ? new DefaultComparator!(K) : c;
217
218	if (count !is 0)
219	{
220	// must rebuild tree!
221	incVersion();
222	auto t = cast(RBPairT) (tree.leftmost());
223	tree = null;
224	count = 0;
225
226	while (t !is null)
227	{
228	add_(t.key(), t.element(), false);
229	t = cast(RBPairT)(t.successor());
230	}
231	}
232	}
233	}
234
235	// Map methods
236
237	/**
238	* Implements tango.util.collection.Map.containsKey.
239	* Time complexity: O(log n).
240	* See_Also: tango.util.collection.Map.containsKey
241	**/
242	public final bool containsKey(K key)
243	{
244	if (!isValidKey(key) \|\| count is 0)
245	return false;
246	return tree.findKey(key, cmp) !is null;
247	}
248
249	/**
250	* Implements tango.util.collection.Map.containsPair.
251	* Time complexity: O(n).
252	* See_Also: tango.util.collection.Map.containsPair
253	**/
254	public final bool containsPair(K key, T element)
255	{
256	if (count is 0 \|\| !isValidKey(key) \|\| !isValidArg(element))
257	return false;
258	return tree.find(key, element, cmp) !is null;
259	}
260
261	/**
262	* Implements tango.util.collection.Map.keys.
263	* Time complexity: O(1).
264	* See_Also: tango.util.collection.Map.keys
265	**/
266	public final PairIterator!(K, T) keys()
267	{
268	return new MapIterator!(K, T)(this);
269	}
270
271	/**
272	* Implements tango.util.collection.Map.get.
273	* Time complexity: O(log n).
274	* See_Also: tango.util.collection.Map.get
275	**/
276	public final T get(K key)
277	{
278	if (count !is 0)
279	{
280	RBPairT p = tree.findKey(key, cmp);
281	if (p !is null)
282	return p.element();
283	}
284	throw new NoSuchElementException("no matching Key ");
285	}
286
287	/**
288	* Return the element associated with Key key.
289	* @param key a key
290	* Returns: whether the key is contained or not
291	**/
292
293	public final bool get(K key, inout T value)
294	{
295	if (count !is 0)
296	{
297	RBPairT p = tree.findKey(key, cmp);
298	if (p !is null)
299	{
300	value = p.element();
301	return true;
302	}
303	}
304	return false;
305	}
306
307
308
309	/**
310	* Implements tango.util.collection.Map.keyOf.
311	* Time complexity: O(n).
312	* See_Also: tango.util.collection.Map.keyOf
313	**/
314	public final K keyOf(T element)
315	{
316	if (!isValidArg(element) \|\| count is 0)
317	throw new NoSuchElementException("no matching Element ");
318
319	RBPairT p = (cast(RBPairT)( tree.find(element, cmpElem)));
320	if (p !is null)
321	return p.key();
322	else
323	throw new NoSuchElementException("no matching Element ");
324	}
325
326
327	// MutableCollection methods
328
329	/**
330	* Implements tango.util.collection.impl.Collection.Collection.clear.
331	* Time complexity: O(1).
332	* See_Also: tango.util.collection.impl.Collection.Collection.clear
333	**/
334	public final void clear()
335	{
336	setCount(0);
337	tree = null;
338	}
339
340
341	/**
342	* Implements tango.util.collection.impl.Collection.Collection.removeAll.
343	* Time complexity: O(n).
344	* See_Also: tango.util.collection.impl.Collection.Collection.removeAll
345	**/
346	public final void removeAll(T element)
347	{
348	if (!isValidArg(element) \|\| count is 0)
349	return ;
350
351	RBPairT p = cast(RBPairT)(tree.find(element, cmpElem));
352	while (p !is null)
353	{
354	tree = cast(RBPairT)(p.remove(tree));
355	decCount();
356	if (count is 0)
357	return ;
358	p = cast(RBPairT)(tree.find(element, cmpElem));
359	}
360	}
361
362	/**
363	* Implements tango.util.collection.impl.Collection.Collection.removeOneOf.
364	* Time complexity: O(n).
365	* See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf
366	**/
367	public final void remove (T element)
368	{
369	if (!isValidArg(element) \|\| count is 0)
370	return ;
371
372	RBPairT p = cast(RBPairT)(tree.find(element, cmpElem));
373	if (p !is null)
374	{
375	tree = cast(RBPairT)(p.remove(tree));
376	decCount();
377	}
378	}
379
380
381	/**
382	* Implements tango.util.collection.impl.Collection.Collection.replaceOneOf.
383	* Time complexity: O(n).
384	* See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf
385	**/
386	public final void replace(T oldElement, T newElement)
387	{
388	if (count is 0 \|\| !isValidArg(oldElement) \|\| !isValidArg(oldElement))
389	return ;
390
391	RBPairT p = cast(RBPairT)(tree.find(oldElement, cmpElem));
392	if (p !is null)
393	{
394	checkElement(newElement);
395	incVersion();
396	p.element(newElement);
397	}
398	}
399
400	/**
401	* Implements tango.util.collection.impl.Collection.Collection.replaceAllOf.
402	* Time complexity: O(n).
403	* See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf
404	**/
405	public final void replaceAll(T oldElement, T newElement)
406	{
407	RBPairT p = cast(RBPairT)(tree.find(oldElement, cmpElem));
408	while (p !is null)
409	{
410	checkElement(newElement);
411	incVersion();
412	p.element(newElement);
413	p = cast(RBPairT)(tree.find(oldElement, cmpElem));
414	}
415	}
416
417	/**
418	* Implements tango.util.collection.impl.Collection.Collection.take.
419	* Time complexity: O(log n).
420	* Takes the element associated with the least key.
421	* See_Also: tango.util.collection.impl.Collection.Collection.take
422	**/
423	public final T take()
424	{
425	if (count !is 0)
426	{
427	RBPairT p = cast(RBPairT)(tree.leftmost());
428	T v = p.element();
429	tree = cast(RBPairT)(p.remove(tree));
430	decCount();
431	return v;
432	}
433
434	checkIndex(0);
435	return T.init; // not reached
436	}
437
438
439	// MutableMap methods
440
441	/**
442	* Implements tango.util.collection.impl.MapCollection.MapCollection.add.
443	* Time complexity: O(log n).
444	* See_Also: tango.util.collection.impl.MapCollection.MapCollection.add
445	**/
446	public final void add(K key, T element)
447	{
448	add_(key, element, true);
449	}
450
451
452	/**
453	* Implements tango.util.collection.impl.MapCollection.MapCollection.remove.
454	* Time complexity: O(log n).
455	* See_Also: tango.util.collection.impl.MapCollection.MapCollection.remove
456	**/
457	public final void removeKey (K key)
458	{
459	if (!isValidKey(key) \|\| count is 0)
460	return ;
461
462	RBCellT p = tree.findKey(key, cmp);
463	if (p !is null)
464	{
465	tree = cast(RBPairT)(p.remove(tree));
466	decCount();
467	}
468	}
469
470
471	/**
472	* Implements tango.util.collection.impl.MapCollection.MapCollection.replaceElement.
473	* Time complexity: O(log n).
474	* See_Also: tango.util.collection.impl.MapCollection.MapCollection.replaceElement
475	**/
476	public final void replacePair (K key, T oldElement,
477	T newElement)
478	{
479	if (!isValidKey(key) \|\| !isValidArg(oldElement) \|\| count is 0)
480	return ;
481
482	RBPairT p = tree.find(key, oldElement, cmp);
483	if (p !is null)
484	{
485	checkElement(newElement);
486	p.element(newElement);
487	incVersion();
488	}
489	}
490
491
492	// helper methods
493
494
495	private final void add_(K key, T element, bool checkOccurrence)
496	{
497	checkKey(key);
498	checkElement(element);
499
500	if (tree is null)
501	{
502	tree = new RBPairT(key, element);
503	incCount();
504	}
505	else
506	{
507	RBPairT t = tree;
508	for (;;)
509	{
510	int diff = cmp.compare(key, t.key());
511	if (diff is 0 && checkOccurrence)
512	{
513	if (t.element() != element)
514	{
515	t.element(element);
516	incVersion();
517	}
518	return ;
519	}
520	else
521	if (diff <= 0)
522	{
523	if (t.left() !is null)
524	t = cast(RBPairT)(t.left());
525	else
526	{
527	tree = cast(RBPairT)(t.insertLeft(new RBPairT(key, element), tree));
528	incCount();
529	return ;
530	}
531	}
532	else
533	{
534	if (t.right() !is null)
535	t = cast(RBPairT)(t.right());
536	else
537	{
538	tree = cast(RBPairT)(t.insertRight(new RBPairT(key, element), tree));
539	incCount();
540	return ;
541	}
542	}
543	}
544	}
545	}
546
547	// ImplementationCheckable methods
548
549	/**
550	* Implements tango.util.collection.model.View.View.checkImplementation.
551	* See_Also: tango.util.collection.model.View.View.checkImplementation
552	**/
553	public override void checkImplementation()
554	{
555	super.checkImplementation();
556	assert(cmp !is null);
557	assert(((count is 0) is (tree is null)));
558	assert((tree is null \|\| tree.size() is count));
559
560	if (tree !is null)
561	{
562	tree.checkImplementation();
563	K last = K.init;
564	RBPairT t = cast(RBPairT)(tree.leftmost());
565
566	while (t !is null)
567	{
568	K v = t.key();
569	assert((last is K.init \|\| cmp.compare(last, v) <= 0));
570	last = v;
571	t = cast(RBPairT)(t.successor());
572	}
573	}
574	}
575
576
577	/***********************************************************************
578
579	opApply() has migrated here to mitigate the virtual call
580	on method get()
581
582	************************************************************************/
583
584	private static class MapIterator(K, V) : AbstractMapIterator!(K, V)
585	{
586	private RBPairT pair;
587
588	public this (TreeMap map)
589	{
590	super (map);
591
592	if (map.tree)
593	pair = cast(RBPairT) map.tree.leftmost;
594	}
595
596	public final V get(inout K key)
597	{
598	if (pair)
599	key = pair.key;
600	return get();
601	}
602
603	public final V get()
604	{
605	decRemaining();
606	auto v = pair.element();
607	pair = cast(RBPairT) pair.successor();
608	return v;
609	}
610
611	int opApply (int delegate (inout V value) dg)
612	{
613	int result;
614
615	for (auto i=remaining(); i--;)
616	{
617	auto value = get();
618	if ((result = dg(value)) != 0)
619	break;
620	}
621	return result;
622	}
623
624	int opApply (int delegate (inout K key, inout V value) dg)
625	{
626	K key;
627	int result;
628
629