Tanoda
MinHeap.cs
Go to the documentation of this file.
1/******************************************************************************
2 * Copyright (C) Ultraleap, Inc. 2011-2020. *
3 * *
4 * Use subject to the terms of the Apache License 2.0 available at *
5 * http://www.apache.org/licenses/LICENSE-2.0, or another agreement *
6 * between Ultraleap and you, your company or other organization. *
7 ******************************************************************************/
8
9//#define VALIDATE
10using UnityEngine;
11using System;
12
13namespace Leap.Unity {
14
15 public interface IMinHeapNode {
16 int heapIndex { get; set; }
17 }
18
19 public class MinHeap<T> where T : IMinHeapNode, IComparable<T> {
20
21 private T[] _array = new T[4];
22 private int _count = 0;
23
24 public int Count {
25 get {
26 return _count;
27 }
28 }
29
30 public void Clear() {
31 Array.Clear(_array, 0, _count);
32 _count = 0;
33 }
34
35 public void Insert(T element) {
36#if VALIDATE
37 validateHeapInternal("Insert");
38#endif
39
40 //if the array isn't big enough, expand it
41 if (_array.Length == _count) {
42 T[] newArray = new T[_array.Length * 2];
43 Array.Copy(_array, newArray, _array.Length);
44 _array = newArray;
45 }
46
47 element.heapIndex = _count;
48 _count++;
49
50 bubbleUp(element);
51 }
52
53 public void Remove(T element) {
54 removeAt(element.heapIndex);
55 }
56
57 public T PeekMin() {
58 if (_count == 0) {
59 throw new Exception("Cannot peek when there are zero elements!");
60 }
61
62 return _array[0];
63 }
64
65 public T RemoveMin() {
66 if (_count == 0) {
67 throw new Exception("Cannot Remove Min when there are zero elements!");
68 }
69
70 return removeAt(0);
71 }
72
73 private T removeAt(int index) {
74#if VALIDATE
75 validateHeapInternal("Remove At");
76#endif
77
78 T ret = _array[index];
79 _count--;
80
81 if (_count == 0) {
82 return ret;
83 }
84
85 var bottom = _array[_count];
86 bottom.heapIndex = index;
87
88 int parentIndex = getParentIndex(index);
89 if (isValidIndex(parentIndex) && _array[parentIndex].CompareTo(bottom) > 0) {
90 bubbleUp(bottom);
91 } else {
92 bubbleDown(bottom);
93 }
94
95 return ret;
96 }
97
98 private void bubbleUp(T element) {
99 while (true) {
100 if (element.heapIndex == 0) {
101 break;
102 }
103
104 int parentIndex = getParentIndex(element.heapIndex);
105 var parent = _array[parentIndex];
106
107 if (parent.CompareTo(element) <= 0) {
108 break;
109 }
110
111 parent.heapIndex = element.heapIndex;
112 _array[element.heapIndex] = parent;
113
114 element.heapIndex = parentIndex;
115 }
116
117 _array[element.heapIndex] = element;
118
119#if VALIDATE
120 validateHeapInternal("Bubble Up");
121#endif
122 }
123
124 public bool Validate() {
125 return validateHeapInternal("Validation ");
126 }
127
128 private void bubbleDown(T element) {
129 int elementIndex = element.heapIndex;
130
131 while (true) {
132 int leftIndex = getChildLeftIndex(elementIndex);
133 int rightIndex = getChildRightIndex(elementIndex);
134
135 T smallest = element;
136 int smallestIndex = elementIndex;
137
138 if (isValidIndex(leftIndex)) {
139 var leftChild = _array[leftIndex];
140 if (leftChild.CompareTo(smallest) < 0) {
141 smallest = leftChild;
142 smallestIndex = leftIndex;
143 }
144 } else {
145 break;
146 }
147
148 if (isValidIndex(rightIndex)) {
149 var rightChild = _array[rightIndex];
150 if (rightChild.CompareTo(smallest) < 0) {
151 smallest = rightChild;
152 smallestIndex = rightIndex;
153 }
154 }
155
156 if (smallestIndex == elementIndex) {
157 break;
158 }
159
160 smallest.heapIndex = elementIndex;
161 _array[elementIndex] = smallest;
162
163 elementIndex = smallestIndex;
164 }
165
166 element.heapIndex = elementIndex;
167 _array[elementIndex] = element;
168
169#if VALIDATE
170 validateHeapInternal("Bubble Down");
171#endif
172 }
173
174 private bool validateHeapInternal(string operation) {
175 for (int i = 0; i < _count; i++) {
176 if (_array[i].heapIndex != i) {
177 Debug.LogError("Element " + i + " had an index of " + _array[i].heapIndex + " instead, after " + operation);
178 return false;
179 }
180
181 if (i != 0) {
182 var parent = _array[getParentIndex(i)];
183 if (parent.CompareTo(_array[i]) > 0) {
184 Debug.LogError("Element " + i + " had an incorrect order after " + operation);
185 return false;
186 }
187 }
188 }
189 return true;
190 }
191
192 private static int getChildLeftIndex(int index) {
193 return index * 2 + 1;
194 }
195
196 private static int getChildRightIndex(int index) {
197 return index * 2 + 2;
198 }
199
200 private static int getParentIndex(int index) {
201 return (index - 1) / 2;
202 }
203
204 private bool isValidIndex(int index) {
205 return index < _count && index >= 0;
206 }
207 }
208}
UnityEngine.Debug Debug
Definition: TanodaServer.cs:19
void Insert(T element)
Definition: MinHeap.cs:35
void Remove(T element)
Definition: MinHeap.cs:53