|
132
|
1 /*******************************************************************************
|
|
|
2
|
|
|
3 File: Collection.d
|
|
|
4
|
|
|
5 Originally written by Doug Lea and released into the public domain.
|
|
|
6 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
|
|
|
7 Inc, Loral, and everyone contributing, testing, and using this code.
|
|
|
8
|
|
|
9 History:
|
|
|
10 Date Who What
|
|
|
11 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file
|
|
|
12 13Oct95 dl Add assert
|
|
|
13 22Oct95 dl Add excludeElements, removeElements
|
|
|
14 28jan97 dl make class public; isolate version changes
|
|
|
15 14Dec06 kb Adapted for Tango usage
|
|
|
16
|
|
|
17 ********************************************************************************/
|
|
|
18
|
|
|
19 module tango.util.collection.impl.Collection;
|
|
|
20
|
|
|
21 private import tango.core.Exception;
|
|
|
22
|
|
|
23 private import tango.util.collection.model.View,
|
|
|
24 tango.util.collection.model.Iterator,
|
|
|
25 tango.util.collection.model.Dispenser;
|
|
|
26
|
|
|
27 /*******************************************************************************
|
|
|
28
|
|
|
29 Collection serves as a convenient base class for most implementations
|
|
|
30 of mutable containers. It maintains a version number and element count.
|
|
|
31 It also provides default implementations of many collection operations.
|
|
|
32
|
|
|
33 Authors: Doug Lea
|
|
|
34
|
|
|
35 ********************************************************************************/
|
|
|
36
|
|
|
37 public abstract class Collection(T) : Dispenser!(T)
|
|
|
38 {
|
|
|
39 alias View!(T) ViewT;
|
|
|
40
|
|
|
41 alias bool delegate(T) Predicate;
|
|
|
42
|
|
|
43
|
|
|
44 // instance variables
|
|
|
45
|
|
|
46 /***********************************************************************
|
|
|
47
|
|
|
48 version represents the current version number
|
|
|
49
|
|
|
50 ************************************************************************/
|
|
|
51
|
|
|
52 protected uint vershion;
|
|
|
53
|
|
|
54 /***********************************************************************
|
|
|
55
|
|
|
56 screener hold the supplied element screener
|
|
|
57
|
|
|
58 ************************************************************************/
|
|
|
59
|
|
|
60 protected Predicate screener;
|
|
|
61
|
|
|
62 /***********************************************************************
|
|
|
63
|
|
|
64 count holds the number of elements.
|
|
|
65
|
|
|
66 ************************************************************************/
|
|
|
67
|
|
|
68 protected uint count;
|
|
|
69
|
|
|
70 // constructors
|
|
|
71
|
|
|
72 /***********************************************************************
|
|
|
73
|
|
|
74 Initialize at version 0, an empty count, and supplied screener
|
|
|
75
|
|
|
76 ************************************************************************/
|
|
|
77
|
|
|
78 protected this (Predicate screener = null)
|
|
|
79 {
|
|
|
80 this.screener = screener;
|
|
|
81 }
|
|
|
82
|
|
|
83
|
|
|
84 /***********************************************************************
|
|
|
85
|
|
|
86 ************************************************************************/
|
|
|
87
|
|
|
88 protected final static bool isValidArg (T element)
|
|
|
89 {
|
|
|
90 static if (is (T : Object))
|
|
|
91 {
|
|
|
92 if (element is null)
|
|
|
93 return false;
|
|
|
94 }
|
|
|
95 return true;
|
|
|
96 }
|
|
|
97
|
|
|
98 // Default implementations of Collection methods
|
|
|
99
|
|
|
100 /***********************************************************************
|
|
|
101
|
|
|
102 expose collection content as an array
|
|
|
103
|
|
|
104 ************************************************************************/
|
|
|
105
|
|
|
106 public T[] toArray ()
|
|
|
107 {
|
|
|
108 auto result = new T[this.size];
|
|
|
109
|
|
|
110 int i = 0;
|
|
|
111 foreach (e; this)
|
|
|
112 result[i++] = e;
|
|
|
113
|
|
|
114 return result;
|
|
|
115 }
|
|
|
116
|
|
|
117 /***********************************************************************
|
|
|
118
|
|
|
119 Time complexity: O(1).
|
|
|
120 See_Also: tango.util.collection.impl.Collection.Collection.drained
|
|
|
121
|
|
|
122 ************************************************************************/
|
|
|
123
|
|
|
124 public final bool drained()
|
|
|
125 {
|
|
|
126 return count is 0;
|
|
|
127 }
|
|
|
128
|
|
|
129 /***********************************************************************
|
|
|
130
|
|
|
131 Time complexity: O(1).
|
|
|
132 Returns: the count of elements currently in the collection
|
|
|
133 See_Also: tango.util.collection.impl.Collection.Collection.size
|
|
|
134
|
|
|
135 ************************************************************************/
|
|
|
136
|
|
|
137 public final uint size()
|
|
|
138 {
|
|
|
139 return count;
|
|
|
140 }
|
|
|
141
|
|
|
142 /***********************************************************************
|
|
|
143
|
|
|
144 Checks if element is an allowed element for this collection.
|
|
|
145 This will not throw an exception, but any other attemp to add an
|
|
|
146 invalid element will do.
|
|
|
147
|
|
|
148 Time complexity: O(1) + time of screener, if present
|
|
|
149
|
|
|
150 See_Also: tango.util.collection.impl.Collection.Collection.allows
|
|
|
151
|
|
|
152 ************************************************************************/
|
|
|
153
|
|
|
154 public final bool allows (T element)
|
|
|
155 {
|
|
|
156 return isValidArg(element) &&
|
|
|
157 (screener is null || screener(element));
|
|
|
158 }
|
|
|
159
|
|
|
160
|
|
|
161 /***********************************************************************
|
|
|
162
|
|
|
163 Time complexity: O(n).
|
|
|
164 Default implementation. Fairly sleazy approach.
|
|
|
165 (Defensible only when you remember that it is just a default impl.)
|
|
|
166 It tries to cast to one of the known collection interface types
|
|
|
167 and then applies the corresponding comparison rules.
|
|
|
168 This suffices for all currently supported collection types,
|
|
|
169 but must be overridden if you define new Collection subinterfaces
|
|
|
170 and/or implementations.
|
|
|
171
|
|
|
172 See_Also: tango.util.collection.impl.Collection.Collection.matches
|
|
|
173
|
|
|
174 ************************************************************************/
|
|
|
175
|
|
|
176 public bool matches(ViewT other)
|
|
|
177 {
|
|
|
178 /+
|
|
|
179 if (other is null)
|
|
|
180 return false;
|
|
|
181 else
|
|
|
182 if (other is this)
|
|
|
183 return true;
|
|
|
184 else
|
|
|
185 if (cast(SortedKeys) this)
|
|
|
186 {
|
|
|
187 if (!(cast(Map) other))
|
|
|
188 return false;
|
|
|
189 else
|
|
|
190 return sameOrderedPairs(cast(Map)this, cast(Map)other);
|
|
|
191 }
|
|
|
192 else
|
|
|
193 if (cast(Map) this)
|
|
|
194 {
|
|
|
195 if (!(cast(Map) other))
|
|
|
196 return false;
|
|
|
197 else
|
|
|
198 return samePairs(cast(Map)(this), cast(Map)(other));
|
|
|
199 }
|
|
|
200 else
|
|
|
201 if ((cast(Seq) this) || (cast(SortedValues) this))
|
|
|
202 return sameOrderedElements(this, other);
|
|
|
203 else
|
|
|
204 if (cast(Bag) this)
|
|
|
205 return sameOccurrences(this, other);
|
|
|
206 else
|
|
|
207 if (cast(Set) this)
|
|
|
208 return sameInclusions(this, cast(View)(other));
|
|
|
209 else
|
|
|
210 return false;
|
|
|
211 +/
|
|
|
212 return false;
|
|
|
213 }
|
|
|
214
|
|
|
215 // Default implementations of MutableCollection methods
|
|
|
216
|
|
|
217 /***********************************************************************
|
|
|
218
|
|
|
219 Time complexity: O(1).
|
|
|
220 See_Also: tango.util.collection.impl.Collection.Collection.version
|
|
|
221
|
|
|
222 ************************************************************************/
|
|
|
223
|
|
|
224 public final uint mutation()
|
|
|
225 {
|
|
|
226 return vershion;
|
|
|
227 }
|
|
|
228
|
|
|
229 // Object methods
|
|
|
230
|
|
|
231 /***********************************************************************
|
|
|
232
|
|
|
233 Default implementation of toString for Collections. Not
|
|
|
234 very pretty, but parenthesizing each element means that
|
|
|
235 for most kinds of elements, it's conceivable that the
|
|
|
236 strings could be parsed and used to build other tango.util.collection.
|
|
|
237
|
|
|
238 Not a very pretty implementation either. Casts are used
|
|
|
239 to get at elements/keys
|
|
|
240
|
|
|
241 ************************************************************************/
|
|
|
242
|
|
|
243 public override char[] toString()
|
|
|
244 {
|
|
|
245 char[16] tmp;
|
|
|
246
|
|
|
247 return "<" ~ this.classinfo.name ~ ", size:" ~ itoa(tmp, size()) ~ ">";
|
|
|
248 }
|
|
|
249
|
|
|
250
|
|
|
251 /***********************************************************************
|
|
|
252
|
|
|
253 ************************************************************************/
|
|
|
254
|
|
|
255 protected final char[] itoa(char[] buf, uint i)
|
|
|
256 {
|
|
|
257 auto j = buf.length;
|
|
|
258
|
|
|
259 do {
|
|
|
260 buf[--j] = i % 10 + '0';
|
|
|
261 } while (i /= 10);
|
|
|
262 return buf [j..$];
|
|
|
263 }
|
|
|
264
|
|
|
265 // protected operations on version and count
|
|
|
266
|
|
|
267 /***********************************************************************
|
|
|
268
|
|
|
269 change the version number
|
|
|
270
|
|
|
271 ************************************************************************/
|
|
|
272
|
|
|
273 protected final void incVersion()
|
|
|
274 {
|
|
|
275 ++vershion;
|
|
|
276 }
|
|
|
277
|
|
|
278
|
|
|
279 /***********************************************************************
|
|
|
280
|
|
|
281 Increment the element count and update version
|
|
|
282
|
|
|
283 ************************************************************************/
|
|
|
284
|
|
|
285 protected final void incCount()
|
|
|
286 {
|
|
|
287 count++;
|
|
|
288 incVersion();
|
|
|
289 }
|
|
|
290
|
|
|
291 /***********************************************************************
|
|
|
292
|
|
|
293 Decrement the element count and update version
|
|
|
294
|
|
|
295 ************************************************************************/
|
|
|
296
|
|
|
297 protected final void decCount()
|
|
|
298 {
|
|
|
299 count--;
|
|
|
300 incVersion();
|
|
|
301 }
|
|
|
302
|
|
|
303
|
|
|
304 /***********************************************************************
|
|
|
305
|
|
|
306 add to the element count and update version if changed
|
|
|
307
|
|
|
308 ************************************************************************/
|
|
|
309
|
|
|
310 protected final void addToCount(uint c)
|
|
|
311 {
|
|
|
312 if (c !is 0)
|
|
|
313 {
|
|
|
314 count += c;
|
|
|
315 incVersion();
|
|
|
316 }
|
|
|
317 }
|
|
|
318
|
|
|
319
|
|
|
320 /***********************************************************************
|
|
|
321
|
|
|
322 set the element count and update version if changed
|
|
|
323
|
|
|
324 ************************************************************************/
|
|
|
325
|
|
|
326 protected final void setCount(uint c)
|
|
|
327 {
|
|
|
328 if (c !is count)
|
|
|
329 {
|
|
|
330 count = c;
|
|
|
331 incVersion();
|
|
|
332 }
|
|
|
333 }
|
|
|
334
|
|
|
335
|
|
|
336 /***********************************************************************
|
|
|
337
|
|
|
338 Helper method left public since it might be useful
|
|
|
339
|
|
|
340 ************************************************************************/
|
|
|
341
|
|
|
342 public final static bool sameInclusions(ViewT s, ViewT t)
|
|
|
343 {
|
|
|
344 if (s.size !is t.size)
|
|
|
345 return false;
|
|
|
346
|
|
|
347 try { // set up to return false on collection exceptions
|
|
|
348 auto ts = t.elements();
|
|
|
349 while (ts.more)
|
|
|
350 {
|
|
|
351 if (!s.contains(ts.get))
|
|
|
352 return false;
|
|
|
353 }
|
|
|
354 return true;
|
|
|
355 } catch (NoSuchElementException ex)
|
|
|
356 {
|
|
|
357 return false;
|
|
|
358 }
|
|
|
359 }
|
|
|
360
|
|
|
361 /***********************************************************************
|
|
|
362
|
|
|
363 Helper method left public since it might be useful
|
|
|
364
|
|
|
365 ************************************************************************/
|
|
|
366
|
|
|
367 public final static bool sameOccurrences(ViewT s, ViewT t)
|
|
|
368 {
|
|
|
369 if (s.size !is t.size)
|
|
|
370 return false;
|
|
|
371
|
|
|
372 auto ts = t.elements();
|
|
|
373 T last = T.init; // minor optimization -- skip two successive if same
|
|
|
374
|
|
|
375 try { // set up to return false on collection exceptions
|
|
|
376 while (ts.more)
|
|
|
377 {
|
|
|
378 T m = ts.get;
|
|
|
379 if (m !is last)
|
|
|
380 {
|
|
|
381 if (s.instances(m) !is t.instances(m))
|
|
|
382 return false;
|
|
|
383 }
|
|
|
384 last = m;
|
|
|
385 }
|
|
|
386 return true;
|
|
|
387 } catch (NoSuchElementException ex)
|
|
|
388 {
|
|
|
389 return false;
|
|
|
390 }
|
|
|
391 }
|
|
|
392
|
|
|
393
|
|
|
394 /***********************************************************************
|
|
|
395
|
|
|
396 Helper method left public since it might be useful
|
|
|
397
|
|
|
398 ************************************************************************/
|
|
|
399
|
|
|
400 public final static bool sameOrderedElements(ViewT s, ViewT t)
|
|
|
401 {
|
|
|
402 if (s.size !is t.size)
|
|
|
403 return false;
|
|
|
404
|
|
|
405 auto ts = t.elements();
|
|
|
406 auto ss = s.elements();
|
|
|
407
|
|
|
408 try { // set up to return false on collection exceptions
|
|
|
409 while (ts.more)
|
|
|
410 {
|
|
|
411 T m = ts.get;
|
|
|
412 T o = ss.get;
|
|
|
413 if (m != o)
|
|
|
414 return false;
|
|
|
415 }
|
|
|
416 return true;
|
|
|
417 } catch (NoSuchElementException ex)
|
|
|
418 {
|
|
|
419 return false;
|
|
|
420 }
|
|
|
421 }
|
|
|
422
|
|
|
423 // misc common helper methods
|
|
|
424
|
|
|
425 /***********************************************************************
|
|
|
426
|
|
|
427 Principal method to throw a NoSuchElementException.
|
|
|
428 Besides index checks in Seqs, you can use it to check for
|
|
|
429 operations on empty collections via checkIndex(0)
|
|
|
430
|
|
|
431 ************************************************************************/
|
|
|
432
|
|
|
433 protected final void checkIndex(int index)
|
|
|
434 {
|
|
|
435 if (index < 0 || index >= count)
|
|
|
436 {
|
|
|
437 char[] msg;
|
|
|
438
|
|
|
439 if (count is 0)
|
|
|
440 msg = "Element access on empty collection";
|
|
|
441 else
|
|
|
442 {
|
|
|
443 char[16] idx, cnt;
|
|
|
444 msg = "Index " ~ itoa (idx, index) ~ " out of range for collection of size " ~ itoa (cnt, count);
|
|
|
445 }
|
|
|
446 throw new NoSuchElementException(msg);
|
|
|
447 }
|
|
|
448 }
|
|
|
449
|
|
|
450
|
|
|
451 /***********************************************************************
|
|
|
452
|
|
|
453 Principal method to throw a IllegalElementException
|
|
|
454
|
|
|
455 ************************************************************************/
|
|
|
456
|
|
|
457 protected final void checkElement(T element)
|
|
|
458 {
|
|
|
459 if (! allows(element))
|
|
|
460 {
|
|
|
461 throw new IllegalElementException("Attempt to include invalid element _in Collection");
|
|
|
462 }
|
|
|
463 }
|
|
|
464
|
|
|
465 /***********************************************************************
|
|
|
466
|
|
|
467 See_Also: tango.util.collection.model.View.View.checkImplementation
|
|
|
468
|
|
|
469 ************************************************************************/
|
|
|
470
|
|
|
471 public void checkImplementation()
|
|
|
472 {
|
|
|
473 assert(count >= 0);
|
|
|
474 }
|
|
|
475 //public override void checkImplementation() //Doesn't compile with the override attribute
|
|
|
476
|
|
|
477 /***********************************************************************
|
|
|
478
|
|
|
479 Cause the collection to become empty.
|
|
|
480
|
|
|
481 ************************************************************************/
|
|
|
482
|
|
|
483 abstract void clear();
|
|
|
484
|
|
|
485 /***********************************************************************
|
|
|
486
|
|
|
487 Exclude all occurrences of the indicated element from the collection.
|
|
|
488 No effect if element not present.
|
|
|
489 Params:
|
|
|
490 element = the element to exclude.
|
|
|
491 ---
|
|
|
492 !has(element) &&
|
|
|
493 size() == PREV(this).size() - PREV(this).instances(element) &&
|
|
|
494 no other element changes &&
|
|
|
495 Version change iff PREV(this).has(element)
|
|
|
496 ---
|
|
|
497
|
|
|
498 ************************************************************************/
|
|
|
499
|
|
|
500 abstract void removeAll(T element);
|
|
|
501
|
|
|
502 /***********************************************************************
|
|
|
503
|
|
|
504 Remove an instance of the indicated element from the collection.
|
|
|
505 No effect if !has(element)
|
|
|
506 Params:
|
|
|
507 element = the element to remove
|
|
|
508 ---
|
|
|
509 let occ = max(1, instances(element)) in
|
|
|
510 size() == PREV(this).size() - occ &&
|
|
|
511 instances(element) == PREV(this).instances(element) - occ &&
|
|
|
512 no other element changes &&
|
|
|
513 version change iff occ == 1
|
|
|
514 ---
|
|
|
515
|
|
|
516 ************************************************************************/
|
|
|
517
|
|
|
518 abstract void remove (T element);
|
|
|
519
|
|
|
520 /***********************************************************************
|
|
|
521
|
|
|
522 Replace an occurrence of oldElement with newElement.
|
|
|
523 No effect if does not hold oldElement or if oldElement.equals(newElement).
|
|
|
524 The operation has a consistent, but slightly special interpretation
|
|
|
525 when applied to Sets. For Sets, because elements occur at
|
|
|
526 most once, if newElement is already included, replacing oldElement with
|
|
|
527 with newElement has the same effect as just removing oldElement.
|
|
|
528 ---
|
|
|
529 let int delta = oldElement.equals(newElement)? 0 :
|
|
|
530 max(1, PREV(this).instances(oldElement) in
|
|
|
531 instances(oldElement) == PREV(this).instances(oldElement) - delta &&
|
|
|
532 instances(newElement) == (this instanceof Set) ?
|
|
|
533 max(1, PREV(this).instances(oldElement) + delta):
|
|
|
534 PREV(this).instances(oldElement) + delta) &&
|
|
|
535 no other element changes &&
|
|
|
536 Version change iff delta != 0
|
|
|
537 ---
|
|
|
538 Throws: IllegalElementException if has(oldElement) and !allows(newElement)
|
|
|
539
|
|
|
540 ************************************************************************/
|
|
|
541
|
|
|
542 abstract void replace (T oldElement, T newElement);
|
|
|
543
|
|
|
544 /***********************************************************************
|
|
|
545
|
|
|
546 Replace all occurrences of oldElement with newElement.
|
|
|
547 No effect if does not hold oldElement or if oldElement.equals(newElement).
|
|
|
548 The operation has a consistent, but slightly special interpretation
|
|
|
549 when applied to Sets. For Sets, because elements occur at
|
|
|
550 most once, if newElement is already included, replacing oldElement with
|
|
|
551 with newElement has the same effect as just removing oldElement.
|
|
|
552 ---
|
|
|
553 let int delta = oldElement.equals(newElement)? 0 :
|
|
|
554 PREV(this).instances(oldElement) in
|
|
|
555 instances(oldElement) == PREV(this).instances(oldElement) - delta &&
|
|
|
556 instances(newElement) == (this instanceof Set) ?
|
|
|
557 max(1, PREV(this).instances(oldElement) + delta):
|
|
|
558 PREV(this).instances(oldElement) + delta) &&
|
|
|
559 no other element changes &&
|
|
|
560 Version change iff delta != 0
|
|
|
561 ---
|
|
|
562 Throws: IllegalElementException if has(oldElement) and !allows(newElement)
|
|
|
563
|
|
|
564 ************************************************************************/
|
|
|
565
|
|
|
566 abstract void replaceAll(T oldElement, T newElement);
|
|
|
567
|
|
|
568 /***********************************************************************
|
|
|
569
|
|
|
570 Exclude all occurrences of each element of the Iterator.
|
|
|
571 Behaviorally equivalent to
|
|
|
572 ---
|
|
|
573 while (e.more())
|
|
|
574 removeAll(e.get());
|
|
|
575 ---
|
|
|
576 Param :
|
|
|
577 e = the enumeration of elements to exclude.
|
|
|
578
|
|
|
579 Throws: CorruptedIteratorException is propagated if thrown
|
|
|
580
|
|
|
581 See_Also: tango.util.collection.impl.Collection.Collection.removeAll
|
|
|
582
|
|
|
583 ************************************************************************/
|
|
|
584
|
|
|
585 abstract void removeAll (Iterator!(T) e);
|
|
|
586
|
|
|
587 /***********************************************************************
|
|
|
588
|
|
|
589 Remove an occurrence of each element of the Iterator.
|
|
|
590 Behaviorally equivalent to
|
|
|
591
|
|
|
592 ---
|
|
|
593 while (e.more())
|
|
|
594 remove (e.get());
|
|
|
595 ---
|
|
|
596
|
|
|
597 Param:
|
|
|
598 e = the enumeration of elements to remove.
|
|
|
599
|
|
|
600 Throws: CorruptedIteratorException is propagated if thrown
|
|
|
601
|
|
|
602 ************************************************************************/
|
|
|
603
|
|
|
604 abstract void remove (Iterator!(T) e);
|
|
|
605
|
|
|
606 /***********************************************************************
|
|
|
607
|
|
|
608 Remove and return an element. Implementations
|
|
|
609 may strengthen the guarantee about the nature of this element.
|
|
|
610 but in general it is the most convenient or efficient element to remove.
|
|
|
611
|
|
|
612 Examples:
|
|
|
613 One way to transfer all elements from
|
|
|
614 MutableCollection a to MutableBag b is:
|
|
|
615 ---
|
|
|
616 while (!a.empty())
|
|
|
617 b.add(a.take());
|
|
|
618 ---
|
|
|
619
|
|
|
620 Returns:
|
|
|
621 an element v such that PREV(this).has(v)
|
|
|
622 and the postconditions of removeOneOf(v) hold.
|
|
|
623
|
|
|
624 Throws: NoSuchElementException iff drained.
|
|
|
625
|
|
|
626 ************************************************************************/
|
|
|
627
|
|
|
628 abstract T take();
|
|
|
629 }
|
|
|
630
|
|
|
631
|
