Interface ISorted<T>

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, Comparer<T>.Default.

The comparer of the sorted collection is available as the Comparer property (Comparer).

The methods are grouped according to

Since this interface extends ISequenced<T>, sorted collections will also have an item equalityComparer (IExtensible<T>.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, (ICollection<T> and ISequenced<T>)

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.

Implements

IEnumerable<T>, System.Collections.IEnumerable, System.IFormattable, System.ICloneable, System.Collections.Generic.ICollection<T>, ICollection<T>, ICollectionValue<T>, IDirectedCollectionValue<T>, IDirectedEnumerable<T>, IExtensible<T>, ISequenced<T>, IShowable

Implemented by

GuardedIndexedSorted<T>, GuardedSorted<T>, SortedArray<T>, TreeBag<T>, TreeSet<T>

Super

IIndexedSorted<T>, IPersistentSorted<T>

Property overview

Comparer

Method overview

AddSorted<U>(IEnumerable<U> items) ,
Cut(System.IComparable<T> cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid) ,
DeleteMax() ,
DeleteMin() ,
FindMax() ,
FindMin() ,
Predecessor(T item) ,
RangeAll() ,
RangeFrom(T bot) ,
RangeFromTo(T bot, T top) ,
RangeTo(T top) ,
RemoveRangeFrom(T low) ,
RemoveRangeFromTo(T low, T hi) ,
RemoveRangeTo(T hi) ,
Successor(T item) ,
TryPredecessor(T item, out T res) ,
TrySuccessor(T item, out T res) ,
TryWeakPredecessor(T item, out T res) ,
TryWeakSuccessor(T item, out T res) ,
WeakPredecessor(T item) ,
WeakSuccessor(T item)

Property details

A System.Collections.Generic.IComparer<T> ComparerAccess: Read-Only

Value:The comparer

The comparer object supplied at creation time for this sorted collection.

Method details

A void AddSorted<U>(IEnumerable<U> items) Add all the items from another collection with an enumeration order that is increasing in the items.
Throws
System.ArgumentException if the enumerated items turns out not to be in increasing order.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The collection to add.
A bool Cut(System.IComparable<T> cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid) 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.

Returns:True if the cut function is zero somewhere on this collection.
Parameters:
cutFunction:The cut function T to int, given by the CompareTo method of an object implementing IComparable<T>.
low:Returns the largest item in the collection, where the cut function is positive (if any).
lowIsValid:Returns true if the cut function is positive somewhere on this collection.
high:Returns the least item in the collection, where the cut function is negative (if any).
highIsValid:Returns true if the cut function is negative somewhere on this collection.
A T DeleteMax() Remove the largest item from this sorted collection.
Throws
NoSuchItemException if the collection is empty.
Returns:The removed item.
A T DeleteMin() Remove the least item from this sorted collection.
Throws
NoSuchItemException if the collection is empty.
Returns:The removed item.
A T FindMax() Find the current largest item of this sorted collection.
Throws
NoSuchItemException if the collection is empty.
Returns:The largest item.
A T FindMin() Find the current least item of this sorted collection.
Throws
NoSuchItemException if the collection is empty.
Returns:The least item.
A T Predecessor(T item) 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.
Throws
NoSuchItemException if no such element exists (the supplied value is less than or equal to the minimum of this collection.)
Returns:The predecessor.
Parameters:
item:The item to find the predecessor for.
A IDirectedCollectionValue<T> RangeAll() 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.

Returns:The result directed collection.
A IDirectedEnumerable<T> RangeFrom(T bot) 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.

Returns:The result directed collection.
Parameters:
bot:The lower bound (inclusive).
A IDirectedEnumerable<T> RangeFromTo(T bot, T top) 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.

Returns:The result directed collection.
Parameters:
bot:The lower bound (inclusive).
top:The upper bound (exclusive).
A IDirectedEnumerable<T> RangeTo(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.

Returns:The result directed collection.
Parameters:
top:The upper bound (exclusive).
A void RemoveRangeFrom(T low) Remove all items of this collection above or at a supplied threshold.
Parameters:
low:The lower threshold (inclusive).
A void RemoveRangeFromTo(T low, T hi) Remove all items of this collection between two supplied thresholds.
Parameters:
low:The lower threshold (inclusive).
hi:The upper threshold (exclusive).
A void RemoveRangeTo(T hi) Remove all items of this collection below a supplied threshold.
Parameters:
hi:The upper threshold (exclusive).
A T Successor(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.
Throws
NoSuchItemException if no such element exists (the supplied value is greater than or equal to the maximum of this collection.)
Returns:The successor.
Parameters:
item:The item to find the successor for.
A bool TryPredecessor(T item, out T res) Find the strict predecessor of item in the sorted collection, that is, the greatest item in the collection smaller than the item.
Returns:True if item has a predecessor; otherwise false.
Parameters:
item:The item to find the predecessor for.
res:The predecessor, if any; otherwise the default value for T.
A bool TrySuccessor(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.
Returns:True if item has a successor; otherwise false.
Parameters:
item:The item to find the successor for.
res:The successor, if any; otherwise the default value for T.
A bool TryWeakPredecessor(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.
Returns:True if item has a weak predecessor; otherwise false.
Parameters:
item:The item to find the weak predecessor for.
res:The weak predecessor, if any; otherwise the default value for T.
A bool TryWeakSuccessor(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.
Returns:True if item has a weak successor; otherwise false.
Parameters:
item:The item to find the weak successor for.
res:The weak successor, if any; otherwise the default value for T.
A T WeakPredecessor(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.
Throws
NoSuchItemException if no such element exists (the supplied value is less than the minimum of this collection.)
Returns:The weak predecessor.
Parameters:
item:The item to find the weak predecessor for.
A T WeakSuccessor(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.
Throws
NoSuchItemException if no such element exists (the supplied value is greater than the maximum of this collection.)
Returns:The weak successor.
Parameters:
item:The item to find the weak successor for.