Class SortedArray<T>

A collection class implementing a sorted dynamic array data structure.

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>, IIndexed<T>, IIndexedSorted<T>, ISequenced<T>, IShowable, ISorted<T>

Bases

object, EnumerableBase<T>, CollectionValueBase<T>, CollectionBase<T>, DirectedCollectionBase<T>, SequencedBase<T>, ArrayBase<T>

Field overview

array, Inherited from ArrayBase<T> ,
isReadOnlyBase, Inherited from CollectionBase<T> ,
itemequalityComparer, Inherited from CollectionBase<T> ,
offset, Inherited from ArrayBase<T> ,
size, Inherited from CollectionBase<T> ,
stamp, Inherited from CollectionBase<T>

Event overview

CollectionChanged, Inherited from CollectionValueBase<T> ,
CollectionCleared, Inherited from CollectionValueBase<T> ,
ItemInserted, Inherited from CollectionValueBase<T> ,
ItemRemovedAt, Inherited from CollectionValueBase<T> ,
ItemsAdded, Inherited from CollectionValueBase<T> ,
ItemsRemoved, Inherited from CollectionValueBase<T>

Property overview

ActiveEvents, Inherited from CollectionValueBase<T> ,
AllowsDuplicates ,
Comparer ,
ContainsSpeed ,
Count, Inherited from CollectionBase<T> ,
CountSpeed, Inherited from CollectionBase<T> ,
Direction, Inherited from SequencedBase<T> ,
DuplicatesByCounting ,
EqualityComparer, Inherited from CollectionBase<T> ,
Features ,
IndexingSpeed ,
IsEmpty, Inherited from CollectionBase<T> ,
IsReadOnly, Inherited from CollectionBase<T> ,
this[int i] ,
this[int start, int count], Inherited from ArrayBase<T> ,
ListenableEvents

Constructor overview

SortedArray<T>() ,
SortedArray<T>(int capacity) ,
SortedArray<T>(System.Collections.Generic.IComparer<T> comparer) ,
SortedArray<T>(int capacity, System.Collections.Generic.IComparer<T> comparer) ,
SortedArray<T>(int capacity, System.Collections.Generic.IComparer<T> comparer, System.Collections.Generic.IEqualityComparer<T> equalityComparer)

Method overview

Add(T item) ,
AddAll<U>(IEnumerable<U> items) ,
AddSorted<U>(IEnumerable<U> items) ,
All(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Apply(Act<T> action), Inherited from CollectionValueBase<T> ,
Backwards(), Inherited from ArrayBase<T> ,
Check() ,
checkRange(int start, int count), Inherited from CollectionBase<T> ,
Choose(), Inherited from ArrayBase<T> ,
Clear() ,
Clone() ,
Contains(T item) ,
ContainsAll<U>(IEnumerable<U> items) ,
ContainsCount(T item) ,
CopyTo(T[] array, int index), Inherited from CollectionValueBase<T> ,
CountFrom(T bot) ,
CountFromTo(T bot, T top) ,
CountTo(T top) ,
Cut(System.IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid) ,
DeleteMax() ,
DeleteMin() ,
Equals(object obj), Inherited from object ,
Exists(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
expand(), Inherited from ArrayBase<T> ,
expand(int newcapacity, int newsize), Inherited from ArrayBase<T> ,
Filter(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Finalize(), Inherited from object ,
Find(ref T item) ,
Find(Fun<T,bool> predicate, out T item), Inherited from CollectionValueBase<T> ,
FindAll(Fun<T,bool> f) ,
FindIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindLast(Fun<T,bool> predicate, out T item), Inherited from DirectedCollectionBase<T> ,
FindLastIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindMax() ,
FindMin() ,
FindOrAdd(ref T item) ,
GetEnumerator(), Inherited from ArrayBase<T> ,
GetHashCode(), Inherited from object ,
GetSequencedHashCode(), Inherited from SequencedBase<T> ,
GetType(), Inherited from object ,
GetUnsequencedHashCode(), Inherited from CollectionBase<T> ,
IndexOf(T item) ,
insert(int i, T item), Inherited from ArrayBase<T> ,
ItemMultiplicities() ,
LastIndexOf(T item) ,
Map<V>(Fun<T,V> m, System.Collections.Generic.IComparer<V> c) ,
MemberwiseClone(), Inherited from object ,
modifycheck(int thestamp), Inherited from CollectionBase<T> ,
Predecessor(T item) ,
raiseCollectionChanged(), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count, System.Nullable<int> offset), Inherited from CollectionValueBase<T> ,
raiseForAdd(T item), Inherited from CollectionValueBase<T> ,
raiseForInsert(int i, T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item, int count), Inherited from CollectionValueBase<T> ,
raiseForRemoveAll(ICollectionValue<T> wasRemoved), Inherited from CollectionValueBase<T> ,
raiseForRemoveAt(int index, T item), Inherited from CollectionValueBase<T> ,
raiseForSetThis(int index, T value, T item), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem, int count), Inherited from CollectionValueBase<T> ,
raiseItemInserted(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemRemovedAt(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemsAdded(T item, int count), Inherited from CollectionValueBase<T> ,
raiseItemsRemoved(T item, int count), Inherited from CollectionValueBase<T> ,
RangeAll() ,
RangeFrom(T bot) ,
RangeFromTo(T bot, T top) ,
RangeTo(T top) ,
Remove(T item) ,
Remove(T item, out T removeditem) ,
RemoveAll<U>(IEnumerable<U> items) ,
RemoveAllCopies(T item) ,
RemoveAt(int i) ,
RemoveInterval(int start, int count) ,
RemoveRangeFrom(T low) ,
RemoveRangeFromTo(T low, T hi) ,
RemoveRangeTo(T hi) ,
RetainAll<U>(IEnumerable<U> items) ,
SequencedEquals(ISequenced<T> otherCollection), Inherited from SequencedBase<T> ,
Show(System.Text.StringBuilder stringbuilder, ref int rest, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
Successor(T item) ,
ToArray(), Inherited from ArrayBase<T> ,
ToString(string format, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
ToString(), Inherited from CollectionValueBase<T> ,
TryPredecessor(T item, out T res) ,
TrySuccessor(T item, out T res) ,
TryWeakPredecessor(T item, out T res) ,
TryWeakSuccessor(T item, out T res) ,
UniqueItems() ,
UnsequencedEquals(ICollection<T> otherCollection), Inherited from CollectionBase<T> ,
Update(T item) ,
Update(T item, out T olditem) ,
updatecheck(), Inherited from CollectionBase<T> ,
UpdateOrAdd(T item) ,
UpdateOrAdd(T item, out T olditem) ,
WeakPredecessor(T item) ,
WeakSuccessor(T item)

Property details

F bool AllowsDuplicatesAccess: Read-Only

Value:False since this collection has set semantics

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

Value:The comparer

The comparer object supplied at creation time for this collection
F Speed ContainsSpeedAccess: Read-Only

Value:Speed.Log

The value is symbolic indicating the type of asymptotic complexity in terms of the size of this collection (worst-case).
bool DuplicatesByCountingAccess: Read-Only

Value:True if only one representative of a group of equal items is kept in the collection together with the total count.

By convention this is true for any collection with set semantics.
S SortedArray<T>.Feature FeaturesAccess: Read-Only

Value:

A debugging artifact. To be removed.
Speed IndexingSpeedAccess: Read-Only

Value:

F T this[int i]Access: Read-Only

Value:The i'th item of this list.

/ThrowsSystem.IndexOutOfRangeException if i is negative or >= the size of the collection.
Parameters:
i:the index to lookup
EventTypeEnum ListenableEventsAccess: Read-Only

Value:

Constructor details

SortedArray<T>() Create a dynamic sorted array with a natural comparer (and item equalityComparer, assumed compatible)
Throws
NotComparableExceptionIf T is not comparable.
SortedArray<T>(int capacity) Create a dynamic sorted array with a natural comparer (and item equalityComparer, assumed compatible) and prescribed initial capacity.
Throws
NotComparableExceptionIf T is not comparable.
Parameters:
capacity:The capacity
SortedArray<T>(System.Collections.Generic.IComparer<T> comparer) Create a dynamic sorted array with an external comparer.

The itemequalityComparer will be compatible ComparerZeroHashCodeEqualityComparer<T> since the default equalityComparer for T (EqualityComparer<T>.Default) is unlikely to be compatible with the external comparer. This makes the array inadequate for use as item in a collection of unsequenced or sequenced sets or bags (ICollection<T> and ISequenced<T>)

Parameters:
comparer:The comparer
SortedArray<T>(int capacity, System.Collections.Generic.IComparer<T> comparer) Create a dynamic sorted array with an external comparer and prescribed initial capacity.

The itemequalityComparer will be a compatible ComparerZeroHashCodeEqualityComparer<T> since the default equalityComparer for T (EqualityComparer<T>.Default) is unlikely to be compatible with the external comparer. This makes the sorted array inadequate for use as item in a collection of unsequenced or sequenced sets or bags (ICollection<T> and ISequenced<T>)

Parameters:
capacity:The capacity
comparer:The comparer
SortedArray<T>(int capacity, System.Collections.Generic.IComparer<T> comparer, System.Collections.Generic.IEqualityComparer<T> equalityComparer) Create a dynamic sorted array with an external comparer, an external item equalityComparer and prescribed initial capacity. This is the constructor to use if the collection will be used as item in a hash table based collection.
Parameters:
capacity:The capacity
comparer:The item comparer
equalityComparer:The item equalityComparer (assumed compatible)

Method details

F bool Add(T item) 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.
Returns:True if item was added.
Parameters:
item:The item to add.
F void AddAll<U>(IEnumerable<U> items) Add the elements from another collection with a more specialized item type to this collection. Since this collection has set semantics, only items not already in the collection will be added.
Type parameters:
UThe type of items to add
Constraints:
U : T
Parameters:
items:The items to add
F void AddSorted<U>(IEnumerable<U> items) Add all the items from another collection with an enumeration order that is increasing in the items. /ThrowsSystem.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.
bool Check() Check the integrity of the internal data structures of this collection. Only avaliable in DEBUG builds???
Returns:True if check does not fail.
void Clear() Remove all items from this collection, resetting internal array size.
object Clone() Make a shallow copy of this SortedArray.
Returns:
F bool Contains(T item) Check if this collection contains (an item equivalent according to the itemequalityComparer) to a particular value.
Returns:True if the items is in this collection.
Parameters:
item:The value to check for.
F bool ContainsAll<U>(IEnumerable<U> items) Check if this collection contains all the values in another collection. Multiplicities are not taken into account.
Type parameters:
U
Constraints:
U : T
Returns:True if all values in itemsis in this collection.
Parameters:
items:The
F int ContainsCount(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.
Returns:The number of copies found (0 or 1).
Parameters:
item:The value to count.
F int CountFrom(T bot) Determine the number of items at or above a supplied threshold.
Returns:The number of matcing items.
Parameters:
bot:The lower bound (inclusive)
F int CountFromTo(T bot, T top) Determine the number of items between two supplied thresholds.
Returns:The number of matcing items.
Parameters:
bot:The lower bound (inclusive)
top:The upper bound (exclusive)
F int CountTo(T top) Determine the number of items below a supplied threshold.
Returns:The number of matcing items.
Parameters:
top:The upper bound (exclusive)
F bool Cut(System.IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid) Perform a search in the sorted collection for the ranges in which a non-increasing (i.e. weakly decrerasing) function from the item type to int is negative, zero respectively positive. If the supplied cut function is not non-increasing, the result of this call is undefined.
Returns:
Parameters:
c:The cut function T to int, given as an IComparable<T> object, where the cut function is the c.CompareTo(T that) method.
low:Returns the largest item in the collection, where the cut function is positive (if any).
lowIsValid: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:True if the cut function is negative somewhere on this collection.
F T DeleteMax() Remove the largest item from this priority queue.
Returns:The removed item.
F T DeleteMin() Remove the least item from this priority queue.
Returns:The removed item.
F bool Find(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.
Returns:True if the items is in this collection.
Parameters:
item:The value to look for.
F IIndexedSorted<T> FindAll(Fun<T,bool> f) Create a new indexed sorted collection consisting of the items of this indexed sorted collection satisfying a certain predicate.
Returns:The new indexed sorted collection.
Parameters:
f:The filter delegate defining the predicate.
F T FindMax() Find the current largest item of this priority queue.
Returns:The largest item.
F T FindMin() Find the current least item of this priority queue.
Returns:The least item.
F bool FindOrAdd(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.
Returns:True if the item was added (hence not found).
Parameters:
item:The value to look for.
F int IndexOf(T item) Searches for an item in the list going forwrds from the start.
Returns:Index of item from start.
Parameters:
item:Item to search for.
ICollectionValue<KeyValuePair<T,int>> ItemMultiplicities()
Returns:
F int LastIndexOf(T item) Searches for an item in the list going backwords from the end.
Returns:Index of of item from the end.
Parameters:
item:Item to search for.
F IIndexedSorted<V> Map<V>(Fun<T,V> m, System.Collections.Generic.IComparer<V> c) Create a new indexed sorted collection consisting of the results of mapping all items of this list. /ThrowsSystem.ArgumentException if the map is not increasing over the items of this collection (with respect to the two given comparison relations).
Returns:The new sorted collection.
Parameters:
m:The delegate definging the map.
c:The comparion relation to use for the result.
F T Predecessor(T item) Find the strict predecessor in the sorted collection of a particular value, i.e. 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.
F IDirectedCollectionValue<T> RangeAll() Create a directed collection with the same items as this collection.
Returns:The result directed collection.
F IDirectedCollectionValue<T> RangeFrom(T bot) Query this sorted collection for items greater than or equal to a supplied value.
Returns:The result directed collection.
Parameters:
bot:The lower bound (inclusive).
F IDirectedCollectionValue<T> RangeFromTo(T bot, T top) Query this sorted collection for items between two supplied values.
Returns:The result directed collection.
Parameters:
bot:The lower bound (inclusive).
top:The upper bound (exclusive).
F IDirectedCollectionValue<T> RangeTo(T top) Query this sorted collection for items less than a supplied value.
Returns:The result directed collection.
Parameters:
top:The upper bound (exclusive).
F bool Remove(T item) Remove a particular item from this collection. If the collection has bag semantics only one copy equivalent to the supplied item is removed.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
F bool Remove(T item, out T removeditem) 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.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
removeditem:The removed value.
F void RemoveAll<U>(IEnumerable<U> items) Remove all items in another collection from this one.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to remove.
F void RemoveAllCopies(T item) Remove all (0 or 1) items equivalent to a given value.
Parameters:
item:The value to remove.
F T RemoveAt(int i) Remove the item at a specific position of the list. /ThrowsSystem.IndexOutOfRangeException if i is negative or >= the size of the collection.
Returns:The removed item.
Parameters:
i:The index of the item to remove.
F void RemoveInterval(int start, int count) Remove all items in an index interval. /ThrowsSystem.IndexOutOfRangeException???.
Parameters:
start:The index of the first item to remove.
count:The number of items to remove.
F void RemoveRangeFrom(T low) Remove all items of this collection above or at a supplied threshold.
Parameters:
low:The lower threshold (inclusive).
F 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).
F void RemoveRangeTo(T hi) Remove all items of this collection below a supplied threshold.
Parameters:
hi:The upper threshold (exclusive).
F void RetainAll<U>(IEnumerable<U> items) Remove all items not in some other collection from this one.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to retain.
F T Successor(T item) Find the strict successor in the sorted collection of a particular value, i.e. 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.
F bool TryPredecessor(T item, out T res) Find the strict predecessor of item in the sorted array, 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.
F bool TrySuccessor(T item, out T res) Find the strict successor of item in the sorted array, 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.
F bool TryWeakPredecessor(T item, out T res) Find the weak predecessor of item in the sorted array, 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.
F bool TryWeakSuccessor(T item, out T res) Find the weak successor of item in the sorted array, 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.
ICollectionValue<T> UniqueItems()
Returns:
F 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 to with a binary copy of the supplied value. If the collection has bag semantics, it is implementation dependent if this updates all equivalent copies in the collection or just one.
Returns:True if the item was found and hence updated.
Parameters:
item:Value to update.
F bool Update(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
F 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.
Returns:True if the item was found and updated (hence not added).
Parameters:
item:Value to add or update.
F bool UpdateOrAdd(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
F T WeakPredecessor(T item) Find the weak predecessor in the sorted collection of a particular value, i.e. the largest item in the collection less than or equal to the supplied value. /ThrowsC5.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.
F T WeakSuccessor(T item) Find the weak successor in the sorted collection of a particular value, i.e. 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.