opensim-development – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 eva 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 }