1
0

PriorityQueue.cs 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149
  1. // this code is borrowed from RxOfficial(rx.codeplex.com) and modified
  2. using System;
  3. using System.Collections.Generic;
  4. using System.Text;
  5. using System.Threading;
  6. namespace UniRx.InternalUtil
  7. {
  8. internal class PriorityQueue<T> where T : IComparable<T>
  9. {
  10. private static long _count = long.MinValue;
  11. private IndexedItem[] _items;
  12. private int _size;
  13. public PriorityQueue()
  14. : this(16)
  15. {
  16. }
  17. public PriorityQueue(int capacity)
  18. {
  19. _items = new IndexedItem[capacity];
  20. _size = 0;
  21. }
  22. private bool IsHigherPriority(int left, int right)
  23. {
  24. return _items[left].CompareTo(_items[right]) < 0;
  25. }
  26. private void Percolate(int index)
  27. {
  28. if (index >= _size || index < 0)
  29. return;
  30. var parent = (index - 1) / 2;
  31. if (parent < 0 || parent == index)
  32. return;
  33. if (IsHigherPriority(index, parent))
  34. {
  35. var temp = _items[index];
  36. _items[index] = _items[parent];
  37. _items[parent] = temp;
  38. Percolate(parent);
  39. }
  40. }
  41. private void Heapify()
  42. {
  43. Heapify(0);
  44. }
  45. private void Heapify(int index)
  46. {
  47. if (index >= _size || index < 0)
  48. return;
  49. var left = 2 * index + 1;
  50. var right = 2 * index + 2;
  51. var first = index;
  52. if (left < _size && IsHigherPriority(left, first))
  53. first = left;
  54. if (right < _size && IsHigherPriority(right, first))
  55. first = right;
  56. if (first != index)
  57. {
  58. var temp = _items[index];
  59. _items[index] = _items[first];
  60. _items[first] = temp;
  61. Heapify(first);
  62. }
  63. }
  64. public int Count { get { return _size; } }
  65. public T Peek()
  66. {
  67. if (_size == 0)
  68. throw new InvalidOperationException("HEAP is Empty");
  69. return _items[0].Value;
  70. }
  71. private void RemoveAt(int index)
  72. {
  73. _items[index] = _items[--_size];
  74. _items[_size] = default(IndexedItem);
  75. Heapify();
  76. if (_size < _items.Length / 4)
  77. {
  78. var temp = _items;
  79. _items = new IndexedItem[_items.Length / 2];
  80. Array.Copy(temp, 0, _items, 0, _size);
  81. }
  82. }
  83. public T Dequeue()
  84. {
  85. var result = Peek();
  86. RemoveAt(0);
  87. return result;
  88. }
  89. public void Enqueue(T item)
  90. {
  91. if (_size >= _items.Length)
  92. {
  93. var temp = _items;
  94. _items = new IndexedItem[_items.Length * 2];
  95. Array.Copy(temp, _items, temp.Length);
  96. }
  97. var index = _size++;
  98. _items[index] = new IndexedItem { Value = item, Id = Interlocked.Increment(ref _count) };
  99. Percolate(index);
  100. }
  101. public bool Remove(T item)
  102. {
  103. for (var i = 0; i < _size; ++i)
  104. {
  105. if (EqualityComparer<T>.Default.Equals(_items[i].Value, item))
  106. {
  107. RemoveAt(i);
  108. return true;
  109. }
  110. }
  111. return false;
  112. }
  113. struct IndexedItem : IComparable<IndexedItem>
  114. {
  115. public T Value;
  116. public long Id;
  117. public int CompareTo(IndexedItem other)
  118. {
  119. var c = Value.CompareTo(other.Value);
  120. if (c == 0)
  121. c = Id.CompareTo(other.Id);
  122. return c;
  123. }
  124. }
  125. }
  126. }