-using System;
-using System.Collections.Generic;
-using System.Text;
-
-namespace NMeCab.Core
-{
- public class PriorityQueue<T>
- where T : IComparable<T>
- {
- private class HeapNode
- {
- public T Value { get; private set; }
- public int ChildsCount { get; private set; }
- public HeapNode FirstChild { get; private set; }
- public HeapNode LastChild { get; private set; }
- public HeapNode Prev { get; private set; }
- public HeapNode Next { get; private set; }
-
- public void AddFirstChild(HeapNode first)
- {
- this.ChildsCount++;
- if (this.ChildsCount == 1)
- {
- this.LastChild = first;
- }
- else
- {
- HeapNode old = this.FirstChild;
- first.Next = old;
- old.Prev = first;
- }
- this.FirstChild = first;
- }
-
- public void AddLastChild(HeapNode last)
- {
- this.ChildsCount++;
- if (this.ChildsCount == 1)
- {
- this.FirstChild = last;
- }
- else
- {
- HeapNode old = this.LastChild;
- last.Prev = old;
- old.Next = last;
- }
- this.LastChild = last;
- }
-
- public HeapNode PollFirstChild()
- {
- this.ChildsCount--;
- if (this.ChildsCount == 0)
- {
- this.LastChild.Prev = null;
- this.LastChild = null;
- }
- HeapNode first = this.FirstChild;
- this.FirstChild = first.Next;
- first.Next = null;
- return first;
- }
-
- public HeapNode(T value)
- {
- this.Value = value;
- }
- }
-
- private HeapNode rootNode;
-
- public int Count { get; private set; }
-
- public void Clear()
- {
- this.Count = 0;
- this.rootNode = null;
- }
-
- public void Push(T item)
- {
- this.Count++;
- this.rootNode = this.Merge(this.rootNode, new HeapNode(item));
- }
-
- public T Peek()
- {
- return this.rootNode.Value;
- }
-
- public T Pop()
- {
- T ret = this.Peek();
- this.RemoveFirst();
- return ret;
- }
-
- public void RemoveFirst()
- {
- this.Count--;
- this.rootNode = this.UnifyChilds(this.rootNode);
- }
-
- private HeapNode Merge(HeapNode l, HeapNode r)
- {
- if (l == null) return r;
- if (r == null) return l;
-
- if (l.Value.CompareTo(r.Value) > 0)
- {
- r.AddFirstChild(l);
- return r;
- }
- else
- {
- l.AddLastChild(r);
- return l;
- }
- }
-
- private HeapNode UnifyChilds(HeapNode node)
- {
- HeapNode[] tmp = new HeapNode[node.ChildsCount / 2]; //必要な要素数が明らかなのでStackではなく配列
-
- for (int i = 0; i < tmp.Length; i++)
- {
- HeapNode x = node.PollFirstChild();
- HeapNode y = node.PollFirstChild();
- tmp[i] = this.Merge(x, y);
- }
-
- HeapNode z;
- if (node.ChildsCount == 1) //子要素数が奇数の場合、まだ１つ残っている子要素をここで処理
- z = node.PollFirstChild();
- else
- z = null;
-
- for (int i = tmp.Length - 1; i >= 0; i--) //逆順ループで配列をStackのように振る舞わせる
- {
- z = this.Merge(tmp[i], z);
- }
-
- return z;
- }
- }
-}
+using System;\r
+using System.Collections.Generic;\r
+using System.Text;\r
+\r
+namespace NMeCab.Core\r
+{\r
+ /// <summary>\r
+ /// 優先度付き先入れ先出しコレクション（実装アルゴリズムはPairing Heap）\r
+ /// </summary>\r
+ /// <typeparam name="T"></typeparam>\r
+ public class PriorityQueue<T>\r
+ where T : IComparable<T>\r
+ {\r
+ private class HeapNode\r
+ {\r
+ public T Value { get; private set; }\r
+ public int ChildsCount { get; private set; }\r
+ private HeapNode firstChild;\r
+ private HeapNode lastChild;\r
+ private HeapNode next;\r
+\r
+ public void AddFirstChild(HeapNode newNode)\r
+ {\r
+ this.ChildsCount++;\r
+ if (this.ChildsCount == 1)\r
+ this.lastChild = newNode;\r
+ else\r
+ newNode.next = this.firstChild;\r
+ this.firstChild = newNode;\r
+ }\r
+\r
+ public void AddLastChild(HeapNode newNode)\r
+ {\r
+ this.ChildsCount++;\r
+ if (this.ChildsCount == 1)\r
+ this.firstChild = newNode;\r
+ else\r
+ this.lastChild.next = newNode;\r
+ this.lastChild = newNode;\r
+ }\r
+\r
+ public HeapNode PollFirstChild()\r
+ {\r
+ HeapNode ret = this.firstChild;\r
+ this.ChildsCount--;\r
+ if (this.ChildsCount == 0)\r
+ {\r
+ this.firstChild = null;\r
+ this.lastChild = null;\r
+ }\r
+ else\r
+ {\r
+ this.firstChild = ret.next;\r
+ ret.next = null;\r
+ }\r
+ return ret;\r
+ }\r
+\r
+ public HeapNode(T value)\r
+ {\r
+ this.Value = value;\r
+ }\r
+ }\r
+\r
+ private HeapNode rootNode;\r
+\r
+ public int Count { get; private set; }\r
+\r
+ public void Clear()\r
+ {\r
+ this.Count = 0;\r
+ this.rootNode = null;\r
+ }\r
+\r
+ public void Push(T item)\r
+ {\r
+ this.Count++;\r
+ this.rootNode = this.MergeNodes(this.rootNode, new HeapNode(item));\r
+ }\r
+\r
+ public T Pop()\r
+ {\r
+ if (this.Count == 0) throw new InvalidOperationException("Empty");\r
+\r
+ this.Count--;\r
+ T ret = this.rootNode.Value;\r
+ this.rootNode = this.UnifyChildNodes(this.rootNode);\r
+ return ret;\r
+ }\r
+\r
+ private HeapNode MergeNodes(HeapNode l, HeapNode r)\r
+ {\r
+ if (l == null) return r;\r
+ if (r == null) return l;\r
+\r
+ if (l.Value.CompareTo(r.Value) > 0)\r
+ {\r
+ r.AddFirstChild(l);\r
+ return r;\r
+ }\r
+ else\r
+ {\r
+ l.AddLastChild(r);\r
+ return l;\r
+ }\r
+ }\r
+\r
+ private HeapNode UnifyChildNodes(HeapNode node)\r
+ {\r
+ HeapNode[] tmp = new HeapNode[node.ChildsCount / 2]; //必要な要素数が明らかなのでStackではなく配列\r
+\r
+ for (int i = 0; i < tmp.Length; i++)\r
+ {\r
+ HeapNode x = node.PollFirstChild();\r
+ HeapNode y = node.PollFirstChild();\r
+ tmp[i] = this.MergeNodes(x, y);\r
+ }\r
+\r
+ HeapNode z;\r
+ if (node.ChildsCount == 1) //子要素数が奇数の場合、まだ１つ残っている子要素をここで処理\r
+ z = node.PollFirstChild();\r
+ else\r
+ z = null;\r
+\r
+ for (int i = tmp.Length - 1; i >= 0; i--) //逆順ループで配列をStackのように振る舞わせる\r
+ {\r
+ z = this.MergeNodes(tmp[i], z);\r
+ }\r
+\r
+ return z;\r
+ }\r
+ }\r
+}\r
-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 queue = new NMeCab.Core.PriorityQueue<Element>();
- var collection = new List<Element>();
- var count = 0;
-
- for (int i = 0; i < 5; i++)
- {
- //追加 優先度昇順
- for (int j = 0; j < 5; j++)
- {
- var item = new Element { Priority = j, Order = count };
- queue.Push(item);
- collection.Add(item);
- count++;
- Assert.AreEqual(queue.Count, count);
- }
- }
-
- //並べ直し
- collection = (from e in collection
- orderby e.Priority, e.Order
- select e).ToList();
-
- //取り出し
- foreach (var expected in collection)
- {
- var actual = queue.Pop();
- count--;
-
- Assert.AreEqual(expected, actual);
- Assert.AreEqual(count, queue.Count);
- }
- }
-
- [TestMethod]
- public void TestMethod2()
- {
- var queue = new NMeCab.Core.PriorityQueue<Element>();
- var collection = new List<Element>();
- var count = 0;
-
- for (int i = 0; i < 5; i++)
- {
- //追加 優先度降順
- for (int j = 5; j >= 0; j--)
- {
- var item = new Element { Priority = j, Order = count };
- queue.Push(item);
- collection.Add(item);
- count++;
-
- Assert.AreEqual(count, queue.Count);
- }
- }
-
- //並べ直し
- collection = (from e in collection
- orderby e.Priority, e.Order
- select e).ToList();
-
- //取り出し
- foreach (var expected in collection)
- {
- var actual = queue.Pop();
- count--;
-
- Assert.AreEqual(expected, actual);
- Assert.AreEqual(count, queue.Count);
- }
- }
-
- [TestMethod]
- public void TestMethod3()
- {
- 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++)
- {
- var item = new Element { Priority = rnd.Next(10), Order = order };
- collection.Add(item);
- queue.Push(item);
- order++;
- count++;
-
- Assert.AreEqual(count, queue.Count);
- }
-
- //並べ直し
- 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++)
- {
- var actual = queue.Pop();
- var expected = collection[j];
- count--;
-
- Assert.AreEqual(expected, actual);
- Assert.AreEqual(count, queue.Count);
- }
- collection.RemoveRange(0, repeat);
- }
- }
- }
-}
+using System;\r
+using Microsoft.VisualStudio.TestTools.UnitTesting;\r
+using System.Collections.Generic;\r
+using System.Linq;\r
+using System.Diagnostics;\r
+\r
+namespace LibNMeCabTest\r
+{\r
+ public class Element : IComparable<Element>\r
+ {\r
+ public int Priority { get; set; }\r
+\r
+ public int Order { get; set; }\r
+\r
+ public int CompareTo(Element other)\r
+ {\r
+ return this.Priority.CompareTo(other.Priority);\r
+ }\r
+\r
+ public override int GetHashCode()\r
+ {\r
+ return this.Priority;\r
+ }\r
+\r
+ public override bool Equals(object obj)\r
+ {\r
+ var other = obj as Element;\r
+ return other != null\r
+ && this.Priority == other.Priority\r
+ && this.Order == other.Order;\r
+ }\r
+\r
+ public override string ToString()\r
+ {\r
+ return "priority:" + this.Priority + " order:" + this.Order;\r
+ }\r
+ }\r
+\r
+ [TestClass]\r
+ public class PriorityQueueTest\r
+ {\r
+ [TestMethod]\r
+ public void TestMethod1()\r
+ {\r
+ var queue = new NMeCab.Core.PriorityQueue<Element>();\r
+ var collection = new List<Element>();\r
+ var count = 0;\r
+\r
+ for (int i = 0; i < 5; i++)\r
+ {\r
+ //追加 優先度昇順\r
+ for (int j = 0; j < 5; j++)\r
+ {\r
+ var item = new Element { Priority = j, Order = count };\r
+ queue.Push(item);\r
+ collection.Add(item);\r
+ count++;\r
+ Assert.AreEqual(queue.Count, count);\r
+ }\r
+ }\r
+\r
+ //並べ直し\r
+ collection = (from e in collection\r
+ orderby e.Priority, e.Order\r
+ select e).ToList();\r
+\r
+ //取り出し\r
+ foreach (var expected in collection)\r
+ {\r
+ var actual = queue.Pop();\r
+ count--;\r
+\r
+ Assert.AreEqual(expected, actual);\r
+ Assert.AreEqual(count, queue.Count);\r
+ }\r
+\r
+ this.EmptyExceptionTest(queue);\r
+ }\r
+\r
+ [TestMethod]\r
+ public void TestMethod2()\r
+ {\r
+ var queue = new NMeCab.Core.PriorityQueue<Element>();\r
+ var collection = new List<Element>();\r
+ var count = 0;\r
+\r
+ for (int i = 0; i < 5; i++)\r
+ {\r
+ //追加 優先度降順\r
+ for (int j = 5; j >= 0; j--)\r
+ {\r
+ var item = new Element { Priority = j, Order = count };\r
+ queue.Push(item);\r
+ collection.Add(item);\r
+ count++;\r
+\r
+ Assert.AreEqual(count, queue.Count);\r
+ }\r
+ }\r
+\r
+ //並べ直し\r
+ collection = (from e in collection\r
+ orderby e.Priority, e.Order\r
+ select e).ToList();\r
+\r
+ //取り出し\r
+ foreach (var expected in collection)\r
+ {\r
+ var actual = queue.Pop();\r
+ count--;\r
+\r
+ Assert.AreEqual(expected, actual);\r
+ Assert.AreEqual(count, queue.Count);\r
+ }\r
+\r
+ this.EmptyExceptionTest(queue);\r
+ }\r
+\r
+ [TestMethod]\r
+ public void TestMethod3()\r
+ {\r
+ var queue = new NMeCab.Core.PriorityQueue<Element>();\r
+ var collection = new List<Element>();\r
+ var order = 0;\r
+ var count = 0;\r
+ var rnd = new Random();\r
+\r
+ //追加と取り出しを一定数繰り返す\r
+ for (int i = 0; i < 1000; i++)\r
+ {\r
+ //ランダム優先度でランダム個追加\r
+ int repeat = rnd.Next(1, 10);\r
+ for (int j = 0; j < repeat; j++)\r
+ {\r
+ var item = new Element { Priority = rnd.Next(10), Order = order };\r
+ collection.Add(item);\r
+ queue.Push(item);\r
+ order++;\r
+ count++;\r
+\r
+ Assert.AreEqual(count, queue.Count);\r
+ }\r
+\r
+ //並べ直し\r
+ collection = (from e in collection\r
+ orderby e.Priority, e.Order\r
+ select e).ToList();\r
+\r
+ //ランダム個取り出し\r
+ repeat = rnd.Next(1, collection.Count);\r
+ for (int j = 0; j < repeat; j++)\r
+ {\r
+ var actual = queue.Pop();\r
+ var expected = collection[j];\r
+ count--;\r
+\r
+ Assert.AreEqual(expected, actual);\r
+ Assert.AreEqual(count, queue.Count);\r
+ }\r
+ collection.RemoveRange(0, repeat);\r
+ }\r
+\r
+ while (queue.Count > 0) queue.Pop(); //空にする\r
+ this.EmptyExceptionTest(queue);\r
+ }\r
+\r
+ [TestMethod]\r
+ public void TestMethod4()\r
+ {\r
+ var queue = new NMeCab.Core.PriorityQueue<string>();\r
+\r
+ for (int i = 0; i < 10; i++) queue.Push("abc");\r
+\r
+ queue.Clear(); //テスト\r
+\r
+ Assert.AreEqual(0, queue.Count);\r
+ this.EmptyExceptionTest(queue);\r
+ }\r
+\r
+ [TestMethod]\r
+ public void TestMethod5()\r
+ {\r
+ var queue = new NMeCab.Core.PriorityQueue<int>();\r
+\r
+ //10万件挿入\r
+ for (int i = 0; i < 100000; i++) queue.Push(i % 5);\r
+\r
+ //取り出し\r
+ while (queue.Count > 0) queue.Pop();\r
+ }\r
+\r
+ private void EmptyExceptionTest<T>(NMeCab.Core.PriorityQueue<T> queue)\r
+ where T : IComparable<T>\r
+ {\r
+ try\r
+ {\r
+ queue.Pop();//空なら例外発生\r
+ }\r
+ catch (InvalidOperationException)\r
+ {\r
+ return;\r
+ }\r
+ Assert.Fail("Not Throwed Empty Exception");\r
+ }\r
+ }\r
+}\r
OSDN Git Service
