From 960dc370960a97a7bebb113cf73d89e168cd6f3e Mon Sep 17 00:00:00 2001
From: Toby Vincent <tobyv13@gmail.com>
Date: Thu, 25 Mar 2021 00:39:48 +0000
Subject: refactored project layout

---
 PriorityQueue.cs | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)
 create mode 100755 PriorityQueue.cs

(limited to 'PriorityQueue.cs')

diff --git a/PriorityQueue.cs b/PriorityQueue.cs
new file mode 100755
index 0000000..d708f58
--- /dev/null
+++ b/PriorityQueue.cs
@@ -0,0 +1,90 @@
+using System;
+using PriorityQueue.Interfaces;
+
+namespace PriorityQueue
+{
+    public class PriorityQueue<T, U> : Heap<T, U> where T : INode<U> where U : IComparable<U>
+    {
+        static readonly U _maxValue = (U)typeof(U).GetField("MaxValue").GetValue(null);
+        static readonly U _minValue = (U)typeof(U).GetField("MinValue").GetValue(null);
+
+        public U LeastSignificant { get => IsMin ? _maxValue : _minValue; }
+        public int[] Location { get; set; }
+        
+        // indexer
+        public T this[int i] { get => Array[Location[i]]; }
+
+        public PriorityQueue(int size, bool isMin = false)
+            : this(new T[size], isMin) { }
+
+        public PriorityQueue(T[] array, bool isMin = false)
+            : base(array, isMin)
+        {
+            Location = new int[Array.Length];
+            for (int i = 0; i < HeapSize; i++)
+                Location[Array[i].Id] = i;
+        }
+
+        // swap two indexies
+        public new void Swap(int first, int second)
+        {
+            // swap in heap
+            base.Swap(first, second);
+
+            // swap in location table
+            Location[Array[first].Id] = first;
+            Location[Array[second].Id] = second;
+        }
+
+        public void Insert(T node)
+        {
+            int index = ++HeapSize;
+            U key = node.Key;
+
+            node.Key = LeastSignificant;
+            Array[index] = node;
+            Location[node.Id] = index;
+            ChangeKey(index, key);
+        }
+
+        public T Peek() =>
+            Array[0];
+
+        public bool IsEmpty() =>
+            HeapSize < 0;
+
+        // remove and return top node
+        public T Extract()
+        {
+            if (HeapSize < 0)
+                throw new System.OverflowException("Heap Underflow");
+
+            T sig = Peek();
+
+            Swap(0, HeapSize--);
+            Heapify(0);
+
+            return sig;
+        }
+
+        protected bool IsMoreSignificant(U that, U other) =>
+            that.CompareTo(other) * (IsMin ? -1 : 1) > 0;
+
+        public void ChangeKey(int id, U key)
+        {
+            int index = Location[id];
+
+            // key <= Array[index].Key
+            if (!IsMoreSignificant(key, Array[index].Key))
+                throw new System.ArgumentException($"New key ({key}) is less significant than node {id}'s current key ({Array[index].Key}).");
+
+            Array[index].Key = key;
+
+            while (index > 0 && IsMoreSignificant(Array[index], Array[Parent(index)]))
+            {
+                Swap(index, Parent(index));
+                index = Parent(index);
+            }
+        }
+    }
+}
\ No newline at end of file
-- 
cgit v1.2.3-70-g09d2