-#if NET_2_0
-/*\r
- Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\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 SCG = System.Collections.Generic;\r
-namespace C5\r
-{\r
- /// <summary>\r
- /// A generic collection, that can be enumerated backwards.\r
- /// </summary>\r
- public interface IDirectedEnumerable<T> : SCG.IEnumerable<T>\r
- {\r
- /// <summary>\r
- /// Create a collection containing the same items as this collection, but\r
- /// whose enumerator will enumerate the items backwards. The new collection\r
- /// will become invalid if the original is modified. Method typically used as in\r
- /// <code>foreach (T x in coll.Backwards()) {...}</code>\r
- /// </summary>\r
- /// <returns>The backwards collection.</returns>\r
- IDirectedEnumerable<T> Backwards();\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
- EnumerationDirection Direction { get;}\r
- }\r
-\r
- /// <summary>\r
- /// A generic collection that may be enumerated and can answer\r
- /// efficiently how many items it contains. Like <code>IEnumerable<T></code>,\r
- /// this interface does not prescribe any operations to initialize or update the \r
- /// collection. The main usage for this interface is to be the return type of \r
- /// query operations on generic collection.\r
- /// </summary>\r
- public interface ICollectionValue<T> : SCG.IEnumerable<T>, IShowable\r
- {\r
- /// <summary>\r
- /// A flag bitmap of the events subscribable to by this collection.\r
- /// </summary>\r
- /// <value></value>\r
- EventTypeEnum ListenableEvents { get;}\r
-\r
- /// <summary>\r
- /// A flag bitmap of the events currently subscribed to by this collection.\r
- /// </summary>\r
- /// <value></value>\r
- EventTypeEnum ActiveEvents { get;}\r
-\r
- /// <summary>\r
- /// The change event. Will be raised for every change operation on the collection.\r
- /// </summary>\r
- event CollectionChangedHandler<T> CollectionChanged;\r
-\r
- /// <summary>\r
- /// The change event. Will be raised for every clear operation on the collection.\r
- /// </summary>\r
- event CollectionClearedHandler<T> CollectionCleared;\r
-\r
- /// <summary>\r
- /// The item added event. Will be raised for every individual addition to the collection.\r
- /// </summary>\r
- event ItemsAddedHandler<T> ItemsAdded;\r
-\r
- /// <summary>\r
- /// The item inserted event. Will be raised for every individual insertion to the collection.\r
- /// </summary>\r
- event ItemInsertedHandler<T> ItemInserted;\r
-\r
- /// <summary>\r
- /// The item removed event. Will be raised for every individual removal from the collection.\r
- /// </summary>\r
- event ItemsRemovedHandler<T> ItemsRemoved;\r
-\r
- /// <summary>\r
- /// The item removed at event. Will be raised for every individual removal at from the collection.\r
- /// </summary>\r
- event ItemRemovedAtHandler<T> ItemRemovedAt;\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>True if this collection is empty.</value>\r
- bool IsEmpty { get;}\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>The number of items in this collection</value>\r
- 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
- Speed CountSpeed { get;}\r
-\r
- /// <summary>\r
- /// Copy the items of this collection to a contiguous part of an array.\r
- /// </summary>\r
- /// <param name="array">The array to copy to</param>\r
- /// <param name="index">The index at which to copy the first item</param>\r
- void CopyTo(T[] array, int index);\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
- T[] ToArray();\r
-\r
- /// <summary>\r
- /// Apply a delegate to all items of this collection.\r
- /// </summary>\r
- /// <param name="action">The delegate to apply</param>\r
- void Apply(Act<T> action);\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="predicate">A delegate \r
- /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
- /// <returns>True is such an item exists</returns>\r
- bool Exists(Fun<T, bool> predicate);\r
-\r
- /// <summary>\r
- /// Check if there exists an item that satisfies a\r
- /// specific predicate in this collection and return the first one in enumeration order.\r
- /// </summary>\r
- /// <param name="predicate">A delegate \r
- /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
- /// <param name="item"></param>\r
- /// <returns>True is such an item exists</returns>\r
- bool Find(Fun<T, bool> predicate, out T item);\r
-\r
-\r
- /// <summary>\r
- /// Check if all items in this collection satisfies a specific predicate.\r
- /// </summary>\r
- /// <param name="predicate">A delegate \r
- /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
- /// <returns>True if all items satisfies the predicate</returns>\r
- bool All(Fun<T, bool> predicate);\r
-\r
- /// <summary>\r
- /// Choose some item of this collection. \r
- /// <para>Implementations must assure that the item \r
- /// returned may be efficiently removed.</para>\r
- /// <para>Implementors may decide to implement this method in a way such that repeated\r
- /// calls do not necessarily give the same result, i.e. so that the result of the following \r
- /// test is undetermined:\r
- /// <code>coll.Choose() == coll.Choose()</code></para>\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException">if collection is empty.</exception>\r
- /// <returns></returns>\r
- T Choose();\r
-\r
- /// <summary>\r
- /// Create an enumerable, enumerating the items of this collection that satisfies \r
- /// a certain condition.\r
- /// </summary>\r
- /// <param name="filter">The T->bool filter delegate defining the condition</param>\r
- /// <returns>The filtered enumerable</returns>\r
- SCG.IEnumerable<T> Filter(Fun<T, bool> filter);\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// A sized generic collection, that can be enumerated backwards.\r
- /// </summary>\r
- public interface IDirectedCollectionValue<T> : ICollectionValue<T>, IDirectedEnumerable<T>\r
- {\r
- /// <summary>\r
- /// Create a collection containing the same items as this collection, but\r
- /// whose enumerator will enumerate the items backwards. The new collection\r
- /// will become invalid if the original is modified. Method typically used as in\r
- /// <code>foreach (T x in coll.Backwards()) {...}</code>\r
- /// </summary>\r
- /// <returns>The backwards collection.</returns>\r
- new IDirectedCollectionValue<T> Backwards();\r
-\r
- /// <summary>\r
- /// Check if there exists an item that satisfies a\r
- /// specific predicate in this collection and return the first one in enumeration order.\r
- /// </summary>\r
- /// <param name="predicate">A delegate \r
- /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
- /// <param name="item"></param>\r
- /// <returns>True is such an item exists</returns>\r
- bool FindLast(Fun<T, bool> predicate, out T item);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// A generic collection to which one may add items. This is just the intersection\r
- /// of the main stream generic collection interfaces and the priority queue interface,\r
- /// <see cref="T:C5.ICollection`1"/> and <see cref="T:C5.IPriorityQueue`1"/>.\r
- /// </summary>\r
- public interface IExtensible<T> : ICollectionValue<T>, ICloneable\r
- {\r
- /// <summary>\r
- /// If true any call of an updating operation will throw an\r
- /// <code>ReadOnlyCollectionException</code>\r
- /// </summary>\r
- /// <value>True if this collection is read-only.</value>\r
- bool IsReadOnly { get;}\r
-\r
- //TODO: wonder where the right position of this is\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>False if this collection has set semantics, true if bag semantics.</value>\r
- bool AllowsDuplicates { get;}\r
-\r
- //TODO: wonder where the right position of this is. And the semantics.\r
- /// <summary>\r
- /// (Here should be a discussion of the role of equalityComparers. Any ). \r
- /// </summary>\r
- /// <value>The equalityComparer used by this collection to check equality of items. \r
- /// Or null (????) if collection does not check equality at all or uses a comparer.</value>\r
- SCG.IEqualityComparer<T> EqualityComparer { get;}\r
-\r
- //ItemEqualityTypeEnum ItemEqualityType {get ;}\r
-\r
- //TODO: find a good name\r
-\r
- /// <summary>\r
- /// By convention this is true for any collection with set semantics.\r
- /// </summary>\r
- /// <value>True if only one representative of a group of equal items \r
- /// is kept in the collection together with the total count.</value>\r
- bool DuplicatesByCounting { get;}\r
-\r
- /// <summary>\r
- /// Add an item to this collection if possible. If this collection has set\r
- /// semantics, the item will be added if not already in the collection. If\r
- /// bag semantics, the item will always be added.\r
- /// </summary>\r
- /// <param name="item">The item to add.</param>\r
- /// <returns>True if item was added.</returns>\r
- bool Add(T item);\r
-\r
- /// <summary>\r
- /// Add the elements from another collection with a more specialized item type \r
- /// to this collection. If this\r
- /// collection has set semantics, only items not already in the collection\r
- /// will be added.\r
- /// </summary>\r
- /// <typeparam name="U">The type of items to add</typeparam>\r
- /// <param name="items">The items to add</param>\r
- void AddAll<U>(SCG.IEnumerable<U> items) where U : T;\r
-\r
- //void Clear(); // for priority queue\r
- //int Count why not?\r
- /// <summary>\r
- /// Check the integrity of the internal data structures of this collection.\r
- /// <i>This is only relevant for developers of the library</i>\r
- /// </summary>\r
- /// <returns>True if check was passed.</returns>\r
- bool Check();\r
- }\r
-\r
- /// <summary>\r
- /// The simplest interface of a main stream generic collection\r
- /// with lookup, insertion and removal operations. \r
- /// </summary>\r
- public interface ICollection<T> : IExtensible<T>\r
- {\r
- //This is somewhat similar to the RandomAccess marker itf in java\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
- /// <para>See <see cref="T:C5.Speed"/> for the set of symbols.</para>\r
- /// </summary>\r
- /// <value>A characterization of the speed of lookup operations\r
- /// (<code>Contains()</code> etc.) of the implementation of this collection.</value>\r
- Speed ContainsSpeed { get;}\r
-\r
- /// <summary>\r
- /// The unordered collection hashcode is defined as the sum of \r
- /// <code>h(hashcode(item))</code> over the items\r
- /// of the collection, where the function <code>h</code> is a function from \r
- /// int to int of the form <code> t -> (a0*t+b0)^(a1*t+b1)^(a2*t+b2)</code>, where \r
- /// the ax and bx are the same for all collection classes. \r
- /// <para>The current implementation uses fixed values for the ax and bx, \r
- /// specified as constants in the code.</para>\r
- /// </summary>\r
- /// <returns>The unordered hashcode of this collection.</returns>\r
- int GetUnsequencedHashCode();\r
-\r
-\r
- /// <summary>\r
- /// Compare the contents of this collection to another one without regards to\r
- /// the sequence order. The comparison will use this collection's itemequalityComparer\r
- /// to compare individual items.\r
- /// </summary>\r
- /// <param name="otherCollection">The collection to compare to.</param>\r
- /// <returns>True if this collection and that contains the same items.</returns>\r
- bool UnsequencedEquals(ICollection<T> otherCollection);\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains (an item equivalent to according to the\r
- /// itemequalityComparer) a particular value.\r
- /// </summary>\r
- /// <param name="item">The value to check for.</param>\r
- /// <returns>True if the items is in this collection.</returns>\r
- bool Contains(T item);\r
-\r
-\r
- /// <summary>\r
- /// Count the number of items of the collection equal to a particular value.\r
- /// Returns 0 if and only if the value is not in the collection.\r
- /// </summary>\r
- /// <param name="item">The value to count.</param>\r
- /// <returns>The number of copies found.</returns>\r
- int ContainsCount(T item);\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- ICollectionValue<T> UniqueItems();\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities();\r
-\r
- /// <summary>\r
- /// Check whether this collection contains all the values in another collection.\r
- /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)\r
- /// the check is made with respect to multiplicities, else multiplicities\r
- /// are not taken into account.\r
- /// </summary>\r
- /// <param name="items">The </param>\r
- /// <typeparam name="U"></typeparam>\r
- /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
- bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T;\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemequalityComparer to a particular value. If so, return in the ref argument (a\r
- /// binary copy of) the actual value found.\r
- /// </summary>\r
- /// <param name="item">The value to look for.</param>\r
- /// <returns>True if the items is in this collection.</returns>\r
- bool Find(ref T item);\r
-\r
-\r
- //This should probably just be bool Add(ref T item); !!!\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemequalityComparer to a particular value. If so, return in the ref argument (a\r
- /// binary copy of) the actual value found. Else, add the item to the collection.\r
- /// </summary>\r
- /// <param name="item">The value to look for.</param>\r
- /// <returns>True if the item was found (hence not added).</returns>\r
- bool FindOrAdd(ref T item);\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemequalityComparer to a particular value. If so, update the item in the collection \r
- /// with a (binary copy of) the supplied value. If the collection has bag semantics,\r
- /// it depends on the value of DuplicatesByCounting if this updates all equivalent copies in\r
- /// the collection or just one.\r
- /// </summary>\r
- /// <param name="item">Value to update.</param>\r
- /// <returns>True if the item was found and hence updated.</returns>\r
- bool Update(T item);\r
-\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemequalityComparer to a particular value. If so, update the item in the collection \r
- /// with a (binary copy of) the supplied value. If the collection has bag semantics,\r
- /// it depends on the value of DuplicatesByCounting if this updates all equivalent copies in\r
- /// the collection or just one.\r
- /// </summary>\r
- /// <param name="item">Value to update.</param>\r
- /// <param name="olditem">On output the olditem, if found.</param>\r
- /// <returns>True if the item was found and hence updated.</returns>\r
- bool Update(T item, out T olditem);\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemequalityComparer to a particular value. If so, update the item in the collection \r
- /// to with a binary copy of the supplied value; else add the value to the collection. \r
- /// </summary>\r
- /// <param name="item">Value to add or update.</param>\r
- /// <returns>True if the item was found and updated (hence not added).</returns>\r
- bool UpdateOrAdd(T item);\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemequalityComparer to a particular value. If so, update the item in the collection \r
- /// to with a binary copy of the supplied value; else add the value to the collection. \r
- /// </summary>\r
- /// <param name="item">Value to add or update.</param>\r
- /// <param name="olditem">On output the olditem, if found.</param>\r
- /// <returns>True if the item was found and updated (hence not added).</returns>\r
- bool UpdateOrAdd(T item, out T olditem);\r
-\r
- /// <summary>\r
- /// Remove a particular item from this collection. If the collection has bag\r
- /// semantics only one copy equivalent to the supplied item is removed. \r
- /// </summary>\r
- /// <param name="item">The value to remove.</param>\r
- /// <returns>True if the item was found (and removed).</returns>\r
- bool Remove(T item);\r
-\r
-\r
- /// <summary>\r
- /// Remove a particular item from this collection if found. If the collection\r
- /// has bag semantics only one copy equivalent to the supplied item is removed,\r
- /// which one is implementation dependent. \r
- /// If an item was removed, report a binary copy of the actual item removed in \r
- /// the argument.\r
- /// </summary>\r
- /// <param name="item">The value to remove.</param>\r
- /// <param name="removeditem">The value removed if any.</param>\r
- /// <returns>True if the item was found (and removed).</returns>\r
- bool Remove(T item, out T removeditem);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items equivalent to a given value.\r
- /// </summary>\r
- /// <param name="item">The value to remove.</param>\r
- void RemoveAllCopies(T item);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items in another collection from this one. If this collection\r
- /// has bag semantics, take multiplicities into account.\r
- /// </summary>\r
- /// <typeparam name="U"></typeparam>\r
- /// <param name="items">The items to remove.</param>\r
- void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T;\r
-\r
- //void RemoveAll(Fun<T, bool> predicate);\r
-\r
- /// <summary>\r
- /// Remove all items from this collection.\r
- /// </summary>\r
- void Clear();\r
-\r
-\r
- /// <summary>\r
- /// Remove all items not in some other collection from this one. If this collection\r
- /// has bag semantics, take multiplicities into account.\r
- /// </summary>\r
- /// <typeparam name="U"></typeparam>\r
- /// <param name="items">The items to retain.</param>\r
- void RetainAll<U>(SCG.IEnumerable<U> items) where U : T;\r
-\r
- //void RetainAll(Fun<T, bool> predicate);\r
- //IDictionary<T> UniqueItems()\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// An editable collection maintaining a definite sequence order of the items.\r
- ///\r
- /// <i>Implementations of this interface must compute the hash code and \r
- /// equality exactly as prescribed in the method definitions in order to\r
- /// be consistent with other collection classes implementing this interface.</i>\r
- /// <i>This interface is usually implemented by explicit interface implementation,\r
- /// not as ordinary virtual methods.</i>\r
- /// </summary>\r
- public interface ISequenced<T> : ICollection<T>, IDirectedCollectionValue<T>\r
- {\r
- /// <summary>\r
- /// The hashcode is defined as <code>h(...h(h(h(x1),x2),x3),...,xn)</code> for\r
- /// <code>h(a,b)=CONSTANT*a+b</code> and the x's the hash codes of the items of \r
- /// this collection.\r
- /// </summary>\r
- /// <returns>The sequence order hashcode of this collection.</returns>\r
- int GetSequencedHashCode();\r
-\r
-\r
- /// <summary>\r
- /// Compare this sequenced collection to another one in sequence order.\r
- /// </summary>\r
- /// <param name="otherCollection">The sequenced collection to compare to.</param>\r
- /// <returns>True if this collection and that contains equal (according to\r
- /// this collection's itemequalityComparer) in the same sequence order.</returns>\r
- bool SequencedEquals(ISequenced<T> otherCollection);\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// A sequenced collection, where indices of items in the order are maintained\r
- /// </summary>\r
- public interface IIndexed<T> : ISequenced<T>\r
- {\r
- /// <summary>\r
- /// </summary>\r
- /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
- /// >= the size of the collection.</exception>\r
- /// <value>The <code>index</code>'th item of this list.</value>\r
- /// <param name="index">the index to lookup</param>\r
- T this[int index] { get;}\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- Speed IndexingSpeed { get;}\r
-\r
- /// <summary>\r
- /// </summary>\r
- /// <exception cref="ArgumentOutOfRangeException"></exception>\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
- IDirectedCollectionValue<T> this[int start, int count] { get;}\r
-\r
-\r
- /// <summary>\r
- /// Searches for an item in the list going forwards from the start. \r
- /// </summary>\r
- /// <param name="item">Item to search for.</param>\r
- /// <returns>Index of item from start. A negative number if item not found, \r
- /// namely the two-complement of the index at which the Add operation would put the item.</returns>\r
- int IndexOf(T item);\r
-\r
-\r
- /// <summary>\r
- /// Searches for an item in the list going backwards from the end.\r
- /// </summary>\r
- /// <param name="item">Item to search for.</param>\r
- /// <returns>Index of of item from the end. A negative number if item not found, \r
- /// namely the two-complement of the index at which the Add operation would put the item.</returns>\r
- int LastIndexOf(T item);\r
-\r
- /// <summary>\r
- /// Check if there exists an item that satisfies a\r
- /// specific predicate in this collection and return the index of the first one.\r
- /// </summary>\r
- /// <param name="predicate">A delegate \r
- /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
- /// <returns>the index, if found, a negative value else</returns>\r
- int FindIndex(Fun<T, bool> predicate);\r
-\r
- /// <summary>\r
- /// Check if there exists an item that satisfies a\r
- /// specific predicate in this collection and return the index of the last one.\r
- /// </summary>\r
- /// <param name="predicate">A delegate \r
- /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
- /// <returns>the index, if found, a negative value else</returns>\r
- int FindLastIndex(Fun<T, bool> predicate);\r
-\r
-\r
- /// <summary>\r
- /// Remove the item at a specific position of the list.\r
- /// </summary>\r
- /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
- /// >= the size of the collection.</exception>\r
- /// <param name="index">The index of the item to remove.</param>\r
- /// <returns>The removed item.</returns>\r
- T RemoveAt(int index);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items in an index interval.\r
- /// </summary>\r
- /// <exception cref="ArgumentOutOfRangeException"> if start or count \r
- /// is negative or start+count > the size of the collection.</exception>\r
- /// <param name="start">The index of the first item to remove.</param>\r
- /// <param name="count">The number of items to remove.</param>\r
- void RemoveInterval(int start, int count);\r
- }\r
-\r
- //TODO: decide if this should extend ICollection\r
- /// <summary>\r
- /// The interface describing the operations of a LIFO stack data structure.\r
- /// </summary>\r
- /// <typeparam name="T">The item type</typeparam>\r
- public interface IStack<T> : IDirectedCollectionValue<T>\r
- {\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- bool AllowsDuplicates { get;}\r
- /// <summary>\r
- /// Get the <code>index</code>'th element of the stack. The bottom of the stack has index 0.\r
- /// </summary>\r
- /// <param name="index"></param>\r
- /// <returns></returns>\r
- T this[int index] { get;}\r
- /// <summary>\r
- /// Push an item to the top of the stack.\r
- /// </summary>\r
- /// <param name="item">The item</param>\r
- void Push(T item);\r
- /// <summary>\r
- /// Pop the item at the top of the stack from the stack.\r
- /// </summary>\r
- /// <returns>The popped item.</returns>\r
- T Pop();\r
- }\r
-\r
- /// <summary>\r
- /// The interface describing the operations of a FIFO queue data structure.\r
- /// </summary>\r
- /// <typeparam name="T">The item type</typeparam>\r
- public interface IQueue<T> : IDirectedCollectionValue<T>\r
- {\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- bool AllowsDuplicates { get;}\r
- /// <summary>\r
- /// Get the <code>index</code>'th element of the queue. The front of the queue has index 0.\r
- /// </summary>\r
- /// <param name="index"></param>\r
- /// <returns></returns>\r
- T this[int index] { get;}\r
- /// <summary>\r
- /// Enqueue an item at the back of the queue. \r
- /// </summary>\r
- /// <param name="item">The item</param>\r
- void Enqueue(T item);\r
- /// <summary>\r
- /// Dequeue an item from the front of the queue.\r
- /// </summary>\r
- /// <returns>The item</returns>\r
- T Dequeue();\r
- }\r
-\r
-\r
- /// <summary>\r
- /// This is an indexed collection, where the item order is chosen by \r
- /// the user at insertion time.\r
- ///\r
- /// NBNBNB: we need a description of the view functionality here!\r
- /// </summary>\r
- public interface IList<T> : IIndexed<T>, IDisposable\r
- {\r
- /// <summary>\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if this list is empty.</exception>\r
- /// <value>The first item in this list.</value>\r
- T First { get;}\r
-\r
- /// <summary>\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if this list is empty.</exception>\r
- /// <value>The last item in this list.</value>\r
- T Last { get;}\r
-\r
- /// <summary>\r
- /// Since <code>Add(T item)</code> always add at the end of the list,\r
- /// this describes if list has FIFO or LIFO semantics.\r
- /// </summary>\r
- /// <value>True if the <code>Remove()</code> operation removes from the\r
- /// start of the list, false if it removes from the end.</value>\r
- bool FIFO { get; set;}\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- bool IsFixedSize { get; }\r
-\r
- /// <summary>\r
- /// On this list, this indexer is read/write.\r
- /// </summary>\r
- /// <exception cref="IndexOutOfRangeException"> if index is negative or\r
- /// >= the size of the collection.</exception>\r
- /// <value>The index'th item of this list.</value>\r
- /// <param name="index">The index of the item to fetch or store.</param>\r
- new T this[int index] { get; set;}\r
-\r
- /// <summary>\r
- /// Insert an item at a specific index location in this list. \r
- /// </summary>\r
- /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
- /// > the size of the collection.</exception>\r
- /// <exception cref="DuplicateNotAllowedException"> if the list has\r
- /// <code>AllowsDuplicates==false</code> and the item is \r
- /// already in the list.</exception>\r
- /// <param name="index">The index at which to insert.</param>\r
- /// <param name="item">The item to insert.</param>\r
- void Insert(int index, T item);\r
-\r
- /// <summary>\r
- /// Insert an item at the end of a compatible view, used as a pointer.\r
- /// <para>The <code>pointer</code> must be a view on the same list as\r
- /// <code>this</code> and the endpoitn of <code>pointer</code> must be\r
- /// a valid insertion point of <code>this</code></para>\r
- /// </summary>\r
- /// <exception cref="IncompatibleViewException">If <code>pointer</code> \r
- /// is not a view on the same list as <code>this</code></exception>\r
- /// <exception cref="IndexOutOfRangeException"><b>??????</b> if the endpoint of \r
- /// <code>pointer</code> is not inside <code>this</code></exception>\r
- /// <exception cref="DuplicateNotAllowedException"> if the list has\r
- /// <code>AllowsDuplicates==false</code> and the item is \r
- /// already in the list.</exception>\r
- /// <param name="pointer"></param>\r
- /// <param name="item"></param>\r
- void Insert(IList<T> pointer, T item);\r
-\r
- /// <summary>\r
- /// Insert an item at the front of this list.\r
- /// <exception cref="DuplicateNotAllowedException"/> if the list has\r
- /// <code>AllowsDuplicates==false</code> and the item is \r
- /// already in the list.\r
- /// </summary>\r
- /// <param name="item">The item to insert.</param>\r
- void InsertFirst(T item);\r
-\r
- /// <summary>\r
- /// Insert an item at the back of this list.\r
- /// <exception cref="DuplicateNotAllowedException"/> if the list has\r
- /// <code>AllowsDuplicates==false</code> and the item is \r
- /// already in the list.\r
- /// </summary>\r
- /// <param name="item">The item to insert.</param>\r
- void InsertLast(T item);\r
-\r
- /// <summary>\r
- /// Insert into this list all items from an enumerable collection starting \r
- /// at a particular index.\r
- /// </summary>\r
- /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
- /// > the size of the collection.</exception>\r
- /// <exception cref="DuplicateNotAllowedException"> if the list has \r
- /// <code>AllowsDuplicates==false</code> and one of the items to insert is\r
- /// already in the list.</exception>\r
- /// <param name="index">Index to start inserting at</param>\r
- /// <param name="items">Items to insert</param>\r
- /// <typeparam name="U"></typeparam>\r
- void InsertAll<U>(int index, SCG.IEnumerable<U> items) where U : T;\r
-\r
- /// <summary>\r
- /// Create a new list consisting of the items of this list satisfying a \r
- /// certain predicate.\r
- /// </summary>\r
- /// <param name="filter">The filter delegate defining the predicate.</param>\r
- /// <returns>The new list.</returns>\r
- IList<T> FindAll(Fun<T, bool> filter);\r
-\r
- /// <summary>\r
- /// Create a new list consisting of the results of mapping all items of this\r
- /// list. The new list will use the default equalityComparer for the item type V.\r
- /// </summary>\r
- /// <typeparam name="V">The type of items of the new list</typeparam>\r
- /// <param name="mapper">The delegate defining the map.</param>\r
- /// <returns>The new list.</returns>\r
- IList<V> Map<V>(Fun<T, V> mapper);\r
-\r
- /// <summary>\r
- /// Create a new list consisting of the results of mapping all items of this\r
- /// list. The new list will use a specified equalityComparer for the item type.\r
- /// </summary>\r
- /// <typeparam name="V">The type of items of the new list</typeparam>\r
- /// <param name="mapper">The delegate defining the map.</param>\r
- /// <param name="equalityComparer">The equalityComparer to use for the new list</param>\r
- /// <returns>The new list.</returns>\r
- IList<V> Map<V>(Fun<T, V> mapper, SCG.IEqualityComparer<V> equalityComparer);\r
-\r
- /// <summary>\r
- /// Remove one item from the list: from the front if <code>FIFO</code>\r
- /// is true, else from the back.\r
- /// <exception cref="NoSuchItemException"/> if this list is empty.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- T Remove();\r
-\r
- /// <summary>\r
- /// Remove one item from the front of the list.\r
- /// <exception cref="NoSuchItemException"/> if this list is empty.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- T RemoveFirst();\r
-\r
- /// <summary>\r
- /// Remove one item from the back of the list.\r
- /// <exception cref="NoSuchItemException"/> if this list is empty.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- T RemoveLast();\r
-\r
- /// <summary>\r
- /// Create a list view on this list. \r
- /// <exception cref="ArgumentOutOfRangeException"/> if the view would not fit into\r
- /// this list.\r
- /// </summary>\r
- /// <param name="start">The index in this list of the start of the view.</param>\r
- /// <param name="count">The size of the view.</param>\r
- /// <returns>The new list view.</returns>\r
- IList<T> View(int start, int count);\r
-\r
- /// <summary>\r
- /// Create a list view on this list containing the (first) occurrence of a particular item. \r
- /// <exception cref="NoSuchItemException"/> if the item is not in this list.\r
- /// </summary>\r
- /// <param name="item">The item to find.</param>\r
- /// <returns>The new list view.</returns>\r
- IList<T> ViewOf(T item);\r
-\r
- /// <summary>\r
- /// Create a list view on this list containing the last occurrence of a particular item. \r
- /// <exception cref="NoSuchItemException"/> if the item is not in this list.\r
- /// </summary>\r
- /// <param name="item">The item to find.</param>\r
- /// <returns>The new list view.</returns>\r
- IList<T> LastViewOf(T item);\r
-\r
- /// <summary>\r
- /// Null if this list is not a view.\r
- /// </summary>\r
- /// <value>Underlying list for view.</value>\r
- IList<T> Underlying { get;}\r
-\r
- /// <summary>\r
- /// </summary>\r
- /// <value>Offset for this list view or 0 for an underlying list.</value>\r
- int Offset { get;}\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- bool IsValid { get;}\r
-\r
- /// <summary>\r
- /// Slide this list view along the underlying list.\r
- /// </summary>\r
- /// <exception cref="NotAViewException"> if this list is not a view.</exception>\r
- /// <exception cref="ArgumentOutOfRangeException"> if the operation\r
- /// would bring either end of the view outside the underlying list.</exception>\r
- /// <param name="offset">The signed amount to slide: positive to slide\r
- /// towards the end.</param>\r
- IList<T> Slide(int offset);\r
-\r
- /// <summary>\r
- /// Slide this list view along the underlying list, changing its size.\r
- /// \r
- /// </summary>\r
- /// <exception cref="NotAViewException"> if this list is not a view.</exception>\r
- /// <exception cref="ArgumentOutOfRangeException"> if the operation\r
- /// would bring either end of the view outside the underlying list.</exception>\r
- /// <param name="offset">The signed amount to slide: positive to slide\r
- /// towards the end.</param>\r
- /// <param name="size">The new size of the view.</param>\r
- IList<T> Slide(int offset, int size);\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="offset"></param>\r
- /// <returns></returns>\r
- bool TrySlide(int offset);\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="offset"></param>\r
- /// <param name="size"></param>\r
- /// <returns></returns>\r
- bool TrySlide(int offset, int size);\r
-\r
- /// <summary>\r
- /// \r
- /// <para>Returns null if <code>otherView</code> is strictly to the left of this view</para>\r
- /// </summary>\r
- /// <param name="otherView"></param>\r
- /// <exception cref="IncompatibleViewException">If otherView does not have the same underlying list as this</exception>\r
- /// <exception cref="ArgumentOutOfRangeException">If <code>otherView</code> is strictly to the left of this view</exception>\r
- /// <returns></returns>\r
- IList<T> Span(IList<T> otherView);\r
-\r
- /// <summary>\r
- /// Reverse the list so the items are in the opposite sequence order.\r
- /// </summary>\r
- void Reverse();\r
-\r
- /// <summary>\r
- /// Check if this list is sorted according to the default sorting order\r
- /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class \r
- /// </summary>\r
- /// <exception cref="NotComparableException">if T is not comparable</exception>\r
- /// <returns>True if the list is sorted, else false.</returns>\r
- bool IsSorted();\r
-\r
- /// <summary>\r
- /// Check if this list is sorted according to a specific sorting order.\r
- /// </summary>\r
- /// <param name="comparer">The comparer defining the sorting order.</param>\r
- /// <returns>True if the list is sorted, else false.</returns>\r
- bool IsSorted(SCG.IComparer<T> comparer);\r
-\r
- /// <summary>\r
- /// Sort the items of the list according to the default sorting order\r
- /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class \r
- /// </summary>\r
- /// <exception cref="NotComparableException">if T is not comparable</exception>\r
- void Sort();\r
-\r
- /// <summary>\r
- /// Sort the items of the list according to a specified sorting order.\r
- /// <para>The sorting does not perform duplicate elimination or identify items\r
- /// according to the comparer or itemequalityComparer. I.e. the list as an \r
- /// unsequenced collection with binary equality, will not change.\r
- /// </para>\r
- /// </summary>\r
- /// <param name="comparer">The comparer defining the sorting order.</param>\r
- void Sort(SCG.IComparer<T> comparer);\r
-\r
-\r
- /// <summary>\r
- /// Randomly shuffle the items of this list. \r
- /// </summary>\r
- void Shuffle();\r
-\r
-\r
- /// <summary>\r
- /// Shuffle the items of this list according to a specific random source.\r
- /// </summary>\r
- /// <param name="rnd">The random source.</param>\r
- void Shuffle(Random rnd);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// The base type of a priority queue handle\r
- /// </summary>\r
- /// <typeparam name="T"></typeparam>\r
- public interface IPriorityQueueHandle<T>\r
- {\r
- //TODO: make abstract and prepare for double dispatch:\r
- //public virtual bool Delete(IPriorityQueue<T> q) { throw new InvalidFooException();}\r
- //bool Replace(T item);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// A generic collection of items prioritized by a comparison (order) relation.\r
- /// Supports adding items and reporting or removing extremal elements. \r
- /// <para>\r
- /// \r
- /// </para>\r
- /// When adding an item, the user may choose to have a handle allocated for this item in the queue. \r
- /// The resulting handle may be used for deleting the item even if not extremal, and for replacing the item.\r
- /// A priority queue typically only holds numeric priorities associated with some objects\r
- /// maintained separately in other collection objects.\r
- /// </summary>\r
- public interface IPriorityQueue<T> : IExtensible<T>\r
- {\r
- /// <summary>\r
- /// Find the current least item of this priority queue.\r
- /// </summary>\r
- /// <returns>The least item.</returns>\r
- T FindMin();\r
-\r
-\r
- /// <summary>\r
- /// Remove the least item from this priority queue.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- T DeleteMin();\r
-\r
-\r
- /// <summary>\r
- /// Find the current largest item of this priority queue.\r
- /// </summary>\r
- /// <returns>The largest item.</returns>\r
- T FindMax();\r
-\r
-\r
- /// <summary>\r
- /// Remove the largest item from this priority queue.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- T DeleteMax();\r
-\r
- /// <summary>\r
- /// The comparer object supplied at creation time for this collection\r
- /// </summary>\r
- /// <value>The comparer</value>\r
- SCG.IComparer<T> Comparer { get;}\r
- /// <summary>\r
- /// Get or set the item corresponding to a handle. Throws exceptions on \r
- /// invalid handles.\r
- /// </summary>\r
- /// <param name="handle"></param>\r
- /// <returns></returns>\r
- T this[IPriorityQueueHandle<T> handle] { get; set;}\r
-\r
- /// <summary>\r
- /// Check if the entry corresponding to a handle is in the priority queue.\r
- /// </summary>\r
- /// <param name="handle"></param>\r
- /// <param name="item"></param>\r
- /// <returns></returns>\r
- bool Find(IPriorityQueueHandle<T> handle, out T item);\r
-\r
- /// <summary>\r
- /// Add an item to the priority queue, receiving a \r
- /// handle for the item in the queue, \r
- /// or reusing an existing unused handle.\r
- /// </summary>\r
- /// <param name="handle">On output: a handle for the added item. \r
- /// On input: null for allocating a new handle, or a currently unused handle for reuse. \r
- /// A handle for reuse must be compatible with this priority queue, \r
- /// by being created by a priority queue of the same runtime type, but not \r
- /// necessarily the same priority queue object.</param>\r
- /// <param name="item"></param>\r
- /// <returns></returns>\r
- bool Add(ref IPriorityQueueHandle<T> handle, T item);\r
-\r
- /// <summary>\r
- /// Delete an item with a handle from a priority queue\r
- /// </summary>\r
- /// <param name="handle">The handle for the item. The handle will be invalidated, but reusable.</param>\r
- /// <returns>The deleted item</returns>\r
- T Delete(IPriorityQueueHandle<T> handle);\r
-\r
- /// <summary>\r
- /// Replace an item with a handle in a priority queue with a new item. \r
- /// Typically used for changing the priority of some queued object.\r
- /// </summary>\r
- /// <param name="handle">The handle for the old item</param>\r
- /// <param name="item">The new item</param>\r
- /// <returns>The old item</returns>\r
- T Replace(IPriorityQueueHandle<T> handle, T item);\r
-\r
- /// <summary>\r
- /// Find the current least item of this priority queue.\r
- /// </summary>\r
- /// <param name="handle">On return: the handle of the item.</param>\r
- /// <returns>The least item.</returns>\r
- T FindMin(out IPriorityQueueHandle<T> handle);\r
-\r
- /// <summary>\r
- /// Find the current largest item of this priority queue.\r
- /// </summary>\r
- /// <param name="handle">On return: the handle of the item.</param>\r
- /// <returns>The largest item.</returns>\r
-\r
- T FindMax(out IPriorityQueueHandle<T> handle);\r
-\r
- /// <summary>\r
- /// Remove the least item from this priority queue.\r
- /// </summary>\r
- /// <param name="handle">On return: the handle of the removed item.</param>\r
- /// <returns>The removed item.</returns>\r
-\r
- T DeleteMin(out IPriorityQueueHandle<T> handle);\r
-\r
- /// <summary>\r
- /// Remove the largest item from this priority queue.\r
- /// </summary>\r
- /// <param name="handle">On return: the handle of the removed item.</param>\r
- /// <returns>The removed item.</returns>\r
- T DeleteMax(out IPriorityQueueHandle<T> handle);\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// A sorted collection, i.e. a collection where items are maintained and can be searched for in sorted order.\r
- /// Thus the sequence order is given as a sorting order.\r
- /// \r
- /// <para>The sorting order is defined by a comparer, an object of type IComparer<T> \r
- /// (<see cref="T:C5.IComparer`1"/>). Implementors of this interface will normally let the user \r
- /// define the comparer as an argument to a constructor. \r
- /// Usually there will also be constructors without a comparer argument, in which case the \r
- /// comparer should be the defalt comparer for the item type, <see cref="P:C5.Comparer`1.Default"/>.</para>\r
- /// \r
- /// <para>The comparer of the sorted collection is available as the <code>Comparer</code> property \r
- /// (<see cref="P:C5.ISorted`1.Comparer"/>).</para>\r
- /// \r
- /// <para>The methods are grouped according to\r
- /// <list>\r
- /// <item>Extrema: report or report and delete an extremal item. This is reminiscent of simplified priority queues.</item>\r
- /// <item>Nearest neighbor: report predecessor or successor in the collection of an item. Cut belongs to this group.</item>\r
- /// <item>Range: report a view of a range of elements or remove all elements in a range.</item>\r
- /// <item>AddSorted: add a collection of items known to be sorted in the same order (should be faster) (to be removed?)</item>\r
- /// </list>\r
- /// </para>\r
- /// \r
- /// <para>Since this interface extends ISequenced<T>, sorted collections will also have an \r
- /// item equalityComparer (<see cref="P:C5.IExtensible`1.EqualityComparer"/>). This equalityComparer will not be used in connection with \r
- /// the inner workings of the sorted collection, but will be used if the sorted collection is used as \r
- /// an item in a collection of unsequenced or sequenced collections, \r
- /// (<see cref="T:C5.ICollection`1"/> and <see cref="T:C5.ISequenced`1"/>)</para>\r
- /// \r
- /// <para>Note that code may check if two sorted collections has the same sorting order \r
- /// by checking if the Comparer properties are equal. This is done a few places in this library\r
- /// for optimization purposes.</para>\r
- /// </summary>\r
- public interface ISorted<T> : ISequenced<T>\r
- {\r
- /// <summary>\r
- /// Find the current least item of this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The least item.</returns>\r
- T FindMin();\r
-\r
-\r
- /// <summary>\r
- /// Remove the least item from this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The removed item.</returns>\r
- T DeleteMin();\r
-\r
-\r
- /// <summary>\r
- /// Find the current largest item of this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The largest item.</returns>\r
- T FindMax();\r
-\r
-\r
- /// <summary>\r
- /// Remove the largest item from this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The removed item.</returns>\r
- T DeleteMax();\r
-\r
- /// <summary>\r
- /// The comparer object supplied at creation time for this sorted collection.\r
- /// </summary>\r
- /// <value>The comparer</value>\r
- SCG.IComparer<T> Comparer { get;}\r
-\r
- /// <summary>\r
- /// Find the strict predecessor in the sorted collection of a particular value,\r
- /// that is, the largest item in the collection less than the supplied value.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if no such element exists (the\r
- /// supplied value is less than or equal to the minimum of this collection.)</exception>\r
- /// <param name="item">The item to find the predecessor for.</param>\r
- /// <returns>The predecessor.</returns>\r
- T Predecessor(T item);\r
-\r
-\r
- /// <summary>\r
- /// Find the strict successor in the sorted collection of a particular value,\r
- /// that is, the least item in the collection greater than the supplied value.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if no such element exists (the\r
- /// supplied value is greater than or equal to the maximum of this collection.)</exception>\r
- /// <param name="item">The item to find the successor for.</param>\r
- /// <returns>The successor.</returns>\r
- T Successor(T item);\r
-\r
-\r
- /// <summary>\r
- /// Find the weak predecessor in the sorted collection of a particular value,\r
- /// that is, the largest item in the collection less than or equal to the supplied value.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if no such element exists (the\r
- /// supplied value is less than the minimum of this collection.)</exception>\r
- /// <param name="item">The item to find the weak predecessor for.</param>\r
- /// <returns>The weak predecessor.</returns>\r
- T WeakPredecessor(T item);\r
-\r
-\r
- /// <summary>\r
- /// Find the weak successor in the sorted collection of a particular value,\r
- /// that is, the least item in the collection greater than or equal to the supplied value.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if no such element exists (the\r
- /// supplied value is greater than the maximum of this collection.)</exception>\r
- ///<param name="item">The item to find the weak successor for.</param>\r
- /// <returns>The weak successor.</returns>\r
- T WeakSuccessor(T item);\r
-\r
-\r
- /// <summary>\r
- /// Given a "cut" function from the items of the sorted collection to <code>int</code>\r
- /// whose only sign changes when going through items in increasing order\r
- /// can be \r
- /// <list>\r
- /// <item>from positive to zero</item>\r
- /// <item>from positive to negative</item>\r
- /// <item>from zero to negative</item>\r
- /// </list>\r
- /// The "cut" function is supplied as the <code>CompareTo</code> method \r
- /// of an object <code>c</code> implementing \r
- /// <code>IComparable<T></code>. \r
- /// A typical example is the case where <code>T</code> is comparable and \r
- /// <code>cutFunction</code> is itself of type <code>T</code>.\r
- /// <para>This method performs a search in the sorted collection for the ranges in which the\r
- /// "cut" function is negative, zero respectively positive. If <code>T</code> is comparable\r
- /// and <code>c</code> is of type <code>T</code>, this is a safe way (no exceptions thrown) \r
- /// to find predecessor and successor of <code>c</code>.\r
- /// </para>\r
- /// <para> If the supplied cut function does not satisfy the sign-change condition, \r
- /// the result of this call is undefined.\r
- /// </para>\r
- /// \r
- /// </summary>\r
- /// <param name="cutFunction">The cut function <code>T</code> to <code>int</code>, given\r
- /// by the <code>CompareTo</code> method of an object implementing \r
- /// <code>IComparable<T></code>.</param>\r
- /// <param name="low">Returns the largest item in the collection, where the\r
- /// cut function is positive (if any).</param>\r
- /// <param name="lowIsValid">Returns true if the cut function is positive somewhere\r
- /// on this collection.</param>\r
- /// <param name="high">Returns the least item in the collection, where the\r
- /// cut function is negative (if any).</param>\r
- /// <param name="highIsValid">Returns true if the cut function is negative somewhere\r
- /// on this collection.</param>\r
- /// <returns>True if the cut function is zero somewhere\r
- /// on this collection.</returns>\r
- bool Cut(IComparable<T> cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items greater than or equal to a supplied value.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedEnumerable<T> RangeFrom(T bot);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items between two supplied values.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedEnumerable<T> RangeFromTo(T bot, T top);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items less than a supplied value.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedEnumerable<T> RangeTo(T top);\r
-\r
-\r
- /// <summary>\r
- /// Create a directed collection with the same items as this collection.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedCollectionValue<T> RangeAll();\r
-\r
-\r
- //TODO: remove now that we assume that we can check the sorting order?\r
- /// <summary>\r
- /// Add all the items from another collection with an enumeration order that \r
- /// is increasing in the items.\r
- /// </summary>\r
- /// <exception cref="ArgumentException"> if the enumerated items turns out\r
- /// not to be in increasing order.</exception>\r
- /// <param name="items">The collection to add.</param>\r
- /// <typeparam name="U"></typeparam>\r
- void AddSorted<U>(SCG.IEnumerable<U> items) where U : T;\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection above or at a supplied threshold.\r
- /// </summary>\r
- /// <param name="low">The lower threshold (inclusive).</param>\r
- void RemoveRangeFrom(T low);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection between two supplied thresholds.\r
- /// </summary>\r
- /// <param name="low">The lower threshold (inclusive).</param>\r
- /// <param name="hi">The upper threshold (exclusive).</param>\r
- void RemoveRangeFromTo(T low, T hi);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection below a supplied threshold.\r
- /// </summary>\r
- /// <param name="hi">The upper threshold (exclusive).</param>\r
- void RemoveRangeTo(T hi);\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// A collection where items are maintained in sorted order together\r
- /// with their indexes in that order.\r
- /// </summary>\r
- public interface IIndexedSorted<T> : ISorted<T>, IIndexed<T>\r
- {\r
- /// <summary>\r
- /// Determine the number of items at or above a supplied threshold.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive)</param>\r
- /// <returns>The number of matcing items.</returns>\r
- int CountFrom(T bot);\r
-\r
-\r
- /// <summary>\r
- /// Determine the number of items between two supplied thresholds.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive)</param>\r
- /// <param name="top">The upper bound (exclusive)</param>\r
- /// <returns>The number of matcing items.</returns>\r
- int CountFromTo(T bot, T top);\r
-\r
-\r
- /// <summary>\r
- /// Determine the number of items below a supplied threshold.\r
- /// </summary>\r
- /// <param name="top">The upper bound (exclusive)</param>\r
- /// <returns>The number of matcing items.</returns>\r
- int CountTo(T top);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items greater than or equal to a supplied value.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- new IDirectedCollectionValue<T> RangeFrom(T bot);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items between two supplied values.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- new IDirectedCollectionValue<T> RangeFromTo(T bot, T top);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items less than a supplied value.\r
- /// </summary>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- new IDirectedCollectionValue<T> RangeTo(T top);\r
-\r
-\r
- /// <summary>\r
- /// Create a new indexed sorted collection consisting of the items of this\r
- /// indexed sorted collection satisfying a certain predicate.\r
- /// </summary>\r
- /// <param name="predicate">The filter delegate defining the predicate.</param>\r
- /// <returns>The new indexed sorted collection.</returns>\r
- IIndexedSorted<T> FindAll(Fun<T, bool> predicate);\r
-\r
-\r
- /// <summary>\r
- /// Create a new indexed sorted collection consisting of the results of\r
- /// mapping all items of this list.\r
- /// <exception cref="ArgumentException"/> if the map is not increasing over \r
- /// the items of this collection (with respect to the two given comparison \r
- /// relations).\r
- /// </summary>\r
- /// <param name="mapper">The delegate definging the map.</param>\r
- /// <param name="comparer">The comparion relation to use for the result.</param>\r
- /// <returns>The new sorted collection.</returns>\r
- IIndexedSorted<V> Map<V>(Fun<T, V> mapper, SCG.IComparer<V> comparer);\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// The type of a sorted collection with persistence\r
- /// </summary>\r
- public interface IPersistentSorted<T> : ISorted<T>, IDisposable\r
- {\r
- /// <summary>\r
- /// Make a (read-only) snap shot of this collection.\r
- /// </summary>\r
- /// <returns>The snap shot.</returns>\r
- ISorted<T> Snapshot();\r
- }\r
-\r
-\r
-\r
- /*************************************************************************/\r
- /// <summary>\r
- /// A dictionary with keys of type K and values of type V. Equivalent to a\r
- /// finite partial map from K to V.\r
- /// </summary>\r
- public interface IDictionary<K, V> : ICollectionValue<KeyValuePair<K, V>>, ICloneable\r
- {\r
- /// <summary>\r
- /// The key equalityComparer.\r
- /// </summary>\r
- /// <value></value>\r
- SCG.IEqualityComparer<K> EqualityComparer { get;}\r
-\r
- /// <summary>\r
- /// Indexer for dictionary.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if no entry is found. </exception>\r
- /// <value>The value corresponding to the key</value>\r
- V this[K key] { get; set;}\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>True if dictionary is read-only</value>\r
- bool IsReadOnly { get;}\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>A collection containg the all the keys of the dictionary</value>\r
- ICollectionValue<K> Keys { get;}\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>A collection containing all the values of the dictionary</value>\r
- ICollectionValue<V> Values { get;}\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>A delegate of type <see cref="T:C5.Fun`2"/> defining the partial function from K to V give by the dictionary.</value>\r
- Fun<K, V> Fun { get; }\r
-\r
-\r
- //TODO: resolve inconsistency: Add thows exception if key already there, AddAll ignores keys already There?\r
- /// <summary>\r
- /// Add a new (key, value) pair (a mapping) to the dictionary.\r
- /// </summary>\r
- /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>>\r
- /// <param name="key">Key to add</param>\r
- /// <param name="val">Value to add</param>\r
- void Add(K key, V val);\r
-\r
- /// <summary>\r
- /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.\r
- /// </summary>\r
- /// <exception cref="DuplicateNotAllowedException"> \r
- /// If the input contains duplicate keys or a key already present in this dictionary.</exception>\r
- /// <param name="entries"></param>\r
- void AddAll<U, W>(SCG.IEnumerable<KeyValuePair<U, W>> entries)\r
- where U : K\r
- where W : V\r
- ;\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
- /// <para>See <see cref="T:C5.Speed"/> for the set of symbols.</para>\r
- /// </summary>\r
- /// <value>A characterization of the speed of lookup operations\r
- /// (<code>Contains()</code> etc.) of the implementation of this dictionary.</value>\r
- Speed ContainsSpeed { get;}\r
-\r
- /// <summary>\r
- /// Check whether this collection contains all the values in another collection.\r
- /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)\r
- /// the check is made with respect to multiplicities, else multiplicities\r
- /// are not taken into account.\r
- /// </summary>\r
- /// <param name="items">The </param>\r
- /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
- bool ContainsAll<H>(SCG.IEnumerable<H> items) where H : K;\r
-\r
- /// <summary>\r
- /// Remove an entry with a given key from the dictionary\r
- /// </summary>\r
- /// <param name="key">The key of the entry to remove</param>\r
- /// <returns>True if an entry was found (and removed)</returns>\r
- bool Remove(K key);\r
-\r
-\r
- /// <summary>\r
- /// Remove an entry with a given key from the dictionary and report its value.\r
- /// </summary>\r
- /// <param name="key">The key of the entry to remove</param>\r
- /// <param name="val">On exit, the value of the removed entry</param>\r
- /// <returns>True if an entry was found (and removed)</returns>\r
- bool Remove(K key, out V val);\r
-\r
-\r
- /// <summary>\r
- /// Remove all entries from the dictionary\r
- /// </summary>\r
- void Clear();\r
-\r
-\r
- /// <summary>\r
- /// Check if there is an entry with a specified key\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <returns>True if key was found</returns>\r
- bool Contains(K key);\r
-\r
-\r
- /// <summary>\r
- /// Check if there is an entry with a specified key and report the corresponding\r
- /// value if found. This can be seen as a safe form of "val = this[key]".\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">On exit, the value of the entry</param>\r
- /// <returns>True if key was found</returns>\r
- bool Find(K key, out V val);\r
-\r
- /// <summary>\r
- /// Check if there is an entry with a specified key and report the corresponding\r
- /// value if found. This can be seen as a safe form of "val = this[key]".\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">On exit, the value of the entry</param>\r
- /// <returns>True if key was found</returns>\r
- bool Find(ref K key, out V val);\r
-\r
-\r
- /// <summary>\r
- /// Look for a specific key in the dictionary and if found replace the value with a new one.\r
- /// This can be seen as a non-adding version of "this[key] = val".\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">The new value</param>\r
- /// <returns>True if key was found</returns>\r
- bool Update(K key, V val); //no-adding \r
-\r
-\r
- /// <summary>\r
- /// Look for a specific key in the dictionary and if found replace the value with a new one.\r
- /// This can be seen as a non-adding version of "this[key] = val" reporting the old value.\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">The new value</param>\r
- /// <param name="oldval">The old value if any</param>\r
- /// <returns>True if key was found</returns>\r
- bool Update(K key, V val, out V oldval); //no-adding \r
-\r
- /// <summary>\r
- /// Look for a specific key in the dictionary. If found, report the corresponding value,\r
- /// else add an entry with the key and the supplied value.\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">On entry the value to add if the key is not found.\r
- /// On exit the value found if any.</param>\r
- /// <returns>True if key was found</returns>\r
- bool FindOrAdd(K key, ref V val); //mixture\r
-\r
-\r
- /// <summary>\r
- /// Update value in dictionary corresponding to key if found, else add new entry.\r
- /// More general than "this[key] = val;" by reporting if key was found.\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">The value to add or replace with.</param>\r
- /// <returns>True if key was found and value updated.</returns>\r
- bool UpdateOrAdd(K key, V val);\r
-\r
-\r
- /// <summary>\r
- /// Update value in dictionary corresponding to key if found, else add new entry.\r
- /// More general than "this[key] = val;" by reporting if key was found.\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="val">The value to add or replace with.</param>\r
- /// <param name="oldval">The old value if any</param>\r
- /// <returns>True if key was found and value updated.</returns>\r
- bool UpdateOrAdd(K key, V val, out V oldval);\r
-\r
-\r
- /// <summary>\r
- /// Check the integrity of the internal data structures of this dictionary.\r
- /// Only avaliable in DEBUG builds???\r
- /// </summary>\r
- /// <returns>True if check does not fail.</returns>\r
- bool Check();\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// A dictionary with sorted keys.\r
- /// </summary>\r
- public interface ISortedDictionary<K, V> : IDictionary<K, V>\r
- {\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- new ISorted<K> Keys { get;}\r
-\r
- /// <summary>\r
- /// Find the current least item of this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The least item.</returns>\r
- KeyValuePair<K, V> FindMin();\r
-\r
-\r
- /// <summary>\r
- /// Remove the least item from this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The removed item.</returns>\r
- KeyValuePair<K, V> DeleteMin();\r
-\r
-\r
- /// <summary>\r
- /// Find the current largest item of this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The largest item.</returns>\r
- KeyValuePair<K, V> FindMax();\r
-\r
-\r
- /// <summary>\r
- /// Remove the largest item from this sorted collection.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
- /// <returns>The removed item.</returns>\r
- KeyValuePair<K, V> DeleteMax();\r
-\r
- /// <summary>\r
- /// The key comparer used by this dictionary.\r
- /// </summary>\r
- /// <value></value>\r
- SCG.IComparer<K> Comparer { get;}\r
-\r
- /// <summary>\r
- /// Find the entry with the largest key less than a given key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
- /// <param name="key">The key to compare to</param>\r
- /// <returns>The entry</returns>\r
- KeyValuePair<K, V> Predecessor(K key);\r
-\r
-\r
- /// <summary>\r
- /// Find the entry with the least key greater than a given key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
- /// <param name="key">The key to compare to</param>\r
- /// <returns>The entry</returns>\r
- KeyValuePair<K, V> Successor(K key);\r
-\r
-\r
- /// <summary>\r
- /// Find the entry with the largest key less than or equal to a given key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
- /// <param name="key">The key to compare to</param>\r
- /// <returns>The entry</returns>\r
- KeyValuePair<K, V> WeakPredecessor(K key);\r
-\r
-\r
- /// <summary>\r
- /// Find the entry with the least key greater than or equal to a given key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
- /// <param name="key">The key to compare to</param>\r
- /// <returns>The entry</returns>\r
- KeyValuePair<K, V> WeakSuccessor(K key);\r
-\r
- /// <summary>\r
- /// Given a "cut" function from the items of the sorted collection to <code>int</code>\r
- /// whose only sign changes when going through items in increasing order\r
- /// can be \r
- /// <list>\r
- /// <item>from positive to zero</item>\r
- /// <item>from positive to negative</item>\r
- /// <item>from zero to negative</item>\r
- /// </list>\r
- /// The "cut" function is supplied as the <code>CompareTo</code> method \r
- /// of an object <code>c</code> implementing \r
- /// <code>IComparable<K></code>. \r
- /// A typical example is the case where <code>K</code> is comparable and \r
- /// <code>c</code> is itself of type <code>K</code>.\r
- /// <para>This method performs a search in the sorted collection for the ranges in which the\r
- /// "cut" function is negative, zero respectively positive. If <code>K</code> is comparable\r
- /// and <code>c</code> is of type <code>K</code>, this is a safe way (no exceptions thrown) \r
- /// to find predecessor and successor of <code>c</code>.\r
- /// </para>\r
- /// <para> If the supplied cut function does not satisfy the sign-change condition, \r
- /// the result of this call is undefined.\r
- /// </para>\r
- /// \r
- /// </summary>\r
- /// <param name="cutFunction">The cut function <code>K</code> to <code>int</code>, given\r
- /// by the <code>CompareTo</code> method of an object implementing \r
- /// <code>IComparable<K></code>.</param>\r
- /// <param name="lowEntry">Returns the largest item in the collection, where the\r
- /// cut function is positive (if any).</param>\r
- /// <param name="lowIsValid">Returns true if the cut function is positive somewhere\r
- /// on this collection.</param>\r
- /// <param name="highEntry">Returns the least item in the collection, where the\r
- /// cut function is negative (if any).</param>\r
- /// <param name="highIsValid">Returns true if the cut function is negative somewhere\r
- /// on this collection.</param>\r
- /// <returns>True if the cut function is zero somewhere\r
- /// on this collection.</returns>\r
- bool Cut(IComparable<K> cutFunction, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid);\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items greater than or equal to a supplied value.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items between two supplied values.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <param name="lowerBound">The lower bound (inclusive).</param>\r
- /// <param name="upperBound">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K lowerBound, K upperBound);\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items less than a supplied value.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top);\r
-\r
-\r
- /// <summary>\r
- /// Create a directed collection with the same items as this collection.\r
- /// <para>The returned collection is not a copy but a view into the collection.</para>\r
- /// <para>The view is fragile in the sense that changes to the underlying collection will \r
- /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
- /// </summary>\r
- /// <returns>The result directed collection.</returns>\r
- IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll();\r
-\r
-\r
- //TODO: remove now that we assume that we can check the sorting order?\r
- /// <summary>\r
- /// Add all the items from another collection with an enumeration order that \r
- /// is increasing in the items.\r
- /// </summary>\r
- /// <exception cref="ArgumentException"> if the enumerated items turns out\r
- /// not to be in increasing order.</exception>\r
- /// <param name="items">The collection to add.</param>\r
- void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection above or at a supplied threshold.\r
- /// </summary>\r
- /// <param name="low">The lower threshold (inclusive).</param>\r
- void RemoveRangeFrom(K low);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection between two supplied thresholds.\r
- /// </summary>\r
- /// <param name="low">The lower threshold (inclusive).</param>\r
- /// <param name="hi">The upper threshold (exclusive).</param>\r
- void RemoveRangeFromTo(K low, K hi);\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection below a supplied threshold.\r
- /// </summary>\r
- /// <param name="hi">The upper threshold (exclusive).</param>\r
- void RemoveRangeTo(K hi);\r
- }\r
-\r
-\r
-\r
- /*******************************************************************/\r
- /*/// <summary>\r
- /// The type of an item comparer\r
- /// <i>Implementations of this interface must asure that the method is self-consistent\r
- /// and defines a sorting order on items, or state precise conditions under which this is true.</i>\r
- /// <i>Implementations <b>must</b> assure that repeated calls of\r
- /// the method to the same (in reference or binary identity sense) arguments \r
- /// will return values with the same sign (-1, 0 or +1), or state precise conditions\r
- /// under which the user \r
- /// can be assured repeated calls will return the same sign.</i>\r
- /// <i>Implementations of this interface must always return values from the method\r
- /// and never throw exceptions.</i>\r
- /// <i>This interface is identical to System.Collections.Generic.IComparer<T></i>\r
- /// </summary>\r
- public interface IComparer<T>\r
- {\r
- /// <summary>\r
- /// Compare two items with respect to this item comparer\r
- /// </summary>\r
- /// <param name="item1">First item</param>\r
- /// <param name="item2">Second item</param>\r
- /// <returns>Positive if item1 is greater than item2, 0 if they are equal, negative if item1 is less than item2</returns>\r
- int Compare(T item1, T item2);\r
- }\r
-\r
- /// <summary>\r
- /// The type of an item equalityComparer. \r
- /// <i>Implementations of this interface <b>must</b> assure that the methods are \r
- /// consistent, that is, that whenever two items i1 and i2 satisfies that Equals(i1,i2)\r
- /// returns true, then GetHashCode returns the same value for i1 and i2.</i>\r
- /// <i>Implementations of this interface <b>must</b> assure that repeated calls of\r
- /// the methods to the same (in reference or binary identity sense) arguments \r
- /// will return the same values, or state precise conditions under which the user \r
- /// can be assured repeated calls will return the same values.</i>\r
- /// <i>Implementations of this interface must always return values from the methods\r
- /// and never throw exceptions.</i>\r
- /// <i>This interface is similar in function to System.IKeyComparer<T></i>\r
- /// </summary>\r
- public interface SCG.IEqualityComparer<T>\r
- {\r
- /// <summary>\r
- /// Get the hash code with respect to this item equalityComparer\r
- /// </summary>\r
- /// <param name="item">The item</param>\r
- /// <returns>The hash code</returns>\r
- int GetHashCode(T item);\r
-\r
-\r
- /// <summary>\r
- /// Check if two items are equal with respect to this item equalityComparer\r
- /// </summary>\r
- /// <param name="item1">first item</param>\r
- /// <param name="item2">second item</param>\r
- /// <returns>True if equal</returns>\r
- bool Equals(T item1, T item2);\r
- }*/\r
-}\r
-
-#endif
+/*
+ Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+*/
+
+using System;
+using SCG = System.Collections.Generic;
+namespace C5
+{
+ /// <summary>
+ /// A generic collection, that can be enumerated backwards.
+ /// </summary>
+ public interface IDirectedEnumerable<T> : SCG.IEnumerable<T>
+ {
+ /// <summary>
+ /// Create a collection containing the same items as this collection, but
+ /// whose enumerator will enumerate the items backwards. The new collection
+ /// will become invalid if the original is modified. Method typically used as in
+ /// <code>foreach (T x in coll.Backwards()) {...}</code>
+ /// </summary>
+ /// <returns>The backwards collection.</returns>
+ IDirectedEnumerable<T> Backwards();
+
+
+ /// <summary>
+ /// <code>Forwards</code> if same, else <code>Backwards</code>
+ /// </summary>
+ /// <value>The enumeration direction relative to the original collection.</value>
+ EnumerationDirection Direction { get;}
+ }
+
+ /// <summary>
+ /// A generic collection that may be enumerated and can answer
+ /// efficiently how many items it contains. Like <code>IEnumerable<T></code>,
+ /// this interface does not prescribe any operations to initialize or update the
+ /// collection. The main usage for this interface is to be the return type of
+ /// query operations on generic collection.
+ /// </summary>
+ public interface ICollectionValue<T> : SCG.IEnumerable<T>, IShowable
+ {
+ /// <summary>
+ /// A flag bitmap of the events subscribable to by this collection.
+ /// </summary>
+ /// <value></value>
+ EventTypeEnum ListenableEvents { get;}
+
+ /// <summary>
+ /// A flag bitmap of the events currently subscribed to by this collection.
+ /// </summary>
+ /// <value></value>
+ EventTypeEnum ActiveEvents { get;}
+
+ /// <summary>
+ /// The change event. Will be raised for every change operation on the collection.
+ /// </summary>
+ event CollectionChangedHandler<T> CollectionChanged;
+
+ /// <summary>
+ /// The change event. Will be raised for every clear operation on the collection.
+ /// </summary>
+ event CollectionClearedHandler<T> CollectionCleared;
+
+ /// <summary>
+ /// The item added event. Will be raised for every individual addition to the collection.
+ /// </summary>
+ event ItemsAddedHandler<T> ItemsAdded;
+
+ /// <summary>
+ /// The item inserted event. Will be raised for every individual insertion to the collection.
+ /// </summary>
+ event ItemInsertedHandler<T> ItemInserted;
+
+ /// <summary>
+ /// The item removed event. Will be raised for every individual removal from the collection.
+ /// </summary>
+ event ItemsRemovedHandler<T> ItemsRemoved;
+
+ /// <summary>
+ /// The item removed at event. Will be raised for every individual removal at from the collection.
+ /// </summary>
+ event ItemRemovedAtHandler<T> ItemRemovedAt;
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>True if this collection is empty.</value>
+ bool IsEmpty { get;}
+
+ /// <summary>
+ /// </summary>
+ /// <value>The number of items in this collection</value>
+ int Count { get;}
+
+ /// <summary>
+ /// The value is symbolic indicating the type of asymptotic complexity
+ /// in terms of the size of this collection (worst-case or amortized as
+ /// relevant).
+ /// </summary>
+ /// <value>A characterization of the speed of the
+ /// <code>Count</code> property in this collection.</value>
+ Speed CountSpeed { get;}
+
+ /// <summary>
+ /// Copy the items of this collection to a contiguous part of an array.
+ /// </summary>
+ /// <param name="array">The array to copy to</param>
+ /// <param name="index">The index at which to copy the first item</param>
+ void CopyTo(T[] array, int index);
+
+ /// <summary>
+ /// Create an array with the items of this collection (in the same order as an
+ /// enumerator would output them).
+ /// </summary>
+ /// <returns>The array</returns>
+ T[] ToArray();
+
+ /// <summary>
+ /// Apply a delegate to all items of this collection.
+ /// </summary>
+ /// <param name="action">The delegate to apply</param>
+ void Apply(Act<T> action);
+
+
+ /// <summary>
+ /// Check if there exists an item that satisfies a
+ /// specific predicate in this collection.
+ /// </summary>
+ /// <param name="predicate">A delegate
+ /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
+ /// <returns>True is such an item exists</returns>
+ bool Exists(Fun<T, bool> predicate);
+
+ /// <summary>
+ /// Check if there exists an item that satisfies a
+ /// specific predicate in this collection and return the first one in enumeration order.
+ /// </summary>
+ /// <param name="predicate">A delegate
+ /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
+ /// <param name="item"></param>
+ /// <returns>True is such an item exists</returns>
+ bool Find(Fun<T, bool> predicate, out T item);
+
+
+ /// <summary>
+ /// Check if all items in this collection satisfies a specific predicate.
+ /// </summary>
+ /// <param name="predicate">A delegate
+ /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
+ /// <returns>True if all items satisfies the predicate</returns>
+ bool All(Fun<T, bool> predicate);
+
+ /// <summary>
+ /// Choose some item of this collection.
+ /// <para>Implementations must assure that the item
+ /// returned may be efficiently removed.</para>
+ /// <para>Implementors may decide to implement this method in a way such that repeated
+ /// calls do not necessarily give the same result, i.e. so that the result of the following
+ /// test is undetermined:
+ /// <code>coll.Choose() == coll.Choose()</code></para>
+ /// </summary>
+ /// <exception cref="NoSuchItemException">if collection is empty.</exception>
+ /// <returns></returns>
+ T Choose();
+
+ /// <summary>
+ /// Create an enumerable, enumerating the items of this collection that satisfies
+ /// a certain condition.
+ /// </summary>
+ /// <param name="filter">The T->bool filter delegate defining the condition</param>
+ /// <returns>The filtered enumerable</returns>
+ SCG.IEnumerable<T> Filter(Fun<T, bool> filter);
+ }
+
+
+
+ /// <summary>
+ /// A sized generic collection, that can be enumerated backwards.
+ /// </summary>
+ public interface IDirectedCollectionValue<T> : ICollectionValue<T>, IDirectedEnumerable<T>
+ {
+ /// <summary>
+ /// Create a collection containing the same items as this collection, but
+ /// whose enumerator will enumerate the items backwards. The new collection
+ /// will become invalid if the original is modified. Method typically used as in
+ /// <code>foreach (T x in coll.Backwards()) {...}</code>
+ /// </summary>
+ /// <returns>The backwards collection.</returns>
+ new IDirectedCollectionValue<T> Backwards();
+
+ /// <summary>
+ /// Check if there exists an item that satisfies a
+ /// specific predicate in this collection and return the first one in enumeration order.
+ /// </summary>
+ /// <param name="predicate">A delegate
+ /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
+ /// <param name="item"></param>
+ /// <returns>True is such an item exists</returns>
+ bool FindLast(Fun<T, bool> predicate, out T item);
+ }
+
+
+ /// <summary>
+ /// A generic collection to which one may add items. This is just the intersection
+ /// of the main stream generic collection interfaces and the priority queue interface,
+ /// <see cref="T:C5.ICollection`1"/> and <see cref="T:C5.IPriorityQueue`1"/>.
+ /// </summary>
+ public interface IExtensible<T> : ICollectionValue<T>, ICloneable
+ {
+ /// <summary>
+ /// If true any call of an updating operation will throw an
+ /// <code>ReadOnlyCollectionException</code>
+ /// </summary>
+ /// <value>True if this collection is read-only.</value>
+ bool IsReadOnly { get;}
+
+ //TODO: wonder where the right position of this is
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>False if this collection has set semantics, true if bag semantics.</value>
+ bool AllowsDuplicates { get;}
+
+ //TODO: wonder where the right position of this is. And the semantics.
+ /// <summary>
+ /// (Here should be a discussion of the role of equalityComparers. Any ).
+ /// </summary>
+ /// <value>The equalityComparer used by this collection to check equality of items.
+ /// Or null (????) if collection does not check equality at all or uses a comparer.</value>
+ SCG.IEqualityComparer<T> EqualityComparer { get;}
+
+ //ItemEqualityTypeEnum ItemEqualityType {get ;}
+
+ //TODO: find a good name
+
+ /// <summary>
+ /// By convention this is true for any collection with set semantics.
+ /// </summary>
+ /// <value>True if only one representative of a group of equal items
+ /// is kept in the collection together with the total count.</value>
+ bool DuplicatesByCounting { get;}
+
+ /// <summary>
+ /// Add an item to this collection if possible. If this collection has set
+ /// semantics, the item will be added if not already in the collection. If
+ /// bag semantics, the item will always be added.
+ /// </summary>
+ /// <param name="item">The item to add.</param>
+ /// <returns>True if item was added.</returns>
+ bool Add(T item);
+
+ /// <summary>
+ /// Add the elements from another collection with a more specialized item type
+ /// to this collection. If this
+ /// collection has set semantics, only items not already in the collection
+ /// will be added.
+ /// </summary>
+ /// <typeparam name="U">The type of items to add</typeparam>
+ /// <param name="items">The items to add</param>
+ void AddAll<U>(SCG.IEnumerable<U> items) where U : T;
+
+ //void Clear(); // for priority queue
+ //int Count why not?
+ /// <summary>
+ /// Check the integrity of the internal data structures of this collection.
+ /// <i>This is only relevant for developers of the library</i>
+ /// </summary>
+ /// <returns>True if check was passed.</returns>
+ bool Check();
+ }
+
+ /// <summary>
+ /// The simplest interface of a main stream generic collection
+ /// with lookup, insertion and removal operations.
+ /// </summary>
+ public interface ICollection<T> : IExtensible<T>, SCG.ICollection<T>
+ {
+ //This is somewhat similar to the RandomAccess marker itf in java
+ /// <summary>
+ /// The value is symbolic indicating the type of asymptotic complexity
+ /// in terms of the size of this collection (worst-case or amortized as
+ /// relevant).
+ /// <para>See <see cref="T:C5.Speed"/> for the set of symbols.</para>
+ /// </summary>
+ /// <value>A characterization of the speed of lookup operations
+ /// (<code>Contains()</code> etc.) of the implementation of this collection.</value>
+ Speed ContainsSpeed { get;}
+
+ /// <summary>
+ /// </summary>
+ /// <value>The number of items in this collection</value>
+ new int Count { get; }
+
+ /// <summary>
+ /// If true any call of an updating operation will throw an
+ /// <code>ReadOnlyCollectionException</code>
+ /// </summary>
+ /// <value>True if this collection is read-only.</value>
+ new bool IsReadOnly { get; }
+
+ /// <summary>
+ /// Add an item to this collection if possible. If this collection has set
+ /// semantics, the item will be added if not already in the collection. If
+ /// bag semantics, the item will always be added.
+ /// </summary>
+ /// <param name="item">The item to add.</param>
+ /// <returns>True if item was added.</returns>
+ new bool Add(T item);
+
+ /// <summary>
+ /// Copy the items of this collection to a contiguous part of an array.
+ /// </summary>
+ /// <param name="array">The array to copy to</param>
+ /// <param name="index">The index at which to copy the first item</param>
+ new void CopyTo(T[] array, int index);
+
+ /// <summary>
+ /// The unordered collection hashcode is defined as the sum of
+ /// <code>h(hashcode(item))</code> over the items
+ /// of the collection, where the function <code>h</code> is a function from
+ /// int to int of the form <code> t -> (a0*t+b0)^(a1*t+b1)^(a2*t+b2)</code>, where
+ /// the ax and bx are the same for all collection classes.
+ /// <para>The current implementation uses fixed values for the ax and bx,
+ /// specified as constants in the code.</para>
+ /// </summary>
+ /// <returns>The unordered hashcode of this collection.</returns>
+ int GetUnsequencedHashCode();
+
+
+ /// <summary>
+ /// Compare the contents of this collection to another one without regards to
+ /// the sequence order. The comparison will use this collection's itemequalityComparer
+ /// to compare individual items.
+ /// </summary>
+ /// <param name="otherCollection">The collection to compare to.</param>
+ /// <returns>True if this collection and that contains the same items.</returns>
+ bool UnsequencedEquals(ICollection<T> otherCollection);
+
+
+ /// <summary>
+ /// Check if this collection contains (an item equivalent to according to the
+ /// itemequalityComparer) a particular value.
+ /// </summary>
+ /// <param name="item">The value to check for.</param>
+ /// <returns>True if the items is in this collection.</returns>
+ new bool Contains(T item);
+
+
+ /// <summary>
+ /// Count the number of items of the collection equal to a particular value.
+ /// Returns 0 if and only if the value is not in the collection.
+ /// </summary>
+ /// <param name="item">The value to count.</param>
+ /// <returns>The number of copies found.</returns>
+ int ContainsCount(T item);
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ ICollectionValue<T> UniqueItems();
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities();
+
+ /// <summary>
+ /// Check whether this collection contains all the values in another collection.
+ /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)
+ /// the check is made with respect to multiplicities, else multiplicities
+ /// are not taken into account.
+ /// </summary>
+ /// <param name="items">The </param>
+ /// <typeparam name="U"></typeparam>
+ /// <returns>True if all values in <code>items</code>is in this collection.</returns>
+ bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T;
+
+
+ /// <summary>
+ /// Check if this collection contains an item equivalent according to the
+ /// itemequalityComparer to a particular value. If so, return in the ref argument (a
+ /// binary copy of) the actual value found.
+ /// </summary>
+ /// <param name="item">The value to look for.</param>
+ /// <returns>True if the items is in this collection.</returns>
+ bool Find(ref T item);
+
+
+ //This should probably just be bool Add(ref T item); !!!
+ /// <summary>
+ /// Check if this collection contains an item equivalent according to the
+ /// itemequalityComparer to a particular value. If so, return in the ref argument (a
+ /// binary copy of) the actual value found. Else, add the item to the collection.
+ /// </summary>
+ /// <param name="item">The value to look for.</param>
+ /// <returns>True if the item was found (hence not added).</returns>
+ bool FindOrAdd(ref T item);
+
+
+ /// <summary>
+ /// Check if this collection contains an item equivalent according to the
+ /// itemequalityComparer to a particular value. If so, update the item in the collection
+ /// with a (binary copy of) the supplied value. If the collection has bag semantics,
+ /// it depends on the value of DuplicatesByCounting if this updates all equivalent copies in
+ /// the collection or just one.
+ /// </summary>
+ /// <param name="item">Value to update.</param>
+ /// <returns>True if the item was found and hence updated.</returns>
+ bool Update(T item);
+
+ /// <summary>
+ /// Check if this collection contains an item equivalent according to the
+ /// itemequalityComparer to a particular value. If so, update the item in the collection
+ /// with a (binary copy of) the supplied value. If the collection has bag semantics,
+ /// it depends on the value of DuplicatesByCounting if this updates all equivalent copies in
+ /// the collection or just one.
+ /// </summary>
+ /// <param name="item">Value to update.</param>
+ /// <param name="olditem">On output the olditem, if found.</param>
+ /// <returns>True if the item was found and hence updated.</returns>
+ bool Update(T item, out T olditem);
+
+
+ /// <summary>
+ /// Check if this collection contains an item equivalent according to the
+ /// itemequalityComparer to a particular value. If so, update the item in the collection
+ /// to with a binary copy of the supplied value; else add the value to the collection.
+ /// </summary>
+ /// <param name="item">Value to add or update.</param>
+ /// <returns>True if the item was found and updated (hence not added).</returns>
+ bool UpdateOrAdd(T item);
+
+
+ /// <summary>
+ /// Check if this collection contains an item equivalent according to the
+ /// itemequalityComparer to a particular value. If so, update the item in the collection
+ /// to with a binary copy of the supplied value; else add the value to the collection.
+ /// </summary>
+ /// <param name="item">Value to add or update.</param>
+ /// <param name="olditem">On output the olditem, if found.</param>
+ /// <returns>True if the item was found and updated (hence not added).</returns>
+ bool UpdateOrAdd(T item, out T olditem);
+
+ /// <summary>
+ /// Remove a particular item from this collection. If the collection has bag
+ /// semantics only one copy equivalent to the supplied item is removed.
+ /// </summary>
+ /// <param name="item">The value to remove.</param>
+ /// <returns>True if the item was found (and removed).</returns>
+ new bool Remove(T item);
+
+
+ /// <summary>
+ /// Remove a particular item from this collection if found. If the collection
+ /// has bag semantics only one copy equivalent to the supplied item is removed,
+ /// which one is implementation dependent.
+ /// If an item was removed, report a binary copy of the actual item removed in
+ /// the argument.
+ /// </summary>
+ /// <param name="item">The value to remove.</param>
+ /// <param name="removeditem">The value removed if any.</param>
+ /// <returns>True if the item was found (and removed).</returns>
+ bool Remove(T item, out T removeditem);
+
+
+ /// <summary>
+ /// Remove all items equivalent to a given value.
+ /// </summary>
+ /// <param name="item">The value to remove.</param>
+ void RemoveAllCopies(T item);
+
+
+ /// <summary>
+ /// Remove all items in another collection from this one. If this collection
+ /// has bag semantics, take multiplicities into account.
+ /// </summary>
+ /// <typeparam name="U"></typeparam>
+ /// <param name="items">The items to remove.</param>
+ void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T;
+
+ //void RemoveAll(Fun<T, bool> predicate);
+
+ /// <summary>
+ /// Remove all items from this collection.
+ /// </summary>
+ new void Clear();
+
+
+ /// <summary>
+ /// Remove all items not in some other collection from this one. If this collection
+ /// has bag semantics, take multiplicities into account.
+ /// </summary>
+ /// <typeparam name="U"></typeparam>
+ /// <param name="items">The items to retain.</param>
+ void RetainAll<U>(SCG.IEnumerable<U> items) where U : T;
+
+ //void RetainAll(Fun<T, bool> predicate);
+ //IDictionary<T> UniqueItems()
+ }
+
+
+
+ /// <summary>
+ /// An editable collection maintaining a definite sequence order of the items.
+ ///
+ /// <i>Implementations of this interface must compute the hash code and
+ /// equality exactly as prescribed in the method definitions in order to
+ /// be consistent with other collection classes implementing this interface.</i>
+ /// <i>This interface is usually implemented by explicit interface implementation,
+ /// not as ordinary virtual methods.</i>
+ /// </summary>
+ public interface ISequenced<T> : ICollection<T>, IDirectedCollectionValue<T>
+ {
+ /// <summary>
+ /// The hashcode is defined as <code>h(...h(h(h(x1),x2),x3),...,xn)</code> for
+ /// <code>h(a,b)=CONSTANT*a+b</code> and the x's the hash codes of the items of
+ /// this collection.
+ /// </summary>
+ /// <returns>The sequence order hashcode of this collection.</returns>
+ int GetSequencedHashCode();
+
+
+ /// <summary>
+ /// Compare this sequenced collection to another one in sequence order.
+ /// </summary>
+ /// <param name="otherCollection">The sequenced collection to compare to.</param>
+ /// <returns>True if this collection and that contains equal (according to
+ /// this collection's itemequalityComparer) in the same sequence order.</returns>
+ bool SequencedEquals(ISequenced<T> otherCollection);
+ }
+
+
+
+ /// <summary>
+ /// A sequenced collection, where indices of items in the order are maintained
+ /// </summary>
+ public interface IIndexed<T> : ISequenced<T>
+ {
+ /// <summary>
+ /// </summary>
+ /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or
+ /// >= the size of the collection.</exception>
+ /// <value>The <code>index</code>'th item of this list.</value>
+ /// <param name="index">the index to lookup</param>
+ T this[int index] { get;}
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ Speed IndexingSpeed { get;}
+
+ /// <summary>
+ /// </summary>
+ /// <exception cref="ArgumentOutOfRangeException"></exception>
+ /// <value>The directed collection of items in a specific index interval.</value>
+ /// <param name="start">The low index of the interval (inclusive).</param>
+ /// <param name="count">The size of the range.</param>
+ IDirectedCollectionValue<T> this[int start, int count] { get;}
+
+
+ /// <summary>
+ /// Searches for an item in the list going forwards from the start.
+ /// </summary>
+ /// <param name="item">Item to search for.</param>
+ /// <returns>Index of item from start. A negative number if item not found,
+ /// namely the one's complement of the index at which the Add operation would put the item.</returns>
+ int IndexOf(T item);
+
+
+ /// <summary>
+ /// Searches for an item in the list going backwards from the end.
+ /// </summary>
+ /// <param name="item">Item to search for.</param>
+ /// <returns>Index of of item from the end. A negative number if item not found,
+ /// namely the two-complement of the index at which the Add operation would put the item.</returns>
+ int LastIndexOf(T item);
+
+ /// <summary>
+ /// Check if there exists an item that satisfies a
+ /// specific predicate in this collection and return the index of the first one.
+ /// </summary>
+ /// <param name="predicate">A delegate
+ /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
+ /// <returns>the index, if found, a negative value else</returns>
+ int FindIndex(Fun<T, bool> predicate);
+
+ /// <summary>
+ /// Check if there exists an item that satisfies a
+ /// specific predicate in this collection and return the index of the last one.
+ /// </summary>
+ /// <param name="predicate">A delegate
+ /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
+ /// <returns>the index, if found, a negative value else</returns>
+ int FindLastIndex(Fun<T, bool> predicate);
+
+
+ /// <summary>
+ /// Remove the item at a specific position of the list.
+ /// </summary>
+ /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or
+ /// >= the size of the collection.</exception>
+ /// <param name="index">The index of the item to remove.</param>
+ /// <returns>The removed item.</returns>
+ T RemoveAt(int index);
+
+
+ /// <summary>
+ /// Remove all items in an index interval.
+ /// </summary>
+ /// <exception cref="ArgumentOutOfRangeException"> if start or count
+ /// is negative or start+count > the size of the collection.</exception>
+ /// <param name="start">The index of the first item to remove.</param>
+ /// <param name="count">The number of items to remove.</param>
+ void RemoveInterval(int start, int count);
+ }
+
+ //TODO: decide if this should extend ICollection
+ /// <summary>
+ /// The interface describing the operations of a LIFO stack data structure.
+ /// </summary>
+ /// <typeparam name="T">The item type</typeparam>
+ public interface IStack<T> : IDirectedCollectionValue<T>
+ {
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ bool AllowsDuplicates { get;}
+ /// <summary>
+ /// Get the <code>index</code>'th element of the stack. The bottom of the stack has index 0.
+ /// </summary>
+ /// <param name="index"></param>
+ /// <returns></returns>
+ T this[int index] { get;}
+ /// <summary>
+ /// Push an item to the top of the stack.
+ /// </summary>
+ /// <param name="item">The item</param>
+ void Push(T item);
+ /// <summary>
+ /// Pop the item at the top of the stack from the stack.
+ /// </summary>
+ /// <returns>The popped item.</returns>
+ T Pop();
+ }
+
+ /// <summary>
+ /// The interface describing the operations of a FIFO queue data structure.
+ /// </summary>
+ /// <typeparam name="T">The item type</typeparam>
+ public interface IQueue<T> : IDirectedCollectionValue<T>
+ {
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ bool AllowsDuplicates { get;}
+ /// <summary>
+ /// Get the <code>index</code>'th element of the queue. The front of the queue has index 0.
+ /// </summary>
+ /// <param name="index"></param>
+ /// <returns></returns>
+ T this[int index] { get;}
+ /// <summary>
+ /// Enqueue an item at the back of the queue.
+ /// </summary>
+ /// <param name="item">The item</param>
+ void Enqueue(T item);
+ /// <summary>
+ /// Dequeue an item from the front of the queue.
+ /// </summary>
+ /// <returns>The item</returns>
+ T Dequeue();
+ }
+
+
+ /// <summary>
+ /// This is an indexed collection, where the item order is chosen by
+ /// the user at insertion time.
+ ///
+ /// NBNBNB: we need a description of the view functionality here!
+ /// </summary>
+ public interface IList<T> : IIndexed<T>, IDisposable, SCG.IList<T>, System.Collections.IList
+ {
+ /// <summary>
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if this list is empty.</exception>
+ /// <value>The first item in this list.</value>
+ T First { get;}
+
+ /// <summary>
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if this list is empty.</exception>
+ /// <value>The last item in this list.</value>
+ T Last { get;}
+
+ /// <summary>
+ /// Since <code>Add(T item)</code> always add at the end of the list,
+ /// this describes if list has FIFO or LIFO semantics.
+ /// </summary>
+ /// <value>True if the <code>Remove()</code> operation removes from the
+ /// start of the list, false if it removes from the end.</value>
+ bool FIFO { get; set;}
+
+ /// <summary>
+ ///
+ /// </summary>
+ bool IsFixedSize { get; }
+
+ /// <summary>
+ /// On this list, this indexer is read/write.
+ /// </summary>
+ /// <exception cref="IndexOutOfRangeException"> if index is negative or
+ /// >= the size of the collection.</exception>
+ /// <value>The index'th item of this list.</value>
+ /// <param name="index">The index of the item to fetch or store.</param>
+ new T this[int index] { get; set;}
+
+ #region Ambiguous calls when extending SCG.IList<T>
+
+ #region SCG.ICollection<T>
+ /// <summary>
+ ///
+ /// </summary>
+ new int Count { get; }
+
+ /// <summary>
+ ///
+ /// </summary>
+ new bool IsReadOnly { get; }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="item"></param>
+ /// <returns></returns>
+ new bool Add(T item);
+
+ /// <summary>
+ ///
+ /// </summary>
+ new void Clear();
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="item"></param>
+ /// <returns></returns>
+ new bool Contains(T item);
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="array"></param>
+ /// <param name="index"></param>
+ new void CopyTo(T[] array, int index);
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="item"></param>
+ /// <returns></returns>
+ new bool Remove(T item);
+
+ #endregion
+
+ #region SCG.IList<T> proper
+
+ /// <summary>
+ /// Searches for an item in the list going forwards from the start.
+ /// </summary>
+ /// <param name="item">Item to search for.</param>
+ /// <returns>Index of item from start. A negative number if item not found,
+ /// namely the one's complement of the index at which the Add operation would put the item.</returns>
+ new int IndexOf(T item);
+
+ /// <summary>
+ /// Remove the item at a specific position of the list.
+ /// </summary>
+ /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or
+ /// >= the size of the collection.</exception>
+ /// <param name="index">The index of the item to remove.</param>
+ /// <returns>The removed item.</returns>
+ new T RemoveAt(int index);
+
+ #endregion
+
+ #endregion
+
+ /*/// <summary>
+ /// Insert an item at a specific index location in this list.
+ /// </summary>
+ /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or
+ /// > the size of the collection.</exception>
+ /// <exception cref="DuplicateNotAllowedException"> if the list has
+ /// <code>AllowsDuplicates==false</code> and the item is
+ /// already in the list.</exception>
+ /// <param name="index">The index at which to insert.</param>
+ /// <param name="item">The item to insert.</param>
+ void Insert(int index, T item);*/
+
+ /// <summary>
+ /// Insert an item at the end of a compatible view, used as a pointer.
+ /// <para>The <code>pointer</code> must be a view on the same list as
+ /// <code>this</code> and the endpoitn of <code>pointer</code> must be
+ /// a valid insertion point of <code>this</code></para>
+ /// </summary>
+ /// <exception cref="IncompatibleViewException">If <code>pointer</code>
+ /// is not a view on the same list as <code>this</code></exception>
+ /// <exception cref="IndexOutOfRangeException"><b>??????</b> if the endpoint of
+ /// <code>pointer</code> is not inside <code>this</code></exception>
+ /// <exception cref="DuplicateNotAllowedException"> if the list has
+ /// <code>AllowsDuplicates==false</code> and the item is
+ /// already in the list.</exception>
+ /// <param name="pointer"></param>
+ /// <param name="item"></param>
+ void Insert(IList<T> pointer, T item);
+
+ /// <summary>
+ /// Insert an item at the front of this list.
+ /// <exception cref="DuplicateNotAllowedException"/> if the list has
+ /// <code>AllowsDuplicates==false</code> and the item is
+ /// already in the list.
+ /// </summary>
+ /// <param name="item">The item to insert.</param>
+ void InsertFirst(T item);
+
+ /// <summary>
+ /// Insert an item at the back of this list.
+ /// <exception cref="DuplicateNotAllowedException"/> if the list has
+ /// <code>AllowsDuplicates==false</code> and the item is
+ /// already in the list.
+ /// </summary>
+ /// <param name="item">The item to insert.</param>
+ void InsertLast(T item);
+
+ /// <summary>
+ /// Insert into this list all items from an enumerable collection starting
+ /// at a particular index.
+ /// </summary>
+ /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or
+ /// > the size of the collection.</exception>
+ /// <exception cref="DuplicateNotAllowedException"> if the list has
+ /// <code>AllowsDuplicates==false</code> and one of the items to insert is
+ /// already in the list.</exception>
+ /// <param name="index">Index to start inserting at</param>
+ /// <param name="items">Items to insert</param>
+ /// <typeparam name="U"></typeparam>
+ void InsertAll<U>(int index, SCG.IEnumerable<U> items) where U : T;
+
+ /// <summary>
+ /// Create a new list consisting of the items of this list satisfying a
+ /// certain predicate.
+ /// </summary>
+ /// <param name="filter">The filter delegate defining the predicate.</param>
+ /// <returns>The new list.</returns>
+ IList<T> FindAll(Fun<T, bool> filter);
+
+ /// <summary>
+ /// Create a new list consisting of the results of mapping all items of this
+ /// list. The new list will use the default equalityComparer for the item type V.
+ /// </summary>
+ /// <typeparam name="V">The type of items of the new list</typeparam>
+ /// <param name="mapper">The delegate defining the map.</param>
+ /// <returns>The new list.</returns>
+ IList<V> Map<V>(Fun<T, V> mapper);
+
+ /// <summary>
+ /// Create a new list consisting of the results of mapping all items of this
+ /// list. The new list will use a specified equalityComparer for the item type.
+ /// </summary>
+ /// <typeparam name="V">The type of items of the new list</typeparam>
+ /// <param name="mapper">The delegate defining the map.</param>
+ /// <param name="equalityComparer">The equalityComparer to use for the new list</param>
+ /// <returns>The new list.</returns>
+ IList<V> Map<V>(Fun<T, V> mapper, SCG.IEqualityComparer<V> equalityComparer);
+
+ /// <summary>
+ /// Remove one item from the list: from the front if <code>FIFO</code>
+ /// is true, else from the back.
+ /// <exception cref="NoSuchItemException"/> if this list is empty.
+ /// </summary>
+ /// <returns>The removed item.</returns>
+ T Remove();
+
+ /// <summary>
+ /// Remove one item from the front of the list.
+ /// <exception cref="NoSuchItemException"/> if this list is empty.
+ /// </summary>
+ /// <returns>The removed item.</returns>
+ T RemoveFirst();
+
+ /// <summary>
+ /// Remove one item from the back of the list.
+ /// <exception cref="NoSuchItemException"/> if this list is empty.
+ /// </summary>
+ /// <returns>The removed item.</returns>
+ T RemoveLast();
+
+ /// <summary>
+ /// Create a list view on this list.
+ /// <exception cref="ArgumentOutOfRangeException"/> if the view would not fit into
+ /// this list.
+ /// </summary>
+ /// <param name="start">The index in this list of the start of the view.</param>
+ /// <param name="count">The size of the view.</param>
+ /// <returns>The new list view.</returns>
+ IList<T> View(int start, int count);
+
+ /// <summary>
+ /// Create a list view on this list containing the (first) occurrence of a particular item.
+ /// <exception cref="NoSuchItemException"/> if the item is not in this list.
+ /// </summary>
+ /// <param name="item">The item to find.</param>
+ /// <returns>The new list view.</returns>
+ IList<T> ViewOf(T item);
+
+ /// <summary>
+ /// Create a list view on this list containing the last occurrence of a particular item.
+ /// <exception cref="NoSuchItemException"/> if the item is not in this list.
+ /// </summary>
+ /// <param name="item">The item to find.</param>
+ /// <returns>The new list view.</returns>
+ IList<T> LastViewOf(T item);
+
+ /// <summary>
+ /// Null if this list is not a view.
+ /// </summary>
+ /// <value>Underlying list for view.</value>
+ IList<T> Underlying { get;}
+
+ /// <summary>
+ /// </summary>
+ /// <value>Offset for this list view or 0 for an underlying list.</value>
+ int Offset { get;}
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ bool IsValid { get;}
+
+ /// <summary>
+ /// Slide this list view along the underlying list.
+ /// </summary>
+ /// <exception cref="NotAViewException"> if this list is not a view.</exception>
+ /// <exception cref="ArgumentOutOfRangeException"> if the operation
+ /// would bring either end of the view outside the underlying list.</exception>
+ /// <param name="offset">The signed amount to slide: positive to slide
+ /// towards the end.</param>
+ IList<T> Slide(int offset);
+
+ /// <summary>
+ /// Slide this list view along the underlying list, changing its size.
+ ///
+ /// </summary>
+ /// <exception cref="NotAViewException"> if this list is not a view.</exception>
+ /// <exception cref="ArgumentOutOfRangeException"> if the operation
+ /// would bring either end of the view outside the underlying list.</exception>
+ /// <param name="offset">The signed amount to slide: positive to slide
+ /// towards the end.</param>
+ /// <param name="size">The new size of the view.</param>
+ IList<T> Slide(int offset, int size);
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="offset"></param>
+ /// <returns></returns>
+ bool TrySlide(int offset);
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="offset"></param>
+ /// <param name="size"></param>
+ /// <returns></returns>
+ bool TrySlide(int offset, int size);
+
+ /// <summary>
+ ///
+ /// <para>Returns null if <code>otherView</code> is strictly to the left of this view</para>
+ /// </summary>
+ /// <param name="otherView"></param>
+ /// <exception cref="IncompatibleViewException">If otherView does not have the same underlying list as this</exception>
+ /// <exception cref="ArgumentOutOfRangeException">If <code>otherView</code> is strictly to the left of this view</exception>
+ /// <returns></returns>
+ IList<T> Span(IList<T> otherView);
+
+ /// <summary>
+ /// Reverse the list so the items are in the opposite sequence order.
+ /// </summary>
+ void Reverse();
+
+ /// <summary>
+ /// Check if this list is sorted according to the default sorting order
+ /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class
+ /// </summary>
+ /// <exception cref="NotComparableException">if T is not comparable</exception>
+ /// <returns>True if the list is sorted, else false.</returns>
+ bool IsSorted();
+
+ /// <summary>
+ /// Check if this list is sorted according to a specific sorting order.
+ /// </summary>
+ /// <param name="comparer">The comparer defining the sorting order.</param>
+ /// <returns>True if the list is sorted, else false.</returns>
+ bool IsSorted(SCG.IComparer<T> comparer);
+
+ /// <summary>
+ /// Sort the items of the list according to the default sorting order
+ /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class
+ /// </summary>
+ /// <exception cref="NotComparableException">if T is not comparable</exception>
+ void Sort();
+
+ /// <summary>
+ /// Sort the items of the list according to a specified sorting order.
+ /// <para>The sorting does not perform duplicate elimination or identify items
+ /// according to the comparer or itemequalityComparer. I.e. the list as an
+ /// unsequenced collection with binary equality, will not change.
+ /// </para>
+ /// </summary>
+ /// <param name="comparer">The comparer defining the sorting order.</param>
+ void Sort(SCG.IComparer<T> comparer);
+
+
+ /// <summary>
+ /// Randomly shuffle the items of this list.
+ /// </summary>
+ void Shuffle();
+
+
+ /// <summary>
+ /// Shuffle the items of this list according to a specific random source.
+ /// </summary>
+ /// <param name="rnd">The random source.</param>
+ void Shuffle(Random rnd);
+ }
+
+
+ /// <summary>
+ /// The base type of a priority queue handle
+ /// </summary>
+ /// <typeparam name="T"></typeparam>
+ public interface IPriorityQueueHandle<T>
+ {
+ //TODO: make abstract and prepare for double dispatch:
+ //public virtual bool Delete(IPriorityQueue<T> q) { throw new InvalidFooException();}
+ //bool Replace(T item);
+ }
+
+
+ /// <summary>
+ /// A generic collection of items prioritized by a comparison (order) relation.
+ /// Supports adding items and reporting or removing extremal elements.
+ /// <para>
+ ///
+ /// </para>
+ /// When adding an item, the user may choose to have a handle allocated for this item in the queue.
+ /// The resulting handle may be used for deleting the item even if not extremal, and for replacing the item.
+ /// A priority queue typically only holds numeric priorities associated with some objects
+ /// maintained separately in other collection objects.
+ /// </summary>
+ public interface IPriorityQueue<T> : IExtensible<T>
+ {
+ /// <summary>
+ /// Find the current least item of this priority queue.
+ /// </summary>
+ /// <returns>The least item.</returns>
+ T FindMin();
+
+
+ /// <summary>
+ /// Remove the least item from this priority queue.
+ /// </summary>
+ /// <returns>The removed item.</returns>
+ T DeleteMin();
+
+
+ /// <summary>
+ /// Find the current largest item of this priority queue.
+ /// </summary>
+ /// <returns>The largest item.</returns>
+ T FindMax();
+
+
+ /// <summary>
+ /// Remove the largest item from this priority queue.
+ /// </summary>
+ /// <returns>The removed item.</returns>
+ T DeleteMax();
+
+ /// <summary>
+ /// The comparer object supplied at creation time for this collection
+ /// </summary>
+ /// <value>The comparer</value>
+ SCG.IComparer<T> Comparer { get;}
+ /// <summary>
+ /// Get or set the item corresponding to a handle. Throws exceptions on
+ /// invalid handles.
+ /// </summary>
+ /// <param name="handle"></param>
+ /// <returns></returns>
+ T this[IPriorityQueueHandle<T> handle] { get; set;}
+
+ /// <summary>
+ /// Check if the entry corresponding to a handle is in the priority queue.
+ /// </summary>
+ /// <param name="handle"></param>
+ /// <param name="item"></param>
+ /// <returns></returns>
+ bool Find(IPriorityQueueHandle<T> handle, out T item);
+
+ /// <summary>
+ /// Add an item to the priority queue, receiving a
+ /// handle for the item in the queue,
+ /// or reusing an existing unused handle.
+ /// </summary>
+ /// <param name="handle">On output: a handle for the added item.
+ /// On input: null for allocating a new handle, or a currently unused handle for reuse.
+ /// A handle for reuse must be compatible with this priority queue,
+ /// by being created by a priority queue of the same runtime type, but not
+ /// necessarily the same priority queue object.</param>
+ /// <param name="item"></param>
+ /// <returns></returns>
+ bool Add(ref IPriorityQueueHandle<T> handle, T item);
+
+ /// <summary>
+ /// Delete an item with a handle from a priority queue
+ /// </summary>
+ /// <param name="handle">The handle for the item. The handle will be invalidated, but reusable.</param>
+ /// <returns>The deleted item</returns>
+ T Delete(IPriorityQueueHandle<T> handle);
+
+ /// <summary>
+ /// Replace an item with a handle in a priority queue with a new item.
+ /// Typically used for changing the priority of some queued object.
+ /// </summary>
+ /// <param name="handle">The handle for the old item</param>
+ /// <param name="item">The new item</param>
+ /// <returns>The old item</returns>
+ T Replace(IPriorityQueueHandle<T> handle, T item);
+
+ /// <summary>
+ /// Find the current least item of this priority queue.
+ /// </summary>
+ /// <param name="handle">On return: the handle of the item.</param>
+ /// <returns>The least item.</returns>
+ T FindMin(out IPriorityQueueHandle<T> handle);
+
+ /// <summary>
+ /// Find the current largest item of this priority queue.
+ /// </summary>
+ /// <param name="handle">On return: the handle of the item.</param>
+ /// <returns>The largest item.</returns>
+
+ T FindMax(out IPriorityQueueHandle<T> handle);
+
+ /// <summary>
+ /// Remove the least item from this priority queue.
+ /// </summary>
+ /// <param name="handle">On return: the handle of the removed item.</param>
+ /// <returns>The removed item.</returns>
+
+ T DeleteMin(out IPriorityQueueHandle<T> handle);
+
+ /// <summary>
+ /// Remove the largest item from this priority queue.
+ /// </summary>
+ /// <param name="handle">On return: the handle of the removed item.</param>
+ /// <returns>The removed item.</returns>
+ T DeleteMax(out IPriorityQueueHandle<T> handle);
+ }
+
+
+
+ /// <summary>
+ /// A sorted collection, i.e. a collection where items are maintained and can be searched for in sorted order.
+ /// Thus the sequence order is given as a sorting order.
+ ///
+ /// <para>The sorting order is defined by a comparer, an object of type IComparer<T>
+ /// (<see cref="T:C5.IComparer`1"/>). Implementors of this interface will normally let the user
+ /// define the comparer as an argument to a constructor.
+ /// Usually there will also be constructors without a comparer argument, in which case the
+ /// comparer should be the defalt comparer for the item type, <see cref="P:C5.Comparer`1.Default"/>.</para>
+ ///
+ /// <para>The comparer of the sorted collection is available as the <code>Comparer</code> property
+ /// (<see cref="P:C5.ISorted`1.Comparer"/>).</para>
+ ///
+ /// <para>The methods are grouped according to
+ /// <list>
+ /// <item>Extrema: report or report and delete an extremal item. This is reminiscent of simplified priority queues.</item>
+ /// <item>Nearest neighbor: report predecessor or successor in the collection of an item. Cut belongs to this group.</item>
+ /// <item>Range: report a view of a range of elements or remove all elements in a range.</item>
+ /// <item>AddSorted: add a collection of items known to be sorted in the same order (should be faster) (to be removed?)</item>
+ /// </list>
+ /// </para>
+ ///
+ /// <para>Since this interface extends ISequenced<T>, sorted collections will also have an
+ /// item equalityComparer (<see cref="P:C5.IExtensible`1.EqualityComparer"/>). This equalityComparer will not be used in connection with
+ /// the inner workings of the sorted collection, but will be used if the sorted collection is used as
+ /// an item in a collection of unsequenced or sequenced collections,
+ /// (<see cref="T:C5.ICollection`1"/> and <see cref="T:C5.ISequenced`1"/>)</para>
+ ///
+ /// <para>Note that code may check if two sorted collections has the same sorting order
+ /// by checking if the Comparer properties are equal. This is done a few places in this library
+ /// for optimization purposes.</para>
+ /// </summary>
+ public interface ISorted<T> : ISequenced<T>
+ {
+ /// <summary>
+ /// Find the current least item of this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The least item.</returns>
+ T FindMin();
+
+
+ /// <summary>
+ /// Remove the least item from this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The removed item.</returns>
+ T DeleteMin();
+
+
+ /// <summary>
+ /// Find the current largest item of this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The largest item.</returns>
+ T FindMax();
+
+
+ /// <summary>
+ /// Remove the largest item from this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The removed item.</returns>
+ T DeleteMax();
+
+ /// <summary>
+ /// The comparer object supplied at creation time for this sorted collection.
+ /// </summary>
+ /// <value>The comparer</value>
+ SCG.IComparer<T> Comparer { get; }
+
+ /// <summary>
+ /// Find the strict predecessor of item in the sorted collection,
+ /// that is, the greatest item in the collection smaller than the item.
+ /// </summary>
+ /// <param name="item">The item to find the predecessor for.</param>
+ /// <param name="res">The predecessor, if any; otherwise the default value for T.</param>
+ /// <returns>True if item has a predecessor; otherwise false.</returns>
+ bool TryPredecessor(T item, out T res);
+
+
+ /// <summary>
+ /// Find the strict successor of item in the sorted collection,
+ /// that is, the least item in the collection greater than the supplied value.
+ /// </summary>
+ /// <param name="item">The item to find the successor for.</param>
+ /// <param name="res">The successor, if any; otherwise the default value for T.</param>
+ /// <returns>True if item has a successor; otherwise false.</returns>
+ bool TrySuccessor(T item, out T res);
+
+
+ /// <summary>
+ /// Find the weak predecessor of item in the sorted collection,
+ /// that is, the greatest item in the collection smaller than or equal to the item.
+ /// </summary>
+ /// <param name="item">The item to find the weak predecessor for.</param>
+ /// <param name="res">The weak predecessor, if any; otherwise the default value for T.</param>
+ /// <returns>True if item has a weak predecessor; otherwise false.</returns>
+ bool TryWeakPredecessor(T item, out T res);
+
+
+ /// <summary>
+ /// Find the weak successor of item in the sorted collection,
+ /// that is, the least item in the collection greater than or equal to the supplied value.
+ /// </summary>
+ /// <param name="item">The item to find the weak successor for.</param>
+ /// <param name="res">The weak successor, if any; otherwise the default value for T.</param>
+ /// <returns>True if item has a weak successor; otherwise false.</returns>
+ bool TryWeakSuccessor(T item, out T res);
+
+
+ /// <summary>
+ /// Find the strict predecessor in the sorted collection of a particular value,
+ /// that is, the largest item in the collection less than the supplied value.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if no such element exists (the
+ /// supplied value is less than or equal to the minimum of this collection.)</exception>
+ /// <param name="item">The item to find the predecessor for.</param>
+ /// <returns>The predecessor.</returns>
+ T Predecessor(T item);
+
+
+ /// <summary>
+ /// Find the strict successor in the sorted collection of a particular value,
+ /// that is, the least item in the collection greater than the supplied value.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if no such element exists (the
+ /// supplied value is greater than or equal to the maximum of this collection.)</exception>
+ /// <param name="item">The item to find the successor for.</param>
+ /// <returns>The successor.</returns>
+ T Successor(T item);
+
+
+ /// <summary>
+ /// Find the weak predecessor in the sorted collection of a particular value,
+ /// that is, the largest item in the collection less than or equal to the supplied value.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if no such element exists (the
+ /// supplied value is less than the minimum of this collection.)</exception>
+ /// <param name="item">The item to find the weak predecessor for.</param>
+ /// <returns>The weak predecessor.</returns>
+ T WeakPredecessor(T item);
+
+
+ /// <summary>
+ /// Find the weak successor in the sorted collection of a particular value,
+ /// that is, the least item in the collection greater than or equal to the supplied value.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if no such element exists (the
+ /// supplied value is greater than the maximum of this collection.)</exception>
+ ///<param name="item">The item to find the weak successor for.</param>
+ /// <returns>The weak successor.</returns>
+ T WeakSuccessor(T item);
+
+
+ /// <summary>
+ /// Given a "cut" function from the items of the sorted collection to <code>int</code>
+ /// whose only sign changes when going through items in increasing order
+ /// can be
+ /// <list>
+ /// <item>from positive to zero</item>
+ /// <item>from positive to negative</item>
+ /// <item>from zero to negative</item>
+ /// </list>
+ /// The "cut" function is supplied as the <code>CompareTo</code> method
+ /// of an object <code>c</code> implementing
+ /// <code>IComparable<T></code>.
+ /// A typical example is the case where <code>T</code> is comparable and
+ /// <code>cutFunction</code> is itself of type <code>T</code>.
+ /// <para>This method performs a search in the sorted collection for the ranges in which the
+ /// "cut" function is negative, zero respectively positive. If <code>T</code> is comparable
+ /// and <code>c</code> is of type <code>T</code>, this is a safe way (no exceptions thrown)
+ /// to find predecessor and successor of <code>c</code>.
+ /// </para>
+ /// <para> If the supplied cut function does not satisfy the sign-change condition,
+ /// the result of this call is undefined.
+ /// </para>
+ ///
+ /// </summary>
+ /// <param name="cutFunction">The cut function <code>T</code> to <code>int</code>, given
+ /// by the <code>CompareTo</code> method of an object implementing
+ /// <code>IComparable<T></code>.</param>
+ /// <param name="low">Returns the largest item in the collection, where the
+ /// cut function is positive (if any).</param>
+ /// <param name="lowIsValid">Returns true if the cut function is positive somewhere
+ /// on this collection.</param>
+ /// <param name="high">Returns the least item in the collection, where the
+ /// cut function is negative (if any).</param>
+ /// <param name="highIsValid">Returns true if the cut function is negative somewhere
+ /// on this collection.</param>
+ /// <returns>True if the cut function is zero somewhere
+ /// on this collection.</returns>
+ bool Cut(IComparable<T> cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid);
+
+
+ /// <summary>
+ /// Query this sorted collection for items greater than or equal to a supplied value.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ IDirectedEnumerable<T> RangeFrom(T bot);
+
+
+ /// <summary>
+ /// Query this sorted collection for items between two supplied values.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive).</param>
+ /// <param name="top">The upper bound (exclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ IDirectedEnumerable<T> RangeFromTo(T bot, T top);
+
+
+ /// <summary>
+ /// Query this sorted collection for items less than a supplied value.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <param name="top">The upper bound (exclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ IDirectedEnumerable<T> RangeTo(T top);
+
+
+ /// <summary>
+ /// Create a directed collection with the same items as this collection.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <returns>The result directed collection.</returns>
+ IDirectedCollectionValue<T> RangeAll();
+
+
+ //TODO: remove now that we assume that we can check the sorting order?
+ /// <summary>
+ /// Add all the items from another collection with an enumeration order that
+ /// is increasing in the items.
+ /// </summary>
+ /// <exception cref="ArgumentException"> if the enumerated items turns out
+ /// not to be in increasing order.</exception>
+ /// <param name="items">The collection to add.</param>
+ /// <typeparam name="U"></typeparam>
+ void AddSorted<U>(SCG.IEnumerable<U> items) where U : T;
+
+
+ /// <summary>
+ /// Remove all items of this collection above or at a supplied threshold.
+ /// </summary>
+ /// <param name="low">The lower threshold (inclusive).</param>
+ void RemoveRangeFrom(T low);
+
+
+ /// <summary>
+ /// Remove all items of this collection between two supplied thresholds.
+ /// </summary>
+ /// <param name="low">The lower threshold (inclusive).</param>
+ /// <param name="hi">The upper threshold (exclusive).</param>
+ void RemoveRangeFromTo(T low, T hi);
+
+
+ /// <summary>
+ /// Remove all items of this collection below a supplied threshold.
+ /// </summary>
+ /// <param name="hi">The upper threshold (exclusive).</param>
+ void RemoveRangeTo(T hi);
+ }
+
+
+
+ /// <summary>
+ /// A collection where items are maintained in sorted order together
+ /// with their indexes in that order.
+ /// </summary>
+ public interface IIndexedSorted<T> : ISorted<T>, IIndexed<T>
+ {
+ /// <summary>
+ /// Determine the number of items at or above a supplied threshold.
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive)</param>
+ /// <returns>The number of matcing items.</returns>
+ int CountFrom(T bot);
+
+
+ /// <summary>
+ /// Determine the number of items between two supplied thresholds.
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive)</param>
+ /// <param name="top">The upper bound (exclusive)</param>
+ /// <returns>The number of matcing items.</returns>
+ int CountFromTo(T bot, T top);
+
+
+ /// <summary>
+ /// Determine the number of items below a supplied threshold.
+ /// </summary>
+ /// <param name="top">The upper bound (exclusive)</param>
+ /// <returns>The number of matcing items.</returns>
+ int CountTo(T top);
+
+
+ /// <summary>
+ /// Query this sorted collection for items greater than or equal to a supplied value.
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ new IDirectedCollectionValue<T> RangeFrom(T bot);
+
+
+ /// <summary>
+ /// Query this sorted collection for items between two supplied values.
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive).</param>
+ /// <param name="top">The upper bound (exclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ new IDirectedCollectionValue<T> RangeFromTo(T bot, T top);
+
+
+ /// <summary>
+ /// Query this sorted collection for items less than a supplied value.
+ /// </summary>
+ /// <param name="top">The upper bound (exclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ new IDirectedCollectionValue<T> RangeTo(T top);
+
+
+ /// <summary>
+ /// Create a new indexed sorted collection consisting of the items of this
+ /// indexed sorted collection satisfying a certain predicate.
+ /// </summary>
+ /// <param name="predicate">The filter delegate defining the predicate.</param>
+ /// <returns>The new indexed sorted collection.</returns>
+ IIndexedSorted<T> FindAll(Fun<T, bool> predicate);
+
+
+ /// <summary>
+ /// Create a new indexed sorted collection consisting of the results of
+ /// mapping all items of this list.
+ /// <exception cref="ArgumentException"/> if the map is not increasing over
+ /// the items of this collection (with respect to the two given comparison
+ /// relations).
+ /// </summary>
+ /// <param name="mapper">The delegate definging the map.</param>
+ /// <param name="comparer">The comparion relation to use for the result.</param>
+ /// <returns>The new sorted collection.</returns>
+ IIndexedSorted<V> Map<V>(Fun<T, V> mapper, SCG.IComparer<V> comparer);
+ }
+
+
+
+ /// <summary>
+ /// The type of a sorted collection with persistence
+ /// </summary>
+ public interface IPersistentSorted<T> : ISorted<T>, IDisposable
+ {
+ /// <summary>
+ /// Make a (read-only) snap shot of this collection.
+ /// </summary>
+ /// <returns>The snap shot.</returns>
+ ISorted<T> Snapshot();
+ }
+
+
+
+ /*************************************************************************/
+ /// <summary>
+ /// A dictionary with keys of type K and values of type V. Equivalent to a
+ /// finite partial map from K to V.
+ /// </summary>
+ public interface IDictionary<K, V> : ICollectionValue<KeyValuePair<K, V>>, ICloneable
+ {
+ /// <summary>
+ /// The key equalityComparer.
+ /// </summary>
+ /// <value></value>
+ SCG.IEqualityComparer<K> EqualityComparer { get;}
+
+ /// <summary>
+ /// Indexer for dictionary.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if no entry is found. </exception>
+ /// <value>The value corresponding to the key</value>
+ V this[K key] { get; set;}
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>True if dictionary is read-only</value>
+ bool IsReadOnly { get;}
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>A collection containg the all the keys of the dictionary</value>
+ ICollectionValue<K> Keys { get;}
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>A collection containing all the values of the dictionary</value>
+ ICollectionValue<V> Values { get;}
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>A delegate of type <see cref="T:C5.Fun`2"/> defining the partial function from K to V give by the dictionary.</value>
+ Fun<K, V> Fun { get; }
+
+
+ //TODO: resolve inconsistency: Add thows exception if key already there, AddAll ignores keys already There?
+ /// <summary>
+ /// Add a new (key, value) pair (a mapping) to the dictionary.
+ /// </summary>
+ /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>>
+ /// <param name="key">Key to add</param>
+ /// <param name="val">Value to add</param>
+ void Add(K key, V val);
+
+ /// <summary>
+ /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.
+ /// </summary>
+ /// <exception cref="DuplicateNotAllowedException">
+ /// If the input contains duplicate keys or a key already present in this dictionary.</exception>
+ /// <param name="entries"></param>
+ void AddAll<U, W>(SCG.IEnumerable<KeyValuePair<U, W>> entries)
+ where U : K
+ where W : V
+ ;
+
+ /// <summary>
+ /// The value is symbolic indicating the type of asymptotic complexity
+ /// in terms of the size of this collection (worst-case or amortized as
+ /// relevant).
+ /// <para>See <see cref="T:C5.Speed"/> for the set of symbols.</para>
+ /// </summary>
+ /// <value>A characterization of the speed of lookup operations
+ /// (<code>Contains()</code> etc.) of the implementation of this dictionary.</value>
+ Speed ContainsSpeed { get;}
+
+ /// <summary>
+ /// Check whether this collection contains all the values in another collection.
+ /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)
+ /// the check is made with respect to multiplicities, else multiplicities
+ /// are not taken into account.
+ /// </summary>
+ /// <param name="items">The </param>
+ /// <returns>True if all values in <code>items</code>is in this collection.</returns>
+ bool ContainsAll<H>(SCG.IEnumerable<H> items) where H : K;
+
+ /// <summary>
+ /// Remove an entry with a given key from the dictionary
+ /// </summary>
+ /// <param name="key">The key of the entry to remove</param>
+ /// <returns>True if an entry was found (and removed)</returns>
+ bool Remove(K key);
+
+
+ /// <summary>
+ /// Remove an entry with a given key from the dictionary and report its value.
+ /// </summary>
+ /// <param name="key">The key of the entry to remove</param>
+ /// <param name="val">On exit, the value of the removed entry</param>
+ /// <returns>True if an entry was found (and removed)</returns>
+ bool Remove(K key, out V val);
+
+
+ /// <summary>
+ /// Remove all entries from the dictionary
+ /// </summary>
+ void Clear();
+
+
+ /// <summary>
+ /// Check if there is an entry with a specified key
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <returns>True if key was found</returns>
+ bool Contains(K key);
+
+
+ /// <summary>
+ /// Check if there is an entry with a specified key and report the corresponding
+ /// value if found. This can be seen as a safe form of "val = this[key]".
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">On exit, the value of the entry</param>
+ /// <returns>True if key was found</returns>
+ bool Find(K key, out V val);
+
+ /// <summary>
+ /// Check if there is an entry with a specified key and report the corresponding
+ /// value if found. This can be seen as a safe form of "val = this[key]".
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">On exit, the value of the entry</param>
+ /// <returns>True if key was found</returns>
+ bool Find(ref K key, out V val);
+
+
+ /// <summary>
+ /// Look for a specific key in the dictionary and if found replace the value with a new one.
+ /// This can be seen as a non-adding version of "this[key] = val".
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">The new value</param>
+ /// <returns>True if key was found</returns>
+ bool Update(K key, V val); //no-adding
+
+
+ /// <summary>
+ /// Look for a specific key in the dictionary and if found replace the value with a new one.
+ /// This can be seen as a non-adding version of "this[key] = val" reporting the old value.
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">The new value</param>
+ /// <param name="oldval">The old value if any</param>
+ /// <returns>True if key was found</returns>
+ bool Update(K key, V val, out V oldval); //no-adding
+
+ /// <summary>
+ /// Look for a specific key in the dictionary. If found, report the corresponding value,
+ /// else add an entry with the key and the supplied value.
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">On entry the value to add if the key is not found.
+ /// On exit the value found if any.</param>
+ /// <returns>True if key was found</returns>
+ bool FindOrAdd(K key, ref V val); //mixture
+
+
+ /// <summary>
+ /// Update value in dictionary corresponding to key if found, else add new entry.
+ /// More general than "this[key] = val;" by reporting if key was found.
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">The value to add or replace with.</param>
+ /// <returns>True if key was found and value updated.</returns>
+ bool UpdateOrAdd(K key, V val);
+
+
+ /// <summary>
+ /// Update value in dictionary corresponding to key if found, else add new entry.
+ /// More general than "this[key] = val;" by reporting if key was found.
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="val">The value to add or replace with.</param>
+ /// <param name="oldval">The old value if any</param>
+ /// <returns>True if key was found and value updated.</returns>
+ bool UpdateOrAdd(K key, V val, out V oldval);
+
+
+ /// <summary>
+ /// Check the integrity of the internal data structures of this dictionary.
+ /// Only avaliable in DEBUG builds???
+ /// </summary>
+ /// <returns>True if check does not fail.</returns>
+ bool Check();
+ }
+
+
+
+ /// <summary>
+ /// A dictionary with sorted keys.
+ /// </summary>
+ public interface ISortedDictionary<K, V> : IDictionary<K, V>
+ {
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ new ISorted<K> Keys { get;}
+
+ /// <summary>
+ /// Find the current least item of this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The least item.</returns>
+ KeyValuePair<K, V> FindMin();
+
+
+ /// <summary>
+ /// Remove the least item from this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The removed item.</returns>
+ KeyValuePair<K, V> DeleteMin();
+
+
+ /// <summary>
+ /// Find the current largest item of this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The largest item.</returns>
+ KeyValuePair<K, V> FindMax();
+
+
+ /// <summary>
+ /// Remove the largest item from this sorted collection.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>
+ /// <returns>The removed item.</returns>
+ KeyValuePair<K, V> DeleteMax();
+
+ /// <summary>
+ /// The key comparer used by this dictionary.
+ /// </summary>
+ /// <value></value>
+ SCG.IComparer<K> Comparer { get;}
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// predecessor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The predecessor, if any</param>
+ /// <returns>True if key has a predecessor</returns>
+ bool TryPredecessor(K key, out KeyValuePair<K, V> res);
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// successor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The successor, if any</param>
+ /// <returns>True if the key has a successor</returns>
+ bool TrySuccessor(K key, out KeyValuePair<K, V> res);
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// weak predecessor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The predecessor, if any</param>
+ /// <returns>True if key has a weak predecessor</returns>
+ bool TryWeakPredecessor(K key, out KeyValuePair<K, V> res);
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// weak successor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The weak successor, if any</param>
+ /// <returns>True if the key has a weak successor</returns>
+ bool TryWeakSuccessor(K key, out KeyValuePair<K, V> res);
+
+ /// <summary>
+ /// Find the entry with the largest key less than a given key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>
+ /// <param name="key">The key to compare to</param>
+ /// <returns>The entry</returns>
+ KeyValuePair<K, V> Predecessor(K key);
+
+
+ /// <summary>
+ /// Find the entry with the least key greater than a given key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>
+ /// <param name="key">The key to compare to</param>
+ /// <returns>The entry</returns>
+ KeyValuePair<K, V> Successor(K key);
+
+
+ /// <summary>
+ /// Find the entry with the largest key less than or equal to a given key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>
+ /// <param name="key">The key to compare to</param>
+ /// <returns>The entry</returns>
+ KeyValuePair<K, V> WeakPredecessor(K key);
+
+
+ /// <summary>
+ /// Find the entry with the least key greater than or equal to a given key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>
+ /// <param name="key">The key to compare to</param>
+ /// <returns>The entry</returns>
+ KeyValuePair<K, V> WeakSuccessor(K key);
+
+ /// <summary>
+ /// Given a "cut" function from the items of the sorted collection to <code>int</code>
+ /// whose only sign changes when going through items in increasing order
+ /// can be
+ /// <list>
+ /// <item>from positive to zero</item>
+ /// <item>from positive to negative</item>
+ /// <item>from zero to negative</item>
+ /// </list>
+ /// The "cut" function is supplied as the <code>CompareTo</code> method
+ /// of an object <code>c</code> implementing
+ /// <code>IComparable<K></code>.
+ /// A typical example is the case where <code>K</code> is comparable and
+ /// <code>c</code> is itself of type <code>K</code>.
+ /// <para>This method performs a search in the sorted collection for the ranges in which the
+ /// "cut" function is negative, zero respectively positive. If <code>K</code> is comparable
+ /// and <code>c</code> is of type <code>K</code>, this is a safe way (no exceptions thrown)
+ /// to find predecessor and successor of <code>c</code>.
+ /// </para>
+ /// <para> If the supplied cut function does not satisfy the sign-change condition,
+ /// the result of this call is undefined.
+ /// </para>
+ ///
+ /// </summary>
+ /// <param name="cutFunction">The cut function <code>K</code> to <code>int</code>, given
+ /// by the <code>CompareTo</code> method of an object implementing
+ /// <code>IComparable<K></code>.</param>
+ /// <param name="lowEntry">Returns the largest item in the collection, where the
+ /// cut function is positive (if any).</param>
+ /// <param name="lowIsValid">Returns true if the cut function is positive somewhere
+ /// on this collection.</param>
+ /// <param name="highEntry">Returns the least item in the collection, where the
+ /// cut function is negative (if any).</param>
+ /// <param name="highIsValid">Returns true if the cut function is negative somewhere
+ /// on this collection.</param>
+ /// <returns>True if the cut function is zero somewhere
+ /// on this collection.</returns>
+ bool Cut(IComparable<K> cutFunction, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid);
+
+ /// <summary>
+ /// Query this sorted collection for items greater than or equal to a supplied value.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <param name="bot">The lower bound (inclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot);
+
+
+ /// <summary>
+ /// Query this sorted collection for items between two supplied values.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <param name="lowerBound">The lower bound (inclusive).</param>
+ /// <param name="upperBound">The upper bound (exclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K lowerBound, K upperBound);
+
+
+ /// <summary>
+ /// Query this sorted collection for items less than a supplied value.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <param name="top">The upper bound (exclusive).</param>
+ /// <returns>The result directed collection.</returns>
+ IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top);
+
+
+ /// <summary>
+ /// Create a directed collection with the same items as this collection.
+ /// <para>The returned collection is not a copy but a view into the collection.</para>
+ /// <para>The view is fragile in the sense that changes to the underlying collection will
+ /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>
+ /// </summary>
+ /// <returns>The result directed collection.</returns>
+ IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll();
+
+
+ //TODO: remove now that we assume that we can check the sorting order?
+ /// <summary>
+ /// Add all the items from another collection with an enumeration order that
+ /// is increasing in the items.
+ /// </summary>
+ /// <exception cref="ArgumentException"> if the enumerated items turns out
+ /// not to be in increasing order.</exception>
+ /// <param name="items">The collection to add.</param>
+ void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items);
+
+
+ /// <summary>
+ /// Remove all items of this collection above or at a supplied threshold.
+ /// </summary>
+ /// <param name="low">The lower threshold (inclusive).</param>
+ void RemoveRangeFrom(K low);
+
+
+ /// <summary>
+ /// Remove all items of this collection between two supplied thresholds.
+ /// </summary>
+ /// <param name="low">The lower threshold (inclusive).</param>
+ /// <param name="hi">The upper threshold (exclusive).</param>
+ void RemoveRangeFromTo(K low, K hi);
+
+
+ /// <summary>
+ /// Remove all items of this collection below a supplied threshold.
+ /// </summary>
+ /// <param name="hi">The upper threshold (exclusive).</param>
+ void RemoveRangeTo(K hi);
+ }
+
+
+
+ /*******************************************************************/
+ /*/// <summary>
+ /// The type of an item comparer
+ /// <i>Implementations of this interface must asure that the method is self-consistent
+ /// and defines a sorting order on items, or state precise conditions under which this is true.</i>
+ /// <i>Implementations <b>must</b> assure that repeated calls of
+ /// the method to the same (in reference or binary identity sense) arguments
+ /// will return values with the same sign (-1, 0 or +1), or state precise conditions
+ /// under which the user
+ /// can be assured repeated calls will return the same sign.</i>
+ /// <i>Implementations of this interface must always return values from the method
+ /// and never throw exceptions.</i>
+ /// <i>This interface is identical to System.Collections.Generic.IComparer<T></i>
+ /// </summary>
+ public interface IComparer<T>
+ {
+ /// <summary>
+ /// Compare two items with respect to this item comparer
+ /// </summary>
+ /// <param name="item1">First item</param>
+ /// <param name="item2">Second item</param>
+ /// <returns>Positive if item1 is greater than item2, 0 if they are equal, negative if item1 is less than item2</returns>
+ int Compare(T item1, T item2);
+ }
+
+ /// <summary>
+ /// The type of an item equalityComparer.
+ /// <i>Implementations of this interface <b>must</b> assure that the methods are
+ /// consistent, that is, that whenever two items i1 and i2 satisfies that Equals(i1,i2)
+ /// returns true, then GetHashCode returns the same value for i1 and i2.</i>
+ /// <i>Implementations of this interface <b>must</b> assure that repeated calls of
+ /// the methods to the same (in reference or binary identity sense) arguments
+ /// will return the same values, or state precise conditions under which the user
+ /// can be assured repeated calls will return the same values.</i>
+ /// <i>Implementations of this interface must always return values from the methods
+ /// and never throw exceptions.</i>
+ /// <i>This interface is similar in function to System.IKeyComparer<T></i>
+ /// </summary>
+ public interface SCG.IEqualityComparer<T>
+ {
+ /// <summary>
+ /// Get the hash code with respect to this item equalityComparer
+ /// </summary>
+ /// <param name="item">The item</param>
+ /// <returns>The hash code</returns>
+ int GetHashCode(T item);
+
+
+ /// <summary>
+ /// Check if two items are equal with respect to this item equalityComparer
+ /// </summary>
+ /// <param name="item1">first item</param>
+ /// <param name="item2">second item</param>
+ /// <returns>True if equal</returns>
+ bool Equals(T item1, T item2);
+ }*/
+}
projects / mono.git / blobdiff