source: trunk/CrypPlugins/PlayfairAnalysis/PriorityQueue.cs @ 2334

Last change on this file since 2334 was 1939, checked in by Christoph Hartmann, 11 years ago

Playfair Analysis Plugin (basically runs, but not ready yet)

File size: 11.3 KB
Line 
1// PriorityQueue.cs
2//
3// Jim Mischel
4using System;
5using System.Collections;
6using System.Collections.Generic;
7using System.Runtime.InteropServices;
8
9namespace Mischel.Collections
10{
11    [Serializable]
12    [ComVisible(false)]
13    public struct PriorityQueueItem<TValue, TPriority>
14    {
15        private TValue _value;
16        public TValue Value
17        {
18            get { return _value; }
19        }
20
21        private TPriority _priority;
22        public TPriority Priority
23        {
24            get { return _priority; }
25        }
26
27        internal PriorityQueueItem(TValue val, TPriority pri)
28        {
29            this._value = val;
30            this._priority = pri;
31        }
32    }
33
34    [Serializable]
35    [ComVisible(false)]
36    public class PriorityQueue<TValue, TPriority> : ICollection,
37        IEnumerable<PriorityQueueItem<TValue, TPriority>>
38    {
39        private PriorityQueueItem<TValue, TPriority>[] items;
40
41        private const Int32 DefaultCapacity = 16;
42        private Int32 capacity;
43        private Int32 numItems;
44
45        private Comparison<TPriority> compareFunc;
46
47        /// <summary>
48        /// Initializes a new instance of the PriorityQueue class that is empty,
49        /// has the default initial capacity, and uses the default IComparer.
50        /// </summary>
51        public PriorityQueue()
52            : this(DefaultCapacity, Comparer<TPriority>.Default)
53        {
54        }
55
56        public PriorityQueue(Int32 initialCapacity)
57            : this(initialCapacity, Comparer<TPriority>.Default)
58        {
59        }
60
61        public PriorityQueue(IComparer<TPriority> comparer)
62            : this(DefaultCapacity, comparer)
63        {
64        }
65
66        public PriorityQueue(int initialCapacity, IComparer<TPriority> comparer)
67        {
68            Init(initialCapacity, new Comparison<TPriority>(comparer.Compare));
69        }
70
71        public PriorityQueue(Comparison<TPriority> comparison)
72            : this(DefaultCapacity, comparison)
73        {
74        }
75
76        public PriorityQueue(int initialCapacity, Comparison<TPriority> comparison)
77        {
78            Init(initialCapacity, comparison);
79        }
80
81        private void Init(int initialCapacity, Comparison<TPriority> comparison)
82        {
83            numItems = 0;
84            compareFunc = comparison;
85            SetCapacity(initialCapacity);
86        }
87
88        public int Count
89        {
90            get { return numItems; }
91        }
92
93        public int Capacity
94        {
95            get { return items.Length; }
96            set { SetCapacity(value); }
97        }
98
99        private void SetCapacity(int newCapacity)
100        {
101            int newCap = newCapacity;
102            if (newCap < DefaultCapacity)
103                newCap = DefaultCapacity;
104
105            // throw exception if newCapacity < NumItems
106            if (newCap < numItems)
107                throw new ArgumentOutOfRangeException("newCapacity", "New capacity is less than Count");
108
109            this.capacity = newCap;
110            if (items == null)
111            {
112                items = new PriorityQueueItem<TValue, TPriority>[newCap];
113                return;
114            }
115
116            // Resize the array.
117            Array.Resize<PriorityQueueItem<TValue, TPriority>>(ref items, newCap);
118        }
119
120        public void Enqueue(PriorityQueueItem<TValue, TPriority> newItem)
121        {
122            if (numItems == capacity)
123            {
124                // need to increase capacity
125                // grow by 50 percent
126                SetCapacity((3 * Capacity) / 2);
127            }
128
129            int i = numItems;
130            ++numItems;
131            while ((i > 0) && (compareFunc(items[(i - 1) / 2].Priority, newItem.Priority) < 0))
132            {
133                items[i] = items[(i - 1) / 2];
134                i = (i - 1) / 2;
135            }
136            items[i] = newItem;
137            //if (!VerifyQueue())
138            //{
139            //    Console.WriteLine("ERROR: Queue out of order!");
140            //}
141        }
142
143        public void Enqueue(TValue value, TPriority priority)
144        {
145            Enqueue(new PriorityQueueItem<TValue, TPriority>(value, priority));
146        }
147
148        private PriorityQueueItem<TValue, TPriority> RemoveAt(Int32 index)
149        {
150            PriorityQueueItem<TValue, TPriority> o = items[index];
151            --numItems;
152            // move the last item to fill the hole
153            PriorityQueueItem<TValue, TPriority> tmp = items[numItems];
154            // If you forget to clear this, you have a potential memory leak.
155            items[numItems] = default(PriorityQueueItem<TValue, TPriority>);
156            if (numItems > 0 && index != numItems)
157            {
158                // If the new item is greater than its parent, bubble up.
159                int i = index;
160                int parent = (i - 1) / 2;
161                while (compareFunc(tmp.Priority, items[parent].Priority) > 0)
162                {
163                    items[i] = items[parent];
164                    i = parent;
165                    parent = (i - 1) / 2;
166                }
167
168                // if i == index, then we didn't move the item up
169                if (i == index)
170                {
171                    // bubble down ...
172                    while (i < (numItems) / 2)
173                    {
174                        int j = (2 * i) + 1;
175                        if ((j < numItems - 1) && (compareFunc(items[j].Priority, items[j + 1].Priority) < 0))
176                        {
177                            ++j;
178                        }
179                        if (compareFunc(items[j].Priority, tmp.Priority) <= 0)
180                        {
181                            break;
182                        }
183                        items[i] = items[j];
184                        i = j;
185                    }
186                }
187                // Be sure to store the item in its place.
188                items[i] = tmp;
189            }
190            //if (!VerifyQueue())
191            //{
192            //    Console.WriteLine("ERROR: Queue out of order!");
193            //}
194            return o;
195        }
196
197        // Function to check that the queue is coherent.
198        public bool VerifyQueue()
199        {
200            int i = 0;
201            while (i < numItems / 2)
202            {
203                int leftChild = (2 * i) + 1;
204                int rightChild = leftChild + 1;
205                if (compareFunc(items[i].Priority, items[leftChild].Priority) < 0)
206                {
207                    return false;
208                }
209                if (rightChild < numItems && compareFunc(items[i].Priority, items[rightChild].Priority) < 0)
210                {
211                    return false;
212                }
213                ++i;
214            }
215            return true;
216        }
217
218        public PriorityQueueItem<TValue, TPriority> Dequeue()
219        {
220            if (Count == 0)
221                throw new InvalidOperationException("The queue is empty");
222            return RemoveAt(0);
223        }
224
225        /// <summary>
226        /// Removes the item with the specified value from the queue.
227        /// The passed equality comparison is used.
228        /// </summary>
229        /// <param name="item">The item to be removed.</param>
230        /// <param name="comp">An object that implements the IEqualityComparer interface
231        /// for the type of item in the collection.</param>
232        public void Remove(TValue item, IEqualityComparer comparer)
233        {
234            // need to find the PriorityQueueItem that has the Data value of o
235            for (int index = 0; index < numItems; ++index)
236            {
237                if (comparer.Equals(item, items[index].Value))
238                {
239                    RemoveAt(index);
240                    return;
241                }
242            }
243            throw new ApplicationException("The specified itemm is not in the queue.");
244        }
245
246        /// <summary>
247        /// Removes the item with the specified value from the queue.
248        /// The default type comparison function is used.
249        /// </summary>
250        /// <param name="item">The item to be removed.</param>
251        public void Remove(TValue item)
252        {
253            Remove(item, EqualityComparer<TValue>.Default);
254        }
255
256        public PriorityQueueItem<TValue, TPriority> Peek()
257        {
258            if (Count == 0)
259                throw new InvalidOperationException("The queue is empty");
260            return items[0];
261        }
262
263        // Clear
264        public void Clear()
265        {
266            for (int i = 0; i < numItems; ++i)
267            {
268                items[i] = default(PriorityQueueItem<TValue, TPriority>);
269            }
270            numItems = 0;
271            TrimExcess();
272        }
273
274        /// <summary>
275        /// Set the capacity to the actual number of items, if the current
276        /// number of items is less than 90 percent of the current capacity.
277        /// </summary>
278        public void TrimExcess()
279        {
280            if (numItems < (float)0.9 * capacity)
281            {
282                SetCapacity(numItems);
283            }
284        }
285
286        // Contains
287        public bool Contains(TValue o)
288        {
289            foreach (PriorityQueueItem<TValue, TPriority> x in items)
290            {
291                if (x.Value.Equals(o))
292                    return true;
293            }
294            return false;
295        }
296
297        public void CopyTo(PriorityQueueItem<TValue, TPriority>[] array, int arrayIndex)
298        {
299            if (array == null)
300                throw new ArgumentNullException("array");
301            if (arrayIndex < 0)
302                throw new ArgumentOutOfRangeException("arrayIndex", "arrayIndex is less than 0.");
303            if (array.Rank > 1)
304                throw new ArgumentException("array is multidimensional.");
305            if (numItems == 0)
306                return;
307            if (arrayIndex >= array.Length)
308                throw new ArgumentException("arrayIndex is equal to or greater than the length of the array.");
309            if (numItems > (array.Length - arrayIndex))
310                throw new ArgumentException("The number of elements in the source ICollection is greater than the available space from arrayIndex to the end of the destination array.");
311
312            for (int i = 0; i < numItems; i++)
313            {
314                array[arrayIndex + i] = items[i];
315            }
316        }
317
318        #region ICollection Members
319
320        public void CopyTo(Array array, int index)
321        {
322            this.CopyTo((PriorityQueueItem<TValue, TPriority>[])array, index);
323        }
324
325        public bool IsSynchronized
326        {
327            get { return false; }
328        }
329
330        public object SyncRoot
331        {
332            get { return items.SyncRoot; }
333        }
334
335        #endregion
336
337        #region IEnumerable<PriorityQueueItem<TValue,TPriority>> Members
338
339        public IEnumerator<PriorityQueueItem<TValue, TPriority>> GetEnumerator()
340        {
341            for (int i = 0; i < numItems; i++)
342            {
343                yield return items[i];
344            }
345        }
346
347        #endregion
348
349        #region IEnumerable Members
350
351        IEnumerator IEnumerable.GetEnumerator()
352        {
353            return GetEnumerator();
354        }
355
356        #endregion
357    }
358}
Note: See TracBrowser for help on using the repository browser.