PriorityQueue.cs 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Diagnostics;
  5. namespace Amib.Threading.Internal
  6. {
  7. #region PriorityQueue class
  8. /// <summary>
  9. /// PriorityQueue class
  10. /// This class is not thread safe because we use external lock
  11. /// </summary>
  12. public sealed class PriorityQueue : IEnumerable
  13. {
  14. #region Private members
  15. /// <summary>
  16. /// The number of queues, there is one for each type of priority
  17. /// </summary>
  18. private const int _queuesCount = WorkItemPriority.Highest-WorkItemPriority.Lowest+1;
  19. /// <summary>
  20. /// Work items queues. There is one for each type of priority
  21. /// </summary>
  22. private readonly LinkedList<IHasWorkItemPriority>[] _queues = new LinkedList<IHasWorkItemPriority>[_queuesCount];
  23. /// <summary>
  24. /// The total number of work items within the queues
  25. /// </summary>
  26. private int _workItemsCount;
  27. /// <summary>
  28. /// Use with IEnumerable interface
  29. /// </summary>
  30. private int _version;
  31. #endregion
  32. #region Contructor
  33. public PriorityQueue()
  34. {
  35. for(int i = 0; i < _queues.Length; ++i)
  36. {
  37. _queues[i] = new LinkedList<IHasWorkItemPriority>();
  38. }
  39. }
  40. #endregion
  41. #region Methods
  42. /// <summary>
  43. /// Enqueue a work item.
  44. /// </summary>
  45. /// <param name="workItem">A work item</param>
  46. public void Enqueue(IHasWorkItemPriority workItem)
  47. {
  48. Debug.Assert(null != workItem);
  49. int queueIndex = _queuesCount-(int)workItem.WorkItemPriority-1;
  50. Debug.Assert(queueIndex >= 0);
  51. Debug.Assert(queueIndex < _queuesCount);
  52. _queues[queueIndex].AddLast(workItem);
  53. ++_workItemsCount;
  54. ++_version;
  55. }
  56. /// <summary>
  57. /// Dequeque a work item.
  58. /// </summary>
  59. /// <returns>Returns the next work item</returns>
  60. public IHasWorkItemPriority Dequeue()
  61. {
  62. IHasWorkItemPriority workItem = null;
  63. if(_workItemsCount > 0)
  64. {
  65. int queueIndex = GetNextNonEmptyQueue(-1);
  66. Debug.Assert(queueIndex >= 0);
  67. workItem = _queues[queueIndex].First.Value;
  68. _queues[queueIndex].RemoveFirst();
  69. Debug.Assert(null != workItem);
  70. --_workItemsCount;
  71. ++_version;
  72. }
  73. return workItem;
  74. }
  75. /// <summary>
  76. /// Find the next non empty queue starting at queue queueIndex+1
  77. /// </summary>
  78. /// <param name="queueIndex">The index-1 to start from</param>
  79. /// <returns>
  80. /// The index of the next non empty queue or -1 if all the queues are empty
  81. /// </returns>
  82. private int GetNextNonEmptyQueue(int queueIndex)
  83. {
  84. for(int i = queueIndex+1; i < _queuesCount; ++i)
  85. {
  86. if(_queues[i].Count > 0)
  87. {
  88. return i;
  89. }
  90. }
  91. return -1;
  92. }
  93. /// <summary>
  94. /// The number of work items
  95. /// </summary>
  96. public int Count
  97. {
  98. get
  99. {
  100. return _workItemsCount;
  101. }
  102. }
  103. /// <summary>
  104. /// Clear all the work items
  105. /// </summary>
  106. public void Clear()
  107. {
  108. if (_workItemsCount > 0)
  109. {
  110. foreach(LinkedList<IHasWorkItemPriority> queue in _queues)
  111. {
  112. queue.Clear();
  113. }
  114. _workItemsCount = 0;
  115. ++_version;
  116. }
  117. }
  118. #endregion
  119. #region IEnumerable Members
  120. /// <summary>
  121. /// Returns an enumerator to iterate over the work items
  122. /// </summary>
  123. /// <returns>Returns an enumerator</returns>
  124. public IEnumerator GetEnumerator()
  125. {
  126. return new PriorityQueueEnumerator(this);
  127. }
  128. #endregion
  129. #region PriorityQueueEnumerator
  130. /// <summary>
  131. /// The class the implements the enumerator
  132. /// </summary>
  133. private class PriorityQueueEnumerator : IEnumerator
  134. {
  135. private readonly PriorityQueue _priorityQueue;
  136. private int _version;
  137. private int _queueIndex;
  138. private IEnumerator _enumerator;
  139. public PriorityQueueEnumerator(PriorityQueue priorityQueue)
  140. {
  141. _priorityQueue = priorityQueue;
  142. _version = _priorityQueue._version;
  143. _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1);
  144. if (_queueIndex >= 0)
  145. {
  146. _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator();
  147. }
  148. else
  149. {
  150. _enumerator = null;
  151. }
  152. }
  153. #region IEnumerator Members
  154. public void Reset()
  155. {
  156. _version = _priorityQueue._version;
  157. _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1);
  158. if (_queueIndex >= 0)
  159. {
  160. _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator();
  161. }
  162. else
  163. {
  164. _enumerator = null;
  165. }
  166. }
  167. public object Current
  168. {
  169. get
  170. {
  171. Debug.Assert(null != _enumerator);
  172. return _enumerator.Current;
  173. }
  174. }
  175. public bool MoveNext()
  176. {
  177. if (null == _enumerator)
  178. {
  179. return false;
  180. }
  181. if(_version != _priorityQueue._version)
  182. {
  183. throw new InvalidOperationException("The collection has been modified");
  184. }
  185. if (!_enumerator.MoveNext())
  186. {
  187. _queueIndex = _priorityQueue.GetNextNonEmptyQueue(_queueIndex);
  188. if(-1 == _queueIndex)
  189. {
  190. return false;
  191. }
  192. _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator();
  193. _enumerator.MoveNext();
  194. return true;
  195. }
  196. return true;
  197. }
  198. #endregion
  199. }
  200. #endregion
  201. }
  202. #endregion
  203. }