let MinHeap self trim on empty; cleanup

1 files changed, 80 insertions, 70 deletions

diff --git a/OpenSim/Framework/MinHeap.cs b/OpenSim/Framework/MinHeap.cs
index 99ac25d..68f6668 100644
--- a/OpenSim/Framework/MinHeap.cs
+++ b/OpenSim/Framework/MinHeap.cs
@@ -45,8 +45,8 @@ namespace OpenSim.Framework
 
             internal void Clear()
             {
-                this.index = -1;
-                this.heap = null;
+                index = -1;
+                heap = null;
             }
         }
 
@@ -55,23 +55,26 @@ namespace OpenSim.Framework
             internal T value;
             internal Handle handle;
 
-            internal HeapItem(T value, Handle handle)
+            internal HeapItem(T _value, Handle _handle)
             {
-                this.value = value;
-                this.handle = handle;
+                value = _value;
+                handle = _handle;
             }
 
             internal void Clear()
             {
-                if (this.handle != null)
-                    this.handle.Clear();
-                ClearRef();
+                if (handle != null)
+                {
+                    handle.Clear();
+                    handle = null;
+                }               
+                value = default(T);
             }
 
             internal void ClearRef()
             {
-                this.value = default(T);
-                this.handle = null;
+                value = default(T);
+                handle = null;
             }
         }
 
@@ -81,6 +84,7 @@ namespace OpenSim.Framework
         private int size;
         private object sync_root;
         private int version;
+        private int capacity;
 
         private Comparison<T> comparison;
 
@@ -90,14 +94,15 @@ namespace OpenSim.Framework
         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)
+        public MinHeap(int _capacity, Comparison<T> _comparison)
         {
-            this.items = new HeapItem[capacity];
-            this.comparison = comparison;
-            this.size = this.version = 0;
+            capacity = _capacity;
+            items = new HeapItem[capacity];
+            comparison = _comparison;
+            size = version = 0;
         }
 
-        public int Count { get { return this.size; } }
+        public int Count { get { return size; } }
 
         public bool IsReadOnly { get { return false; } }
 
@@ -108,15 +113,16 @@ namespace OpenSim.Framework
             get
             {
                 Handle handle = ValidateThisHandle(key);
-                return this.items[handle.index].value;
+                return items[handle.index].value;
             }
 
             set
             {
                 Handle handle = ValidateThisHandle(key);
-                this.items[handle.index].value = value;
-                if (!BubbleUp(handle.index))
-                    BubbleDown(handle.index);
+                int indx = handle.index;
+                items[indx].value = value;
+                if (!BubbleUp(indx))
+                    BubbleDown(indx);
             }
         }
 
@@ -124,9 +130,9 @@ namespace OpenSim.Framework
         {
             get
             {
-                if (this.sync_root == null)
-                    Interlocked.CompareExchange<object>(ref this.sync_root, new object(), null);
-                return this.sync_root;
+                if (sync_root == null)
+                    Interlocked.CompareExchange<object>(ref sync_root, new object(), null);
+                return sync_root;
             }
         }
 
@@ -152,27 +158,27 @@ namespace OpenSim.Framework
 
         private void Set(HeapItem item, int index)
         {
-            this.items[index] = item;
+            items[index] = item;
             if (item.handle != null)
                 item.handle.index = index;
         }
 
         private bool BubbleUp(int index)
         {
-            HeapItem item = this.items[index];
+            HeapItem item = items[index];
             int current, parent;
 
             for (current = index, parent = (current - 1) / 2;
-                (current > 0) && (this.comparison(this.items[parent].value, item.value)) > 0;
+                (current > 0) && (comparison(items[parent].value, item.value)) > 0;
                 current = parent, parent = (current - 1) / 2)
             {
-                Set(this.items[parent], current);
+                Set(items[parent], current);
             }
 
             if (current != index)
             {
                 Set(item, current);
-                ++this.version;
+                ++version;
                 return true;
             }
             return false;
@@ -180,24 +186,24 @@ namespace OpenSim.Framework
 
         private void BubbleDown(int index)
         {
-            HeapItem item = this.items[index];
+            HeapItem item = items[index];
             int current, child;
 
             for (current = index, child = (2 * current) + 1;
-                current < this.size / 2;
+                current < 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)
+                if ((child < size - 1) && comparison(items[child].value, items[child + 1].value) > 0)
                     ++child;
-                if (this.comparison(this.items[child].value, item.value) >= 0)
+                if (comparison(items[child].value, item.value) >= 0)
                     break;
-                Set(this.items[child], current);
+                Set(items[child], current);
             }
 
             if (current != index)
             {
                 Set(item, current);
-                ++this.version;
+                ++version;
             }
         }
 
@@ -206,7 +212,7 @@ namespace OpenSim.Framework
             Handle handle = ValidateHandle(key);
             if (handle.index > -1)
             {
-                value = this.items[handle.index].value;
+                value = items[handle.index].value;
                 return true;
             }
             value = default(T);
@@ -228,12 +234,12 @@ namespace OpenSim.Framework
 
         public void Add(T value, IHandle ihandle)
         {
-            if (this.size == this.items.Length)
+            if (size == 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);
+                int capacity = (int)((items.Length * 200L) / 100L);
+                if (capacity < (items.Length + DEFAULT_CAPACITY))
+                    capacity = items.Length + DEFAULT_CAPACITY;
+                Array.Resize<HeapItem>(ref items, capacity);
             }
 
             Handle handle = null;
@@ -245,8 +251,8 @@ namespace OpenSim.Framework
 
             HeapItem item = new MinHeap<T>.HeapItem(value, handle);
 
-            Set(item, this.size);
-            BubbleUp(this.size++);
+            Set(item, size);
+            BubbleUp(size++);
         }
 
         public void Add(T value)
@@ -256,50 +262,54 @@ namespace OpenSim.Framework
 
         public T Min()
         {
-            if (this.size == 0)
+            if (size == 0)
                 throw new InvalidOperationException("Heap is empty");
 
-            return this.items[0].value;
+            return items[0].value;
         }
 
         public void Clear()
         {
-            for (int index = 0; index < this.size; ++index)
-                this.items[index].Clear();
-            this.size = 0;
-            ++this.version;
+            for (int index = 0; index < size; ++index)
+                items[index].Clear();
+            size = 0;
+            if(items.Length > capacity)
+                items = new HeapItem[capacity];
+            ++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));
+            int length = (int)(items.Length * 0.9);
+            if (size < length)
+                Array.Resize<HeapItem>(ref items, Math.Min(size, capacity));
         }
 
         private void RemoveAt(int index)
         {
-            if (this.size == 0)
+            if (size == 0)
                 throw new InvalidOperationException("Heap is empty");
-            if (index >= this.size)
+            if (index >= size)
                 throw new ArgumentOutOfRangeException("index");
 
-            this.items[index].Clear();
-            if (--this.size > 0 && index != this.size)
+            items[index].Clear();
+            if (--size > 0 && index != size)
             {
-                Set(this.items[this.size], index);
-                this.items[this.size].ClearRef();
+                Set(items[size], index);
+                items[size].ClearRef();
                 if (!BubbleUp(index))
                     BubbleDown(index);
             }
+            if(size == 0 && items.Length > 4 * capacity)
+                items = new HeapItem[capacity];
         }
 
         public T RemoveMin()
         {
-            if (this.size == 0)
+            if (size == 0)
                 throw new InvalidOperationException("Heap is empty");
 
-            HeapItem item = this.items[0];
+            HeapItem item = items[0];
             RemoveAt(0);
             return item.value;
         }
@@ -307,7 +317,7 @@ namespace OpenSim.Framework
         public T Remove(IHandle ihandle)
         {
             Handle handle = ValidateThisHandle(ihandle);
-            HeapItem item = this.items[handle.index];
+            HeapItem item = items[handle.index];
             RemoveAt(handle.index);
             return item.value;
         }
@@ -317,9 +327,9 @@ namespace OpenSim.Framework
             EqualityComparer<T> comparer = EqualityComparer<T>.Default;
             int index;
 
-            for (index = 0; index < this.size; ++index)
+            for (index = 0; index < size; ++index)
             {
-                if (comparer.Equals(this.items[index].value, value))
+                if (comparer.Equals(items[index].value, value))
                     return index;
             }
             return -1;
@@ -356,8 +366,8 @@ namespace OpenSim.Framework
             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;
+            for (int i = 0; i < size; ++i)
+                array[index + i] = items[i].value;
         }
 
         public void CopyTo(Array array, int index)
@@ -372,13 +382,13 @@ namespace OpenSim.Framework
             int length = array.Length;
             if ((index < 0) || (index > length))
                 throw new ArgumentOutOfRangeException("index");
-            if ((length - index) < this.size)
+            if ((length - index) < 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);
+                for (int i = 0; i < size; ++i)
+                    array.SetValue(items[i].value, index + i);
             }
             catch (ArrayTypeMismatchException)
             {
@@ -388,13 +398,13 @@ namespace OpenSim.Framework
 
         public IEnumerator<T> GetEnumerator()
         {
-            int version = this.version;
+            int cversion = version;
 
-            for (int index = 0; index < this.size; ++index)
+            for (int index = 0; index < size; ++index)
             {
-                if (version != this.version)
+                if (cversion != version)
                     throw new InvalidOperationException("Heap was modified while enumerating");
-                yield return this.items[index].value;
+                yield return items[index].value;
             }
         }