C5  2.4
The C5 Generic Collection Library for C# and CLI is a comprehensive collection library supporting lists, sets, bags, dictionaries, priority queues, (FIFO) queues, and (LIFO) stacks. C5 runs on .NET 3.5+, Silverlight 5, Windows Phone 8, Xamarin.iOS, Xamarin.Android, and Mono.
C5.TreeBag< T > Class Template Reference

An implementation of Red-Black trees as an indexed, sorted collection with bag semantics, cf. CLRS. (T:C5.TreeBag`1 for an implementation with set semantics).
The comparer (sorting order) may be either natural, because the item type is comparable (generic: T:C5.IComparable`1 or non-generic: System.IComparable) or it can be external and supplied by the user in the constructor.
Each distinct item is only kept in one place in the tree - together with the number of times it is a member of the bag. Thus, if two items that are equal according More...

Inheritance diagram for C5.TreeBag< T >:
C5.SequencedBase< T > C5.IIndexedSorted< T > C5.IPersistentSorted< T > C5.DirectedCollectionBase< T > C5.IDirectedCollectionValue< T > C5.ISorted< T > C5.IIndexed< T > C5.ISorted< T > C5.ISequenced< T > C5.ISequenced< T > C5.ISequenced< T > C5.IDirectedEnumerable< T > C5.ICollectionValue< T > C5.IDirectedCollectionValue< T > C5.CollectionBase< T >

Classes

class  Enumerator
 An enumerator for a red-black tree collection. Based on an explicit stack of subtrees waiting to be enumerated. Currently only used for the tree set enumerators (tree bag enumerators use an iterator block based enumerator).
 
class  Range
 
class  SnapEnumerator
 An enumerator for a snapshot of a node copy persistent red-black tree collection.
 

Public Member Functions

 TreeBag ()
 Create a red-black tree collection with natural comparer and item equalityComparer. We assume that if More...
 
 TreeBag (SCG.IComparer< T > comparer)
 Create a red-black tree collection with an external comparer. More...
 
 TreeBag (SCG.IComparer< T > comparer, SCG.IEqualityComparer< T > equalityComparer)
 Create a red-black tree collection with an external comparer and an external item equalityComparer, assumed consistent. More...
 
override T Choose ()
 
override SCG.IEnumerator< T > GetEnumerator ()
 Create an enumerator for this tree More...
 
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. More...
 
void AddAll (SCG.IEnumerable< T > items)
 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. More...
 
void AddSorted (SCG.IEnumerable< T > items)
 Add all the items from another collection with an enumeration order that is increasing in the items. More...
 
bool Contains (T item)
 Check if this collection contains (an item equivalent to according to the itemequalityComparer) a particular value. More...
 
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. More...
 
bool FindOrAdd (ref T item)
 Find or add the item to the tree. If the tree does not contain an item equivalent to this item add it, else return the existing one in the ref argument. More...
 
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, this updates all equivalent copies in the collection. More...
 
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 with a binary copy of the supplied value. If the collection has bag semantics, this updates all equivalent copies in the collection. More...
 
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 with a binary copy of the supplied value; else add the value to the collection. More...
 
bool UpdateOrAdd (T item, out T olditem)
 
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. More...
 
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. More...
 
void Clear ()
 Remove all items from this collection. More...
 
void RemoveAll (SCG.IEnumerable< T > items)
 Remove all items in another collection from this one. If this collection has bag semantics, take multiplicities into account. More...
 
void RetainAll (SCG.IEnumerable< T > items)
 Remove all items not in some other collection from this one. If this collection has bag semantics, take multiplicities into account. More...
 
bool ContainsAll (SCG.IEnumerable< T > items)
 Check if this collection contains all the values in another collection. If this collection has bag semantics ( More...
 
IIndexedSorted< T > FindAll (Func< T, bool > filter)
 Create a new indexed sorted collection consisting of the items of this indexed sorted collection satisfying a certain predicate. More...
 
IIndexedSorted< V > Map< V > (Func< T, V > mapper, SCG.IComparer< V > c)
 Create a new indexed sorted collection consisting of the results of mapping all items of this list.

Exceptions
ArgumentExceptionif the map is not increasing over the items of this collection (with respect to the two given comparison relations).
More...
 
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. More...
 
virtual ICollectionValue< T > UniqueItems ()
 
virtual ICollectionValue< KeyValuePair< T, int > > ItemMultiplicities ()
 
void RemoveAllCopies (T item)
 Remove all items equivalent to a given value. More...
 
int IndexOf (T item)
 Searches for an item in this indexed collection going forwards from the start. More...
 
int LastIndexOf (T item)
 Searches for an item in the tree going backwards from the end. More...
 
RemoveAt (int i)
 Remove the item at a specific position of the list.

Exceptions
IndexOutOfRangeExceptionif i is negative or >= the size of the collection.
More...
 
void RemoveInterval (int start, int count)
 Remove all items in an index interval.

Exceptions
IndexOutOfRangeException???.
More...
 
override IDirectedCollectionValue< T > Backwards ()
 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 More...
 
FindMin ()
 Find the current least item of this priority queue. More...
 
DeleteMin ()
 Remove the least item from this priority queue. More...
 
FindMax ()
 Find the current largest item of this priority queue. More...
 
DeleteMax ()
 Remove the largest item from this priority queue. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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.

Exceptions
NoSuchItemExceptionif no such element exists (the supplied value is greater than the maximum of this collection.)
More...
 
IDirectedCollectionValue< T > RangeFrom (T bot)
 Query this sorted collection for items greater than or equal to a supplied value. More...
 
IDirectedCollectionValue< T > RangeFromTo (T bot, T top)
 Query this sorted collection for items between two supplied values. More...
 
IDirectedCollectionValue< T > RangeTo (T top)
 Query this sorted collection for items less than a supplied value. More...
 
IDirectedCollectionValue< T > RangeAll ()
 Create a directed collection with the same items as this collection. More...
 
bool Cut (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 decreasing) function from the item type to More...
 
int CountFrom (T bot)
 Determine the number of items at or above a supplied threshold. More...
 
int CountFromTo (T bot, T top)
 Determine the number of items between two supplied thresholds. More...
 
int CountTo (T top)
 Determine the number of items below a supplied threshold. More...
 
void RemoveRangeFrom (T low)
 Remove all items of this collection above or at a supplied threshold. More...
 
void RemoveRangeFromTo (T low, T hi)
 Remove all items of this collection between two supplied thresholds. More...
 
void RemoveRangeTo (T hi)
 Remove all items of this collection below a supplied threshold. More...
 
void Dispose ()
 If this tree is a snapshot, remove registration in base tree More...
 
ISorted< T > Snapshot ()
 Make a (read-only) snapshot of this collection. More...
 
void dump ()
 Print the tree structure to the console stdout. More...
 
void dump (string msg)
 Print the tree structure to the console stdout. More...
 
bool Check (string name)
 Checks red-black invariant. Dumps tree to console if bad More...
 
bool Check ()
 Checks red-black invariant. Dumps tree to console if bad More...
 
- Public Member Functions inherited from C5.SequencedBase< T >
virtual int GetSequencedHashCode ()
 Get the sequenced collection hash code of this collection: from the cached value if present and up to date, else (re)compute. More...
 
virtual bool SequencedEquals (ISequenced< T > otherCollection)
 Check if the contents of that is equal to the contents of this in the sequenced sense. Using the item equalityComparer of this collection. More...
 
int FindIndex (Func< T, bool > predicate)
 Check if there exists an item that satisfies a specific predicate in this collection and return the index of the first one. More...
 
int FindLastIndex (Func< T, bool > predicate)
 Check if there exists an item that satisfies a specific predicate in this collection and return the index of the last one. More...
 
- Public Member Functions inherited from C5.DirectedCollectionBase< T >
virtual bool FindLast (Func< T, bool > predicate, out T item)
 Check if there exists an item that satisfies a specific predicate in this collection and return the first one in enumeration order. More...
 
- Public Member Functions inherited from C5.CollectionBase< T >
virtual int GetUnsequencedHashCode ()
 Get the unsequenced collection hash code of this collection: from the cached value if present and up to date, else (re)compute. More...
 
virtual bool UnsequencedEquals (ICollection< T > otherCollection)
 Check if the contents of otherCollection is equal to the contents of this in the unsequenced sense. Uses the item equality comparer of this collection More...
 
- Public Member Functions inherited from C5.CollectionValueBase< T >
virtual void CopyTo (T[] array, int index)
 Copy the items of this collection to part of an array. More...
 
virtual T[] ToArray ()
 Create an array with the items of this collection (in the same order as an enumerator would output them). More...
 
virtual void Apply (Action< T > action)
 Apply an single argument action, T:Action`1 to this enumerable More...
 
virtual bool Exists (Func< T, bool > predicate)
 Check if there exists an item that satisfies a specific predicate in this collection. More...
 
virtual bool Find (Func< T, bool > predicate, out T item)
 Check if there exists an item that satisfies a specific predicate in this collection and return the first one in enumeration order. More...
 
virtual bool All (Func< T, bool > predicate)
 Check if all items in this collection satisfies a specific predicate. More...
 
virtual SCG.IEnumerable< T > Filter (Func< T, bool > predicate)
 Create an enumerable, enumerating the items of this collection that satisfies a certain condition. More...
 
virtual bool Show (System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
 
virtual string ToString (string format, IFormatProvider formatProvider)
 
override string ToString ()
 
- Public Member Functions inherited from C5.IShowable
bool Show (StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
 Format More...
 
- Public Member Functions inherited from C5.ISequenced< T >
int GetSequencedHashCode ()
 The hashcode is defined as More...
 
bool SequencedEquals (ISequenced< T > otherCollection)
 Compare this sequenced collection to another one in sequence order. More...
 
- Public Member Functions inherited from C5.ICollection< T >
new void CopyTo (T[] array, int index)
 Copy the items of this collection to a contiguous part of an array. More...
 
int GetUnsequencedHashCode ()
 The unordered collection hashcode is defined as the sum of More...
 
bool UnsequencedEquals (ICollection< T > otherCollection)
 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. More...
 
- Public Member Functions inherited from C5.IIndexed< T >
int FindIndex (Func< T, bool > predicate)
 Check if there exists an item that satisfies a specific predicate in this collection and return the index of the first one. More...
 
int FindLastIndex (Func< T, bool > predicate)
 Check if there exists an item that satisfies a specific predicate in this collection and return the index of the last one. More...
 

Public Attributes

int uniqueCount = 0
 

Properties

override EventTypeEnum ListenableEvents [get]
 
bool AllowsDuplicates [get]
 
virtual bool DuplicatesByCounting [get]
 By convention this is true for any collection with set semantics. More...
 
Speed ContainsSpeed [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). More...
 
this[int i] [get]
 
Exceptions
IndexOutOfRangeExceptionif i is negative or >= the size of the collection.
More...
 
virtual Speed IndexingSpeed [get]
 
IDirectedCollectionValue< T > this[int start, int count] [get]
 
Exceptions
IndexOutOfRangeException.
More...
 
SCG.IComparer< T > Comparer [get]
 The comparer object supplied at creation time for this collection More...
 
- Properties inherited from C5.SequencedBase< T >
override EnumerationDirection Direction [get]
 
- Properties inherited from C5.DirectedCollectionBase< T >
virtual EnumerationDirection Direction [get]
 
- Properties inherited from C5.CollectionBase< T >
virtual bool IsReadOnly [get]
 
override int Count [get]
 
override Speed CountSpeed [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). More...
 
virtual SCG.IEqualityComparer< T > EqualityComparer [get]
 
override bool IsEmpty [get]
 
- Properties inherited from C5.CollectionValueBase< T >
virtual EventTypeEnum ListenableEvents [get]
 
virtual EventTypeEnum ActiveEvents [get]
 A flag bitmap of the events currently subscribed to by this collection. More...
 
virtual CollectionChangedHandler< T > CollectionChanged
 The change event. Will be raised for every change operation on the collection. More...
 
virtual CollectionClearedHandler< T > CollectionCleared
 The clear event. Will be raised for every Clear operation on the collection. More...
 
virtual ItemsAddedHandler< T > ItemsAdded
 The item added event. Will be raised for every individual addition to the collection. More...
 
virtual ItemsRemovedHandler< T > ItemsRemoved
 The item removed event. Will be raised for every individual removal from the collection. More...
 
virtual ItemInsertedHandler< T > ItemInserted
 The item added event. Will be raised for every individual addition to the collection. More...
 
virtual ItemRemovedAtHandler< T > ItemRemovedAt
 The item removed event. Will be raised for every individual removal from the collection. More...
 
abstract bool IsEmpty [get]
 Check if collection is empty. More...
 
abstract int Count [get]
 The number of items in this collection. More...
 
abstract Speed CountSpeed [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). More...
 
- Properties inherited from C5.ICollectionValue< T >
EventTypeEnum ListenableEvents [get]
 A flag bitmap of the events subscribable to by this collection. More...
 
EventTypeEnum ActiveEvents [get]
 A flag bitmap of the events currently subscribed to by this collection. More...
 
bool IsEmpty [get]
 
int Count [get]
 
Speed CountSpeed [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). More...
 
- Properties inherited from C5.IDirectedEnumerable< T >
EnumerationDirection Direction [get]
 
- Properties inherited from C5.ISorted< T >
SCG.IComparer< T > Comparer [get]
 The comparer object supplied at creation time for this sorted collection. More...
 
- Properties inherited from C5.ICollection< T >
Speed ContainsSpeed [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). More...
 
new int Count [get]
 
new bool IsReadOnly [get]
 If true any call of an updating operation will throw an More...
 
- Properties inherited from C5.IExtensible< T >
bool IsReadOnly [get]
 If true any call of an updating operation will throw an More...
 
bool AllowsDuplicates [get]
 
SCG.IEqualityComparer< T > EqualityComparer [get]
 (Here should be a discussion of the role of equalityComparers. Any ). More...
 
bool DuplicatesByCounting [get]
 By convention this is true for any collection with set semantics. More...
 
- Properties inherited from C5.IIndexed< T >
Speed IndexingSpeed [get]
 
IDirectedCollectionValue< T > this[int start, int count] [get]
 

Additional Inherited Members

- Static Public Member Functions inherited from C5.SequencedBase< T >
static int ComputeHashCode (ISequenced< T > items, SCG.IEqualityComparer< T > itemequalityComparer)
 Compute the unsequenced hash code of a collection More...
 
static bool StaticEquals (ISequenced< T > collection1, ISequenced< T > collection2, SCG.IEqualityComparer< T > itemequalityComparer)
 Examine if tit and tat are equal as sequenced collections using the specified item equalityComparer (assumed compatible with the two collections). More...
 
- Static Public Member Functions inherited from C5.CollectionBase< T >
static int ComputeHashCode (ICollectionValue< T > items, SCG.IEqualityComparer< T > itemequalityComparer)
 Compute the unsequenced hash code of a collection More...
 
static bool StaticEquals (ICollection< T > collection1, ICollection< T > collection2, SCG.IEqualityComparer< T > itemequalityComparer)
 Examine if collection1 and collection2 are equal as unsequenced collections using the specified item equalityComparer (assumed compatible with the two collections). More...
 
- Protected Member Functions inherited from C5.SequencedBase< T >
 SequencedBase (SCG.IEqualityComparer< T > itemequalityComparer)
 
- Protected Member Functions inherited from C5.DirectedCollectionBase< T >
 DirectedCollectionBase (SCG.IEqualityComparer< T > itemequalityComparer)
 
- Protected Member Functions inherited from C5.CollectionBase< T >
 CollectionBase (SCG.IEqualityComparer< T > itemequalityComparer)
 
void checkRange (int start, int count)
 Utility method for range checking. More...
 
virtual void modifycheck (int thestamp)
 Check if the collection has been modified since a specified time, expressed as a stamp value. More...
 
virtual void updatecheck ()
 Check if it is valid to perform update operations, and if so increment stamp. More...
 
- Protected Member Functions inherited from C5.CollectionValueBase< T >
virtual void raiseCollectionChanged ()
 Fire the CollectionChanged event More...
 
virtual void raiseCollectionCleared (bool full, int count)
 Fire the CollectionCleared event More...
 
virtual void raiseCollectionCleared (bool full, int count, int?offset)
 Fire the CollectionCleared event More...
 
virtual void raiseItemsAdded (T item, int count)
 Fire the ItemsAdded event More...
 
virtual void raiseItemsRemoved (T item, int count)
 Fire the ItemsRemoved event More...
 
virtual void raiseItemInserted (T item, int index)
 Fire the ItemInserted event More...
 
virtual void raiseItemRemovedAt (T item, int index)
 Fire the ItemRemovedAt event More...
 
virtual void raiseForSetThis (int index, T value, T item)
 
virtual void raiseForInsert (int i, T item)
 
void raiseForRemove (T item)
 
void raiseForRemove (T item, int count)
 
void raiseForRemoveAt (int index, T item)
 
virtual void raiseForUpdate (T newitem, T olditem)
 
virtual void raiseForUpdate (T newitem, T olditem, int count)
 
virtual void raiseForAdd (T item)
 
virtual void raiseForRemoveAll (ICollectionValue< T > wasRemoved)
 
- Static Protected Member Functions inherited from C5.EnumerableBase< T >
static int countItems (SCG.IEnumerable< T > items)
 Count the number of items in an enumerable by enumeration More...
 
- Protected Attributes inherited from C5.CollectionBase< T >
bool isReadOnlyBase = false
 The underlying field of the ReadOnly property More...
 
int stamp
 The current stamp value More...
 
int size
 The number of items in the collection More...
 
readonly SCG.IEqualityComparer< T > itemequalityComparer
 The item equalityComparer of the collection More...
 
- Events inherited from C5.ICollectionValue< T >
CollectionChangedHandler< T > CollectionChanged
 The change event. Will be raised for every change operation on the collection. More...
 
CollectionClearedHandler< T > CollectionCleared
 The change event. Will be raised for every clear operation on the collection. More...
 
ItemsAddedHandler< T > ItemsAdded
 The item added event. Will be raised for every individual addition to the collection. More...
 
ItemInsertedHandler< T > ItemInserted
 The item inserted event. Will be raised for every individual insertion to the collection. More...
 
ItemsRemovedHandler< T > ItemsRemoved
 The item removed event. Will be raised for every individual removal from the collection. More...
 
ItemRemovedAtHandler< T > ItemRemovedAt
 The item removed at event. Will be raised for every individual removal at from the collection. More...
 

Detailed Description

An implementation of Red-Black trees as an indexed, sorted collection with bag semantics, cf. CLRS. (T:C5.TreeBag`1 for an implementation with set semantics).
The comparer (sorting order) may be either natural, because the item type is comparable (generic: T:C5.IComparable`1 or non-generic: System.IComparable) or it can be external and supplied by the user in the constructor.
Each distinct item is only kept in one place in the tree - together with the number of times it is a member of the bag. Thus, if two items that are equal according

Constructor & Destructor Documentation

C5.TreeBag< T >.TreeBag ( )

Create a red-black tree collection with natural comparer and item equalityComparer. We assume that if

T is comparable, its default equalityComparer will be compatible with the comparer.

Exceptions
NotComparableExceptionIf
T
is not comparable.
C5.TreeBag< T >.TreeBag ( SCG.IComparer< T >  comparer)

Create a red-black tree collection with an external comparer.

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

Parameters
comparerThe external comparer
C5.TreeBag< T >.TreeBag ( SCG.IComparer< T >  comparer,
SCG.IEqualityComparer< T >  equalityComparer 
)

Create a red-black tree collection with an external comparer and an external item equalityComparer, assumed consistent.

Parameters
comparerThe external comparer
equalityComparerThe external item equalitySCG.Comparer

Member Function Documentation

bool C5.TreeBag< T >.Add ( 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.

Parameters
itemThe item to add.
Returns
True if item was added.

Implements C5.ICollection< T >.

void C5.TreeBag< T >.AddAll ( SCG.IEnumerable< T >  items)

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.

Parameters
itemsThe items to add

Implements C5.IExtensible< T >.

void C5.TreeBag< T >.AddSorted ( SCG.IEnumerable< T >  items)

Add all the items from another collection with an enumeration order that is increasing in the items.

The idea is that the implementation may use a faster algorithm to merge the two collections.

Exceptions
ArgumentExceptionif the enumerated items turns out not to be in increasing order.
Parameters
itemsThe collection to add.

Implements C5.ISorted< T >.

override IDirectedCollectionValue<T> C5.TreeBag< T >.Backwards ( )
virtual

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()) {...}

Returns
The backwards collection.

Implements C5.DirectedCollectionBase< T >.

bool C5.TreeBag< T >.Check ( string  name)

Checks red-black invariant. Dumps tree to console if bad

Parameters
nameTitle of dump
Returns
false if invariant violation
bool C5.TreeBag< T >.Check ( )

Checks red-black invariant. Dumps tree to console if bad

Returns
false if invariant violation

Implements C5.IExtensible< T >.

override T C5.TreeBag< T >.Choose ( )

Exceptions
NoSuchItemExceptionIf tree is empty
Returns

Implements C5.ICollectionValue< T >.

void C5.TreeBag< T >.Clear ( )

Remove all items from this collection.

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.Contains ( item)

Check if this collection contains (an item equivalent to according to the itemequalityComparer) a particular value.

Parameters
itemThe value to check for.
Returns
True if the items is in this collection.

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.ContainsAll ( SCG.IEnumerable< T >  items)

Check if 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.

Parameters
itemsThe
Returns
True if all values in
items
is in this collection.

Implements C5.ICollection< T >.

int C5.TreeBag< T >.ContainsCount ( 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.

Parameters
itemThe value to count.
Returns
The number of copies found.

Implements C5.ICollection< T >.

int C5.TreeBag< T >.CountFrom ( bot)

Determine the number of items at or above a supplied threshold.

Parameters
botThe lower bound (inclusive)
Returns
The number of matching items.

Implements C5.IIndexedSorted< T >.

int C5.TreeBag< T >.CountFromTo ( bot,
top 
)

Determine the number of items between two supplied thresholds.

Parameters
botThe lower bound (inclusive)
topThe upper bound (exclusive)
Returns
The number of matching items.

Implements C5.IIndexedSorted< T >.

int C5.TreeBag< T >.CountTo ( top)

Determine the number of items below a supplied threshold.

Parameters
topThe upper bound (exclusive)
Returns
The number of matching items.

Implements C5.IIndexedSorted< T >.

bool C5.TreeBag< T >.Cut ( 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 decreasing) 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.

Parameters
cThe cut function
T
to
int
, given as an
IComparable<T>
object, where the cut function is the
c.CompareTo(T that)
method.
lowReturns the largest item in the collection, where the cut function is positive (if any).
lowIsValidTrue if the cut function is positive somewhere on this collection.
highReturns the least item in the collection, where the cut function is negative (if any).
highIsValidTrue if the cut function is negative somewhere on this collection.
Returns

Implements C5.ISorted< T >.

T C5.TreeBag< T >.DeleteMax ( )

Remove the largest item from this priority queue.

Returns
The removed item.

Implements C5.ISorted< T >.

T C5.TreeBag< T >.DeleteMin ( )

Remove the least item from this priority queue.

Returns
The removed item.

Implements C5.ISorted< T >.

void C5.TreeBag< T >.Dispose ( )

If this tree is a snapshot, remove registration in base tree

void C5.TreeBag< T >.dump ( )

Print the tree structure to the console stdout.

void C5.TreeBag< T >.dump ( string  msg)

Print the tree structure to the console stdout.

bool C5.TreeBag< T >.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.

Parameters
itemThe value to look for.
Returns
True if the items is in this collection.

Implements C5.ICollection< T >.

IIndexedSorted<T> C5.TreeBag< T >.FindAll ( Func< T, bool >  filter)

Create a new indexed sorted collection consisting of the items of this indexed sorted collection satisfying a certain predicate.

Parameters
filterThe filter delegate defining the predicate.
Returns
The new indexed sorted collection.

Implements C5.IIndexedSorted< T >.

T C5.TreeBag< T >.FindMax ( )

Find the current largest item of this priority queue.

Returns
The largest item.

Implements C5.ISorted< T >.

T C5.TreeBag< T >.FindMin ( )

Find the current least item of this priority queue.

Returns
The least item.

Implements C5.ISorted< T >.

bool C5.TreeBag< T >.FindOrAdd ( ref T  item)

Find or add the item to the tree. If the tree does not contain an item equivalent to this item add it, else return the existing one in the ref argument.

Parameters
item
Returns
True if item was found

Implements C5.ICollection< T >.

override SCG.IEnumerator<T> C5.TreeBag< T >.GetEnumerator ( )
virtual

Create an enumerator for this tree

Returns
The enumerator

Implements C5.SequencedBase< T >.

int C5.TreeBag< T >.IndexOf ( item)

Searches for an item in this indexed collection going forwards from the start.

Parameters
itemItem to search for.
Returns
Index of first occurrence from start of the item if found, else the two-complement (always negative) of the index at which the item would be put if it was added.

Implements C5.IIndexed< T >.

virtual ICollectionValue<KeyValuePair<T, int> > C5.TreeBag< T >.ItemMultiplicities ( )
virtual

Returns

Implements C5.ICollection< T >.

int C5.TreeBag< T >.LastIndexOf ( item)

Searches for an item in the tree going backwards from the end.

Parameters
itemItem to search for.
Returns
Index of last occurrence from the end of item if found, else the two-complement (always negative) of the index at which the item would be put if it was added.

Implements C5.IIndexed< T >.

IIndexedSorted<V> C5.TreeBag< T >.Map< V > ( Func< T, V >  mapper,
SCG.IComparer< V >  c 
)

Create a new indexed sorted collection consisting of the results of mapping all items of this list.

Exceptions
ArgumentExceptionif the map is not increasing over the items of this collection (with respect to the two given comparison relations).

Parameters
mapperThe delegate definging the map.
cThe comparion relation to use for the result.
Returns
The new sorted collection.

Implements C5.IIndexedSorted< T >.

T C5.TreeBag< T >.Predecessor ( 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.

Exceptions
NoSuchItemExceptionif no such element exists (the supplied value is less than or equal to the minimum of this collection.)
Parameters
itemThe item to find the predecessor for.
Returns
The predecessor.

Implements C5.ISorted< T >.

IDirectedCollectionValue<T> C5.TreeBag< T >.RangeAll ( )

Create a directed collection with the same items as this collection.

Returns
The result directed collection.

Implements C5.ISorted< T >.

IDirectedCollectionValue<T> C5.TreeBag< T >.RangeFrom ( bot)

Query this sorted collection for items greater than or equal to a supplied value.

Parameters
botThe lower bound (inclusive).
Returns
The result directed collection.

Implements C5.IIndexedSorted< T >.

IDirectedCollectionValue<T> C5.TreeBag< T >.RangeFromTo ( bot,
top 
)

Query this sorted collection for items between two supplied values.

Parameters
botThe lower bound (inclusive).
topThe upper bound (exclusive).
Returns
The result directed collection.

Implements C5.IIndexedSorted< T >.

IDirectedCollectionValue<T> C5.TreeBag< T >.RangeTo ( top)

Query this sorted collection for items less than a supplied value.

Parameters
topThe upper bound (exclusive).
Returns
The result directed collection.

Implements C5.IIndexedSorted< T >.

bool C5.TreeBag< T >.Remove ( item)

Remove a particular item from this collection. If the collection has bag semantics only one copy equivalent to the supplied item is removed.

Parameters
itemThe value to remove.
Returns
True if the item was found (and removed).

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.Remove ( 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.

Parameters
itemThe value to remove.
removeditemThe removed value.
Returns
True if the item was found (and removed).

Implements C5.ICollection< T >.

void C5.TreeBag< T >.RemoveAll ( SCG.IEnumerable< T >  items)

Remove all items in another collection from this one. If this collection has bag semantics, take multiplicities into account.

Parameters
itemsThe items to remove.

Implements C5.ICollection< T >.

void C5.TreeBag< T >.RemoveAllCopies ( item)

Remove all items equivalent to a given value.

Parameters
itemThe value to remove.

Implements C5.ICollection< T >.

T C5.TreeBag< T >.RemoveAt ( int  i)

Remove the item at a specific position of the list.

Exceptions
IndexOutOfRangeExceptionif i is negative or >= the size of the collection.

Parameters
iThe index of the item to remove.
Returns
The removed item.

Implements C5.IIndexed< T >.

void C5.TreeBag< T >.RemoveInterval ( int  start,
int  count 
)

Remove all items in an index interval.

Exceptions
IndexOutOfRangeException???.

Parameters
startThe index of the first item to remove.
countThe number of items to remove.

Implements C5.IIndexed< T >.

void C5.TreeBag< T >.RemoveRangeFrom ( low)

Remove all items of this collection above or at a supplied threshold.

Parameters
lowThe lower threshold (inclusive).

Implements C5.ISorted< T >.

void C5.TreeBag< T >.RemoveRangeFromTo ( low,
hi 
)

Remove all items of this collection between two supplied thresholds.

Parameters
lowThe lower threshold (inclusive).
hiThe upper threshold (exclusive).

Implements C5.ISorted< T >.

void C5.TreeBag< T >.RemoveRangeTo ( hi)

Remove all items of this collection below a supplied threshold.

Parameters
hiThe upper threshold (exclusive).

Implements C5.ISorted< T >.

void C5.TreeBag< T >.RetainAll ( SCG.IEnumerable< T >  items)

Remove all items not in some other collection from this one. If this collection has bag semantics, take multiplicities into account.

Parameters
itemsThe items to retain.

Implements C5.ICollection< T >.

ISorted<T> C5.TreeBag< T >.Snapshot ( )

Make a (read-only) snapshot of this collection.

Returns
The snapshot.

Implements C5.IPersistentSorted< T >.

T C5.TreeBag< T >.Successor ( 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.

Exceptions
NoSuchItemExceptionif no such element exists (the supplied value is greater than or equal to the maximum of this collection.)
Parameters
itemThe item to find the successor for.
Returns
The successor.

Implements C5.ISorted< T >.

bool C5.TreeBag< T >.TryPredecessor ( 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.

Parameters
itemThe item to find the predecessor for.
resThe predecessor, if any; otherwise the default value for T.
Returns
True if item has a predecessor; otherwise false.

Implements C5.ISorted< T >.

bool C5.TreeBag< T >.TrySuccessor ( 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.

Parameters
itemThe item to find the successor for.
resThe successor, if any; otherwise the default value for T.
Returns
True if item has a successor; otherwise false.

Implements C5.ISorted< T >.

bool C5.TreeBag< T >.TryWeakPredecessor ( 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.

Parameters
itemThe item to find the weak predecessor for.
resThe weak predecessor, if any; otherwise the default value for T.
Returns
True if item has a weak predecessor; otherwise false.

Implements C5.ISorted< T >.

bool C5.TreeBag< T >.TryWeakSuccessor ( 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.

Parameters
itemThe item to find the weak successor for.
resThe weak successor, if any; otherwise the default value for T.
Returns
True if item has a weak successor; otherwise false.

Implements C5.ISorted< T >.

virtual ICollectionValue<T> C5.TreeBag< T >.UniqueItems ( )
virtual

Returns

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.Update ( 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, this updates all equivalent copies in the collection.

Parameters
itemValue to update.
Returns
True if the item was found and hence updated.

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.Update ( 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 with a binary copy of the supplied value. If the collection has bag semantics, this updates all equivalent copies in the collection.

Parameters
item
olditem
Returns

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.UpdateOrAdd ( 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; else add the value to the collection.

NOTE: the bag implementation is currently wrong! ?????

Parameters
itemValue to add or update.
Returns
True if the item was found and updated (hence not added).

Implements C5.ICollection< T >.

bool C5.TreeBag< T >.UpdateOrAdd ( item,
out T  olditem 
)

Parameters
item
olditem
Returns

Implements C5.ICollection< T >.

T C5.TreeBag< T >.WeakPredecessor ( 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.

Exceptions
NoSuchItemExceptionif no such element exists (the supplied value is less than the minimum of this collection.)
Parameters
itemThe item to find the weak predecessor for.
Returns
The weak predecessor.

Implements C5.ISorted< T >.

T C5.TreeBag< T >.WeakSuccessor ( 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.

Exceptions
NoSuchItemExceptionif no such element exists (the supplied value is greater than the maximum of this collection.)

Parameters
itemThe item to find the weak successor for.
Returns
The weak successor.

Implements C5.ISorted< T >.

Member Data Documentation

int C5.TreeBag< T >.uniqueCount = 0

Property Documentation

bool C5.TreeBag< T >.AllowsDuplicates
get

True since this collection has bag semantics.

SCG.IComparer<T> C5.TreeBag< T >.Comparer
get

The comparer object supplied at creation time for this collection

The comparer

Speed C5.TreeBag< T >.ContainsSpeed
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).

Speed.Log

virtual bool C5.TreeBag< T >.DuplicatesByCounting
get

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.

virtual Speed C5.TreeBag< T >.IndexingSpeed
get

override EventTypeEnum C5.TreeBag< T >.ListenableEvents
get

T C5.TreeBag< T >.this[int i]
get

Exceptions
IndexOutOfRangeExceptionif i is negative or >= the size of the collection.

The i'th item of this list.

Parameters
ithe index to lookup
IDirectedCollectionValue<T> C5.TreeBag< T >.this[int start, int count]
get

Exceptions
IndexOutOfRangeException.

The directed collection of items in a specific index interval.

Parameters
startThe starting index of the interval (inclusive).
countThe length of the interval.

The documentation for this class was generated from the following file: