1 //
2 // Copyright (c) 2010-2023 Antmicro
3 //
4 // This file is licensed under the MIT License.
5 // Full license text is available in 'licenses/MIT.txt'.
6 //
7 using System;
8 using System.Collections.Generic;
9 
10 namespace Antmicro.Renode.Utilities.Collections
11 {
12     public class PriorityQueue<TElement, TPriority> where TPriority : IComparable<TPriority>
13     {
PriorityQueue()14         public PriorityQueue()
15         {
16             list = new SortedList<Key, TElement>();
17         }
18 
Enqueue(TElement item, TPriority priority)19         public void Enqueue(TElement item, TPriority priority)
20         {
21             list.Add(new Key(priority, count), item);
22             count++;
23         }
24 
TryDequeue(out TElement item, out TPriority priority)25         public bool TryDequeue(out TElement item, out TPriority priority)
26         {
27             if(!TryPeek(out item, out priority))
28             {
29                 return false;
30             }
31             list.RemoveAt(0);
32             return true;
33         }
34 
Dequeue()35         public TElement Dequeue()
36         {
37             var item = Peek();
38             list.RemoveAt(0);
39             return item;
40         }
41 
TryPeek(out TElement item, out TPriority priority)42         public bool TryPeek(out TElement item, out TPriority priority)
43         {
44             if(Count == 0)
45             {
46                 item = default(TElement);
47                 priority = default(TPriority);
48                 return false;
49             }
50             item = list[list.Keys[0]];
51             priority = list.Keys[0].priority;
52             return true;
53         }
54 
Peek()55         public TElement Peek()
56         {
57             if(!TryPeek(out var item, out _))
58             {
59                 throw new InvalidOperationException("The queue is empty");
60             }
61             return item;
62         }
63 
Clear()64         public void Clear()
65         {
66             list.Clear();
67             count = 0;
68         }
69 
70         public int Count => list.Count;
71 
72         private readonly SortedList<Key, TElement> list;
73         // Used to ensure keys are not duplicate, incremented for every item inserted
74         private ulong count;
75 
76         private class Key : IComparable<Key>
77         {
Key(TPriority priority, ulong count)78             public Key(TPriority priority, ulong count)
79             {
80                 this.priority = priority;
81                 this.count = count;
82             }
83 
CompareTo(Key other)84             public int CompareTo(Key other)
85             {
86                 int priorityDiff = priority.CompareTo(other.priority);
87                 return priorityDiff != 0 ? priorityDiff : count.CompareTo(other.count);
88             }
89 
90             public readonly TPriority priority;
91             public readonly ulong count;
92         }
93     }
94 }
95