123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205 |
- using System;
- using System.Collections.Generic;
- using System.Diagnostics;
- using System.Threading;
- namespace MatrixIO.Collections
- {
-
-
-
- public class ConcurrentPriorityQueue<TPriority, TItem> : IEnumerable<TItem>
- {
- #region Private Members
- private readonly object _syncRoot = new object();
- private readonly IComparer<TPriority> _comparer;
- private readonly int _maxLevel;
- private readonly double _bias;
- private int _level;
- private readonly Node _head;
- private readonly Node _foot;
- private readonly Random _random = new Random();
- private volatile int _count;
-
- private readonly AutoResetEvent _itemReady = new AutoResetEvent(false);
- #endregion
- public int Count { get { return _count; } }
- public bool IsEmpty { get { return _count <= 0; } }
- public bool IsSynchronized { get { return true; } }
- public object SyncRoot { get { return _syncRoot; } }
- #region Constructors
- public ConcurrentPriorityQueue() : this(Comparer<TPriority>.Default) { }
- public ConcurrentPriorityQueue(int maxLevel) : this(Comparer<TPriority>.Default, maxLevel) { }
- public ConcurrentPriorityQueue(int maxLevel, double bias) : this(Comparer<TPriority>.Default, maxLevel, bias) { }
- public ConcurrentPriorityQueue(IComparer<TPriority> keyComparer) : this(keyComparer, 32) { }
- public ConcurrentPriorityQueue(IComparer<TPriority> keyComparer, int maxLevel) : this(keyComparer, maxLevel, 0.5D) { }
- public ConcurrentPriorityQueue(IComparer<TPriority> keyComparer, int maxLevel, double bias)
- {
- _comparer = keyComparer;
- _maxLevel = maxLevel;
- _bias = bias;
- _head = new Node(_maxLevel);
- _foot = new Node(0);
- for (var i = 0; i < _head.Forward.Length; i++) _head.Forward[i] = _foot;
- }
- #endregion
- public void Enqueue(TPriority priority, TItem value)
- {
- lock (_syncRoot)
- {
- var update = new Node[_level+1];
- var x = _head;
-
- for (var i = _level; i >= 0; i--)
- {
- while (x.Forward[i] != _foot && _comparer.Compare(x.Forward[i].Key, priority) < 1)
- x = x.Forward[i];
-
- update[i] = x;
- }
- x = x.Forward[0];
-
- var level = 1;
- while (_random.NextDouble() < _bias && level < _maxLevel && level <= _level) level++;
- if (level > _level)
- {
- for (var i = _level + 1; i < level; i++)
- update[i] = _head;
- _level = level;
- }
-
- x = new Node(level, priority, value);
-
- for (var i = 0; i < level; i++)
- {
- x.Forward[i] = update[i].Forward[i];
- update[i].Forward[i] = x;
- }
- _count++;
- }
- _itemReady.Set();
- }
- public bool TryDequeue(out TItem item)
- {
- lock (_syncRoot)
- {
- if (!_head.Forward[0].Equals(_foot))
- {
- var x = _head.Forward[0];
- item = x.Item;
- for (var i = 0; i < x.Forward.Length; i++)
- _head.Forward[i] = x.Forward[i];
- _count--;
- if (_count <= 0) _itemReady.Reset();
- else _itemReady.Set();
- return true;
- }
- }
- item = default(TItem);
- return false;
- }
-
-
- public bool TryDequeue(out TItem item, TimeSpan timeout)
- {
- lock (_syncRoot)
- {
- if (_itemReady.WaitOne(timeout))
- if (TryDequeue(out item)) return true;
- else Debug.WriteLine("Failed to get item after wait of less than requested timeout.");
- }
- item = default(TItem);
- return false;
- }
- public bool TryPeek(out TItem item)
- {
- lock (_syncRoot)
- {
- if(_head.Forward[0] != _foot)
- {
- item = _head.Forward[0].Item;
- return true;
- }
- item = default(TItem);
- return false;
- }
- }
- public void CopyTo(TItem[] array, int arrayIndex)
- {
- var offset = arrayIndex;
- foreach(var value in this)
- array[offset++] = value;
- }
- public TItem[] ToArray()
- {
- lock(_syncRoot)
- {
- var items = new TItem[_count];
- CopyTo(items, 0);
- return items;
- }
- }
- #region IEnumerable Implementation
- public IEnumerator<TItem> GetEnumerator()
- {
- lock (_syncRoot)
- {
- var x = _head;
- while (!x.Forward[0].Equals(_foot))
- {
- yield return x.Forward[0].Item;
- x = x.Forward[0];
- }
- }
- }
- System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
- {
- return GetEnumerator();
- }
- #endregion
- #region Node Class
- private class Node
- {
- public readonly TPriority Key;
- public readonly TItem Item;
- public readonly Node[] Forward;
- public Node(int level)
- {
- Forward = new Node[level];
- }
- public Node(int level, TPriority key, TItem item) : this(level)
- {
- Key = key;
- Item = item;
- }
- }
- #endregion
- }
- }
|