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 items
is 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 items
is 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 items
is 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.
+ ///