Commit: 7a41749a49ff6a165011c5d3a73203b3a07be29c - NMeCabRepo2 (git)

Commit MetaInfo

• Revision: 7a41749a49ff6a165011c5d3a73203b3a07be29c (tree)
• Time: 2015-07-07 22:14:58
• Author: komutan <t_komuta@nift...>
• Commiter: komutan

Log Message

PriorityQueueをPairringHeapで実装。キューとしての順序を確保。

Change Summary

• modified: src/LibNMeCab/Core/PriorityQueue.cs
• modified: src/LibNMeCabTest/LibNMeCabTest.csproj
• modified: src/LibNMeCabTest/PriorityQueueTest.cs

Incremental Difference

--- a/src/LibNMeCab/Core/PriorityQueue.cs
+++ b/src/LibNMeCab/Core/PriorityQueue.cs
@@ -7,77 +7,78 @@ namespace NMeCab.Core
     public class PriorityQueue<T>
         where T : IComparable<T>
     {
-        private readonly List<T> heapList = new List<T>();
-
-        public int Count
+        private class Node
         {
-            get { return this.heapList.Count; }
+            public T Value;
+
+            public LinkedList<Node> Childs = new LinkedList<Node>();
+
+            public Node(T value)
+            {
+                this.Value = value;
+            }
         }
 
+        private Node rootNode = null;
+
+        public int Count { get; private set; }
+
+        public T First { get { return this.rootNode.Value; } }
+
         public void Clear()
         {
-            this.heapList.Clear();
+            this.rootNode = null;
+            this.Count = 0;
+        }
+
+        public void RemoveFirst()
+        {
+            this.rootNode = this.Unify(this.rootNode.Childs);
+            this.Count--;
         }
 
         public void Push(T item)
         {
-            if (item == null) throw new ArgumentNullException("item");
+            this.rootNode = this.Merge(this.rootNode, new Node(item));
+            this.Count++;
+        }
 
-            //up heap
-            int currentPos = this.heapList.Count; //tail
-            this.heapList.Add(default(T));
-            while (currentPos != 0)
-            {
-                int parentPos = (currentPos - 1) / 2;
-                T parent = this.heapList[parentPos];
+        public T Pop()
+        {
+            T ret = this.First;
+            this.RemoveFirst();
+            return ret;
+        }
 
-                if (parent.CompareTo(item) <= 0) break;
+        private Node Merge(Node l, Node r)
+        {
+            if (l == null) return r;
+            if (r == null) return l;
 
-                this.heapList[currentPos] = parent; //down
-                currentPos = parentPos;
+            if (l.Value.CompareTo(r.Value) > 0)
+            {
+                r.Childs.AddFirst(l);
+                return r;
+            }
+            else
+            {
+                l.Childs.AddLast(r);
+                return l;
             }
-            this.heapList[currentPos] = item; //commit
         }
 
-        public T Pop()
+        private Node Unify(LinkedList<Node> nodes)
         {
-            if (this.heapList.Count == 0) throw new InvalidOperationException("Empty");
+            if (nodes == null || nodes.Count == 0) return null;
 
-            T root = this.heapList[0];
+            Node x = nodes.First.Value;
+            nodes.RemoveFirst();
+            if (nodes.Count == 0) return x;
 
-            int tailPos = this.heapList.Count - 1;
-            if (tailPos != 0)
-            {
-                //down heap
-                T tail = this.heapList[tailPos];
-                int currentPos = 0;
-                while (true) 
-                {
-                    int childPos = currentPos * 2 + 1; //left child
-                    if (childPos >= tailPos) break;
-                    T child = this.heapList[childPos];
-
-                    int rChiledPos = childPos + 1; //right child
-                    if (rChiledPos < tailPos)
-                    {
-                        T rChiled = this.heapList[rChiledPos];
-                        if (child.CompareTo(rChiled) > 0)
-                        {
-                            child = rChiled;
-                            childPos = rChiledPos;
-                        }
-                    }
-
-                    if (tail.CompareTo(child) < 0) break;
-
-                    this.heapList[currentPos] = child; //up
-                    currentPos = childPos;
-                }
-                this.heapList[currentPos] = tail; //commit
-            }
-            this.heapList.RemoveAt(tailPos);
+            Node y = nodes.First.Value;
+            nodes.RemoveFirst();
 
-            return root;
+            return this.Merge(this.Merge(x, y), this.Unify(nodes));
         }
     }
 }

--- a/src/LibNMeCabTest/LibNMeCabTest.csproj
+++ b/src/LibNMeCabTest/LibNMeCabTest.csproj
@@ -57,9 +57,9 @@
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
   <ItemGroup>
-    <ProjectReference Include="..\LibNMeCab35\LibNMeCab35.csproj">
-      <Project>{4ffe4221-2f41-446e-be59-d9cfcdf91ac6}</Project>
-      <Name>LibNMeCab35</Name>
+    <ProjectReference Include="..\LibNMeCab40MMF\LibNMeCab40MMF.csproj">
+      <Project>{86711194-4c2b-4853-830f-07c57f035283}</Project>
+      <Name>LibNMeCab40MMF</Name>
     </ProjectReference>
   </ItemGroup>
   <Choose>

--- a/src/LibNMeCabTest/PriorityQueueTest.cs
+++ b/src/LibNMeCabTest/PriorityQueueTest.cs
@@ -1,92 +1,159 @@
 using System;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
+using System.Collections.Generic;
+using System.Linq;
+using System.Diagnostics;
 
 namespace LibNMeCabTest
 {
+    public class Element : IComparable<Element>
+    {
+        public int Priority { get; set; }
+
+        public int Order { get; set; }
+
+        public int CompareTo(Element other)
+        {
+            return this.Priority.CompareTo(other.Priority);
+        }
+
+        public override int GetHashCode()
+        {
+            return this.Priority;
+        }
+
+        public override bool Equals(object obj)
+        {
+            var other = obj as Element;
+            return other != null
+                && this.Priority == other.Priority
+                && this.Order == other.Order;
+        }
+
+        public override string ToString()
+        {
+            return "priority:" + this.Priority + " order:" + this.Order;
+        }
+    }
+
     [TestClass]
     public class PriorityQueueTest
     {
         [TestMethod]
         public void TestMethod1()
         {
-            var target = new NMeCab.Core.PriorityQueue<int>();
+            var queue = new NMeCab.Core.PriorityQueue<Element>();
+            var collection = new List<Element>();
             var count = 0;
 
-            for (int i = 0; i < 10; i++)
+            for (int i = 0; i < 2; i++)
             {
-                for (int j = 0; j < 10; j++)
+                //追加 優先度昇順
+                for (int j = 0; j < 3; j++)
                 {
-                    target.Push(j);
+                    var item = new Element { Priority = j, Order = count };
+                    queue.Push(item);
+                    collection.Add(item);
                     count++;
-                    Assert.AreEqual(target.Count, count);
+                    Assert.AreEqual(queue.Count, count);
                 }
             }
 
-            int wrk1 = 0;
-            for (int k = 0; k < count; k++)
+            //並べ直し
+            collection = (from e in collection
+                          orderby e.Priority, e.Order
+                          select e).ToList();
+
+            //取り出し
+            foreach (var expected in collection)
             {
-                int wrk2 = target.Pop();
+                var actual = queue.Pop();
                 count--;
-                Assert.AreEqual(target.Count, count);
-                Assert.IsTrue(wrk1 <= wrk2);
-                wrk1 = wrk2;
+
+                Assert.AreEqual(expected, actual);
+                Assert.AreEqual(count, queue.Count);
             }
         }
 
         [TestMethod]
         public void TestMethod2()
         {
-            var target = new NMeCab.Core.PriorityQueue<int>();
+            var queue = new NMeCab.Core.PriorityQueue<Element>();
+            var collection = new List<Element>();
             var count = 0;
 
-            for (int i = 0; i < 10; i++)
+            for (int i = 0; i < 2; i++)
             {
-                for (int j = 10; j >= 0; j--)
+                //追加 優先度降順
+                for (int j = 3; j >= 0; j--)
                 {
-                    target.Push(j);
+                    var item = new Element { Priority = j, Order = count };
+                    queue.Push(item);
+                    collection.Add(item);
                     count++;
-                    Assert.AreEqual(target.Count, count);
+
+                    Assert.AreEqual(count, queue.Count);
                 }
             }
 
-            int wrk1 = 0;
-            for (int k = 0; k < count; k++)
+            //並べ直し
+            collection = (from e in collection
+                          orderby e.Priority, e.Order
+                          select e).ToList();
+
+            //取り出し
+            foreach (var expected in collection)
             {
-                int wrk2 = target.Pop();
+                var actual = queue.Pop();
                 count--;
-                Assert.AreEqual(target.Count, count);
-                Assert.IsTrue(wrk1 <= wrk2);
-                wrk1 = wrk2;
+
+                Assert.AreEqual(expected, actual);
+                Assert.AreEqual(count, queue.Count);
             }
         }
 
         [TestMethod]
         public void TestMethod3()
         {
-            var target = new NMeCab.Core.PriorityQueue<int>();
+            var queue = new NMeCab.Core.PriorityQueue<Element>();
+            var collection = new List<Element>();
+            var order = 0;
             var count = 0;
             var rnd = new Random();
 
+            //追加と取り出しを一定数繰り返す
             for (int i = 0; i < 1000; i++)
             {
+                //ランダム優先度でランダム個追加
                 int repeat = rnd.Next(10);
                 for (int j = 0; j < repeat; j++)
                 {
-                    target.Push(rnd.Next(10));
+                    var item = new Element { Priority = rnd.Next(10), Order = order };
+                    collection.Add(item);
+                    queue.Push(item);
+                    order++;
                     count++;
-                    Assert.AreEqual(target.Count, count);
+
+                    Assert.AreEqual(count, queue.Count);
                 }
 
-                repeat = rnd.Next(target.Count);
-                int wrk1 = 0;
-                for (int k = 0; k < repeat; k++)
+                //並べ直し
+                collection = (from e in collection
+                              orderby e.Priority, e.Order
+                              select e).ToList();
+
+                //ランダム個取り出し
+                repeat = rnd.Next(collection.Count);
+                for (int j = 0; j < repeat; j++)
                 {
-                    int wrk2 = target.Pop();
+                    var actual = queue.Pop();
+                    var expected = collection[j];
                     count--;
-                    Assert.AreEqual(target.Count, count);
-                    Assert.IsTrue(wrk1 <= wrk2);
-                    wrk1 = wrk2;
+
+                    Assert.AreEqual(expected, actual);
+                    Assert.AreEqual(count, queue.Count);
                 }
+                collection.RemoveRange(0, repeat);
             }
         }
     }