source: stable/HeuristicLab.ExtLibs/HeuristicLab.SimSharp/3.1.1/SimSharp-3.1.1/Collections/EventQueue.cs @ 17053

Last change on this file since 17053 was 17053, checked in by abeham, 2 years ago

#2975: merged to stable

File size: 10.0 KB
Line 
1using System;
2using System.Collections;
3using System.Collections.Generic;
4
5namespace SimSharp {
6  /// <summary>
7  /// An implementation of a min-Priority Queue using a heap.  Has O(1) .Contains()!
8  /// See https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/wiki/Getting-Started for more information
9  /// </summary>
10  /// <remarks>
11  /// There are modifications so that the type is not generic anymore and can only hold values of type EventQueueNode
12  /// </remarks>
13  public sealed class EventQueue : IEnumerable<EventQueueNode> {
14    private int _numNodes;
15    private readonly EventQueueNode[] _nodes;
16    private long _numNodesEverEnqueued;
17
18    /// <summary>
19    /// Instantiate a new Priority Queue
20    /// </summary>
21    /// <param name="maxNodes">EventQueueNodehe max nodes ever allowed to be enqueued (going over this will cause an exception)</param>
22    public EventQueue(int maxNodes) {
23      _numNodes = 0;
24      _nodes = new EventQueueNode[maxNodes + 1];
25      _numNodesEverEnqueued = 0;
26    }
27
28    /// <summary>
29    /// Returns the number of nodes in the queue.  O(1)
30    /// </summary>
31    public int Count {
32      get {
33        return _numNodes;
34      }
35    }
36
37    /// <summary>
38    /// Returns the maximum number of items that can be enqueued at once in this queue.  Once you hit this number (ie. once Count == MaxSize),
39    /// attempting to enqueue another item will throw an exception.  O(1)
40    /// </summary>
41    public int MaxSize {
42      get {
43        return _nodes.Length - 1;
44      }
45    }
46
47    /// <summary>
48    /// Removes every node from the queue.  O(n) (So, don't do this often!)
49    /// </summary>
50    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
51    public void Clear() {
52      Array.Clear(_nodes, 1, _numNodes);
53      _numNodes = 0;
54    }
55
56    /// <summary>
57    /// Returns (in O(1)!) whether the given node is in the queue.  O(1)
58    /// </summary>
59    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
60    public bool Contains(EventQueueNode node) {
61      return (_nodes[node.QueueIndex] == node);
62    }
63
64    /// <summary>
65    /// Enqueue a node - .Priority must be set beforehand!  O(log n)
66    /// </summary>
67    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
68    public EventQueueNode Enqueue(DateTime primaryPriority, Event @event, int secondaryPriority = 0) {
69      var node = new EventQueueNode {
70        PrimaryPriority = primaryPriority,
71        SecondaryPriority = secondaryPriority,
72        Event = @event,
73        QueueIndex = ++_numNodes,
74        InsertionIndex = _numNodesEverEnqueued++
75      };
76      _nodes[_numNodes] = node;
77      CascadeUp(_nodes[_numNodes]);
78      return node;
79    }
80   
81    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
82    private void Swap(EventQueueNode node1, EventQueueNode node2) {
83      //Swap the nodes
84      _nodes[node1.QueueIndex] = node2;
85      _nodes[node2.QueueIndex] = node1;
86
87      //Swap their indicies
88      int temp = node1.QueueIndex;
89      node1.QueueIndex = node2.QueueIndex;
90      node2.QueueIndex = temp;
91    }
92
93    //Performance appears to be slightly better when this is NOT inlined o_O
94    private void CascadeUp(EventQueueNode node) {
95      //aka Heapify-up
96      int parent = node.QueueIndex / 2;
97      while (parent >= 1) {
98        EventQueueNode parentNode = _nodes[parent];
99        if (HasHigherPriority(parentNode, node))
100          break;
101
102        //Node has lower priority value, so move it up the heap
103        Swap(node, parentNode); //For some reason, this is faster with Swap() rather than (less..?) individual operations, like in CascadeDown()
104
105        parent = node.QueueIndex / 2;
106      }
107    }
108
109
110    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
111    private void CascadeDown(EventQueueNode node) {
112      //aka Heapify-down
113      EventQueueNode newParent;
114      int finalQueueIndex = node.QueueIndex;
115      while (true) {
116        newParent = node;
117        int childLeftIndex = 2 * finalQueueIndex;
118
119        //Check if the left-child is higher-priority than the current node
120        if (childLeftIndex > _numNodes) {
121          //This could be placed outside the loop, but then we'd have to check newParent != node twice
122          node.QueueIndex = finalQueueIndex;
123          _nodes[finalQueueIndex] = node;
124          break;
125        }
126
127        EventQueueNode childLeft = _nodes[childLeftIndex];
128        if (HasHigherPriority(childLeft, newParent)) {
129          newParent = childLeft;
130        }
131
132        //Check if the right-child is higher-priority than either the current node or the left child
133        int childRightIndex = childLeftIndex + 1;
134        if (childRightIndex <= _numNodes) {
135          EventQueueNode childRight = _nodes[childRightIndex];
136          if (HasHigherPriority(childRight, newParent)) {
137            newParent = childRight;
138          }
139        }
140
141        //If either of the children has higher (smaller) priority, swap and continue cascading
142        if (newParent != node) {
143          //Move new parent to its new index.  node will be moved once, at the end
144          //Doing it this way is one less assignment operation than calling Swap()
145          _nodes[finalQueueIndex] = newParent;
146
147          int temp = newParent.QueueIndex;
148          newParent.QueueIndex = finalQueueIndex;
149          finalQueueIndex = temp;
150        } else {
151          //See note above
152          node.QueueIndex = finalQueueIndex;
153          _nodes[finalQueueIndex] = node;
154          break;
155        }
156      }
157    }
158
159    /// <summary>
160    /// Returns true if 'higher' has higher priority than 'lower', false otherwise.
161    /// Note that calling HasHigherPriority(node, node) (ie. both arguments the same node) will return false
162    /// </summary>
163
164    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
165    private bool HasHigherPriority(EventQueueNode higher, EventQueueNode lower) {
166      return (higher.PrimaryPriority < lower.PrimaryPriority ||
167          (higher.PrimaryPriority == lower.PrimaryPriority
168            && (higher.SecondaryPriority < lower.SecondaryPriority ||
169            (higher.SecondaryPriority == lower.SecondaryPriority
170              && higher.InsertionIndex < lower.InsertionIndex))));
171    }
172
173    /// <summary>
174    /// Removes the head of the queue (node with highest priority; ties are broken by order of insertion), and returns it.  O(log n)
175    /// </summary>
176    public EventQueueNode Dequeue() {
177      EventQueueNode returnMe = _nodes[1];
178      Remove(returnMe);
179      return returnMe;
180    }
181
182    /// <summary>
183    /// Returns the head of the queue, without removing it (use Dequeue() for that).  O(1)
184    /// </summary>
185    public EventQueueNode First {
186      get {
187        return _nodes[1];
188      }
189    }
190
191    /// <summary>
192    /// This method must be called on a node every time its priority changes while it is in the queue. 
193    /// <b>Forgetting to call this method will result in a corrupted queue!</b>
194    /// O(log n)
195    /// </summary>
196
197    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
198    public void UpdatePriority(EventQueueNode node, DateTime primaryPriority, int secondaryPriority) {
199      node.PrimaryPriority = primaryPriority;
200      node.SecondaryPriority = secondaryPriority;
201      OnNodeUpdated(node);
202    }
203
204    internal void OnNodeUpdated(EventQueueNode node) {
205      //Bubble the updated node up or down as appropriate
206      int parentIndex = node.QueueIndex / 2;
207      EventQueueNode parentNode = _nodes[parentIndex];
208
209      if (parentIndex > 0 && HasHigherPriority(node, parentNode)) {
210        CascadeUp(node);
211      } else {
212        //Note that CascadeDown will be called if parentNode == node (that is, node is the root)
213        CascadeDown(node);
214      }
215    }
216
217    /// <summary>
218    /// Removes a node from the queue.  Note that the node does not need to be the head of the queue.  O(log n)
219    /// </summary>
220    public void Remove(EventQueueNode node) {
221      if (!Contains(node)) {
222        return;
223      }
224      if (_numNodes <= 1) {
225        _nodes[1] = null;
226        _numNodes = 0;
227        return;
228      }
229
230      //Make sure the node is the last node in the queue
231      bool wasSwapped = false;
232      EventQueueNode formerLastNode = _nodes[_numNodes];
233      if (node.QueueIndex != _numNodes) {
234        //Swap the node with the last node
235        Swap(node, formerLastNode);
236        wasSwapped = true;
237      }
238
239      _numNodes--;
240      _nodes[node.QueueIndex] = null;
241
242      if (wasSwapped) {
243        //Now bubble formerLastNode (which is no longer the last node) up or down as appropriate
244        OnNodeUpdated(formerLastNode);
245      }
246    }
247
248    public IEnumerator<EventQueueNode> GetEnumerator() {
249      for (int i = 1; i <= _numNodes; i++)
250        yield return _nodes[i];
251    }
252
253    IEnumerator IEnumerable.GetEnumerator() {
254      return GetEnumerator();
255    }
256
257    /// <summary>
258    /// <b>Should not be called in production code.</b>
259    /// Checks to make sure the queue is still in a valid state.  Used for testing/debugging the queue.
260    /// </summary>
261    public bool IsValidQueue() {
262      for (int i = 1; i < _nodes.Length; i++) {
263        if (_nodes[i] != null) {
264          int childLeftIndex = 2 * i;
265          if (childLeftIndex < _nodes.Length && _nodes[childLeftIndex] != null && HasHigherPriority(_nodes[childLeftIndex], _nodes[i]))
266            return false;
267
268          int childRightIndex = childLeftIndex + 1;
269          if (childRightIndex < _nodes.Length && _nodes[childRightIndex] != null && HasHigherPriority(_nodes[childRightIndex], _nodes[i]))
270            return false;
271        }
272      }
273      return true;
274    }
275  }
276}
Note: See TracBrowser for help on using the repository browser.