Mercurial > projects > ldc

comparison tango/tango/util/collection/ArrayBag.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
1 /*
2 File: ArrayBag.d
3
4 Originally written by Doug Lea and released into the public domain.
5 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
6 Inc, Loral, and everyone contributing, testing, and using this code.
7
8 History:
9 Date Who What
10 24Sep95 dl@cs.oswego.edu Create from store.d working file
11 13Oct95 dl Changed protection statuses
12
13 */
14
15
16 module tango.util.collection.ArrayBag;
17
18 private import tango.core.Exception;
19
20 private import tango.util.collection.model.GuardIterator;
21
22 private import tango.util.collection.impl.CLCell,
23 tango.util.collection.impl.BagCollection,
24 tango.util.collection.impl.AbstractIterator;
25
26
27
28 /**
29 *
30 * Linked Buffer implementation of Bags. The Bag consists of
31 * any number of buffers holding elements, arranged in a list.
32 * Each buffer holds an array of elements. The size of each
33 * buffer is the value of chunkSize that was current during the
34 * operation that caused the Bag to grow. The chunkSize() may
35 * be adjusted at any time. (It is not considered a version change.)
36 *
37 * <P>
38 * All but the final buffer is always kept full.
39 * When a buffer has no elements, it is released (so is
40 * available for garbage collection).
41 * <P>
42 * ArrayBags are good choices for collections in which
43 * you merely put a lot of things in, and then look at
44 * them via enumerations, but don't often look for
45 * particular elements.
46 *
47 *
48 author: Doug Lea
49 * @version 0.93
50 *
51 * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
52 **/
53
54 public class ArrayBag(T) : BagCollection!(T)
55 {
56 alias CLCell!(T[]) CLCellT;
57
58 alias BagCollection!(T).remove remove;
59 alias BagCollection!(T).removeAll removeAll;
60
61 /**
62 * The default chunk size to use for buffers
63 **/
64
65 public static int defaultChunkSize = 32;
66
67 // instance variables
68
69 /**
70 * The last node of the circular list of chunks. Null if empty.
71 **/
72
73 package CLCellT tail;
74
75 /**
76 * The number of elements of the tail node actually used. (all others
77 * are kept full).
78 **/
79 protected int lastCount;
80
81 /**
82 * The chunk size to use for making next buffer
83 **/
84
85 protected int chunkSize_;
86
87 // constructors
88
89 /**
90 * Make an empty buffer.
91 **/
92 public this ()
93 {
94 this (null, 0, null, 0, defaultChunkSize);
95 }
96
97 /**
98 * Make an empty buffer, using the supplied element screener.
99 **/
100
101 public this (Predicate s)
102 {
103 this (s, 0, null, 0, defaultChunkSize);
104 }
105
106 /**
107 * Special version of constructor needed by clone()
108 **/
109 protected this (Predicate s, int n, CLCellT t, int lc, int cs)
110 {
111 super (s);
112 count = n;
113 tail = t;
114 lastCount = lc;
115 chunkSize_ = cs;
116 }
117
118 /**
119 * Make an independent copy. Does not clone elements.
120 **/
121
122 public final ArrayBag duplicate ()
123 {
124 if (count is 0)
125 return new ArrayBag (screener);
126 else
127 {
128 CLCellT h = tail.copyList();
129 CLCellT p = h;
130
131 do {
132 T[] obuff = p.element();
133 T[] nbuff = new T[obuff.length];
134
135 for (int i = 0; i < obuff.length; ++i)
136 nbuff[i] = obuff[i];
137
138 p.element(nbuff);
139 p = p.next();
140 } while (p !is h);
141
142 return new ArrayBag (screener, count, h, lastCount, chunkSize_);
143 }
144 }
145
146
147 /**
148 * Report the chunk size used when adding new buffers to the list
149 **/
150
151 public final int chunkSize()
152 {
153 return chunkSize_;
154 }
155
156 /**
157 * Set the chunk size to be used when adding new buffers to the
158 * list during future add() operations.
159 * Any value greater than 0 is OK. (A value of 1 makes this a
160 * into very slow simulation of a linked list!)
161 **/
162
163 public final void chunkSize (int newChunkSize)
164 {
165 if (newChunkSize > 0)
166 chunkSize_ = newChunkSize;
167 else
168 throw new IllegalArgumentException("Attempt to set negative chunk size value");
169 }
170
171 // Collection methods
172
173 /*
174 This code is pretty repetitive, but I don't know a nice way to
175 separate traversal logic from actions
176 */
177
178 /**
179 * Implements tango.util.collection.impl.Collection.Collection.contains
180 * Time complexity: O(n).
181 * See_Also: tango.util.collection.impl.Collection.Collection.contains
182 **/
183 public final bool contains(T element)
184 {
185 if (!isValidArg(element) || count is 0)
186 return false;
187
188 CLCellT p = tail.next();
189
190 for (;;)
191 {
192 T[] buff = p.element();
193 bool isLast = p is tail;
194
195 int n;
196 if (isLast)
197 n = lastCount;
198 else
199 n = buff.length;
200
201 for (int i = 0; i < n; ++i)
202 {
203 if (buff[i] == (element))
204 return true;
205 }
206
207 if (isLast)
208 break;
209 else
210 p = p.next();
211 }
212 return false;
213 }
214
215 /**
216 * Implements tango.util.collection.impl.Collection.Collection.instances
217 * Time complexity: O(n).
218 * See_Also: tango.util.collection.impl.Collection.instances
219 **/
220 public final uint instances(T element)
221 {
222 if (!isValidArg(element) || count is 0)
223 return 0;
224
225 uint c = 0;
226 CLCellT p = tail.next();
227
228 for (;;)
229 {
230 T[] buff = p.element();
231 bool isLast = p is tail;
232
233 int n;
234 if (isLast)
235 n = lastCount;
236 else
237 n = buff.length;
238
239 for (int i = 0; i < n; ++i)
240 {
241 if (buff[i] == (element))
242 ++c;
243 }
244
245 if (isLast)
246 break;
247 else
248 p = p.next();
249 }
250 return c;
251 }
252
253 /**
254 * Implements tango.util.collection.impl.Collection.Collection.elements
255 * Time complexity: O(1).
256 * See_Also: tango.util.collection.impl.Collection.Collection.elements
257 **/
258 public final GuardIterator!(T) elements()
259 {
260 return new ArrayIterator!(T)(this);
261 }
262
263 /**
264 * Implements tango.util.collection.model.View.View.opApply
265 * Time complexity: O(n).
266 * See_Also: tango.util.collection.model.View.View.opApply
267 **/
268 int opApply (int delegate (inout T value) dg)
269 {
270 auto scope iterator = new ArrayIterator!(T)(this);
271 return iterator.opApply (dg);
272 }
273
274 // MutableCollection methods
275
276 /**
277 * Implements tango.util.collection.impl.Collection.Collection.clear.
278 * Time complexity: O(1).
279 * See_Also: tango.util.collection.impl.Collection.Collection.clear
280 **/
281 public final void clear()
282 {
283 setCount(0);
284 tail = null;
285 lastCount = 0;
286 }
287
288 /**
289 * Implements tango.util.collection.impl.Collection.Collection.removeAll.
290 * Time complexity: O(n).
291 * See_Also: tango.util.collection.impl.Collection.Collection.removeAll
292 **/
293 public final void removeAll (T element)
294 {
295 remove_(element, true);
296 }
297
298
299 /**
300 * Implements tango.util.collection.impl.Collection.Collection.removeOneOf.
301 * Time complexity: O(n).
302 * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf
303 **/
304 public final void remove(T element)
305 {
306 remove_(element, false);
307 }
308
309 /**
310 * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf
311 * Time complexity: O(n).
312 * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf
313 **/
314 public final void replace(T oldElement, T newElement)
315 {
316 replace_(oldElement, newElement, false);
317 }
318
319 /**
320 * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf.
321 * Time complexity: O(n).
322 * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf
323 **/
324 public final void replaceAll(T oldElement, T newElement)
325 {
326 replace_(oldElement, newElement, true);
327 }
328
329 /**
330 * Implements tango.util.collection.impl.Collection.Collection.take.
331 * Time complexity: O(1).
332 * Takes the least element.
333 * See_Also: tango.util.collection.impl.Collection.Collection.take
334 **/
335 public final T take()
336 {
337 if (count !is 0)
338 {
339 T[] buff = tail.element();
340 T v = buff[lastCount -1];
341 buff[lastCount -1] = T.init;
342 shrink_();
343 return v;
344 }
345 checkIndex(0);
346 return T.init; // not reached
347 }
348
349
350
351 // MutableBag methods
352
353 /**
354 * Implements tango.util.collection.MutableBag.addIfAbsent.
355 * Time complexity: O(n).
356 * See_Also: tango.util.collection.MutableBag.addIfAbsent
357 **/
358 public final void addIf(T element)
359 {
360 if (!contains(element))
361 add (element);
362 }
363
364
365 /**
366 * Implements tango.util.collection.MutableBag.add.
367 * Time complexity: O(1).
368 * See_Also: tango.util.collection.MutableBag.add
369 **/
370 public final void add (T element)
371 {
372 checkElement(element);
373
374 incCount();
375 if (tail is null)
376 {
377 tail = new CLCellT(new T[chunkSize_]);
378 lastCount = 0;
379 }
380
381 T[] buff = tail.element();
382 if (lastCount is buff.length)
383 {
384 buff = new T[chunkSize_];
385 tail.addNext(buff);
386 tail = tail.next();
387 lastCount = 0;
388 }
389
390 buff[lastCount++] = element;
391 }
392
393 /**
394 * helper for remove/exclude
395 **/
396
397 private final void remove_(T element, bool allOccurrences)
398 {
399 if (!isValidArg(element) || count is 0)
400 return ;
401
402 CLCellT p = tail;
403
404 for (;;)
405 {
406 T[] buff = p.element();
407 int i = (p is tail) ? lastCount - 1 : buff.length - 1;
408
409 while (i >= 0)
410 {
411 if (buff[i] == (element))
412 {
413 T[] lastBuff = tail.element();
414 buff[i] = lastBuff[lastCount -1];
415 lastBuff[lastCount -1] = T.init;
416 shrink_();
417
418 if (!allOccurrences || count is 0)
419 return ;
420
421 if (p is tail && i >= lastCount)
422 i = lastCount -1;
423 }
424 else
425 --i;
426 }
427
428 if (p is tail.next())
429 break;
430 else
431 p = p.prev();
432 }
433 }
434
435 private final void replace_(T oldElement, T newElement, bool allOccurrences)
436 {
437 if (!isValidArg(oldElement) || count is 0 || oldElement == (newElement))
438 return ;
439
440 CLCellT p = tail.next();
441
442 for (;;)
443 {
444 T[] buff = p.element();
445 bool isLast = p is tail;
446
447 int n;
448 if (isLast)
449 n = lastCount;
450 else
451 n = buff.length;
452
453 for (int i = 0; i < n; ++i)
454 {
455 if (buff[i] == (oldElement))
456 {
457 checkElement(newElement);
458 incVersion();
459 buff[i] = newElement;
460 if (!allOccurrences)
461 return ;
462 }
463 }
464
465 if (isLast)
466 break;
467 else
468 p = p.next();
469 }
470 }
471
472 private final void shrink_()
473 {
474 decCount();
475 lastCount--;
476 if (lastCount is 0)
477 {
478 if (count is 0)
479 clear();
480 else
481 {
482 CLCellT tmp = tail;
483 tail = tail.prev();
484 tmp.unlink();
485 T[] buff = tail.element();
486 lastCount = buff.length;
487 }
488 }
489 }
490
491 // ImplementationCheckable methods
492
493 /**
494 * Implements tango.util.collection.model.View.View.checkImplementation.
495 * See_Also: tango.util.collection.model.View.View.checkImplementation
496 **/
497 public override void checkImplementation()
498 {
499
500 super.checkImplementation();
501 assert(chunkSize_ >= 0);
502 assert(lastCount >= 0);
503 assert(((count is 0) is (tail is null)));
504
505 if (tail is null)
506 return ;
507
508 int c = 0;
509 CLCellT p = tail.next();
510
511 for (;;)
512 {
513 T[] buff = p.element();
514 bool isLast = p is tail;
515
516 int n;
517 if (isLast)
518 n = lastCount;
519 else
520 n = buff.length;
521
522 c += n;
523 for (int i = 0; i < n; ++i)
524 {
525 auto v = buff[i];
526 assert(allows(v) && contains(v));
527 }
528
529 if (isLast)
530 break;
531 else
532 p = p.next();
533 }
534
535 assert(c is count);
536
537 }
538
539
540
541 /***********************************************************************
542
543 opApply() has migrated here to mitigate the virtual call
544 on method get()
545
546 ************************************************************************/
547
548 static class ArrayIterator(T) : AbstractIterator!(T)
549 {
550 private CLCellT cell;
551 private T[] buff;
552 private int index;
553
554 public this (ArrayBag bag)
555 {
556 super(bag);
557 cell = bag.tail;
558
559 if (cell)
560 buff = cell.element();
561 }
562
563 public final T get()
564 {
565 decRemaining();
566 if (index >= buff.length)
567 {
568 cell = cell.next();
569 buff = cell.element();
570 index = 0;
571 }
572 return buff[index++];
573 }
574
575 int opApply (int delegate (inout T value) dg)
576 {
577 int result;
578
579 for (auto i=remaining(); i--;)
580 {
581 auto value = get();
582 if ((result = dg(value)) != 0)
583 break;
584 }
585 return result;
586 }
587 }
588 }
589
590
591
592
593 debug (Test)
594 {
595 import tango.io.Console;
596
597 void main()
598 {
599 auto bag = new ArrayBag!(char[]);
600 bag.add ("foo");
601 bag.add ("bar");
602 bag.add ("wumpus");
603
604 foreach (value; bag.elements) {}
605
606 auto elements = bag.elements();
607 while (elements.more)
608 auto v = elements.get();
609
610 foreach (value; bag)
611 Cout (value).newline;
612
613 bag.checkImplementation();
614
615 Cout (bag).newline;
616 }
617 }