clockwerk-opensim – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | vero | 1 | /* |
2 | * Copyright (c) Contributors, http://opensimulator.org/ |
||
3 | * See CONTRIBUTORS.TXT for a full list of copyright holders. |
||
4 | * |
||
5 | * Redistribution and use in source and binary forms, with or without |
||
6 | * modification, are permitted provided that the following conditions are met: |
||
7 | * * Redistributions of source code must retain the above copyright |
||
8 | * notice, this list of conditions and the following disclaimer. |
||
9 | * * Redistributions in binary form must reproduce the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer in the |
||
11 | * documentation and/or other materials provided with the distribution. |
||
12 | * * Neither the name of the OpenSimulator Project nor the |
||
13 | * names of its contributors may be used to endorse or promote products |
||
14 | * derived from this software without specific prior written permission. |
||
15 | * |
||
16 | * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY |
||
17 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
||
18 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
||
19 | * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY |
||
20 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
||
21 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
||
22 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
||
23 | * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
24 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
||
25 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
26 | */ |
||
27 | |||
28 | using System; |
||
29 | using System.Threading; |
||
30 | using System.Collections; |
||
31 | using System.Collections.Generic; |
||
32 | using System.Runtime.InteropServices; |
||
33 | |||
34 | namespace OpenSim.Framework |
||
35 | { |
||
36 | public interface IHandle { } |
||
37 | |||
38 | [Serializable, ComVisible(false)] |
||
39 | public class MinHeap<T> : ICollection<T>, ICollection |
||
40 | { |
||
41 | private class Handle : IHandle |
||
42 | { |
||
43 | internal int index = -1; |
||
44 | internal MinHeap<T> heap = null; |
||
45 | |||
46 | internal void Clear() |
||
47 | { |
||
48 | this.index = -1; |
||
49 | this.heap = null; |
||
50 | } |
||
51 | } |
||
52 | |||
53 | private struct HeapItem |
||
54 | { |
||
55 | internal T value; |
||
56 | internal Handle handle; |
||
57 | |||
58 | internal HeapItem(T value, Handle handle) |
||
59 | { |
||
60 | this.value = value; |
||
61 | this.handle = handle; |
||
62 | } |
||
63 | |||
64 | internal void Clear() |
||
65 | { |
||
66 | if (this.handle != null) |
||
67 | this.handle.Clear(); |
||
68 | ClearRef(); |
||
69 | } |
||
70 | |||
71 | internal void ClearRef() |
||
72 | { |
||
73 | this.value = default(T); |
||
74 | this.handle = null; |
||
75 | } |
||
76 | } |
||
77 | |||
78 | public const int DEFAULT_CAPACITY = 4; |
||
79 | |||
80 | private HeapItem[] items; |
||
81 | private int size; |
||
82 | private object sync_root; |
||
83 | private int version; |
||
84 | |||
85 | private Comparison<T> comparison; |
||
86 | |||
87 | public MinHeap() : this(DEFAULT_CAPACITY, Comparer<T>.Default) { } |
||
88 | public MinHeap(int capacity) : this(capacity, Comparer<T>.Default) { } |
||
89 | public MinHeap(IComparer<T> comparer) : this(DEFAULT_CAPACITY, comparer) { } |
||
90 | public MinHeap(int capacity, IComparer<T> comparer) : |
||
91 | this(capacity, new Comparison<T>(comparer.Compare)) { } |
||
92 | public MinHeap(Comparison<T> comparison) : this(DEFAULT_CAPACITY, comparison) { } |
||
93 | public MinHeap(int capacity, Comparison<T> comparison) |
||
94 | { |
||
95 | this.items = new HeapItem[capacity]; |
||
96 | this.comparison = comparison; |
||
97 | this.size = this.version = 0; |
||
98 | } |
||
99 | |||
100 | public int Count { get { return this.size; } } |
||
101 | |||
102 | public bool IsReadOnly { get { return false; } } |
||
103 | |||
104 | public bool IsSynchronized { get { return false; } } |
||
105 | |||
106 | public T this[IHandle key] |
||
107 | { |
||
108 | get |
||
109 | { |
||
110 | Handle handle = ValidateThisHandle(key); |
||
111 | return this.items[handle.index].value; |
||
112 | } |
||
113 | |||
114 | set |
||
115 | { |
||
116 | Handle handle = ValidateThisHandle(key); |
||
117 | this.items[handle.index].value = value; |
||
118 | if (!BubbleUp(handle.index)) |
||
119 | BubbleDown(handle.index); |
||
120 | } |
||
121 | } |
||
122 | |||
123 | public object SyncRoot |
||
124 | { |
||
125 | get |
||
126 | { |
||
127 | if (this.sync_root == null) |
||
128 | Interlocked.CompareExchange<object>(ref this.sync_root, new object(), null); |
||
129 | return this.sync_root; |
||
130 | } |
||
131 | } |
||
132 | |||
133 | private Handle ValidateHandle(IHandle ihandle) |
||
134 | { |
||
135 | if (ihandle == null) |
||
136 | throw new ArgumentNullException("handle"); |
||
137 | Handle handle = ihandle as Handle; |
||
138 | if (handle == null) |
||
139 | throw new InvalidOperationException("handle is not valid"); |
||
140 | return handle; |
||
141 | } |
||
142 | |||
143 | private Handle ValidateThisHandle(IHandle ihandle) |
||
144 | { |
||
145 | Handle handle = ValidateHandle(ihandle); |
||
146 | if (!object.ReferenceEquals(handle.heap, this)) |
||
147 | throw new InvalidOperationException("handle is not valid for this heap"); |
||
148 | if (handle.index < 0) |
||
149 | throw new InvalidOperationException("handle is not associated to a value"); |
||
150 | return handle; |
||
151 | } |
||
152 | |||
153 | private void Set(HeapItem item, int index) |
||
154 | { |
||
155 | this.items[index] = item; |
||
156 | if (item.handle != null) |
||
157 | item.handle.index = index; |
||
158 | } |
||
159 | |||
160 | private bool BubbleUp(int index) |
||
161 | { |
||
162 | HeapItem item = this.items[index]; |
||
163 | int current, parent; |
||
164 | |||
165 | for (current = index, parent = (current - 1) / 2; |
||
166 | (current > 0) && (this.comparison(this.items[parent].value, item.value)) > 0; |
||
167 | current = parent, parent = (current - 1) / 2) |
||
168 | { |
||
169 | Set(this.items[parent], current); |
||
170 | } |
||
171 | |||
172 | if (current != index) |
||
173 | { |
||
174 | Set(item, current); |
||
175 | ++this.version; |
||
176 | return true; |
||
177 | } |
||
178 | return false; |
||
179 | } |
||
180 | |||
181 | private void BubbleDown(int index) |
||
182 | { |
||
183 | HeapItem item = this.items[index]; |
||
184 | int current, child; |
||
185 | |||
186 | for (current = index, child = (2 * current) + 1; |
||
187 | current < this.size / 2; |
||
188 | current = child, child = (2 * current) + 1) |
||
189 | { |
||
190 | if ((child < this.size - 1) && this.comparison(this.items[child].value, this.items[child + 1].value) > 0) |
||
191 | ++child; |
||
192 | if (this.comparison(this.items[child].value, item.value) >= 0) |
||
193 | break; |
||
194 | Set(this.items[child], current); |
||
195 | } |
||
196 | |||
197 | if (current != index) |
||
198 | { |
||
199 | Set(item, current); |
||
200 | ++this.version; |
||
201 | } |
||
202 | } |
||
203 | |||
204 | public bool TryGetValue(IHandle key, out T value) |
||
205 | { |
||
206 | Handle handle = ValidateHandle(key); |
||
207 | if (handle.index > -1) |
||
208 | { |
||
209 | value = this.items[handle.index].value; |
||
210 | return true; |
||
211 | } |
||
212 | value = default(T); |
||
213 | return false; |
||
214 | } |
||
215 | |||
216 | public bool ContainsHandle(IHandle ihandle) |
||
217 | { |
||
218 | Handle handle = ValidateHandle(ihandle); |
||
219 | return object.ReferenceEquals(handle.heap, this) && handle.index > -1; |
||
220 | } |
||
221 | |||
222 | public void Add(T value, ref IHandle handle) |
||
223 | { |
||
224 | if (handle == null) |
||
225 | handle = new Handle(); |
||
226 | Add(value, handle); |
||
227 | } |
||
228 | |||
229 | public void Add(T value, IHandle ihandle) |
||
230 | { |
||
231 | if (this.size == this.items.Length) |
||
232 | { |
||
233 | int capacity = (int)((this.items.Length * 200L) / 100L); |
||
234 | if (capacity < (this.items.Length + DEFAULT_CAPACITY)) |
||
235 | capacity = this.items.Length + DEFAULT_CAPACITY; |
||
236 | Array.Resize<HeapItem>(ref this.items, capacity); |
||
237 | } |
||
238 | |||
239 | Handle handle = null; |
||
240 | if (ihandle != null) |
||
241 | { |
||
242 | handle = ValidateHandle(ihandle); |
||
243 | handle.heap = this; |
||
244 | } |
||
245 | |||
246 | HeapItem item = new MinHeap<T>.HeapItem(value, handle); |
||
247 | |||
248 | Set(item, this.size); |
||
249 | BubbleUp(this.size++); |
||
250 | } |
||
251 | |||
252 | public void Add(T value) |
||
253 | { |
||
254 | Add(value, null); |
||
255 | } |
||
256 | |||
257 | public T Min() |
||
258 | { |
||
259 | if (this.size == 0) |
||
260 | throw new InvalidOperationException("Heap is empty"); |
||
261 | |||
262 | return this.items[0].value; |
||
263 | } |
||
264 | |||
265 | public void Clear() |
||
266 | { |
||
267 | for (int index = 0; index < this.size; ++index) |
||
268 | this.items[index].Clear(); |
||
269 | this.size = 0; |
||
270 | ++this.version; |
||
271 | } |
||
272 | |||
273 | public void TrimExcess() |
||
274 | { |
||
275 | int length = (int)(this.items.Length * 0.9); |
||
276 | if (this.size < length) |
||
277 | Array.Resize<HeapItem>(ref this.items, Math.Min(this.size, DEFAULT_CAPACITY)); |
||
278 | } |
||
279 | |||
280 | private void RemoveAt(int index) |
||
281 | { |
||
282 | if (this.size == 0) |
||
283 | throw new InvalidOperationException("Heap is empty"); |
||
284 | if (index >= this.size) |
||
285 | throw new ArgumentOutOfRangeException("index"); |
||
286 | |||
287 | this.items[index].Clear(); |
||
288 | if (--this.size > 0 && index != this.size) |
||
289 | { |
||
290 | Set(this.items[this.size], index); |
||
291 | this.items[this.size].ClearRef(); |
||
292 | if (!BubbleUp(index)) |
||
293 | BubbleDown(index); |
||
294 | } |
||
295 | } |
||
296 | |||
297 | public T RemoveMin() |
||
298 | { |
||
299 | if (this.size == 0) |
||
300 | throw new InvalidOperationException("Heap is empty"); |
||
301 | |||
302 | HeapItem item = this.items[0]; |
||
303 | RemoveAt(0); |
||
304 | return item.value; |
||
305 | } |
||
306 | |||
307 | public T Remove(IHandle ihandle) |
||
308 | { |
||
309 | Handle handle = ValidateThisHandle(ihandle); |
||
310 | HeapItem item = this.items[handle.index]; |
||
311 | RemoveAt(handle.index); |
||
312 | return item.value; |
||
313 | } |
||
314 | |||
315 | private int GetIndex(T value) |
||
316 | { |
||
317 | EqualityComparer<T> comparer = EqualityComparer<T>.Default; |
||
318 | int index; |
||
319 | |||
320 | for (index = 0; index < this.size; ++index) |
||
321 | { |
||
322 | if (comparer.Equals(this.items[index].value, value)) |
||
323 | return index; |
||
324 | } |
||
325 | return -1; |
||
326 | } |
||
327 | |||
328 | public bool Contains(T value) |
||
329 | { |
||
330 | return GetIndex(value) != -1; |
||
331 | } |
||
332 | |||
333 | public bool Remove(T value) |
||
334 | { |
||
335 | int index = GetIndex(value); |
||
336 | if (index != -1) |
||
337 | { |
||
338 | RemoveAt(index); |
||
339 | return true; |
||
340 | } |
||
341 | return false; |
||
342 | } |
||
343 | |||
344 | public void CopyTo(T[] array, int index) |
||
345 | { |
||
346 | if (array == null) |
||
347 | throw new ArgumentNullException("array"); |
||
348 | if (array.Rank != 1) |
||
349 | throw new ArgumentException("Multidimensional array not supported"); |
||
350 | if (array.GetLowerBound(0) != 0) |
||
351 | throw new ArgumentException("Non-zero lower bound array not supported"); |
||
352 | |||
353 | int length = array.Length; |
||
354 | if ((index < 0) || (index > length)) |
||
355 | throw new ArgumentOutOfRangeException("index"); |
||
356 | if ((length - index) < this.size) |
||
357 | throw new ArgumentException("Not enough space available in array starting at index"); |
||
358 | |||
359 | for (int i = 0; i < this.size; ++i) |
||
360 | array[index + i] = this.items[i].value; |
||
361 | } |
||
362 | |||
363 | public void CopyTo(Array array, int index) |
||
364 | { |
||
365 | if (array == null) |
||
366 | throw new ArgumentNullException("array"); |
||
367 | if (array.Rank != 1) |
||
368 | throw new ArgumentException("Multidimensional array not supported"); |
||
369 | if (array.GetLowerBound(0) != 0) |
||
370 | throw new ArgumentException("Non-zero lower bound array not supported"); |
||
371 | |||
372 | int length = array.Length; |
||
373 | if ((index < 0) || (index > length)) |
||
374 | throw new ArgumentOutOfRangeException("index"); |
||
375 | if ((length - index) < this.size) |
||
376 | throw new ArgumentException("Not enough space available in array starting at index"); |
||
377 | |||
378 | try |
||
379 | { |
||
380 | for (int i = 0; i < this.size; ++i) |
||
381 | array.SetValue(this.items[i].value, index + i); |
||
382 | } |
||
383 | catch (ArrayTypeMismatchException) |
||
384 | { |
||
385 | throw new ArgumentException("Invalid array type"); |
||
386 | } |
||
387 | } |
||
388 | |||
389 | public IEnumerator<T> GetEnumerator() |
||
390 | { |
||
391 | int version = this.version; |
||
392 | |||
393 | for (int index = 0; index < this.size; ++index) |
||
394 | { |
||
395 | if (version != this.version) |
||
396 | throw new InvalidOperationException("Heap was modified while enumerating"); |
||
397 | yield return this.items[index].value; |
||
398 | } |
||
399 | } |
||
400 | |||
401 | IEnumerator IEnumerable.GetEnumerator() |
||
402 | { |
||
403 | return GetEnumerator(); |
||
404 | } |
||
405 | } |
||
406 | } |