--- /dev/null
+#if NET_2_0\r
+/*\r
+ Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>\r
+ Permission is hereby granted, free of charge, to any person obtaining a copy\r
+ of this software and associated documentation files (the "Software"), to deal\r
+ in the Software without restriction, including without limitation the rights\r
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
+ copies of the Software, and to permit persons to whom the Software is\r
+ furnished to do so, subject to the following conditions:\r
+ \r
+ The above copyright notice and this permission notice shall be included in\r
+ all copies or substantial portions of the Software.\r
+ \r
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
+ SOFTWARE.\r
+*/\r
+\r
+using System;\r
+using System.Diagnostics;\r
+using MSG = System.Collections.Generic;\r
+namespace C5\r
+{\r
+ /// <summary>\r
+ /// Direction of enumeration order relative to original collection.\r
+ /// </summary>\r
+ public enum EnumerationDirection { \r
+ /// <summary>\r
+ /// Same direction\r
+ /// </summary>\r
+ Forwards, \r
+ /// <summary>\r
+ /// Opposite direction\r
+ /// </summary>\r
+ Backwards \r
+ }\r
+\r
+ #region int stuff\r
+ class IC: IComparer<int>\r
+ {\r
+ [Tested]\r
+ public int Compare(int a, int b) { return a > b ? 1 : a < b ? -1 : 0; }\r
+ }\r
+\r
+\r
+\r
+ /// <summary>\r
+ /// A hasher for int32\r
+ /// </summary>\r
+ public class IntHasher: IHasher<int>\r
+ {\r
+ /// <summary>\r
+ /// Get the hash code of this integer, i.e. itself\r
+ /// </summary>\r
+ /// <param name="item">The integer</param>\r
+ /// <returns>The same</returns>\r
+ [Tested]\r
+ public int GetHashCode(int item) { return item; }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if two integers are equal\r
+ /// </summary>\r
+ /// <param name="i1">first integer</param>\r
+ /// <param name="i2">second integer</param>\r
+ /// <returns>True if equal</returns>\r
+ [Tested]\r
+ public bool Equals(int i1, int i2) { return i1 == i2; }\r
+ }\r
+\r
+\r
+ #endregion\r
+\r
+ #region Natural Comparers\r
+\r
+\r
+ /// <summary>\r
+ /// A natural generic IComparer for an IComparable<T> item type\r
+ /// </summary>\r
+ public class NaturalComparer<T>: IComparer<T>\r
+ where T: IComparable<T>\r
+ {\r
+ /// <summary>\r
+ /// Compare two items\r
+ /// </summary>\r
+ /// <param name="a">First item</param>\r
+ /// <param name="b">Second item</param>\r
+ /// <returns>a <=> b</returns>\r
+ [Tested]\r
+ public int Compare(T a, T b) { return a.CompareTo(b); }\r
+ }\r
+\r
+\r
+\r
+ /// <summary>\r
+ /// A natural generic IComparer for a System.IComparable item type\r
+ /// </summary>\r
+ public class NaturalComparerO<T>: IComparer<T>\r
+ where T: System.IComparable\r
+ {\r
+ /// <summary>\r
+ /// Compare two items\r
+ /// </summary>\r
+ /// <param name="a">First item</param>\r
+ /// <param name="b">Second item</param>\r
+ /// <returns>a <=> b</returns>\r
+ [Tested]\r
+ public int Compare(T a, T b) { return a.CompareTo(b); }\r
+ }\r
+\r
+\r
+\r
+ #endregion\r
+\r
+ #region Hashers\r
+ /// <summary>\r
+ /// The default item hasher for a reference type. A trivial wrapper for calling \r
+ /// the GetHashCode and Equals methods inherited from object.\r
+ ///\r
+ /// <p>Should only be instantiated with a reference type as generic type parameter. \r
+ /// This is asserted at instatiation time in Debug builds.</p>\r
+ /// </summary>\r
+ public sealed class DefaultReferenceTypeHasher<T>: IHasher<T>\r
+ {\r
+ static DefaultReferenceTypeHasher()\r
+ {\r
+ Debug.Assert(!typeof(T).IsValueType, "DefaultReferenceTypeHasher instantiated with value type: " + typeof(T));\r
+ }\r
+ \r
+ /// <summary>\r
+ /// Get the hash code with respect to this item hasher\r
+ /// </summary>\r
+ /// <param name="item">The item</param>\r
+ /// <returns>The hash code</returns>\r
+ [Tested]\r
+ public int GetHashCode(T item) { return item.GetHashCode(); }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if two items are equal with respect to this item hasher\r
+ /// </summary>\r
+ /// <param name="i1">first item</param>\r
+ /// <param name="i2">second item</param>\r
+ /// <returns>True if equal</returns>\r
+ [Tested]\r
+ public bool Equals(T i1, T i2)\r
+ {\r
+ //For reference types, the (object) cast should be jitted as a noop. \r
+ return (object)i1 == null ? (object)i2 == null : i1.Equals(i2);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// The default item hasher for a value type. A trivial wrapper for calling \r
+ /// the GetHashCode and Equals methods inherited from object.\r
+ ///\r
+ /// <p>Should only be instantiated with a value type as generic type parameter. \r
+ /// This is asserted at instatiation time in Debug builds.</p>\r
+ /// <p>We cannot add the constraint "where T : struct" to get a compile time check\r
+ /// because we need to instantiate this class in C5.HasherBuilder.ByPrototype[T].Examine()\r
+ /// with a T that is only known at runtime to be a value type!</p>\r
+ /// </summary>\r
+ \r
+ //Note: we could (now) add a constraint "where T : struct" to get a compile time check,\r
+ //but \r
+ public sealed class DefaultValueTypeHasher<T>: IHasher<T>\r
+ {\r
+ static DefaultValueTypeHasher()\r
+ {\r
+ Debug.Assert(typeof(T).IsValueType, "DefaultValueTypeHasher instantiated with reference type: " + typeof(T));\r
+ }\r
+ /// <summary>\r
+ /// Get the hash code with respect to this item hasher\r
+ /// </summary>\r
+ /// <param name="item">The item</param>\r
+ /// <returns>The hash code</returns>\r
+ [Tested]\r
+ public int GetHashCode(T item) { return item.GetHashCode(); }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if two items are equal with respect to this item hasher\r
+ /// </summary>\r
+ /// <param name="i1">first item</param>\r
+ /// <param name="i2">second item</param>\r
+ /// <returns>True if equal</returns>\r
+ [Tested]\r
+ public bool Equals(T i1, T i2) { return i1.Equals(i2); }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region Bases\r
+\r
+ /// <summary>\r
+ /// A base class for implementing an IEnumerable<T>\r
+ /// </summary>\r
+ public abstract class EnumerableBase<T>: MSG.IEnumerable<T>\r
+ {\r
+ /// <summary>\r
+ /// Create an enumerator for this collection.\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ public abstract MSG.IEnumerator<T> GetEnumerator();\r
+\r
+ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()\r
+ {\r
+ return GetEnumerator ();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Count the number of items in an enumerable by enumeration\r
+ /// </summary>\r
+ /// <param name="items">The enumerable to count</param>\r
+ /// <returns>The size of the enumerable</returns>\r
+ protected static int countItems(MSG.IEnumerable<T> items)\r
+ {\r
+ ICollectionValue<T> jtems = items as ICollectionValue<T>;\r
+\r
+ if (jtems != null)\r
+ return jtems.Count;\r
+\r
+ int count = 0;\r
+\r
+ using (MSG.IEnumerator<T> e = items.GetEnumerator())\r
+ while (e.MoveNext()) count++;\r
+\r
+ return count;\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Base class for classes implementing ICollectionValue[T]\r
+ /// </summary>\r
+ public abstract class CollectionValueBase<T>: EnumerableBase<T>, ICollectionValue<T>\r
+ {\r
+ //This forces our subclasses to make Count virtual!\r
+ /// <summary>\r
+ /// The number of items in this collection.\r
+ /// </summary>\r
+ /// <value></value>\r
+ public abstract int Count { get;}\r
+\r
+ /// <summary>\r
+ /// The value is symbolic indicating the type of asymptotic complexity\r
+ /// in terms of the size of this collection (worst-case or amortized as\r
+ /// relevant).\r
+ /// </summary>\r
+ /// <value>A characterization of the speed of the \r
+ /// <code>Count</code> property in this collection.</value>\r
+ public abstract Speed CountSpeed { get; }\r
+\r
+\r
+ /// <summary>\r
+ /// Copy the items of this collection to part of an array.\r
+ /// <exception cref="ArgumentOutOfRangeException"/> if i is negative.\r
+ /// <exception cref="ArgumentException"/> if the array does not have room for the items.\r
+ /// </summary>\r
+ /// <param name="a">The array to copy to</param>\r
+ /// <param name="i">The starting index.</param>\r
+ [Tested]\r
+ public virtual void CopyTo(T[] a, int i)\r
+ {\r
+ if (i < 0)\r
+ throw new ArgumentOutOfRangeException();\r
+\r
+ if (i + Count > a.Length)\r
+ throw new ArgumentException();\r
+\r
+ foreach (T item in this) a[i++] = item;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an array with the items of this collection (in the same order as an\r
+ /// enumerator would output them).\r
+ /// </summary>\r
+ /// <returns>The array</returns>\r
+ //[Tested]\r
+ public virtual T[] ToArray()\r
+ {\r
+ T[] res = new T[Count];\r
+ int i = 0;\r
+\r
+ foreach (T item in this) res[i++] = item;\r
+\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Apply an Applier<T> to this enumerable\r
+ /// </summary>\r
+ /// <param name="a">The applier delegate</param>\r
+ [Tested]\r
+ public void Apply(Applier<T> a)\r
+ {\r
+ foreach (T item in this)\r
+ a(item);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if there exists an item that satisfies a\r
+ /// specific predicate in this collection.\r
+ /// </summary>\r
+ /// <param name="filter">A filter delegate \r
+ /// (<see cref="T:C5.Filter!1"/>) defining the predicate</param>\r
+ /// <returns>True is such an item exists</returns>\r
+ [Tested]\r
+ public bool Exists(Filter<T> filter)\r
+ {\r
+ foreach (T item in this)\r
+ if (filter(item))\r
+ return true;\r
+\r
+ return false;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if all items in this collection satisfies a specific predicate.\r
+ /// </summary>\r
+ /// <param name="filter">A filter delegate \r
+ /// (<see cref="T:C5.Filter!1"/>) defining the predicate</param>\r
+ /// <returns>True if all items satisfies the predicate</returns>\r
+ [Tested]\r
+ public bool All(Filter<T> filter)\r
+ {\r
+ foreach (T item in this)\r
+ if (!filter(item))\r
+ return false;\r
+\r
+ return true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an enumerator for this collection.\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ public override abstract MSG.IEnumerator<T> GetEnumerator();\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Base class (abstract) for ICollection implementations.\r
+ /// </summary>\r
+ public abstract class CollectionBase<T>: CollectionValueBase<T>\r
+ {\r
+ #region Fields\r
+\r
+ object syncroot = new object();\r
+\r
+ /// <summary>\r
+ /// The underlying field of the ReadOnly property\r
+ /// </summary>\r
+ protected bool isReadOnly = false;\r
+\r
+ /// <summary>\r
+ /// The current stamp value\r
+ /// </summary>\r
+ protected int stamp;\r
+\r
+ /// <summary>\r
+ /// The number of items in the collection\r
+ /// </summary>\r
+ protected int size;\r
+\r
+ /// <summary>\r
+ /// The item hasher of the collection\r
+ /// </summary>\r
+ protected IHasher<T> itemhasher;\r
+\r
+ int iUnSequencedHashCode, iUnSequencedHashCodeStamp = -1;\r
+\r
+ #endregion\r
+ \r
+ #region Util\r
+\r
+ //protected bool equals(T i1, T i2) { return itemhasher.Equals(i1, i2); }\r
+ /// <summary>\r
+ /// Utility method for range checking.\r
+ /// <exception cref="ArgumentOutOfRangeException"/> if the start or count is negative\r
+ /// <exception cref="ArgumentException"/> if the range does not fit within collection size.\r
+ /// </summary>\r
+ /// <param name="start">start of range</param>\r
+ /// <param name="count">size of range</param>\r
+ [Tested]\r
+ protected void checkRange(int start, int count)\r
+ {\r
+ if (start < 0 || count < 0)\r
+ throw new ArgumentOutOfRangeException();\r
+\r
+ if (start + count > size)\r
+ throw new ArgumentException();\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Compute the unsequenced hash code of a collection\r
+ /// </summary>\r
+ /// <param name="items">The collection to compute hash code for</param>\r
+ /// <param name="itemhasher">The item hasher</param>\r
+ /// <returns>The hash code</returns>\r
+ [Tested]\r
+ public static int ComputeHashCode(ICollectionValue<T> items, IHasher<T> itemhasher)\r
+ {\r
+ int h = 0;\r
+\r
+ foreach (T item in items)\r
+ h ^= itemhasher.GetHashCode(item);\r
+\r
+ return (items.Count << 16) + h;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Examine if tit and tat are equal as unsequenced collections\r
+ /// using the specified item hasher (assumed compatible with the two collections).\r
+ /// </summary>\r
+ /// <param name="tit">The first collection</param>\r
+ /// <param name="tat">The second collection</param>\r
+ /// <param name="itemhasher">The item hasher to use for comparison</param>\r
+ /// <returns>True if equal</returns>\r
+ [Tested]\r
+ public static bool StaticEquals(ICollection<T> tit, ICollection<T> tat, IHasher<T> itemhasher)\r
+ {\r
+ if (tat == null)\r
+ return tit == null;\r
+\r
+ if (tit.Count != tat.Count)\r
+ return false;\r
+\r
+ //This way we might run through both enumerations twice, but\r
+ //probably not (if the hash codes are good)\r
+ if (tit.GetHashCode() != tat.GetHashCode())\r
+ return false;\r
+\r
+ if (!tit.AllowsDuplicates && (tat.AllowsDuplicates || tat.ContainsSpeed >= tit.ContainsSpeed))\r
+ {\r
+ //TODO: use foreach construction\r
+ using (MSG.IEnumerator<T> dit = tit.GetEnumerator())\r
+ {\r
+ while (dit.MoveNext())\r
+ if (!tat.Contains(dit.Current))\r
+ return false;\r
+ }\r
+ }\r
+ else if (!tat.AllowsDuplicates)\r
+ {\r
+ using (MSG.IEnumerator<T> dat = tat.GetEnumerator())\r
+ {\r
+ while (dat.MoveNext())\r
+ if (!tit.Contains(dat.Current))\r
+ return false;\r
+ }\r
+ }\r
+ else\r
+ {//both are bags, we only have a slow one\r
+ //unless the bags are based on a fast T->int dictinary (tree or hash) \r
+ using (MSG.IEnumerator<T> dat = tat.GetEnumerator())\r
+ {\r
+ while (dat.MoveNext())\r
+ {\r
+ T item = dat.Current;\r
+\r
+ if (tit.ContainsCount(item) != tat.ContainsCount(item))\r
+ return false;\r
+ }\r
+ }\r
+ //That was O(n^3) - completely unacceptable.\r
+ //If we use an auxiliary bool[] we can do the comparison in O(n^2)\r
+ }\r
+\r
+ return true;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get the unsequenced collection hash code of this collection: from the cached \r
+ /// value if present and up to date, else (re)compute.\r
+ /// </summary>\r
+ /// <returns>The hash code</returns>\r
+ protected int unsequencedhashcode()\r
+ {\r
+ if (iUnSequencedHashCodeStamp == stamp)\r
+ return iUnSequencedHashCode;\r
+\r
+ iUnSequencedHashCode = ComputeHashCode(this, itemhasher);\r
+ iUnSequencedHashCodeStamp = stamp;\r
+ return iUnSequencedHashCode;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if the contents of that is equal to the contents of this\r
+ /// in the unsequenced sense. Using the item hasher of this collection.\r
+ /// </summary>\r
+ /// <param name="that">The collection to compare to.</param>\r
+ /// <returns>True if equal</returns>\r
+ protected bool unsequencedequals(ICollection<T> that)\r
+ {\r
+ return StaticEquals((ICollection<T>)this, that, itemhasher);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// <exception cref="InvalidOperationException"/> if this collection has been updated \r
+ /// since a target time\r
+ /// </summary>\r
+ /// <param name="thestamp">The stamp identifying the target time</param>\r
+ protected virtual void modifycheck(int thestamp)\r
+ {\r
+ if (this.stamp != thestamp)\r
+ throw new InvalidOperationException("Collection was modified");\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if it is valid to perform update operations, and if so increment stamp\r
+ /// </summary>\r
+ protected virtual void updatecheck()\r
+ {\r
+ if (isReadOnly)\r
+ throw new InvalidOperationException("Collection cannot be modified through this guard object");\r
+\r
+ stamp++;\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IEditableCollection<T> members\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>True if this collection is read only</value>\r
+ [Tested]\r
+ public bool IsReadOnly { [Tested]get { return isReadOnly; } }\r
+\r
+ #endregion\r
+\r
+ #region ICollection<T> members\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>The size of this collection</value>\r
+ [Tested]\r
+ public override int Count { [Tested]get { return size; } }\r
+\r
+ /// <summary>\r
+ /// The value is symbolic indicating the type of asymptotic complexity\r
+ /// in terms of the size of this collection (worst-case or amortized as\r
+ /// relevant).\r
+ /// </summary>\r
+ /// <value>A characterization of the speed of the \r
+ /// <code>Count</code> property in this collection.</value>\r
+ public override Speed CountSpeed { get { return Speed.Constant; } }\r
+\r
+\r
+ #endregion\r
+\r
+ #region ISink<T> members\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>A distinguished object to use for locking to synchronize multithreaded access</value>\r
+ [Tested]\r
+ public object SyncRoot { get { return syncroot; } }\r
+\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>True is this collection is empty</value>\r
+ [Tested]\r
+ public bool IsEmpty { [Tested]get { return size == 0; } }\r
+ #endregion\r
+\r
+ #region IEnumerable<T> Members\r
+ /// <summary>\r
+ /// Create an enumerator for this collection.\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ public override abstract MSG.IEnumerator<T> GetEnumerator();\r
+ #endregion\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Base class (abstract) for sequenced collection implementations.\r
+ /// </summary>\r
+ public abstract class SequencedBase<T>: CollectionBase<T>\r
+ {\r
+ #region Fields\r
+\r
+ int iSequencedHashCode, iSequencedHashCodeStamp = -1;\r
+\r
+ #endregion\r
+\r
+ #region Util\r
+\r
+ /// <summary>\r
+ /// Compute the unsequenced hash code of a collection\r
+ /// </summary>\r
+ /// <param name="items">The collection to compute hash code for</param>\r
+ /// <param name="itemhasher">The item hasher</param>\r
+ /// <returns>The hash code</returns>\r
+ [Tested]\r
+ public static int ComputeHashCode(ISequenced<T> items, IHasher<T> itemhasher)\r
+ {\r
+ //NOTE: It must be possible to devise a much stronger combined hashcode, \r
+ //but unfortunately, it has to be universal. OR we could use a (strong)\r
+ //family and initialise its parameter randomly at load time of this class!\r
+ //(We would not want to have yet a flag to check for invalidation?!)\r
+ int iIndexedHashCode = 0;\r
+\r
+ foreach (T item in items)\r
+ iIndexedHashCode = iIndexedHashCode * 31 + itemhasher.GetHashCode(item);\r
+\r
+ return iIndexedHashCode;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Examine if tit and tat are equal as sequenced collections\r
+ /// using the specified item hasher (assumed compatible with the two collections).\r
+ /// </summary>\r
+ /// <param name="tit">The first collection</param>\r
+ /// <param name="tat">The second collection</param>\r
+ /// <param name="itemhasher">The item hasher to use for comparison</param>\r
+ /// <returns>True if equal</returns>\r
+ [Tested]\r
+ public static bool StaticEquals(ISequenced<T> tit, ISequenced<T> tat, IHasher<T> itemhasher)\r
+ {\r
+ if (tat == null)\r
+ return tit == null;\r
+\r
+ if (tit.Count != tat.Count)\r
+ return false;\r
+\r
+ //This way we might run through both enumerations twice, but\r
+ //probably not (if the hash codes are good)\r
+ if (tit.GetHashCode() != tat.GetHashCode())\r
+ return false;\r
+\r
+ using (MSG.IEnumerator<T> dat = tat.GetEnumerator(), dit = tit.GetEnumerator())\r
+ {\r
+ while (dit.MoveNext())\r
+ {\r
+ dat.MoveNext();\r
+ if (!itemhasher.Equals(dit.Current, dat.Current))\r
+ return false;\r
+ }\r
+ }\r
+\r
+ return true;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get the sequenced collection hash code of this collection: from the cached \r
+ /// value if present and up to date, else (re)compute.\r
+ /// </summary>\r
+ /// <returns>The hash code</returns>\r
+ protected int sequencedhashcode()\r
+ {\r
+ if (iSequencedHashCodeStamp == stamp)\r
+ return iSequencedHashCode;\r
+\r
+ iSequencedHashCode = ComputeHashCode((ISequenced<T>)this, itemhasher);\r
+ iSequencedHashCodeStamp = stamp;\r
+ return iSequencedHashCode;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Check if the contents of that is equal to the contents of this\r
+ /// in the sequenced sense. Using the item hasher of this collection.\r
+ /// </summary>\r
+ /// <param name="that">The collection to compare to.</param>\r
+ /// <returns>True if equal</returns>\r
+ protected bool sequencedequals(ISequenced<T> that)\r
+ {\r
+ return StaticEquals((ISequenced<T>)this, that, itemhasher);\r
+ }\r
+\r
+\r
+ #endregion\r
+\r
+ /// <summary>\r
+ /// Create an enumerator for this collection.\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ public override abstract MSG.IEnumerator<T> GetEnumerator();\r
+\r
+\r
+ /// <summary>\r
+ /// <code>Forwards</code> if same, else <code>Backwards</code>\r
+ /// </summary>\r
+ /// <value>The enumeration direction relative to the original collection.</value>\r
+ [Tested]\r
+ public EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Base class for collection classes of dynamic array type implementations.\r
+ /// </summary>\r
+ public class ArrayBase<T>: SequencedBase<T>\r
+ {\r
+ #region Fields\r
+ /// <summary>\r
+ /// The actual internal array container. Will be extended on demand.\r
+ /// </summary>\r
+ protected T[] array;\r
+\r
+ /// <summary>\r
+ /// The offset into the internal array container of the first item. The offset is 0 for a \r
+ /// base dynamic array and may be positive for an updatable view into a base dynamic array.\r
+ /// </summary>\r
+ protected int offset;\r
+ #endregion\r
+\r
+ #region Util\r
+ /// <summary>\r
+ /// Double the size of the internal array.\r
+ /// </summary>\r
+ protected virtual void expand()\r
+ {\r
+ expand(2 * array.Length, size);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Expand the internal array container.\r
+ /// </summary>\r
+ /// <param name="newcapacity">The new size of the internal array - \r
+ /// will be rounded upwards to a power of 2.</param>\r
+ /// <param name="newsize">The (new) size of the (base) collection.</param>\r
+ protected virtual void expand(int newcapacity, int newsize)\r
+ {\r
+ Debug.Assert(newcapacity >= newsize);\r
+\r
+ int newlength = array.Length;\r
+\r
+ while (newlength < newcapacity) newlength *= 2;\r
+\r
+ T[] newarray = new T[newlength];\r
+\r
+ Array.Copy(array, newarray, newsize);\r
+ array = newarray;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Insert an item at a specific index, moving items to the right\r
+ /// upwards and expanding the array if necessary.\r
+ /// </summary>\r
+ /// <param name="i">The index at which to insert.</param>\r
+ /// <param name="item">The item to insert.</param>\r
+ protected virtual void insert(int i, T item)\r
+ {\r
+ if (size == array.Length)\r
+ expand();\r
+\r
+ if (i < size)\r
+ Array.Copy(array, i, array, i + 1, size - i);\r
+\r
+ array[i] = item;\r
+ size++;\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region Constructors\r
+\r
+ /// <summary>\r
+ /// Create an empty ArrayBase object.\r
+ /// </summary>\r
+ /// <param name="capacity">The initial capacity of the internal array container.\r
+ /// Will be rounded upwards to the nearest power of 2 greater than or equal to 8.</param>\r
+ /// <param name="hasher">The item hasher to use, primarily for item equality</param>\r
+ public ArrayBase(int capacity, IHasher<T> hasher)\r
+ {\r
+ int newlength = 8;\r
+\r
+ while (newlength < capacity) newlength *= 2;\r
+\r
+ array = new T[newlength];\r
+ itemhasher = hasher;\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IIndexed members\r
+\r
+ /// <summary>\r
+ /// <exception cref="IndexOutOfRangeException"/>.\r
+ /// </summary>\r
+ /// <value>The directed collection of items in a specific index interval.</value>\r
+ /// <param name="start">The low index of the interval (inclusive).</param>\r
+ /// <param name="count">The size of the range.</param>\r
+ [Tested]\r
+ public IDirectedCollectionValue<T> this[int start, int count]\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+ checkRange(start, count);\r
+ return new Range(this, start, count, true);\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IEditableCollection members\r
+ /// <summary>\r
+ /// Remove all items and reset size of internal array container.\r
+ /// </summary>\r
+ [Tested]\r
+ public virtual void Clear()\r
+ {\r
+ updatecheck();\r
+ array = new T[8];\r
+ size = 0;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Create an array containing (copies) of the items of this collection in enumeration order.\r
+ /// </summary>\r
+ /// <returns>The new array</returns>\r
+ [Tested]\r
+ public override T[] ToArray()\r
+ {\r
+ T[] res = new T[size];\r
+\r
+ Array.Copy(array, res, size);\r
+ return res;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Perform an internal consistency (invariant) test on the array base.\r
+ /// </summary>\r
+ /// <returns>True if test succeeds.</returns>\r
+ [Tested]\r
+ public virtual bool Check()\r
+ {\r
+ bool retval = true;\r
+\r
+ if (size > array.Length)\r
+ {\r
+ Console.WriteLine("Bad size ({0}) > array.Length ({1})", size, array.Length);\r
+ return false;\r
+ }\r
+\r
+ for (int i = 0; i < size; i++)\r
+ {\r
+ if ((object)(array[i]) == null)\r
+ {\r
+ Console.WriteLine("Bad element: null at index {0}", i);\r
+ return false;\r
+ }\r
+ }\r
+\r
+ return retval;\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IDirectedCollection<T> Members\r
+\r
+ /// <summary>\r
+ /// Create a directed collection with the same contents as this one, but \r
+ /// opposite enumeration sequence.\r
+ /// </summary>\r
+ /// <returns>The mirrored collection.</returns>\r
+ [Tested]\r
+ public IDirectedCollectionValue<T> Backwards() { return this[0, size].Backwards(); }\r
+\r
+ #endregion\r
+\r
+ #region IEnumerable<T> Members\r
+ /// <summary>\r
+ /// Create an enumerator for this array based collection.\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ [Tested]\r
+ public override MSG.IEnumerator<T> GetEnumerator()\r
+ {\r
+ int thestamp = stamp, theend = size + offset, thestart = offset;\r
+\r
+ for (int i = thestart; i < theend; i++)\r
+ {\r
+ modifycheck(thestamp);\r
+ yield return array[i];\r
+ }\r
+ }\r
+ #endregion\r
+\r
+ #region Range nested class\r
+ /// <summary>\r
+ /// A helper class for defining results of interval queries on array based collections.\r
+ /// </summary>\r
+ protected class Range: CollectionValueBase<T>, IDirectedCollectionValue<T>\r
+ {\r
+ int start, count, delta, stamp;\r
+\r
+ ArrayBase<T> thebase;\r
+\r
+\r
+ internal Range(ArrayBase<T> thebase, int start, int count, bool forwards)\r
+ {\r
+ this.thebase = thebase; stamp = thebase.stamp;\r
+ delta = forwards ? 1 : -1;\r
+ this.start = start + thebase.offset; this.count = count;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>The number of items in the range</value>\r
+ [Tested]\r
+ public override int Count { [Tested]get { thebase.modifycheck(stamp); return count; } }\r
+\r
+ /// <summary>\r
+ /// The value is symbolic indicating the type of asymptotic complexity\r
+ /// in terms of the size of this collection (worst-case or amortized as\r
+ /// relevant).\r
+ /// </summary>\r
+ /// <value>A characterization of the speed of the \r
+ /// <code>Count</code> property in this collection.</value>\r
+ public override Speed CountSpeed { get { thebase.modifycheck(stamp); return Speed.Constant; } }\r
+\r
+ /// <summary>\r
+ /// Create an enumerator for this range of an array based collection.\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ [Tested]\r
+ public override MSG.IEnumerator<T> GetEnumerator()\r
+ {\r
+ for (int i = 0; i < count; i++)\r
+ {\r
+ thebase.modifycheck(stamp);\r
+ yield return thebase.array[start + delta * i];\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Create a araay collection range with the same contents as this one, but \r
+ /// opposite enumeration sequence.\r
+ /// </summary>\r
+ /// <returns>The mirrored collection.</returns>\r
+ [Tested]\r
+ public IDirectedCollectionValue<T> Backwards()\r
+ {\r
+ thebase.modifycheck(stamp);\r
+\r
+ Range res = (Range)MemberwiseClone();\r
+\r
+ res.delta = -delta;\r
+ res.start = start + (count - 1) * delta;\r
+ return res;\r
+ }\r
+\r
+\r
+ IDirectedEnumerable<T> C5.IDirectedEnumerable<T>.Backwards()\r
+ {\r
+ return Backwards();\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// <code>Forwards</code> if same, else <code>Backwards</code>\r
+ /// </summary>\r
+ /// <value>The enumeration direction relative to the original collection.</value>\r
+ [Tested]\r
+ public EnumerationDirection Direction\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+ thebase.modifycheck(stamp);\r
+ return delta > 0 ? EnumerationDirection.Forwards : EnumerationDirection.Backwards;\r
+ }\r
+ }\r
+ }\r
+ #endregion\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region Sorting\r
+ /// <summary>\r
+ /// A utility class with functions for sorting arrays with respect to an IComparer<T>\r
+ /// </summary>\r
+ public class Sorting\r
+ {\r
+ /// <summary>\r
+ /// Sort part of array in place using IntroSort\r
+ /// </summary>\r
+ /// <param name="a">Array to sort</param>\r
+ /// <param name="f">Index of first position to sort</param>\r
+ /// <param name="b">Index of first position beyond the part to sort</param>\r
+ /// <param name="c">IComparer<T> to sort by</param>\r
+ [Tested]\r
+ public static void IntroSort<T>(T[] a, int f, int b, IComparer<T> c)\r
+ {\r
+ new Sorter<T>(a, c).IntroSort(f, b);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Sort part of array in place using Insertion Sort\r
+ /// </summary>\r
+ /// <param name="a">Array to sort</param>\r
+ /// <param name="f">Index of first position to sort</param>\r
+ /// <param name="b">Index of first position beyond the part to sort</param>\r
+ /// <param name="c">IComparer<T> to sort by</param>\r
+ [Tested]\r
+ public static void InsertionSort<T>(T[] a, int f, int b, IComparer<T> c)\r
+ {\r
+ new Sorter<T>(a, c).InsertionSort(f, b);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Sort part of array in place using Heap Sort\r
+ /// </summary>\r
+ /// <param name="a">Array to sort</param>\r
+ /// <param name="f">Index of first position to sort</param>\r
+ /// <param name="b">Index of first position beyond the part to sort</param>\r
+ /// <param name="c">IComparer<T> to sort by</param>\r
+ [Tested]\r
+ public static void HeapSort<T>(T[] a, int f, int b, IComparer<T> c)\r
+ {\r
+ new Sorter<T>(a, c).HeapSort(f, b);\r
+ }\r
+\r
+\r
+ class Sorter<T>\r
+ {\r
+ T[] a;\r
+\r
+ IComparer<T> c;\r
+\r
+\r
+ internal Sorter(T[] a, IComparer<T> c) { this.a = a; this.c = c; }\r
+\r
+\r
+ internal void IntroSort(int f, int b)\r
+ {\r
+ if (b - f > 31)\r
+ {\r
+ int depth_limit = (int)Math.Floor(2.5 * Math.Log(b - f, 2));\r
+\r
+ introSort(f, b, depth_limit);\r
+ }\r
+ else\r
+ InsertionSort(f, b);\r
+ }\r
+\r
+\r
+ private void introSort(int f, int b, int depth_limit)\r
+ {\r
+ const int size_threshold = 14;//24;\r
+\r
+ if (depth_limit-- == 0)\r
+ HeapSort(f, b);\r
+ else if (b - f <= size_threshold)\r
+ InsertionSort(f, b);\r
+ else\r
+ {\r
+ int p = partition(f, b);\r
+\r
+ introSort(f, p, depth_limit);\r
+ introSort(p, b, depth_limit);\r
+ }\r
+ }\r
+\r
+\r
+ private int compare(T i1, T i2) { return c.Compare(i1, i2); }\r
+\r
+\r
+ private int partition(int f, int b)\r
+ {\r
+ int bot = f, mid = (b + f) / 2, top = b - 1;\r
+ T abot = a[bot], amid = a[mid], atop = a[top];\r
+\r
+ if (compare(abot, amid) < 0)\r
+ {\r
+ if (compare(atop, abot) < 0)//atop<abot<amid\r
+ { a[top] = amid; amid = a[mid] = abot; a[bot] = atop; }\r
+ else if (compare(atop, amid) < 0) //abot<=atop<amid\r
+ { a[top] = amid; amid = a[mid] = atop; }\r
+ //else abot<amid<=atop\r
+ }\r
+ else\r
+ {\r
+ if (compare(amid, atop) > 0) //atop<amid<=abot\r
+ { a[bot] = atop; a[top] = abot; }\r
+ else if (compare(abot, atop) > 0) //amid<=atop<abot\r
+ { a[bot] = amid; amid = a[mid] = atop; a[top] = abot; }\r
+ else //amid<=abot<=atop\r
+ { a[bot] = amid; amid = a[mid] = abot; }\r
+ }\r
+\r
+ int i = bot, j = top;\r
+\r
+ while (true)\r
+ {\r
+ while (compare(a[++i], amid) < 0);\r
+\r
+ while (compare(amid, a[--j]) < 0);\r
+\r
+ if (i < j)\r
+ {\r
+ T tmp = a[i]; a[i] = a[j]; a[j] = tmp;\r
+ }\r
+ else\r
+ return i;\r
+ }\r
+ }\r
+\r
+\r
+ internal void InsertionSort(int f, int b)\r
+ {\r
+ for (int j = f + 1; j < b; j++)\r
+ {\r
+ T key = a[j], other;\r
+ int i = j - 1;\r
+\r
+ if (c.Compare(other = a[i], key) > 0)\r
+ {\r
+ a[j] = other;\r
+ while (i > f && c.Compare(other = a[i - 1], key) > 0) { a[i--] = other; }\r
+\r
+ a[i] = key;\r
+ }\r
+ }\r
+ }\r
+\r
+\r
+ internal void HeapSort(int f, int b)\r
+ {\r
+ for (int i = (b + f) / 2; i >= f; i--) heapify(f, b, i);\r
+\r
+ for (int i = b - 1; i > f; i--)\r
+ {\r
+ T tmp = a[f]; a[f] = a[i]; a[i] = tmp;\r
+ heapify(f, i, f);\r
+ }\r
+ }\r
+\r
+\r
+ private void heapify(int f, int b, int i)\r
+ {\r
+ T pv = a[i], lv, rv, max = pv;\r
+ int j = i, maxpt = j;\r
+\r
+ while (true)\r
+ {\r
+ int l = 2 * j - f + 1, r = l + 1;\r
+\r
+ if (l < b && compare(lv = a[l], max) > 0) { maxpt = l; max = lv; }\r
+\r
+ if (r < b && compare(rv = a[r], max) > 0) { maxpt = r; max = rv; }\r
+\r
+ if (maxpt == j)\r
+ break;\r
+\r
+ a[j] = max;\r
+ max = pv;\r
+ j = maxpt;\r
+ }\r
+\r
+ if (j > i)\r
+ a[j] = pv;\r
+ }\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region Random\r
+ /// <summary>\r
+ /// A modern random number generator based on (whatever)\r
+ /// </summary>\r
+ public class C5Random : Random\r
+ {\r
+ private uint[] Q = new uint[16];\r
+\r
+ private uint c = 362436, i = 15;\r
+\r
+\r
+ private uint Cmwc()\r
+ {\r
+ ulong t, a = 487198574UL;\r
+ uint x, r = 0xfffffffe;\r
+\r
+ i = (i + 1) & 15;\r
+ t = a * Q[i] + c;\r
+ c = (uint)(t >> 32);\r
+ x = (uint)(t + c);\r
+ if (x < c)\r
+ {\r
+ x++;\r
+ c++;\r
+ }\r
+\r
+ return Q[i] = r - x;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get a new random System.Double value\r
+ /// </summary>\r
+ /// <returns>The random double</returns>\r
+ public override double NextDouble()\r
+ {\r
+ return Cmwc() / 4294967296.0;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get a new random System.Double value\r
+ /// </summary>\r
+ /// <returns>The random double</returns>\r
+ protected override double Sample()\r
+ {\r
+ return NextDouble();\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get a new random System.Int32 value\r
+ /// </summary>\r
+ /// <returns>The random int</returns>\r
+ public override int Next()\r
+ {\r
+ return (int)Cmwc();\r
+ }\r
+ \r
+\r
+ /// <summary>\r
+ /// Get a random non-negative integer less than a given upper bound\r
+ /// </summary>\r
+ /// <param name="max">The upper bound (exclusive)</param>\r
+ /// <returns></returns>\r
+ public override int Next(int max)\r
+ {\r
+ if (max < 0)\r
+ throw new ApplicationException("max must be non-negative");\r
+\r
+ return (int)(Cmwc() / 4294967296.0 * max);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get a random integer between two given bounds\r
+ /// </summary>\r
+ /// <param name="min">The lower bound (inclusive)</param>\r
+ /// <param name="max">The upper bound (exclusive)</param>\r
+ /// <returns></returns>\r
+ public override int Next(int min, int max)\r
+ {\r
+ if (min > max)\r
+ throw new ApplicationException("min must be less than or equal to max");\r
+\r
+ return min + (int)(Cmwc() / 4294967296.0 * max);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Fill a array of byte with random bytes\r
+ /// </summary>\r
+ /// <param name="buffer">The array to fill</param>\r
+ public override void NextBytes(byte[] buffer)\r
+ {\r
+ for (int i = 0, length = buffer.Length; i < length; i++)\r
+ buffer[i] = (byte)Cmwc();\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Create a random number generator seed by system time.\r
+ /// </summary>\r
+ public C5Random() : this(DateTime.Now.Ticks)\r
+ {\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Create a random number generator with a given seed\r
+ /// </summary>\r
+ /// <param name="seed">The seed</param>\r
+ public C5Random(long seed)\r
+ {\r
+ if (seed == 0)\r
+ throw new ApplicationException("Seed must be non-zero");\r
+\r
+ uint j = (uint)(seed & 0xFFFFFFFF);\r
+\r
+ for (int i = 0; i < 16; i++)\r
+ {\r
+ j ^= j << 13;\r
+ j ^= j >>17;\r
+ j ^= j << 5;\r
+ Q[i] = j;\r
+ }\r
+\r
+ Q[15] = (uint)(seed ^ (seed >> 32));\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region Custom code attributes\r
+\r
+ /// <summary>\r
+ /// A custom attribute to mark methods and properties as being tested \r
+ /// sufficiently in the regression test suite.\r
+ /// </summary>\r
+ [AttributeUsage(AttributeTargets.All, AllowMultiple = true)]\r
+ public class TestedAttribute: Attribute\r
+ {\r
+\r
+ /// <summary>\r
+ /// Optional reference to test case\r
+ /// </summary>\r
+ [Tested]\r
+ public string via;\r
+\r
+\r
+ /// <summary>\r
+ /// Pretty print attribute value\r
+ /// </summary>\r
+ /// <returns>"Tested via " + via</returns>\r
+ [Tested]\r
+ public override string ToString() { return "Tested via " + via; }\r
+ }\r
+\r
+ #endregion\r
+}\r
+#endif\r
projects / mono.git / blobdiff