Class DuplicatedItemsResolution<TItems, THeap>

An object storing and keeping up-to-date the "TItems to TreeNode<T>" back-references, necessary to find back the TreeNode<T> in the heap with highest priority for a given item, without exposing iterators to the client.

Inheritance
System.Object
DuplicatedItemsResolution<TItems, THeap>
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.BinomialHeap
Assembly: MoreStructures.dll
Syntax
public class DuplicatedItemsResolution<TItems, THeap>
    where THeap : IPriorityQueue<int>, new()
Type Parameters
Name Description
TItems

THeap

A type constructor for an heap of System.Int32. Needed to store all push timestamps for each item.
Remarks

In order to support updates and deletions of items, two additional data structures are introduced:

  • a Item2PT, mapping items I of type TItems to THeap instances, containing values of type System.Int32, of MoreStructures.PriorityQueues.PrioritizedItem<T> instances containing I.
  • a PT2Idx from values to TreeNode<T> of type System.Int32, into the backing THeap structure of this priority queue.

    Every time a request to remove or update an item I from the priority queue is made, Item2PT is used to retrieve all the values of MoreStructures.PriorityQueues.PrioritizedItem<T> instances with item.
    Those push timestamps can be multiple because the same item can be added multiple times to the queue.
    The push timestamps are organized themselves in per-item priority queues, with the same priority as the items in the main priority queue.
    This way, the push timestamp of highest priority for a given item can be peeked in constant time and extracted in logarithmic time.
    Once the timestamp of highest priority has been found, the corresponding TreeNode<T> (if any) in the backing THeap structure of this priority queue can be found in constant time via the PT2Idx dictionary.

Methods

| Improve this Doc View Source

Clear()

Clears the content of this object.

Declaration
public void Clear()
| Improve this Doc View Source

FindTreeNode(TItems)

Retrieves the TreeNode<T> associated with the provided item in the queue, selecting the one of highest priority in case of duplicates (i.e. multiple occurrences of item within the priority queue).

Declaration
public TreeNode<TItems> FindTreeNode(TItems item)
Parameters
Type Name Description
TItems item

The item to be mapped to a TreeNode<T>.
Returns
Type Description
TreeNode<TItems>

The corresponding TreeNode<T>.
Remarks

ALGORITHM - TREENODE RETRIEVAL PART
- The priority queue of push timestamps for the provided item is retrieved from the dictionary of per-item queues of push timestamps.
- If such a priority queue is not found, it means that item is not present in the main priority queue either. So, an is thrown.
- If the priority queue is found, push timestamps are popped from it until the root of the priority queue contains a valid timestamp ts, i.e. a timestamp present in the dictionary mapping timestamps to TreeNode<T> instances and the IsInAHeap.
- If such a timestamp is not found, it means that that item used to be present in the main priority, but it is not anymore. So, an is thrown.
- If such a timestamp is found, the MoreStructures.PriorityQueues.PrioritizedItem<T> can be accessed via the PrioritizedItem property.

COMPLEXITY - TREENODE RETRIEVAL PART
- Retrieving the priority queue associated with the item is a O(1) operation.
- Finding the right push timestamp may require a number of Pop() proportional to the number of times the priority of item has been changed.
- In the worst case, such number is equal to the number of insertion of item.
- Therefore, Time Complexity is O(dup_factor) and Space Complexity is O(1), where dup_factor is the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the item appears twice, etc.).

| Improve this Doc View Source

GetPrioritiesOf(TItems)

Returns all the priorities with which item is registered in the queue, sorted by highest to smallest.

Declaration
public IEnumerable<int> GetPrioritiesOf(TItems item)
Parameters
Type Name Description
TItems item
Returns
Type Description
IEnumerable<System.Int32>

The sequence of System.Int32 values, each being a priority.
Remarks

ALGORITHM
- First, the priority queue of push timestamps for the provided item is retrieved from the dictionary of per-item queues of push timestamps.
- If such a queue is not found, item is not present in the main priority queue, and an empty sequence is returned.
- Otherwise, the queue is iterated over, getting the TreeNode<T> corresponding to each timestamp extracted from the queue, where such node is still in a heap (it may have been detached since).
- The TreeNode<T> is used to make a direct access to the corresponding MoreStructures.PriorityQueues.PrioritizedItem<T>. The priority is taken from .

COMPLEXITY
- Retrieving the priority queue of push timestamps from the dictionary of per-item priority queues is a O(1) operation.
- Iterating such a priority queue requires duplicating the underlying data structure, which is a O(dup_factor) operation, where dup_factor is the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the item appears twice, etc.).
- Retrieving the TreeNode<T> from the push timestamp and the priority from the MoreStructures.PriorityQueues.PrioritizedItem<T> instance are both constant-time operations.
- Therefore Time and Space Complexity are O(dup_factor), where dup_factor is the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the item appears twice, etc.).

| Improve this Doc View Source

RaiseItemPopping(TreeNode<TItems>)

To be invoked just before the provided root is popped from the heap.

Declaration
public void RaiseItemPopping(TreeNode<TItems> root)
Parameters
Type Name Description
TreeNode<TItems> root

The root about to be popped from the heap forest.
| Improve this Doc View Source

RaiseItemPriorityChanged(TreeNode<TItems>, PrioritizedItem<TItems>)

To be invoked just after the priority of a TreeNode<T> has changed.

Declaration
public void RaiseItemPriorityChanged(TreeNode<TItems> treeNode, PrioritizedItem<TItems> itemBefore)
Parameters
Type Name Description
TreeNode<TItems> treeNode

The node in the heap which has changed priority.
MoreStructures.PriorityQueues.PrioritizedItem<TItems> itemBefore

The MoreStructures.PriorityQueues.PrioritizedItem<T> as it was before the priority change.
| Improve this Doc View Source

RaiseItemPushed(TreeNode<TItems>)

To be invoked just after a newRoot has been pushed into the heap.

Declaration
public void RaiseItemPushed(TreeNode<TItems> newRoot)
Parameters
Type Name Description
TreeNode<TItems> newRoot

The new root pushed into the heap forest.
| Improve this Doc View Source

RaiseItemsSwapped(TreeNode<TItems>, TreeNode<TItems>)

Invoked just after two items have had their MoreStructures.PriorityQueues.PrioritizedItem<T> swapped.

Declaration
public void RaiseItemsSwapped(TreeNode<TItems> treeNode1, TreeNode<TItems> treeNode2)
Parameters
Type Name Description
TreeNode<TItems> treeNode1

The first node.
TreeNode<TItems> treeNode2

The second node.

Extension Methods