OSDN -- 開發和下載開源軟體
繁體中文翻譯狀態 translation status for zh-tw
  • R/O
  • HTTP
  • SSH
  • HTTPS
Fork

提交

標籤
無標籤

Frequently used words (click to add to your profile)

javac++androidlinuxc#windowsobjective-ccocoa誰得qtpythonphprubygameguibathyscaphec計画中(planning stage)翻訳omegatframeworktwitterdomtestvb.netdirectxゲームエンジンbtronarduinopreviewer

Commit MetaInfo

修訂7f9939c59704045451e4981d83bfc0b05f9b4487 (tree)
時間2015-07-12 18:16:03
作者komutan <t_komuta@nift...>
Commiterkomutan

Log Message

微修正

Change Summary

差異

--- a/src/LibNMeCab/Core/PriorityQueue.cs
+++ b/src/LibNMeCab/Core/PriorityQueue.cs
@@ -1,147 +1,133 @@
1-using System;
2-using System.Collections.Generic;
3-using System.Text;
4-
5-namespace NMeCab.Core
6-{
7- public class PriorityQueue<T>
8- where T : IComparable<T>
9- {
10- private class HeapNode
11- {
12- public T Value { get; private set; }
13- public int ChildsCount { get; private set; }
14- public HeapNode FirstChild { get; private set; }
15- public HeapNode LastChild { get; private set; }
16- public HeapNode Prev { get; private set; }
17- public HeapNode Next { get; private set; }
18-
19- public void AddFirstChild(HeapNode first)
20- {
21- this.ChildsCount++;
22- if (this.ChildsCount == 1)
23- {
24- this.LastChild = first;
25- }
26- else
27- {
28- HeapNode old = this.FirstChild;
29- first.Next = old;
30- old.Prev = first;
31- }
32- this.FirstChild = first;
33- }
34-
35- public void AddLastChild(HeapNode last)
36- {
37- this.ChildsCount++;
38- if (this.ChildsCount == 1)
39- {
40- this.FirstChild = last;
41- }
42- else
43- {
44- HeapNode old = this.LastChild;
45- last.Prev = old;
46- old.Next = last;
47- }
48- this.LastChild = last;
49- }
50-
51- public HeapNode PollFirstChild()
52- {
53- this.ChildsCount--;
54- if (this.ChildsCount == 0)
55- {
56- this.LastChild.Prev = null;
57- this.LastChild = null;
58- }
59- HeapNode first = this.FirstChild;
60- this.FirstChild = first.Next;
61- first.Next = null;
62- return first;
63- }
64-
65- public HeapNode(T value)
66- {
67- this.Value = value;
68- }
69- }
70-
71- private HeapNode rootNode;
72-
73- public int Count { get; private set; }
74-
75- public void Clear()
76- {
77- this.Count = 0;
78- this.rootNode = null;
79- }
80-
81- public void Push(T item)
82- {
83- this.Count++;
84- this.rootNode = this.Merge(this.rootNode, new HeapNode(item));
85- }
86-
87- public T Peek()
88- {
89- return this.rootNode.Value;
90- }
91-
92- public T Pop()
93- {
94- T ret = this.Peek();
95- this.RemoveFirst();
96- return ret;
97- }
98-
99- public void RemoveFirst()
100- {
101- this.Count--;
102- this.rootNode = this.UnifyChilds(this.rootNode);
103- }
104-
105- private HeapNode Merge(HeapNode l, HeapNode r)
106- {
107- if (l == null) return r;
108- if (r == null) return l;
109-
110- if (l.Value.CompareTo(r.Value) > 0)
111- {
112- r.AddFirstChild(l);
113- return r;
114- }
115- else
116- {
117- l.AddLastChild(r);
118- return l;
119- }
120- }
121-
122- private HeapNode UnifyChilds(HeapNode node)
123- {
124- HeapNode[] tmp = new HeapNode[node.ChildsCount / 2]; //必要な要素数が明らかなのでStackではなく配列
125-
126- for (int i = 0; i < tmp.Length; i++)
127- {
128- HeapNode x = node.PollFirstChild();
129- HeapNode y = node.PollFirstChild();
130- tmp[i] = this.Merge(x, y);
131- }
132-
133- HeapNode z;
134- if (node.ChildsCount == 1) //子要素数が奇数の場合、まだ１つ残っている子要素をここで処理
135- z = node.PollFirstChild();
136- else
137- z = null;
138-
139- for (int i = tmp.Length - 1; i >= 0; i--) //逆順ループで配列をStackのように振る舞わせる
140- {
141- z = this.Merge(tmp[i], z);
142- }
143-
144- return z;
145- }
146- }
147-}
1+using System;
2+using System.Collections.Generic;
3+using System.Text;
4+
5+namespace NMeCab.Core
6+{
7+ /// <summary>
8+ /// 優先度付き先入れ先出しコレクション（実装アルゴリズムはPairing Heap）
9+ /// </summary>
10+ /// <typeparam name="T"></typeparam>
11+ public class PriorityQueue<T>
12+ where T : IComparable<T>
13+ {
14+ private class HeapNode
15+ {
16+ public T Value { get; private set; }
17+ public int ChildsCount { get; private set; }
18+ private HeapNode firstChild;
19+ private HeapNode lastChild;
20+ private HeapNode next;
21+
22+ public void AddFirstChild(HeapNode newNode)
23+ {
24+ this.ChildsCount++;
25+ if (this.ChildsCount == 1)
26+ this.lastChild = newNode;
27+ else
28+ newNode.next = this.firstChild;
29+ this.firstChild = newNode;
30+ }
31+
32+ public void AddLastChild(HeapNode newNode)
33+ {
34+ this.ChildsCount++;
35+ if (this.ChildsCount == 1)
36+ this.firstChild = newNode;
37+ else
38+ this.lastChild.next = newNode;
39+ this.lastChild = newNode;
40+ }
41+
42+ public HeapNode PollFirstChild()
43+ {
44+ HeapNode ret = this.firstChild;
45+ this.ChildsCount--;
46+ if (this.ChildsCount == 0)
47+ {
48+ this.firstChild = null;
49+ this.lastChild = null;
50+ }
51+ else
52+ {
53+ this.firstChild = ret.next;
54+ ret.next = null;
55+ }
56+ return ret;
57+ }
58+
59+ public HeapNode(T value)
60+ {
61+ this.Value = value;
62+ }
63+ }
64+
65+ private HeapNode rootNode;
66+
67+ public int Count { get; private set; }
68+
69+ public void Clear()
70+ {
71+ this.Count = 0;
72+ this.rootNode = null;
73+ }
74+
75+ public void Push(T item)
76+ {
77+ this.Count++;
78+ this.rootNode = this.MergeNodes(this.rootNode, new HeapNode(item));
79+ }
80+
81+ public T Pop()
82+ {
83+ if (this.Count == 0) throw new InvalidOperationException("Empty");
84+
85+ this.Count--;
86+ T ret = this.rootNode.Value;
87+ this.rootNode = this.UnifyChildNodes(this.rootNode);
88+ return ret;
89+ }
90+
91+ private HeapNode MergeNodes(HeapNode l, HeapNode r)
92+ {
93+ if (l == null) return r;
94+ if (r == null) return l;
95+
96+ if (l.Value.CompareTo(r.Value) > 0)
97+ {
98+ r.AddFirstChild(l);
99+ return r;
100+ }
101+ else
102+ {
103+ l.AddLastChild(r);
104+ return l;
105+ }
106+ }
107+
108+ private HeapNode UnifyChildNodes(HeapNode node)
109+ {
110+ HeapNode[] tmp = new HeapNode[node.ChildsCount / 2]; //必要な要素数が明らかなのでStackではなく配列
111+
112+ for (int i = 0; i < tmp.Length; i++)
113+ {
114+ HeapNode x = node.PollFirstChild();
115+ HeapNode y = node.PollFirstChild();
116+ tmp[i] = this.MergeNodes(x, y);
117+ }
118+
119+ HeapNode z;
120+ if (node.ChildsCount == 1) //子要素数が奇数の場合、まだ１つ残っている子要素をここで処理
121+ z = node.PollFirstChild();
122+ else
123+ z = null;
124+
125+ for (int i = tmp.Length - 1; i >= 0; i--) //逆順ループで配列をStackのように振る舞わせる
126+ {
127+ z = this.MergeNodes(tmp[i], z);
128+ }
129+
130+ return z;
131+ }
132+ }
133+}
--- a/src/LibNMeCabTest/PriorityQueueTest.cs
+++ b/src/LibNMeCabTest/PriorityQueueTest.cs
@@ -1,160 +1,206 @@
1-using System;
2-using Microsoft.VisualStudio.TestTools.UnitTesting;
3-using System.Collections.Generic;
4-using System.Linq;
5-using System.Diagnostics;
6-
7-namespace LibNMeCabTest
8-{
9- public class Element : IComparable<Element>
10- {
11- public int Priority { get; set; }
12-
13- public int Order { get; set; }
14-
15- public int CompareTo(Element other)
16- {
17- return this.Priority.CompareTo(other.Priority);
18- }
19-
20- public override int GetHashCode()
21- {
22- return this.Priority;
23- }
24-
25- public override bool Equals(object obj)
26- {
27- var other = obj as Element;
28- return other != null
29- && this.Priority == other.Priority
30- && this.Order == other.Order;
31- }
32-
33- public override string ToString()
34- {
35- return "priority:" + this.Priority + " order:" + this.Order;
36- }
37- }
38-
39- [TestClass]
40- public class PriorityQueueTest
41- {
42- [TestMethod]
43- public void TestMethod1()
44- {
45- var queue = new NMeCab.Core.PriorityQueue<Element>();
46- var collection = new List<Element>();
47- var count = 0;
48-
49- for (int i = 0; i < 5; i++)
50- {
51- //追加 優先度昇順
52- for (int j = 0; j < 5; j++)
53- {
54- var item = new Element { Priority = j, Order = count };
55- queue.Push(item);
56- collection.Add(item);
57- count++;
58- Assert.AreEqual(queue.Count, count);
59- }
60- }
61-
62- //並べ直し
63- collection = (from e in collection
64- orderby e.Priority, e.Order
65- select e).ToList();
66-
67- //取り出し
68- foreach (var expected in collection)
69- {
70- var actual = queue.Pop();
71- count--;
72-
73- Assert.AreEqual(expected, actual);
74- Assert.AreEqual(count, queue.Count);
75- }
76- }
77-
78- [TestMethod]
79- public void TestMethod2()
80- {
81- var queue = new NMeCab.Core.PriorityQueue<Element>();
82- var collection = new List<Element>();
83- var count = 0;
84-
85- for (int i = 0; i < 5; i++)
86- {
87- //追加 優先度降順
88- for (int j = 5; j >= 0; j--)
89- {
90- var item = new Element { Priority = j, Order = count };
91- queue.Push(item);
92- collection.Add(item);
93- count++;
94-
95- Assert.AreEqual(count, queue.Count);
96- }
97- }
98-
99- //並べ直し
100- collection = (from e in collection
101- orderby e.Priority, e.Order
102- select e).ToList();
103-
104- //取り出し
105- foreach (var expected in collection)
106- {
107- var actual = queue.Pop();
108- count--;
109-
110- Assert.AreEqual(expected, actual);
111- Assert.AreEqual(count, queue.Count);
112- }
113- }
114-
115- [TestMethod]
116- public void TestMethod3()
117- {
118- var queue = new NMeCab.Core.PriorityQueue<Element>();
119- var collection = new List<Element>();
120- var order = 0;
121- var count = 0;
122- var rnd = new Random();
123-
124- //追加と取り出しを一定数繰り返す
125- for (int i = 0; i < 1000; i++)
126- {
127- //ランダム優先度でランダム個追加
128- int repeat = rnd.Next(10);
129- for (int j = 0; j < repeat; j++)
130- {
131- var item = new Element { Priority = rnd.Next(10), Order = order };
132- collection.Add(item);
133- queue.Push(item);
134- order++;
135- count++;
136-
137- Assert.AreEqual(count, queue.Count);
138- }
139-
140- //並べ直し
141- collection = (from e in collection
142- orderby e.Priority, e.Order
143- select e).ToList();
144-
145- //ランダム個取り出し
146- repeat = rnd.Next(collection.Count);
147- for (int j = 0; j < repeat; j++)
148- {
149- var actual = queue.Pop();
150- var expected = collection[j];
151- count--;
152-
153- Assert.AreEqual(expected, actual);
154- Assert.AreEqual(count, queue.Count);
155- }
156- collection.RemoveRange(0, repeat);
157- }
158- }
159- }
160-}
1+using System;
2+using Microsoft.VisualStudio.TestTools.UnitTesting;
3+using System.Collections.Generic;
4+using System.Linq;
5+using System.Diagnostics;
6+
7+namespace LibNMeCabTest
8+{
9+ public class Element : IComparable<Element>
10+ {
11+ public int Priority { get; set; }
12+
13+ public int Order { get; set; }
14+
15+ public int CompareTo(Element other)
16+ {
17+ return this.Priority.CompareTo(other.Priority);
18+ }
19+
20+ public override int GetHashCode()
21+ {
22+ return this.Priority;
23+ }
24+
25+ public override bool Equals(object obj)
26+ {
27+ var other = obj as Element;
28+ return other != null
29+ && this.Priority == other.Priority
30+ && this.Order == other.Order;
31+ }
32+
33+ public override string ToString()
34+ {
35+ return "priority:" + this.Priority + " order:" + this.Order;
36+ }
37+ }
38+
39+ [TestClass]
40+ public class PriorityQueueTest
41+ {
42+ [TestMethod]
43+ public void TestMethod1()
44+ {
45+ var queue = new NMeCab.Core.PriorityQueue<Element>();
46+ var collection = new List<Element>();
47+ var count = 0;
48+
49+ for (int i = 0; i < 5; i++)
50+ {
51+ //追加 優先度昇順
52+ for (int j = 0; j < 5; j++)
53+ {
54+ var item = new Element { Priority = j, Order = count };
55+ queue.Push(item);
56+ collection.Add(item);
57+ count++;
58+ Assert.AreEqual(queue.Count, count);
59+ }
60+ }
61+
62+ //並べ直し
63+ collection = (from e in collection
64+ orderby e.Priority, e.Order
65+ select e).ToList();
66+
67+ //取り出し
68+ foreach (var expected in collection)
69+ {
70+ var actual = queue.Pop();
71+ count--;
72+
73+ Assert.AreEqual(expected, actual);
74+ Assert.AreEqual(count, queue.Count);
75+ }
76+
77+ this.EmptyExceptionTest(queue);
78+ }
79+
80+ [TestMethod]
81+ public void TestMethod2()
82+ {
83+ var queue = new NMeCab.Core.PriorityQueue<Element>();
84+ var collection = new List<Element>();
85+ var count = 0;
86+
87+ for (int i = 0; i < 5; i++)
88+ {
89+ //追加 優先度降順
90+ for (int j = 5; j >= 0; j--)
91+ {
92+ var item = new Element { Priority = j, Order = count };
93+ queue.Push(item);
94+ collection.Add(item);
95+ count++;
96+
97+ Assert.AreEqual(count, queue.Count);
98+ }
99+ }
100+
101+ //並べ直し
102+ collection = (from e in collection
103+ orderby e.Priority, e.Order
104+ select e).ToList();
105+
106+ //取り出し
107+ foreach (var expected in collection)
108+ {
109+ var actual = queue.Pop();
110+ count--;
111+
112+ Assert.AreEqual(expected, actual);
113+ Assert.AreEqual(count, queue.Count);
114+ }
115+
116+ this.EmptyExceptionTest(queue);
117+ }
118+
119+ [TestMethod]
120+ public void TestMethod3()
121+ {
122+ var queue = new NMeCab.Core.PriorityQueue<Element>();
123+ var collection = new List<Element>();
124+ var order = 0;
125+ var count = 0;
126+ var rnd = new Random();
127+
128+ //追加と取り出しを一定数繰り返す
129+ for (int i = 0; i < 1000; i++)
130+ {
131+ //ランダム優先度でランダム個追加
132+ int repeat = rnd.Next(1, 10);
133+ for (int j = 0; j < repeat; j++)
134+ {
135+ var item = new Element { Priority = rnd.Next(10), Order = order };
136+ collection.Add(item);
137+ queue.Push(item);
138+ order++;
139+ count++;
140+
141+ Assert.AreEqual(count, queue.Count);
142+ }
143+
144+ //並べ直し
145+ collection = (from e in collection
146+ orderby e.Priority, e.Order
147+ select e).ToList();
148+
149+ //ランダム個取り出し
150+ repeat = rnd.Next(1, collection.Count);
151+ for (int j = 0; j < repeat; j++)
152+ {
153+ var actual = queue.Pop();
154+ var expected = collection[j];
155+ count--;
156+
157+ Assert.AreEqual(expected, actual);
158+ Assert.AreEqual(count, queue.Count);
159+ }
160+ collection.RemoveRange(0, repeat);
161+ }
162+
163+ while (queue.Count > 0) queue.Pop(); //空にする
164+ this.EmptyExceptionTest(queue);
165+ }
166+
167+ [TestMethod]
168+ public void TestMethod4()
169+ {
170+ var queue = new NMeCab.Core.PriorityQueue<string>();
171+
172+ for (int i = 0; i < 10; i++) queue.Push("abc");
173+
174+ queue.Clear(); //テスト
175+
176+ Assert.AreEqual(0, queue.Count);
177+ this.EmptyExceptionTest(queue);
178+ }
179+
180+ [TestMethod]
181+ public void TestMethod5()
182+ {
183+ var queue = new NMeCab.Core.PriorityQueue<int>();
184+
185+ //10万件挿入
186+ for (int i = 0; i < 100000; i++) queue.Push(i % 5);
187+
188+ //取り出し
189+ while (queue.Count > 0) queue.Pop();
190+ }
191+
192+ private void EmptyExceptionTest<T>(NMeCab.Core.PriorityQueue<T> queue)
193+ where T : IComparable<T>
194+ {
195+ try
196+ {
197+ queue.Pop();//空なら例外発生
198+ }
199+ catch (InvalidOperationException)
200+ {
201+ return;
202+ }
203+ Assert.Fail("Not Throwed Empty Exception");
204+ }
205+ }
206+}