| | | 1 | | using System.Diagnostics.CodeAnalysis; |
| | | 2 | | |
| | | 3 | | namespace CounterpointCollective.Collections |
| | | 4 | | { |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// A priority queue where each key is unique and associated with a value and a priority. |
| | | 8 | | /// When <see cref="Enqueue"/> is called for a key already existing in the queue, its associated value and priority |
| | | 9 | | /// Dequeue operations always return the item with the highest priority. |
| | | 10 | | /// </summary> |
| | | 11 | | /// <typeparam name="K">The type of keys in the queue. Must be non-nullable.</typeparam> |
| | | 12 | | /// <typeparam name="V">The type of values associated with the keys.</typeparam> |
| | | 13 | | /// <typeparam name="P">The type used for priority comparisons. Typically implements <see cref="IComparable{P}"/> or |
| | | 14 | | public class UniquePriorityQueue<K, V, P> where K : notnull |
| | | 15 | | { |
| | 9 | 16 | | private readonly Dictionary<K, (V Value, P Priority)> _dictionary = []; |
| | | 17 | | private readonly PriorityQueue<K, P> _priorityQueue; |
| | | 18 | | private readonly IComparer<P> _priorityComparer; |
| | | 19 | | |
| | | 20 | | private const int CutOffMayUseQueueCount = 12; |
| | | 21 | | private const int CutoffMustUseQueueCount = 32; |
| | | 22 | | private bool usingPriorityQueue = false; |
| | | 23 | | |
| | | 24 | | /// <summary> |
| | | 25 | | /// Get the number of unique keys currently in the queue. |
| | | 26 | | /// </summary> |
| | 1 | 27 | | public int Count => _dictionary.Count; |
| | | 28 | | |
| | | 29 | | /// <summary> |
| | | 30 | | /// Initializes a new instance of the <see cref="UniquePriorityQueue{K,V,P}"/> class |
| | | 31 | | /// using the default priority comparer for type <typeparamref name="P"/>. |
| | | 32 | | /// </summary> |
| | 9 | 33 | | public UniquePriorityQueue() : this(Comparer<P>.Default) |
| | | 34 | | { |
| | 9 | 35 | | } |
| | | 36 | | |
| | | 37 | | /// <summary> |
| | | 38 | | /// Initializes a new instance of the <see cref="UniquePriorityQueue{K,V,P}"/> class |
| | | 39 | | /// using the specified priority comparer. |
| | | 40 | | /// </summary> |
| | | 41 | | /// <param name="priorityComparer"> |
| | | 42 | | /// An <see cref="IComparer{P}"/> implementation used to determine the ordering of priorities in the queue. |
| | | 43 | | /// </param> |
| | 9 | 44 | | public UniquePriorityQueue(IComparer<P> priorityComparer) |
| | | 45 | | { |
| | 9 | 46 | | _priorityQueue = new(comparer: priorityComparer); |
| | 9 | 47 | | _priorityComparer = _priorityQueue.Comparer; |
| | 9 | 48 | | } |
| | | 49 | | |
| | | 50 | | /// <summary> |
| | | 51 | | /// Adds a key, value, and priority to the queue. |
| | | 52 | | /// If the key already exists, its value and priority are updated. |
| | | 53 | | /// </summary> |
| | | 54 | | /// <param name="k">The key to add or update in the queue. Must be unique.</param> |
| | | 55 | | /// <param name="v">The value associated with the key.</param> |
| | | 56 | | /// <param name="p">The priority of the item.</param> |
| | | 57 | | /// <remarks> |
| | | 58 | | /// The operation has an amortized time complexity of O(log n). |
| | | 59 | | /// </remarks> |
| | | 60 | | public void Enqueue(K k, V v, P p) |
| | | 61 | | { |
| | 213 | 62 | | _dictionary[k] = (v, p); |
| | | 63 | | |
| | 213 | 64 | | if (!AmortizedCleanupIfNecessary() && usingPriorityQueue) |
| | | 65 | | { |
| | 137 | 66 | | _priorityQueue.Enqueue(k, p); |
| | | 67 | | } |
| | 213 | 68 | | } |
| | | 69 | | |
| | | 70 | | /// <summary> |
| | | 71 | | /// Attempts to remove and return the item with the highest priority from the queue. |
| | | 72 | | /// </summary> |
| | | 73 | | /// <param name="key">When this method returns, contains the key of the removed item, if successful; otherwise, |
| | | 74 | | /// <param name="value">When this method returns, contains the value of the removed item, if successful; otherwi |
| | | 75 | | /// <param name="highestPriority">When this method returns, contains the priority of the removed item, if succes |
| | | 76 | | /// <returns><c>true</c> if an item was successfully removed; otherwise, <c>false</c> if the queue is empty.</re |
| | | 77 | | /// <remarks> |
| | | 78 | | /// The operation has an amortized time complexity of O(log n). |
| | | 79 | | /// </remarks> |
| | | 80 | | public bool TryDequeue([MaybeNullWhen(false)] out K key, [MaybeNullWhen(false)] out V value, [MaybeNullWhen(fals |
| | | 81 | | { |
| | 107 | 82 | | if (FindMinimum(true, out key, out value, out highestPriority)) |
| | | 83 | | { |
| | 105 | 84 | | if (usingPriorityQueue && _dictionary.Count < CutOffMayUseQueueCount) |
| | | 85 | | { |
| | 1 | 86 | | _priorityQueue.Clear(); |
| | 1 | 87 | | usingPriorityQueue = false; |
| | | 88 | | } |
| | 105 | 89 | | return true; |
| | | 90 | | } |
| | | 91 | | else |
| | | 92 | | { |
| | 2 | 93 | | return false; |
| | | 94 | | } |
| | | 95 | | } |
| | | 96 | | |
| | | 97 | | |
| | | 98 | | private bool MinimumPrioUsingQueue(bool remove, [MaybeNullWhen(false)] out K key, [MaybeNullWhen(false)] out V v |
| | | 99 | | { |
| | 180 | 100 | | while (remove ? _priorityQueue.TryDequeue(out key, out highestPriority) : _priorityQueue.TryPeek(out key, ou |
| | | 101 | | { |
| | 180 | 102 | | var keyWasInDict = remove |
| | 180 | 103 | | ? _dictionary.Remove(key, out (V Value, P Priority) vpFromDict) //we optimistically remove. It'll p |
| | 180 | 104 | | : _dictionary.TryGetValue(key, out vpFromDict); |
| | 180 | 105 | | if (keyWasInDict) |
| | | 106 | | { |
| | 180 | 107 | | var currentPriority = vpFromDict.Priority; |
| | 180 | 108 | | if (_priorityComparer.Compare(highestPriority, currentPriority) == 0) |
| | | 109 | | { |
| | 179 | 110 | | value = vpFromDict.Value; |
| | 179 | 111 | | return true; |
| | | 112 | | } |
| | 1 | 113 | | else if (remove) |
| | | 114 | | { |
| | | 115 | | // Our optimism was a case of premature swag; the priority was stale. |
| | | 116 | | // So we put it back. |
| | 1 | 117 | | _dictionary[key] = vpFromDict; |
| | | 118 | | } |
| | | 119 | | } |
| | | 120 | | else |
| | | 121 | | { |
| | 0 | 122 | | if (!remove) |
| | | 123 | | { |
| | 0 | 124 | | _priorityQueue.Dequeue(); // stale entry, and we didn't dequeue it yet. |
| | | 125 | | } |
| | | 126 | | } |
| | | 127 | | } |
| | 0 | 128 | | value = default; |
| | 0 | 129 | | return false; |
| | | 130 | | } |
| | | 131 | | |
| | | 132 | | private bool MinimumPrioUsingLinearDictScan(bool remove, [MaybeNullWhen(false)] out K k, [MaybeNullWhen(false)] |
| | | 133 | | { |
| | 31 | 134 | | using var e = _dictionary.GetEnumerator(); |
| | 47 | 135 | | if (!e.MoveNext()) { k = default; v = default; p = default; return false; } |
| | 81 | 136 | | k = e.Current.Key; v = e.Current.Value.Value; p = e.Current.Value.Priority; |
| | 142 | 137 | | while (e.MoveNext()) |
| | | 138 | | { |
| | 115 | 139 | | if (_priorityComparer.Compare(e.Current.Value.Priority, p) < 0) |
| | | 140 | | { |
| | 339 | 141 | | k = e.Current.Key; v = e.Current.Value.Value; p = e.Current.Value.Priority; |
| | | 142 | | } |
| | | 143 | | } |
| | 27 | 144 | | if (remove) |
| | | 145 | | { |
| | 15 | 146 | | _dictionary.Remove(k); |
| | | 147 | | } |
| | 27 | 148 | | return true; |
| | 31 | 149 | | } |
| | | 150 | | |
| | | 151 | | /// <summary> |
| | | 152 | | /// Attempts to return the item with the highest priority from the queue without removing it. |
| | | 153 | | /// </summary> |
| | | 154 | | /// <param name="key">When this method returns, contains the key of the highest-priority item, if successful; ot |
| | | 155 | | /// <param name="value">When this method returns, contains the value of the highest-priority item, if successful |
| | | 156 | | /// <param name="highestPriority">When this method returns, contains the priority of the highest-priority item, |
| | | 157 | | /// <returns><c>true</c> if the queue contains at least one item; otherwise, <c>false</c>.</returns> |
| | | 158 | | /// <remarks> |
| | | 159 | | /// The operation has an amortized time complexity of O(log n). |
| | | 160 | | /// </remarks> |
| | | 161 | | public bool TryPeek([MaybeNullWhen(false)] out K key, [MaybeNullWhen(false)] out V value, [MaybeNullWhen(false)] |
| | 103 | 162 | | => FindMinimum(false, out key, out value, out highestPriority); |
| | | 163 | | |
| | | 164 | | private bool FindMinimum(bool remove, [MaybeNullWhen(false)] out K key, [MaybeNullWhen(false)] out V value, [May |
| | | 165 | | => |
| | 210 | 166 | | usingPriorityQueue |
| | 210 | 167 | | ? MinimumPrioUsingQueue(remove, out key, out value, out highestPriority) |
| | 210 | 168 | | : MinimumPrioUsingLinearDictScan(remove, out key, out value, out highestPriority); |
| | | 169 | | |
| | | 170 | | /// <summary> |
| | | 171 | | /// Returns the item with the highest priority without removing it from the queue. |
| | | 172 | | /// </summary> |
| | | 173 | | /// <returns>A tuple containing the key, value, and priority of the highest-priority item.</returns> |
| | | 174 | | /// <exception cref="InvalidOperationException">Thrown if the queue is empty.</exception> |
| | | 175 | | /// <remarks> |
| | | 176 | | /// The operation has an amortized time complexity of O(log n). |
| | | 177 | | /// </remarks> |
| | | 178 | | public (K key, V value, P priority) Peek() => |
| | 2 | 179 | | TryPeek(out var key, out var value, out var priority) |
| | 2 | 180 | | ? (key, value, priority) |
| | 2 | 181 | | : throw new InvalidOperationException("Queue is empty"); |
| | | 182 | | |
| | | 183 | | /// <summary> |
| | | 184 | | /// Removes the item with the specified key from the queue, if it exists. |
| | | 185 | | /// </summary> |
| | | 186 | | /// <param name="s">The key of the item to remove.</param> |
| | | 187 | | /// <param name="value">When this method returns, contains the value of the removed item, if successful; otherwi |
| | | 188 | | /// <param name="priority">When this method returns, contains the priority of the removed item, if successful; o |
| | | 189 | | /// <returns><c>true</c> if the item was found and removed; otherwise, <c>false</c>.</returns> |
| | | 190 | | /// <remarks> |
| | | 191 | | /// The operation has an amortized time complexity of O(log n). |
| | | 192 | | /// </remarks> |
| | | 193 | | public bool Remove(K s, [MaybeNullWhen(false)] out V value, [MaybeNullWhen(false)] out P priority) |
| | | 194 | | { |
| | 1 | 195 | | if (_dictionary.Remove(s, out var kv)) |
| | | 196 | | { |
| | 1 | 197 | | value = kv.Value; |
| | 1 | 198 | | priority = kv.Priority; |
| | 1 | 199 | | AmortizedCleanupIfNecessary(); |
| | 1 | 200 | | return true; |
| | | 201 | | } |
| | | 202 | | else |
| | | 203 | | { |
| | 0 | 204 | | value = default; |
| | 0 | 205 | | priority = default; |
| | 0 | 206 | | return false; |
| | | 207 | | } |
| | | 208 | | } |
| | | 209 | | |
| | | 210 | | /// <summary> |
| | | 211 | | /// Attempts to get the value and priority associated with the specified key without removing it from the queue. |
| | | 212 | | /// </summary> |
| | | 213 | | /// <param name="k">The key of the item to look up.</param> |
| | | 214 | | /// <param name="v">When this method returns, contains the value associated with the key, if found; otherwise, t |
| | | 215 | | /// <param name="p">When this method returns, contains the priority associated with the key, if found; otherwise |
| | | 216 | | /// <returns><c>true</c> if the key exists in the queue; otherwise, <c>false</c>.</returns> |
| | | 217 | | /// <remarks> |
| | | 218 | | /// The operation has a time complexity of O(1). |
| | | 219 | | /// </remarks> |
| | | 220 | | public bool TryGet(K k, [MaybeNullWhen(false)] out V v, [MaybeNullWhen(false)] out P p) |
| | | 221 | | { |
| | 3 | 222 | | if (_dictionary.TryGetValue(k, out var vp)) |
| | | 223 | | { |
| | 1 | 224 | | v = vp.Value; |
| | 1 | 225 | | p = vp.Priority; |
| | 1 | 226 | | return true; |
| | | 227 | | } |
| | | 228 | | else |
| | | 229 | | { |
| | 2 | 230 | | v = default; |
| | 2 | 231 | | p = default; |
| | 2 | 232 | | return false; |
| | | 233 | | } |
| | | 234 | | } |
| | | 235 | | |
| | | 236 | | /// <summary> |
| | | 237 | | /// Returns the value and priority associated with the specified key. |
| | | 238 | | /// </summary> |
| | | 239 | | /// <param name="k">The key of the item to retrieve.</param> |
| | | 240 | | /// <returns>A tuple containing the value and priority associated with the key.</returns> |
| | | 241 | | /// <exception cref="KeyNotFoundException">Thrown if the specified key does not exist in the queue.</exception> |
| | | 242 | | /// <remarks> |
| | | 243 | | /// The operation has a time complexity of O(1). |
| | | 244 | | /// </remarks> |
| | | 245 | | public (V Value, P Priority) Get(K k) => |
| | 0 | 246 | | TryGet(k, out var v, out var p) ? (v, p) : throw new KeyNotFoundException(); |
| | | 247 | | |
| | | 248 | | /// <summary> |
| | | 249 | | /// Removes all items from the queue. |
| | | 250 | | /// </summary> |
| | | 251 | | public void Clear() |
| | | 252 | | { |
| | 1 | 253 | | _dictionary.Clear(); |
| | 1 | 254 | | _priorityQueue.Clear(); |
| | 1 | 255 | | } |
| | | 256 | | |
| | | 257 | | /// <returns>Whether we rebuilt the queue</returns> |
| | | 258 | | private bool AmortizedCleanupIfNecessary() |
| | | 259 | | { |
| | 214 | 260 | | var c = _dictionary.Count; |
| | 214 | 261 | | if (usingPriorityQueue && (c < CutOffMayUseQueueCount || _priorityQueue.Count > c * 2)) |
| | | 262 | | { |
| | | 263 | | //Ditch the queue: There are too many stale entries, or our Count is simply too small. |
| | 0 | 264 | | _priorityQueue.Clear(); |
| | 0 | 265 | | usingPriorityQueue = false; |
| | | 266 | | } |
| | | 267 | | |
| | 214 | 268 | | if (!usingPriorityQueue && c >= CutoffMustUseQueueCount) |
| | | 269 | | { |
| | 2 | 270 | | usingPriorityQueue = true; |
| | 132 | 271 | | foreach (var (k, (v, p)) in _dictionary) |
| | | 272 | | { |
| | 64 | 273 | | _priorityQueue.Enqueue(k, p); |
| | | 274 | | } |
| | 2 | 275 | | return true; |
| | | 276 | | } |
| | | 277 | | |
| | 212 | 278 | | return false; |
| | | 279 | | } |
| | | 280 | | } |
| | | 281 | | } |