using System;

using System.Collections.Concurrent;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using FluentAssertions;

​

public class Program

{

    public static void Main()

    {

        // This test fails:

        EnqueueAndTryDequeue_ConcurrentAccess_Successful();

        // Other simple tests that always pass:

        EnqueueAndTryDequeue_SingleElement_Successful();

        TryDequeue_EmptyQueue_ReturnsFalse();

        EnqueueAndTryDequeue_MultipleElementsInOrder_Successful();

        EnqueueAndTryDequeue_MultipleElementsInReverseOrder_Successful();

    }

​

    /// <summary>

    /// Implementation of PriorityQueue that has the following characteristics:

    ///     - The priority is defined so that high number = high priority

    ///     - The dequeue order within the same priority level is consistent, always FIFO.

    ///     - It's thread-safe.

    /// In this, it is different from the PriorityQueue introduced in .NET6.

    /// </summary>

    public class ConcurrentPriorityQueue<TElement, TPriority> where TPriority : IComparable<TPriority>

    {

        public ConcurrentDictionary<TPriority, ConcurrentQueue<TElement>> Queues { get; private set; } = new();

​

        public bool IsEmpty { get { return !Queues.Any(q => q.Value.Any()); } }

​

        public void Enqueue(TElement element, TPriority priority)

        {

            if (!Queues.TryGetValue(priority, out var queue))

            {

                queue = new();

                Queues[priority] = queue;

            }

​

            queue.Enqueue(element);

        }

​

        public bool TryDequeue(out TElement? element, out TPriority? priority)

        {

            if (IsEmpty)

            {

                element = default(TElement);

                priority = default(TPriority);

                return false;

            }

​

            var highestPriority = Queues.Keys.Max();

            var highestPriorityQueue = Queues[highestPriority];

​

            highestPriorityQueue.TryDequeue(out element);

            if (!highestPriorityQueue.Any())

                Queues.Remove(highestPriority, out _);

​

            priority = highestPriority;

            return true;

        }

​

        public TElement Dequeue()

        {

            if (IsEmpty)

                throw new InvalidOperationException("PriorityQueue is empty.");

​

            TryDequeue(out var element, out _);

            return element;

        }

​

        public TElement Peek()

        {

            if (IsEmpty)

                throw new InvalidOperationException("PriorityQueue is empty.");

​

            var highestPriority = Queues.Keys.Max();

            Queues[highestPriority].TryPeek(out var peeked);

            return peeked;

        }

​

        public TElement? TryPeek()

        {

            if (IsEmpty)

                return default;

​

            return Peek();

        }

​

        public int Count()

        {

            return Queues.Sum(q => q.Value.Count);

        }

    }

    //********************************************************************//

    // TESTS

    //********************************************************************//

​

    public static void EnqueueAndTryDequeue_SingleElement_Successful()

    {

        var queue = new ConcurrentPriorityQueue<int, int>();

        queue.Enqueue(1, 10);

​

        queue.TryDequeue(out var element, out var priority);

​

        element.Should().Be(1);

        priority.Should().Be(10);

    }

    //********************************************************************//

​

    public static void TryDequeue_EmptyQueue_ReturnsFalse()

    {

        var queue = new ConcurrentPriorityQueue<int, int>();

​

        var result = queue.TryDequeue(out _, out _);

​

        result.Should().BeFalse();

    }

​

    //********************************************************************//

​

    public static void EnqueueAndTryDequeue_MultipleElementsInOrder_Successful()

    {

        var queue = new ConcurrentPriorityQueue<int, int>();

​

        queue.Enqueue(1, 30);

        queue.Enqueue(2, 20);

        queue.Enqueue(3, 40);

​

        queue.TryDequeue(out var element1, out var priority1);

        queue.TryDequeue(out var element2, out var priority2);

        queue.TryDequeue(out var element3, out var priority3);

​

        element1.Should().Be(3);

        priority1.Should().Be(40);

​

        element2.Should().Be(1);

        priority2.Should().Be(30);

​

        element3.Should().Be(2);

        priority3.Should().Be(20);

    }

    //********************************************************************//

​

    public static void EnqueueAndTryDequeue_MultipleElementsInReverseOrder_Successful()

    {

        var queue = new ConcurrentPriorityQueue<int, int>();

​

        queue.Enqueue(1, 30);

        queue.Enqueue(2, 20);

        queue.Enqueue(3, 40);

​

        queue.TryDequeue(out var element3, out var priority3);

        queue.TryDequeue(out var element2, out var priority2);

        queue.TryDequeue(out var element1, out var priority1);

​

        element3.Should().Be(3);

        priority3.Should().Be(40);

​

        element2.Should().Be(1);

        priority2.Should().Be(30);

​

        element1.Should().Be(2);

        priority1.Should().Be(20);

    }

    //********************************************************************//

​

    public static void EnqueueAndTryDequeue_ConcurrentAccess_Successful()

    {

        var queue = new ConcurrentPriorityQueue<int, int>();

        int numElements = 100;

        int numThreads = 10;

​

        var tasks = new List<Task>();

​

        // Enqueue tasks

        for (int i = 0; i < numThreads; i++)

        {

            tasks.Add(Task.Run(() =>

                               {

                                   for (int j = 0; j < numElements; j++)

                                   {

                                       queue.Enqueue(j, j);

                                   }

                               }));

        }

​

        // Dequeue tasks

        for (int i = 0; i < numThreads; i++)

        {

            tasks.Add(Task.Run(() =>

                               {

                                   for (int j = 0; j < numElements; j++)

                                   {

                                       if (queue.TryDequeue(out var element, out var priority))

                                       {

                                           // Do something with dequeued element

                                       }

                                   }

                               }));

        }

​

        Task.WhenAll(tasks).Wait();

​

        queue.Count().Should().Be(0);

    }

}