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.IntervalHeap< T > Class Template Reference

A priority queue class based on an interval heap data structure. More...

Inheritance diagram for C5.IntervalHeap< T >:
C5.CollectionValueBase< T > C5.IPriorityQueue< T > C5.EnumerableBase< T > C5.ICollectionValue< T > C5.IShowable C5.IExtensible< T > C5.IShowable C5.ICollectionValue< T > C5.IShowable

Public Member Functions

 IntervalHeap ()
 Create an interval heap with natural item comparer and default initial capacity (16) More...
 
 IntervalHeap (SCG.IComparer< T > comparer)
 Create an interval heap with external item comparer and default initial capacity (16) More...
 
 IntervalHeap (int capacity)
 Create an interval heap with natural item comparer and prescribed initial capacity More...
 
 IntervalHeap (int capacity, SCG.IComparer< T > comparer)
 Create an interval heap with external item comparer and prescribed initial capacity More...
 
FindMin ()
 Find the current least item of this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty
More...
 
DeleteMin ()
 Remove the least item from this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty
More...
 
FindMax ()
 Find the current largest item of this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty
More...
 
DeleteMax ()
 Remove the largest item from this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty
More...
 
bool Add (T item)
 Add an item to this priority queue. More...
 
void AddAll (SCG.IEnumerable< T > items)
 Add the elements from another collection with a more specialized item type to this collection. More...
 
override T Choose ()
 Choose some item of this collection. More...
 
override SCG.IEnumerator< T > GetEnumerator ()
 Create an enumerator for the collection More...
 
bool Check ()
 Check the integrity of the internal data structures of this collection. Only available in DEBUG builds??? More...
 
bool Find (IPriorityQueueHandle< T > handle, out T item)
 Check safely if a handle is valid for this queue and if so, report the corresponding queue item. More...
 
bool Add (ref IPriorityQueueHandle< T > handle, T item)
 Add an item to the priority queue, receiving a handle for the item in the queue, or reusing an already existing handle. More...
 
Delete (IPriorityQueueHandle< T > handle)
 Delete an item with a handle from a priority queue. More...
 
Replace (IPriorityQueueHandle< T > handle, T item)
 Replace an item with a handle in a priority queue with a new item. Typically used for changing the priority of some queued object. More...
 
FindMin (out IPriorityQueueHandle< T > handle)
 Find the current least item of this priority queue. More...
 
FindMax (out IPriorityQueueHandle< T > handle)
 Find the current largest item of this priority queue. More...
 
DeleteMin (out IPriorityQueueHandle< T > handle)
 Remove the least item from this priority queue. More...
 
DeleteMax (out IPriorityQueueHandle< T > handle)
 Remove the largest item from this priority queue. 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...
 

Properties

override EventTypeEnum ListenableEvents [get]
 
SCG.IComparer< T > Comparer [get]
 The comparer object supplied at creation time for this collection More...
 
bool IsReadOnly [get]
 If true any call of an updating operation will throw an More...
 
bool AllowsDuplicates [get]
 
virtual SCG.IEqualityComparer< T > EqualityComparer [get]
 Value is null since this collection has no equality concept for its items. More...
 
virtual bool DuplicatesByCounting [get]
 By convention this is true for any collection with set semantics. More...
 
override bool IsEmpty [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...
 
this[IPriorityQueueHandle< T > handle] [get, set]
 Get or set the item corresponding to a handle. More...
 
- 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.IPriorityQueue< T >
SCG.IComparer< T > Comparer [get]
 The comparer object supplied at creation time for this collection More...
 
this[IPriorityQueueHandle< T > handle] [get, set]
 Get or set the item corresponding to a handle. Throws exceptions on invalid handles. 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...
 

Additional Inherited Members

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

A priority queue class based on an interval heap data structure.

Template Parameters
TThe item type

Constructor & Destructor Documentation

Create an interval heap with natural item comparer and default initial capacity (16)

C5.IntervalHeap< T >.IntervalHeap ( SCG.IComparer< T >  comparer)

Create an interval heap with external item comparer and default initial capacity (16)

Parameters
comparerThe external comparer
C5.IntervalHeap< T >.IntervalHeap ( int  capacity)

Create an interval heap with natural item comparer and prescribed initial capacity

Parameters
capacityThe initial capacity
C5.IntervalHeap< T >.IntervalHeap ( int  capacity,
SCG.IComparer< T >  comparer 
)

Create an interval heap with external item comparer and prescribed initial capacity

Parameters
comparerThe external comparer
capacityThe initial capacity

Member Function Documentation

bool C5.IntervalHeap< T >.Add ( item)

Add an item to this priority queue.

Parameters
itemThe item to add.
Returns
True

Implements C5.IExtensible< T >.

bool C5.IntervalHeap< T >.Add ( ref IPriorityQueueHandle< T >  handle,
item 
)

Add an item to the priority queue, receiving a handle for the item in the queue, or reusing an already existing handle.

Parameters
handleOn output: a handle for the added item. On input: null for allocating a new handle, an invalid 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.
itemThe item to add.
Returns
True since item will always be added unless the call throws an exception.

Implements C5.IPriorityQueue< T >.

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

Add the elements from another collection with a more specialized item type to this collection.

Parameters
itemsThe items to add

Implements C5.IExtensible< T >.

bool C5.IntervalHeap< T >.Check ( )

Check the integrity of the internal data structures of this collection. Only available in DEBUG builds???

Returns
True if check does not fail.

Implements C5.IExtensible< T >.

override T C5.IntervalHeap< T >.Choose ( )
virtual

Choose some item of this collection.

Exceptions
NoSuchItemExceptionif collection is empty.
Returns

Implements C5.CollectionValueBase< T >.

T C5.IntervalHeap< T >.Delete ( IPriorityQueueHandle< T >  handle)

Delete an item with a handle from a priority queue.

Exceptions
InvalidPriorityQueueHandleExceptionif the handle is invalid
Parameters
handleThe handle for the item. The handle will be invalidated, but reusable.
Returns
The deleted item

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.DeleteMax ( )

Remove the largest item from this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty

Returns
The removed item.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.DeleteMax ( out IPriorityQueueHandle< T >  handle)

Remove the largest item from this priority queue.

Parameters
handleOn return: the handle of the removed item.
Returns
The removed item.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.DeleteMin ( )

Remove the least item from this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty

Returns
The removed item.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.DeleteMin ( out IPriorityQueueHandle< T >  handle)

Remove the least item from this priority queue.

Parameters
handleOn return: the handle of the removed item.
Returns
The removed item.

Implements C5.IPriorityQueue< T >.

bool C5.IntervalHeap< T >.Find ( IPriorityQueueHandle< T >  handle,
out T  item 
)

Check safely if a handle is valid for this queue and if so, report the corresponding queue item.

Parameters
handleThe handle to check
itemIf the handle is valid this will contain the corresponding item on output.
Returns
True if the handle is valid.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.FindMax ( )

Find the current largest item of this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty

Returns
The largest item.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.FindMax ( out IPriorityQueueHandle< T >  handle)

Find the current largest item of this priority queue.

Parameters
handleOn return: the handle of the item.
Returns
The largest item.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.FindMin ( )

Find the current least item of this priority queue.

Exceptions
NoSuchItemExceptionif queue is empty

Returns
The least item.

Implements C5.IPriorityQueue< T >.

T C5.IntervalHeap< T >.FindMin ( out IPriorityQueueHandle< T >  handle)

Find the current least item of this priority queue.

Parameters
handleOn return: the handle of the item.
Returns
The least item.

Implements C5.IPriorityQueue< T >.

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

Create an enumerator for the collection

Note: the enumerator does not enumerate the items in sorted order, but in the internal table order.

Returns
The enumerator(SIC)

Implements C5.CollectionValueBase< T >.

T C5.IntervalHeap< T >.Replace ( IPriorityQueueHandle< T >  handle,
item 
)

Replace an item with a handle in a priority queue with a new item. Typically used for changing the priority of some queued object.

Parameters
handleThe handle for the old item
itemThe new item
Returns
The old item

Implements C5.IPriorityQueue< T >.

Property Documentation

bool C5.IntervalHeap< T >.AllowsDuplicates
get

True since this collection has bag semantics

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

The comparer object supplied at creation time for this collection

The comparer

override int C5.IntervalHeap< T >.Count
get

The size of this collection

override Speed C5.IntervalHeap< T >.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).

A characterization of the speed of the Count property in this collection.

virtual bool C5.IntervalHeap< 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 SCG.IEqualityComparer<T> C5.IntervalHeap< T >.EqualityComparer
get

Value is null since this collection has no equality concept for its items.

override bool C5.IntervalHeap< T >.IsEmpty
get

True if this collection is empty.

bool C5.IntervalHeap< T >.IsReadOnly
get

If true any call of an updating operation will throw an

ReadOnlyCollectionException

True if this collection is read-only.

override EventTypeEnum C5.IntervalHeap< T >.ListenableEvents
get

T C5.IntervalHeap< T >.this[IPriorityQueueHandle< T > handle]
getset

Get or set the item corresponding to a handle.

Exceptions
InvalidPriorityQueueHandleExceptionif the handle is invalid for this queue
Parameters
handleThe reference into the heap
Returns

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