CircularList.d

Revision 4008, 34.6 kB (checked in by larsivi, 1 month ago)
Fixed eol style for container package, refs #1303
Property svn:eol-style set to `native`

Line
1	/*******************************************************************************
2
3	copyright: Copyright (c) 2008 Kris Bell. All rights reserved
4
5	license: BSD style: $(LICENSE)
6
7	version: Apr 2008: Initial release
8
9	authors: Kris
10
11	Since: 0.99.7
12
13	Based upon Doug Lea's Java collection package
14
15	*******************************************************************************/
16
17	module tango.util.container.CircularList;
18
19	private import tango.util.container.Clink;
20
21	public import tango.util.container.Container;
22
23	private import tango.util.container.model.IContainer;
24
25	/*******************************************************************************
26
27	Circular linked list
28
29	---
30	Iterator iterator ()
31	uint opApply (int delegate(ref V value) dg)
32
33	CircularList add (V element)
34	CircularList addAt (uint index, V element)
35	CircularList append (V element)
36	CircularList prepend (V element)
37	uint addAt (uint index, IContainer!(V) e)
38	uint append (IContainer!(V) e)
39	uint prepend (IContainer!(V) e)
40
41	bool take (ref V v)
42	bool contains (V element)
43	V get (uint index)
44	uint first (V element, uint startingIndex = 0)
45	uint last (V element, uint startingIndex = 0)
46
47	V head ()
48	V tail ()
49	V head (V element)
50	V tail (V element)
51	V removeHead ()
52	V removeTail ()
53
54	bool removeAt (uint index)
55	uint remove (V element, bool all)
56	uint removeRange (uint fromIndex, uint toIndex)
57
58	uint replace (V oldElement, V newElement, bool all)
59	bool replaceAt (uint index, V element)
60
61	uint size ()
62	bool isEmpty ()
63	V[] toArray (V[] dst)
64	CircularList dup ()
65	CircularList subset (uint from, uint length)
66	CircularList clear ()
67	CircularList reset ()
68	CircularList check ()
69	---
70
71	*******************************************************************************/
72
73	class CircularList (V, alias Reap = Container.reap,
74	alias Heap = Container.Collect)
75	: IContainer!(V)
76	{
77	// use this type for Allocator configuration
78	public alias Clink!(V) Type;
79
80	private alias Type *Ref;
81
82	private alias Heap!(Type) Alloc;
83
84	// number of elements contained
85	private uint count;
86
87	// configured heap manager
88	private Alloc heap;
89
90	// mutation tag updates on each change
91	private uint mutation;
92
93	// head of the list. Null if empty
94	private Ref list;
95
96
97	/***********************************************************************
98
99	Make an empty list
100
101	***********************************************************************/
102
103	this ()
104	{
105	this (null, 0);
106	}
107
108	/***********************************************************************
109
110	Make an configured list
111
112	***********************************************************************/
113
114	protected this (Ref h, uint c)
115	{
116	list = h;
117	count = c;
118	}
119
120	/***********************************************************************
121
122	Clean up when deleted
123
124	***********************************************************************/
125
126	~this ()
127	{
128	reset;
129	}
130
131	/***********************************************************************
132
133	Return the configured allocator
134
135	***********************************************************************/
136
137	final Alloc allocator ()
138	{
139	return heap;
140	}
141
142	/***********************************************************************
143
144	Return a generic iterator for contained elements
145
146	***********************************************************************/
147
148	final Iterator iterator ()
149	{
150	Iterator i = void;
151	i.mutation = mutation;
152	i.owner = this;
153	i.cell = list;
154	i.head = list;
155	i.bump = &Iterator.fore;
156	return i;
157	}
158
159	/***********************************************************************
160
161
162	***********************************************************************/
163
164	final int opApply (int delegate(ref V value) dg)
165	{
166	return iterator.opApply (dg);
167	}
168
169	/***********************************************************************
170
171	Return the number of elements contained
172
173	***********************************************************************/
174
175	final uint size ()
176	{
177	return count;
178	}
179
180	/***********************************************************************
181
182	Make an independent copy of the list. Elements themselves
183	are not cloned
184
185	***********************************************************************/
186
187	final CircularList dup ()
188	{
189	return new CircularList!(V, Reap, Heap) (list ? list.copyList(&heap.allocate) : null, count);
190	}
191
192	/***********************************************************************
193
194	Time complexity: O(n)
195
196	***********************************************************************/
197
198	final bool contains (V element)
199	{
200	if (list)
201	return list.find (element) !is null;
202	return false;
203	}
204
205	/***********************************************************************
206
207	Time complexity: O(1)
208
209	***********************************************************************/
210
211	final V head ()
212	{
213	return firstCell.value;
214	}
215
216	/***********************************************************************
217
218	Time complexity: O(1)
219
220	***********************************************************************/
221
222	final V tail ()
223	{
224	return lastCell.value;
225	}
226
227	/***********************************************************************
228
229	Time complexity: O(n)
230
231	***********************************************************************/
232
233	final V get (uint index)
234	{
235	return cellAt(index).value;
236	}
237
238	/***********************************************************************
239
240	Time complexity: O(n)
241
242	***********************************************************************/
243
244	final uint first (V element, uint startingIndex = 0)
245	{
246	if (startingIndex < 0)
247	startingIndex = 0;
248
249	auto p = list;
250	if (p is null)
251	return uint.max;
252
253	for (uint i = 0; true; ++i)
254	{
255	if (i >= startingIndex && element == p.value)
256	return i;
257
258	p = p.next;
259	if (p is list)
260	break;
261	}
262	return uint.max;
263	}
264
265	/***********************************************************************
266
267	Time complexity: O(n)
268
269	***********************************************************************/
270
271	final uint last (V element, uint startingIndex = 0)
272	{
273	if (count is 0)
274	return uint.max;
275
276	if (startingIndex >= count)
277	startingIndex = count - 1;
278
279	if (startingIndex < 0)
280	startingIndex = 0;
281
282	auto p = cellAt (startingIndex);
283	uint i = startingIndex;
284	for (;;)
285	{
286	if (element == p.value)
287	return i;
288	else
289	if (p is list)
290	break;
291	else
292	{
293	p = p.prev;
294	--i;
295	}
296	}
297	return uint.max;
298	}
299
300	/***********************************************************************
301
302	Time complexity: O(length)
303
304	***********************************************************************/
305
306	final CircularList subset (uint from, uint length)
307	{
308	Ref newlist = null;
309
310	if (length > 0)
311	{
312	checkIndex (from);
313	auto p = cellAt (from);
314	auto current = newlist = heap.allocate.set (p.value);
315
316	for (uint i = 1; i < length; ++i)
317	{
318	p = p.next;
319	if (p is null)
320	length = i;
321	else
322	{
323	current.addNext (p.value, &heap.allocate);
324	current = current.next;
325	}
326	}
327	}
328
329	return new CircularList (newlist, length);
330	}
331
332	/***********************************************************************
333
334	Time complexity: O(1)
335
336	***********************************************************************/
337
338	final CircularList clear ()
339	{
340	return clear (false);
341	}
342
343	/***********************************************************************
344
345	Reset the HashMap contents and optionally configure a new
346	heap manager. This releases more memory than clear() does
347
348	Time complexity: O(n)
349
350	***********************************************************************/
351
352	final CircularList reset ()
353	{
354	return clear (true);
355	}
356
357	/***********************************************************************
358
359	Time complexity: O(n)
360
361	Takes the last element on the list
362
363	***********************************************************************/
364
365	final bool take (ref V v)
366	{
367	if (count)
368	{
369	v = tail;
370	removeTail ();
371	return true;
372	}
373	return false;
374	}
375
376	/***********************************************************************
377
378	Time complexity: O(1)
379
380	***********************************************************************/
381
382	final CircularList prepend (V element)
383	{
384	if (list is null)
385	list = heap.allocate.set (element);
386	else
387	list = list.addPrev (element, &heap.allocate);
388	increment;
389	return this;
390	}
391
392	/***********************************************************************
393
394	Time complexity: O(1)
395
396	***********************************************************************/
397
398	final V head (V element)
399	{
400	auto p = firstCell;
401	auto v = p.value;
402	p.value = element;
403	mutate;
404	return v;
405	}
406
407	/***********************************************************************
408
409	Time complexity: O(1)
410
411	***********************************************************************/
412
413	final V removeHead ()
414	{
415	auto p = firstCell;
416	if (p.singleton)
417	list = null;
418	else
419	{
420	auto n = p.next;
421	p.unlink;
422	list = n;
423	}
424
425	auto v = p.value;
426	decrement (p);
427	return v;
428	}
429
430	/***********************************************************************
431
432	Time complexity: O(1)
433
434	***********************************************************************/
435
436	final CircularList add (V element)
437	{
438	return append (element);
439	}
440
441	/***********************************************************************
442
443	Time complexity: O(1)
444
445	***********************************************************************/
446
447	final CircularList append (V element)
448	{
449	if (list is null)
450	prepend (element);
451	else
452	{
453	list.prev.addNext (element, &heap.allocate);
454	increment;
455	}
456	return this;
457	}
458
459	/***********************************************************************
460
461	Time complexity: O(1)
462
463	***********************************************************************/
464
465	final V tail (V element)
466	{
467	auto p = lastCell;
468	auto v = p.value;
469	p.value = element;
470	mutate;
471	return v;
472	}
473
474	/***********************************************************************
475
476	Time complexity: O(1)
477
478	***********************************************************************/
479
480	final V removeTail ()
481	{
482	auto p = lastCell;
483	if (p is list)
484	list = null;
485	else
486	p.unlink;
487
488	auto v = p.value;
489	decrement (p);
490	return v;
491	}
492
493	/***********************************************************************
494
495	Time complexity: O(n)
496
497	***********************************************************************/
498
499	final CircularList addAt (uint index, V element)
500	{
501	if (index is 0)
502	prepend (element);
503	else
504	{
505	cellAt(index - 1).addNext(element, &heap.allocate);
506	increment;
507	}
508	return this;
509	}
510
511	/***********************************************************************
512
513	Time complexity: O(n)
514
515	***********************************************************************/
516
517	final CircularList replaceAt (uint index, V element)
518	{
519	cellAt(index).value = element;
520	mutate;
521	return this;
522	}
523
524	/***********************************************************************
525
526	Time complexity: O(n)
527
528	***********************************************************************/
529
530	final CircularList removeAt (uint index)
531	{
532	if (index is 0)
533	removeHead;
534	else
535	{
536	auto p = cellAt(index);
537	p.unlink;
538	decrement (p);
539	}
540	return this;
541	}
542
543	/***********************************************************************
544
545	Time complexity: O(n)
546
547	***********************************************************************/
548
549	final uint remove (V element, bool all)
550	{
551	auto c = count;
552	if (list)
553	{
554	auto p = list;
555	for (;;)
556	{
557	auto n = p.next;
558	if (element == p.value)
559	{
560	p.unlink;
561	decrement (p);
562	if (p is list)
563	{
564	if (p is n)
565	{
566	list = null;
567	break;
568	}
569	else
570	list = n;
571	}
572
573	if (! all)
574	break;
575	else
576	p = n;
577	}
578	else
579	if (n is list)
580	break;
581	else
582	p = n;
583	}
584	}
585	return c - count;
586	}
587
588	/***********************************************************************
589
590	Time complexity: O(n)
591
592	***********************************************************************/
593
594	final uint replace (V oldElement, V newElement, bool all)
595	{
596	uint c;
597	if (list)
598	{
599	auto p = list;
600	do {
601	if (oldElement == p.value)
602	{
603	++c;
604	mutate;
605	p.value = newElement;
606	if (! all)
607	break;
608	}
609	p = p.next;
610	} while (p !is list);
611	}
612	return c;
613	}
614
615	/***********************************************************************
616
617	Time complexity: O(number of elements in e)
618
619	***********************************************************************/
620
621	final uint prepend (IContainer!(V) e)
622	{
623	Ref hd = null;
624	Ref current = null;
625	auto c = count;
626
627	foreach (element; e)
628	{
629	increment;
630
631	if (hd is null)
632	{
633	hd = heap.allocate.set(element);
634	current = hd;
635	}
636	else
637	{
638	current.addNext (element, &heap.allocate);
639	current = current.next;
640	}
641	}
642
643	if (list is null)
644	list = hd;
645	else
646	if (hd)
647	{
648	auto tl = list.prev;
649	current.next = list;
650	list.prev = current;
651	tl.next = hd;
652	hd.prev = tl;
653	list = hd;
654	}
655	return count - c;
656	}
657
658	/***********************************************************************
659
660	Time complexity: O(number of elements in e)
661
662	***********************************************************************/
663
664	final uint append (IContainer!(V) e)
665	{
666	auto c = count;
667	if (list is null)
668	prepend (e);
669	else
670	{
671	auto current = list.prev;
672	foreach (element; e)
673	{
674	increment;
675	current.addNext (element, &heap.allocate);
676	current = current.next;
677	}
678	}
679	return count - c;
680	}
681
682	/***********************************************************************
683
684	Time complexity: O(size() + number of elements in e)
685
686	***********************************************************************/
687
688	final uint addAt (uint index, IContainer!(V) e)
689	{
690	auto c = count;
691	if (list is null \|\| index is 0)
692	prepend (e);
693	else
694	{
695	auto current = cellAt (index - 1);
696	foreach (element; e)
697	{
698	increment;
699	current.addNext (element, &heap.allocate);
700	current = current.next;
701	}
702	}
703	return count - c;
704	}
705
706	/***********************************************************************
707
708	Time complexity: O(n)
709
710	******************************************