Pro_Unit

HeapQueue

Nov 30th, 2020
494
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace Platformer.Core
  5. {
  6.     /// <summary>
  7.     /// HeapQueue provides a queue collection that is always ordered.
  8.     /// </summary>
  9.     /// <typeparam name="T"></typeparam>
  10.     public class HeapQueue<T> where T : IComparable<T>
  11.     {
  12.         List<T> items;
  13.  
  14.         public int Count { get { return items.Count; } }
  15.  
  16.         public bool IsEmpty { get { return items.Count == 0; } }
  17.  
  18.         public T First { get { return items[0]; } }
  19.  
  20.         public void Clear() => items.Clear();
  21.  
  22.         public bool Contains(T item) => items.Contains(item);
  23.  
  24.         public void Remove(T item) => items.Remove(item);
  25.  
  26.         public T Peek() => items[0];
  27.  
  28.         public HeapQueue()
  29.         {
  30.             items = new List<T>();
  31.         }
  32.  
  33.         public void Push(T item)
  34.         {
  35.             //add item to end of tree to extend the list
  36.             items.Add(item);
  37.             //find correct position for new item.
  38.             SiftDown(0, items.Count - 1);
  39.         }
  40.  
  41.         public T Pop()
  42.         {
  43.  
  44.             //if there are more than 1 items, returned item will be first in tree.
  45.             //then, add last item to front of tree, shrink the list
  46.             //and find correct index in tree for first item.
  47.             T item;
  48.             var last = items[items.Count - 1];
  49.             items.RemoveAt(items.Count - 1);
  50.             if (items.Count > 0)
  51.             {
  52.                 item = items[0];
  53.                 items[0] = last;
  54.                 SiftUp();
  55.             }
  56.             else
  57.             {
  58.                 item = last;
  59.             }
  60.             return item;
  61.         }
  62.  
  63.  
  64.         int Compare(T A, T B) => A.CompareTo(B);
  65.  
  66.         void SiftDown(int startpos, int pos)
  67.         {
  68.             //preserve the newly added item.
  69.             var newitem = items[pos];
  70.             while (pos > startpos)
  71.             {
  72.                 //find parent index in binary tree
  73.                 var parentpos = (pos - 1) >> 1;
  74.                 var parent = items[parentpos];
  75.                 //if new item precedes or equal to parent, pos is new item position.
  76.                 if (Compare(parent, newitem) <= 0)
  77.                     break;
  78.                 //else move parent into pos, then repeat for grand parent.
  79.                 items[pos] = parent;
  80.                 pos = parentpos;
  81.             }
  82.             items[pos] = newitem;
  83.         }
  84.  
  85.         void SiftUp()
  86.         {
  87.             var endpos = items.Count;
  88.             var startpos = 0;
  89.             //preserve the inserted item
  90.             var newitem = items[0];
  91.             var childpos = 1;
  92.             var pos = 0;
  93.             //find child position to insert into binary tree
  94.             while (childpos < endpos)
  95.             {
  96.                 //get right branch
  97.                 var rightpos = childpos + 1;
  98.                 //if right branch should precede left branch, move right branch up the tree
  99.                 if (rightpos < endpos && Compare(items[rightpos], items[childpos]) <= 0)
  100.                     childpos = rightpos;
  101.                 //move child up the tree
  102.                 items[pos] = items[childpos];
  103.                 pos = childpos;
  104.                 //move down the tree and repeat.
  105.                 childpos = 2 * pos + 1;
  106.             }
  107.             //the child position for the new item.
  108.             items[pos] = newitem;
  109.             SiftDown(startpos, pos);
  110.         }
  111.     }
  112. }
RAW Paste Data