aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Framework/MinHeap.cs
diff options
context:
space:
mode:
Diffstat (limited to '')
-rwxr-xr-xOpenSim/Framework/MinHeap.cs375
1 files changed, 375 insertions, 0 deletions
diff --git a/OpenSim/Framework/MinHeap.cs b/OpenSim/Framework/MinHeap.cs
new file mode 100755
index 0000000..ad39bbc
--- /dev/null
+++ b/OpenSim/Framework/MinHeap.cs
@@ -0,0 +1,375 @@
1using System;
2using System.Threading;
3using System.Collections;
4using System.Collections.Generic;
5using System.Runtime.InteropServices;
6
7namespace OpenSim.Framework
8{
9 public interface IHandle { }
10
11 [Serializable, ComVisible(false)]
12 public class MinHeap<T> : ICollection<T>, ICollection
13 {
14 private class Handle : IHandle
15 {
16 internal int index = -1;
17 internal MinHeap<T> heap = null;
18
19 internal void Clear()
20 {
21 this.index = -1;
22 this.heap = null;
23 }
24 }
25
26 private struct HeapItem
27 {
28 internal T value;
29 internal Handle handle;
30
31 internal HeapItem(T value, Handle handle)
32 {
33 this.value = value;
34 this.handle = handle;
35 }
36
37 internal void Clear()
38 {
39 this.value = default(T);
40 if (this.handle != null)
41 {
42 this.handle.Clear();
43 this.handle = null;
44 }
45 }
46 }
47
48 public const int DEFAULT_CAPACITY = 4;
49
50 private HeapItem[] items;
51 private int size;
52 private object sync_root;
53 private int version;
54
55 private Comparison<T> comparison;
56
57 public MinHeap() : this(DEFAULT_CAPACITY, Comparer<T>.Default) { }
58 public MinHeap(int capacity) : this(capacity, Comparer<T>.Default) { }
59 public MinHeap(IComparer<T> comparer) : this(DEFAULT_CAPACITY, comparer) { }
60 public MinHeap(int capacity, IComparer<T> comparer) :
61 this(capacity, new Comparison<T>(comparer.Compare)) { }
62 public MinHeap(Comparison<T> comparison) : this(DEFAULT_CAPACITY, comparison) { }
63 public MinHeap(int capacity, Comparison<T> comparison)
64 {
65 this.items = new HeapItem[capacity];
66 this.comparison = comparison;
67 this.size = this.version = 0;
68 }
69
70 public int Count { get { return this.size; } }
71
72 public bool IsReadOnly { get { return false; } }
73
74 public bool IsSynchronized { get { return false; } }
75
76 public T this[IHandle key]
77 {
78 get
79 {
80 Handle handle = ValidateThisHandle(key);
81 return this.items[handle.index].value;
82 }
83
84 set
85 {
86 Handle handle = ValidateThisHandle(key);
87 this.items[handle.index].value = value;
88 if (!BubbleUp(handle.index))
89 BubbleDown(handle.index);
90 }
91 }
92
93 public object SyncRoot
94 {
95 get
96 {
97 if (this.sync_root == null)
98 Interlocked.CompareExchange<object>(ref this.sync_root, new object(), null);
99 return this.sync_root;
100 }
101 }
102
103 private Handle ValidateHandle(IHandle ihandle)
104 {
105 if (ihandle == null)
106 throw new ArgumentNullException("handle");
107 Handle handle = ihandle as Handle;
108 if (handle == null)
109 throw new InvalidOperationException("handle is not valid");
110 return handle;
111 }
112
113 private Handle ValidateThisHandle(IHandle ihandle)
114 {
115 Handle handle = ValidateHandle(ihandle);
116 if (!object.ReferenceEquals(handle.heap, this))
117 throw new InvalidOperationException("handle is not valid for this heap");
118 if (handle.index < 0)
119 throw new InvalidOperationException("handle is not associated to a value");
120 return handle;
121 }
122
123 private void Set(HeapItem item, int index)
124 {
125 this.items[index] = item;
126 if (item.handle != null)
127 item.handle.index = index;
128 }
129
130 private bool BubbleUp(int index)
131 {
132 HeapItem item = this.items[index];
133 int current, parent;
134
135 for (current = index, parent = (current - 1) / 2;
136 (current > 0) && (this.comparison(this.items[parent].value, item.value)) > 0;
137 current = parent, parent = (current - 1) / 2)
138 {
139 Set(this.items[parent], current);
140 }
141
142 if (current != index)
143 {
144 Set(item, current);
145 ++this.version;
146 return true;
147 }
148 return false;
149 }
150
151 private void BubbleDown(int index)
152 {
153 HeapItem item = this.items[index];
154 int current, child;
155
156 for (current = index, child = (2 * current) + 1;
157 current < this.size / 2;
158 current = child, child = (2 * current) + 1)
159 {
160 if ((child < this.size - 1) && this.comparison(this.items[child].value, this.items[child + 1].value) > 0)
161 ++child;
162 if (this.comparison(this.items[child].value, item.value) >= 0)
163 break;
164 Set(this.items[child], current);
165 }
166
167 if (current != index)
168 {
169 Set(item, current);
170 ++this.version;
171 }
172 }
173
174 public bool TryGetValue(IHandle key, out T value)
175 {
176 Handle handle = ValidateHandle(key);
177 if (handle.index > -1)
178 {
179 value = this.items[handle.index].value;
180 return true;
181 }
182 value = default(T);
183 return false;
184 }
185
186 public bool ContainsHandle(IHandle ihandle)
187 {
188 Handle handle = ValidateHandle(ihandle);
189 return object.ReferenceEquals(handle.heap, this) && handle.index > -1;
190 }
191
192 public void Add(T value, ref IHandle handle)
193 {
194 if (handle == null)
195 handle = new Handle();
196 Add(value, handle);
197 }
198
199 public void Add(T value, IHandle ihandle)
200 {
201 if (this.size == this.items.Length)
202 {
203 int capacity = (int)((this.items.Length * 200L) / 100L);
204 if (capacity < (this.items.Length + DEFAULT_CAPACITY))
205 capacity = this.items.Length + DEFAULT_CAPACITY;
206 Array.Resize<HeapItem>(ref this.items, capacity);
207 }
208
209 Handle handle = null;
210 if (ihandle != null)
211 {
212 handle = ValidateHandle(ihandle);
213 handle.heap = this;
214 }
215
216 HeapItem item = new MinHeap<T>.HeapItem(value, handle);
217
218 Set(item, this.size);
219 BubbleUp(this.size++);
220 }
221
222 public void Add(T value)
223 {
224 Add(value, null);
225 }
226
227 public T Min()
228 {
229 if (this.size == 0)
230 throw new InvalidOperationException("Heap is empty");
231
232 return this.items[0].value;
233 }
234
235 public void Clear()
236 {
237 for (int index = 0; index < this.size; ++index)
238 this.items[index].Clear();
239 this.size = 0;
240 ++this.version;
241 }
242
243 public void TrimExcess()
244 {
245 int length = (int)(this.items.Length * 0.9);
246 if (this.size < length)
247 Array.Resize<HeapItem>(ref this.items, Math.Min(this.size, DEFAULT_CAPACITY));
248 }
249
250 private void RemoveAt(int index)
251 {
252 if (this.size == 0)
253 throw new InvalidOperationException("Heap is empty");
254 if (index >= this.size)
255 throw new ArgumentOutOfRangeException("index");
256
257 this.items[index].Clear();
258 if (--this.size > 0 && index != this.size)
259 {
260 Set(this.items[this.size], index);
261 if (!BubbleUp(index))
262 BubbleDown(index);
263 }
264 }
265
266 public T RemoveMin()
267 {
268 if (this.size == 0)
269 throw new InvalidOperationException("Heap is empty");
270
271 HeapItem item = this.items[0];
272 RemoveAt(0);
273 return item.value;
274 }
275
276 public T Remove(IHandle ihandle)
277 {
278 Handle handle = ValidateThisHandle(ihandle);
279 HeapItem item = this.items[handle.index];
280 RemoveAt(handle.index);
281 return item.value;
282 }
283
284 private int GetIndex(T value)
285 {
286 EqualityComparer<T> comparer = EqualityComparer<T>.Default;
287 int index;
288
289 for (index = 0; index < this.size; ++index)
290 {
291 if (comparer.Equals(this.items[index].value, value))
292 return index;
293 }
294 return -1;
295 }
296
297 public bool Contains(T value)
298 {
299 return GetIndex(value) != -1;
300 }
301
302 public bool Remove(T value)
303 {
304 int index = GetIndex(value);
305 if (index != -1)
306 {
307 RemoveAt(index);
308 return true;
309 }
310 return false;
311 }
312
313 public void CopyTo(T[] array, int index)
314 {
315 if (array == null)
316 throw new ArgumentNullException("array");
317 if (array.Rank != 1)
318 throw new ArgumentException("Multidimensional array not supported");
319 if (array.GetLowerBound(0) != 0)
320 throw new ArgumentException("Non-zero lower bound array not supported");
321
322 int length = array.Length;
323 if ((index < 0) || (index > length))
324 throw new ArgumentOutOfRangeException("index");
325 if ((length - index) < this.size)
326 throw new ArgumentException("Not enough space available in array starting at index");
327
328 for (int i = 0; i < this.size; ++i)
329 array[index + i] = this.items[i].value;
330 }
331
332 public void CopyTo(Array array, int index)
333 {
334 if (array == null)
335 throw new ArgumentNullException("array");
336 if (array.Rank != 1)
337 throw new ArgumentException("Multidimensional array not supported");
338 if (array.GetLowerBound(0) != 0)
339 throw new ArgumentException("Non-zero lower bound array not supported");
340
341 int length = array.Length;
342 if ((index < 0) || (index > length))
343 throw new ArgumentOutOfRangeException("index");
344 if ((length - index) < this.size)
345 throw new ArgumentException("Not enough space available in array starting at index");
346
347 try
348 {
349 for (int i = 0; i < this.size; ++i)
350 array.SetValue(this.items[i].value, index + i);
351 }
352 catch (ArrayTypeMismatchException)
353 {
354 throw new ArgumentException("Invalid array type");
355 }
356 }
357
358 public IEnumerator<T> GetEnumerator()
359 {
360 int version = this.version;
361
362 for (int index = 0; index < this.size; ++index)
363 {
364 if (version != this.version)
365 throw new InvalidOperationException("Heap was modified while enumerating");
366 yield return this.items[index].value;
367 }
368 }
369
370 IEnumerator IEnumerable.GetEnumerator()
371 {
372 return GetEnumerator();
373 }
374 }
375}
generated by cgit v1.1 at 2024-12-19 09:46:14 +0000