< Summary

Information
Class: MoreStructures.PriorityQueues.BinomialHeap.BinomialHeapPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinomialHeap/BinomialHeapPriorityQueue.cs
Line coverage
100%
Covered lines: 154
Uncovered lines: 0
Coverable lines: 154
Total lines: 589
Line coverage: 100%
Branch coverage
100%
Covered branches: 34
Total branches: 34
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Roots()100%1100%
get_ItemsCount()100%1100%
get_MaxRootsListNode()100%1100%
get_CurrentPushTimestamp()100%1100%
get_PushTimestampEras()100%1100%
.ctor()100%1100%
.ctor(...)100%6100%
get_Count()100%1100%
GetEnumerator()100%2100%
System.Collections.IEnumerable.GetEnumerator()100%1100%
Peek()100%2100%
Push(...)100%1100%
Pop()100%4100%
MergeFrom(...)100%4100%
Clear()100%1100%
RaiseItemPushed(...)100%1100%
RaiseItemPopping(...)100%1100%
RaiseItemsClearing()100%1100%
RaiseRootMerged(...)100%1100%
UpdateMaxRootsListNodeAfterRootNewOrIncrease(...)100%4100%
UpdateMaxRootsListNode()100%6100%
AddRoot(...)100%1100%
AttachToRoots(...)100%1100%
MergeEquiDegreeTrees()100%4100%
MergeRoots(...)100%2100%
DetachFromRoots(...)100%1100%
PromoteChildToRoot(...)100%1100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinomialHeap/BinomialHeapPriorityQueue.cs

#LineLine coverage
 1using MoreStructures.Utilities;
 2using System.Collections;
 3
 4namespace MoreStructures.PriorityQueues.BinomialHeap;
 5
 6/// <summary>
 7/// An <see cref="IPriorityQueue{T}"/> implementation based on a Binomial Max Heap of its items. It also supports
 8/// <see cref="IMergeablePriorityQueue{T, TPQTarget}"/> operations.
 9/// </summary>
 10/// <typeparam name="T"><inheritdoc cref="IPriorityQueue{T}"/></typeparam>
 11/// <remarks>
 12///     <para id="definition">
 13///     DEFINITION
 14///     <br/>
 15///     - A <b>Binomial Heap</b> is a forest of <b>n-ary trees</b>, each respecting the <b>heap max property</b>,
 16///       having a <b>binomial layout</b> and <b>unicity of degree</b>.
 17///       <br/>
 18///     - A tree respects the heap max property when each node has a value to be non-smaller than all its children
 19///       (and, by transitivity, its grand-children, grand-grand-children etc.).
 20///       <br/>
 21///     - A tree has a binomial layout when is in the set of tree defined in the following constructive way: a
 22///       singleton tree is a binomial tree of degree 0, a binomial tree of degree k + 1 is obtained merging two
 23///       binomial trees of degree k, so that the root of one becomes immediate child of the root of the other.
 24///       <br/>
 25///     - A tree has unicity of degree when it is the only tree in the forest having its degree, which is the number of
 26///       children it has. That means that there can be a single tree with 0 children (singleton), a single tree with
 27///       1 child, etc.
 28///     </para>
 29///     <para id="advantages">
 30///     ADVANTAGES AND DISADVANTAGES
 31///     <br/>
 32///     - This heap implementation is conceptually extending <see cref="BinaryHeap.BinaryHeapPriorityQueue{T}"/>,
 33///       making heaps easily mergeable (i.e. in less time than O(n).
 34///       <br/>
 35///     - Binary Heaps provide logarithmic insertion and extraction. They can also provide linear construction, when
 36///       the data is provided in batch and not online.
 37///       <br/>
 38///     - However, Binary Heap have O(n * log(n)) Time Complexity in merge. Merging the smaller heap into the bigger
 39///       one, in the worst case the two heaps being merged have comparable size n / 2, resulting into an overall
 40///       O(n / 2 * log(n / 2)) = O(n * log(n)) Time Complexity.
 41///       <br/>
 42///     - Merging the underlying arrays and building the new Binary Heap in batch would improve performance, yielding
 43///       O(n) Time Complexity. Still an expensive operation, as it means going through all elements of one heap.
 44///       <br/>
 45///     - Binomial Heaps overcome this limitation and offer sub-linear performance by taking advantage of both the
 46///       linked list layout and the tree layout, and taking the best of both worlds.
 47///       <br/>
 48///     - So the underlying idea behind Binomial Heaps is to combine linked lists and trees, and represent the data as
 49///       a forest of n-ry heap trees (respecting the binomial layout), which can be easily merged together into a
 50///       single Binomial Heap, due to their "recurrent" structure.
 51///       <br/>
 52///     - While <see cref="Push(T, int)"/> and <see cref="Pop"/> retain logarithmic complexity, merging also becomes
 53///       a logarithmic operation.
 54///     </para>
 55/// </remarks>
 56public partial class BinomialHeapPriorityQueue<T>
 57    : IMergeablePriorityQueue<T, BinomialHeapPriorityQueue<T>>
 58    where T : notnull
 59{
 60    /// <summary>
 61    /// A <see cref="LinkedList{T}"/> of all the roots of the forest representing the heap.
 62    /// </summary>
 31323363    protected LinkedList<TreeNode<T>> Roots { get; }
 64
 65    /// <summary>
 66    /// The total number of items in this queue.
 67    /// </summary>
 17991968    protected int ItemsCount { get; set; }
 69
 70    /// <summary>
 71    /// Reference to the tree root in the forest with the highest priority. Makes Peek O(1).
 72    /// </summary>
 18007473    protected LinkedListNode<TreeNode<T>>? MaxRootsListNode { get; set; }
 74
 75
 76    /// <summary>
 77    /// A non-negative, zero-based, monotonically strictly increasing counter, incremented at every insertion into this
 78    /// data structure by a <see cref="Push(T, int)"/>.
 79    /// </summary>
 7883780    protected int CurrentPushTimestamp { get; set; }
 81
 82    /// <summary>
 83    /// The eras in which all push timestamps created by this instance (e.g. on push), or merged into this instance,
 84    /// leave in. The last in the list is the current one.
 85    /// </summary>
 86    /// <remarks>
 87    /// By default, initialized to a singleton list containing the era "0".
 88    /// <br/>
 89    /// Depending on the implementation, may be relevant in merging.
 90    /// </remarks>
 3570291    protected IList<PushTimestampEra> PushTimestampEras { get; }
 92
 93
 94    /// <summary>
 95    /// Builds an empty priority queue.
 96    /// </summary>
 1384997    public BinomialHeapPriorityQueue()
 1384998    {
 1384999        Roots = new();
 13849100        ItemsCount = 0;
 13849101        MaxRootsListNode = null;
 102
 13849103        CurrentPushTimestamp = 0;
 13849104        PushTimestampEras = new List<PushTimestampEra>() { new(0) };
 13849105    }
 106
 107    /// <summary>
 108    /// Builds a deep, separate copy of the provided <paramref name="source"/> priority queue.
 109    /// </summary>
 110    /// <param name="source">The priority queue to be copied over.</param>
 111    /// <remarks>
 112    /// Doesn't copy the items themselves, it only deep-copies the internal structure of the <paramref name="source"/>
 113    /// queue.
 114    /// <br/>
 115    /// Warning: push timestamp eras are shared between items of the two queues! To be used only for
 116    /// <see cref="GetEnumerator"/> support.
 117    /// </remarks>
 474118    protected BinomialHeapPriorityQueue(BinomialHeapPriorityQueue<T> source)
 474119    {
 1753120        Roots = new LinkedList<TreeNode<T>>(source.Roots.Select(r => r.DeepCopy()));
 3980121        foreach (var rootsListNode in Roots.AsNodes())
 1279122            rootsListNode.Value.RootsListNode = rootsListNode;
 123
 474124        ItemsCount = source.ItemsCount;
 474125        UpdateMaxRootsListNode();
 474126        CurrentPushTimestamp = source.CurrentPushTimestamp;
 1772127        PushTimestampEras = source.PushTimestampEras.Select(e => e with { }).ToList();
 474128    }
 129
 130    #region Public API
 131
 132    /// <inheritdoc path="//*[not(self::remarks)]"/>
 133    /// <remarks>
 134    /// Checks the count internally stored, keeping track of the sum of the size of all trees in the linked list.
 135    /// <br/>
 136    /// Time and Space Complexity are O(1).
 137    /// </remarks>
 19908138    public virtual int Count => ItemsCount;
 139
 140    /// <inheritdoc path="//*[not(self::remarks)]"/>
 141    /// <remarks>
 142    /// In order to return items in heap order (i.e. the max at each step), it first copies this priority queue into a
 143    /// second temporary queue, which can be mutated without affecting the state of this queue.
 144    /// <br/>
 145    /// It then iterates over the copy, calling <see cref="Pop"/> until it becomes empty.
 146    /// <br/>
 147    /// Time Complexity is O(n * log(n)) (when fully enumerated), because a single <see cref="Pop"/> on a Binomial
 148    /// Heap takes logarithmic time, and there are n items to be extracted.
 149    /// <br/>
 150    /// Space Complexity is O(n), as a copy of this queue is required as auxiliary data structure to emit elements in
 151    /// the right order of priority.
 152    /// </remarks>
 153    public virtual IEnumerator<T> GetEnumerator()
 237154    {
 237155        var copy = new BinomialHeapPriorityQueue<T>(this);
 5962156        while (copy.Count > 0)
 5733157            yield return copy.Pop().Item;
 229158    }
 159
 160    /// <inheritdoc path="//*[not(self::remarks)]"/>
 161    /// <remarks>
 162    ///     <inheritdoc cref="GetEnumerator"/>
 163    /// </remarks>
 4164    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 165
 166    /// <inheritdoc path="//*[not(self::remarks)]"/>
 167    /// <remarks>
 168    /// Peeks the item of the linked list pointed by the "max root" internal property.
 169    /// <br/>
 170    /// By transitivity, the item of the max root contains the max item in the queue, since all roots are non-smaller
 171    /// than their descendants.
 172    /// <br/>
 173    /// Therefore, Time and Space Complexity are O(1).
 174    /// </remarks>
 175    public virtual PrioritizedItem<T> Peek()
 1800176    {
 1800177        if (MaxRootsListNode == null)
 12178            throw new InvalidOperationException($"Can't {nameof(Peek)} on an empty queue.");
 179
 1788180        return MaxRootsListNode.Value.PrioritizedItem;
 1788181    }
 182
 183    /// <inheritdoc path="//*[not(self::remarks)]"/>
 184    /// <remarks>
 185    ///     <para id="algorithm">
 186    ///     ALGORITHM
 187    ///     <br/>
 188    ///     - Adds a new singleton tree T (degree 0) to the forest, wrapping the provided <paramref name="item"/> with
 189    ///       its <paramref name="priority"/> into an object R with no children, and wrapping R into a
 190    ///       <see cref="LinkedListNode{T}"/> LLN, which represents the root of T.
 191    ///       <br/>
 192    ///     - Then all trees with the same degree are merged together, with the same procedure explained in the
 193    ///       documentation of <see cref="Pop"/>.
 194    ///       <br/>
 195    ///     - That ensures that the binomial shape of the forest (i.e. binomial trees all of different degrees) is
 196    ///       preserved. Without merging, if a tree of degree 0 (i.e. a singleton tree) was already present before the
 197    ///       push of the new root, the binomial heap property would have been violated.
 198    ///       <br/>
 199    ///     - After all equi-degree trees have been merged, a new linear scan of the root is done, to update the
 200    ///       reference to the root with highest priority (so that <see cref="Peek"/> will work correctly and in
 201    ///       constant time).
 202    ///     </para>
 203    ///     <para id="complexity">
 204    ///     COMPLEXITY
 205    ///     <br/>
 206    ///     - Adding a new root to the forest of trees is a constant-time operation, since the root is added at
 207    ///       the end of the linked list representing the forest, which keeps references to both ends of the chain of
 208    ///       nodes.
 209    ///       <br/>
 210    ///     - Merging equi-degree trees, to restore the binomial shape of the heap forest, and updating the max root
 211    ///       reference are both logarithmic operations in time. The merge also requires a space proportional to the
 212    ///       logarithm of the number of items in the heap, to instantiate its data structure.
 213    ///       <br/>
 214    ///     - Check the complexity analysis of <see cref="Pop"/> for further details.
 215    ///       <br/>
 216    ///     - Therefore, Time and Space Complexity are both O(log(n)).
 217    ///     </para>
 218    /// </remarks>
 219    public virtual void Push(T item, int priority)
 17462220    {
 17462221        var prioritizedItem = new PrioritizedItem<T>(item, priority, CurrentPushTimestamp++, PushTimestampEras[^1]);
 17462222        var newRoot = new TreeNode<T> { PrioritizedItem = prioritizedItem };
 17462223        AddRoot(newRoot);
 17462224        RaiseItemPushed(newRoot);
 17462225        MergeEquiDegreeTrees();
 17462226        UpdateMaxRootsListNode();
 17462227    }
 228
 229    /// <inheritdoc path="//*[not(self::remarks)]"/>
 230    /// <remarks>
 231    ///     <para id="algorithm">
 232    ///     ALGORITHM
 233    ///     <br/>
 234    ///     - The value of the tree root with highest priority is read, then the root is removed from the forest.
 235    ///       <br/>
 236    ///     - The orphan children of the removed root are promoted to being roots and added to the forest.
 237    ///       <br/>
 238    ///     - Then all trees with the same degree are merged together, where the root with lower priority becomes
 239    ///       immediate child of the root with higher priority.
 240    ///       <br/>
 241    ///     - Merging is done efficiently by linearly scanning all the tree roots in the forest, and keeping an array
 242    ///       A of tree roots indexed by their degree.
 243    ///       <br/>
 244    ///     - Every time a second tree with the same degree is encountered: if T1 has degree k and A[k] already
 245    ///       references another tree T2 with degree k, T1 and T2 are merged into a tree whose root has degree k + 1,
 246    ///       A[k] is reset and A[k + 1] is set.
 247    ///       <br/>
 248    ///     - After all equi-degree trees have been merged, a new linear scan of the root is done, to update the
 249    ///       reference to the root with highest priority.
 250    ///     </para>
 251    ///     <para>
 252    ///     COMPLEXITY
 253    ///     <br/>
 254    ///     - Removing the root with highest priority from the forest is a O(1) operation.
 255    ///       <br/>
 256    ///     - Promoting to roots all its children is proportional to the number of children, a root of the forest has.
 257    ///       <br/>
 258    ///     - In a Binomial Heap the max degree of the roots of the forest is logarithmic with the total number of
 259    ///       items in the heap. Therefore, promotion of children to roots is a O(log(n)) operation.
 260    ///       <br/>
 261    ///     - Merging equi-degree trees requires a full scan of the roots in the forest. If the forest were made of
 262    ///       a lot of shallow trees, that would result into a O(n) operation.
 263    ///       <br/>
 264    ///     - However, while <see cref="Push(T, int)"/> increases every time by 1 the count of trees, after n
 265    ///       insertions in O(1), a single O(n) scan done by a <see cref="Pop"/> would merge trees, making them
 266    ///       logarithmic in number.
 267    ///       <br/>
 268    ///     - Updating the max root reference takes time proportional to the number of trees in the forest AFTER the
 269    ///       merging.
 270    ///       <br/>
 271    ///     - Because the merging of equi-degree trees leaves a forest of trees all of different degrees, and the max
 272    ///       degree is logarithmic with n, at the end of the merging procedure there can be at most a logarithmic
 273    ///       number of different trees in the forest.
 274    ///       <br/>
 275    ///     - So the linear scan of tree roots in the forest to find the max root reference takes only a logarithmic
 276    ///       amount of time.
 277    ///       <br/>
 278    ///     - Therefore, Time Complexity is O(log(n)). Space Complexity is also O(log(n)), since merging equi-degree
 279    ///       trees requires instantiating an array index by degrees, and max degree is O(log(n)).
 280    ///     </para>
 281    /// </remarks>
 282    public virtual PrioritizedItem<T> Pop()
 19019283    {
 19019284        if (MaxRootsListNode == null)
 12285            throw new InvalidOperationException($"Can't {nameof(Pop)} on an empty queue.");
 286
 19007287        RaiseItemPopping(MaxRootsListNode.Value);
 19007288        var oldRoot = DetachFromRoots(MaxRootsListNode);
 19007289        ItemsCount--;
 290
 206035291        foreach (var child in oldRoot.Children.ToList())
 74507292            PromoteChildToRoot(child);
 293
 19007294        MergeEquiDegreeTrees();
 19007295        UpdateMaxRootsListNode();
 296
 19007297        return oldRoot.PrioritizedItem;
 19007298    }
 299
 300    /// <inheritdoc path="//*[not(self::remarks)]"/>
 301    /// <remarks>
 302    ///     <para id="algorithm">
 303    ///     ALGORITHM
 304    ///     <br/>
 305    ///     - Before the actual merge of roots, push timestamp eras need to be adjusted, to deal with potentially
 306    ///       conflicting timestamps from the two queues without scanning through all items, which would take a linear
 307    ///       amount of time.
 308    ///       <br/>
 309    ///     - In order to do so, the max push timestamp era M, between the current era of the source and the current
 310    ///       era of the target (the last in the list of eras of each), is calculated.
 311    ///       <br/>
 312    ///     - Then, all the push timestamp eras of the target are <b>mutated</b> (i.e. by a set accessor on the
 313    ///       instance) in order (from the first = the older, to the last = the most recent) to M + 1, M + 2, ...
 314    ///       <br/>
 315    ///     - This way all items of the target are considered as added after all current items of the source, and keep
 316    ///       the order they had in the target between themselves, before the merge.
 317    ///       <br/>
 318    ///     - Then, a new current push timestamp era of the source is <b>added</b> (i.e. new instance) with a new
 319    ///       push timestamp era set to M + N + 1, so that all items of the source coming after the merge are
 320    ///       considered as added after all items of the target added during merge.
 321    ///       <br/>
 322    ///     - After that, the algorithm iterates over all the roots of the target heap.
 323    ///       <br/>
 324    ///     - Add each root R to the linked list of roots of the source heap and increases the total items count of
 325    ///       the source heap by the number of items in R, which can be calculated without traversing, from the number
 326    ///       of immediate children c of R as 2^c, being R a binomial tree.
 327    ///       tree.
 328    ///       <br/>
 329    ///     - For each added root, <see cref=" RaiseRootMerged(TreeNode{T})"/> is invoked.
 330    ///       <br/>
 331    ///     - Then binomial heap shape is restored by merging together all trees with the same degree and a new linear
 332    ///       scan of the root is done, to update the reference to the root with highest priority, exactly as in
 333    ///       <see cref="Push(T, int)"/> and <see cref="Pop"/>.
 334    ///       <br/>
 335    ///     - To separate avoid interferences between this queue and the <paramref name="targetPriorityQueue"/>, the
 336    ///       <paramref name="targetPriorityQueue"/> is cleared of all its items.
 337    ///       <br/>
 338    ///     - Its current push timestamp is left unchanged and the push timestamp eras are cleared and set to a new
 339    ///       single instance with the same era value it had before the merge. This way all new items in the
 340    ///       <paramref name="targetPriorityQueue"/> will share the reference to the new era object, and wont interfere
 341    ///       with the era object of all items moved to this priority queue.
 342    ///     </para>
 343    ///     <para id="complexity">
 344    ///     COMPLEXITY
 345    ///     <br/>
 346    ///     - For this analysis, events, and in particular <see cref="RaiseRootMerged(TreeNode{T})"/>, are considered
 347    ///       O(1) both in Time and Space Complexity.
 348    ///       <br/>
 349    ///     - The number of roots of the target heap is logarithmic with the number m of items in the target heap.
 350    ///       <br/>
 351    ///     - Adding each root R of the target heap to the forest of the source heap and increasing the items count are
 352    ///       both constant-time operations.
 353    ///       <br/>
 354    ///     - Housekeeping operations, done after that on the source heap, take logarithmic time, as explained in
 355    ///       <see cref="Pop"/>.
 356    ///       <br/>
 357    ///     - Clearing the target is also a constant-time operation.
 358    ///       <br/>
 359    ///     - Therefore, Time and Space Complexity are O(log(m)).
 360    ///     </para>
 361    /// </remarks>
 362    public virtual void MergeFrom(BinomialHeapPriorityQueue<T> targetPriorityQueue)
 468363    {
 468364        var previousSourceEra = PushTimestampEras[^1].Era;
 468365        var previousTargetEra = targetPriorityQueue.PushTimestampEras[^1].Era;
 468366        var previousNextEra = Math.Max(previousSourceEra, previousTargetEra) + 1;
 367
 2356368        foreach (var targetPushstampEra in targetPriorityQueue.PushTimestampEras)
 476369        {
 476370            targetPushstampEra.Era = previousNextEra++;
 476371            PushTimestampEras.Add(targetPushstampEra);
 476372        }
 373
 468374        PushTimestampEras.Add(new PushTimestampEra(previousNextEra));
 468375        CurrentPushTimestamp = 0;
 376
 7240377        foreach (var targetRoot in targetPriorityQueue.Roots)
 2918378        {
 2918379            AttachToRoots(targetRoot);
 2918380            ItemsCount += (int)Math.Pow(2, targetRoot.Children.Count);
 2918381            RaiseRootMerged(targetRoot);
 2918382        }
 383
 468384        MergeEquiDegreeTrees();
 468385        UpdateMaxRootsListNode();
 386
 468387        targetPriorityQueue.PushTimestampEras.Clear();
 468388        targetPriorityQueue.PushTimestampEras.Add(new PushTimestampEra(previousTargetEra));
 468389        targetPriorityQueue.Clear();
 468390    }
 391
 392    /// <inheritdoc path="//*[not(self::remarks)]"/>
 393    /// <remarks>
 394    /// First, calls <see cref="RaiseItemsClearing"/>.
 395    /// <br/>
 396    /// Then, removes all the trees from the forest, reset to the items count to 0 and set the reference to the
 397    /// max priority root to <see langword="null"/>.
 398    /// <br/>
 399    /// The internal push timestamp counter is not reset, nor the era. Therefore, new pushes after the clear will
 400    /// receive push timestamps strictly higher than the ones assigned to the items in the queue before the clear.
 401    /// <br/>
 402    /// Time and Space Complexity are O(1), with <see cref="RaiseItemsClearing"/> assumed to be O(1).
 403    /// </remarks>
 404    public virtual void Clear()
 684405    {
 684406        RaiseItemsClearing();
 407
 684408        Roots.Clear();
 409
 684410        ItemsCount = 0;
 684411        MaxRootsListNode = null;
 684412    }
 413
 414    #endregion
 415
 416    #region Hooks
 417
 418    /// <summary>
 419    /// Invoked just after an item has been pushed into the heap (as a root).
 420    /// </summary>
 421    /// <param name="newRoot">The <see cref="TreeNode{T}"/> added to the heap.</param>
 422    /// <remarks>
 423    /// Not invoked on merging, for which <see cref="RaiseRootMerged(TreeNode{T})"/> is invoked instead.
 424    /// </remarks>
 39368425    protected virtual void RaiseItemPushed(TreeNode<T> newRoot) { }
 426
 427    /// <summary>
 428    /// Invoked just before an item is removed from the heap.
 429    /// </summary>
 430    /// <param name="root">The <see cref="TreeNode{T}"/> about to be removed from the heap.</param>
 27526431    protected virtual void RaiseItemPopping(TreeNode<T> root) { }
 432
 433    /// <summary>
 434    /// Invoked just before the all the items in the heap are wiped out.
 435    /// </summary>
 1368436    protected virtual void RaiseItemsClearing() { }
 437
 438    /// <summary>
 439    /// Invoked just after an heap tree has been added to the forest (root and all its descendants).
 440    /// </summary>
 441    /// <param name="root">The root <see cref="TreeNode{T}"/> of the heap tree added to the forest.</param>
 5836442    protected virtual void RaiseRootMerged(TreeNode<T> root) { }
 443
 444    #endregion
 445
 446    #region Helpers
 447
 448    /// <summary>
 449    /// Updates the reference to the max priority root to the provided <paramref name="rootsListNode"/>,
 450    /// if that root has a higher priority than the value of the current max priority root.
 451    /// </summary>
 452    /// <param name="rootsListNode">The root whose priority has been increased.</param>
 453    protected void UpdateMaxRootsListNodeAfterRootNewOrIncrease(LinkedListNode<TreeNode<T>> rootsListNode)
 31736454    {
 31736455        if (MaxRootsListNode == null ||
 31736456            MaxRootsListNode.Value.PrioritizedItem.CompareTo(rootsListNode.Value.PrioritizedItem) < 0)
 18205457            MaxRootsListNode = rootsListNode;
 31736458    }
 459
 460    /// <summary>
 461    /// Performs a linear scan of the roots and update the <see cref="MaxRootsListNode"/> with a reference to the root
 462    /// of max priority.
 463    /// </summary>
 464    protected void UpdateMaxRootsListNode()
 37486465    {
 37486466        if (ItemsCount > 0)
 35103467        {
 35103468            LinkedListNode<TreeNode<T>> maxRootNode = Roots.First!;
 268015469            foreach (var rootNode in Roots.AsNodes().Skip(1))
 81353470            {
 81353471                if (rootNode.Value.PrioritizedItem.CompareTo(maxRootNode.Value.PrioritizedItem) > 0)
 16389472                    maxRootNode = rootNode;
 81353473            }
 474
 35103475            MaxRootsListNode = maxRootNode;
 35103476        }
 477        else
 2383478        {
 2383479            MaxRootsListNode = null;
 2383480        }
 37486481    }
 482
 483    /// <summary>
 484    /// Adds a brand new <see cref="TreeNode{T}"/> to the heap, as a new root in the forest.
 485    /// </summary>
 486    /// <param name="newRoot">The new root.</param>
 487    protected void AddRoot(TreeNode<T> newRoot)
 31597488    {
 31597489        var newRootsListNode = AttachToRoots(newRoot);
 31597490        ItemsCount++;
 31597491        UpdateMaxRootsListNodeAfterRootNewOrIncrease(newRootsListNode);
 31597492    }
 493
 494    /// <summary>
 495    /// Attaches the provided <see cref="TreeNode{T}"/> to the <see cref="Roots"/>.
 496    /// </summary>
 497    /// <param name="newRoot">A node with no parent, and not already a root.</param>
 498    /// <returns>
 499    /// The <see cref="LinkedListNode{T}"/> of <see cref="Roots"/> pointing to the <paramref name="newRoot"/>.
 500    /// </returns>
 501    protected LinkedListNode<TreeNode<T>> AttachToRoots(TreeNode<T> newRoot)
 109160502    {
 109160503        var newRootsListNode = Roots.AddLast(newRoot);
 109160504        newRoot.RootsListNode = newRootsListNode;
 109160505        return newRootsListNode;
 109160506    }
 507
 508    /// <summary>
 509    /// Merges all trees of the <see cref="Roots"/> forest with the same degree (number of children of the root).
 510    /// </summary>
 511    protected virtual void MergeEquiDegreeTrees()
 36997512    {
 36997513        var degrees = new Dictionary<int, LinkedListNode<TreeNode<T>>>();
 492823514        foreach (var rootsListNode in Roots.AsNodes().ToList())
 190916515        {
 190916516            var currentRootsListNode = rootsListNode;
 190916517            var currentRootsListNodeDegree = currentRootsListNode.Value.Children.Count;
 266679518            while (degrees.TryGetValue(currentRootsListNodeDegree, out var otherRoot))
 75763519            {
 75763520                var newRootsListNode = MergeRoots(currentRootsListNode, otherRoot);
 75763521                degrees.Remove(currentRootsListNodeDegree);
 522
 75763523                currentRootsListNodeDegree = newRootsListNode.Value.Children.Count;
 75763524                currentRootsListNode = newRootsListNode;
 75763525            }
 526
 190916527            degrees[currentRootsListNodeDegree] = currentRootsListNode;
 190916528        }
 36997529    }
 530
 531    /// <summary>
 532    /// Merges the two provided trees of the forest into a single one, preserving the heap property.
 533    /// </summary>
 534    /// <param name="first">
 535    /// The <see cref="LinkedListNode{T}"/> of <see cref="Roots"/> pointing to the root of the first tree to merge.
 536    /// </param>
 537    /// <param name="second">
 538    /// The <see cref="LinkedListNode{T}"/> of <see cref="Roots"/> pointing to the root of the second tree to merge.
 539    /// </param>
 540    /// <returns>
 541    /// The <see cref="LinkedListNode{T}"/> of <see cref="Roots"/> pointing to the root of the merged tree: either
 542    /// <paramref name="first"/> or <paramref name="second"/>, depending on the <see cref="PrioritizedItem{T}"/> stored
 543    /// in the <see cref="TreeNode{T}.PrioritizedItem"/> of <see cref="LinkedListNode{T}.Value"/>.
 544    /// </returns>
 545    protected LinkedListNode<TreeNode<T>> MergeRoots(
 546        LinkedListNode<TreeNode<T>> first, LinkedListNode<TreeNode<T>> second)
 75763547    {
 75763548        if (first.Value.PrioritizedItem.CompareTo(second.Value.PrioritizedItem) >= 0)
 36242549        {
 36242550            DetachFromRoots(second);
 36242551            first.Value.AddChild(second.Value);
 36242552            return first;
 553        }
 554
 39521555        DetachFromRoots(first);
 39521556        second.Value.AddChild(first.Value);
 39521557        return second;
 75763558    }
 559
 560    /// <summary>
 561    /// Detaches the <see cref="TreeNode{T}"/> pointed by the provided <paramref name="rootsListNode"/> from the
 562    /// <see cref="Roots"/>.
 563    /// </summary>
 564    /// <param name="rootsListNode">
 565    /// The <see cref="LinkedListNode{T}"/> of <see cref="Roots"/>, pointing to the <see cref="TreeNode{T}"/> root.
 566    /// </param>
 567    /// <returns>The detached <see cref="TreeNode{T}"/> root.</returns>
 568    protected TreeNode<T> DetachFromRoots(LinkedListNode<TreeNode<T>> rootsListNode)
 94770569    {
 94770570        var oldRoot = rootsListNode.Value;
 94770571        oldRoot.RootsListNode = null;
 94770572        Roots.Remove(rootsListNode);
 573
 94770574        return oldRoot;
 94770575    }
 576
 577    /// <summary>
 578    /// Promotes the provided <see cref="TreeNode{T}"/>, to being a root, detaching it from
 579    /// its current parent.
 580    /// </summary>
 581    /// <param name="child">A child of a node of a tree in the forest.</param>
 582    protected virtual void PromoteChildToRoot(TreeNode<T> child)
 74645583    {
 74645584        child.DetachFromParent();
 74645585        AttachToRoots(child);
 74645586    }
 587
 588    #endregion
 589}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_Roots()
get_ItemsCount()
get_MaxRootsListNode()
get_CurrentPushTimestamp()
get_PushTimestampEras()
.ctor()
.ctor(MoreStructures.PriorityQueues.BinomialHeap.BinomialHeapPriorityQueue`1<T>)
get_Count()
GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
Peek()
Push(T,System.Int32)
Pop()
MergeFrom(MoreStructures.PriorityQueues.BinomialHeap.BinomialHeapPriorityQueue`1<T>)
Clear()
RaiseItemPushed(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
RaiseItemPopping(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
RaiseItemsClearing()
RaiseRootMerged(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
UpdateMaxRootsListNodeAfterRootNewOrIncrease(System.Collections.Generic.LinkedListNode`1<MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>>)
UpdateMaxRootsListNode()
AddRoot(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
AttachToRoots(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
MergeEquiDegreeTrees()
MergeRoots(System.Collections.Generic.LinkedListNode`1<MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>>,System.Collections.Generic.LinkedListNode`1<MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>>)
DetachFromRoots(System.Collections.Generic.LinkedListNode`1<MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>>)
PromoteChildToRoot(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)