|
132
|
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 }
|
