1 files changed, 406 insertions, 0 deletions

diff --git a/OpenSim/Framework/MinHeap.cs b/OpenSim/Framework/MinHeap.cs
new file mode 100644
index 0000000..99ac25d
--- /dev/null
+++ b/OpenSim/Framework/MinHeap.cs
@@ -0,0 +1,406 @@
+/*
+ * Copyright (c) Contributors, http://opensimulator.org/
+ * See CONTRIBUTORS.TXT for a full list of copyright holders.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in the
+ *       documentation and/or other materials provided with the distribution.
+ *     * Neither the name of the OpenSimulator Project nor the
+ *       names of its contributors may be used to endorse or promote products
+ *       derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+using System;
+using System.Threading;
+using System.Collections;
+using System.Collections.Generic;
+using System.Runtime.InteropServices;
+
+namespace OpenSim.Framework
+{
+    public interface IHandle { }
+
+    [Serializable, ComVisible(false)]
+    public class MinHeap<T> : ICollection<T>, ICollection
+    {
+        private class Handle : IHandle
+        {
+            internal int index = -1;
+            internal MinHeap<T> heap = null;
+
+            internal void Clear()
+            {
+                this.index = -1;
+                this.heap = null;
+            }
+        }
+
+        private struct HeapItem
+        {
+            internal T value;
+            internal Handle handle;
+
+            internal HeapItem(T value, Handle handle)
+            {
+                this.value = value;
+                this.handle = handle;
+            }
+
+            internal void Clear()
+            {
+                if (this.handle != null)
+                    this.handle.Clear();
+                ClearRef();
+            }
+
+            internal void ClearRef()
+            {
+                this.value = default(T);
+                this.handle = null;
+            }
+        }
+
+        public const int DEFAULT_CAPACITY = 4;
+
+        private HeapItem[] items;
+        private int size;
+        private object sync_root;
+        private int version;
+
+        private Comparison<T> comparison;
+
+        public MinHeap() : this(DEFAULT_CAPACITY, Comparer<T>.Default) { }
+        public MinHeap(int capacity) : this(capacity, Comparer<T>.Default) { }
+        public MinHeap(IComparer<T> comparer) : this(DEFAULT_CAPACITY, comparer) { }
+        public MinHeap(int capacity, IComparer<T> comparer) :
+            this(capacity, new Comparison<T>(comparer.Compare)) { }
+        public MinHeap(Comparison<T> comparison) : this(DEFAULT_CAPACITY, comparison) { }
+        public MinHeap(int capacity, Comparison<T> comparison)
+        {
+            this.items = new HeapItem[capacity];
+            this.comparison = comparison;
+            this.size = this.version = 0;
+        }
+
+        public int Count { get { return this.size; } }
+
+        public bool IsReadOnly { get { return false; } }
+
+        public bool IsSynchronized { get { return false; } }
+
+        public T this[IHandle key]
+        {
+            get
+            {
+                Handle handle = ValidateThisHandle(key);
+                return this.items[handle.index].value;
+            }
+
+            set
+            {
+                Handle handle = ValidateThisHandle(key);
+                this.items[handle.index].value = value;
+                if (!BubbleUp(handle.index))
+                    BubbleDown(handle.index);
+            }
+        }
+
+        public object SyncRoot
+        {
+            get
+            {
+                if (this.sync_root == null)
+                    Interlocked.CompareExchange<object>(ref this.sync_root, new object(), null);
+                return this.sync_root;
+            }
+        }
+
+        private Handle ValidateHandle(IHandle ihandle)
+        {
+            if (ihandle == null)
+                throw new ArgumentNullException("handle");
+            Handle handle = ihandle as Handle;
+            if (handle == null)
+                throw new InvalidOperationException("handle is not valid");
+            return handle;
+        }
+
+        private Handle ValidateThisHandle(IHandle ihandle)
+        {
+            Handle handle = ValidateHandle(ihandle);
+            if (!object.ReferenceEquals(handle.heap, this))
+                throw new InvalidOperationException("handle is not valid for this heap");
+            if (handle.index < 0)
+                throw new InvalidOperationException("handle is not associated to a value");
+            return handle;
+        }
+
+        private void Set(HeapItem item, int index)
+        {
+            this.items[index] = item;
+            if (item.handle != null)
+                item.handle.index = index;
+        }
+
+        private bool BubbleUp(int index)
+        {
+            HeapItem item = this.items[index];
+            int current, parent;
+
+            for (current = index, parent = (current - 1) / 2;
+                (current > 0) && (this.comparison(this.items[parent].value, item.value)) > 0;
+                current = parent, parent = (current - 1) / 2)
+            {
+                Set(this.items[parent], current);
+            }
+
+            if (current != index)
+            {
+                Set(item, current);
+                ++this.version;
+                return true;
+            }
+            return false;
+        }
+
+        private void BubbleDown(int index)
+        {
+            HeapItem item = this.items[index];
+            int current, child;
+
+            for (current = index, child = (2 * current) + 1;
+                current < this.size / 2;
+                current = child, child = (2 * current) + 1)
+            {
+                if ((child < this.size - 1) && this.comparison(this.items[child].value, this.items[child + 1].value) > 0)
+                    ++child;
+                if (this.comparison(this.items[child].value, item.value) >= 0)
+                    break;
+                Set(this.items[child], current);
+            }
+
+            if (current != index)
+            {
+                Set(item, current);
+                ++this.version;
+            }
+        }
+
+        public bool TryGetValue(IHandle key, out T value)
+        {
+            Handle handle = ValidateHandle(key);
+            if (handle.index > -1)
+            {
+                value = this.items[handle.index].value;
+                return true;
+            }
+            value = default(T);
+            return false;
+        }
+
+        public bool ContainsHandle(IHandle ihandle)
+        {
+            Handle handle = ValidateHandle(ihandle);
+            return object.ReferenceEquals(handle.heap, this) && handle.index > -1;
+        }
+
+        public void Add(T value, ref IHandle handle)
+        {
+            if (handle == null)
+                handle = new Handle();
+            Add(value, handle);
+        }
+
+        public void Add(T value, IHandle ihandle)
+        {
+            if (this.size == this.items.Length)
+            {
+                int capacity = (int)((this.items.Length * 200L) / 100L);
+                if (capacity < (this.items.Length + DEFAULT_CAPACITY))
+                    capacity = this.items.Length + DEFAULT_CAPACITY;
+                Array.Resize<HeapItem>(ref this.items, capacity);
+            }
+
+            Handle handle = null;
+            if (ihandle != null)
+            {
+                handle = ValidateHandle(ihandle);
+                handle.heap = this;
+            }
+
+            HeapItem item = new MinHeap<T>.HeapItem(value, handle);
+
+            Set(item, this.size);
+            BubbleUp(this.size++);
+        }
+
+        public void Add(T value)
+        {
+            Add(value, null);
+        }
+
+        public T Min()
+        {
+            if (this.size == 0)
+                throw new InvalidOperationException("Heap is empty");
+
+            return this.items[0].value;
+        }
+
+        public void Clear()
+        {
+            for (int index = 0; index < this.size; ++index)
+                this.items[index].Clear();
+            this.size = 0;
+            ++this.version;
+        }
+
+        public void TrimExcess()
+        {
+            int length = (int)(this.items.Length * 0.9);
+            if (this.size < length)
+                Array.Resize<HeapItem>(ref this.items, Math.Min(this.size, DEFAULT_CAPACITY));
+        }
+
+        private void RemoveAt(int index)
+        {
+            if (this.size == 0)
+                throw new InvalidOperationException("Heap is empty");
+            if (index >= this.size)
+                throw new ArgumentOutOfRangeException("index");
+
+            this.items[index].Clear();
+            if (--this.size > 0 && index != this.size)
+            {
+                Set(this.items[this.size], index);
+                this.items[this.size].ClearRef();
+                if (!BubbleUp(index))
+                    BubbleDown(index);
+            }
+        }
+
+        public T RemoveMin()
+        {
+            if (this.size == 0)
+                throw new InvalidOperationException("Heap is empty");
+
+            HeapItem item = this.items[0];
+            RemoveAt(0);
+            return item.value;
+        }
+
+        public T Remove(IHandle ihandle)
+        {
+            Handle handle = ValidateThisHandle(ihandle);
+            HeapItem item = this.items[handle.index];
+            RemoveAt(handle.index);
+            return item.value;
+        }
+
+        private int GetIndex(T value)
+        {
+            EqualityComparer<T> comparer = EqualityComparer<T>.Default;
+            int index;
+
+            for (index = 0; index < this.size; ++index)
+            {
+                if (comparer.Equals(this.items[index].value, value))
+                    return index;
+            }
+            return -1;
+        }
+
+        public bool Contains(T value)
+        {
+            return GetIndex(value) != -1;
+        }
+
+        public bool Remove(T value)
+        {
+            int index = GetIndex(value);
+            if (index != -1)
+            {
+                RemoveAt(index);
+                return true;
+            }
+            return false;
+        }
+
+        public void CopyTo(T[] array, int index)
+        {
+            if (array == null)
+                throw new ArgumentNullException("array");
+            if (array.Rank != 1)
+                throw new ArgumentException("Multidimensional array not supported");
+            if (array.GetLowerBound(0) != 0)
+                throw new ArgumentException("Non-zero lower bound array not supported");
+
+            int length = array.Length;
+            if ((index < 0) || (index > length))
+                throw new ArgumentOutOfRangeException("index");
+            if ((length - index) < this.size)
+                throw new ArgumentException("Not enough space available in array starting at index");
+
+            for (int i = 0; i < this.size; ++i)
+                array[index + i] = this.items[i].value;
+        }
+
+        public void CopyTo(Array array, int index)
+        {
+            if (array == null)
+                throw new ArgumentNullException("array");
+            if (array.Rank != 1)
+                throw new ArgumentException("Multidimensional array not supported");
+            if (array.GetLowerBound(0) != 0)
+                throw new ArgumentException("Non-zero lower bound array not supported");
+
+            int length = array.Length;
+            if ((index < 0) || (index > length))
+                throw new ArgumentOutOfRangeException("index");
+            if ((length - index) < this.size)
+                throw new ArgumentException("Not enough space available in array starting at index");
+
+            try
+            {
+                for (int i = 0; i < this.size; ++i)
+                    array.SetValue(this.items[i].value, index + i);
+            }
+            catch (ArrayTypeMismatchException)
+            {
+                throw new ArgumentException("Invalid array type");
+            }
+        }
+
+        public IEnumerator<T> GetEnumerator()
+        {
+            int version = this.version;
+
+            for (int index = 0; index < this.size; ++index)
+            {
+                if (version != this.version)
+                    throw new InvalidOperationException("Heap was modified while enumerating");
+                yield return this.items[index].value;
+            }
+        }
+
+        IEnumerator IEnumerable.GetEnumerator()
+        {
+            return GetEnumerator();
+        }
+    }
+}