PBL - The program base library
C# AvlDictionary and Priority Queue implementation
 All Classes Namespaces Files Functions Properties
PriorityQueue.cs
Go to the documentation of this file.
1 /*
2  PriorityQueue.cs - C# implementation of a binary min-heap based generic priority queue.
3 
4  Copyright (C) 2012 Peter Graf
5 
6  This file is part of PBL - The Program Base Library.
7  PBL is free software.
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 
23  For more information on the Program Base Library or Peter Graf,
24  please see: http://www.mission-base.com/.
25 
26  $Log: PriorityQueue.cs,v $
27  Revision 1.3 2012/12/11 00:44:32 peter
28  Added documentation comments.
29 
30  Revision 1.2 2012/12/09 02:40:28 peter
31  Better exception handling
32 
33  Revision 1.1 2012/12/09 01:19:23 peter
34  Initial Version
35 
36  */
37 
38 using System;
39 using System.Collections.Generic;
40 using System.Runtime.InteropServices;
41 using System.Diagnostics;
42 
43 namespace Com.Mission_Base.Pbl
44 {
54  [Serializable]
55  [ComVisible(false)]
56  [DebuggerDisplay("Count = {Count}")]
57  public class PriorityQueue<T> : List<T>, IList<T> where T : IComparable<T>
58  {
59  private readonly object _lock;
60  private readonly IComparer<T> _comparer;
61 
62  #region Heap handling
63 
64  private int CompareItems(T left, T right)
65  {
66  if (_comparer == null)
67  {
68  if (left == null)
69  {
70  if (right == null)
71  {
72  return 0;
73  }
74  return -1;
75  }
76  return left.CompareTo(right);
77  }
78  return _comparer.Compare(left, right);
79  }
80 
81  private int LastParentIndex
82  {
83  // For zero based arrays all elements with an index bigger
84  // than 'Count / 2 - 1' do not have any children
85  get
86  {
87  return Count / 2 - 1;
88  }
89  }
90 
91  private void EnsureHeapConditionDownward(int index)
92  {
93  int lastParentIndex = LastParentIndex;
94  if (index <= lastParentIndex)
95  {
96  var entry = base[index];
97 
98  // As long as the entry has at least one child
99  //
100  while (index <= lastParentIndex)
101  {
102  // For zero based arrays the left child is at '2 * index + 1'
103  //
104  int childIndex = 2 * index + 1;
105 
106  var child = base[childIndex];
107 
108  // If the entry also has a right child, the smaller child
109  // needs to be considered for the swap
110  //
111  if (childIndex < Count - 1)
112  {
113  // The right child is next to the left child in the array
114  //
115  int rightChildIndex = childIndex + 1;
116  var rightChild = base[rightChildIndex];
117 
118  if (CompareItems(rightChild, child) < 0)
119  {
120  // Use the right child for the swap
121  //
122  child = rightChild;
123  childIndex = rightChildIndex;
124  }
125  }
126 
127  if (CompareItems(entry, child) <= 0)
128  {
129  // The heap condition is fulfilled for the entry
130  //
131  return;
132  }
133 
134  // Do the swap with the child
135  //
136  base[childIndex] = entry;
137  base[index] = child;
138 
139  index = childIndex;
140  }
141  }
142 
143  // The entry does not have any children, therefore
144  // the heap condition is fulfilled for the entry
145  }
146 
147  private int EnsureHeapConditionUpward(int index)
148  {
149  if (index > 0)
150  {
151  var entry = base[index];
152 
153  // As long as the entry is not the top of the heap
154  //
155  while (index > 0)
156  {
157  // For zero based arrays the parent index is '( index - 1 ) / 2'
158  //
159  int parentIndex = (index - 1) / 2;
160  var parent = this[parentIndex];
161 
162  if (CompareItems(entry, parent) >= 0)
163  {
164  // The heap condition is fulfilled for the entry
165  //
166  return index;
167  }
168 
169  // Do the swap with the parent
170  //
171  base[parentIndex] = entry;
172  base[index] = parent;
173 
174  index = parentIndex;
175  }
176  }
177 
178  // The entry is the top of the heap
179  //
180  return index;
181  }
182 
189  public void EnsureHeapCondition(int index)
190  {
191  int rc = EnsureHeapConditionUpward(index);
192  if (rc == index)
193  {
194  EnsureHeapConditionDownward(index);
195  }
196  }
197 
204  public void EnsureHeapCondition()
205  {
206  // The heap condition is always fulfilled for entries without children,
207  // therefore 'bottom-up heap construction' only needs to look
208  // at elements that do have children
209  //
210  for (int index = LastParentIndex; index >= 0; index--)
211  {
212  EnsureHeapConditionDownward(index);
213  }
214  }
215 
216  private void HeapRemoveAt(int index)
217  {
218  if (index < 0 || index >= Count)
219  {
220  throw new ArgumentOutOfRangeException(string.Format("Index {0} is less than 0, or index is equal to or greater than priority queue count {1}.", index, Count));
221  }
222  else if (index == Count - 1)
223  {
224  base.RemoveAt(index);
225  return;
226  }
227 
228  // Remove the last entry in the list
229  //
230  base[index] = base[Count - 1];
231  base.RemoveAt(Count - 1);
232 
233  if (Count > 1)
234  {
235  // Copying the values might have violated the heap condition
236  // at position index, it needs to ensured
237  //
238  EnsureHeapCondition(index);
239  }
240  }
241  #endregion
242 
243  #region Constructors
244 
248  public PriorityQueue()
249  {
250  _lock = new object();
251  }
252 
256  public PriorityQueue(IEnumerable<T> enumerable)
257  : base(enumerable)
258  {
259  _lock = new object();
260  EnsureHeapCondition();
261  }
262 
266  public PriorityQueue(Int32 capacity)
267  : base(capacity)
268  {
269  _lock = new object();
270  }
271 
275  public PriorityQueue(IComparer<T> comparer)
276  {
277  _comparer = comparer;
278  _lock = new object();
279  }
280 
284  public PriorityQueue(IEnumerable<T> enumerable, IComparer<T> comparer)
285  : base(enumerable)
286  {
287  _comparer = comparer;
288  _lock = new object();
289  EnsureHeapCondition();
290  }
291 
295  public PriorityQueue(Int32 capacity, IComparer<T> comparer)
296  : base(capacity)
297  {
298  _comparer = comparer;
299  _lock = new object();
300  }
301  #endregion
302 
303  #region Queue methods
304 
316  public void Enqueue(T item)
317  {
318  base.Add(item);
319  EnsureHeapConditionUpward(Count - 1);
320  }
321 
333  public T Dequeue()
334  {
335  if (Count == 0)
336  {
337  throw new InvalidOperationException("The priority queue is empty.");
338  }
339  var result = base[0];
340  HeapRemoveAt(0);
341  return result;
342  }
343 
355  public T Peek()
356  {
357  if (Count == 0)
358  {
359  throw new InvalidOperationException("The priority queue is empty.");
360  }
361  return base[0];
362  }
363  #endregion
364 
365  #region List methods
366 
379 
381  public new T this[int index]
382  {
383  get { return base[index]; }
384  set
385  {
386  base[index] = value;
387  EnsureHeapCondition(index);
388  }
389  }
390 
402  public new void Add(T item)
403  {
404  Enqueue(item);
405  }
406 
416  public new void AddRange(IEnumerable<T> collection)
417  {
418  base.AddRange(collection);
419  EnsureHeapCondition();
420  }
421 
438  public new void Insert(int index, T item)
439  {
440  Enqueue(item);
441  }
442 
457  public new void InsertRange(int index, IEnumerable<T> collection)
458  {
459  base.InsertRange(index, collection);
460  EnsureHeapCondition();
461  }
462 
472  public new void RemoveAt(int index)
473  {
474  HeapRemoveAt(index);
475  }
476 
489  public new bool Remove(T item)
490  {
491  int index = IndexOf(item);
492  if (index < 0)
493  {
494  return false;
495  }
496  HeapRemoveAt(index);
497  return true;
498  }
499 
512  public new int RemoveAll(Predicate<T> match)
513  {
514  var result = base.RemoveAll(match);
515  if (result > 0)
516  {
517  EnsureHeapCondition();
518  }
519  return result;
520  }
521 
534  public new void RemoveRange(int index, int count)
535  {
536  base.RemoveRange(index, count);
537  if (index > LastParentIndex)
538  {
539  EnsureHeapCondition();
540  }
541  }
542 
549  public new void Reverse()
550  {
551  if (Count > 1)
552  {
553  throw new InvalidOperationException("A priority queue cannot be reversed.");
554  }
555  }
556 
563  public new void Reverse(int index, int count)
564  {
565  if (index > LastParentIndex)
566  {
567  throw new InvalidOperationException("A priority queue cannot be partially reversed.");
568  }
569  base.Reverse(index, count);
570  }
571 
580  public new void Sort()
581  {
582  if (Count > 1)
583  {
584  if (_comparer != null)
585  {
586  base.Sort(_comparer);
587  }
588  else
589  {
590  base.Sort();
591  }
592  }
593  }
594 
601  public new void Sort(IComparer<T> comparer)
602  {
603  if (Count > 1)
604  {
605  if (!ReferenceEquals(comparer, _comparer))
606  {
607  throw new InvalidOperationException("A priority queue cannot be sorted with a comparer other than the one specified for the priority queue.");
608  }
609  base.Sort(_comparer);
610  }
611  }
612 
619  public new void Sort(int index, int count, IComparer<T> comparer)
620  {
621  if (Count > 1)
622  {
623  if (!ReferenceEquals(comparer, _comparer) || index != 0 || count != Count)
624  {
625  throw new InvalidOperationException("A priority queue cannot be partially sorted.");
626  }
627  base.Sort(index, count, _comparer);
628  }
629  }
630 
637  public new void Sort(Comparison<T> comparison)
638  {
639  if (Count > 1)
640  {
641  throw new InvalidOperationException("A priority queue cannot be sorted with a comparison.");
642  }
643  }
644  #endregion
645 
646  #region Misc
647 
654  public object SyncRoot
655  {
656  get { return _lock; }
657  }
658 
665  public bool IsSynchronized
666  {
667  get { return false; }
668  }
669 
676  public IComparer<T> Comparer { get { return _comparer; } }
677 
678  #endregion
679  }
680 }