Ticket #1303: x86_64-changes-r3995

File x86_64-changes-r3995, 165.9 kB (added by Cyborg16, 4 years ago)
full (but not very useful) diff

Line
1	Index: tango/util/container/model/IContainer.d
2	===================================================================
3	--- tango/util/container/model/IContainer.d (revision 3995)
4	+++ tango/util/container/model/IContainer.d (working copy)
5	@@ -22,7 +22,7 @@
6
7	interface IContainer (V)
8	{
9	- uint size ();
10	+ size_t size ();
11
12	bool isEmpty ();
13
14	@@ -40,11 +40,11 @@
15
16	V[] toArray (V[] dst = null);
17
18	- uint remove (V element, bool all);
19	+ size_t remove (V element, bool all);
20
21	int opApply (int delegate(ref V value) dg);
22
23	- uint replace (V oldElement, V newElement, bool all);
24	+ size_t replace (V oldElement, V newElement, bool all);
25	}
26
27
28	Index: tango/util/container/SortedMap.d
29	===================================================================
30	--- tango/util/container/SortedMap.d (revision 3995)
31	+++ tango/util/container/SortedMap.d (working copy)
32	@@ -1,1117 +1,1117 @@
33	-/*******************************************************************************
34	-
35	- copyright: Copyright (c) 2008 Kris Bell. All rights reserved
36	-
37	- license: BSD style: $(LICENSE)
38	-
39	- version: Apr 2008: Initial release
40	-
41	- authors: Kris
42	-
43	- Since: 0.99.7
44	-
45	- Based upon Doug Lea's Java collection package
46	-
47	-*******************************************************************************/
48	-
49	-module tango.util.container.SortedMap;
50	-
51	-public import tango.util.container.Container;
52	-
53	-private import tango.util.container.RedBlack;
54	-
55	-private import tango.util.container.model.IContainer;
56	-
57	-private import tango.core.Exception : NoSuchElementException;
58	-
59	-/*******************************************************************************
60	-
61	- RedBlack trees of (key, value) pairs
62	-
63	- ---
64	- Iterator iterator (bool forward)
65	- Iterator iterator (K key, bool forward)
66	- int opApply (int delegate (ref V value) dg)
67	- int opApply (int delegate (ref K key, ref V value) dg)
68	-
69	- bool contains (V value)
70	- bool containsKey (K key)
71	- bool containsPair (K key, V value)
72	- bool keyOf (V value, ref K key)
73	- bool get (K key, ref V value)
74	-
75	- bool take (ref V v)
76	- bool take (K key, ref V v)
77	- bool removeKey (K key)
78	- uint remove (V value, bool all)
79	- uint remove (IContainer!(V) e, bool all)
80	-
81	- bool add (K key, V value)
82	- uint replace (V oldElement, V newElement, bool all)
83	- bool replacePair (K key, V oldElement, V newElement)
84	- bool opIndexAssign (V element, K key)
85	- K nearbyKey (K key, bool greater)
86	- V opIndex (K key)
87	- V* opIn_r (K key)
88	-
89	- uint size ()
90	- bool isEmpty ()
91	- V[] toArray (V[] dst)
92	- SortedMap dup ()
93	- SortedMap clear ()
94	- SortedMap reset ()
95	- SortedMap comparator (Comparator c)
96	- ---
97	-
98	-*******************************************************************************/
99	-
100	-class SortedMap (K, V, alias Reap = Container.reap,
101	- alias Heap = Container.Collect)
102	- : IContainer!(V)
103	-{
104	- // use this type for Allocator configuration
105	- public alias RedBlack!(K, V) Type;
106	- private alias Type *Ref;
107	-
108	- private alias Heap!(Type) Alloc;
109	- private alias Compare!(K) Comparator;
110	-
111	- // root of the tree. Null if empty.
112	- package Ref tree;
113	-
114	- // configured heap manager
115	- private Alloc heap;
116	-
117	- // Comparators used for ordering
118	- private Comparator cmp;
119	- private Compare!(V) cmpElem;
120	-
121	- private int count,
122	- mutation;
123	-
124	-
125	- /***********************************************************************
126	-
127	- Make an empty tree, using given Comparator for ordering
128	-
129	- ***********************************************************************/
130	-
131	- public this (Comparator c = null)
132	- {
133	- this (c, 0);
134	- }
135	-
136	- /***********************************************************************
137	-
138	- Special version of constructor needed by dup()
139	-
140	- ***********************************************************************/
141	-
142	- private this (Comparator c, int n)
143	- {
144	- count = n;
145	- cmpElem = &compareElem;
146	- cmp = (c is null) ? &compareKey : c;
147	- }
148	-
149	- /***********************************************************************
150	-
151	- Clean up when deleted
152	-
153	- ***********************************************************************/
154	-
155	- ~this ()
156	- {
157	- reset;
158	- }
159	-
160	- /***********************************************************************
161	-
162	- Return the configured allocator
163	-
164	- ***********************************************************************/
165	-
166	- final Alloc allocator ()
167	- {
168	- return heap;
169	- }
170	-
171	- /***********************************************************************
172	-
173	- Return a generic iterator for contained elements
174	-
175	- ***********************************************************************/
176	-
177	- final Iterator iterator (bool forward = true)
178	- {
179	- Iterator i = void;
180	- i.node = count ? (forward ? tree.leftmost : tree.rightmost) : null;
181	- i.bump = forward ? &Iterator.fore : &Iterator.back;
182	- i.mutation = mutation;
183	- i.owner = this;
184	- i.prior = null;
185	- return i;
186	- }
187	-
188	- /***********************************************************************
189	-
190	- Return an iterator which return all elements matching
191	- or greater/lesser than the key in argument. The second
192	- argument dictates traversal direction.
193	-
194	- Return a generic iterator for contained elements
195	-
196	- ***********************************************************************/
197	-
198	- final Iterator iterator (K key, bool forward)
199	- {
200	- Iterator i = iterator (forward);
201	- i.node = count ? tree.findFirst(key, cmp, forward) : null;
202	- return i;
203	- }
204	-
205	- /***********************************************************************
206	-
207	- Return the number of elements contained
208	-
209	- ***********************************************************************/
210	-
211	- final uint size ()
212	- {
213	- return count;
214	- }
215	-
216	- /***********************************************************************
217	-
218	- Create an independent copy. Does not clone elements
219	-
220	- ***********************************************************************/
221	-
222	- final SortedMap dup ()
223	- {
224	- auto clone = new SortedMap!(K, V, Reap, Heap) (cmp, count);
225	- if (count)
226	- clone.tree = tree.copyTree (&clone.heap.allocate);
227	-
228	- return clone;
229	- }
230	-
231	- /***********************************************************************
232	-
233	- Time complexity: O(log n)
234	-
235	- ***********************************************************************/
236	-
237	- final bool contains (V value)
238	- {
239	- if (count is 0)
240	- return false;
241	- return tree.findAttribute (value, cmpElem) !is null;
242	- }
243	-
244	- /***********************************************************************
245	-
246	- ***********************************************************************/
247	-
248	- final int opApply (int delegate (ref V value) dg)
249	- {
250	- return iterator.opApply ((ref K k, ref V v) {return dg(v);});
251	- }
252	-
253	-
254	- /***********************************************************************
255	-
256	- ***********************************************************************/
257	-
258	- final int opApply (int delegate (ref K key, ref V value) dg)
259	- {
260	- return iterator.opApply (dg);
261	- }
262	-
263	- /***********************************************************************
264	-
265	- Use a new Comparator. Causes a reorganization
266	-
267	- ***********************************************************************/
268	-
269	- final SortedMap comparator (Comparator c)
270	- {
271	- if (cmp !is c)
272	- {
273	- cmp = (c is null) ? &compareKey : c;
274	-
275	- if (count !is 0)
276	- {
277	- // must rebuild tree!
278	- mutate;
279	- auto t = tree.leftmost;
280	- tree = null;
281	- count = 0;
282	-
283	- while (t)
284	- {
285	- add_ (t.value, t.attribute, false);
286	- t = t.successor;
287	- }
288	- }
289	- }
290	- return this;
291	- }
292	-
293	- /***********************************************************************
294	-
295	- Time complexity: O(log n)
296	-
297	- ***********************************************************************/
298	-
299	- final bool containsKey (K key)
300	- {
301	- if (count is 0)
302	- return false;
303	-
304	- return tree.find (key, cmp) !is null;
305	- }
306	-
307	- /***********************************************************************
308	-
309	- Time complexity: O(n)
310	-
311	- ***********************************************************************/
312	-
313	- final bool containsPair (K key, V value)
314	- {
315	- if (count is 0)
316	- return false;
317	-
318	- return tree.find (key, value, cmp) !is null;
319	- }
320	-
321	- /***********************************************************************
322	-
323	- Return the value associated with Key key.
324	-
325	- param: key a key
326	- Returns: whether the key is contained or not
327	-
328	- ***********************************************************************/
329	-
330	- final bool get (K key, ref V value)
331	- {
332	- if (count)
333	- {
334	- auto p = tree.find (key, cmp);
335	- if (p)
336	- {
337	- value = p.attribute;
338	- return true;
339	- }
340	- }
341	- return false;
342	- }
343	-
344	- /***********************************************************************
345	-
346	- Return the value of the key exactly matching the provided
347	- key or, if none, the key just after/before it based on the
348	- setting of the second argument
349	-
350	- param: key a key
351	- param: after indicates whether to look beyond or before
352	- the given key, where there is no exact match
353	- throws: NoSuchElementException if none found
354	- returns: a pointer to the value, or null if not present
355	-
356	- ***********************************************************************/
357	-
358	- K nearbyKey (K key, bool after)
359	- {
360	- if (count)
361	- {
362	- auto p = tree.findFirst (key, cmp, after);
363	- if (p)
364	- return p.value;
365	- }
366	-
367	- noSuchElement ("no such key");
368	- assert (0);
369	- }
370	-
371	- /***********************************************************************
372	-
373	- Return the first key of the map
374	-
375	- throws: NoSuchElementException where the map is empty
376	-
377	- ***********************************************************************/
378	-
379	- K firstKey ()
380	- {
381	- if (count)
382	- return tree.leftmost.value;
383	-
384	- noSuchElement ("no such key");
385	- assert (0);
386	- }
387	-
388	- /***********************************************************************
389	-
390	- Return the last key of the map
391	-
392	- throws: NoSuchElementException where the map is empty
393	-
394	- ***********************************************************************/
395	-
396	- K lastKey ()
397	- {
398	- if (count)
399	- return tree.rightmost.value;
400	-
401	- noSuchElement ("no such key");
402	- assert (0);
403	- }
404	-
405	- /***********************************************************************
406	-
407	- Return the value associated with Key key.
408	-
409	- param: key a key
410	- Returns: a pointer to the value, or null if not present
411	-
412	- ***********************************************************************/
413	-
414	- final V* opIn_r (K key)
415	- {
416	- if (count)
417	- {
418	- auto p = tree.find (key, cmp);
419	- if (p)
420	- return &p.attribute;
421	- }
422	- return null;
423	- }
424	-
425	- /***********************************************************************
426	-
427	- Time complexity: O(n)
428	-
429	- ***********************************************************************/
430	-
431	- final bool keyOf (V value, ref K key)
432	- {
433	- if (count is 0)
434	- return false;
435	-
436	- auto p = tree.findAttribute (value, cmpElem);
437	- if (p is null)
438	- return false;
439	-
440	- key = p.value;
441	- return true;
442	- }
443	-
444	- /***********************************************************************
445	-
446	- Time complexity: O(n)
447	-
448	- ***********************************************************************/
449	-
450	- final SortedMap clear ()
451	- {
452	- return clear (false);
453	- }
454	-
455	- /***********************************************************************
456	-
457	- Reset the SortedMap contents. This releases more memory
458	- than clear() does
459	-
460	- Time complexity: O(n)
461	-
462	- ***********************************************************************/
463	-
464	- final SortedMap reset ()
465	- {
466	- return clear (true);
467	- }
468	-
469	- /***********************************************************************
470	-
471	- ************************************************************************/
472	-
473	- final uint remove (IContainer!(V) e, bool all)
474	- {
475	- auto c = count;
476	- foreach (v; e)
477	- remove (v, all);
478	- return c - count;
479	- }
480	-
481	- /***********************************************************************
482	-
483	- Time complexity: O(n
484	-
485	- ***********************************************************************/
486	-
487	- final uint remove (V value, bool all = false)
488	- {
489	- uint i = count;
490	- if (count)
491	- {
492	- auto p = tree.findAttribute (value, cmpElem);
493	- while (p)
494	- {
495	- tree = p.remove (tree);
496	- decrement (p);
497	- if (!all \|\| count is 0)
498	- break;
499	- p = tree.findAttribute (value, cmpElem);
500	- }
501	- }
502	- return i - count;
503	- }
504	-
505	- /***********************************************************************
506	-
507	- Time complexity: O(n)
508	-
509	- ***********************************************************************/
510	-
511	- final uint replace (V oldElement, V newElement, bool all = false)
512	- {
513	- uint c;
514	-
515	- if (count)
516	- {
517	- auto p = tree.findAttribute (oldElement, cmpElem);
518	- while (p)
519	- {
520	- ++c;
521	- mutate;
522	- p.attribute = newElement;
523	- if (!all)
524	- break;
525	- p = tree.findAttribute (oldElement, cmpElem);
526	- }
527	- }
528	- return c;
529	- }
530	-
531	- /***********************************************************************
532	-
533	- Time complexity: O(log n)
534	-
535	- Takes the value associated with the least key.
536	-
537	- ***********************************************************************/
538	-
539	- final bool take (ref V v)
540	- {
541	- if (count)
542	- {
543	- auto p = tree.leftmost;
544	- v = p.attribute;
545	- tree = p.remove (tree);
546	- decrement (p);
547	- return true;
548	- }
549	- return false;
550	- }
551	-
552	- /***********************************************************************
553	-
554	- Time complexity: O(log n)
555	-
556	- ***********************************************************************/
557	-
558	- final bool take (K key, ref V value)
559	- {
560	- if (count)
561	- {
562	- auto p = tree.find (key, cmp);
563	- if (p)
564	- {
565	- value = p.attribute;
566	- tree = p.remove (tree);
567	- decrement (p);
568	- return true;
569	- }
570	- }
571	- return false;
572	- }
573	-
574	- /***********************************************************************
575	-
576	- Time complexity: O(log n)
577	-
578	- Returns true if inserted, false where an existing key
579	- exists and was updated instead
580	-
581	- ***********************************************************************/
582	-
583	- final bool add (K key, V value)
584	- {
585	- return add_ (key, value, true);
586	- }
587	-
588	- /***********************************************************************
589	-
590	- Time complexity: O(log n)
591	-
592	- Returns true if inserted, false where an existing key
593	- exists and was updated instead
594	-
595	- ***********************************************************************/
596	-
597	- final bool opIndexAssign (V element, K key)
598	- {
599	- return add (key, element);
600	- }
601	-
602	- /***********************************************************************
603	-
604	- Operator retreival function
605	-
606	- Throws NoSuchElementException where key is missing
607	-
608	- ***********************************************************************/
609	-
610	- final V opIndex (K key)
611	- {
612	- auto p = opIn_r (key);
613	- if (p)
614	- return *p;
615	-
616	- noSuchElement ("missing or invalid key");
617	- assert (0);
618	- }
619	-
620	- /***********************************************************************
621	-
622	- Time complexity: O(log n)
623	-
624	- ***********************************************************************/
625	-
626	- final bool removeKey (K key)
627	- {
628	- V value;
629	-
630	- return take (key, value);
631	- }
632	-
633	- /***********************************************************************
634	-
635	- Time complexity: O(log n)
636	-
637	- ***********************************************************************/
638	-
639	- final bool replacePair (K key, V oldElement, V newElement)
640	- {
641	- if (count)
642	- {
643	- auto p = tree.find (key, oldElement, cmp);
644	- if (p)
645	- {
646	- p.attribute = newElement;
647	- mutate;
648	- return true;
649	- }
650	- }
651	- return false;
652	- }
653	-
654	- /***********************************************************************
655	-
656	- Copy and return the contained set of values in an array,
657	- using the optional dst as a recipient (which is resized
658	- as necessary).
659	-
660	- Returns a slice of dst representing the container values.
661	-
662	- Time complexity: O(n)
663	-
664	- ***********************************************************************/
665	-
666	- final V[] toArray (V[] dst = null)
667	- {
668	- if (dst.length < count)
669	- dst.length = count;
670	-
671	- int i = 0;
672	- foreach (k, v; this)
673	- dst[i++] = v;
674	- return dst [0 .. count];
675	- }
676	-
677	- /***********************************************************************
678	-
679	- Is this container empty?
680	-
681	- Time complexity: O(1)
682	-
683	- ***********************************************************************/
684	-
685	- final bool isEmpty ()
686	- {
687	- return count is 0;
688	- }
689	-
690	- /***********************************************************************
691	-
692	-
693	- ***********************************************************************/
694	-
695	- final SortedMap check ()
696	- {
697	- assert(cmp !is null);
698	- assert(((count is 0) is (tree is null)));
699	- assert((tree is null \|\| tree.size() is count));
700	-
701	- if (tree)
702	- {
703	- tree.checkImplementation;
704	- auto t = tree.leftmost;
705	- K last = K.init;
706	-
707	- while (t)
708	- {
709	- auto v = t.value;
710	- assert((last is K.init \|\| cmp(last, v) <= 0));
711	- last = v;
712	- t = t.successor;
713	- }
714	- }
715	- return this;
716	- }
717	-
718	-
719	- /***********************************************************************
720	-
721	-
722	- ***********************************************************************/
723	-
724	- private void noSuchElement (char[] msg)
725	- {
726	- throw new NoSuchElementException (msg);
727	- }
728	-
729	- /***********************************************************************
730	-
731	- Time complexity: O(log n)
732	-
733	- ***********************************************************************/
734	-
735	- private uint instances (V value)
736	- {
737	- if (count is 0)
738	- return 0;
739	- return tree.countAttribute (value, cmpElem);
740	- }
741	-
742	- /***********************************************************************
743	-
744	- Returns true where an element is added, false where an
745	- existing key is found
746	-
747	- ***********************************************************************/
748	-
749	- private final bool add_ (K key, V value, bool checkOccurrence)
750	- {
751	- if (tree is null)
752	- {
753	- tree = heap.allocate.set (key, value);
754	- increment;
755	- }
756	- else
757	- {
758	- auto t = tree;
759	- for (;;)
760	- {
761	- int diff = cmp (key, t.value);
762	- if (diff is 0 && checkOccurrence)
763	- {
764	- if (t.attribute != value)
765	- {
766	- t.attribute = value;
767	- mutate;
768	- }
769	- return false;
770	- }
771	- else
772	- if (diff <= 0)
773	- {
774	- if (t.left)
775	- t = t.left;
776	- else
777	- {
778	- tree = t.insertLeft (heap.allocate.set(key, value), tree);
779	- increment;
780	- break;
781	- }
782	- }
783	- else
784	- {
785	- if (t.right)
786	- t = t.right;
787	- else
788	- {
789	- tree = t.insertRight (heap.allocate.set(key, value), tree);
790	- increment;
791	- break;
792	- }
793	- }
794	- }
795	- }
796	-
797	- return true;
798	- }
799	-
800	- /***********************************************************************
801	-
802	- Time complexity: O(n)
803	-
804	- ***********************************************************************/
805	-
806	- private SortedMap clear (bool all)
807	- {
808	- mutate;
809	-
810	- // collect each node if we can't collect all at once
811	- if (heap.collect(all) is false & count)
812	- {
813	- auto node = tree.leftmost;
814	- while (node)
815	- {
816	- auto next = node.successor;
817	- decrement (node);
818	- node = next;
819	- }
820	- }
821	-
822	- count = 0;
823	- tree = null;
824	- return this;
825	- }
826	-
827	- /***********************************************************************
828	-
829	- Time complexity: O(log n)
830	-
831	- ***********************************************************************/
832	-
833	- private void remove (Ref node)
834	- {
835	- tree = node.remove (tree);
836	- decrement (node);
837	- }
838	-
839	- /***********************************************************************
840	-
841	- new element was added
842	-
843	- ***********************************************************************/
844	-
845	- private void increment ()
846	- {
847	- ++mutation;
848	- ++count;
849	- }
850	-
851	- /***********************************************************************
852	-
853	- element was removed
854	-
855	- ***********************************************************************/
856	-
857	- private void decrement (Ref p)
858	- {
859	- Reap (p.value, p.attribute);
860	- heap.collect (p);
861	- ++mutation;
862	- --count;
863	- }
864	-
865	- /***********************************************************************
866	-
867	- set was changed
868	-
869	- ***********************************************************************/
870	-
871	- private void mutate ()
872	- {
873	- ++mutation;
874	- }
875	-
876	- /***********************************************************************
877	-
878	- The default key comparator
879	-
880	- @param fst first argument
881	- @param snd second argument
882	-
883	- Returns: a negative number if fst is less than snd; a
884	- positive number if fst is greater than snd; else 0
885	-
886	- ***********************************************************************/
887	-
888	- private static int compareKey (ref K fst, ref K snd)
889	- {
890	- if (fst is snd)
891	- return 0;
892	-
893	- return typeid(K).compare (&fst, &snd);
894	- }
895	-
896	-
897	- /***********************************************************************
898	-
899	- The default value comparator
900	-
901	- @param fst first argument
902	- @param snd second argument
903	-
904	- Returns: a negative number if fst is less than snd; a
905	- positive number if fst is greater than snd; else 0
906	-
907	- ***********************************************************************/
908	-
909	- private static int compareElem(ref V fst, ref V snd)
910	- {
911	- if (fst is snd)
912	- return 0;
913	-
914	- return typeid(V).compare (&fst, &snd);
915	- }
916	-
917	- /***********************************************************************
918	-
919	- Iterator with no filtering
920	-
921	- ***********************************************************************/
922	-
923	- private struct Iterator
924	- {
925	- Ref function(Ref) bump;
926	- Ref node,
927	- prior;
928	- SortedMap owner;
929	- uint mutation;
930	-
931	- /***************************************************************
932	-
933	- Did the container change underneath us?
934	-
935	- ***************************************************************/
936	-
937	- bool valid ()
938	- {
939	- return owner.mutation is mutation;
940	- }
941	-
942	- /***************************************************************
943	-
944	- Accesses the next value, and returns false when
945	- there are no further values to traverse
946	-
947	- ***************************************************************/
948	-
949	- bool next (ref K k, ref V v)
950	- {
951	- auto n = next (k);
952	- return (n) ? v = *n, true : false;
953	- }
954	-
955	- /***************************************************************
956	-
957	- Return a pointer to the next value, or null when
958	- there are no further values to traverse
959	-
960	- ***************************************************************/
961	-
962	- V* next (ref K k)
963	- {
964	- V* r;
965	-
966	- if (node)
967	- {
968	- prior = node;
969	- k = node.value;
970	- r = &node.attribute;
971	- node = bump (node);
972	- }
973	- return r;
974	- }
975	-
976	- /***************************************************************
977	-
978	- Foreach support
979	-
980	- ***************************************************************/
981	-
982	- int opApply (int delegate(ref K key, ref V value) dg)
983	- {
984	- int result;
985	-
986	- auto n = node;
987	- while (n)
988	- {
989	- prior = n;
990	- auto next = bump (n);
991	- if ((result = dg(n.value, n.attribute)) != 0)
992	- break;
993	- n = next;
994	- }
995	- node = n;
996	- return result;
997	- }
998	-
999	- /***************************************************************
1000	-
1001	- Remove value at the current iterator location
1002	-
1003	- ***************************************************************/
1004	-
1005	- bool remove ()
1006	- {
1007	- if (prior)
1008	- {
1009	- owner.remove (prior);
1010	-
1011	- // ignore this change
1012	- ++mutation;
1013	- return true;
1014	- }
1015	-
1016	- prior = null;
1017	- return false;
1018	- }
1019	-
1020	- /***************************************************************
1021	-
1022	- ***************************************************************/
1023	-
1024	- Iterator reverse ()
1025	- {
1026	- if (bump is &fore)
1027	- bump = &back;
1028	- else
1029	- bump = &fore;
1030	- return *this;
1031	- }
1032	-
1033	- /***************************************************************
1034	-
1035	- ***************************************************************/
1036	-
1037	- private static Ref fore (Ref p)
1038	- {
1039	- return p.successor;
1040	- }
1041	-
1042	- /***************************************************************
1043	-
1044	- ***************************************************************/
1045	-
1046	- private static Ref back (Ref p)
1047	- {
1048	- return p.predecessor;
1049	- }
1050	- }
1051	-}
1052	-
1053	-
1054	-
1055	-/*******************************************************************************
1056	-
1057	-*******************************************************************************/
1058	-
1059	-debug (SortedMap)
1060	-{
1061	- import tango.io.Stdout;
1062	- import tango.core.Thread;
1063	- import tango.time.StopWatch;
1064	- import tango.math.random.Kiss;
1065	-
1066	- void main()
1067	- {
1068	- // usage examples ...
1069	- auto map = new SortedMap!(char[], int);
1070	- map.add ("foo", 1);
1071	- map.add ("bar", 2);
1072	- map.add ("wumpus", 3);
1073	-
1074	- // implicit generic iteration
1075	- foreach (key, value; map)
1076	- Stdout.formatln ("{}:{}", key, value);
1077	-
1078	- // explicit iteration
1079	- foreach (key, value; map.iterator("foo", false))
1080	- Stdout.formatln ("{}:{}", key, value);
1081	-
1082	- // generic iteration with optional remove
1083	- auto s = map.iterator;
1084	- foreach (key, value; s)
1085	- {} // s.remove;
1086	-
1087	- // incremental iteration, with optional remove
1088	- char[] k;
1089	- int v;
1090	- auto iterator = map.iterator;
1091	- while (iterator.next(k, v))
1092	- {} //iterator.remove;
1093	-
1094	- // incremental iteration, with optional failfast
1095	- auto it = map.iterator;
1096	- while (it.valid && it.next(k, v))
1097	- {}
1098	-
1099	- // remove specific element
1100	- map.removeKey ("wumpus");
1101	-
1102	- // remove first element ...
1103	- while (map.take(v))
1104	- Stdout.formatln ("taking {}, {} left", v, map.size);
1105	-
1106	-
1107	- // setup for benchmark, with a set of integers. We
1108	- // use a chunk allocator, and presize the bucket[]
1109	- auto test = new SortedMap!(int, int, Container.reap, Container.Chunk);
1110	- test.allocator.config (1000, 500);
1111	- const count = 500_000;
1112	- StopWatch w;
1113	-
1114	- auto keys = new int[count];
1115	- foreach (ref vv; keys)
1116	- vv = Kiss.shared.toInt(int.max);
1117	-
1118	- // benchmark adding
1119	- w.start;
1120	- for (int i=count; i--;)
1121	- test.add(keys[i], i);
1122	- Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop);
1123	-
1124	- // benchmark reading
1125	- w.start;
1126	- for (int i=count; i--;)
1127	- test.get(keys[i], v);
1128	- Stdout.formatln ("{} lookups: {}/s", test.size, test.size/w.stop);
1129	-
1130	- // benchmark adding without allocation overhead
1131	- test.clear;
1132	- w.start;
1133	- for (int i=count; i--;)
1134	- test.add(keys[i], i);
1135	- Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop);
1136	-
1137	- // benchmark duplication
1138	- w.start;
1139	- auto dup = test.dup;
1140	- Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop);
1141	-
1142	- // benchmark iteration
1143	- w.start;
1144	- foreach (key, value; test) {}
1145	- Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop);
1146	-
1147	- test.check;
1148	- }
1149	-}
1150	+/*******************************************************************************
1151	+
1152	+ copyright: Copyright (c) 2008 Kris Bell. All rights reserved
1153	+
1154	+ license: BSD style: $(LICENSE)
1155	+
1156	+ version: Apr 2008: Initial release
1157	+
1158	+ authors: Kris
1159	+
1160	+ Since: 0.99.7
1161	+
1162	+ Based upon Doug Lea's Java collection package
1163	+
1164	+*******************************************************************************/
1165	+
1166	+module tango.util.container.SortedMap;
1167	+
1168	+public import tango.util.container.Container;
1169	+
1170	+private import tango.util.container.RedBlack;
1171	+
1172	+private import tango.util.container.model.IContainer;
1173	+
1174	+private import tango.core.Exception : NoSuchElementException;
1175	+
1176	+/*******************************************************************************
1177	+
1178	+ RedBlack trees of (key, value) pairs
1179	+
1180	+ ---
1181	+ Iterator iterator (bool forward)
1182	+ Iterator iterator (K key, bool forward)
1183	+ int opApply (int delegate (ref V value) dg)
1184	+ int opApply (int delegate (ref K key, ref V value) dg)
1185	+
1186	+ bool contains (V value)
1187	+ bool containsKey (K key)
1188	+ bool containsPair (K key, V value)
1189	+ bool keyOf (V value, ref K key)
1190	+ bool get (K key, ref V value)
1191	+
1192	+ bool take (ref V v)
1193	+ bool take (K key, ref V v)
1194	+ bool removeKey (K key)
1195	+ size_t remove (V value, bool all)
1196	+ size_t remove (IContainer!(V) e, bool all)
1197	+
1198	+ bool add (K key, V value)
1199	+ size_t replace (V oldElement, V newElement, bool all)
1200	+ bool replacePair (K key, V oldElement, V newElement)
1201	+ bool opIndexAssign (V element, K key)
1202	+ K nearbyKey (K key, bool greater)
1203	+ V opIndex (K key)
1204	+ V* opIn_r (K key)
1205	+
1206	+ size_t size ()
1207	+ bool isEmpty ()
1208	+ V[] toArray (V[] dst)
1209	+ SortedMap dup ()
1210	+ SortedMap clear ()
1211	+ SortedMap reset ()
1212	+ SortedMap comparator (Comparator c)
1213	+ ---
1214	+
1215	+*******************************************************************************/
1216	+
1217	+class SortedMap (K, V, alias Reap = Container.reap,
1218	+ alias Heap = Container.Collect)
1219	+ : IContainer!(V)
1220	+{
1221	+ // use this type for Allocator configuration
1222	+ public alias RedBlack!(K, V) Type;
1223	+ private alias Type *Ref;
1224	+
1225	+ private alias Heap!(Type) Alloc;
1226	+ private alias Compare!(K) Comparator;
1227	+
1228	+ // root of the tree. Null if empty.
1229	+ package Ref tree;
1230	+
1231	+ // configured heap manager
1232	+ private Alloc heap;
1233	+
1234	+ // Comparators used for ordering
1235	+ private Comparator cmp;
1236	+ private Compare!(V) cmpElem;
1237	+
1238	+ private size_t count,
1239	+ mutation;
1240	+
1241	+
1242	+ /***********************************************************************
1243	+
1244	+ Make an empty tree, using given Comparator for ordering
1245	+
1246	+ ***********************************************************************/
1247	+
1248	+ public this (Comparator c = null)
1249	+ {
1250	+ this (c, 0);
1251	+ }
1252	+
1253	+ /***********************************************************************
1254	+
1255	+ Special version of constructor needed by dup()
1256	+
1257	+ ***********************************************************************/
1258	+
1259	+ private this (Comparator c, size_t n)
1260	+ {
1261	+ count = n;
1262	+ cmpElem = &compareElem;
1263	+ cmp = (c is null) ? &compareKey : c;
1264	+ }
1265	+
1266	+ /***********************************************************************
1267	+
1268	+ Clean up when deleted
1269	+
1270	+ ***********************************************************************/
1271	+
1272	+ ~this ()
1273	+ {
1274	+ reset;
1275	+ }
1276	+
1277	+ /***********************************************************************
1278	+
1279	+ Return the configured allocator
1280	+
1281	+ ***********************************************************************/
1282	+
1283	+ final Alloc allocator ()
1284	+ {
1285	+ return heap;
1286	+ }
1287	+
1288	+ /***********************************************************************
1289	+
1290	+ Return a generic iterator for contained elements
1291	+
1292	+ ***********************************************************************/
1293	+
1294	+ final Iterator iterator (bool forward = true)
1295	+ {
1296	+ Iterator i = void;
1297	+ i.node = count ? (forward ? tree.leftmost : tree.rightmost) : null;
1298	+ i.bump = forward ? &Iterator.fore : &Iterator.back;
1299	+ i.mutation = mutation;
1300	+ i.owner = this;
1301	+ i.prior = null;
1302	+ return i;
1303	+ }
1304	+
1305	+ /***********************************************************************
1306	+
1307	+ Return an iterator which return all elements matching
1308	+ or greater/lesser than the key in argument. The second
1309	+ argument dictates traversal direction.
1310	+
1311	+ Return a generic iterator for contained elements
1312	+
1313	+ ***********************************************************************/
1314	+
1315	+ final Iterator iterator (K key, bool forward)
1316	+ {
1317	+ Iterator i = iterator (forward);
1318	+ i.node = count ? tree.findFirst(key, cmp, forward) : null;
1319	+ return i;
1320	+ }
1321	+
1322	+ /***********************************************************************
1323	+
1324	+ Return the number of elements contained
1325	+
1326	+ ***********************************************************************/
1327	+
1328	+ final size_t size ()
1329	+ {
1330	+ return count;
1331	+ }
1332	+
1333	+ /***********************************************************************
1334	+
1335	+ Create an independent copy. Does not clone elements
1336	+
1337	+ ***********************************************************************/
1338	+
1339	+ final SortedMap dup ()
1340	+ {
1341	+ auto clone = new SortedMap!(K, V, Reap, Heap) (cmp, count);
1342	+ if (count)
1343	+ clone.tree = tree.copyTree (&clone.heap.allocate);
1344	+
1345	+ return clone;
1346	+ }
1347	+
1348	+ /***********************************************************************
1349	+
1350	+ Time complexity: O(log n)
1351	+
1352	+ ***********************************************************************/
1353	+
1354	+ final bool contains (V value)
1355	+ {
1356	+ if (count is 0)
1357	+ return false;
1358	+ return tree.findAttribute (value, cmpElem) !is null;
1359	+ }
1360	+
1361	+ /***********************************************************************
1362	+
1363	+ ***********************************************************************/
1364	+
1365	+ final int opApply (int delegate (ref V value) dg)
1366	+ {
1367	+ return iterator.opApply ((ref K k, ref V v) {return dg(v);});
1368	+ }
1369	+
1370	+
1371	+ /***********************************************************************
1372	+
1373	+ ***********************************************************************/
1374	+
1375	+ final int opApply (int delegate (ref K key, ref V value) dg)
1376	+ {
1377	+ return iterator.opApply (dg);
1378	+ }
1379	+
1380	+ /***********************************************************************
1381	+
1382	+ Use a new Comparator. Causes a reorganization
1383	+
1384	+ ***********************************************************************/
1385	+
1386	+ final SortedMap comparator (Comparator c)
1387	+ {
1388	+ if (cmp !is c)
1389	+ {
1390	+ cmp = (c is null) ? &compareKey : c;
1391	+
1392	+ if (count !is 0)
1393	+ {
1394	+ // must rebuild tree!
1395	+ mutate;
1396	+ auto t = tree.leftmost;
1397	+ tree = null;
1398	+ count = 0;
1399	+
1400	+ while (t)
1401	+ {
1402	+ add_ (t.value, t.attribute, false);
1403	+ t = t.successor;
1404	+ }
1405	+ }
1406	+ }
1407	+ return this;
1408	+ }
1409	+
1410	+ /***********************************************************************
1411	+
1412	+ Time complexity: O(log n)
1413	+
1414	+ ***********************************************************************/
1415	+
1416	+ final bool containsKey (K key)
1417	+ {
1418	+ if (count is 0)
1419	+ return false;
1420	+
1421	+ return tree.find (key, cmp) !is null;
1422	+ }
1423	+
1424	+ /***********************************************************************
1425	+
1426	+ Time complexity: O(n)
1427	+
1428	+ ***********************************************************************/
1429	+
1430	+ final bool containsPair (K key, V value)
1431	+ {
1432	+ if (count is 0)
1433	+ return false;
1434	+
1435	+ return tree.find (key, value, cmp) !is null;
1436	+ }
1437	+
1438	+ /***********************************************************************
1439	+
1440	+ Return the value associated with Key key.
1441	+
1442	+ param: key a key
1443	+ Returns: whether the key is contained or not
1444	+
1445	+ ***********************************************************************/
1446	+
1447	+ final bool get (K key, ref V value)
1448	+ {
1449	+ if (count)
1450	+ {
1451	+ auto p = tree.find (key, cmp);
1452	+ if (p)
1453	+ {
1454	+ value = p.attribute;
1455	+ return true;
1456	+ }
1457	+ }
1458	+ return false;
1459	+ }
1460	+
1461	+ /***********************************************************************
1462	+
1463	+ Return the value of the key exactly matching the provided
1464	+ key or, if none, the key just after/before it based on the
1465	+ setting of the second argument
1466	+
1467	+ param: key a key
1468	+ param: after indicates whether to look beyond or before
1469	+ the given key, where there is no exact match
1470	+ throws: NoSuchElementException if none found
1471	+ returns: a pointer to the value, or null if not present
1472	+
1473	+ ***********************************************************************/
1474	+
1475	+ K nearbyKey (K key, bool after)
1476	+ {
1477	+ if (count)
1478	+ {
1479	+ auto p = tree.findFirst (key, cmp, after);
1480	+ if (p)
1481	+ return p.value;
1482	+ }
1483	+
1484	+ noSuchElement ("no such key");
1485	+ assert (0);
1486	+ }
1487	+
1488	+ /***********************************************************************
1489	+
1490	+ Return the first key of the map
1491	+
1492	+ throws: NoSuchElementException where the map is empty
1493	+
1494	+ ***********************************************************************/
1495	+
1496	+ K firstKey ()
1497	+ {
1498	+ if (count)
1499	+ return tree.leftmost.value;
1500	+
1501	+ noSuchElement ("no such key");
1502	+ assert (0);
1503	+ }
1504	+
1505	+ /***********************************************************************
1506	+
1507	+ Return the last key of the map
1508	+
1509	+ throws: NoSuchElementException where the map is empty
1510	+
1511	+ ***********************************************************************/
1512	+
1513	+ K lastKey ()
1514	+ {
1515	+ if (count)
1516	+ return tree.rightmost.value;
1517	+
1518	+ noSuchElement ("no such key");
1519	+ assert (0);
1520	+ }
1521	+
1522	+ /***********************************************************************
1523	+
1524	+ Return the value associated with Key key.
1525	+
1526	+ param: key a key
1527	+ Returns: a pointer to the value, or null if not present
1528	+
1529	+ ***********************************************************************/
1530	+
1531	+ final V* opIn_r (K key)
1532	+ {
1533	+ if (count)
1534	+ {
1535	+ auto p = tree.find (key, cmp);
1536	+ if (p)
1537	+ return &p.attribute;
1538	+ }
1539	+ return null;
1540	+ }
1541	+
1542	+ /***********************************************************************
1543	+
1544	+ Time complexity: O(n)
1545	+
1546	+ ***********************************************************************/
1547	+
1548	+ final bool keyOf (V value, ref K key)
1549	+ {
1550	+ if (count is 0)
1551	+ return false;
1552	+
1553	+ auto p = tree.findAttribute (value, cmpElem);
1554	+ if (p is null)
1555	+ return false;
1556	+
1557	+ key = p.value;
1558	+ return true;
1559	+ }
1560	+
1561	+ /***********************************************************************
1562	+
1563	+ Time complexity: O(n)
1564	+
1565	+ ***********************************************************************/
1566	+
1567	+ final SortedMap clear ()
1568	+ {
1569	+ return clear (false);
1570	+ }
1571	+
1572	+ /***********************************************************************
1573	+
1574	+ Reset the SortedMap contents. This releases more memory
1575	+ than clear() does
1576	+
1577	+ Time complexity: O(n)
1578	+
1579	+ ***********************************************************************/
1580	+
1581	+ final SortedMap reset ()
1582	+ {
1583	+ return clear (true);
1584	+ }
1585	+
1586	+ /***********************************************************************
1587	+
1588	+ ************************************************************************/
1589	+
1590	+ final size_t remove (IContainer!(V) e, bool all)
1591	+ {
1592	+ auto c = count;
1593	+ foreach (v; e)
1594	+ remove (v, all);
1595	+ return c - count;
1596	+ }
1597	+
1598	+ /***********************************************************************
1599	+
1600	+ Time complexity: O(n
1601	+
1602	+ ***********************************************************************/
1603	+
1604	+ final size_t remove (V value, bool all = false)
1605	+ {
1606	+ size_t i = count;
1607	+ if (count)
1608	+ {
1609	+ auto p = tree.findAttribute (value, cmpElem);
1610	+ while (p)
1611	+ {
1612	+ tree = p.remove (tree);
1613	+ decrement (p);
1614	+ if (!all \|\| count is 0)
1615	+ break;
1616	+ p = tree.findAttribute (value, cmpElem);
1617	+ }
1618	+ }
1619	+ return i - count;
1620	+ }
1621	+
1622	+ /***********************************************************************
1623	+
1624	+ Time complexity: O(n)
1625	+
1626	+ ***********************************************************************/
1627	+
1628	+ final size_t replace (V oldElement, V newElement, bool all = false)
1629	+ {
1630	+ size_t c;
1631	+
1632	+ if (count)
1633	+ {
1634	+ auto p = tree.findAttribute (oldElement, cmpElem);
1635	+ while (p)
1636	+ {
1637	+ ++c;
1638	+ mutate;
1639	+ p.attribute = newElement;
1640	+ if (!all)
1641	+ break;
1642	+ p = tree.findAttribute (oldElement, cmpElem);
1643	+ }
1644	+ }
1645	+ return c;
1646	+ }
1647	+
1648	+ /***********************************************************************
1649	+
1650	+ Time complexity: O(log n)
1651	+
1652	+ Takes the value associated with the least key.
1653	+
1654	+ ***********************************************************************/
1655	+
1656	+ final bool take (ref V v)
1657	+ {
1658	+ if (count)
1659	+ {
1660	+ auto p = tree.leftmost;
1661	+ v = p.attribute;
1662	+ tree = p.remove (tree);
1663	+ decrement (p);
1664	+ return true;
1665	+ }
1666	+ return false;
1667	+ }
1668	+
1669	+ /***********************************************************************
1670	+
1671	+ Time complexity: O(log n)
1672	+
1673	+ ***********************************************************************/
1674	+
1675	+ final bool take (K key, ref V value)
1676	+ {
1677	+ if (count)
1678	+ {
1679	+ auto p = tree.find (key, cmp);
1680	+ if (p)
1681	+ {
1682	+ value = p.attribute;
1683	+ tree = p.remove (tree);
1684	+ decrement (p);
1685	+ return true;
1686	+ }
1687	+ }
1688	+ return false;
1689	+ }
1690	+
1691	+ /***********************************************************************
1692	+
1693	+ Time complexity: O(log n)
1694	+
1695	+ Returns true if inserted, false where an existing key
1696	+ exists and was updated instead
1697	+
1698	+ ***********************************************************************/
1699	+
1700	+ final bool add (K key, V value)
1701	+ {
1702	+ return add_ (key, value, true);
1703	+ }
1704	+
1705	+ /***********************************************************************
1706	+
1707	+ Time complexity: O(log n)
1708	+
1709	+ Returns true if inserted, false where an existing key
1710	+ exists and was updated instead
1711	+
1712	+ ***********************************************************************/
1713	+
1714	+ final bool opIndexAssign (V element, K key)
1715	+ {
1716	+ return add (key, element);
1717	+ }
1718	+
1719	+ /***********************************************************************
1720	+
1721	+ Operator retreival function
1722	+
1723	+ Throws NoSuchElementException where key is missing
1724	+
1725	+ ***********************************************************************/
1726	+
1727	+ final V opIndex (K key)
1728	+ {
1729	+ auto p = opIn_r (key);
1730	+ if (p)
1731	+ return *p;
1732	+
1733	+ noSuchElement ("missing or invalid key");
1734	+ assert (0);
1735	+ }
1736	+
1737	+ /***********************************************************************
1738	+
1739	+ Time complexity: O(log n)
1740	+
1741	+ ***********************************************************************/
1742	+
1743	+ final bool removeKey (K key)
1744	+ {
1745	+ V value;
1746	+
1747	+ return take (key, value);
1748	+ }
1749	+
1750	+ /***********************************************************************
1751	+
1752	+ Time complexity: O(log n)
1753	+
1754	+ ***********************************************************************/
1755	+
1756	+ final bool replacePair (K key, V oldElement, V newElement)
1757	+ {
1758	+ if (count)
1759	+ {
1760	+ auto p = tree.find (key, oldElement, cmp);
1761	+ if (p)
1762	+ {
1763	+ p.attribute = newElement;
1764	+ mutate;
1765	+ return true;
1766	+ }
1767	+ }
1768	+ return false;
1769	+ }
1770	+
1771	+ /***********************************************************************
1772	+
1773	+ Copy and return the contained set of values in an array,
1774	+ using the optional dst as a recipient (which is resized
1775	+ as necessary).
1776	+
1777	+ Returns a slice of dst representing the container values.
1778	+
1779	+ Time complexity: O(n)
1780	+
1781	+ ***********************************************************************/
1782	+
1783	+ final V[] toArray (V[] dst = null)
1784	+ {
1785	+ if (dst.length < count)
1786	+ dst.length = count;
1787	+
1788	+ size_t i = 0;
1789	+ foreach (k, v; this)
1790	+ dst[i++] = v;
1791	+ return dst [0 .. count];
1792	+ }
1793	+
1794	+ /***********************************************************************
1795	+
1796	+ Is this container empty?
1797	+
1798	+ Time complexity: O(1)
1799	+
1800	+ ***********************************************************************/
1801	+
1802	+ final bool isEmpty ()
1803	+ {
1804	+ return count is 0;
1805	+ }
1806	+
1807	+ /***********************************************************************
1808	+
1809	+
1810	+ ***********************************************************************/
1811	+
1812	+ final SortedMap check ()
1813	+ {
1814	+ assert(cmp !is null);
1815	+ assert(((count is 0) is (tree is null)));
1816	+ assert((tree is null \|\| tree.size() is count));
1817	+
1818	+ if (tree)
1819	+ {
1820	+ tree.checkImplementation;
1821	+ auto t = tree.leftmost;
1822	+ K last = K.init;
1823	+
1824	+ while (t)
1825	+ {
1826	+ auto v = t.value;
1827	+ assert((last is K.init \|\| cmp(last, v) <= 0));
1828	+ last = v;
1829	+ t = t.successor;
1830	+ }
1831	+ }
1832	+ return this;
1833	+ }
1834	+
1835	+
1836	+ /***********************************************************************
1837	+
1838	+
1839	+ ***********************************************************************/
1840	+
1841	+ private void noSuchElement (char[] msg)
1842	+ {
1843	+ throw new NoSuchElementException (msg);
1844	+ }
1845	+
1846	+ /***********************************************************************
1847	+
1848	+ Time complexity: O(log n)
1849	+
1850	+ ***********************************************************************/
1851	+
1852	+ private size_t instances (V value)
1853	+ {
1854	+ if (count is 0)
1855	+ return 0;
1856	+ return tree.countAttribute (value, cmpElem);
1857	+ }
1858	+
1859	+ /***********************************************************************
1860	+
1861	+ Returns true where an element is added, false where an
1862	+ existing key is found
1863	+
1864	+ ***********************************************************************/
1865	+
1866	+ private final bool add_ (K key, V value, bool checkOccurrence)
1867	+ {
1868	+ if (tree is null)
1869	+ {
1870	+ tree = heap.allocate.set (key, value);
1871	+ increment;
1872	+ }
1873	+ else
1874	+ {
1875	+ auto t = tree;
1876	+ for (;;)
1877	+ {
1878	+ int diff = cmp (key, t.value);
1879	+ if (diff is 0 && checkOccurrence)
1880	+ {
1881	+ if (t.attribute != value)
1882	+ {
1883	+ t.attribute = value;
1884	+ mutate;
1885	+ }
1886	+ return false;
1887	+ }
1888	+ else
1889	+ if (diff <= 0)
1890	+ {
1891	+ if (t.left)
1892	+ t = t.left;
1893	+ else
1894	+ {
1895	+ tree = t.insertLeft (heap.allocate.set(key, value), tree);
1896	+ increment;
1897	+ break;
1898	+ }
1899	+ }
1900	+ else
1901	+ {
1902	+ if (t.right)
1903	+ t = t.right;
1904	+ else
1905	+ {
1906	+ tree = t.insertRight (heap.allocate.set(key, value), tree);
1907	+ increment;
1908	+ break;
1909	+ }
1910	+ }
1911	+ }
1912	+ }
1913	+
1914	+ return true;
1915	+ }
1916	+
1917	+ /***********************************************************************
1918	+
1919	+ Time complexity: O(n)
1920	+
1921	+ ***********************************************************************/
1922	+
1923	+ private SortedMap clear (bool all)
1924	+ {
1925	+ mutate;
1926	+
1927	+ // collect each node if we can't collect all at once
1928	+ if (heap.collect(all) is false & count)
1929	+ {
1930	+ auto node = tree.leftmost;
1931	+ while (node)
1932	+ {
1933	+ auto next = node.successor;
1934	+ decrement (node);
1935	+ node = next;
1936	+ }
1937	+ }
1938	+
1939	+ count = 0;
1940	+ tree = null;
1941	+ return this;
1942	+ }
1943	+
1944	+ /***********************************************************************
1945	+
1946	+ Time complexity: O(log n)
1947	+
1948	+ ***********************************************************************/
1949	+
1950	+ private void remove (Ref node)
1951	+ {
1952	+ tree = node.remove (tree);
1953	+ decrement (node);
1954	+ }
1955	+
1956	+ /***********************************************************************
1957	+
1958	+ new element was added
1959	+
1960	+ ***********************************************************************/
1961	+
1962	+ private void increment ()
1963	+ {
1964	+ ++mutation;
1965	+ ++count;
1966	+ }
1967	+
1968	+ /***********************************************************************
1969	+
1970	+ element was removed
1971	+
1972	+ ***********************************************************************/
1973	+
1974	+ private void decrement (Ref p)
1975	+ {
1976	+ Reap (p.value, p.attribute);
1977	+ heap.collect (p);
1978	+ ++mutation;
1979	+ --count;
1980	+ }
1981	+
1982	+ /***********************************************************************
1983	+
1984	+ set was changed
1985	+
1986	+ ***********************************************************************/
1987	+
1988	+ private void mutate ()
1989	+ {
1990	+ ++mutation;
1991	+ }
1992	+
1993	+ /***********************************************************************
1994	+
1995	+ The default key comparator
1996	+
1997	+ @param fst first argument
1998	+ @param snd second argument
1999	+
2000	+ Returns: a negative number if fst is less than snd; a
2001	+ positive number if fst is greater than snd; else 0
2002	+
2003	+ ***********************************************************************/
2004	+
2005	+ private static int compareKey (ref K fst, ref K snd)
2006	+ {
2007	+ if (fst is snd)
2008	+ return 0;
2009	+
2010	+ return typeid(K).compare (&fst, &snd);
2011	+ }
2012	+
2013	+
2014	+ /***********************************************************************
2015	+
2016	+ The default value comparator
2017	+
2018	+ @param fst first argument
2019	+ @param snd second argument
2020	+
2021	+ Returns: a negative number if fst is less than snd; a
2022	+ positive number if fst is greater than snd; else 0
2023	+
2024	+ ***********************************************************************/
2025	+
2026	+ private static int compareElem(ref V fst, ref V snd)
2027	+ {
2028	+ if (fst is snd)
2029	+ return 0;
2030	+
2031	+ return typeid(V).compare (&fst, &snd);
2032	+ }
2033	+
2034	+ /***********************************************************************
2035	+
2036	+ Iterator with no filtering
2037	+
2038	+ ***********************************************************************/
2039	+
2040	+ private struct Iterator
2041	+ {
2042	+ Ref function(Ref) bump;
2043	+ Ref node,
2044	+ prior;
2045	+ SortedMap owner;
2046	+ size_t mutation;
2047	+
2048	+ /***************************************************************
2049	+
2050	+ Did the container change underneath us?
2051	+
2052	+ ***************************************************************/
2053	+
2054	+ bool valid ()
2055	+ {
2056	+ return owner.mutation is mutation;
2057	+ }
2058	+
2059	+ /***************************************************************
2060	+
2061	+ Accesses the next value, and returns false when
2062	+ there are no further values to traverse
2063	+
2064	+ ***************************************************************/
2065	+
2066	+ bool next (ref K k, ref V v)
2067	+ {
2068	+ auto n = next (k);
2069	+ return (n) ? v = *n, true : false;
2070	+ }
2071	+
2072	+ /***************************************************************
2073	+
2074	+ Return a pointer to the next value, or null when
2075	+ there are no further values to traverse
2076	+
2077	+ ***************************************************************/
2078	+
2079	+ V* next (ref K k)
2080	+ {
2081	+ V* r;
2082	+
2083	+ if (node)
2084	+ {
2085	+ prior = node;
2086	+ k = node.value;
2087	+ r = &node.attribute;
2088	+ node = bump (node);
2089	+ }
2090	+ return r;
2091	+ }
2092	+
2093	+ /***************************************************************
2094	+
2095	+ Foreach support
2096	+
2097	+ ***************************************************************/
2098	+
2099	+ int opApply (int delegate(ref K key, ref V value) dg)
2100	+ {
2101	+ int result;
2102	+
2103	+ auto n = node;
2104	+ while (n)
2105	+ {
2106	+ prior = n;
2107	+ auto next = bump (n);
2108	+ if ((result = dg(n.value, n.attribute)) != 0)
2109	+ break;
2110	+ n = next;
2111	+ }
2112	+ node = n;
2113	+ return result;
2114	+ }
2115	+
2116	+ /***************************************************************
2117	+
2118	+ Remove value at the current iterator location
2119	+
2120	+ ***************************************************************/
2121	+
2122	+ bool remove ()
2123	+ {
2124	+ if (prior)
2125	+ {
2126	+ owner.remove (prior);
2127	+
2128	+ // ignore this change
2129	+ ++mutation;
2130	+ return true;
2131	+ }
2132	+
2133	+ prior = null;
2134	+ return false;
2135	+ }
2136	+
2137	+ /***************************************************************
2138	+
2139	+ ***************************************************************/
2140	+
2141	+ Iterator reverse ()
2142	+ {
2143	+ if (bump is &fore)
2144	+ bump = &back;
2145	+ else
2146	+ bump = &fore;
2147	+ return *this;
2148	+ }
2149	+
2150	+ /***************************************************************
2151	+
2152	+ ***************************************************************/
2153	+
2154	+ private static Ref fore (Ref p)
2155	+ {
2156	+ return p.successor;
2157	+ }
2158	+
2159	+ /***************************************************************
2160	+
2161	+ ***************************************************************/
2162	+
2163	+ private static Ref back (Ref p)
2164	+ {
2165	+ return p.predecessor;
2166	+ }
2167	+ }
2168	+}
2169	+
2170	+
2171	+
2172	+/*******************************************************************************
2173	+
2174	+*******************************************************************************/
2175	+
2176	+debug (SortedMap)
2177	+{
2178	+ import tango.io.Stdout;
2179	+ import tango.core.Thread;
2180	+ import tango.time.StopWatch;
2181	+ import tango.math.random.Kiss;
2182	+
2183	+ void main()
2184	+ {
2185	+ // usage examples ...
2186	+ auto map = new SortedMap!(char[], int);
2187	+ map.add ("foo", 1);
2188	+ map.add ("bar", 2);
2189	+ map.add ("wumpus", 3);
2190	+
2191	+ // implicit generic iteration
2192	+ foreach (key, value; map)
2193	+ Stdout.formatln ("{}:{}", key, value);
2194	+
2195	+ // explicit iteration
2196	+ foreach (key, value; map.iterator("foo", false))
2197	+ Stdout.formatln ("{}:{}", key, value);
2198	+
2199	+ // generic iteration with optional remove
2200	+ auto s = map.iterator;
2201	+ foreach (key, value; s)
2202	+ {} // s.remove;
2203	+
2204	+ // incremental iteration, with optional remove
2205	+ char[] k;
2206	+ int v;
2207	+ auto iterator = map.iterator;
2208	+ while (iterator.next(k, v))
2209	+ {} //iterator.remove;
2210	+
2211	+ // incremental iteration, with optional failfast
2212	+ auto it = map.iterator;
2213	+ while (it.valid && it.next(k, v))
2214	+ {}
2215	+
2216	+ // remove specific element
2217	+ map.removeKey ("wumpus");
2218	+
2219	+ // remove first element ...
2220	+ while (map.take(v))
2221	+ Stdout.formatln ("taking {}, {} left", v, map.size);
2222	+
2223	+
2224	+ // setup for benchmark, with a set of integers. We
2225	+ // use a chunk allocator, and presize the bucket[]
2226	+ auto test = new SortedMap!(int, int, Container.reap, Container.Chunk);
2227	+ test.allocator.config (1000, 500);
2228	+ const count = 500_000;
2229	+ StopWatch w;
2230	+
2231	+ auto keys = new int[count];
2232	+ foreach (ref vv; keys)
2233	+ vv = Kiss.shared.toInt(int.max);
2234	+
2235	+ // benchmark adding
2236	+ w.start;
2237	+ for (int i=count; i--;)
2238	+ test.add(keys[i], i);
2239	+ Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop);
2240	+
2241	+ // benchmark reading
2242	+ w.start;
2243	+ for (int i=count; i--;)
2244	+ test.get(keys[i], v);
2245	+ Stdout.formatln ("{} lookups: {}/s", test.size, test.size/w.stop);
2246	+
2247	+ // benchmark adding without allocation overhead
2248	+ test.clear;
2249	+ w.start;
2250	+ for (int i=count; i--;)
2251	+ test.add(keys[i], i);
2252	+ Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop);
2253	+
2254	+ // benchmark duplication
2255	+ w.start;
2256	+ auto dup = test.dup;
2257	+ Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop);
2258	+
2259	+ // benchmark iteration
2260	+ w.start;
2261	+ foreach (key, value; test) {}
2262	+ Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop);
2263	+
2264	+ test.check;
2265	+ }
2266	+}
2267	Index: tango/util/container/HashSet.d
2268	===================================================================
2269	--- tango/util/container/HashSet.d (revision 3995)
2270	+++ tango/util/container/HashSet.d (working copy)
2271	@@ -34,18 +34,18 @@
2272	bool contains (V element)
2273	bool take (ref V element)
2274	bool remove (V element)
2275	- uint remove (IContainer!(V) e)
2276	+ size_t remove (IContainer!(V) e)
2277	bool replace (V oldElement, V newElement)
2278
2279	- uint size ()
2280	+ size_t size ()
2281	bool isEmpty ()
2282	V[] toArray (V[] dst)
2283	HashSet dup ()
2284	HashSet clear ()
2285	HashSet reset ()
2286
2287	- uint buckets ()
2288	- void buckets (uint cap)
2289	+ size_t buckets ()
2290	+ void buckets (size_t cap)
2291	float threshold ()
2292	void threshold (float desired)
2293	---
2294	@@ -68,7 +68,7 @@
2295	private Ref table[];
2296
2297	// number of elements contained
2298	- private uint count;
2299	+ private size_t count;
2300
2301	// the threshold load factor
2302	private float loadFactor;
2303	@@ -77,7 +77,7 @@
2304	private Alloc heap;
2305
2306	// mutation tag updates on each change
2307	- private uint mutation;
2308	+ private size_t mutation;
2309
2310	/***********************************************************************
2311
2312	@@ -145,7 +145,7 @@
2313
2314	***********************************************************************/
2315
2316	- final uint size ()
2317	+ final size_t size ()
2318	{
2319	return count;
2320	}
2321	@@ -231,7 +231,7 @@
2322
2323	***********************************************************************/
2324
2325	- final uint remove (V element, bool all)
2326	+ final size_t remove (V element, bool all)
2327	{
2328	return remove(element) ? 1 : 0;
2329	}
2330	@@ -287,7 +287,7 @@
2331
2332	***********************************************************************/
2333
2334	- final uint replace (V oldElement, V newElement, bool all)
2335	+ final size_t replace (V oldElement, V newElement, bool all)
2336	{
2337	return replace (oldElement, newElement) ? 1 : 0;
2338	}
2339	@@ -351,9 +351,9 @@
2340
2341	************************************************************************/
2342
2343	- public uint remove (IContainer!(V) e)
2344	+ public size_t remove (IContainer!(V) e)
2345	{
2346	- uint c;
2347	+ size_t c;
2348	foreach (value; e)
2349	if (remove (value))
2350	++c;
2351	@@ -400,7 +400,7 @@
2352
2353	***********************************************************************/
2354
2355	- final uint buckets ()
2356	+ final size_t buckets ()
2357	{
2358	return table ? table.length : 0;
2359	}
2360	@@ -413,7 +413,7 @@
2361
2362	***********************************************************************/
2363
2364	- final void buckets (uint cap)
2365	+ final void buckets (size_t cap)
2366	{
2367	if (cap < Container.defaultInitialBuckets)
2368	cap = Container.defaultInitialBuckets;
2369	@@ -548,7 +548,7 @@
2370
2371	***********************************************************************/
2372
2373	- private void resize (uint newCap)
2374	+ private void resize (size_t newCap)
2375	{
2376	//Stdout.formatln ("resize {}", newCap);
2377	auto newtab = heap.allocate (newCap);
2378	@@ -579,7 +579,7 @@
2379
2380	***********************************************************************/
2381
2382	- private bool remove (Ref node, uint row)
2383	+ private bool remove (Ref node, size_t row)
2384	{
2385	auto hd = table[row];
2386	auto trail = hd;
2387	@@ -683,12 +683,12 @@
2388
2389	private struct Iterator
2390	{
2391	- uint row;
2392	+ size_t row;
2393	Ref cell,
2394	prior;
2395	Ref[] table;
2396	HashSet owner;
2397	- uint mutation;
2398	+ size_t mutation;
2399
2400	/***************************************************************
2401
2402	Index: tango/util/container/CircularList.d
2403	===================================================================
2404	--- tango/util/container/CircularList.d (revision 3995)
2405	+++ tango/util/container/CircularList.d (working copy)
2406	@@ -1,1154 +1,1156 @@
2407	-/*******************************************************************************
2408	-
2409	- copyright: Copyright (c) 2008 Kris Bell. All rights reserved
2410	-
2411	- license: BSD style: $(LICENSE)
2412	-
2413	- version: Apr 2008: Initial release
2414	-
2415	- authors: Kris
2416	-
2417	- Since: 0.99.7
2418	-
2419	- Based upon Doug Lea's Java collection package
2420	-
2421	-*******************************************************************************/
2422	-
2423	-module tango.util.container.CircularList;
2424	-
2425	-private import tango.util.container.Clink;
2426	-
2427	-public import tango.util.container.Container;
2428	-
2429	-private import tango.util.container.model.IContainer;
2430	-
2431	-/*******************************************************************************
2432	-
2433	- Circular linked list
2434	-
2435	- ---
2436	- Iterator iterator ()
2437	- uint opApply (int delegate(ref V value) dg)
2438	-
2439	- CircularList add (V element)
2440	- CircularList addAt (uint index, V element)
2441	- CircularList append (V element)
2442	- CircularList prepend (V element)
2443	- uint addAt (uint index, IContainer!(V) e)
2444	- uint append (IContainer!(V) e)
2445	- uint prepend (IContainer!(V) e)
2446	-
2447	- bool take (ref V v)
2448	- bool contains (V element)
2449	- V get (uint index)
2450	- uint first (V element, uint startingIndex = 0)
2451	- uint last (V element, uint startingIndex = 0)
2452	-
2453	- V head ()
2454	- V tail ()
2455	- V head (V element)
2456	- V tail (V element)
2457	- V removeHead ()
2458	- V removeTail ()
2459	-
2460	- bool removeAt (uint index)
2461	- uint remove (V element, bool all)
2462	- uint removeRange (uint fromIndex, uint toIndex)
2463	-
2464	- uint replace (V oldElement, V newElement, bool all)
2465	- bool replaceAt (uint index, V element)
2466	-
2467	- uint size ()
2468	- bool isEmpty ()
2469	- V[] toArray (V[] dst)
2470	- CircularList dup ()
2471	- CircularList subset (uint from, uint length)
2472	- CircularList clear ()
2473	- CircularList reset ()
2474	- CircularList check ()
2475	- ---
2476	-
2477	-*******************************************************************************/
2478	-
2479	-class CircularList (V, alias Reap = Container.reap,
2480	- alias Heap = Container.Collect)
2481	- : IContainer!(V)
2482	-{
2483	- // use this type for Allocator configuration
2484	- public alias Clink!(V) Type;
2485	-
2486	- private alias Type *Ref;
2487	-
2488	- private alias Heap!(Type) Alloc;
2489	-
2490	- // number of elements contained
2491	- private uint count;
2492	-
2493	- // configured heap manager
2494	- private Alloc heap;
2495	-
2496	- // mutation tag updates on each change
2497	- private uint mutation;
2498	-
2499	- // head of the list. Null if empty
2500	- private Ref list;
2501	-
2502	-
2503	- /***********************************************************************
2504	-
2505	- Make an empty list
2506	-
2507	- ***********************************************************************/
2508	-
2509	- this ()
2510	- {
2511	- this (null, 0);
2512	- }
2513	-
2514	- /***********************************************************************
2515	-
2516	- Make an configured list
2517	-
2518	- ***********************************************************************/
2519	-
2520	- protected this (Ref h, uint c)
2521	- {
2522	- list = h;
2523	- count = c;
2524	- }
2525	-
2526	- /***********************************************************************
2527	-
2528	- Clean up when deleted
2529	-
2530	- ***********************************************************************/
2531	-
2532	- ~this ()
2533	- {
2534	- reset;
2535	- }
2536	-
2537	- /***********************************************************************
2538	-
2539	- Return the configured allocator
2540	-
2541	- ***********************************************************************/
2542	-
2543	- final Alloc allocator ()
2544	- {
2545	- return heap;
2546	- }
2547	-
2548	- /***********************************************************************
2549	-
2550	- Return a generic iterator for contained elements
2551	-
2552	- ***********************************************************************/
2553	-
2554	- final Iterator iterator ()
2555	- {
2556	- Iterator i = void;
2557	- i.mutation = mutation;
2558	- i.owner = this;
2559	- i.cell = list;
2560	- i.head = list;
2561	- i.bump = &Iterator.fore;
2562	- return i;
2563	- }
2564	-
2565	- /***********************************************************************
2566	-
2567	-
2568	- ***********************************************************************/
2569	-
2570	- final int opApply (int delegate(ref V value) dg)
2571	- {
2572	- return iterator.opApply (dg);
2573	- }
2574	-
2575	- /***********************************************************************
2576	-
2577	- Return the number of elements contained
2578	-
2579	- ***********************************************************************/
2580	-
2581	- final uint size ()
2582	- {
2583	- return count;
2584	- }
2585	-
2586	- /***********************************************************************
2587	-
2588	- Make an independent copy of the list. Elements themselves
2589	- are not cloned
2590	-
2591	- ***********************************************************************/
2592	-
2593	- final CircularList dup ()
2594	- {
2595	- return new CircularList!(V, Reap, Heap) (list ? list.copyList(&heap.allocate) : null, count);
2596	- }
2597	-
2598	- /***********************************************************************
2599	-
2600	- Time complexity: O(n)
2601	-
2602	- ***********************************************************************/
2603	-
2604	- final bool contains (V element)
2605	- {
2606	- if (list)
2607	- return list.find (element) !is null;
2608	- return false;
2609	- }
2610	-
2611	- /***********************************************************************
2612	-
2613	- Time complexity: O(1)
2614	-
2615	- ***********************************************************************/
2616	-
2617	- final V head ()
2618	- {
2619	- return firstCell.value;
2620	- }
2621	-
2622	- /***********************************************************************
2623	-
2624	- Time complexity: O(1)
2625	-
2626	- ***********************************************************************/
2627	-
2628	- final V tail ()
2629	- {
2630	- return lastCell.value;
2631	- }
2632	-
2633	- /***********************************************************************
2634	-
2635	- Time complexity: O(n)
2636	-
2637	- ***********************************************************************/
2638	-
2639	- final V get (uint index)
2640	- {
2641	- return cellAt(index).value;
2642	- }
2643	-
2644	- /***********************************************************************
2645	-
2646	- Time complexity: O(n)
2647	-
2648	- ***********************************************************************/
2649	-
2650	- final uint first (V element, uint startingIndex = 0)
2651	- {
2652	- if (startingIndex < 0)
2653	- startingIndex = 0;
2654	-
2655	- auto p = list;
2656	- if (p is null)
2657	- return uint.max;
2658	-
2659	- for (uint i = 0; true; ++i)
2660	- {
2661	- if (i >= startingIndex && element == p.value)
2662	- return i;
2663	-
2664	- p = p.next;
2665	- if (p is list)
2666	- break;
2667	- }
2668	- return uint.max;
2669	- }
2670	-
2671	- /***********************************************************************
2672	-
2673	- Time complexity: O(n)
2674	-
2675	- ***********************************************************************/
2676	-
2677	- final uint last (V element, uint startingIndex = 0)
2678	- {
2679	- if (count is 0)
2680	- return uint.max;
2681	-
2682	- if (startingIndex >= count)
2683	- startingIndex = count - 1;
2684	-
2685	- if (startingIndex < 0)
2686	- startingIndex = 0;
2687	-
2688	- auto p = cellAt (startingIndex);
2689	- uint i = startingIndex;
2690	- for (;;)
2691	- {
2692	- if (element == p.value)
2693	- return i;
2694	- else
2695	- if (p is list)
2696	- break;
2697	- else
2698	- {
2699	- p = p.prev;
2700	- --i;
2701	- }
2702	- }
2703	- return uint.max;
2704	- }
2705	-
2706	- /***********************************************************************
2707	-
2708	- Time complexity: O(length)
2709	-
2710	- ***********************************************************************/
2711	-
2712	- final CircularList subset (uint from, uint length)
2713	- {
2714	- Ref newlist = null;
2715	-
2716	- if (length > 0)
2717	- {
2718	- checkIndex (from);
2719	- auto p = cellAt (from);
2720	- auto current = newlist = heap.allocate.set (p.value);
2721	-
2722	- for (uint i = 1; i < length; ++i)
2723	- {
2724	- p = p.next;
2725	- if (p is null)
2726	- length = i;
2727	- else
2728	- {
2729	- current.addNext (p.value, &heap.allocate);
2730	- current = current.next;
2731	- }
2732	- }
2733	- }
2734	-
2735	- return new CircularList (newlist, length);
2736	- }
2737	-
2738	- /***********************************************************************
2739	-
2740	- Time complexity: O(1)
2741	-
2742	- ***********************************************************************/
2743	-
2744	- final CircularList clear ()
2745	- {
2746	- return clear (false);
2747	- }
2748	-
2749	- /***********************************************************************
2750	-
2751	- Reset the HashMap contents and optionally configure a new
2752	- heap manager. This releases more memory than clear() does
2753	-
2754	- Time complexity: O(n)
2755	-
2756	- ***********************************************************************/
2757	-
2758	- final CircularList reset ()
2759	- {
2760	- return clear (true);
2761	- }
2762	-
2763	- /***********************************************************************
2764	-
2765	- Time complexity: O(n)
2766	-
2767	- Takes the last element on the list
2768	-
2769	- ***********************************************************************/
2770	-
2771	- final bool take (ref V v)
2772	- {
2773	- if (count)
2774	- {
2775	- v = tail;
2776	- removeTail ();
2777	- return true;
2778	- }
2779	- return false;
2780	- }
2781	-
2782	- /***********************************************************************
2783	-
2784	- Time complexity: O(1)
2785	-
2786	- ***********************************************************************/
2787	-
2788	- final CircularList prepend (V element)
2789	- {
2790	- if (list is null)
2791	- list = heap.allocate.set (element);
2792	- else
2793	- list = list.addPrev (element, &heap.allocate);
2794	- increment;
2795	- return this;
2796	- }
2797	-
2798	- /***********************************************************************
2799	-
2800	- Time complexity: O(1)
2801	-
2802	- ***********************************************************************/
2803	-
2804	- final V head (V element)
2805	- {
2806	- auto p = firstCell;
2807	- auto v = p.value;
2808	- p.value = element;
2809	- mutate;
2810	- return v;
2811	- }
2812	-
2813	- /***********************************************************************
2814	-
2815	- Time complexity: O(1)
2816	-
2817	- ***********************************************************************/
2818	-
2819	- final V removeHead ()
2820	- {
2821	- auto p = firstCell;
2822	- if (p.singleton)
2823	- list = null;
2824	- else
2825	- {
2826	- auto n = p.next;
2827	- p.unlink;
2828	- list = n;
2829	- }
2830	-
2831	- auto v = p.value;
2832	- decrement (p);
2833	- return v;
2834	- }
2835	-
2836	- /***********************************************************************
2837	-
2838	- Time complexity: O(1)
2839	-
2840	- ***********************************************************************/
2841	-
2842	- final CircularList add (V element)
2843	- {
2844	- return append (element);
2845	- }
2846	-
2847	- /***********************************************************************
2848	-
2849	- Time complexity: O(1)
2850	-
2851	- ***********************************************************************/
2852	-
2853	- final CircularList append (V element)
2854	- {
2855	- if (list is null)
2856	- prepend (element);
2857	- else
2858	- {
2859	- list.prev.addNext (element, &heap.allocate);
2860	- increment;
2861	- }
2862	- return this;
2863	- }
2864	-
2865	- /***********************************************************************
2866	-
2867	- Time complexity: O(1)
2868	-
2869	- ***********************************************************************/
2870	-
2871	- final V tail (V element)
2872	- {
2873	- auto p = lastCell;
2874	- auto v = p.value;
2875	- p.value = element;
2876	- mutate;
2877	- return v;
2878	- }
2879	-
2880	- /***********************************************************************
2881	-
2882	- Time complexity: O(1)
2883	-
2884	- ***********************************************************************/
2885	-
2886	- final V removeTail ()
2887	- {
2888	- auto p = lastCell;
2889	- if (p is list)
2890	- list = null;
2891	- else
2892	- p.unlink;
2893	-
2894	- auto v = p.value;
2895	- decrement (p);
2896	- return v;
2897	- }
2898	-
2899	- /***********************************************************************
2900	-
2901	- Time complexity: O(n)
2902	-
2903	- ***********************************************************************/
2904	-
2905	- final CircularList addAt (uint index, V element)
2906	- {
2907	- if (index is 0)
2908	- prepend (element);
2909	- else
2910	- {
2911	- cellAt(index - 1).addNext(element, &heap.allocate);
2912	- increment;
2913	- }
2914	- return this;
2915	- }
2916	-
2917	- /***********************************************************************
2918	-
2919	- Time complexity: O(n)
2920	-
2921	- ***********************************************************************/
2922	-
2923	- final CircularList replaceAt (uint index, V element)
2924	- {
2925	- cellAt(index).value = element;
2926	- mutate;
2927	- return this;
2928	- }
2929	-
2930	- /***********************************************************************
2931	-
2932	- Time complexity: O(n)
2933	-
2934	- ***********************************************************************/
2935	-
2936	- final CircularList removeAt (uint index)
2937	- {
2938	- if (index is 0)
2939	- removeHead;
2940	- else
2941	- {
2942	- auto p = cellAt(index);
2943	- p.unlink;
2944	- decrement (p);
2945	- }
2946	- return this;
2947	- }
2948	-
2949	- /***********************************************************************
2950	-
2951	- Time complexity: O(n)
2952	-
2953	- ***********************************************************************/
2954	-
2955	- final uint remove (V element, bool all)
2956	- {
2957	- auto c = count;
2958	- if (list)
2959	- {
2960	- auto p = list;
2961	- for (;;)
2962	- {
2963	- auto n = p.next;
2964	- if (element == p.value)
2965	- {
2966	- p.unlink;
2967	- decrement (p);
2968	- if (p is list)
2969	- {
2970	- if (p is n)
2971	- {
2972	- list = null;
2973	- break;
2974	- }
2975	- else
2976	- list = n;
2977	- }
2978	-
2979	- if (! all)
2980	- break;
2981	- else
2982	- p = n;
2983	- }
2984	- else
2985	- if (n is list)
2986	- break;
2987	- else
2988	- p = n;
2989	- }
2990	- }
2991	- return c - count;
2992	- }
2993	-
2994	- /***********************************************************************
2995	-
2996	- Time complexity: O(n)
2997	-
2998	- ***********************************************************************/
2999	-
3000	- final uint replace (V oldElement, V newElement, bool all)
3001	- {
3002	- uint c;
3003	- if (list)
3004	- {
3005	- auto p = list;
3006	- do {
3007	- if (oldElement == p.value)
3008	- {
3009	- ++c;
3010	- mutate;
3011	- p.value = newElement;
3012	- if (! all)
3013	- break;
3014	- }
3015	- p = p.next;
3016	- } while (p !is list);
3017	- }
3018	- return c;
3019	- }
3020	-
3021	- /***********************************************************************
3022	-
3023	- Time complexity: O(number of elements in e)
3024	-
3025	- ***********************************************************************/
3026	-
3027	- final uint prepend (IContainer!(V) e)
3028	- {
3029	- Ref hd = null;
3030	- Ref current = null;
3031	- auto c = count;
3032	-
3033	- foreach (element; e)
3034	- {
3035	- increment;
3036	-
3037	- if (hd is null)
3038	- {
3039	- hd = heap.allocate.set(element);
3040	- current = hd;
3041	- }
3042	- else
3043	- {
3044	- current.addNext (element, &heap.allocate);
3045	- current = current.next;
3046	- }
3047	- }
3048	-
3049	- if (list is null)
3050	- list = hd;
3051	- else
3052	- if (hd)
3053	- {
3054	- auto tl = list.prev;
3055	- current.next = list;
3056	- list.prev = current;
3057	- tl.next = hd;
3058	- hd.prev = tl;
3059	- list = hd;
3060	- }
3061	- return count - c;
3062	- }
3063	-
3064	- /***********************************************************************
3065	-
3066	- Time complexity: O(number of elements in e)
3067	-
3068	- ***********************************************************************/
3069	-
3070	- final uint append (IContainer!(V) e)
3071	- {
3072	- auto c = count;
3073	- if (list is null)
3074	- prepend (e);
3075	- else
3076	- {
3077	- auto current = list.prev;
3078	- foreach (element; e)
3079	- {
3080	- increment;
3081	- current.addNext (element, &heap.allocate);
3082	- current = current.next;
3083	- }
3084	- }
3085	- return count - c;
3086	- }
3087	-
3088	- /***********************************************************************
3089	-
3090	- Time complexity: O(size() + number of elements in e)
3091	-
3092	- ***********************************************************************/
3093	-
3094	- final uint addAt (uint index, IContainer!(V) e)
3095	- {
3096	- auto c = count;
3097	- if (list is null \|\| index is 0)
3098	- prepend (e);
3099	- else
3100	- {
3101	- auto current = cellAt (index - 1);
3102	- foreach (element; e)
3103	- {
3104	- increment;
3105	- current.addNext (element, &heap.allocate);
3106	- current = current.next;
3107	- }
3108	- }
3109	- return count - c;
3110	- }
3111	-
3112	- /***********************************************************************
3113	-
3114	- Time complexity: O(n)
3115	-
3116	- ***********************************************************************/
3117	-
3118	- final uint removeRange (uint fromIndex, uint toIndex)
3119	- {
3120	- auto p = cellAt (fromIndex);
3121	- auto last = list.prev;
3122	- auto c = count;
3123	- for (uint i = fromIndex; i <= toIndex; ++i)
3124	- {
3125	- auto n = p.next;
3126	- p.unlink;
3127	- decrement (p);
3128	- if (p is list)
3129	- {
3130	- if (p is last)
3131	- {
3132	- list = null;
3133	- break;
3134	- }
3135	- else
3136	- list = n;
3137	- }
3138	- p = n;
3139	- }
3140	- return c - count;
3141	- }
3142	-
3143	- /***********************************************************************
3144	-
3145	- Copy and return the contained set of values in an array,
3146	- using the optional dst as a recipient (which is resized
3147	- as necessary).
3148	-
3149	- Returns a slice of dst representing the container values.
3150	-
3151	- Time complexity: O(n)
3152	-
3153	- ***********************************************************************/
3154	-
3155	- final V[] toArray (V[] dst = null)
3156	- {
3157	- if (dst.length < count)
3158	- dst.length = count;
3159	-
3160	- int i = 0;
3161	- foreach (v; this)
3162	- dst[i++] = v;
3163	- return dst [0 .. count];
3164	- }
3165	-
3166	- /***********************************************************************
3167	-
3168	- Is this container empty?
3169	-
3170	- Time complexity: O(1)
3171	-
3172	- ***********************************************************************/
3173	-
3174	- final bool isEmpty ()
3175	- {
3176	- return count is 0;
3177	- }
3178	-
3179	- /***********************************************************************
3180	-
3181	-
3182	- ***********************************************************************/
3183	-
3184	- final CircularList check()
3185	- {
3186	- assert(((count is 0) is (list is null)));
3187	- assert((list is null \|\| list.size is count));
3188	-
3189	- if (list)
3190	- {
3191	- uint c = 0;
3192	- auto p = list;
3193	- do {
3194	- assert(p.prev.next is p);
3195	- assert(p.next.prev is p);
3196	- assert(instances(p.value) > 0);
3197	- assert(contains(p.value));
3198	- p = p.next;
3199	- ++c;
3200	- } while (p !is list);
3201	- assert(c is size);
3202	- }
3203	- return this;
3204	- }
3205	-
3206	- /***********************************************************************
3207	-
3208	- Time complexity: O(n)
3209	-
3210	- ***********************************************************************/
3211	-
3212	- private uint instances (V element)
3213	- {
3214	- if (list)
3215	- return list.count (element);
3216	- return 0;
3217	- }
3218	-
3219	- /***********************************************************************
3220	-
3221	-
3222	- ***********************************************************************/
3223	-
3224	- private void checkIndex (uint i)
3225	- {
3226	- if (i >= count)
3227	- throw new Exception ("out of range");
3228	- }
3229	-
3230	- /***********************************************************************
3231	-
3232	- return the first cell, or throw exception if empty
3233	-
3234	- ***********************************************************************/
3235	-
3236	- private Ref firstCell ()
3237	- {
3238	- checkIndex (0);
3239	- return list;
3240	- }
3241	-
3242	- /***********************************************************************
3243	-
3244	- return the last cell, or throw exception if empty
3245	-
3246	- ***********************************************************************/
3247	-
3248	- private Ref lastCell ()
3249	- {
3250	- checkIndex (0);
3251	- return list.prev;
3252	- }
3253	-
3254	- /***********************************************************************
3255	-
3256	- return the index'th cell, or throw exception if bad index
3257	-
3258	- ***********************************************************************/
3259	-
3260	- private Ref cellAt (uint index)
3261	- {
3262	- checkIndex (index);
3263	- return list.nth (index);
3264	- }
3265	-
3266	- /***********************************************************************
3267	-
3268	- Time complexity: O(1)
3269	-
3270	- ***********************************************************************/
3271	-
3272	- private CircularList clear (bool all)
3273	- {
3274	- mutate;
3275	-
3276	- // collect each node if we can't collect all at once
3277	- if (heap.collect(all) is false && count)
3278	- {
3279	- auto p = list;
3280	- do {
3281	- auto n = p.next;
3282	- decrement (p);
3283	- p = n;
3284	- } while (p != list);
3285	- }
3286	-
3287	- list = null;
3288	- count = 0;
3289	- return this;
3290	- }
3291	-
3292	- /***********************************************************************
3293	-
3294	- new element was added
3295	-
3296	- ***********************************************************************/
3297	-
3298	- private void increment ()
3299	- {
3300	- ++mutation;
3301	- ++count;
3302	- }
3303	-
3304	- /***********************************************************************
3305	-
3306	- element was removed
3307	-
3308	- ***********************************************************************/
3309	-
3310	- private void decrement (Ref p)
3311	- {
3312	- Reap (p.value);
3313	- heap.collect (p);
3314	- ++mutation;
3315	- --count;
3316	- }
3317	-
3318	- /***********************************************************************
3319	-
3320	- set was changed
3321	-
3322	- ***********************************************************************/
3323	-
3324	- private void mutate ()
3325	- {
3326	- ++mutation;
3327	- }
3328	-
3329	- /***********************************************************************
3330	-
3331	- Iterator with no filtering
3332	-
3333	- ***********************************************************************/
3334	-
3335	- private struct Iterator
3336	- {
3337	- Ref function(Ref) bump;
3338	- Ref cell,
3339	- head,
3340	- prior;
3341	- CircularList owner;
3342	- uint mutation;
3343	-
3344	- /***************************************************************
3345	-
3346	- Did the container change underneath us?
3347	-
3348	- ***************************************************************/
3349	-
3350	- bool valid ()
3351	- {
3352	- return owner.mutation is mutation;
3353	- }
3354	-
3355	- /***************************************************************
3356	-
3357	- Accesses the next value, and returns false when
3358	- there are no further values to traverse
3359	-
3360	- ***************************************************************/
3361	-
3362	- bool next (ref V v)
3363	- {
3364	- auto n = next;
3365	- return (n) ? v = *n, true : false;
3366	- }
3367	-
3368	- /***************************************************************
3369	-
3370	- Return a pointer to the next value, or null when
3371	- there are no further values to traverse
3372	-
3373	- ***************************************************************/
3374	-
3375	- V* next ()
3376	- {
3377	- V* r;
3378	-
3379	- if (cell)
3380	- {
3381	- prior = cell;
3382	- r = &cell.value;
3383	- cell = bump (cell);
3384	- if (cell is head)
3385	- cell = null;
3386	- }
3387	- return r;
3388	- }
3389	-
3390	- /***************************************************************
3391	-
3392	- Foreach support
3393	-
3394	- ***************************************************************/
3395	-
3396	- int opApply (int delegate(ref V value) dg)
3397	- {
3398	- int result;
3399	-
3400	- auto c = cell;
3401	- while (c)
3402	- {
3403	- prior = c;
3404	- if ((c = bump(c)) is head)
3405	- c = null;
3406	- if ((result = dg(prior.value)) != 0)
3407	- break;
3408	- }
3409	- cell = c;
3410	- return result;
3411	- }
3412	-
3413	- /***************************************************************
3414	-
3415	- Remove value at the current iterator location
3416	-
3417	- ***************************************************************/
3418	-
3419	- bool remove ()
3420	- {
3421	- if (prior)
3422	- {
3423	- auto next = bump (prior);
3424	- if (prior is head)
3425	- if (prior is next)
3426	- owner.list = null;
3427	- else
3428	- head = next;
3429	-
3430	- prior.unlink;
3431	- owner.decrement (prior);
3432	- prior = null;
3433	-
3434	- // ignore this change
3435	- ++mutation;
3436	- return true;
3437	- }
3438	- return false;
3439	- }
3440	-
3441	- /***************************************************************
3442	-
3443	- ***************************************************************/
3444	-
3445	- Iterator reverse ()
3446	- {
3447	- if (bump is &fore)
3448	- bump = &back;
3449	- else
3450	- bump = &fore;
3451	- return *this;
3452	- }
3453	-
3454	- /***************************************************************
3455	-
3456	- ***************************************************************/
3457	-
3458	- private static Ref fore (Ref p)
3459	- {
3460	- return p.next;
3461	- }
3462	-
3463	- /***************************************************************
3464	-
3465	- ***************************************************************/
3466	-
3467	- private static Ref back (Ref p)
3468	- {
3469	- return p.prev;
3470	- }
3471	- }
3472	-}
3473	-
3474	-
3475	-/*******************************************************************************
3476	-
3477	-*******************************************************************************/
3478	-
3479	-debug (CircularList)
3480	-{
3481	- import tango.io.Stdout;
3482	- import tango.core.Thread;
3483	- import tango.time.StopWatch;
3484	-
3485	- void main()
3486	- {
3487	- // usage examples ...
3488	- auto list = new CircularList!(char[]);
3489	- foreach (value; list)
3490	- Stdout (value).newline;
3491	-
3492	- list.add ("foo");
3493	- list.add ("bar");
3494	- list.add ("wumpus");
3495	-
3496	- // implicit generic iteration
3497	- foreach (value; list)
3498	- Stdout (value).newline;
3499	-
3500	- // explicit generic iteration
3501	- foreach (value; list.iterator.reverse)
3502	- Stdout.formatln ("> {}", value);
3503	-
3504	- // generic iteration with optional remove
3505	- auto s = list.iterator;
3506	- foreach (value; s)
3507	- {} //s.remove;
3508	-
3509	- // incremental iteration, with optional remove
3510	- char[] v;
3511	- auto iterator = list.iterator;
3512	- while (iterator.next(v))
3513	- {}//iterator.remove;
3514	-
3515	- // incremental iteration, with optional failfast
3516	- auto it = list.iterator;
3517	- while (it.valid && it.next(v))
3518	- {}
3519	-
3520	- // remove specific element
3521	- list.remove ("wumpus", false);
3522	-
3523	- // remove first element ...
3524	- while (list.take(v))
3525	- Stdout.formatln ("taking {}, {} left", v, list.size);
3526	-
3527	-
3528	- // setup for benchmark, with a set of integers. We
3529	- // use a chunk allocator, and presize the bucket[]
3530	- auto test = new CircularList!(uint, Container.reap, Container.Chunk);
3531	- test.allocator.config (1000, 1000);
3532	- const count = 1_000_000;
3533	- StopWatch w;
3534	-
3535	- // benchmark adding
3536	- w.start;
3537	- for (uint i=count; i--;)
3538	- test.add(i);
3539	- Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop);
3540	-
3541	- // benchmark adding without allocation overhead
3542	- test.clear;
3543	- w.start;
3544	- for (uint i=count; i--;)
3545	- test.add(i);
3546	- Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop);
3547	-
3548	- // benchmark duplication
3549	- w.start;
3550	- auto dup = test.dup;
3551	- Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop);
3552	-
3553	- // benchmark iteration
3554	- w.start;
3555	- foreach (value; test) {}
3556	- Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop);
3557	-
3558	- test.check;
3559	- }
3560	-}
3561	+/*******************************************************************************
3562	+
3563	+ copyright: Copyright (c) 2008 Kris Bell. All rights reserved
3564	+
3565	+ license: BSD style: $(LICENSE)
3566	+
3567	+ version: Apr 2008: Initial release
3568	+
3569	+ authors: Kris
3570	+
3571	+ Since: 0.99.7
3572	+
3573	+ Based upon Doug Lea's Java collection package
3574	+
3575	+*******************************************************************************/
3576	+
3577	+module tango.util.container.CircularList;
3578	+
3579	+private import tango.util.container.Clink;
3580	+
3581	+public import tango.util.container.Container;
3582	+
3583	+private import tango.util.container.model.IContainer;
3584	+
3585	+/*******************************************************************************
3586	+
3587	+ Circular linked list
3588	+
3589	+ ---
3590	+ Iterator iterator ()
3591	+ int opApply (int delegate(ref V value) dg)
3592	+
3593	+ CircularList add (V element)
3594	+ CircularList addAt (size_t index, V element)
3595	+ CircularList append (V element)
3596	+ CircularList prepend (V element)
3597	+ size_t addAt (size_t index, IContainer!(V) e)
3598	+ size_t append (IContainer!(V) e)
3599	+ size_t prepend (IContainer!(V) e)
3600	+
3601	+ bool take (ref V v)
3602	+ bool contains (V element)
3603	+ V get (size_t index)
3604	+ size_t first (V element, size_t startingIndex = 0)
3605	+ size_t last (V element, size_t startingIndex = 0)
3606	+
3607	+ V head ()
3608	+ V tail ()
3609	+ V head (V element)
3610	+ V tail (V element)
3611	+ V removeHead ()
3612	+ V removeTail ()
3613	+
3614	+ bool removeAt (size_t index)
3615	+ size_t remove (V element, bool all)
3616	+ size_t removeRange (size_t fromIndex, size_t toIndex)
3617	+
3618	+ size_t replace (V oldElement, V newElement, bool all)
3619	+ bool replaceAt (size_t index, V element)
3620	+
3621	+ size_t size ()
3622	+ bool isEmpty ()
3623	+ V[] toArray (V[] dst)
3624	+ CircularList dup ()
3625	+ CircularList subset (size_t from, size_t length)
3626	+ CircularList clear ()
3627	+ CircularList reset ()
3628	+ CircularList check ()
3629	+ ---
3630	+
3631	+*******************************************************************************/
3632	+
3633	+class CircularList (V, alias Reap = Container.reap,
3634	+ alias Heap = Container.Collect)
3635	+ : IContainer!(V)
3636	+{
3637	+ // use this type for Allocator configuration
3638	+ public alias Clink!(V) Type;
3639	+
3640	+ private alias Type *Ref;
3641	+
3642	+ private alias Heap!(Type) Alloc;
3643	+
3644	+ // number of elements contained
3645	+ private size_t count;
3646	+
3647	+ // configured heap manager
3648	+ private Alloc heap;
3649	+
3650	+ // mutation tag updates on each change
3651	+ private size_t mutation;
3652	+
3653	+ // head of the list. Null if empty
3654	+ private Ref list;
3655	+
3656	+
3657	+ /***********************************************************************
3658	+
3659	+ Make an empty list
3660	+
3661	+ ***********************************************************************/
3662	+
3663	+ this ()
3664	+ {
3665	+ this (null, 0);
3666	+ }
3667	+
3668	+ /***********************************************************************
3669	+
3670	+ Make an configured list
3671	+
3672	+ ***********************************************************************/
3673	+
3674	+ protected this (Ref h, size_t c)
3675	+ {
3676	+ list = h;
3677	+ count = c;
3678	+ }
3679	+
3680	+ /***********************************************************************
3681	+
3682	+ Clean up when deleted
3683	+
3684	+ ***********************************************************************/
3685	+
3686	+ ~this ()
3687	+ {
3688	+ reset;
3689	+ }
3690	+
3691	+ /***********************************************************************
3692	+
3693	+ Return the configured allocator
3694	+
3695	+ ***********************************************************************/
3696	+
3697	+ final Alloc allocator ()
3698	+ {
3699	+ return heap;
3700	+ }
3701	+
3702	+ /***********************************************************************
3703	+
3704	+ Return a generic iterator for contained elements
3705	+
3706	+ ***********************************************************************/
3707	+
3708	+ final Iterator iterator ()
3709	+ {
3710	+ Iterator i = void;
3711	+ i.mutation = mutation;
3712	+ i.owner = this;
3713	+ i.cell = list;
3714	+ i.head = list;
3715	+ i.bump = &Iterator.fore;
3716	+ return i;
3717	+ }
3718	+
3719	+ /***********************************************************************
3720	+
3721	+
3722	+ ***********************************************************************/
3723	+
3724	+ final int opApply (int delegate(ref V value) dg)
3725	+ {
3726	+ return iterator.opApply (dg);
3727	+ }
3728	+
3729	+ /***********************************************************************
3730	+
3731	+ Return the number of elements contained
3732	+
3733	+ ***********************************************************************/
3734	+
3735	+ final size_t size ()
3736	+ {
3737	+ return count;
3738	+ }
3739	+
3740	+ /***********************************************************************
3741	+
3742	+ Make an independent copy of the list. Elements themselves
3743	+ are not cloned
3744	+
3745	+ ***********************************************************************/
3746	+
3747	+ final CircularList dup ()
3748	+ {
3749	+ return new CircularList!(V, Reap, Heap) (list ? list.copyList(&heap.allocate) : null, count);
3750	+ }
3751	+
3752	+ /***********************************************************************
3753	+
3754	+ Time complexity: O(n)
3755	+
3756	+ ***********************************************************************/
3757	+
3758	+ final bool contains (V element)
3759	+ {
3760	+ if (list)
3761	+ return list.find (element) !is null;
3762	+ return false;
3763	+ }
3764	+
3765	+ /***********************************************************************
3766	+
3767	+ Time complexity: O(1)
3768	+
3769	+ ***********************************************************************/
3770	+
3771	+ final V head ()
3772	+ {
3773	+ return firstCell.value;
3774	+ }
3775	+
3776	+ /***********************************************************************
3777	+
3778	+ Time complexity: O(1)
3779	+
3780	+ ***********************************************************************/
3781	+
3782	+ final V tail ()
3783	+ {
3784	+ return lastCell.value;
3785	+ }
3786	+
3787	+ /***********************************************************************
3788	+
3789	+ Time complexity: O(n)
3790	+
3791	+ ***********************************************************************/
3792	+
3793	+ final V get (size_t index)
3794	+ {
3795	+ return cellAt(index).value;
3796	+ }
3797	+
3798	+ /***********************************************************************
3799	+
3800	+ Time complexity: O(n)
3801	+ Returns size_t.max if no element found.
3802	+
3803	+ ***********************************************************************/
3804	+
3805	+ final size_t first (V element, size_t startingIndex = 0)
3806	+ {
3807	+ if (startingIndex < 0)
3808	+ startingIndex = 0;
3809	+
3810	+ auto p = list;
3811	+ if (p is null)
3812	+ return size_t.max;
3813	+
3814	+ for (size_t i = 0; true; ++i)
3815	+ {
3816	+ if (i >= startingIndex && element == p.value)
3817	+ return i;
3818	+
3819	+ p = p.next;
3820	+ if (p is list)
3821	+ break;
3822	+ }
3823	+ return size_t.max;
3824	+ }
3825	+
3826	+ /***********************************************************************
3827	+
3828	+ Time complexity: O(n)
3829	+ Returns size_t.max if no element found.
3830	+
3831	+ ***********************************************************************/
3832	+
3833	+ final size_t last (V element, size_t startingIndex = 0)
3834	+ {
3835	+ if (count is 0)
3836	+ return size_t.max;
3837	+
3838	+ if (startingIndex >= count)
3839	+ startingIndex = count - 1;
3840	+
3841	+ if (startingIndex < 0)
3842	+ startingIndex = 0;
3843	+
3844	+ auto p = cellAt (startingIndex);
3845	+ size_t i = startingIndex;
3846	+ for (;;)
3847	+ {
3848	+ if (element == p.value)
3849	+ return i;
3850	+ else
3851	+ if (p is list)
3852	+ break;
3853	+ else
3854	+ {
3855	+ p = p.prev;
3856	+ --i;
3857	+ }
3858	+ }
3859	+ return size_t.max;
3860	+ }
3861	+
3862	+ /***********************************************************************
3863	+
3864	+ Time complexity: O(length)
3865	+
3866	+ ***********************************************************************/
3867	+
3868	+ final CircularList subset (size_t from, size_t length)
3869	+ {
3870	+ Ref newlist = null;
3871	+
3872	+ if (length > 0)
3873	+ {
3874	+ checkIndex (from);
3875	+ auto p = cellAt (from);
3876	+ auto current = newlist = heap.allocate.set (p.value);
3877	+
3878	+ for (size_t i = 1; i < length; ++i)
3879	+ {
3880	+ p = p.next;
3881	+ if (p is null)
3882	+ length = i;
3883	+ else
3884	+ {
3885	+ current.addNext (p.value, &heap.allocate);
3886	+ current = current.next;
3887	+ }
3888	+ }
3889	+ }
3890	+
3891	+ return new CircularList (newlist, length);
3892	+ }
3893	+
3894	+ /***********************************************************************
3895	+
3896	+ Time complexity: O(1)
3897	+
3898	+ ***********************************************************************/
3899	+
3900	+ final CircularList clear ()
3901	+ {
3902	+ return clear (false);
3903	+ }
3904	+
3905	+ /***********************************************************************
3906	+
3907	+ Reset the HashMap contents and optionally configure a new
3908	+ heap manager. This releases more memory than clear() does
3909	+
3910	+ Time complexity: O(n)
3911	+
3912	+ ***********************************************************************/
3913	+
3914	+ final CircularList reset ()
3915	+ {
3916	+ return clear (true);
3917	+ }
3918	+
3919	+ /***********************************************************************
3920	+
3921	+ Time complexity: O(n)
3922	+
3923	+ Takes the last element on the list
3924	+
3925	+ ***********************************************************************/
3926	+
3927	+ final bool take (ref V v)
3928	+ {
3929	+ if (count)
3930	+ {
3931	+ v = tail;
3932	+ removeTail ();
3933	+ return true;
3934	+ }
3935	+ return false;
3936	+ }
3937	+
3938	+ /***********************************************************************
3939	+
3940	+ Time complexity: O(1)
3941	+
3942	+ ***********************************************************************/
3943	+
3944	+ final CircularList prepend (V element)
3945	+ {
3946	+ if (list is null)
3947	+ list = heap.allocate.set (element);
3948	+ else
3949	+ list = list.addPrev (element, &heap.allocate);
3950	+ increment;
3951	+ return this;
3952	+ }
3953	+
3954	+ /***********************************************************************
3955	+
3956	+ Time complexity: O(1)
3957	+
3958	+ ***********************************************************************/
3959	+
3960	+ final V head (V element)
3961	+ {
3962	+ auto p = firstCell;
3963	+ auto v = p.value;
3964	+ p.value = element;
3965	+ mutate;
3966	+ return v;
3967	+ }
3968	+
3969	+ /***********************************************************************
3970	+
3971	+ Time complexity: O(1)
3972	+
3973	+ ***********************************************************************/
3974	+
3975	+ final V removeHead ()
3976	+ {
3977	+ auto p = firstCell;
3978	+ if (p.singleton)
3979	+ list = null;
3980	+ else
3981	+ {
3982	+ auto n = p.next;
3983	+ p.unlink;
3984	+ list = n;
3985	+ }
3986	+
3987	+ auto v = p.value;
3988	+ decrement (p);
3989	+ return v;
3990	+ }
3991	+
3992	+ /***********************************************************************
3993	+
3994	+ Time complexity: O(1)
3995	+
3996	+ ***********************************************************************/
3997	+
3998	+ final CircularList add (V element)
3999	+ {
4000	+ return append (element);
4001	+ }
4002	+
4003	+ /***********************************************************************
4004	+
4005	+ Time complexity: O(1)
4006	+
4007	+ ***********************************************************************/
4008	+
4009	+ final CircularList append (V element)
4010	+ {
4011	+ if (list is null)
4012	+ prepend (element);
4013	+ else
4014	+ {
4015	+ list.prev.addNext (element, &heap.allocate);
4016	+ increment;
4017	+ }
4018	+ return this;
4019	+ }
4020	+
4021	+ /***********************************************************************
4022	+
4023	+ Time complexity: O(1)
4024	+
4025	+ ***********************************************************************/
4026	+
4027	+ final V tail (V element)
4028	+ {
4029	+ auto p = lastCell;
4030	+ auto v = p.value;
4031	+ p.value = element;
4032	+ mutate;
4033	+ return v;
4034	+ }
4035	+
4036	+ /***********************************************************************
4037	+
4038	+ Time complexity: O(1)
4039	+
4040	+ ***********************************************************************/
4041	+
4042	+ final V removeTail ()
4043	+ {
4044	+ auto p = lastCell;
4045	+ if (p is list)
4046	+ list = null;
4047	+ else
4048	+ p.unlink;
4049	+
4050	+ auto v = p.value;
4051	+ decrement (p);
4052	+ return v;
4053	+ }
4054	+
4055	+ /***********************************************************************
4056	+
4057	+ Time complexity: O(n)
4058	+
4059	+ ***********************************************************************/
4060	+
4061	+ final CircularList addAt (size_t index, V element)
4062	+ {
4063	+ if (index is 0)
4064	+ prepend (element);
4065	+ else
4066	+ {
4067	+ cellAt(index - 1).addNext(element, &heap.allocate);
4068	+ increment;
4069	+ }
4070	+ return this;
4071	+ }
4072	+
4073	+ /***********************************************************************
4074	+
4075	+ Time complexity: O(n)
4076	+
4077	+ ***********************************************************************/
4078	+
4079	+ final CircularList replaceAt (size_t index, V element)
4080	+ {
4081	+ cellAt(index).value = element;
4082	+ mutate;
4083	+ return this;
4084	+ }
4085	+
4086	+ /***********************************************************************
4087	+
4088	+ Time complexity: O(n)
4089	+
4090	+ ***********************************************************************/
4091	+
4092	+ final CircularList removeAt (size_t index)
4093	+ {
4094	+ if (index is 0)
4095	+ removeHead;
4096	+ else
4097	+ {
4098	+ auto p = cellAt(index);
4099	+ p.unlink;
4100	+ decrement (p);
4101	+ }
4102	+ return this;
4103	+ }
4104	+
4105	+ /***********************************************************************
4106	+
4107	+ Time complexity: O(n)
4108	+
4109	+ ***********************************************************************/
4110	+
4111	+ final size_t remove (V element, bool all)
4112	+ {
4113	+ auto c = count;
4114	+ if (list)
4115	+ {
4116	+ auto p = list;
4117	+ for (;;)
4118	+ {
4119	+ auto n = p.next;
4120	+ if (element == p.value)
4121	+ {
4122	+ p.unlink;
4123	+ decrement (p);
4124	+ if (p is list)
4125	+ {
4126	+ if (p is n)
4127	+ {
4128	+ list = null;
4129	+ break;
4130	+ }
4131	+ else
4132	+ list = n;
4133	+ }
4134	+
4135	+ if (! all)
4136	+ break;
4137	+ else
4138	+ p = n;
4139	+ }
4140	+ else
4141	+ if (n is list)
4142	+ break;
4143	+ else
4144	+ p = n;
4145	+ }
4146	+ }
4147	+ return c - count;
4148	+ }
4149	+
4150	+ /***********************************************************************
4151	+
4152	+ Time complexity: O(n)
4153	+
4154	+ ***********************************************************************/
4155	+
4156	+ final size_t replace (V oldElement, V newElement, bool all)
4157	+ {
4158	+ size_t c;
4159	+ if (list)
4160	+ {
4161	+ auto p = list;
4162	+ do {
4163	+ if (oldElement == p.value)
4164	+ {
4165	+ ++c;
4166	+ mutate;
4167	+ p.value = newElement;
4168	+ if (! all)
4169	+ break;
4170	+ }
4171	+ p = p.next;
4172	+ } while (p !is list);
4173	+ }
4174	+ return c;
4175	+ }
4176	+
4177	+ /***********************************************************************
4178	+
4179	+ Time complexity: O(number of elements in e)
4180	+
4181	+ ***********************************************************************/
4182	+
4183	+ final size_t prepend (IContainer!(V) e)
4184	+ {
4185	+ Ref hd = null;
4186	+ Ref current = null;
4187	+ auto c = count;
4188	+
4189	+ foreach (element; e)
4190	+ {
4191	+ increment;
4192	+
4193	+ if (hd is null)
4194	+ {
4195	+ hd = heap.allocate.set(element);
4196	+ current = hd;
4197	+ }
4198	+ else
4199	+ {
4200	+ current.addNext (element, &heap.allocate);
4201	+ current = current.next;
4202	+ }
4203	+ }
4204	+
4205	+ if (list is null)
4206	+ list = hd;
4207	+ else
4208	+ if (hd)
4209	+ {
4210	+ auto tl = list.prev;
4211	+ current.next = list;
4212	+ list.prev = current;
4213	+ tl.next = hd;
4214	+ hd.prev = tl;
4215	+ list = hd;
4216	+ }
4217	+ return count - c;
4218	+ }
4219	+
4220	+ /***********************************************************************
4221	+
4222	+ Time complexity: O(number of elements in e)
4223	+
4224	+ ***********************************************************************/
4225	+
4226	+ final size_t append (IContainer!(V) e)
4227	+ {
4228	+ auto c = count;
4229	+ if (list is null)
4230	+ prepend (e);
4231	+ else
4232	+ {
4233	+ auto current = list.prev;
4234	+ foreach (element; e)
4235	+ {
4236	+ increment;
4237	+ current.addNext (element, &heap.allocate);
4238	+ current = current.next;
4239	+ }
4240	+ }
4241	+ return count - c;
4242	+ }
4243	+
4244	+ /***********************************************************************
4245	+
4246	+ Time complexity: O(size() + number of elements in e)
4247	+
4248	+ ***********************************************************************/
4249	+
4250	+ final size_t addAt (size_t index, IContainer!(V) e)
4251	+ {
4252	+ auto c = count;
4253	+ if (list is null \|\| index is 0)
4254	+ prepend (e);
4255	+ else
4256	+ {
4257	+ auto current = cellAt (index - 1);
4258	+ foreach (element; e)
4259	+ {
4260	+ increment;
4261	+ current.addNext (element, &heap.allocate);
4262	+ current = current.next;
4263	+ }
4264	+ }
4265	+ return count - c;
4266	+ }
4267	+
4268	+ /***********************************************************************
4269	+
4270	+ Time complexity: O(n)
4271	+
4272	+ ***********************************************************************/
4273	+
4274	+ final size_t removeRange (size_t fromIndex, size_t toIndex)
4275	+ {
4276	+ auto p = cellAt (fromIndex);
4277	+ auto last = list.prev;
4278	+ auto c = count;
4279	+ for (size_t i = fromIndex; i <= toIndex; ++i)
4280	+ {
4281	+ auto n = p.next;
4282	+ p.unlink;
4283	+ decrement (p);
4284	+ if (p is list)
4285	+ {
4286	+ if (p is last)
4287	+ {
4288	+ list = null;
4289	+ break;
4290	+ }
4291	+ else
4292	+ list = n;
4293	+ }
4294	+ p = n;
4295	+ }
4296	+ return c - count;
4297	+ }
4298	+
4299	+ /***********************************************************************
4300	+
4301	+ Copy and return the contained set of values in an array,
4302	+ using the optional dst as a recipient (which is resized
4303	+ as necessary).
4304	+
4305	+ Returns a slice of dst representing the container values.
4306	+
4307	+ Time complexity: O(n)
4308	+
4309	+ ***********************************************************************/
4310	+
4311	+ final V[] toArray (V[] dst = null)
4312	+ {
4313	+ if (dst.length < count)
4314	+ dst.length = count;
4315	+
4316	+ int i = 0;
4317	+ foreach (v; this)
4318	+ dst[i++] = v;
4319	+ return dst [0 .. count];
4320	+ }
4321	+
4322	+ /***********************************************************************
4323	+
4324	+ Is this container empty?
4325	+
4326	+ Time complexity: O(1)
4327	+
4328	+ ***********************************************************************/
4329	+
4330	+ final bool isEmpty ()
4331	+ {
4332	+ return count is 0;
4333	+ }
4334	+
4335	+ /***********************************************************************
4336	+
4337	+
4338	+ ***********************************************************************/
4339	+
4340	+ final CircularList check()
4341	+ {
4342	+ assert(((count is 0) is (list is null)));
4343	+ assert((list is null \|\| list.size is count));
4344	+
4345	+ if (list)
4346	+ {
4347	+ size_t c = 0;
4348	+ auto p = list;
4349	+ do {
4350	+ assert(p.prev.next is p);
4351	+ assert(p.next.prev is p);
4352	+ assert(instances(p.value) > 0);
4353	+ assert(contains(p.value));
4354	+ p = p.next;
4355	+ ++c;
4356	+ } while (p !is list);
4357	+ assert(c is size);
4358	+ }
4359	+ return this;
4360	+ }
4361	+
4362	+ /***********************************************************************
4363	+
4364	+ Time complexity: O(n)
4365	+
4366	+ ***********************************************************************/
4367	+
4368	+ private size_t instances (V element)
4369	+ {
4370	+ if (list)
4371	+ return list.count (element);
4372	+ return 0;
4373	+ }
4374	+
4375	+ /***********************************************************************
4376	+
4377	+
4378	+ ***********************************************************************/
4379	+
4380	+ private void checkIndex (size_t i)
4381	+ {
4382	+ if (i >= count)
4383	+ throw new Exception ("out of range");
4384	+ }
4385	+
4386	+ /***********************************************************************
4387	+
4388	+ return the first cell, or throw exception if empty
4389	+
4390	+ ***********************************************************************/
4391	+
4392	+ private Ref firstCell ()
4393	+ {
4394	+ checkIndex (0);
4395	+ return list;
4396	+ }
4397	+
4398	+ /***********************************************************************
4399	+
4400	+ return the last cell, or throw exception if empty
4401	+
4402	+ ***********************************************************************/
4403	+
4404	+ private Ref lastCell ()
4405	+ {
4406	+ checkIndex (0);
4407	+ return list.prev;
4408	+ }
4409	+
4410	+ /***********************************************************************
4411	+
4412	+ return the index'th cell, or throw exception if bad index
4413	+
4414	+ ***********************************************************************/
4415	+
4416	+ private Ref cellAt (size_t index)
4417	+ {
4418	+ checkIndex (index);
4419	+ return list.nth (index);
4420	+ }
4421	+
4422	+ /***********************************************************************
4423	+
4424	+ Time complexity: O(1)
4425	+
4426	+ ***********************************************************************/
4427	+
4428	+ private CircularList clear (bool all)
4429	+ {
4430	+ mutate;
4431	+
4432	+ // collect each node if we can't collect all at once
4433	+ if (heap.collect(all) is false && count)
4434	+ {
4435	+ auto p = list;
4436	+ do {
4437	+ auto n = p.next;
4438	+ decrement (p);
4439	+ p = n;
4440	+ } while (p != list);
4441	+ }
4442	+
4443	+ list = null;
4444	+ count = 0;
4445	+ return this;
4446	+ }
4447	+
4448	+ /***********************************************************************
4449	+
4450	+ new element was added
4451	+
4452	+ ***********************************************************************/
4453	+
4454	+ private void increment ()
4455	+ {
4456	+ ++mutation;
4457	+ ++count;
4458	+ }
4459	+
4460	+ /***********************************************************************
4461	+
4462	+ element was removed
4463	+
4464	+ ***********************************************************************/
4465	+
4466	+ private void decrement (Ref p)
4467	+ {
4468	+ Reap (p.value);
4469	+ heap.collect (p);
4470	+ ++mutation;
4471	+ --count;
4472	+ }
4473	+
4474	+ /***********************************************************************
4475	+
4476	+ set was changed
4477	+
4478	+ ***********************************************************************/
4479	+
4480	+ private void mutate ()
4481	+ {
4482	+ ++mutation;
4483	+ }
4484	+
4485	+ /***********************************************************************
4486	+
4487	+ Iterator with no filtering
4488	+
4489	+ ***********************************************************************/
4490	+
4491	+ private struct Iterator
4492	+ {
4493	+ Ref function(Ref) bump;
4494	+ Ref cell,
4495	+ head,
4496	+ prior;
4497	+ CircularList owner;
4498	+ size_t mutation;
4499	+
4500	+ /***************************************************************
4501	+
4502	+ Did the container change underneath us?
4503	+
4504	+ ***************************************************************/
4505	+
4506	+ bool valid ()
4507	+ {
4508	+ return owner.mutation is mutation;
4509	+ }
4510	+
4511	+ /***************************************************************
4512	+
4513	+ Accesses the next value, and returns false when
4514	+ there are no further values to traverse
4515	+
4516	+ ***************************************************************/
4517	+
4518	+ bool next (ref V v)
4519	+ {
4520	+ auto n = next;
4521	+ return (n) ? v = *n, true : false;
4522	+ }
4523	+
4524	+ /***************************************************************
4525	+
4526	+ Return a pointer to the next value, or null when
4527	+ there are no further values to traverse
4528	+
4529	+ ***************************************************************/
4530	+
4531	+ V* next ()
4532	+ {
4533	+ V* r;
4534	+
4535	+ if (cell)
4536	+ {
4537	+ prior = cell;
4538	+ r = &cell.value;
4539	+ cell = bump (cell);
4540	+ if (cell is head)
4541	+ cell = null;
4542	+ }
4543	+ return r;
4544	+ }
4545	+
4546	+ /***************************************************************
4547	+
4548	+ Foreach support
4549	+
4550	+ ***************************************************************/
4551	+
4552	+ int opApply (int delegate(ref V value) dg)
4553	+ {
4554	+ int result;
4555	+
4556	+ auto c = cell;
4557	+ while (c)
4558	+ {
4559	+ prior = c;
4560	+ if ((c = bump(c)) is head)
4561	+ c = null;
4562	+ if ((result = dg(prior.value)) != 0)
4563	+ break;
4564	+ }
4565	+ cell = c;
4566	+ return result;
4567	+ }
4568	+
4569	+ /***************************************************************
4570	+
4571	+ Remove value at the current iterator location
4572	+
4573	+ ***************************************************************/
4574	+
4575	+ bool remove ()
4576	+ {
4577	+ if (prior)
4578	+ {
4579	+ auto next = bump (prior);
4580	+ if (prior is head)
4581	+ if (prior is next)
4582	+ owner.list = null;
4583	+ else
4584	+ head = next;
4585	+
4586	+ prior.unlink;
4587	+ owner.decrement (prior);
4588	+ prior = null;
4589	+
4590	+ // ignore this change
4591	+ ++mutation;
4592	+ return true;
4593	+ }
4594	+ return false;
4595	+ }
4596	+
4597	+ /***************************************************************
4598	+
4599	+ ***************************************************************/
4600	+
4601	+ Iterator reverse ()
4602	+ {
4603	+ if (bump is &fore)
4604	+ bump = &back;
4605	+ else
4606	+ bump = &fore;
4607	+ return *this;
4608	+ }
4609	+
4610	+ /***************************************************************
4611	+
4612	+ ***************************************************************/
4613	+
4614	+ private static Ref fore (Ref p)
4615	+ {
4616	+ return p.next;
4617	+ }
4618	+
4619	+ /***************************************************************
4620	+
4621	+ ***************************************************************/
4622	+
4623	+ private static Ref back (Ref p)
4624	+ {
4625	+ return p.prev;
4626	+ }
4627	+ }
4628	+}
4629	+
4630	+
4631	+/*******************************************************************************
4632	+
4633	+*******************************************************************************/
4634	+
4635	+debug (CircularList)
4636	+{
4637	+ import tango.io.Stdout;
4638	+ import tango.core.Thread;
4639	+ import tango.time.StopWatch;
4640	+
4641	+ void main()
4642	+ {
4643	+ // usage examples ...
4644	+ auto list = new CircularList!(char[]);
4645	+ foreach (value; list)
4646	+ Stdout (value).newline;
4647	+
4648	+ list.add ("foo");
4649	+ list.add ("bar");
4650	+ list.add ("wumpus");
4651	+
4652	+ // implicit generic iteration
4653	+ foreach (value; list)
4654	+ Stdout (value).newline;
4655	+
4656	+ // explicit generic iteration
4657	+ foreach (value; list.iterator.reverse)
4658	+ Stdout.formatln ("> {}", value);
4659	+
4660	+ // generic iteration with optional remove
4661	+ auto s = list.iterator;
4662	+ foreach (value; s)
4663	+ {} //s.remove;
4664	+
4665	+ // incremental iteration, with optional remove
4666	+ char[] v;
4667	+ auto iterator = list.iterator;
4668	+ while (iterator.next(v))
4669	+ {}//iterator.remove;
4670	+
4671	+ // incremental iteration, with optional failfast
4672	+ auto it = list.iterator;
4673	+ while (it.valid && it.next(v))
4674	+ {}
4675	+
4676	+ // remove specific element
4677	+ list.remove ("wumpus", false);
4678	+
4679	+ // remove first element ...
4680	+ while (list.take(v))
4681	+ Stdout.formatln ("taking {}, {} left", v, list.size);
4682	+
4683	+
4684	+ // setup for benchmark, with a set of integers. We
4685	+ // use a chunk allocator, and presize the bucket[]
4686	+ auto test = new CircularList!(uint, Container.reap, Container.Chunk);
4687	+ test.allocator.config (1000, 1000);
4688	+ const count = 1_000_000;
4689	+ StopWatch w;
4690	+
4691	+ // benchmark adding
4692	+ w.start;
4693	+ for (uint i=count; i--;)
4694	+ test.add(i);
4695	+ Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop);
4696	+
4697	+ // benchmark adding without allocation overhead
4698	+ test.clear;
4699	+ w.start;
4700	+ for (uint i=count; i--;)
4701	+ test.add(i);
4702	+ Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop);
4703	+
4704	+ // benchmark duplication
4705	+ w.start;
4706	+ auto dup = test.dup;
4707	+ Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop);
4708	+
4709	+ // benchmark iteration
4710	+ w.start;
4711	+ foreach (value; test) {}
4712	+ Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop);
4713	+
4714	+ test.check;
4715	+ }
4716	+}
4717	Index: tango/util/container/HashMap.d
4718	===================================================================
4719	--- tango/util/container/HashMap.d (revision 3995)
4720	+++ tango/util/container/HashMap.d (working copy)
4721	@@ -41,9 +41,9 @@
4722	bool removeKey (K key)
4723	bool take (ref V element)
4724	bool take (K key, ref V element)
4725	- uint remove (V element, bool all)
4726	- uint remove (IContainer!(V) e, bool all)
4727	- uint replace (V oldElement, V newElement, bool all)
4728	+ size_t remove (V element, bool all)
4729	+ size_t remove (IContainer!(V) e, bool all)
4730	+ size_t replace (V oldElement, V newElement, bool all)
4731	bool replacePair (K key, V oldElement, V newElement)
4732
4733	bool add (K key, V element)
4734	@@ -51,15 +51,15 @@
4735	V opIndex (K key)
4736	V* opIn_r (K key)
4737
4738	- uint size ()
4739	+ size_t size ()
4740	bool isEmpty ()
4741	V[] toArray (V[] dst)
4742	HashMap dup ()
4743	HashMap clear ()
4744	HashMap reset ()
4745	- uint buckets ()
4746	+ size_t buckets ()
4747	float threshold ()
4748	- void buckets (uint cap)
4749	+ void buckets (size_t cap)
4750	void threshold (float desired)
4751	Allocator allocator()
4752	---
4753	@@ -82,7 +82,7 @@
4754	private Ref table[];
4755
4756	// number of elements contained
4757	- private uint count;
4758	+ private size_t count;
4759
4760	// the threshold load factor
4761	private float loadFactor;
4762	@@ -91,7 +91,7 @@
4763	private Alloc heap;
4764
4765	// mutation tag updates on each change
4766	- private uint mutation;
4767	+ private size_t mutation;
4768
4769	/***********************************************************************
4770
4771	@@ -169,7 +169,7 @@
4772
4773	***********************************************************************/
4774
4775	- final uint size ()
4776	+ final size_t size ()
4777	{
4778	return count;
4779	}
4780	@@ -526,9 +526,9 @@
4781
4782	************************************************************************/
4783
4784	- final uint remove (IContainer!(V) e, bool all = false)
4785	+ final size_t remove (IContainer!(V) e, bool all = false)
4786	{
4787	- int i = count;
4788	+ auto i = count;
4789	foreach (value; e)
4790	remove (value, all);
4791	return i - count;
4792	@@ -543,7 +543,7 @@
4793
4794	************************************************************************/
4795
4796	- final uint remove (V element, bool all = false)
4797	+ final size_t remove (V element, bool all = false)
4798	{
4799	auto i = count;
4800
4801	@@ -592,9 +592,9 @@
4802
4803	************************************************************************/
4804
4805	- final uint replace (V oldElement, V newElement, bool all = false)
4806	+ final size_t replace (V oldElement, V newElement, bool all = false)
4807	{
4808	- uint i;
4809	+ size_t i;
4810
4811	if (count && oldElement != newElement)
4812	foreach (node; table)
4813	@@ -649,7 +649,7 @@
4814
4815	***********************************************************************/
4816
4817	- final uint buckets ()
4818	+ final size_t buckets ()
4819	{
4820	return table ? table.length : 0;
4821	}
4822	@@ -665,7 +665,7 @@
4823
4824	***********************************************************************/
4825
4826	- final void buckets (uint cap)
4827	+ final void buckets (size_t cap)
4828	{
4829	if (cap < Container.defaultInitialBuckets)
4830	cap = Container.defaultInitialBuckets;
4831	@@ -683,7 +683,7 @@
4832
4833	***********************************************************************/
4834
4835	- final void buckets (uint cap, float threshold)
4836	+ final void buckets (size_t cap, float threshold)
4837	{
4838	loadFactor = threshold;
4839	buckets (cast(int)(cap / threshold) + 1);
4840	@@ -799,9 +799,9 @@
4841
4842	***********************************************************************/
4843
4844	- private uint instances (V element)
4845	+ private size_t instances (V element)
4846	{
4847	- uint c = 0;
4848	+ size_t c = 0;
4849	foreach (node; table)
4850	if (node)
4851	c += node.count (element);
4852	@@ -830,7 +830,7 @@
4853
4854	***********************************************************************/
4855
4856	- private void resize (uint newCap)
4857	+ private void resize (size_t newCap)
4858	{
4859	// Stdout.formatln ("resize {}", newCap);
4860	auto newtab = heap.allocate (newCap);
4861	@@ -955,12 +955,12 @@
4862
4863	private struct Iterator
4864	{
4865	- uint row;
4866	+ size_t row;
4867	Ref cell,
4868	prior;
4869	Ref[] table;
4870	HashMap owner;
4871	- uint mutation;
4872	+ size_t mutation;
4873
4874	/***************************************************************
4875
4876	Index: tango/util/container/Container.d
4877	===================================================================
4878	--- tango/util/container/Container.d (revision 3995)
4879	+++ tango/util/container/Container.d (working copy)
4880	@@ -32,7 +32,7 @@
4881
4882	***********************************************************************/
4883
4884	- static int defaultInitialBuckets = 31;
4885	+ static size_t defaultInitialBuckets = 31;
4886
4887	/***********************************************************************
4888
4889	@@ -67,14 +67,14 @@
4890
4891	***********************************************************************/
4892
4893	- static uint hash(K) (K k, uint length)
4894	+ static size_t hash(K) (K k, size_t length)
4895	{
4896	static if (is(K : int) \|\| is(K : uint) \|\|
4897	is(K : long) \|\| is(K : ulong) \|\|
4898	is(K : short) \|\| is(K : ushort) \|\|
4899	is(K : byte) \|\| is(K : ubyte) \|\|
4900	is(K : char) \|\| is(K : wchar) \|\| is (K : dchar))
4901	- return cast(uint) (k % length);
4902	+ return cast(size_t) (k % length);
4903	else
4904	return (typeid(K).getHash(&k) & 0x7FFFFFFF) % length;
4905	}
4906	@@ -104,7 +104,7 @@
4907
4908	***************************************************************/
4909
4910	- T*[] allocate (uint count)
4911	+ T*[] allocate (size_t count)
4912	{
4913	return new T*[count];
4914	}
4915	@@ -191,7 +191,7 @@
4916
4917	***************************************************************/
4918
4919	- T*[] allocate (uint count)
4920	+ T*[] allocate (size_t count)
4921	{
4922	return (cast(T*) calloc(count, (T).sizeof)) [0 .. count];
4923	}
4924	@@ -322,7 +322,7 @@
4925
4926	***************************************************************/
4927
4928	- T*[] allocate (uint count)
4929	+ T*[] allocate (size_t count)
4930	{
4931	return (cast(T*) calloc(count, (T).sizeof)) [0 .. count];
4932	}
4933	Index: tango/util/container/LinkedList.d
4934	===================================================================
4935	--- tango/util/container/LinkedList.d (revision 3995)
4936	+++ tango/util/container/LinkedList.d (working copy)
4937	@@ -38,32 +38,32 @@
4938	V removeTail ()
4939
4940	bool contains (V value)
4941	- uint first (V value, uint startingIndex = 0)
4942	- uint last (V value, uint startingIndex = 0)
4943	+ size_t first (V value, size_t startingIndex = 0)
4944	+ size_t last (V value, size_t startingIndex = 0)
4945
4946	LinkedList add (V value)
4947	LinkedList prepend (V value)
4948	- uint prepend (IContainer!(V) e)
4949	+ size_t prepend (IContainer!(V) e)
4950	LinkedList append (V value)
4951	- uint append (IContainer!(V) e)
4952	- LinkedList addAt (uint index, V value)
4953	- uint addAt (uint index, IContainer!(V) e)
4954	+ size_t append (IContainer!(V) e)
4955	+ LinkedList addAt (size_t index, V value)
4956	+ size_t addAt (size_t index, IContainer!(V) e)
4957
4958	- V get (uint index)
4959	+ V get (size_t index)
4960	bool take (ref V v)
4961	- uint remove (V value, bool all)
4962	- bool removeAt (uint index)
4963	- uint removeRange (uint fromIndex, uint toIndex)
4964	- uint replace (V oldElement, V newElement, bool all)
4965	- bool replaceAt (uint index, V value)
4966	+ size_t remove (V value, bool all)
4967	+ bool removeAt (size_t index)
4968	+ size_t removeRange (size_t fromIndex, size_t toIndex)
4969	+ size_t replace (V oldElement, V newElement, bool all)
4970	+ bool replaceAt (size_t index, V value)
4971
4972	LinkedList clear ()
4973	LinkedList reset ()
4974
4975	- LinkedList subset (uint from, uint length = int.max)
4976	+ LinkedList subset (size_t from, size_t length = int.max)
4977	LinkedList dup ()
4978
4979	- uint size ()
4980	+ size_t size ()
4981	bool isEmpty ()
4982	V[] toArray (V[] dst)
4983	LinkedList sort (Compare!(V) cmp)
4984	@@ -85,13 +85,13 @@
4985	private alias Heap!(Type) Alloc;
4986
4987	// number of elements contained
4988	- private uint count;
4989	+ private size_t count;
4990
4991	// configured heap manager
4992	private Alloc heap;
4993
4994	// mutation tag updates on each change
4995	- private uint mutation;
4996	+ private size_t mutation;
4997
4998	// head of the list. Null if empty
4999	private Ref list;
5000	@@ -173,7 +173,7 @@
5001
5002	***********************************************************************/
5003
5004	- final uint size ()
5005	+ final size_t size ()
5006	{
5007	return count;
5008	}
5009	@@ -232,7 +232,7 @@
5010
5011	***********************************************************************/
5012
5013	- final V get (uint index)
5014	+ final V get (size_t index)
5015	{
5016	return cellAt(index).value;
5017	}
5018	@@ -240,13 +240,14 @@
5019	/***********************************************************************
5020
5021	Time complexity: O(n)
5022	-
5023	+ Returns size_t.max if no element found.
5024	+
5025	***********************************************************************/
5026
5027	- final uint first (V value, uint startingIndex = 0)
5028	+ final size_t first (V value, size_t startingIndex = 0)
5029	{
5030	if (list is null \|\| startingIndex >= count)
5031	- return uint.max;
5032	+ return size_t.max;
5033
5034	if (startingIndex < 0)
5035	startingIndex = 0;
5036	@@ -258,25 +259,26 @@
5037	if (i >= 0)
5038	return i + startingIndex;
5039	}
5040	- return uint.max;
5041	+ return size_t.max;
5042	}
5043
5044	/***********************************************************************
5045
5046	Time complexity: O(n)
5047	-
5048	+ Returns size_t.max if no element found.
5049	+
5050	***********************************************************************/
5051
5052	- final uint last (V value, uint startingIndex = 0)
5053	+ final size_t last (V value, size_t startingIndex = 0)
5054	{
5055	if (list is null)
5056	- return uint.max;
5057	+ return size_t.max;
5058
5059	auto i = 0;
5060	if (startingIndex >= count)
5061	startingIndex = count - 1;
5062
5063	- auto index = uint.max;
5064	+ auto index = size_t.max;
5065	auto p = list;
5066	while (i <= startingIndex && p)
5067	{
5068	@@ -294,7 +296,7 @@
5069
5070	***********************************************************************/
5071
5072	- final LinkedList subset (uint from, uint length = int.max)
5073	+ final LinkedList subset (size_t from, size_t length = int.max)
5074	{
5075	Ref newlist = null;
5076
5077	@@ -410,7 +412,7 @@
5078
5079	***********************************************************************/
5080
5081	- final uint remove (V value, bool all = false)
5082	+ final size_t remove (V value, bool all = false)
5083	{
5084	auto c = count;
5085	if (c)
5086	@@ -453,9 +455,9 @@
5087
5088	***********************************************************************/
5089
5090	- final uint replace (V oldElement, V newElement, bool all = false)
5091	+ final size_t replace (V oldElement, V newElement, bool all = false)
5092	{
5093	- uint c;
5094	+ size_t c;
5095	if (count && oldElement != newElement)
5096	{
5097	auto p = list.find (oldElement);
5098	@@ -566,7 +568,7 @@
5099
5100	***********************************************************************/
5101
5102	- final LinkedList addAt (uint index, V value)
5103	+ final LinkedList addAt (size_t index, V value)
5104	{
5105	if (index is 0)
5106	prepend (value);
5107	@@ -584,7 +586,7 @@
5108
5109	***********************************************************************/
5110
5111	- final LinkedList removeAt (uint index)
5112	+ final LinkedList removeAt (size_t index)
5113	{
5114	if (index is 0)
5115	removeHead;
5116	@@ -604,7 +606,7 @@
5117
5118	***********************************************************************/
5119
5120	- final LinkedList replaceAt (uint index, V value)
5121	+ final LinkedList replaceAt (size_t index, V value)
5122	{
5123	cellAt(index).value = value;
5124	mutate;
5125	@@ -617,7 +619,7 @@
5126
5127	***********************************************************************/
5128
5129	- final uint prepend (IContainer!(V) e)
5130	+ final size_t prepend (IContainer!(V) e)
5131	{
5132	auto c = count;
5133	splice_ (e, null, list);
5134	@@ -630,7 +632,7 @@
5135
5136	***********************************************************************/
5137
5138	- final uint append (IContainer!(V) e)
5139	+ final size_t append (IContainer!(V) e)
5140	{
5141	auto c = count;
5142	if (list is null)
5143	@@ -646,7 +648,7 @@
5144
5145	***********************************************************************/
5146
5147	- final uint addAt (uint index, IContainer!(V) e)
5148	+ final size_t addAt (size_t index, IContainer!(V) e)
5149	{
5150	auto c = count;
5151	if (index is 0)
5152	@@ -665,7 +667,7 @@
5153
5154	***********************************************************************/
5155
5156	- final uint removeRange (uint fromIndex, uint toIndex)
5157	+ final size_t removeRange (size_t fromIndex, size_t toIndex)
5158	{
5159	auto c = count;
5160	if (fromIndex <= toIndex)
5161	@@ -754,7 +756,7 @@
5162
5163	***********************************************************************/
5164
5165	- private uint instances (V value)
5166	+ private size_t instances (V value)
5167	{
5168	if (count is 0)
5169	return 0;
5170	@@ -786,7 +788,7 @@
5171
5172	***********************************************************************/
5173
5174	- private Ref cellAt (uint index)
5175	+ private Ref cellAt (size_t index)
5176	{
5177	checkIndex (index);
5178	return list.nth (index);
5179	@@ -796,7 +798,7 @@
5180
5181	***********************************************************************/
5182
5183	- private void checkIndex (uint index)
5184	+ private void checkIndex (size_t index)
5185	{
5186	if (index >= count)
5187	throw new Exception ("out of range");
5188	@@ -915,7 +917,7 @@
5189	Ref* hook,
5190	prior;
5191	LinkedList owner;
5192	- uint mutation;
5193	+ size_t mutation;
5194
5195	/***************************************************************
5196

Ticket #1303: x86_64-changes-r3995

Download in other formats: