SHARE
TWEET

Untitled

a guest Oct 19th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. we depend on the discipline List<T> have (or not) arround allocating arrays
  3. if you are dealing with known length then modify to have a cap parameter and pre allocate your List<T>
  4. */
  5. using System;
  6. using System.Threading;
  7. using System.Collections.Generic;
  8.  
  9. using System.Runtime.CompilerServices;
  10.  
  11. namespace Utils
  12. {
  13.     public delegate bool Comparer<T>(T lh, T rh);
  14.  
  15.     public class PriorityQueue<T> where T : class
  16.     {
  17.         private Comparer<T> comparer;
  18.         private ReaderWriterLockSlim rwLock = new ReaderWriterLockSlim();
  19.         private List<T> list = new List<T>();
  20.  
  21.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  22.         private int ParentIdxOf(int idx) { return (idx - 1) / 2; }
  23.  
  24.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  25.         private int LeftChildIdxOf(int idx) { return (2 * idx + 1); }
  26.  
  27.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  28.         private int RightChildIdxOf(int idx) { return (2 * idx + 2); }
  29.  
  30.         // must be called with lock held
  31.         private void ensureHeap(int atIdx)
  32.         {
  33.             var leftChildIdx = LeftChildIdxOf(atIdx);
  34.             var rightChildIdx = RightChildIdxOf(atIdx);
  35.             var selectedIdx = atIdx;
  36.             var listSize = list.Count;
  37.  
  38.             if (leftChildIdx < listSize && comparer(list[atIdx], list[leftChildIdx]))
  39.                 selectedIdx = leftChildIdx;
  40.  
  41.             if (rightChildIdx < listSize && comparer(list[atIdx], list[rightChildIdx]))
  42.                 selectedIdx = rightChildIdx;
  43.  
  44.  
  45.             if (selectedIdx != atIdx)
  46.             {
  47.                 var temp = list[selectedIdx];
  48.                 list[selectedIdx] = list[atIdx];
  49.                 list[atIdx] = temp;
  50.                 ensureHeap(selectedIdx);
  51.             }
  52.         }
  53.  
  54.         private PriorityQueue() { }
  55.  
  56.         public int Count
  57.         {
  58.             get
  59.             {
  60.                 rwLock.EnterReadLock();
  61.                 var cnt = list.Count;
  62.                 rwLock.ExitReadLock();
  63.                 return cnt;
  64.             }
  65.         }
  66.  
  67.  
  68.  
  69.         public PriorityQueue(Comparer<T> comparer)
  70.         {
  71.             if (comparer == null)
  72.                 throw new ArgumentNullException();
  73.  
  74.             this.comparer = comparer;
  75.         }
  76.  
  77.         public T Peek()
  78.         {
  79.             T item = null;
  80.             rwLock.EnterReadLock();
  81.  
  82.             if (list.Count > 0)
  83.                 item = list[0];
  84.  
  85.             this.rwLock.ExitReadLock();
  86.  
  87.             return item;
  88.         }
  89.  
  90.         public void Enqueue(T item)
  91.         {
  92.             if (item == null)
  93.                 throw new ArgumentNullException();
  94.  
  95.             rwLock.EnterWriteLock();
  96.             list.Add(item);
  97.             var at = list.Count - 1;
  98.             while (at != 0 && comparer(list[ParentIdxOf(at)], list[at]))
  99.             {
  100.                 var temp = list[ParentIdxOf(at)];
  101.                 list[ParentIdxOf(at)] = list[at];
  102.                 list[at] = temp;
  103.                 at = ParentIdxOf(at);
  104.             }
  105.  
  106.             rwLock.ExitWriteLock();
  107.         }
  108.  
  109.         public T Dequeue()
  110.         {
  111.             T item = null;
  112.             rwLock.EnterWriteLock();
  113.  
  114.             if (list.Count > 0)
  115.             {
  116.                 item = list[0];
  117.                 list[0] = list[this.list.Count - 1];
  118.                 list.RemoveAt(list.Count - 1);
  119.                 ensureHeap(0);
  120.             }
  121.  
  122.             rwLock.ExitWriteLock();
  123.             return item;
  124.         }
  125.     }
  126. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top