Mercurial > projects > ldc

comparison tango/tango/util/collection/impl/Collection.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
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