1: using System;
2: using System.Collections.Generic;
3:
4: namespace bloodforge
5: {
6: public class PriorityQueue<P, T>
7: where P : System.IComparable<P>
8: {
9: protected List<Queue<PriorityItem<P, T>>> _queues;
10: protected int _count;
11:
12: public PriorityQueue()
13: {
14: _queues = new List<Queue<PriorityItem<P, T>>>();
15: _count = 0;
16: }
17:
18: /// <summary>
19: /// Add an item to the priority queue
20: /// </summary>
21: public void Enqueue(P priority, T data)
22: {
23: if (_count == 0)
24: {
25: Queue<PriorityItem<P, T>> NewQueue = new Queue<PriorityItem<P, T>>();
26: NewQueue.Enqueue(new PriorityItem<P, T>(priority, data));
27: _queues.Add(NewQueue);
28: }
29: else
30: {
31: QueueInsert(priority, data, 0, _queues.Count - 1);
32: }
33:
34: _count++;
35: }
36:
37: /// <summary>
38: /// Helper method for Enqueue
39: /// </summary>
40: private void QueueInsert(P priority, T data, int qLo, int qHi)
41: {
42: if (qLo == qHi)
43: {
44: // There is only one item left to compare.
45: // Need to decide where this item belongs in relation to the last item.
46: if (_queues[qLo].Peek().Priority.CompareTo(priority) < 0)
47: {
48: Queue<PriorityItem<P, T>> NewQueue = new Queue<PriorityItem<P, T>>();
49: NewQueue.Enqueue(new PriorityItem<P, T>(priority, data));
50: _queues.Insert(qLo, NewQueue);
51: return;
52: }
53: else if (_queues[qLo].Peek().Priority.CompareTo(priority) > 0)
54: {
55: Queue<PriorityItem<P, T>> NewQueue = new Queue<PriorityItem<P, T>>();
56: NewQueue.Enqueue(new PriorityItem<P, T>(priority, data));
57: _queues.Insert(qLo + 1, NewQueue);
58: return;
59: }
60: else
61: {
62: _queues[qLo].Enqueue(new PriorityItem<P, T>(priority, data));
63: return;
64: }
65: }
66: else
67: {
68: // Get the middle item from the queue and see if we
69: // need to go to the first or second half of the queues list
70: int qMid = Convert.ToInt32(Math.Floor((qLo + qHi) / 2));
71: if (_queues[qMid].Peek().Priority.CompareTo(priority) < 0)
72: {
73: // This item belongs in the upper half of the range
74: QueueInsert(priority, data, qLo, qMid);
75: return;
76: }
77: else if (_queues[qMid].Peek().Priority.CompareTo(priority) > 0)
78: {
79: // This item belongs in the lower half of the range
80: QueueInsert(priority, data, qMid + 1, qHi);
81: return;
82: }
83: else
84: {
85: // we got lucky, the middle item is of the same priority
86: _queues[qMid].Enqueue(new PriorityItem<P, T>(priority, data));
87: return;
88: }
89: }
90: }
91:
92: /// <summary>
93: /// Remove the top item from the queue
94: /// </summary>
95: public T Dequeue()
96: {
97: if (_queues.Count == 0)
98: {
99: // There are no items in the priority queue
100: return default(T);
101: }
102:
103: // Get the first item from the first queue
104: T data = _queues[0].Dequeue().Data;
105:
106: if (_queues[0].Count == 0)
107: {
108: // If the queue at the top priority is empty, remove it
109: _queues.RemoveAt(0);
110: }
111:
112: _count--;
113:
114: return data;
115:
116: }
117:
118: /// <summary>
119: /// Retrieves the top item from the queue without removing it
120: /// </summary>
121: public T Peek()
122: {
123: if (_queues.Count > 0)
124: {
125: return _queues[0].Peek().Data;
126: }
127: else return default(T);
128: }
129:
130: /// <summary>
131: /// Gets the number of items in the priority queue
132: /// </summary>
133: public int Count
134: {
135: get
136: {
137: return _count;
138: }
139: }
140:
141: /// <summary>
142: /// Returns a string representation of the queue
143: /// </summary>
144: public override string ToString()
145: {
146: string val = string.Empty;
147: foreach(Queue<PriorityItem<P, T>> queue in _queues)
148: {
149: PriorityItem<P, T>[] items = queue.ToArray();
150: foreach (PriorityItem<P, T> item in items)
151: {
152: val += string.Format(" [ {0} ] ", item.Data.ToString());
153: }
154: }
155: return val.TrimEnd(',');
156: }
157: }
158:
159: public class PriorityItem<P, T>
160: where P : System.IComparable<P>
161: {
162: public P Priority;
163: public T Data;
164:
165: public PriorityItem(P priority, T data)
166: {
167: this.Priority = priority;
168: this.Data = data;
169: }
170: }
171: }
Subscribe