PrioarityQueueでのBinalyHeepアルゴリズムを試行

diff --git a/src/LibNMeCab/Core/PriorityQueue.cs b/src/LibNMeCab/Core/PriorityQueue.cs
index 5851c37..9c26bf3 100644 (file)
--- a/src/LibNMeCab/Core/PriorityQueue.cs
+++ b/src/LibNMeCab/Core/PriorityQueue.cs
@@ -1,60 +1,141 @@
-using System;
-using System.Collections.Generic;
-using System.Text;
-
-namespace NMeCab.Core
-{
-    public class PriorityQueue<T>
-        where T : IComparable<T>
-    {
-        private readonly List<T> list = new List<T>();
-
-        public int Count
-        {
-            get { return this.list.Count; }
-        }
-
-        public void Clear()
-        {
-            this.list.Clear();
-        }
-
-        public int Push(T item)
-        {
-            int index = this.SearchIndex(this.list, item);
-            this.list.Insert(index, item);
-            return index;
-        }
-
-        public T Pop()
-        {
-            if (this.Count == 0) throw new InvalidOperationException("Empty");
-
-            T item = this.list[0];
-            this.list.RemoveAt(0);
-            return item;
-        }
-
-        private int SearchIndex(List<T> list, T item)
-        {
-            int head = 0;
-            int tail = list.Count;
-
-            while (head < tail)
-            {
-                int where = (head + tail) / 2;
-
-                if (list[where].CompareTo(item) <= 0)
-                {
-                    head = where + 1;
-                }
-                else
-                {
-                    tail = where;
-                }
-            }
-
-            return head;
-        }
-    }
-}
+using System;\r
+using System.Collections.Generic;\r
+using System.Text;\r
+\r
+namespace NMeCab.Core\r
+{\r
+    public class PriorityQueue<T>\r
+        where T : IComparable<T>\r
+    {\r
+        private readonly List<T> list = new List<T>();\r
+\r
+        public int Count\r
+        {\r
+            get { return this.list.Count; }\r
+        }\r
+\r
+        public void Clear()\r
+        {\r
+            this.list.Clear();\r
+        }\r
+\r
+#if BinaryHeapPriorityQueue\r
+        \r
+        public void Push(T item)\r
+        {\r
+            int currentPos = this.list.Count;\r
+            this.list.Add(item);\r
+\r
+            while (currentPos != 0) // has more parrent\r
+            {\r
+                int parentPos = (currentPos - 1) / 2;\r
+                T parent = this.list[parentPos];\r
+\r
+                if (parent.CompareTo(item) <= 0) break; // parent is higher or equal\r
+\r
+                this.list[parentPos] = item;\r
+                this.list[currentPos] = parent;\r
+\r
+                currentPos = parentPos;\r
+            }\r
+        }\r
+\r
+        public T Pop()\r
+        {\r
+            if (this.Count == 0) throw new InvalidOperationException("Empty");\r
+\r
+            T ret = this.list[0];\r
+            this.DeleteTop();\r
+            return ret;\r
+        }\r
+\r
+        private void DeleteTop()\r
+        {\r
+            int tailPos = this.list.Count - 1;\r
+            this.list[0] = this.list[tailPos];\r
+            this.list.RemoveAt(tailPos);\r
+            if (tailPos == 0) return;\r
+            tailPos--;\r
+            \r
+            int currentPos = 0;\r
+            T current = this.list[0];\r
+            while (true)\r
+            {\r
+                int leftPos = currentPos * 2 + 1;\r
+                if (leftPos > tailPos) break;\r
+                int rightPos = leftPos + 1;\r
+\r
+                int chiledPos;\r
+                T chiled;\r
+                if (rightPos > tailPos)\r
+                {\r
+                    chiledPos = leftPos;\r
+                    chiled = this.list[chiledPos];\r
+                }\r
+                else\r
+                {\r
+                    T left = this.list[leftPos];\r
+                    T right = this.list[rightPos];\r
+                    if (left.CompareTo(right) < 0)\r
+                    {\r
+                        chiledPos = leftPos;\r
+                        chiled = left;\r
+                    }\r
+                    else\r
+                    {\r
+                        chiledPos = rightPos;\r
+                        chiled = right;\r
+                    }\r
+                }\r
+\r
+                if (current.CompareTo(chiled) < 0) break;\r
+                this.list[currentPos] = chiled;\r
+                this.list[chiledPos] = current;\r
+                current = chiled;\r
+                currentPos = chiledPos;\r
+            }\r
+        }\r
+\r
+#else\r
+\r
+        public int Push(T item)\r
+        {\r
+            int index = this.SearchIndex(this.list, item);\r
+            this.list.Insert(index, item);\r
+            return index;\r
+        }\r
+\r
+        public T Pop()\r
+        {\r
+            if (this.Count == 0) throw new InvalidOperationException("Empty");\r
+\r
+            T item = this.list[0];\r
+            this.list.RemoveAt(0);\r
+            return item;\r
+        }\r
+\r
+        private int SearchIndex(List<T> list, T item)\r
+        {\r
+            int head = 0;\r
+            int tail = list.Count;\r
+\r
+            while (head < tail)\r
+            {\r
+                int where = (head + tail) / 2;\r
+\r
+                if (list[where].CompareTo(item) <= 0)\r
+                {\r
+                    head = where + 1;\r
+                }\r
+                else\r
+                {\r
+                    tail = where;\r
+                }\r
+            }\r
+\r
+            return head;\r
+        }\r
+\r
+#endif\r
+    }\r
+}\r