X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mcs%2Fclass%2FMono.C5%2FC5%2FInterfaces.cs;h=578af96e9769453ca585d59d8e681c3b2395e69a;hb=81bd8db9cf9449aa500910c9fc9003cd77ed5244;hp=46fb2e8ede02de77f39d0c0458cfbbebd5532a23;hpb=53e266903ec6b2d822cf5b0c566f6374df5307a4;p=mono.git diff --git a/mcs/class/Mono.C5/C5/Interfaces.cs b/mcs/class/Mono.C5/C5/Interfaces.cs index 46fb2e8ede0..578af96e976 100644 --- a/mcs/class/Mono.C5/C5/Interfaces.cs +++ b/mcs/class/Mono.C5/C5/Interfaces.cs @@ -1,1887 +1,2059 @@ -#if NET_2_0 -/* - 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 -{ - /// - /// A generic collection, that can be enumerated backwards. - /// - public interface IDirectedEnumerable : SCG.IEnumerable - { - /// - /// 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 - /// foreach (T x in coll.Backwards()) {...} - /// - /// The backwards collection. - IDirectedEnumerable Backwards(); - - - /// - /// Forwards if same, else Backwards - /// - /// The enumeration direction relative to the original collection. - EnumerationDirection Direction { get;} - } - - /// - /// A generic collection that may be enumerated and can answer - /// efficiently how many items it contains. Like IEnumerable<T>, - /// 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. - /// - public interface ICollectionValue : SCG.IEnumerable, IShowable - { - /// - /// A flag bitmap of the events subscribable to by this collection. - /// - /// - EventTypeEnum ListenableEvents { get;} - - /// - /// A flag bitmap of the events currently subscribed to by this collection. - /// - /// - EventTypeEnum ActiveEvents { get;} - - /// - /// The change event. Will be raised for every change operation on the collection. - /// - event CollectionChangedHandler CollectionChanged; - - /// - /// The change event. Will be raised for every clear operation on the collection. - /// - event CollectionClearedHandler CollectionCleared; - - /// - /// The item added event. Will be raised for every individual addition to the collection. - /// - event ItemsAddedHandler ItemsAdded; - - /// - /// The item inserted event. Will be raised for every individual insertion to the collection. - /// - event ItemInsertedHandler ItemInserted; - - /// - /// The item removed event. Will be raised for every individual removal from the collection. - /// - event ItemsRemovedHandler ItemsRemoved; - - /// - /// The item removed at event. Will be raised for every individual removal at from the collection. - /// - event ItemRemovedAtHandler ItemRemovedAt; - - /// - /// - /// - /// True if this collection is empty. - bool IsEmpty { get;} - - /// - /// - /// - /// The number of items in this collection - int Count { get;} - - /// - /// The value is symbolic indicating the type of asymptotic complexity - /// in terms of the size of this collection (worst-case or amortized as - /// relevant). - /// - /// A characterization of the speed of the - /// Count property in this collection. - Speed CountSpeed { get;} - - /// - /// Copy the items of this collection to a contiguous part of an array. - /// - /// The array to copy to - /// The index at which to copy the first item - void CopyTo(T[] array, int index); - - /// - /// Create an array with the items of this collection (in the same order as an - /// enumerator would output them). - /// - /// The array - T[] ToArray(); - - /// - /// Apply a delegate to all items of this collection. - /// - /// The delegate to apply - void Apply(Act action); - - - /// - /// Check if there exists an item that satisfies a - /// specific predicate in this collection. - /// - /// A delegate - /// ( with R == bool) defining the predicate - /// True is such an item exists - bool Exists(Fun predicate); - - /// - /// Check if there exists an item that satisfies a - /// specific predicate in this collection and return the first one in enumeration order. - /// - /// A delegate - /// ( with R == bool) defining the predicate - /// - /// True is such an item exists - bool Find(Fun predicate, out T item); - - - /// - /// Check if all items in this collection satisfies a specific predicate. - /// - /// A delegate - /// ( with R == bool) defining the predicate - /// True if all items satisfies the predicate - bool All(Fun predicate); - - /// - /// Choose some item of this collection. - /// Implementations must assure that the item - /// returned may be efficiently removed. - /// 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: - /// coll.Choose() == coll.Choose() - /// - /// if collection is empty. - /// - T Choose(); - - /// - /// Create an enumerable, enumerating the items of this collection that satisfies - /// a certain condition. - /// - /// The T->bool filter delegate defining the condition - /// The filtered enumerable - SCG.IEnumerable Filter(Fun filter); - } - - - - /// - /// A sized generic collection, that can be enumerated backwards. - /// - public interface IDirectedCollectionValue : ICollectionValue, IDirectedEnumerable - { - /// - /// 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 - /// foreach (T x in coll.Backwards()) {...} - /// - /// The backwards collection. - new IDirectedCollectionValue Backwards(); - - /// - /// Check if there exists an item that satisfies a - /// specific predicate in this collection and return the first one in enumeration order. - /// - /// A delegate - /// ( with R == bool) defining the predicate - /// - /// True is such an item exists - bool FindLast(Fun predicate, out T item); - } - - - /// - /// 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, - /// and . - /// - public interface IExtensible : ICollectionValue, ICloneable - { - /// - /// If true any call of an updating operation will throw an - /// ReadOnlyCollectionException - /// - /// True if this collection is read-only. - bool IsReadOnly { get;} - - //TODO: wonder where the right position of this is - /// - /// - /// - /// False if this collection has set semantics, true if bag semantics. - bool AllowsDuplicates { get;} - - //TODO: wonder where the right position of this is. And the semantics. - /// - /// (Here should be a discussion of the role of equalityComparers. Any ). - /// - /// 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. - SCG.IEqualityComparer EqualityComparer { get;} - - //ItemEqualityTypeEnum ItemEqualityType {get ;} - - //TODO: find a good name - - /// - /// By convention this is true for any collection with set semantics. - /// - /// True if only one representative of a group of equal items - /// is kept in the collection together with the total count. - bool DuplicatesByCounting { get;} - - /// - /// 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. - /// - /// The item to add. - /// True if item was added. - bool Add(T item); - - /// - /// 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. - /// - /// The type of items to add - /// The items to add - void AddAll(SCG.IEnumerable items) where U : T; - - //void Clear(); // for priority queue - //int Count why not? - /// - /// Check the integrity of the internal data structures of this collection. - /// This is only relevant for developers of the library - /// - /// True if check was passed. - bool Check(); - } - - /// - /// The simplest interface of a main stream generic collection - /// with lookup, insertion and removal operations. - /// - public interface ICollection : IExtensible - { - //This is somewhat similar to the RandomAccess marker itf in java - /// - /// The value is symbolic indicating the type of asymptotic complexity - /// in terms of the size of this collection (worst-case or amortized as - /// relevant). - /// See for the set of symbols. - /// - /// A characterization of the speed of lookup operations - /// (Contains() etc.) of the implementation of this collection. - Speed ContainsSpeed { get;} - - /// - /// The unordered collection hashcode is defined as the sum of - /// h(hashcode(item)) over the items - /// of the collection, where the function h is a function from - /// int to int of the form t -> (a0*t+b0)^(a1*t+b1)^(a2*t+b2), where - /// the ax and bx are the same for all collection classes. - /// The current implementation uses fixed values for the ax and bx, - /// specified as constants in the code. - /// - /// The unordered hashcode of this collection. - int GetUnsequencedHashCode(); - - - /// - /// 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. - /// - /// The collection to compare to. - /// True if this collection and that contains the same items. - bool UnsequencedEquals(ICollection otherCollection); - - - /// - /// Check if this collection contains (an item equivalent to according to the - /// itemequalityComparer) a particular value. - /// - /// The value to check for. - /// True if the items is in this collection. - bool Contains(T item); - - - /// - /// 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. - /// - /// The value to count. - /// The number of copies found. - int ContainsCount(T item); - - /// - /// - /// - /// - ICollectionValue UniqueItems(); - - /// - /// - /// - /// - ICollectionValue> ItemMultiplicities(); - - /// - /// Check whether this collection contains all the values in another collection. - /// If this collection has bag semantics (AllowsDuplicates==true) - /// the check is made with respect to multiplicities, else multiplicities - /// are not taken into account. - /// - /// The - /// - /// True if all values in itemsis in this collection. - bool ContainsAll(SCG.IEnumerable items) where U : T; - - - /// - /// 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. - /// - /// The value to look for. - /// True if the items is in this collection. - bool Find(ref T item); - - - //This should probably just be bool Add(ref T item); !!! - /// - /// 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. - /// - /// The value to look for. - /// True if the item was found (hence not added). - bool FindOrAdd(ref T item); - - - /// - /// 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. - /// - /// Value to update. - /// True if the item was found and hence updated. - bool Update(T item); - - /// - /// 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. - /// - /// Value to update. - /// On output the olditem, if found. - /// True if the item was found and hence updated. - bool Update(T item, out T olditem); - - - /// - /// 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. - /// - /// Value to add or update. - /// True if the item was found and updated (hence not added). - bool UpdateOrAdd(T item); - - - /// - /// 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. - /// - /// Value to add or update. - /// On output the olditem, if found. - /// True if the item was found and updated (hence not added). - bool UpdateOrAdd(T item, out T olditem); - - /// - /// Remove a particular item from this collection. If the collection has bag - /// semantics only one copy equivalent to the supplied item is removed. - /// - /// The value to remove. - /// True if the item was found (and removed). - bool Remove(T item); - - - /// - /// 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. - /// - /// The value to remove. - /// The value removed if any. - /// True if the item was found (and removed). - bool Remove(T item, out T removeditem); - - - /// - /// Remove all items equivalent to a given value. - /// - /// The value to remove. - void RemoveAllCopies(T item); - - - /// - /// Remove all items in another collection from this one. If this collection - /// has bag semantics, take multiplicities into account. - /// - /// - /// The items to remove. - void RemoveAll(SCG.IEnumerable items) where U : T; - - //void RemoveAll(Fun predicate); - - /// - /// Remove all items from this collection. - /// - void Clear(); - - - /// - /// Remove all items not in some other collection from this one. If this collection - /// has bag semantics, take multiplicities into account. - /// - /// - /// The items to retain. - void RetainAll(SCG.IEnumerable items) where U : T; - - //void RetainAll(Fun predicate); - //IDictionary UniqueItems() - } - - - - /// - /// An editable collection maintaining a definite sequence order of the items. - /// - /// 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. - /// This interface is usually implemented by explicit interface implementation, - /// not as ordinary virtual methods. - /// - public interface ISequenced : ICollection, IDirectedCollectionValue - { - /// - /// The hashcode is defined as h(...h(h(h(x1),x2),x3),...,xn) for - /// h(a,b)=CONSTANT*a+b and the x's the hash codes of the items of - /// this collection. - /// - /// The sequence order hashcode of this collection. - int GetSequencedHashCode(); - - - /// - /// Compare this sequenced collection to another one in sequence order. - /// - /// The sequenced collection to compare to. - /// True if this collection and that contains equal (according to - /// this collection's itemequalityComparer) in the same sequence order. - bool SequencedEquals(ISequenced otherCollection); - } - - - - /// - /// A sequenced collection, where indices of items in the order are maintained - /// - public interface IIndexed : ISequenced - { - /// - /// - /// if index is negative or - /// >= the size of the collection. - /// The index'th item of this list. - /// the index to lookup - T this[int index] { get;} - - /// - /// - /// - /// - Speed IndexingSpeed { get;} - - /// - /// - /// - /// The directed collection of items in a specific index interval. - /// The low index of the interval (inclusive). - /// The size of the range. - IDirectedCollectionValue this[int start, int count] { get;} - - - /// - /// Searches for an item in the list going forwards from the start. - /// - /// Item to search for. - /// Index of item from start. A negative number if item not found, - /// namely the two-complement of the index at which the Add operation would put the item. - int IndexOf(T item); - - - /// - /// Searches for an item in the list going backwards from the end. - /// - /// Item to search for. - /// 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. - int LastIndexOf(T item); - - /// - /// Check if there exists an item that satisfies a - /// specific predicate in this collection and return the index of the first one. - /// - /// A delegate - /// ( with R == bool) defining the predicate - /// the index, if found, a negative value else - int FindIndex(Fun predicate); - - /// - /// Check if there exists an item that satisfies a - /// specific predicate in this collection and return the index of the last one. - /// - /// A delegate - /// ( with R == bool) defining the predicate - /// the index, if found, a negative value else - int FindLastIndex(Fun predicate); - - - /// - /// Remove the item at a specific position of the list. - /// - /// if index is negative or - /// >= the size of the collection. - /// The index of the item to remove. - /// The removed item. - T RemoveAt(int index); - - - /// - /// Remove all items in an index interval. - /// - /// if start or count - /// is negative or start+count > the size of the collection. - /// The index of the first item to remove. - /// The number of items to remove. - void RemoveInterval(int start, int count); - } - - //TODO: decide if this should extend ICollection - /// - /// The interface describing the operations of a LIFO stack data structure. - /// - /// The item type - public interface IStack : IDirectedCollectionValue - { - /// - /// - /// - /// - bool AllowsDuplicates { get;} - /// - /// Get the index'th element of the stack. The bottom of the stack has index 0. - /// - /// - /// - T this[int index] { get;} - /// - /// Push an item to the top of the stack. - /// - /// The item - void Push(T item); - /// - /// Pop the item at the top of the stack from the stack. - /// - /// The popped item. - T Pop(); - } - - /// - /// The interface describing the operations of a FIFO queue data structure. - /// - /// The item type - public interface IQueue : IDirectedCollectionValue - { - /// - /// - /// - /// - bool AllowsDuplicates { get;} - /// - /// Get the index'th element of the queue. The front of the queue has index 0. - /// - /// - /// - T this[int index] { get;} - /// - /// Enqueue an item at the back of the queue. - /// - /// The item - void Enqueue(T item); - /// - /// Dequeue an item from the front of the queue. - /// - /// The item - T Dequeue(); - } - - - /// - /// 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! - /// - public interface IList : IIndexed, IDisposable - { - /// - /// - /// if this list is empty. - /// The first item in this list. - T First { get;} - - /// - /// - /// if this list is empty. - /// The last item in this list. - T Last { get;} - - /// - /// Since Add(T item) always add at the end of the list, - /// this describes if list has FIFO or LIFO semantics. - /// - /// True if the Remove() operation removes from the - /// start of the list, false if it removes from the end. - bool FIFO { get; set;} - - /// - /// - /// - bool IsFixedSize { get; } - - /// - /// On this list, this indexer is read/write. - /// - /// if index is negative or - /// >= the size of the collection. - /// The index'th item of this list. - /// The index of the item to fetch or store. - new T this[int index] { get; set;} - - /// - /// Insert an item at a specific index location in this list. - /// - /// if index is negative or - /// > the size of the collection. - /// if the list has - /// AllowsDuplicates==false and the item is - /// already in the list. - /// The index at which to insert. - /// The item to insert. - void Insert(int index, T item); - - /// - /// Insert an item at the end of a compatible view, used as a pointer. - /// The pointer must be a view on the same list as - /// this and the endpoitn of pointer must be - /// a valid insertion point of this - /// - /// If pointer - /// is not a view on the same list as this - /// ?????? if the endpoint of - /// pointer is not inside this - /// if the list has - /// AllowsDuplicates==false and the item is - /// already in the list. - /// - /// - void Insert(IList pointer, T item); - - /// - /// Insert an item at the front of this list. - /// if the list has - /// AllowsDuplicates==false and the item is - /// already in the list. - /// - /// The item to insert. - void InsertFirst(T item); - - /// - /// Insert an item at the back of this list. - /// if the list has - /// AllowsDuplicates==false and the item is - /// already in the list. - /// - /// The item to insert. - void InsertLast(T item); - - /// - /// Insert into this list all items from an enumerable collection starting - /// at a particular index. - /// - /// if index is negative or - /// > the size of the collection. - /// if the list has - /// AllowsDuplicates==false and one of the items to insert is - /// already in the list. - /// Index to start inserting at - /// Items to insert - /// - void InsertAll(int index, SCG.IEnumerable items) where U : T; - - /// - /// Create a new list consisting of the items of this list satisfying a - /// certain predicate. - /// - /// The filter delegate defining the predicate. - /// The new list. - IList FindAll(Fun filter); - - /// - /// 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. - /// - /// The type of items of the new list - /// The delegate defining the map. - /// The new list. - IList Map(Fun mapper); - - /// - /// 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. - /// - /// The type of items of the new list - /// The delegate defining the map. - /// The equalityComparer to use for the new list - /// The new list. - IList Map(Fun mapper, SCG.IEqualityComparer equalityComparer); - - /// - /// Remove one item from the list: from the front if FIFO - /// is true, else from the back. - /// if this list is empty. - /// - /// The removed item. - T Remove(); - - /// - /// Remove one item from the front of the list. - /// if this list is empty. - /// - /// The removed item. - T RemoveFirst(); - - /// - /// Remove one item from the back of the list. - /// if this list is empty. - /// - /// The removed item. - T RemoveLast(); - - /// - /// Create a list view on this list. - /// if the view would not fit into - /// this list. - /// - /// The index in this list of the start of the view. - /// The size of the view. - /// The new list view. - IList View(int start, int count); - - /// - /// Create a list view on this list containing the (first) occurrence of a particular item. - /// if the item is not in this list. - /// - /// The item to find. - /// The new list view. - IList ViewOf(T item); - - /// - /// Create a list view on this list containing the last occurrence of a particular item. - /// if the item is not in this list. - /// - /// The item to find. - /// The new list view. - IList LastViewOf(T item); - - /// - /// Null if this list is not a view. - /// - /// Underlying list for view. - IList Underlying { get;} - - /// - /// - /// Offset for this list view or 0 for an underlying list. - int Offset { get;} - - /// - /// - /// - /// - bool IsValid { get;} - - /// - /// Slide this list view along the underlying list. - /// - /// if this list is not a view. - /// if the operation - /// would bring either end of the view outside the underlying list. - /// The signed amount to slide: positive to slide - /// towards the end. - IList Slide(int offset); - - /// - /// Slide this list view along the underlying list, changing its size. - /// - /// - /// if this list is not a view. - /// if the operation - /// would bring either end of the view outside the underlying list. - /// The signed amount to slide: positive to slide - /// towards the end. - /// The new size of the view. - IList Slide(int offset, int size); - - /// - /// - /// - /// - /// - bool TrySlide(int offset); - - /// - /// - /// - /// - /// - /// - bool TrySlide(int offset, int size); - - /// - /// - /// Returns null if otherView is strictly to the left of this view - /// - /// - /// If otherView does not have the same underlying list as this - /// If otherView is strictly to the left of this view - /// - IList Span(IList otherView); - - /// - /// Reverse the list so the items are in the opposite sequence order. - /// - void Reverse(); - - /// - /// Check if this list is sorted according to the default sorting order - /// for the item type T, as defined by the class - /// - /// if T is not comparable - /// True if the list is sorted, else false. - bool IsSorted(); - - /// - /// Check if this list is sorted according to a specific sorting order. - /// - /// The comparer defining the sorting order. - /// True if the list is sorted, else false. - bool IsSorted(SCG.IComparer comparer); - - /// - /// Sort the items of the list according to the default sorting order - /// for the item type T, as defined by the class - /// - /// if T is not comparable - void Sort(); - - /// - /// Sort the items of the list according to a specified sorting order. - /// 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. - /// - /// - /// The comparer defining the sorting order. - void Sort(SCG.IComparer comparer); - - - /// - /// Randomly shuffle the items of this list. - /// - void Shuffle(); - - - /// - /// Shuffle the items of this list according to a specific random source. - /// - /// The random source. - void Shuffle(Random rnd); - } - - - /// - /// The base type of a priority queue handle - /// - /// - public interface IPriorityQueueHandle - { - //TODO: make abstract and prepare for double dispatch: - //public virtual bool Delete(IPriorityQueue q) { throw new InvalidFooException();} - //bool Replace(T item); - } - - - /// - /// A generic collection of items prioritized by a comparison (order) relation. - /// Supports adding items and reporting or removing extremal elements. - /// - /// - /// - /// 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. - /// - public interface IPriorityQueue : IExtensible - { - /// - /// Find the current least item of this priority queue. - /// - /// The least item. - T FindMin(); - - - /// - /// Remove the least item from this priority queue. - /// - /// The removed item. - T DeleteMin(); - - - /// - /// Find the current largest item of this priority queue. - /// - /// The largest item. - T FindMax(); - - - /// - /// Remove the largest item from this priority queue. - /// - /// The removed item. - T DeleteMax(); - - /// - /// The comparer object supplied at creation time for this collection - /// - /// The comparer - SCG.IComparer Comparer { get;} - /// - /// Get or set the item corresponding to a handle. Throws exceptions on - /// invalid handles. - /// - /// - /// - T this[IPriorityQueueHandle handle] { get; set;} - - /// - /// Check if the entry corresponding to a handle is in the priority queue. - /// - /// - /// - /// - bool Find(IPriorityQueueHandle handle, out T item); - - /// - /// Add an item to the priority queue, receiving a - /// handle for the item in the queue, - /// or reusing an existing unused 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. - /// - /// - bool Add(ref IPriorityQueueHandle handle, T item); - - /// - /// Delete an item with a handle from a priority queue - /// - /// The handle for the item. The handle will be invalidated, but reusable. - /// The deleted item - T Delete(IPriorityQueueHandle handle); - - /// - /// Replace an item with a handle in a priority queue with a new item. - /// Typically used for changing the priority of some queued object. - /// - /// The handle for the old item - /// The new item - /// The old item - T Replace(IPriorityQueueHandle handle, T item); - - /// - /// Find the current least item of this priority queue. - /// - /// On return: the handle of the item. - /// The least item. - T FindMin(out IPriorityQueueHandle handle); - - /// - /// Find the current largest item of this priority queue. - /// - /// On return: the handle of the item. - /// The largest item. - - T FindMax(out IPriorityQueueHandle handle); - - /// - /// Remove the least item from this priority queue. - /// - /// On return: the handle of the removed item. - /// The removed item. - - T DeleteMin(out IPriorityQueueHandle handle); - - /// - /// Remove the largest item from this priority queue. - /// - /// On return: the handle of the removed item. - /// The removed item. - T DeleteMax(out IPriorityQueueHandle handle); - } - - - - /// - /// 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. - /// - /// The sorting order is defined by a comparer, an object of type IComparer<T> - /// (). 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, . - /// - /// The comparer of the sorted collection is available as the Comparer property - /// (). - /// - /// The methods are grouped according to - /// - /// Extrema: report or report and delete an extremal item. This is reminiscent of simplified priority queues. - /// Nearest neighbor: report predecessor or successor in the collection of an item. Cut belongs to this group. - /// Range: report a view of a range of elements or remove all elements in a range. - /// AddSorted: add a collection of items known to be sorted in the same order (should be faster) (to be removed?) - /// - /// - /// - /// Since this interface extends ISequenced<T>, sorted collections will also have an - /// item 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, - /// ( and ) - /// - /// 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. - /// - public interface ISorted : ISequenced - { - /// - /// Find the current least item of this sorted collection. - /// - /// if the collection is empty. - /// The least item. - T FindMin(); - - - /// - /// Remove the least item from this sorted collection. - /// - /// if the collection is empty. - /// The removed item. - T DeleteMin(); - - - /// - /// Find the current largest item of this sorted collection. - /// - /// if the collection is empty. - /// The largest item. - T FindMax(); - - - /// - /// Remove the largest item from this sorted collection. - /// - /// if the collection is empty. - /// The removed item. - T DeleteMax(); - - /// - /// The comparer object supplied at creation time for this sorted collection. - /// - /// The comparer - SCG.IComparer Comparer { get;} - - /// - /// 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. - /// - /// if no such element exists (the - /// supplied value is less than or equal to the minimum of this collection.) - /// The item to find the predecessor for. - /// The predecessor. - T Predecessor(T item); - - - /// - /// 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. - /// - /// if no such element exists (the - /// supplied value is greater than or equal to the maximum of this collection.) - /// The item to find the successor for. - /// The successor. - T Successor(T item); - - - /// - /// 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. - /// - /// if no such element exists (the - /// supplied value is less than the minimum of this collection.) - /// The item to find the weak predecessor for. - /// The weak predecessor. - T WeakPredecessor(T item); - - - /// - /// 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. - /// - /// if no such element exists (the - /// supplied value is greater than the maximum of this collection.) - ///The item to find the weak successor for. - /// The weak successor. - T WeakSuccessor(T item); - - - /// - /// Given a "cut" function from the items of the sorted collection to int - /// whose only sign changes when going through items in increasing order - /// can be - /// - /// from positive to zero - /// from positive to negative - /// from zero to negative - /// - /// The "cut" function is supplied as the CompareTo method - /// of an object c implementing - /// IComparable<T>. - /// A typical example is the case where T is comparable and - /// cutFunction is itself of type T. - /// This method performs a search in the sorted collection for the ranges in which the - /// "cut" function is negative, zero respectively positive. If T is comparable - /// and c is of type T, this is a safe way (no exceptions thrown) - /// to find predecessor and successor of c. - /// - /// If the supplied cut function does not satisfy the sign-change condition, - /// the result of this call is undefined. - /// - /// - /// - /// The cut function T to int, given - /// by the CompareTo method of an object implementing - /// IComparable<T>. - /// Returns the largest item in the collection, where the - /// cut function is positive (if any). - /// Returns true if the cut function is positive somewhere - /// on this collection. - /// Returns the least item in the collection, where the - /// cut function is negative (if any). - /// Returns true if the cut function is negative somewhere - /// on this collection. - /// True if the cut function is zero somewhere - /// on this collection. - bool Cut(IComparable cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid); - - - /// - /// Query this sorted collection for items greater than or equal to a supplied value. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The lower bound (inclusive). - /// The result directed collection. - IDirectedEnumerable RangeFrom(T bot); - - - /// - /// Query this sorted collection for items between two supplied values. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The lower bound (inclusive). - /// The upper bound (exclusive). - /// The result directed collection. - IDirectedEnumerable RangeFromTo(T bot, T top); - - - /// - /// Query this sorted collection for items less than a supplied value. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The upper bound (exclusive). - /// The result directed collection. - IDirectedEnumerable RangeTo(T top); - - - /// - /// Create a directed collection with the same items as this collection. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The result directed collection. - IDirectedCollectionValue RangeAll(); - - - //TODO: remove now that we assume that we can check the sorting order? - /// - /// Add all the items from another collection with an enumeration order that - /// is increasing in the items. - /// - /// if the enumerated items turns out - /// not to be in increasing order. - /// The collection to add. - /// - void AddSorted(SCG.IEnumerable items) where U : T; - - - /// - /// Remove all items of this collection above or at a supplied threshold. - /// - /// The lower threshold (inclusive). - void RemoveRangeFrom(T low); - - - /// - /// Remove all items of this collection between two supplied thresholds. - /// - /// The lower threshold (inclusive). - /// The upper threshold (exclusive). - void RemoveRangeFromTo(T low, T hi); - - - /// - /// Remove all items of this collection below a supplied threshold. - /// - /// The upper threshold (exclusive). - void RemoveRangeTo(T hi); - } - - - - /// - /// A collection where items are maintained in sorted order together - /// with their indexes in that order. - /// - public interface IIndexedSorted : ISorted, IIndexed - { - /// - /// Determine the number of items at or above a supplied threshold. - /// - /// The lower bound (inclusive) - /// The number of matcing items. - int CountFrom(T bot); - - - /// - /// Determine the number of items between two supplied thresholds. - /// - /// The lower bound (inclusive) - /// The upper bound (exclusive) - /// The number of matcing items. - int CountFromTo(T bot, T top); - - - /// - /// Determine the number of items below a supplied threshold. - /// - /// The upper bound (exclusive) - /// The number of matcing items. - int CountTo(T top); - - - /// - /// Query this sorted collection for items greater than or equal to a supplied value. - /// - /// The lower bound (inclusive). - /// The result directed collection. - new IDirectedCollectionValue RangeFrom(T bot); - - - /// - /// Query this sorted collection for items between two supplied values. - /// - /// The lower bound (inclusive). - /// The upper bound (exclusive). - /// The result directed collection. - new IDirectedCollectionValue RangeFromTo(T bot, T top); - - - /// - /// Query this sorted collection for items less than a supplied value. - /// - /// The upper bound (exclusive). - /// The result directed collection. - new IDirectedCollectionValue RangeTo(T top); - - - /// - /// Create a new indexed sorted collection consisting of the items of this - /// indexed sorted collection satisfying a certain predicate. - /// - /// The filter delegate defining the predicate. - /// The new indexed sorted collection. - IIndexedSorted FindAll(Fun predicate); - - - /// - /// Create a new indexed sorted collection consisting of the results of - /// mapping all items of this list. - /// if the map is not increasing over - /// the items of this collection (with respect to the two given comparison - /// relations). - /// - /// The delegate definging the map. - /// The comparion relation to use for the result. - /// The new sorted collection. - IIndexedSorted Map(Fun mapper, SCG.IComparer comparer); - } - - - - /// - /// The type of a sorted collection with persistence - /// - public interface IPersistentSorted : ISorted, IDisposable - { - /// - /// Make a (read-only) snap shot of this collection. - /// - /// The snap shot. - ISorted Snapshot(); - } - - - - /*************************************************************************/ - /// - /// A dictionary with keys of type K and values of type V. Equivalent to a - /// finite partial map from K to V. - /// - public interface IDictionary : ICollectionValue>, ICloneable - { - /// - /// The key equalityComparer. - /// - /// - SCG.IEqualityComparer EqualityComparer { get;} - - /// - /// Indexer for dictionary. - /// - /// if no entry is found. - /// The value corresponding to the key - V this[K key] { get; set;} - - - /// - /// - /// - /// True if dictionary is read-only - bool IsReadOnly { get;} - - - /// - /// - /// - /// A collection containg the all the keys of the dictionary - ICollectionValue Keys { get;} - - - /// - /// - /// - /// A collection containing all the values of the dictionary - ICollectionValue Values { get;} - - /// - /// - /// - /// A delegate of type defining the partial function from K to V give by the dictionary. - Fun Fun { get; } - - - //TODO: resolve inconsistency: Add thows exception if key already there, AddAll ignores keys already There? - /// - /// Add a new (key, value) pair (a mapping) to the dictionary. - /// - /// if there already is an entry with the same key. > - /// Key to add - /// Value to add - void Add(K key, V val); - - /// - /// Add the entries from a collection of pairs to this dictionary. - /// - /// - /// If the input contains duplicate keys or a key already present in this dictionary. - /// - void AddAll(SCG.IEnumerable> entries) - where U : K - where W : V - ; - - /// - /// The value is symbolic indicating the type of asymptotic complexity - /// in terms of the size of this collection (worst-case or amortized as - /// relevant). - /// See for the set of symbols. - /// - /// A characterization of the speed of lookup operations - /// (Contains() etc.) of the implementation of this dictionary. - Speed ContainsSpeed { get;} - - /// - /// Check whether this collection contains all the values in another collection. - /// If this collection has bag semantics (AllowsDuplicates==true) - /// the check is made with respect to multiplicities, else multiplicities - /// are not taken into account. - /// - /// The - /// True if all values in itemsis in this collection. - bool ContainsAll(SCG.IEnumerable items) where H : K; - - /// - /// Remove an entry with a given key from the dictionary - /// - /// The key of the entry to remove - /// True if an entry was found (and removed) - bool Remove(K key); - - - /// - /// Remove an entry with a given key from the dictionary and report its value. - /// - /// The key of the entry to remove - /// On exit, the value of the removed entry - /// True if an entry was found (and removed) - bool Remove(K key, out V val); - - - /// - /// Remove all entries from the dictionary - /// - void Clear(); - - - /// - /// Check if there is an entry with a specified key - /// - /// The key to look for - /// True if key was found - bool Contains(K key); - - - /// - /// 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]". - /// - /// The key to look for - /// On exit, the value of the entry - /// True if key was found - bool Find(K key, out V val); - - /// - /// 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]". - /// - /// The key to look for - /// On exit, the value of the entry - /// True if key was found - bool Find(ref K key, out V val); - - - /// - /// 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". - /// - /// The key to look for - /// The new value - /// True if key was found - bool Update(K key, V val); //no-adding - - - /// - /// 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. - /// - /// The key to look for - /// The new value - /// The old value if any - /// True if key was found - bool Update(K key, V val, out V oldval); //no-adding - - /// - /// 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. - /// - /// The key to look for - /// On entry the value to add if the key is not found. - /// On exit the value found if any. - /// True if key was found - bool FindOrAdd(K key, ref V val); //mixture - - - /// - /// 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. - /// - /// The key to look for - /// The value to add or replace with. - /// True if key was found and value updated. - bool UpdateOrAdd(K key, V val); - - - /// - /// 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. - /// - /// The key to look for - /// The value to add or replace with. - /// The old value if any - /// True if key was found and value updated. - bool UpdateOrAdd(K key, V val, out V oldval); - - - /// - /// Check the integrity of the internal data structures of this dictionary. - /// Only avaliable in DEBUG builds??? - /// - /// True if check does not fail. - bool Check(); - } - - - - /// - /// A dictionary with sorted keys. - /// - public interface ISortedDictionary : IDictionary - { - /// - /// - /// - /// - new ISorted Keys { get;} - - /// - /// Find the current least item of this sorted collection. - /// - /// if the collection is empty. - /// The least item. - KeyValuePair FindMin(); - - - /// - /// Remove the least item from this sorted collection. - /// - /// if the collection is empty. - /// The removed item. - KeyValuePair DeleteMin(); - - - /// - /// Find the current largest item of this sorted collection. - /// - /// if the collection is empty. - /// The largest item. - KeyValuePair FindMax(); - - - /// - /// Remove the largest item from this sorted collection. - /// - /// if the collection is empty. - /// The removed item. - KeyValuePair DeleteMax(); - - /// - /// The key comparer used by this dictionary. - /// - /// - SCG.IComparer Comparer { get;} - - /// - /// Find the entry with the largest key less than a given key. - /// - /// if there is no such entry. - /// The key to compare to - /// The entry - KeyValuePair Predecessor(K key); - - - /// - /// Find the entry with the least key greater than a given key. - /// - /// if there is no such entry. - /// The key to compare to - /// The entry - KeyValuePair Successor(K key); - - - /// - /// Find the entry with the largest key less than or equal to a given key. - /// - /// if there is no such entry. - /// The key to compare to - /// The entry - KeyValuePair WeakPredecessor(K key); - - - /// - /// Find the entry with the least key greater than or equal to a given key. - /// - /// if there is no such entry. - /// The key to compare to - /// The entry - KeyValuePair WeakSuccessor(K key); - - /// - /// Given a "cut" function from the items of the sorted collection to int - /// whose only sign changes when going through items in increasing order - /// can be - /// - /// from positive to zero - /// from positive to negative - /// from zero to negative - /// - /// The "cut" function is supplied as the CompareTo method - /// of an object c implementing - /// IComparable<K>. - /// A typical example is the case where K is comparable and - /// c is itself of type K. - /// This method performs a search in the sorted collection for the ranges in which the - /// "cut" function is negative, zero respectively positive. If K is comparable - /// and c is of type K, this is a safe way (no exceptions thrown) - /// to find predecessor and successor of c. - /// - /// If the supplied cut function does not satisfy the sign-change condition, - /// the result of this call is undefined. - /// - /// - /// - /// The cut function K to int, given - /// by the CompareTo method of an object implementing - /// IComparable<K>. - /// Returns the largest item in the collection, where the - /// cut function is positive (if any). - /// Returns true if the cut function is positive somewhere - /// on this collection. - /// Returns the least item in the collection, where the - /// cut function is negative (if any). - /// Returns true if the cut function is negative somewhere - /// on this collection. - /// True if the cut function is zero somewhere - /// on this collection. - bool Cut(IComparable cutFunction, out KeyValuePair lowEntry, out bool lowIsValid, out KeyValuePair highEntry, out bool highIsValid); - - /// - /// Query this sorted collection for items greater than or equal to a supplied value. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The lower bound (inclusive). - /// The result directed collection. - IDirectedEnumerable> RangeFrom(K bot); - - - /// - /// Query this sorted collection for items between two supplied values. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The lower bound (inclusive). - /// The upper bound (exclusive). - /// The result directed collection. - IDirectedEnumerable> RangeFromTo(K lowerBound, K upperBound); - - - /// - /// Query this sorted collection for items less than a supplied value. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The upper bound (exclusive). - /// The result directed collection. - IDirectedEnumerable> RangeTo(K top); - - - /// - /// Create a directed collection with the same items as this collection. - /// The returned collection is not a copy but a view into the collection. - /// 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. - /// - /// The result directed collection. - IDirectedCollectionValue> RangeAll(); - - - //TODO: remove now that we assume that we can check the sorting order? - /// - /// Add all the items from another collection with an enumeration order that - /// is increasing in the items. - /// - /// if the enumerated items turns out - /// not to be in increasing order. - /// The collection to add. - void AddSorted(SCG.IEnumerable> items); - - - /// - /// Remove all items of this collection above or at a supplied threshold. - /// - /// The lower threshold (inclusive). - void RemoveRangeFrom(K low); - - - /// - /// Remove all items of this collection between two supplied thresholds. - /// - /// The lower threshold (inclusive). - /// The upper threshold (exclusive). - void RemoveRangeFromTo(K low, K hi); - - - /// - /// Remove all items of this collection below a supplied threshold. - /// - /// The upper threshold (exclusive). - void RemoveRangeTo(K hi); - } - - - - /*******************************************************************/ - /*/// - /// The type of an item comparer - /// 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. - /// Implementations must 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. - /// Implementations of this interface must always return values from the method - /// and never throw exceptions. - /// This interface is identical to System.Collections.Generic.IComparer<T> - /// - public interface IComparer - { - /// - /// Compare two items with respect to this item comparer - /// - /// First item - /// Second item - /// Positive if item1 is greater than item2, 0 if they are equal, negative if item1 is less than item2 - int Compare(T item1, T item2); - } - - /// - /// The type of an item equalityComparer. - /// Implementations of this interface must 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. - /// Implementations of this interface must 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. - /// Implementations of this interface must always return values from the methods - /// and never throw exceptions. - /// This interface is similar in function to System.IKeyComparer<T> - /// - public interface SCG.IEqualityComparer - { - /// - /// Get the hash code with respect to this item equalityComparer - /// - /// The item - /// The hash code - int GetHashCode(T item); - - - /// - /// Check if two items are equal with respect to this item equalityComparer - /// - /// first item - /// second item - /// True if equal - bool Equals(T item1, T item2); - }*/ -} - -#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 +{ + /// + /// A generic collection, that can be enumerated backwards. + /// + public interface IDirectedEnumerable : SCG.IEnumerable + { + /// + /// 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 + /// foreach (T x in coll.Backwards()) {...} + /// + /// The backwards collection. + IDirectedEnumerable Backwards(); + + + /// + /// Forwards if same, else Backwards + /// + /// The enumeration direction relative to the original collection. + EnumerationDirection Direction { get;} + } + + /// + /// A generic collection that may be enumerated and can answer + /// efficiently how many items it contains. Like IEnumerable<T>, + /// 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. + /// + public interface ICollectionValue : SCG.IEnumerable, IShowable + { + /// + /// A flag bitmap of the events subscribable to by this collection. + /// + /// + EventTypeEnum ListenableEvents { get;} + + /// + /// A flag bitmap of the events currently subscribed to by this collection. + /// + /// + EventTypeEnum ActiveEvents { get;} + + /// + /// The change event. Will be raised for every change operation on the collection. + /// + event CollectionChangedHandler CollectionChanged; + + /// + /// The change event. Will be raised for every clear operation on the collection. + /// + event CollectionClearedHandler CollectionCleared; + + /// + /// The item added event. Will be raised for every individual addition to the collection. + /// + event ItemsAddedHandler ItemsAdded; + + /// + /// The item inserted event. Will be raised for every individual insertion to the collection. + /// + event ItemInsertedHandler ItemInserted; + + /// + /// The item removed event. Will be raised for every individual removal from the collection. + /// + event ItemsRemovedHandler ItemsRemoved; + + /// + /// The item removed at event. Will be raised for every individual removal at from the collection. + /// + event ItemRemovedAtHandler ItemRemovedAt; + + /// + /// + /// + /// True if this collection is empty. + bool IsEmpty { get;} + + /// + /// + /// The number of items in this collection + int Count { get;} + + /// + /// The value is symbolic indicating the type of asymptotic complexity + /// in terms of the size of this collection (worst-case or amortized as + /// relevant). + /// + /// A characterization of the speed of the + /// Count property in this collection. + Speed CountSpeed { get;} + + /// + /// Copy the items of this collection to a contiguous part of an array. + /// + /// The array to copy to + /// The index at which to copy the first item + void CopyTo(T[] array, int index); + + /// + /// Create an array with the items of this collection (in the same order as an + /// enumerator would output them). + /// + /// The array + T[] ToArray(); + + /// + /// Apply a delegate to all items of this collection. + /// + /// The delegate to apply + void Apply(Act action); + + + /// + /// Check if there exists an item that satisfies a + /// specific predicate in this collection. + /// + /// A delegate + /// ( with R == bool) defining the predicate + /// True is such an item exists + bool Exists(Fun predicate); + + /// + /// Check if there exists an item that satisfies a + /// specific predicate in this collection and return the first one in enumeration order. + /// + /// A delegate + /// ( with R == bool) defining the predicate + /// + /// True is such an item exists + bool Find(Fun predicate, out T item); + + + /// + /// Check if all items in this collection satisfies a specific predicate. + /// + /// A delegate + /// ( with R == bool) defining the predicate + /// True if all items satisfies the predicate + bool All(Fun predicate); + + /// + /// Choose some item of this collection. + /// Implementations must assure that the item + /// returned may be efficiently removed. + /// 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: + /// coll.Choose() == coll.Choose() + /// + /// if collection is empty. + /// + T Choose(); + + /// + /// Create an enumerable, enumerating the items of this collection that satisfies + /// a certain condition. + /// + /// The T->bool filter delegate defining the condition + /// The filtered enumerable + SCG.IEnumerable Filter(Fun filter); + } + + + + /// + /// A sized generic collection, that can be enumerated backwards. + /// + public interface IDirectedCollectionValue : ICollectionValue, IDirectedEnumerable + { + /// + /// 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 + /// foreach (T x in coll.Backwards()) {...} + /// + /// The backwards collection. + new IDirectedCollectionValue Backwards(); + + /// + /// Check if there exists an item that satisfies a + /// specific predicate in this collection and return the first one in enumeration order. + /// + /// A delegate + /// ( with R == bool) defining the predicate + /// + /// True is such an item exists + bool FindLast(Fun predicate, out T item); + } + + + /// + /// 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, + /// and . + /// + public interface IExtensible : ICollectionValue, ICloneable + { + /// + /// If true any call of an updating operation will throw an + /// ReadOnlyCollectionException + /// + /// True if this collection is read-only. + bool IsReadOnly { get;} + + //TODO: wonder where the right position of this is + /// + /// + /// + /// False if this collection has set semantics, true if bag semantics. + bool AllowsDuplicates { get;} + + //TODO: wonder where the right position of this is. And the semantics. + /// + /// (Here should be a discussion of the role of equalityComparers. Any ). + /// + /// 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. + SCG.IEqualityComparer EqualityComparer { get;} + + //ItemEqualityTypeEnum ItemEqualityType {get ;} + + //TODO: find a good name + + /// + /// By convention this is true for any collection with set semantics. + /// + /// True if only one representative of a group of equal items + /// is kept in the collection together with the total count. + bool DuplicatesByCounting { get;} + + /// + /// 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. + /// + /// The item to add. + /// True if item was added. + bool Add(T item); + + /// + /// 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. + /// + /// The type of items to add + /// The items to add + void AddAll(SCG.IEnumerable items) where U : T; + + //void Clear(); // for priority queue + //int Count why not? + /// + /// Check the integrity of the internal data structures of this collection. + /// This is only relevant for developers of the library + /// + /// True if check was passed. + bool Check(); + } + + /// + /// The simplest interface of a main stream generic collection + /// with lookup, insertion and removal operations. + /// + public interface ICollection : IExtensible, SCG.ICollection + { + //This is somewhat similar to the RandomAccess marker itf in java + /// + /// The value is symbolic indicating the type of asymptotic complexity + /// in terms of the size of this collection (worst-case or amortized as + /// relevant). + /// See for the set of symbols. + /// + /// A characterization of the speed of lookup operations + /// (Contains() etc.) of the implementation of this collection. + Speed ContainsSpeed { get;} + + /// + /// + /// The number of items in this collection + new int Count { get; } + + /// + /// If true any call of an updating operation will throw an + /// ReadOnlyCollectionException + /// + /// True if this collection is read-only. + new bool IsReadOnly { get; } + + /// + /// 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. + /// + /// The item to add. + /// True if item was added. + new bool Add(T item); + + /// + /// Copy the items of this collection to a contiguous part of an array. + /// + /// The array to copy to + /// The index at which to copy the first item + new void CopyTo(T[] array, int index); + + /// + /// The unordered collection hashcode is defined as the sum of + /// h(hashcode(item)) over the items + /// of the collection, where the function h is a function from + /// int to int of the form t -> (a0*t+b0)^(a1*t+b1)^(a2*t+b2), where + /// the ax and bx are the same for all collection classes. + /// The current implementation uses fixed values for the ax and bx, + /// specified as constants in the code. + /// + /// The unordered hashcode of this collection. + int GetUnsequencedHashCode(); + + + /// + /// 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. + /// + /// The collection to compare to. + /// True if this collection and that contains the same items. + bool UnsequencedEquals(ICollection otherCollection); + + + /// + /// Check if this collection contains (an item equivalent to according to the + /// itemequalityComparer) a particular value. + /// + /// The value to check for. + /// True if the items is in this collection. + new bool Contains(T item); + + + /// + /// 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. + /// + /// The value to count. + /// The number of copies found. + int ContainsCount(T item); + + + /// + /// + /// + /// + ICollectionValue UniqueItems(); + + /// + /// + /// + /// + ICollectionValue> ItemMultiplicities(); + + /// + /// Check whether this collection contains all the values in another collection. + /// If this collection has bag semantics (AllowsDuplicates==true) + /// the check is made with respect to multiplicities, else multiplicities + /// are not taken into account. + /// + /// The + /// + /// True if all values in itemsis in this collection. + bool ContainsAll(SCG.IEnumerable items) where U : T; + + + /// + /// 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. + /// + /// The value to look for. + /// True if the items is in this collection. + bool Find(ref T item); + + + //This should probably just be bool Add(ref T item); !!! + /// + /// 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. + /// + /// The value to look for. + /// True if the item was found (hence not added). + bool FindOrAdd(ref T item); + + + /// + /// 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. + /// + /// Value to update. + /// True if the item was found and hence updated. + bool Update(T item); + + /// + /// 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. + /// + /// Value to update. + /// On output the olditem, if found. + /// True if the item was found and hence updated. + bool Update(T item, out T olditem); + + + /// + /// 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. + /// + /// Value to add or update. + /// True if the item was found and updated (hence not added). + bool UpdateOrAdd(T item); + + + /// + /// 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. + /// + /// Value to add or update. + /// On output the olditem, if found. + /// True if the item was found and updated (hence not added). + bool UpdateOrAdd(T item, out T olditem); + + /// + /// Remove a particular item from this collection. If the collection has bag + /// semantics only one copy equivalent to the supplied item is removed. + /// + /// The value to remove. + /// True if the item was found (and removed). + new bool Remove(T item); + + + /// + /// 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. + /// + /// The value to remove. + /// The value removed if any. + /// True if the item was found (and removed). + bool Remove(T item, out T removeditem); + + + /// + /// Remove all items equivalent to a given value. + /// + /// The value to remove. + void RemoveAllCopies(T item); + + + /// + /// Remove all items in another collection from this one. If this collection + /// has bag semantics, take multiplicities into account. + /// + /// + /// The items to remove. + void RemoveAll(SCG.IEnumerable items) where U : T; + + //void RemoveAll(Fun predicate); + + /// + /// Remove all items from this collection. + /// + new void Clear(); + + + /// + /// Remove all items not in some other collection from this one. If this collection + /// has bag semantics, take multiplicities into account. + /// + /// + /// The items to retain. + void RetainAll(SCG.IEnumerable items) where U : T; + + //void RetainAll(Fun predicate); + //IDictionary UniqueItems() + } + + + + /// + /// An editable collection maintaining a definite sequence order of the items. + /// + /// 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. + /// This interface is usually implemented by explicit interface implementation, + /// not as ordinary virtual methods. + /// + public interface ISequenced : ICollection, IDirectedCollectionValue + { + /// + /// The hashcode is defined as h(...h(h(h(x1),x2),x3),...,xn) for + /// h(a,b)=CONSTANT*a+b and the x's the hash codes of the items of + /// this collection. + /// + /// The sequence order hashcode of this collection. + int GetSequencedHashCode(); + + + /// + /// Compare this sequenced collection to another one in sequence order. + /// + /// The sequenced collection to compare to. + /// True if this collection and that contains equal (according to + /// this collection's itemequalityComparer) in the same sequence order. + bool SequencedEquals(ISequenced otherCollection); + } + + + + /// + /// A sequenced collection, where indices of items in the order are maintained + /// + public interface IIndexed : ISequenced + { + /// + /// + /// if index is negative or + /// >= the size of the collection. + /// The index'th item of this list. + /// the index to lookup + T this[int index] { get;} + + /// + /// + /// + /// + Speed IndexingSpeed { get;} + + /// + /// + /// + /// The directed collection of items in a specific index interval. + /// The low index of the interval (inclusive). + /// The size of the range. + IDirectedCollectionValue this[int start, int count] { get;} + + + /// + /// Searches for an item in the list going forwards from the start. + /// + /// Item to search for. + /// 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. + int IndexOf(T item); + + + /// + /// Searches for an item in the list going backwards from the end. + /// + /// Item to search for. + /// 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. + int LastIndexOf(T item); + + /// + /// Check if there exists an item that satisfies a + /// specific predicate in this collection and return the index of the first one. + /// + /// A delegate + /// ( with R == bool) defining the predicate + /// the index, if found, a negative value else + int FindIndex(Fun predicate); + + /// + /// Check if there exists an item that satisfies a + /// specific predicate in this collection and return the index of the last one. + /// + /// A delegate + /// ( with R == bool) defining the predicate + /// the index, if found, a negative value else + int FindLastIndex(Fun predicate); + + + /// + /// Remove the item at a specific position of the list. + /// + /// if index is negative or + /// >= the size of the collection. + /// The index of the item to remove. + /// The removed item. + T RemoveAt(int index); + + + /// + /// Remove all items in an index interval. + /// + /// if start or count + /// is negative or start+count > the size of the collection. + /// The index of the first item to remove. + /// The number of items to remove. + void RemoveInterval(int start, int count); + } + + //TODO: decide if this should extend ICollection + /// + /// The interface describing the operations of a LIFO stack data structure. + /// + /// The item type + public interface IStack : IDirectedCollectionValue + { + /// + /// + /// + /// + bool AllowsDuplicates { get;} + /// + /// Get the index'th element of the stack. The bottom of the stack has index 0. + /// + /// + /// + T this[int index] { get;} + /// + /// Push an item to the top of the stack. + /// + /// The item + void Push(T item); + /// + /// Pop the item at the top of the stack from the stack. + /// + /// The popped item. + T Pop(); + } + + /// + /// The interface describing the operations of a FIFO queue data structure. + /// + /// The item type + public interface IQueue : IDirectedCollectionValue + { + /// + /// + /// + /// + bool AllowsDuplicates { get;} + /// + /// Get the index'th element of the queue. The front of the queue has index 0. + /// + /// + /// + T this[int index] { get;} + /// + /// Enqueue an item at the back of the queue. + /// + /// The item + void Enqueue(T item); + /// + /// Dequeue an item from the front of the queue. + /// + /// The item + T Dequeue(); + } + + + /// + /// 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! + /// + public interface IList : IIndexed, IDisposable, SCG.IList, System.Collections.IList + { + /// + /// + /// if this list is empty. + /// The first item in this list. + T First { get;} + + /// + /// + /// if this list is empty. + /// The last item in this list. + T Last { get;} + + /// + /// Since Add(T item) always add at the end of the list, + /// this describes if list has FIFO or LIFO semantics. + /// + /// True if the Remove() operation removes from the + /// start of the list, false if it removes from the end. + bool FIFO { get; set;} + + /// + /// + /// + bool IsFixedSize { get; } + + /// + /// On this list, this indexer is read/write. + /// + /// if index is negative or + /// >= the size of the collection. + /// The index'th item of this list. + /// The index of the item to fetch or store. + new T this[int index] { get; set;} + + #region Ambiguous calls when extending SCG.IList + + #region SCG.ICollection + /// + /// + /// + new int Count { get; } + + /// + /// + /// + new bool IsReadOnly { get; } + + /// + /// + /// + /// + /// + new bool Add(T item); + + /// + /// + /// + new void Clear(); + + /// + /// + /// + /// + /// + new bool Contains(T item); + + /// + /// + /// + /// + /// + new void CopyTo(T[] array, int index); + + /// + /// + /// + /// + /// + new bool Remove(T item); + + #endregion + + #region SCG.IList proper + + /// + /// Searches for an item in the list going forwards from the start. + /// + /// Item to search for. + /// 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. + new int IndexOf(T item); + + /// + /// Remove the item at a specific position of the list. + /// + /// if index is negative or + /// >= the size of the collection. + /// The index of the item to remove. + /// The removed item. + new T RemoveAt(int index); + + #endregion + + #endregion + + /*/// + /// Insert an item at a specific index location in this list. + /// + /// if index is negative or + /// > the size of the collection. + /// if the list has + /// AllowsDuplicates==false and the item is + /// already in the list. + /// The index at which to insert. + /// The item to insert. + void Insert(int index, T item);*/ + + /// + /// Insert an item at the end of a compatible view, used as a pointer. + /// The pointer must be a view on the same list as + /// this and the endpoitn of pointer must be + /// a valid insertion point of this + /// + /// If pointer + /// is not a view on the same list as this + /// ?????? if the endpoint of + /// pointer is not inside this + /// if the list has + /// AllowsDuplicates==false and the item is + /// already in the list. + /// + /// + void Insert(IList pointer, T item); + + /// + /// Insert an item at the front of this list. + /// if the list has + /// AllowsDuplicates==false and the item is + /// already in the list. + /// + /// The item to insert. + void InsertFirst(T item); + + /// + /// Insert an item at the back of this list. + /// if the list has + /// AllowsDuplicates==false and the item is + /// already in the list. + /// + /// The item to insert. + void InsertLast(T item); + + /// + /// Insert into this list all items from an enumerable collection starting + /// at a particular index. + /// + /// if index is negative or + /// > the size of the collection. + /// if the list has + /// AllowsDuplicates==false and one of the items to insert is + /// already in the list. + /// Index to start inserting at + /// Items to insert + /// + void InsertAll(int index, SCG.IEnumerable items) where U : T; + + /// + /// Create a new list consisting of the items of this list satisfying a + /// certain predicate. + /// + /// The filter delegate defining the predicate. + /// The new list. + IList FindAll(Fun filter); + + /// + /// 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. + /// + /// The type of items of the new list + /// The delegate defining the map. + /// The new list. + IList Map(Fun mapper); + + /// + /// 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. + /// + /// The type of items of the new list + /// The delegate defining the map. + /// The equalityComparer to use for the new list + /// The new list. + IList Map(Fun mapper, SCG.IEqualityComparer equalityComparer); + + /// + /// Remove one item from the list: from the front if FIFO + /// is true, else from the back. + /// if this list is empty. + /// + /// The removed item. + T Remove(); + + /// + /// Remove one item from the front of the list. + /// if this list is empty. + /// + /// The removed item. + T RemoveFirst(); + + /// + /// Remove one item from the back of the list. + /// if this list is empty. + /// + /// The removed item. + T RemoveLast(); + + /// + /// Create a list view on this list. + /// if the view would not fit into + /// this list. + /// + /// The index in this list of the start of the view. + /// The size of the view. + /// The new list view. + IList View(int start, int count); + + /// + /// Create a list view on this list containing the (first) occurrence of a particular item. + /// if the item is not in this list. + /// + /// The item to find. + /// The new list view. + IList ViewOf(T item); + + /// + /// Create a list view on this list containing the last occurrence of a particular item. + /// if the item is not in this list. + /// + /// The item to find. + /// The new list view. + IList LastViewOf(T item); + + /// + /// Null if this list is not a view. + /// + /// Underlying list for view. + IList Underlying { get;} + + /// + /// + /// Offset for this list view or 0 for an underlying list. + int Offset { get;} + + /// + /// + /// + /// + bool IsValid { get;} + + /// + /// Slide this list view along the underlying list. + /// + /// if this list is not a view. + /// if the operation + /// would bring either end of the view outside the underlying list. + /// The signed amount to slide: positive to slide + /// towards the end. + IList Slide(int offset); + + /// + /// Slide this list view along the underlying list, changing its size. + /// + /// + /// if this list is not a view. + /// if the operation + /// would bring either end of the view outside the underlying list. + /// The signed amount to slide: positive to slide + /// towards the end. + /// The new size of the view. + IList Slide(int offset, int size); + + /// + /// + /// + /// + /// + bool TrySlide(int offset); + + /// + /// + /// + /// + /// + /// + bool TrySlide(int offset, int size); + + /// + /// + /// Returns null if otherView is strictly to the left of this view + /// + /// + /// If otherView does not have the same underlying list as this + /// If otherView is strictly to the left of this view + /// + IList Span(IList otherView); + + /// + /// Reverse the list so the items are in the opposite sequence order. + /// + void Reverse(); + + /// + /// Check if this list is sorted according to the default sorting order + /// for the item type T, as defined by the class + /// + /// if T is not comparable + /// True if the list is sorted, else false. + bool IsSorted(); + + /// + /// Check if this list is sorted according to a specific sorting order. + /// + /// The comparer defining the sorting order. + /// True if the list is sorted, else false. + bool IsSorted(SCG.IComparer comparer); + + /// + /// Sort the items of the list according to the default sorting order + /// for the item type T, as defined by the class + /// + /// if T is not comparable + void Sort(); + + /// + /// Sort the items of the list according to a specified sorting order. + /// 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. + /// + /// + /// The comparer defining the sorting order. + void Sort(SCG.IComparer comparer); + + + /// + /// Randomly shuffle the items of this list. + /// + void Shuffle(); + + + /// + /// Shuffle the items of this list according to a specific random source. + /// + /// The random source. + void Shuffle(Random rnd); + } + + + /// + /// The base type of a priority queue handle + /// + /// + public interface IPriorityQueueHandle + { + //TODO: make abstract and prepare for double dispatch: + //public virtual bool Delete(IPriorityQueue q) { throw new InvalidFooException();} + //bool Replace(T item); + } + + + /// + /// A generic collection of items prioritized by a comparison (order) relation. + /// Supports adding items and reporting or removing extremal elements. + /// + /// + /// + /// 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. + /// + public interface IPriorityQueue : IExtensible + { + /// + /// Find the current least item of this priority queue. + /// + /// The least item. + T FindMin(); + + + /// + /// Remove the least item from this priority queue. + /// + /// The removed item. + T DeleteMin(); + + + /// + /// Find the current largest item of this priority queue. + /// + /// The largest item. + T FindMax(); + + + /// + /// Remove the largest item from this priority queue. + /// + /// The removed item. + T DeleteMax(); + + /// + /// The comparer object supplied at creation time for this collection + /// + /// The comparer + SCG.IComparer Comparer { get;} + /// + /// Get or set the item corresponding to a handle. Throws exceptions on + /// invalid handles. + /// + /// + /// + T this[IPriorityQueueHandle handle] { get; set;} + + /// + /// Check if the entry corresponding to a handle is in the priority queue. + /// + /// + /// + /// + bool Find(IPriorityQueueHandle handle, out T item); + + /// + /// Add an item to the priority queue, receiving a + /// handle for the item in the queue, + /// or reusing an existing unused 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. + /// + /// + bool Add(ref IPriorityQueueHandle handle, T item); + + /// + /// Delete an item with a handle from a priority queue + /// + /// The handle for the item. The handle will be invalidated, but reusable. + /// The deleted item + T Delete(IPriorityQueueHandle handle); + + /// + /// Replace an item with a handle in a priority queue with a new item. + /// Typically used for changing the priority of some queued object. + /// + /// The handle for the old item + /// The new item + /// The old item + T Replace(IPriorityQueueHandle handle, T item); + + /// + /// Find the current least item of this priority queue. + /// + /// On return: the handle of the item. + /// The least item. + T FindMin(out IPriorityQueueHandle handle); + + /// + /// Find the current largest item of this priority queue. + /// + /// On return: the handle of the item. + /// The largest item. + + T FindMax(out IPriorityQueueHandle handle); + + /// + /// Remove the least item from this priority queue. + /// + /// On return: the handle of the removed item. + /// The removed item. + + T DeleteMin(out IPriorityQueueHandle handle); + + /// + /// Remove the largest item from this priority queue. + /// + /// On return: the handle of the removed item. + /// The removed item. + T DeleteMax(out IPriorityQueueHandle handle); + } + + + + /// + /// 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. + /// + /// The sorting order is defined by a comparer, an object of type IComparer<T> + /// (). 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, . + /// + /// The comparer of the sorted collection is available as the Comparer property + /// (). + /// + /// The methods are grouped according to + /// + /// Extrema: report or report and delete an extremal item. This is reminiscent of simplified priority queues. + /// Nearest neighbor: report predecessor or successor in the collection of an item. Cut belongs to this group. + /// Range: report a view of a range of elements or remove all elements in a range. + /// AddSorted: add a collection of items known to be sorted in the same order (should be faster) (to be removed?) + /// + /// + /// + /// Since this interface extends ISequenced<T>, sorted collections will also have an + /// item 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, + /// ( and ) + /// + /// 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. + /// + public interface ISorted : ISequenced + { + /// + /// Find the current least item of this sorted collection. + /// + /// if the collection is empty. + /// The least item. + T FindMin(); + + + /// + /// Remove the least item from this sorted collection. + /// + /// if the collection is empty. + /// The removed item. + T DeleteMin(); + + + /// + /// Find the current largest item of this sorted collection. + /// + /// if the collection is empty. + /// The largest item. + T FindMax(); + + + /// + /// Remove the largest item from this sorted collection. + /// + /// if the collection is empty. + /// The removed item. + T DeleteMax(); + + /// + /// The comparer object supplied at creation time for this sorted collection. + /// + /// The comparer + SCG.IComparer Comparer { get; } + + /// + /// Find the strict predecessor of item in the sorted collection, + /// that is, the greatest item in the collection smaller than the item. + /// + /// The item to find the predecessor for. + /// The predecessor, if any; otherwise the default value for T. + /// True if item has a predecessor; otherwise false. + bool TryPredecessor(T item, out T res); + + + /// + /// Find the strict successor of item in the sorted collection, + /// that is, the least item in the collection greater than the supplied value. + /// + /// The item to find the successor for. + /// The successor, if any; otherwise the default value for T. + /// True if item has a successor; otherwise false. + bool TrySuccessor(T item, out T res); + + + /// + /// 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. + /// + /// The item to find the weak predecessor for. + /// The weak predecessor, if any; otherwise the default value for T. + /// True if item has a weak predecessor; otherwise false. + bool TryWeakPredecessor(T item, out T res); + + + /// + /// 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. + /// + /// The item to find the weak successor for. + /// The weak successor, if any; otherwise the default value for T. + /// True if item has a weak successor; otherwise false. + bool TryWeakSuccessor(T item, out T res); + + + /// + /// 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. + /// + /// if no such element exists (the + /// supplied value is less than or equal to the minimum of this collection.) + /// The item to find the predecessor for. + /// The predecessor. + T Predecessor(T item); + + + /// + /// 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. + /// + /// if no such element exists (the + /// supplied value is greater than or equal to the maximum of this collection.) + /// The item to find the successor for. + /// The successor. + T Successor(T item); + + + /// + /// 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. + /// + /// if no such element exists (the + /// supplied value is less than the minimum of this collection.) + /// The item to find the weak predecessor for. + /// The weak predecessor. + T WeakPredecessor(T item); + + + /// + /// 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. + /// + /// if no such element exists (the + /// supplied value is greater than the maximum of this collection.) + ///The item to find the weak successor for. + /// The weak successor. + T WeakSuccessor(T item); + + + /// + /// Given a "cut" function from the items of the sorted collection to int + /// whose only sign changes when going through items in increasing order + /// can be + /// + /// from positive to zero + /// from positive to negative + /// from zero to negative + /// + /// The "cut" function is supplied as the CompareTo method + /// of an object c implementing + /// IComparable<T>. + /// A typical example is the case where T is comparable and + /// cutFunction is itself of type T. + /// This method performs a search in the sorted collection for the ranges in which the + /// "cut" function is negative, zero respectively positive. If T is comparable + /// and c is of type T, this is a safe way (no exceptions thrown) + /// to find predecessor and successor of c. + /// + /// If the supplied cut function does not satisfy the sign-change condition, + /// the result of this call is undefined. + /// + /// + /// + /// The cut function T to int, given + /// by the CompareTo method of an object implementing + /// IComparable<T>. + /// Returns the largest item in the collection, where the + /// cut function is positive (if any). + /// Returns true if the cut function is positive somewhere + /// on this collection. + /// Returns the least item in the collection, where the + /// cut function is negative (if any). + /// Returns true if the cut function is negative somewhere + /// on this collection. + /// True if the cut function is zero somewhere + /// on this collection. + bool Cut(IComparable cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid); + + + /// + /// Query this sorted collection for items greater than or equal to a supplied value. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The lower bound (inclusive). + /// The result directed collection. + IDirectedEnumerable RangeFrom(T bot); + + + /// + /// Query this sorted collection for items between two supplied values. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The lower bound (inclusive). + /// The upper bound (exclusive). + /// The result directed collection. + IDirectedEnumerable RangeFromTo(T bot, T top); + + + /// + /// Query this sorted collection for items less than a supplied value. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The upper bound (exclusive). + /// The result directed collection. + IDirectedEnumerable RangeTo(T top); + + + /// + /// Create a directed collection with the same items as this collection. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The result directed collection. + IDirectedCollectionValue RangeAll(); + + + //TODO: remove now that we assume that we can check the sorting order? + /// + /// Add all the items from another collection with an enumeration order that + /// is increasing in the items. + /// + /// if the enumerated items turns out + /// not to be in increasing order. + /// The collection to add. + /// + void AddSorted(SCG.IEnumerable items) where U : T; + + + /// + /// Remove all items of this collection above or at a supplied threshold. + /// + /// The lower threshold (inclusive). + void RemoveRangeFrom(T low); + + + /// + /// Remove all items of this collection between two supplied thresholds. + /// + /// The lower threshold (inclusive). + /// The upper threshold (exclusive). + void RemoveRangeFromTo(T low, T hi); + + + /// + /// Remove all items of this collection below a supplied threshold. + /// + /// The upper threshold (exclusive). + void RemoveRangeTo(T hi); + } + + + + /// + /// A collection where items are maintained in sorted order together + /// with their indexes in that order. + /// + public interface IIndexedSorted : ISorted, IIndexed + { + /// + /// Determine the number of items at or above a supplied threshold. + /// + /// The lower bound (inclusive) + /// The number of matcing items. + int CountFrom(T bot); + + + /// + /// Determine the number of items between two supplied thresholds. + /// + /// The lower bound (inclusive) + /// The upper bound (exclusive) + /// The number of matcing items. + int CountFromTo(T bot, T top); + + + /// + /// Determine the number of items below a supplied threshold. + /// + /// The upper bound (exclusive) + /// The number of matcing items. + int CountTo(T top); + + + /// + /// Query this sorted collection for items greater than or equal to a supplied value. + /// + /// The lower bound (inclusive). + /// The result directed collection. + new IDirectedCollectionValue RangeFrom(T bot); + + + /// + /// Query this sorted collection for items between two supplied values. + /// + /// The lower bound (inclusive). + /// The upper bound (exclusive). + /// The result directed collection. + new IDirectedCollectionValue RangeFromTo(T bot, T top); + + + /// + /// Query this sorted collection for items less than a supplied value. + /// + /// The upper bound (exclusive). + /// The result directed collection. + new IDirectedCollectionValue RangeTo(T top); + + + /// + /// Create a new indexed sorted collection consisting of the items of this + /// indexed sorted collection satisfying a certain predicate. + /// + /// The filter delegate defining the predicate. + /// The new indexed sorted collection. + IIndexedSorted FindAll(Fun predicate); + + + /// + /// Create a new indexed sorted collection consisting of the results of + /// mapping all items of this list. + /// if the map is not increasing over + /// the items of this collection (with respect to the two given comparison + /// relations). + /// + /// The delegate definging the map. + /// The comparion relation to use for the result. + /// The new sorted collection. + IIndexedSorted Map(Fun mapper, SCG.IComparer comparer); + } + + + + /// + /// The type of a sorted collection with persistence + /// + public interface IPersistentSorted : ISorted, IDisposable + { + /// + /// Make a (read-only) snap shot of this collection. + /// + /// The snap shot. + ISorted Snapshot(); + } + + + + /*************************************************************************/ + /// + /// A dictionary with keys of type K and values of type V. Equivalent to a + /// finite partial map from K to V. + /// + public interface IDictionary : ICollectionValue>, ICloneable + { + /// + /// The key equalityComparer. + /// + /// + SCG.IEqualityComparer EqualityComparer { get;} + + /// + /// Indexer for dictionary. + /// + /// if no entry is found. + /// The value corresponding to the key + V this[K key] { get; set;} + + + /// + /// + /// + /// True if dictionary is read-only + bool IsReadOnly { get;} + + + /// + /// + /// + /// A collection containg the all the keys of the dictionary + ICollectionValue Keys { get;} + + + /// + /// + /// + /// A collection containing all the values of the dictionary + ICollectionValue Values { get;} + + /// + /// + /// + /// A delegate of type defining the partial function from K to V give by the dictionary. + Fun Fun { get; } + + + //TODO: resolve inconsistency: Add thows exception if key already there, AddAll ignores keys already There? + /// + /// Add a new (key, value) pair (a mapping) to the dictionary. + /// + /// if there already is an entry with the same key. > + /// Key to add + /// Value to add + void Add(K key, V val); + + /// + /// Add the entries from a collection of pairs to this dictionary. + /// + /// + /// If the input contains duplicate keys or a key already present in this dictionary. + /// + void AddAll(SCG.IEnumerable> entries) + where U : K + where W : V + ; + + /// + /// The value is symbolic indicating the type of asymptotic complexity + /// in terms of the size of this collection (worst-case or amortized as + /// relevant). + /// See for the set of symbols. + /// + /// A characterization of the speed of lookup operations + /// (Contains() etc.) of the implementation of this dictionary. + Speed ContainsSpeed { get;} + + /// + /// Check whether this collection contains all the values in another collection. + /// If this collection has bag semantics (AllowsDuplicates==true) + /// the check is made with respect to multiplicities, else multiplicities + /// are not taken into account. + /// + /// The + /// True if all values in itemsis in this collection. + bool ContainsAll(SCG.IEnumerable items) where H : K; + + /// + /// Remove an entry with a given key from the dictionary + /// + /// The key of the entry to remove + /// True if an entry was found (and removed) + bool Remove(K key); + + + /// + /// Remove an entry with a given key from the dictionary and report its value. + /// + /// The key of the entry to remove + /// On exit, the value of the removed entry + /// True if an entry was found (and removed) + bool Remove(K key, out V val); + + + /// + /// Remove all entries from the dictionary + /// + void Clear(); + + + /// + /// Check if there is an entry with a specified key + /// + /// The key to look for + /// True if key was found + bool Contains(K key); + + + /// + /// 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]". + /// + /// The key to look for + /// On exit, the value of the entry + /// True if key was found + bool Find(K key, out V val); + + /// + /// 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]". + /// + /// The key to look for + /// On exit, the value of the entry + /// True if key was found + bool Find(ref K key, out V val); + + + /// + /// 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". + /// + /// The key to look for + /// The new value + /// True if key was found + bool Update(K key, V val); //no-adding + + + /// + /// 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. + /// + /// The key to look for + /// The new value + /// The old value if any + /// True if key was found + bool Update(K key, V val, out V oldval); //no-adding + + /// + /// 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. + /// + /// The key to look for + /// On entry the value to add if the key is not found. + /// On exit the value found if any. + /// True if key was found + bool FindOrAdd(K key, ref V val); //mixture + + + /// + /// 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. + /// + /// The key to look for + /// The value to add or replace with. + /// True if key was found and value updated. + bool UpdateOrAdd(K key, V val); + + + /// + /// 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. + /// + /// The key to look for + /// The value to add or replace with. + /// The old value if any + /// True if key was found and value updated. + bool UpdateOrAdd(K key, V val, out V oldval); + + + /// + /// Check the integrity of the internal data structures of this dictionary. + /// Only avaliable in DEBUG builds??? + /// + /// True if check does not fail. + bool Check(); + } + + + + /// + /// A dictionary with sorted keys. + /// + public interface ISortedDictionary : IDictionary + { + /// + /// + /// + /// + new ISorted Keys { get;} + + /// + /// Find the current least item of this sorted collection. + /// + /// if the collection is empty. + /// The least item. + KeyValuePair FindMin(); + + + /// + /// Remove the least item from this sorted collection. + /// + /// if the collection is empty. + /// The removed item. + KeyValuePair DeleteMin(); + + + /// + /// Find the current largest item of this sorted collection. + /// + /// if the collection is empty. + /// The largest item. + KeyValuePair FindMax(); + + + /// + /// Remove the largest item from this sorted collection. + /// + /// if the collection is empty. + /// The removed item. + KeyValuePair DeleteMax(); + + /// + /// The key comparer used by this dictionary. + /// + /// + SCG.IComparer Comparer { get;} + + /// + /// Find the entry in the dictionary whose key is the + /// predecessor of the specified key. + /// + /// The key + /// The predecessor, if any + /// True if key has a predecessor + bool TryPredecessor(K key, out KeyValuePair res); + + /// + /// Find the entry in the dictionary whose key is the + /// successor of the specified key. + /// + /// The key + /// The successor, if any + /// True if the key has a successor + bool TrySuccessor(K key, out KeyValuePair res); + + /// + /// Find the entry in the dictionary whose key is the + /// weak predecessor of the specified key. + /// + /// The key + /// The predecessor, if any + /// True if key has a weak predecessor + bool TryWeakPredecessor(K key, out KeyValuePair res); + + /// + /// Find the entry in the dictionary whose key is the + /// weak successor of the specified key. + /// + /// The key + /// The weak successor, if any + /// True if the key has a weak successor + bool TryWeakSuccessor(K key, out KeyValuePair res); + + /// + /// Find the entry with the largest key less than a given key. + /// + /// if there is no such entry. + /// The key to compare to + /// The entry + KeyValuePair Predecessor(K key); + + + /// + /// Find the entry with the least key greater than a given key. + /// + /// if there is no such entry. + /// The key to compare to + /// The entry + KeyValuePair Successor(K key); + + + /// + /// Find the entry with the largest key less than or equal to a given key. + /// + /// if there is no such entry. + /// The key to compare to + /// The entry + KeyValuePair WeakPredecessor(K key); + + + /// + /// Find the entry with the least key greater than or equal to a given key. + /// + /// if there is no such entry. + /// The key to compare to + /// The entry + KeyValuePair WeakSuccessor(K key); + + /// + /// Given a "cut" function from the items of the sorted collection to int + /// whose only sign changes when going through items in increasing order + /// can be + /// + /// from positive to zero + /// from positive to negative + /// from zero to negative + /// + /// The "cut" function is supplied as the CompareTo method + /// of an object c implementing + /// IComparable<K>. + /// A typical example is the case where K is comparable and + /// c is itself of type K. + /// This method performs a search in the sorted collection for the ranges in which the + /// "cut" function is negative, zero respectively positive. If K is comparable + /// and c is of type K, this is a safe way (no exceptions thrown) + /// to find predecessor and successor of c. + /// + /// If the supplied cut function does not satisfy the sign-change condition, + /// the result of this call is undefined. + /// + /// + /// + /// The cut function K to int, given + /// by the CompareTo method of an object implementing + /// IComparable<K>. + /// Returns the largest item in the collection, where the + /// cut function is positive (if any). + /// Returns true if the cut function is positive somewhere + /// on this collection. + /// Returns the least item in the collection, where the + /// cut function is negative (if any). + /// Returns true if the cut function is negative somewhere + /// on this collection. + /// True if the cut function is zero somewhere + /// on this collection. + bool Cut(IComparable cutFunction, out KeyValuePair lowEntry, out bool lowIsValid, out KeyValuePair highEntry, out bool highIsValid); + + /// + /// Query this sorted collection for items greater than or equal to a supplied value. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The lower bound (inclusive). + /// The result directed collection. + IDirectedEnumerable> RangeFrom(K bot); + + + /// + /// Query this sorted collection for items between two supplied values. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The lower bound (inclusive). + /// The upper bound (exclusive). + /// The result directed collection. + IDirectedEnumerable> RangeFromTo(K lowerBound, K upperBound); + + + /// + /// Query this sorted collection for items less than a supplied value. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The upper bound (exclusive). + /// The result directed collection. + IDirectedEnumerable> RangeTo(K top); + + + /// + /// Create a directed collection with the same items as this collection. + /// The returned collection is not a copy but a view into the collection. + /// 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. + /// + /// The result directed collection. + IDirectedCollectionValue> RangeAll(); + + + //TODO: remove now that we assume that we can check the sorting order? + /// + /// Add all the items from another collection with an enumeration order that + /// is increasing in the items. + /// + /// if the enumerated items turns out + /// not to be in increasing order. + /// The collection to add. + void AddSorted(SCG.IEnumerable> items); + + + /// + /// Remove all items of this collection above or at a supplied threshold. + /// + /// The lower threshold (inclusive). + void RemoveRangeFrom(K low); + + + /// + /// Remove all items of this collection between two supplied thresholds. + /// + /// The lower threshold (inclusive). + /// The upper threshold (exclusive). + void RemoveRangeFromTo(K low, K hi); + + + /// + /// Remove all items of this collection below a supplied threshold. + /// + /// The upper threshold (exclusive). + void RemoveRangeTo(K hi); + } + + + + /*******************************************************************/ + /*/// + /// The type of an item comparer + /// 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. + /// Implementations must 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. + /// Implementations of this interface must always return values from the method + /// and never throw exceptions. + /// This interface is identical to System.Collections.Generic.IComparer<T> + /// + public interface IComparer + { + /// + /// Compare two items with respect to this item comparer + /// + /// First item + /// Second item + /// Positive if item1 is greater than item2, 0 if they are equal, negative if item1 is less than item2 + int Compare(T item1, T item2); + } + + /// + /// The type of an item equalityComparer. + /// Implementations of this interface must 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. + /// Implementations of this interface must 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. + /// Implementations of this interface must always return values from the methods + /// and never throw exceptions. + /// This interface is similar in function to System.IKeyComparer<T> + /// + public interface SCG.IEqualityComparer + { + /// + /// Get the hash code with respect to this item equalityComparer + /// + /// The item + /// The hash code + int GetHashCode(T item); + + + /// + /// Check if two items are equal with respect to this item equalityComparer + /// + /// first item + /// second item + /// True if equal + bool Equals(T item1, T item2); + }*/ +}