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));
}
}
}
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);
}
}
}
OSDN Git Service
