3 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
\r
4 Permission is hereby granted, free of charge, to any person obtaining a copy
\r
5 of this software and associated documentation files (the "Software"), to deal
\r
6 in the Software without restriction, including without limitation the rights
\r
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
8 copies of the Software, and to permit persons to whom the Software is
\r
9 furnished to do so, subject to the following conditions:
\r
11 The above copyright notice and this permission notice shall be included in
\r
12 all copies or substantial portions of the Software.
\r
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\r
23 #define IMPROVED_COLLECTION_HASHFUNCTION
\r
26 using System.Diagnostics;
\r
27 using SCG = System.Collections.Generic;
\r
31 /// A base class for implementing an IEnumerable<T>
\r
34 public abstract class EnumerableBase<T> : SCG.IEnumerable<T>
\r
37 /// Create an enumerator for this collection.
\r
39 /// <returns>The enumerator</returns>
\r
40 public abstract SCG.IEnumerator<T> GetEnumerator();
\r
43 /// Count the number of items in an enumerable by enumeration
\r
45 /// <param name="items">The enumerable to count</param>
\r
46 /// <returns>The size of the enumerable</returns>
\r
48 protected static int countItems(SCG.IEnumerable<T> items)
\r
50 ICollectionValue<T> jtems = items as ICollectionValue<T>;
\r
57 using (SCG.IEnumerator<T> e = items.GetEnumerator())
\r
58 while (e.MoveNext()) count++;
\r
63 #region IEnumerable Members
\r
65 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
\r
67 return GetEnumerator();
\r
75 /// Base class for classes implementing ICollectionValue[T]
\r
78 public abstract class CollectionValueBase<T> : EnumerableBase<T>, ICollectionValue<T>, IShowable
\r
80 #region Event handling
\r
81 EventBlock<T> eventBlock;
\r
86 public virtual EventTypeEnum ListenableEvents { get { return 0; } }
\r
89 /// A flag bitmap of the events currently subscribed to by this collection.
\r
92 public virtual EventTypeEnum ActiveEvents { get { return eventBlock == null ? 0 : eventBlock.events; } }
\r
94 private void checkWillListen(EventTypeEnum eventType)
\r
96 if ((ListenableEvents & eventType) == 0)
\r
97 throw new UnlistenableEventException();
\r
101 /// The change event. Will be raised for every change operation on the collection.
\r
103 public virtual event CollectionChangedHandler<T> CollectionChanged
\r
105 add { checkWillListen(EventTypeEnum.Changed); (eventBlock ?? (eventBlock = new EventBlock<T>())).CollectionChanged += value; }
\r
108 checkWillListen(EventTypeEnum.Changed);
\r
109 if (eventBlock != null)
\r
111 eventBlock.CollectionChanged -= value;
\r
112 if (eventBlock.events == 0) eventBlock = null;
\r
117 /// Fire the CollectionChanged event
\r
119 protected virtual void raiseCollectionChanged()
\r
120 { if (eventBlock != null) eventBlock.raiseCollectionChanged(this); }
\r
123 /// The clear event. Will be raised for every Clear operation on the collection.
\r
125 public virtual event CollectionClearedHandler<T> CollectionCleared
\r
127 add { checkWillListen(EventTypeEnum.Cleared); (eventBlock ?? (eventBlock = new EventBlock<T>())).CollectionCleared += value; }
\r
130 checkWillListen(EventTypeEnum.Cleared);
\r
131 if (eventBlock != null)
\r
133 eventBlock.CollectionCleared -= value;
\r
134 if (eventBlock.events == 0) eventBlock = null;
\r
139 /// Fire the CollectionCleared event
\r
141 protected virtual void raiseCollectionCleared(bool full, int count)
\r
142 { if (eventBlock != null) eventBlock.raiseCollectionCleared(this, full, count); }
\r
145 /// Fire the CollectionCleared event
\r
147 protected virtual void raiseCollectionCleared(bool full, int count, int? offset)
\r
148 { if (eventBlock != null) eventBlock.raiseCollectionCleared(this, full, count, offset); }
\r
151 /// The item added event. Will be raised for every individual addition to the collection.
\r
153 public virtual event ItemsAddedHandler<T> ItemsAdded
\r
155 add { checkWillListen(EventTypeEnum.Added); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemsAdded += value; }
\r
158 checkWillListen(EventTypeEnum.Added);
\r
159 if (eventBlock != null)
\r
161 eventBlock.ItemsAdded -= value;
\r
162 if (eventBlock.events == 0) eventBlock = null;
\r
167 /// Fire the ItemsAdded event
\r
169 /// <param name="item">The item that was added</param>
\r
170 /// <param name="count"></param>
\r
171 protected virtual void raiseItemsAdded(T item, int count)
\r
172 { if (eventBlock != null) eventBlock.raiseItemsAdded(this, item, count); }
\r
175 /// The item removed event. Will be raised for every individual removal from the collection.
\r
177 public virtual event ItemsRemovedHandler<T> ItemsRemoved
\r
179 add { checkWillListen(EventTypeEnum.Removed); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemsRemoved += value; }
\r
182 checkWillListen(EventTypeEnum.Removed);
\r
183 if (eventBlock != null)
\r
185 eventBlock.ItemsRemoved -= value;
\r
186 if (eventBlock.events == 0) eventBlock = null;
\r
191 /// Fire the ItemsRemoved event
\r
193 /// <param name="item">The item that was removed</param>
\r
194 /// <param name="count"></param>
\r
195 protected virtual void raiseItemsRemoved(T item, int count)
\r
196 { if (eventBlock != null) eventBlock.raiseItemsRemoved(this, item, count); }
\r
199 /// The item added event. Will be raised for every individual addition to the collection.
\r
201 public virtual event ItemInsertedHandler<T> ItemInserted
\r
203 add { checkWillListen(EventTypeEnum.Inserted); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemInserted += value; }
\r
206 checkWillListen(EventTypeEnum.Inserted);
\r
207 if (eventBlock != null)
\r
209 eventBlock.ItemInserted -= value;
\r
210 if (eventBlock.events == 0) eventBlock = null;
\r
215 /// Fire the ItemInserted event
\r
217 /// <param name="item">The item that was added</param>
\r
218 /// <param name="index"></param>
\r
219 protected virtual void raiseItemInserted(T item, int index)
\r
220 { if (eventBlock != null) eventBlock.raiseItemInserted(this, item, index); }
\r
223 /// The item removed event. Will be raised for every individual removal from the collection.
\r
225 public virtual event ItemRemovedAtHandler<T> ItemRemovedAt
\r
227 add { checkWillListen(EventTypeEnum.RemovedAt); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemRemovedAt += value; }
\r
230 checkWillListen(EventTypeEnum.RemovedAt);
\r
231 if (eventBlock != null)
\r
233 eventBlock.ItemRemovedAt -= value;
\r
234 if (eventBlock.events == 0) eventBlock = null;
\r
239 /// Fire the ItemRemovedAt event
\r
241 /// <param name="item">The item that was removed</param>
\r
242 /// <param name="index"></param>
\r
243 protected virtual void raiseItemRemovedAt(T item, int index)
\r
244 { if (eventBlock != null) eventBlock.raiseItemRemovedAt(this, item, index); }
\r
246 #region Event support for IList
\r
250 /// <param name="index"></param>
\r
251 /// <param name="value"></param>
\r
252 /// <param name="item"></param>
\r
253 protected virtual void raiseForSetThis(int index, T value, T item)
\r
255 if (ActiveEvents != 0)
\r
257 raiseItemsRemoved(item, 1);
\r
258 raiseItemRemovedAt(item, index);
\r
259 raiseItemsAdded(value, 1);
\r
260 raiseItemInserted(value, index);
\r
261 raiseCollectionChanged();
\r
267 /// <param name="i"></param>
\r
268 /// <param name="item"></param>
\r
269 protected virtual void raiseForInsert(int i, T item)
\r
271 if (ActiveEvents != 0)
\r
273 raiseItemInserted(item, i);
\r
274 raiseItemsAdded(item, 1);
\r
275 raiseCollectionChanged();
\r
282 /// <param name="item"></param>
\r
283 protected void raiseForRemove(T item)
\r
285 if (ActiveEvents != 0)
\r
287 raiseItemsRemoved(item, 1);
\r
288 raiseCollectionChanged();
\r
295 /// <param name="item"></param>
\r
296 /// <param name="count"></param>
\r
297 protected void raiseForRemove(T item, int count)
\r
299 if (ActiveEvents != 0)
\r
301 raiseItemsRemoved(item, count);
\r
302 raiseCollectionChanged();
\r
309 /// <param name="index"></param>
\r
310 /// <param name="item"></param>
\r
311 protected void raiseForRemoveAt(int index, T item)
\r
313 if (ActiveEvents != 0)
\r
315 raiseItemRemovedAt(item, index);
\r
316 raiseItemsRemoved(item, 1);
\r
317 raiseCollectionChanged();
\r
323 #region Event Support for ICollection
\r
327 /// <param name="newitem"></param>
\r
328 /// <param name="olditem"></param>
\r
329 protected virtual void raiseForUpdate(T newitem, T olditem)
\r
331 if (ActiveEvents != 0)
\r
333 raiseItemsRemoved(olditem, 1);
\r
334 raiseItemsAdded(newitem, 1);
\r
335 raiseCollectionChanged();
\r
341 /// <param name="newitem"></param>
\r
342 /// <param name="olditem"></param>
\r
343 /// <param name="count"></param>
\r
344 protected virtual void raiseForUpdate(T newitem, T olditem, int count)
\r
346 if (ActiveEvents != 0)
\r
348 raiseItemsRemoved(olditem, count);
\r
349 raiseItemsAdded(newitem, count);
\r
350 raiseCollectionChanged();
\r
356 /// <param name="item"></param>
\r
357 protected virtual void raiseForAdd(T item)
\r
359 if (ActiveEvents != 0)
\r
361 raiseItemsAdded(item, 1);
\r
362 raiseCollectionChanged();
\r
368 /// <param name="wasRemoved"></param>
\r
369 protected virtual void raiseForRemoveAll(ICollectionValue<T> wasRemoved)
\r
371 if ((ActiveEvents & EventTypeEnum.Removed) != 0)
\r
372 foreach (T item in wasRemoved)
\r
373 raiseItemsRemoved(item, 1);
\r
374 if (wasRemoved != null && wasRemoved.Count > 0)
\r
375 raiseCollectionChanged();
\r
381 protected class RaiseForRemoveAllHandler
\r
383 CollectionValueBase<T> collection;
\r
384 CircularQueue<T> wasRemoved;
\r
385 bool wasChanged = false;
\r
390 /// <param name="collection"></param>
\r
391 public RaiseForRemoveAllHandler(CollectionValueBase<T> collection)
\r
393 this.collection = collection;
\r
394 mustFireRemoved = (collection.ActiveEvents & EventTypeEnum.Removed) != 0;
\r
395 MustFire = (collection.ActiveEvents & (EventTypeEnum.Removed | EventTypeEnum.Changed)) != 0;
\r
398 bool mustFireRemoved;
\r
402 public readonly bool MustFire;
\r
407 /// <param name="item"></param>
\r
408 public void Remove(T item)
\r
410 if (mustFireRemoved)
\r
412 if (wasRemoved == null)
\r
413 wasRemoved = new CircularQueue<T>();
\r
414 wasRemoved.Enqueue(item);
\r
423 public void Raise()
\r
425 if (wasRemoved != null)
\r
426 foreach (T item in wasRemoved)
\r
427 collection.raiseItemsRemoved(item, 1);
\r
429 collection.raiseCollectionChanged();
\r
437 /// Check if collection is empty.
\r
439 /// <value>True if empty</value>
\r
440 public abstract bool IsEmpty { get;}
\r
443 /// The number of items in this collection.
\r
445 /// <value></value>
\r
446 public abstract int Count { get;}
\r
449 /// The value is symbolic indicating the type of asymptotic complexity
\r
450 /// in terms of the size of this collection (worst-case or amortized as
\r
453 /// <value>A characterization of the speed of the
\r
454 /// <code>Count</code> property in this collection.</value>
\r
455 public abstract Speed CountSpeed { get; }
\r
458 /// Copy the items of this collection to part of an array.
\r
460 /// <exception cref="ArgumentOutOfRangeException"> if <code>index</code>
\r
461 /// is not a valid index
\r
462 /// into the array (i.e. negative or not less than the size of the array)
\r
463 /// or the array does not have room for the items.</exception>
\r
464 /// <param name="array">The array to copy to.</param>
\r
465 /// <param name="index">The starting index.</param>
\r
467 public virtual void CopyTo(T[] array, int index)
\r
469 #warning This code does not fit the doc comment and unit tests
\r
470 if (index < 0 || index + Count > array.Length)
\r
471 throw new ArgumentOutOfRangeException();
\r
473 foreach (T item in this) array[index++] = item;
\r
477 /// Create an array with the items of this collection (in the same order as an
\r
478 /// enumerator would output them).
\r
480 /// <returns>The array</returns>
\r
482 public virtual T[] ToArray()
\r
484 T[] res = new T[Count];
\r
487 foreach (T item in this) res[i++] = item;
\r
493 /// Apply an single argument action, <see cref="T:C5.Act`1"/> to this enumerable
\r
495 /// <param name="action">The action delegate</param>
\r
497 public virtual void Apply(Act<T> action)
\r
499 foreach (T item in this)
\r
505 /// Check if there exists an item that satisfies a
\r
506 /// specific predicate in this collection.
\r
508 /// <param name="predicate">A delegate
\r
509 /// (<see cref="T:C5.Fun`2"/> with <code>R = bool</code>)
\r
510 /// defining the predicate</param>
\r
511 /// <returns>True if such an item exists</returns>
\r
513 public virtual bool Exists(Fun<T, bool> predicate)
\r
515 foreach (T item in this)
\r
516 if (predicate(item))
\r
523 /// Check if there exists an item that satisfies a
\r
524 /// specific predicate in this collection and return the first one in enumeration order.
\r
526 /// <param name="predicate">A delegate
\r
527 /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
\r
528 /// <param name="item"></param>
\r
529 /// <returns>True is such an item exists</returns>
\r
530 public virtual bool Find(Fun<T, bool> predicate, out T item)
\r
532 foreach (T jtem in this)
\r
533 if (predicate(jtem))
\r
543 /// Check if all items in this collection satisfies a specific predicate.
\r
545 /// <param name="predicate">A delegate
\r
546 /// (<see cref="T:C5.Fun`2"/> with <code>R = bool</code>)
\r
547 /// defining the predicate</param>
\r
548 /// <returns>True if all items satisfies the predicate</returns>
\r
550 public virtual bool All(Fun<T, bool> predicate)
\r
552 foreach (T item in this)
\r
553 if (!predicate(item))
\r
560 /// Create an enumerable, enumerating the items of this collection that satisfies
\r
561 /// a certain condition.
\r
563 /// <param name="predicate">A delegate
\r
564 /// (<see cref="T:C5.Fun`2"/> with <code>R = bool</code>)
\r
565 /// defining the predicate</param>
\r
566 /// <returns>The filtered enumerable</returns>
\r
567 public virtual SCG.IEnumerable<T> Filter(Fun<T, bool> predicate)
\r
569 foreach (T item in this)
\r
570 if (predicate(item))
\r
575 /// Choose some item of this collection.
\r
577 /// <exception cref="NoSuchItemException">if collection is empty.</exception>
\r
578 /// <returns></returns>
\r
579 public abstract T Choose();
\r
583 /// Create an enumerator for this collection.
\r
585 /// <returns>The enumerator</returns>
\r
586 public override abstract SCG.IEnumerator<T> GetEnumerator();
\r
588 #region IShowable Members
\r
593 /// <param name="stringbuilder"></param>
\r
594 /// <param name="rest"></param>
\r
595 /// <param name="formatProvider"></param>
\r
596 /// <returns></returns>
\r
597 public virtual bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
599 return Showing.ShowCollectionValue<T>(this, stringbuilder, ref rest, formatProvider);
\r
603 #region IFormattable Members
\r
608 /// <param name="format"></param>
\r
609 /// <param name="formatProvider"></param>
\r
610 /// <returns></returns>
\r
611 public virtual string ToString(string format, IFormatProvider formatProvider)
\r
613 return Showing.ShowString(this, format, formatProvider);
\r
621 /// <returns></returns>
\r
622 public override string ToString()
\r
624 return ToString(null, null);
\r
632 /// <typeparam name="T"></typeparam>
\r
633 public abstract class DirectedCollectionValueBase<T> : CollectionValueBase<T>, IDirectedCollectionValue<T>
\r
636 /// <code>Forwards</code> if same, else <code>Backwards</code>
\r
638 /// <value>The enumeration direction relative to the original collection.</value>
\r
639 public virtual EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
\r
644 /// <returns></returns>
\r
645 public abstract IDirectedCollectionValue<T> Backwards();
\r
647 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return this.Backwards(); }
\r
650 /// Check if there exists an item that satisfies a
\r
651 /// specific predicate in this collection and return the first one in enumeration order.
\r
653 /// <param name="predicate">A delegate
\r
654 /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
\r
655 /// <param name="item"></param>
\r
656 /// <returns>True is such an item exists</returns>
\r
657 public virtual bool FindLast(Fun<T, bool> predicate, out T item)
\r
659 foreach (T jtem in Backwards())
\r
660 if (predicate(jtem))
\r
671 /// Base class (abstract) for ICollection implementations.
\r
674 public abstract class CollectionBase<T> : CollectionValueBase<T>
\r
678 object syncroot = new object();
\r
681 /// The underlying field of the ReadOnly property
\r
683 protected bool isReadOnly = false;
\r
686 /// The current stamp value
\r
688 protected int stamp;
\r
691 /// The number of items in the collection
\r
693 protected int size;
\r
696 /// The item equalityComparer of the collection
\r
698 protected readonly SCG.IEqualityComparer<T> itemequalityComparer;
\r
700 int iUnSequencedHashCode, iUnSequencedHashCodeStamp = -1;
\r
707 /// <param name="itemequalityComparer"></param>
\r
708 public CollectionBase(SCG.IEqualityComparer<T> itemequalityComparer)
\r
710 if (itemequalityComparer == null)
\r
711 throw new NullReferenceException("Item EqualityComparer cannot be null.");
\r
712 this.itemequalityComparer = itemequalityComparer;
\r
718 /// Utility method for range checking.
\r
720 /// <exception cref="ArgumentOutOfRangeException"> if the start or count is negative or
\r
721 /// if the range does not fit within collection size.</exception>
\r
722 /// <param name="start">start of range</param>
\r
723 /// <param name="count">size of range</param>
\r
725 protected void checkRange(int start, int count)
\r
727 if (start < 0 || count < 0 || start + count > size)
\r
728 throw new ArgumentOutOfRangeException();
\r
733 /// Compute the unsequenced hash code of a collection
\r
735 /// <param name="items">The collection to compute hash code for</param>
\r
736 /// <param name="itemequalityComparer">The item equalityComparer</param>
\r
737 /// <returns>The hash code</returns>
\r
739 public static int ComputeHashCode(ICollectionValue<T> items, SCG.IEqualityComparer<T> itemequalityComparer)
\r
743 #if IMPROVED_COLLECTION_HASHFUNCTION
\r
744 //But still heuristic:
\r
745 //Note: the three odd factors should really be random,
\r
746 //but there will be a problem with serialization/deserialization!
\r
747 //Two products is too few
\r
748 foreach (T item in items)
\r
750 uint h1 = (uint)itemequalityComparer.GetHashCode(item);
\r
752 h += (int)((h1 * 1529784657 + 1) ^ (h1 * 2912831877) ^ (h1 * 1118771817 + 2));
\r
757 The pairs (-1657792980, -1570288808) and (1862883298, -272461342) gives the same
\r
758 unsequenced hashcode with this hashfunction. The pair was found with code like
\r
760 HashDictionary<int, int[]> set = new HashDictionary<int, int[]>();
\r
761 Random rnd = new C5Random(12345);
\r
764 int[] a = new int[2];
\r
765 a[0] = rnd.Next(); a[1] = rnd.Next();
\r
766 int h = unsequencedhashcode(a);
\r
768 if (set.FindOrAdd(h, ref b))
\r
770 Console.WriteLine("Code {5}, Pair ({1},{2}) number {0} matched other pair ({3},{4})", set.Count, a[0], a[1], b[0], b[1], h);
\r
775 foreach (T item in items)
\r
776 h ^= itemequalityComparer.GetHashCode(item);
\r
778 return (items.Count << 16) + h;
\r
782 static Type isortedtype = typeof(ISorted<T>);
\r
785 /// Examine if tit and tat are equal as unsequenced collections
\r
786 /// using the specified item equalityComparer (assumed compatible with the two collections).
\r
788 /// <param name="collection1">The first collection</param>
\r
789 /// <param name="collection2">The second collection</param>
\r
790 /// <param name="itemequalityComparer">The item equalityComparer to use for comparison</param>
\r
791 /// <returns>True if equal</returns>
\r
793 public static bool StaticEquals(ICollection<T> collection1, ICollection<T> collection2, SCG.IEqualityComparer<T> itemequalityComparer)
\r
795 if (object.ReferenceEquals(collection1, collection2))
\r
798 if (collection1.Count != collection2.Count)
\r
801 //This way we might run through both enumerations twice, but
\r
802 //probably not (if the hash codes are good)
\r
803 //TODO: cehck equal equalityComparers, at least here!
\r
804 if (collection1.GetUnsequencedHashCode() != collection2.GetUnsequencedHashCode())
\r
807 //TODO: move this to the sorted implementation classes?
\r
808 //Really depends on speed of IntanceOfType: we could save a cast
\r
810 ISorted<T> stit, stat;
\r
811 if ((stit = collection1 as ISorted<T>) != null && (stat = collection2 as ISorted<T>) != null && stit.Comparer == stat.Comparer)
\r
813 using (SCG.IEnumerator<T> dat = collection2.GetEnumerator(), dit = collection1.GetEnumerator())
\r
815 while (dit.MoveNext())
\r
818 if (!itemequalityComparer.Equals(dit.Current, dat.Current))
\r
826 if (!collection1.AllowsDuplicates && (collection2.AllowsDuplicates || collection2.ContainsSpeed >= collection1.ContainsSpeed))
\r
828 foreach (T x in collection1) if (!collection2.Contains(x)) return false;
\r
830 else if (!collection2.AllowsDuplicates)
\r
832 foreach (T x in collection2) if (!collection1.Contains(x)) return false;
\r
834 // Now tit.AllowsDuplicates && tat.AllowsDuplicates
\r
835 else if (collection1.DuplicatesByCounting && collection2.DuplicatesByCounting)
\r
837 foreach (T item in collection2) if (collection1.ContainsCount(item) != collection2.ContainsCount(item)) return false;
\r
841 //To avoid an O(n^2) algorithm, we make an aux hashtable to hold the count of items
\r
842 HashDictionary<T, int> dict = new HashDictionary<T, int>();
\r
843 foreach (T item in collection2)
\r
846 if (dict.FindOrAdd(item, ref count))
\r
847 dict[item] = count + 1;
\r
849 foreach (T item in collection1)
\r
852 if (dict.Find(item, out count) && count > 0)
\r
853 dict[item] = count - 1;
\r
865 /// Get the unsequenced collection hash code of this collection: from the cached
\r
866 /// value if present and up to date, else (re)compute.
\r
868 /// <returns>The hash code</returns>
\r
869 public virtual int GetUnsequencedHashCode()
\r
871 if (iUnSequencedHashCodeStamp == stamp)
\r
872 return iUnSequencedHashCode;
\r
874 iUnSequencedHashCode = ComputeHashCode(this, itemequalityComparer);
\r
875 iUnSequencedHashCodeStamp = stamp;
\r
876 return iUnSequencedHashCode;
\r
881 /// Check if the contents of that is equal to the contents of this
\r
882 /// in the unsequenced sense. Using the item equalityComparer of this collection.
\r
883 /// Assuming that the item EqualityComparer is compatible with otherCollection!
\r
885 /// <param name="otherCollection">The collection to compare to.</param>
\r
886 /// <returns>True if equal</returns>
\r
887 public virtual bool UnsequencedEquals(ICollection<T> otherCollection)
\r
889 return otherCollection != null && StaticEquals((ICollection<T>)this, otherCollection, itemequalityComparer);
\r
894 /// Check if the collection has been modified since a specified time, expressed as a stamp value.
\r
896 /// <exception cref="CollectionModifiedException"> if this collection has been updated
\r
897 /// since a target time</exception>
\r
898 /// <param name="thestamp">The stamp identifying the target time</param>
\r
899 protected virtual void modifycheck(int thestamp)
\r
901 if (this.stamp != thestamp)
\r
902 throw new CollectionModifiedException();
\r
907 /// Check if it is valid to perform update operations, and if so increment stamp.
\r
909 /// <exception cref="ReadOnlyCollectionException">If colection is read-only</exception>
\r
910 protected virtual void updatecheck()
\r
913 throw new ReadOnlyCollectionException();
\r
920 #region ICollection<T> members
\r
925 /// <value>True if this collection is read only</value>
\r
927 public virtual bool IsReadOnly { [Tested]get { return isReadOnly; } }
\r
931 #region ICollectionValue<T> members
\r
935 /// <value>The size of this collection</value>
\r
937 public override int Count { [Tested]get { return size; } }
\r
940 /// The value is symbolic indicating the type of asymptotic complexity
\r
941 /// in terms of the size of this collection (worst-case or amortized as
\r
944 /// <value>A characterization of the speed of the
\r
945 /// <code>Count</code> property in this collection.</value>
\r
946 public override Speed CountSpeed { get { return Speed.Constant; } }
\r
951 #region IExtensible<T> members
\r
956 /// <value></value>
\r
957 public virtual SCG.IEqualityComparer<T> EqualityComparer { get { return itemequalityComparer; } }
\r
962 /// <value>A distinguished object to use for locking to synchronize multithreaded access</value>
\r
964 public virtual object SyncRoot { get { return syncroot; } }
\r
970 /// <value>True if this collection is empty</value>
\r
972 public override bool IsEmpty { [Tested]get { return size == 0; } }
\r
976 #region IEnumerable<T> Members
\r
978 /// Create an enumerator for this collection.
\r
980 /// <returns>The enumerator</returns>
\r
981 public override abstract SCG.IEnumerator<T> GetEnumerator();
\r
988 /// <typeparam name="T"></typeparam>
\r
990 public abstract class DirectedCollectionBase<T> : CollectionBase<T>, IDirectedCollectionValue<T>
\r
995 /// <param name="itemequalityComparer"></param>
\r
996 public DirectedCollectionBase(SCG.IEqualityComparer<T> itemequalityComparer) : base(itemequalityComparer) { }
\r
998 /// <code>Forwards</code> if same, else <code>Backwards</code>
\r
1000 /// <value>The enumeration direction relative to the original collection.</value>
\r
1001 public virtual EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
\r
1006 /// <returns></returns>
\r
1007 public abstract IDirectedCollectionValue<T> Backwards();
\r
1009 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return this.Backwards(); }
\r
1012 /// Check if there exists an item that satisfies a
\r
1013 /// specific predicate in this collection and return the first one in enumeration order.
\r
1015 /// <param name="predicate">A delegate
\r
1016 /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
\r
1017 /// <param name="item"></param>
\r
1018 /// <returns>True is such an item exists</returns>
\r
1019 public virtual bool FindLast(Fun<T, bool> predicate, out T item)
\r
1021 foreach (T jtem in Backwards())
\r
1022 if (predicate(jtem))
\r
1027 item = default(T);
\r
1033 /// Base class (abstract) for sequenced collection implementations.
\r
1036 public abstract class SequencedBase<T> : DirectedCollectionBase<T>, IDirectedCollectionValue<T>
\r
1040 int iSequencedHashCode, iSequencedHashCodeStamp = -1;
\r
1047 /// <param name="itemequalityComparer"></param>
\r
1048 public SequencedBase(SCG.IEqualityComparer<T> itemequalityComparer) : base(itemequalityComparer) { }
\r
1052 //TODO: make random for release
\r
1053 const int HASHFACTOR = 31;
\r
1056 /// Compute the unsequenced hash code of a collection
\r
1058 /// <param name="items">The collection to compute hash code for</param>
\r
1059 /// <param name="itemequalityComparer">The item equalityComparer</param>
\r
1060 /// <returns>The hash code</returns>
\r
1062 public static int ComputeHashCode(ISequenced<T> items, SCG.IEqualityComparer<T> itemequalityComparer)
\r
1064 //NOTE: It must be possible to devise a much stronger combined hashcode,
\r
1065 //but unfortunately, it has to be universal. OR we could use a (strong)
\r
1066 //family and initialise its parameter randomly at load time of this class!
\r
1067 //(We would not want to have yet a flag to check for invalidation?!)
\r
1068 //NBNBNB: the current hashcode has the very bad property that items with hashcode 0
\r
1070 int iIndexedHashCode = 0;
\r
1072 foreach (T item in items)
\r
1073 iIndexedHashCode = iIndexedHashCode * HASHFACTOR + itemequalityComparer.GetHashCode(item);
\r
1075 return iIndexedHashCode;
\r
1080 /// Examine if tit and tat are equal as sequenced collections
\r
1081 /// using the specified item equalityComparer (assumed compatible with the two collections).
\r
1083 /// <param name="collection1">The first collection</param>
\r
1084 /// <param name="collection2">The second collection</param>
\r
1085 /// <param name="itemequalityComparer">The item equalityComparer to use for comparison</param>
\r
1086 /// <returns>True if equal</returns>
\r
1088 public static bool StaticEquals(ISequenced<T> collection1, ISequenced<T> collection2, SCG.IEqualityComparer<T> itemequalityComparer)
\r
1090 if (object.ReferenceEquals(collection1, collection2))
\r
1093 if (collection1.Count != collection2.Count)
\r
1096 //This way we might run through both enumerations twice, but
\r
1097 //probably not (if the hash codes are good)
\r
1098 if (collection1.GetSequencedHashCode() != collection2.GetSequencedHashCode())
\r
1101 using (SCG.IEnumerator<T> dat = collection2.GetEnumerator(), dit = collection1.GetEnumerator())
\r
1103 while (dit.MoveNext())
\r
1106 if (!itemequalityComparer.Equals(dit.Current, dat.Current))
\r
1116 /// Get the sequenced collection hash code of this collection: from the cached
\r
1117 /// value if present and up to date, else (re)compute.
\r
1119 /// <returns>The hash code</returns>
\r
1120 public virtual int GetSequencedHashCode()
\r
1122 if (iSequencedHashCodeStamp == stamp)
\r
1123 return iSequencedHashCode;
\r
1125 iSequencedHashCode = ComputeHashCode((ISequenced<T>)this, itemequalityComparer);
\r
1126 iSequencedHashCodeStamp = stamp;
\r
1127 return iSequencedHashCode;
\r
1132 /// Check if the contents of that is equal to the contents of this
\r
1133 /// in the sequenced sense. Using the item equalityComparer of this collection.
\r
1135 /// <param name="otherCollection">The collection to compare to.</param>
\r
1136 /// <returns>True if equal</returns>
\r
1137 public virtual bool SequencedEquals(ISequenced<T> otherCollection)
\r
1139 return StaticEquals((ISequenced<T>)this, otherCollection, itemequalityComparer);
\r
1146 /// Create an enumerator for this collection.
\r
1148 /// <returns>The enumerator</returns>
\r
1149 public override abstract SCG.IEnumerator<T> GetEnumerator();
\r
1152 /// <code>Forwards</code> if same, else <code>Backwards</code>
\r
1154 /// <value>The enumeration direction relative to the original collection.</value>
\r
1156 public override EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
\r
1159 /// Check if there exists an item that satisfies a
\r
1160 /// specific predicate in this collection and return the index of the first one.
\r
1162 /// <param name="predicate">A delegate
\r
1163 /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
\r
1164 /// <returns>the index, if found, a negative value else</returns>
\r
1165 public int FindIndex(Fun<T, bool> predicate)
\r
1168 foreach (T item in this)
\r
1170 if (predicate(item))
\r
1178 /// Check if there exists an item that satisfies a
\r
1179 /// specific predicate in this collection and return the index of the last one.
\r
1181 /// <param name="predicate">A delegate
\r
1182 /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
\r
1183 /// <returns>the index, if found, a negative value else</returns>
\r
1184 public int FindLastIndex(Fun<T, bool> predicate)
\r
1186 int index = Count - 1;
\r
1187 foreach (T item in Backwards())
\r
1189 if (predicate(item))
\r
1200 /// Base class for collection classes of dynamic array type implementations.
\r
1203 public abstract class ArrayBase<T> : SequencedBase<T>
\r
1207 /// The actual internal array container. Will be extended on demand.
\r
1209 protected T[] array;
\r
1212 /// The offset into the internal array container of the first item. The offset is 0 for a
\r
1213 /// base dynamic array and may be positive for an updatable view into a base dynamic array.
\r
1215 protected int offset;
\r
1220 /// Double the size of the internal array.
\r
1222 protected virtual void expand()
\r
1224 expand(2 * array.Length, size);
\r
1229 /// Expand the internal array container.
\r
1231 /// <param name="newcapacity">The new size of the internal array -
\r
1232 /// will be rounded upwards to a power of 2.</param>
\r
1233 /// <param name="newsize">The (new) size of the (base) collection.</param>
\r
1234 protected virtual void expand(int newcapacity, int newsize)
\r
1236 Debug.Assert(newcapacity >= newsize);
\r
1238 int newlength = array.Length;
\r
1240 while (newlength < newcapacity) newlength *= 2;
\r
1242 T[] newarray = new T[newlength];
\r
1244 Array.Copy(array, newarray, newsize);
\r
1250 /// Insert an item at a specific index, moving items to the right
\r
1251 /// upwards and expanding the array if necessary.
\r
1253 /// <param name="i">The index at which to insert.</param>
\r
1254 /// <param name="item">The item to insert.</param>
\r
1255 protected virtual void insert(int i, T item)
\r
1257 if (size == array.Length)
\r
1261 Array.Copy(array, i, array, i + 1, size - i);
\r
1269 #region Constructors
\r
1272 /// Create an empty ArrayBase object.
\r
1274 /// <param name="capacity">The initial capacity of the internal array container.
\r
1275 /// Will be rounded upwards to the nearest power of 2 greater than or equal to 8.</param>
\r
1276 /// <param name="itemequalityComparer">The item equalityComparer to use, primarily for item equality</param>
\r
1277 public ArrayBase(int capacity, SCG.IEqualityComparer<T> itemequalityComparer)
\r
1278 : base(itemequalityComparer)
\r
1280 int newlength = 8;
\r
1281 while (newlength < capacity) newlength *= 2;
\r
1282 array = new T[newlength];
\r
1287 #region IIndexed members
\r
1291 /// <exception cref="ArgumentOutOfRangeException">If the arguments does not describe a
\r
1292 /// valid range in the indexed collection, cf. <see cref="M:C5.CollectionBase`1.checkRange(System.Int32,System.Int32)"/>.</exception>
\r
1293 /// <value>The directed collection of items in a specific index interval.</value>
\r
1294 /// <param name="start">The low index of the interval (inclusive).</param>
\r
1295 /// <param name="count">The size of the range.</param>
\r
1297 public virtual IDirectedCollectionValue<T> this[int start, int count]
\r
1302 checkRange(start, count);
\r
1303 return new Range(this, start, count, true);
\r
1309 #region IEditableCollection members
\r
1311 /// Remove all items and reset size of internal array container.
\r
1314 public virtual void Clear()
\r
1323 /// Create an array containing (copies) of the items of this collection in enumeration order.
\r
1325 /// <returns>The new array</returns>
\r
1327 public override T[] ToArray()
\r
1329 T[] res = new T[size];
\r
1331 Array.Copy(array, offset, res, 0, size);
\r
1337 /// Perform an internal consistency (invariant) test on the array base.
\r
1339 /// <returns>True if test succeeds.</returns>
\r
1341 public virtual bool Check()
\r
1343 bool retval = true;
\r
1345 if (size > array.Length)
\r
1347 Console.WriteLine("Bad size ({0}) > array.Length ({1})", size, array.Length);
\r
1351 for (int i = 0; i < size; i++)
\r
1353 if ((object)(array[i]) == null)
\r
1355 Console.WriteLine("Bad element: null at index {0}", i);
\r
1365 #region IDirectedCollection<T> Members
\r
1368 /// Create a directed collection with the same contents as this one, but
\r
1369 /// opposite enumeration sequence.
\r
1371 /// <returns>The mirrored collection.</returns>
\r
1373 public override IDirectedCollectionValue<T> Backwards() { return this[0, size].Backwards(); }
\r
1378 /// Choose some item of this collection. The result is the last item in the internal array,
\r
1379 /// making it efficient to remove.
\r
1381 /// <exception cref="NoSuchItemException">if collection is empty.</exception>
\r
1382 /// <returns></returns>
\r
1383 public override T Choose() { if (size > 0) return array[size - 1]; throw new NoSuchItemException(); }
\r
1385 #region IEnumerable<T> Members
\r
1387 /// Create an enumerator for this array based collection.
\r
1389 /// <returns>The enumerator</returns>
\r
1391 public override SCG.IEnumerator<T> GetEnumerator()
\r
1393 int thestamp = stamp, theend = size + offset, thestart = offset;
\r
1395 for (int i = thestart; i < theend; i++)
\r
1397 modifycheck(thestamp);
\r
1398 yield return array[i];
\r
1403 #region Range nested class
\r
1405 /// A helper class for defining results of interval queries on array based collections.
\r
1407 protected class Range : DirectedCollectionValueBase<T>, IDirectedCollectionValue<T>
\r
1409 int start, count, delta, stamp;
\r
1411 ArrayBase<T> thebase;
\r
1414 internal Range(ArrayBase<T> thebase, int start, int count, bool forwards)
\r
1416 this.thebase = thebase; stamp = thebase.stamp;
\r
1417 delta = forwards ? 1 : -1;
\r
1418 this.start = start + thebase.offset; this.count = count;
\r
1424 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1425 /// <value>True if this collection is empty.</value>
\r
1426 public override bool IsEmpty { get { thebase.modifycheck(stamp); return count == 0; } }
\r
1432 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1433 /// <value>The number of items in the range</value>
\r
1435 public override int Count { [Tested]get { thebase.modifycheck(stamp); return count; } }
\r
1438 /// The value is symbolic indicating the type of asymptotic complexity
\r
1439 /// in terms of the size of this collection (worst-case or amortized as
\r
1442 /// <value>A characterization of the speed of the
\r
1443 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1444 /// <code>Count</code> property in this collection.</value>
\r
1445 public override Speed CountSpeed { get { thebase.modifycheck(stamp); return Speed.Constant; } }
\r
1448 /// Choose some item of this collection.
\r
1450 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1451 /// <exception cref="NoSuchItemException">if range is empty.</exception>
\r
1452 /// <returns></returns>
\r
1453 public override T Choose()
\r
1455 thebase.modifycheck(stamp);
\r
1457 throw new NoSuchItemException();
\r
1458 return thebase.array[start];
\r
1463 /// Create an enumerator for this range of an array based collection.
\r
1465 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1466 /// <returns>The enumerator</returns>
\r
1468 public override SCG.IEnumerator<T> GetEnumerator()
\r
1470 for (int i = 0; i < count; i++)
\r
1472 thebase.modifycheck(stamp);
\r
1473 yield return thebase.array[start + delta * i];
\r
1479 /// Create a araay collection range with the same contents as this one, but
\r
1480 /// opposite enumeration sequence.
\r
1482 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1483 /// <returns>The mirrored collection.</returns>
\r
1485 public override IDirectedCollectionValue<T> Backwards()
\r
1487 thebase.modifycheck(stamp);
\r
1489 Range res = (Range)MemberwiseClone();
\r
1491 res.delta = -delta;
\r
1492 res.start = start + (count - 1) * delta;
\r
1497 IDirectedEnumerable<T> C5.IDirectedEnumerable<T>.Backwards()
\r
1499 return Backwards();
\r
1504 /// <code>Forwards</code> if same, else <code>Backwards</code>
\r
1506 /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
\r
1507 /// <value>The enumeration direction relative to the original collection.</value>
\r
1509 public override EnumerationDirection Direction
\r
1514 thebase.modifycheck(stamp);
\r
1515 return delta > 0 ? EnumerationDirection.Forwards : EnumerationDirection.Backwards;
\r