source: branches/2205_OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.SurrogateModeling/3.3/LimitedPriorityQueue.cs @ 16654

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Encodings.RealVectorEncoding;

namespace HeuristicLab.Networks.IntegratedOptimization.SurrogateModeling {
  public class LimitedPriorityQueue : IEnumerable<Tuple<double, RealVector>> {
    public class AscendingPriorityComparer : IComparer<double> {
      public int Compare(double x, double y) {
        return x.CompareTo(y);
      }
    }

    public class DescendingPriorityComparer : IComparer<double> {
      public int Compare(double x, double y) {
        return y.CompareTo(x);
      }
    }

    private class LimitedPriorityQueueComparer : IComparer<Tuple<double, RealVector>> {
      private IComparer<double> comparer;
      public LimitedPriorityQueueComparer(IComparer<double> priorityComparer) {
        comparer = priorityComparer;
      }

      public int Compare(Tuple<double, RealVector> x, Tuple<double, RealVector> y) {
        return comparer.Compare(x.Item1, y.Item1);
      }
    }

    private readonly object locker = new object();
    private readonly List<Tuple<double, RealVector>> list = new List<Tuple<double, RealVector>>();
    private readonly HashSet<RealVector> hashes = new HashSet<RealVector>(new RealVectorEqualityComparer());

    private readonly LimitedPriorityQueueComparer comparer;
    private readonly SemaphoreSlim semaphore;
    private readonly int limit;
    private bool addingCompleted;

    public int Count {
      get { lock (locker) return list.Count; }
    }

    public bool IsAddingCompleted {
      get { lock (locker) return addingCompleted; }
    }

    public LimitedPriorityQueue(int maxCount, IComparer<double> priorityComparer) {
      limit = maxCount;
      comparer = new LimitedPriorityQueueComparer(priorityComparer);
      semaphore = new SemaphoreSlim(0, limit);
    }

    public bool Contains(RealVector value) {
      lock (locker) return hashes.Contains(value);

    }

    public void Enqueue(double priority, RealVector value) {
      lock (locker) {
        var tuple = Tuple.Create(priority, value);
        int index = list.BinarySearch(tuple, comparer);
        if (index < 0) index = ~index;

        if (list.Count == limit) {
          var lastIndex = limit - 1;
          var last = list[lastIndex];
          list.RemoveAt(lastIndex);
          hashes.Remove(last.Item2);
        }

        list.Insert(Math.Min(index, list.Count), tuple);
        hashes.Add(value);

        if (semaphore.CurrentCount < limit)
          semaphore.Release();
      }
    }

    public bool TryDequeue(out RealVector item) {
      if (semaphore.Wait(0)) {
        lock (locker) {
          if (list.Any()) {
            item = list[0].Item2;
            list.RemoveAt(0);
            hashes.Remove(item);
            return true;
          }
        }
      }

      item = default(RealVector);
      return false;
    }

    public Tuple<double, RealVector> LastOrDefault() {
      lock (locker) return list.LastOrDefault();
    }

    public void Clear() {
      lock (locker) {
        list.Clear();
        hashes.Clear();

        for (int i = 0; i < semaphore.CurrentCount; i++)
          semaphore.Wait();
      }
    }

    public void CompleteAdding() {
      lock (locker) addingCompleted = true;
    }

    public IEnumerator<Tuple<double, RealVector>> GetEnumerator() {
      return list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
      return ((IEnumerable)list).GetEnumerator();
    }
  }
}