Class BinaryHeapListWrapper<T>

A wrapper around a , which preserve the max heap property on the subset of items of the list, at the beginning or at the end of it.

Inheritance

System.Object

BinaryHeapListWrapper<T>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.PriorityQueues.BinaryHeap

Assembly: MoreStructures.dll

Syntax

public sealed class BinaryHeapListWrapper<T>

Type Parameters

Name	Description
T	The type of items in the wrapped list.

Remarks

Heap items are either stored:

• from index 0 to HeapCount - 1, i.e. at the beginning of the list,
  
• or from index ListCount - HeapCount to ListCount - 1, i.e. at the end.
  That leaves a buffer of ListCount - HeapCount items, either at the end or at the beginning of the list.
  The functionalities of this wrapper can be used to support HeapSort or a priority queue based on a Max Binary Heap.
  In the first case the buffer area is used (to store already sorted items). In the second case it is not.

Constructors

BinaryHeapListWrapper(IList<T>, IComparer<T>, Int32, Boolean, Int32)

Built around the provided items.

Declaration

public BinaryHeapListWrapper(IList<T> items, IComparer<T> comparer, int count, bool storeHeapAtTheEnd = false, int indexDelta = 0)

Parameters

Type	Name	Description
IList<T>	items	The of items to be wrapped.
IComparer<T>	comparer	The comparer to be used to establish a order relationship between items.
System.Int32	count	The size of the subset of items to be kept in order according to the max heap property. Goes from index 0 to index count - 1. Current size must be non-bigger than the .
System.Boolean	storeHeapAtTheEnd	Whether heap items should be stored at the beginning or at the end of the items list. By default heap items are stored at the beginning (root at index 0) and buffer are is at the end.
System.Int32	indexDelta	The delta, positive or negative, with which heap items will be stored in the items list, w.r.t. the beginning (if storeHeapAtTheEnd is false) or the end (if storeHeapAtTheEnd is true) of the list. By default it is zero (i.e. no displacement).

BinaryHeapListWrapper(BinaryHeapListWrapper<T>)

Built from the provided BinaryHeapListWrapper<T> source.

Declaration

public BinaryHeapListWrapper(BinaryHeapListWrapper<T> source)

Parameters

Type	Name	Description
BinaryHeapListWrapper<T>	source

Properties

HeapCount

The number of items in the heap only, buffer area of the underlying list excluded.

Declaration

public int HeapCount { get; }

Property Value

Type	Description
System.Int32

Remarks

May be smaller than the current of the underlying , which in turn may be smaller than the current Length of the underlying .

Item[Int32]

Retrieves the index-th item in the underlying list (heap or buffer).

Declaration

public T this[int index] { get; set; }

Parameters

Type	Name	Description
System.Int32	index	A non-negative System.Int32. It can be non-smaller than HeapCount, if an element of the buffer is being accessed, but it necessarily has to be smaller than the of the underlying .

Property Value

Type	Description
T	The item, an instance of type T.

ListCount

The number of items in the underlying list, heap and buffer are included.

Declaration

public int ListCount { get; }

Property Value

Type	Description
System.Int32

Remarks

It's always non-smaller than HeapCount, since all the heap items are contained in the underlying list.

RaiseItemPopping

Invoked just before an item is removed from MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapListWrapper`1.Items (at the beginning of the heap), and before "sifting down" procedure is performed.

Declaration

public Action<int, int> RaiseItemPopping { get; set; }

Property Value

Type	Description
Action<System.Int32, System.Int32>

Remarks

The actual index of the item pushed may be different than 0, if the heap is stored in reverse, in which case it is equal to ListCount - 1.
Same applies to the index of the item pushed out of the heap (but still in the list, in the buffer area).

RaiseItemPushed

Invoked just after an item has been pushed into MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapListWrapper`1.Items (at the end of the heap), and before the "sifting up" procedure is performed.

Declaration

public Action<int> RaiseItemPushed { get; set; }

Property Value

Type	Description
Action<System.Int32>

Remarks

The actual index of the item pushed will be different than ListCount - 1, if ListCount is different than HeapCount, or if the heap is stored in reverse.

RaiseItemsSwapped

Invoked just after two items have been swapped of position in MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapListWrapper`1.Items.

Declaration

public Action<int, int> RaiseItemsSwapped { get; set; }

Property Value

Type	Description
Action<System.Int32, System.Int32>

Methods

Clear()

Clears the underlying list (heap and buffer), wiping all its items out, if the list is not readonly.
If it is readonly (e.g. an array), it just resets the HeapCount.

Declaration

public void Clear()

GetEnumerator()

Returns an enumerator of T instances, going through all items of the underlying list, not just the first HeapCount items which form the heap, but also the buffer area at the end of the underlying list.

Declaration

public IEnumerator<T> GetEnumerator()

Returns

Type	Description
IEnumerator<T>	An of T.

Peek()

Peeks the item with max priority from the root of the heap, if any.

Declaration

public T Peek()

Returns

Type	Description
T

PeekKth(Int32)

Retrieves the item of the heap with priority k, without extracting any of the items in the heap.

Declaration

public (T result, bool valid) PeekKth(int k)

Parameters

Type	Name	Description
System.Int32	k	The non-negative priority rank: 0 means highest priority, 1 second highest, etc.

Returns

Type	Description
System.ValueTuple<T, System.Boolean>	The item with k-th highest priority if any, with true as valid flag. The default for T otherwise, with false as valid flag.

Pop()

Pops the item with max priority from the root of the heap, if any, moving the last leaf to the now vacant root and sifting it down until the heap property is restored.

Declaration

public T Pop()

Returns

Type	Description
T	The popped item.

PopAll()

Pops all items of the heap in sequence, from the one with highest priority to the one with lowest priority.

Declaration

public IEnumerable<T> PopAll()

Returns

Type	Description
IEnumerable<T>	A sequence of T instances.

Push(T, Boolean)

Pushes the provided item into the heap, sifting it up until the max heap property is restored.

Declaration

public void Push(T item, bool siftUp = true)

Parameters

Type	Name	Description
T	item	The item to be added to the heap.
System.Boolean	siftUp	Whether the sift up procedure should be executed or not. By default it is set to true. If it is not executed, the max heap property will be temporary violated. The push may fail if the heap is stored at the back of the list and grows backwards (which is the layout applied when MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapListWrapper`1.StoreHeapAtTheEnd is set to true), if the buffer is empty (i.e. if the last leaf of the heap has reached the front of the list, and adding a new leaf would require adding an element before the position 0 of the list). The push never fails when the heap is stored at the front of the list and grows forwards, because the list is able to grow at the back.

RestoreHeapProperty()

Restores the max heap property, ensuring that each node of the heap is at least as big as its children, if any.

Declaration

public void RestoreHeapProperty()

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)