From 30bae02cffc1069c6382a367b6f73f4465ac53d7 Mon Sep 17 00:00:00 2001
From: komutan <t_komuta@nifty.com>
Date: Tue, 22 Jul 2014 23:06:26 +0900
Subject: [PATCH] =?utf8?q?=E3=83=87=E3=83=90=E3=83=83=E3=82=B0=E3=81=A8?=
 =?utf8?q?=E9=AB=98=E9=80=9F=E5=8C=96?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 src/LibNMeCab/Core/PriorityQueue.cs | 81 ++++++++-----------------------------
 1 file changed, 17 insertions(+), 64 deletions(-)

diff --git a/src/LibNMeCab/Core/PriorityQueue.cs b/src/LibNMeCab/Core/PriorityQueue.cs
index 865b73b..004cbd9 100644
--- a/src/LibNMeCab/Core/PriorityQueue.cs
+++ b/src/LibNMeCab/Core/PriorityQueue.cs
@@ -19,25 +19,21 @@ namespace NMeCab.Core
             this.list.Clear();
         }
 
-#if BinaryHeapPriorityQueue
-
         public void Push(T item)
         {
             int currentPos = this.list.Count;
-            this.list.Add(item);
+            this.list.Add(item); // dummy
 
-            while (currentPos != 0) // has more parrent
+            while (currentPos != 0)
             {
                 int parentPos = (currentPos - 1) / 2;
                 T parent = this.list[parentPos];
 
-                if (parent.CompareTo(item) <= 0) break; // parent is higher or equal
-
-                this.list[parentPos] = item;
+                if (parent.CompareTo(item) <= 0) break;
                 this.list[currentPos] = parent;
-
                 currentPos = parentPos;
             }
+            this.list[currentPos] = item;
         }
 
         public T Pop()
@@ -45,84 +41,41 @@ namespace NMeCab.Core
             if (this.Count == 0) throw new InvalidOperationException("Empty");
 
             T ret = this.list[0];
-            this.DeleteTop();
+            this.DeleteRoot();
             return ret;
         }
 
-        private void DeleteTop()
+        private void DeleteRoot()
         {
             int tailPos = this.list.Count - 1;
-            if (tailPos == -1) return;
             T current = this.list[tailPos];
             this.list.RemoveAt(tailPos);
-            if (tailPos == 0) return;
+            if (tailPos == 0) return; // empty
             tailPos--;
 
             int currentPos = 0;
             while (true)
             {
-                int chiledPos = currentPos * 2 + 1;
-                if (chiledPos > tailPos) break;
-                T chiled = this.list[chiledPos];
+                int childPos = currentPos * 2 + 1; // left child
+                if (childPos > tailPos) break;
+                T child = this.list[childPos];
 
-                int wrkPos = chiledPos + 1;
+                int wrkPos = childPos + 1; // right child
                 if (wrkPos <= tailPos)
                 {
                     T wrk = this.list[wrkPos];
-                    if (chiled.CompareTo(wrk) > 0)
+                    if (child.CompareTo(wrk) > 0)
                     {
-                        chiledPos = wrkPos;
-                        chiled = wrk;
+                        childPos = wrkPos;
+                        child = wrk;
                     }
                 }
 
-                if (current.CompareTo(chiled) < 0) break;
-                this.list[currentPos] = chiled;
-                currentPos = chiledPos;
+                if (current.CompareTo(child) < 0) break;
+                this.list[currentPos] = child;
+                currentPos = childPos;
             }
             this.list[currentPos] = current;
         }
-
-#else
-
-        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;
-        }
-
-#endif
     }
 }
-- 
2.11.0