Issue #75070 - Add PriorityQueue DequeueEnqueue Method (#75993)

* Issue #75070 - Add a DequeueEnqueue method to the System.Collections.Generic.PriorityQueue public api and unit test cases for the new method

* Issue #75070 - Remove unnecessary PriorityQueue DequeueEnqueue property test case and update DequeueEnqueue test assertion and xunit attribute

* Item #75070 - Revert the unnecessary name changes to the PriorityQueue.PropertyTests.cs test case method names

4 files changed, 121 insertions, 1 deletions

diff --git a/src/libraries/System.Collections/ref/System.Collections.cs b/src/libraries/System.Collections/ref/System.Collections.cs
index 755cabad174..d841eddec8b 100644
--- a/src/libraries/System.Collections/ref/System.Collections.cs
+++ b/src/libraries/System.Collections/ref/System.Collections.cs
@@ -113,6 +113,7 @@ namespace System.Collections.Generic
         public System.Collections.Generic.PriorityQueue<TElement, TPriority>.UnorderedItemsCollection UnorderedItems { get { throw null; } }
         public void Clear() { }
         public TElement Dequeue() { throw null; }
+        public TElement DequeueEnqueue(TElement element, TPriority priority) { throw null; }
         public void Enqueue(TElement element, TPriority priority) { }
         public TElement EnqueueDequeue(TElement element, TPriority priority) { throw null; }
         public void EnqueueRange(System.Collections.Generic.IEnumerable<(TElement Element, TPriority Priority)> items) { }
diff --git a/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs b/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs
index e76dc3c8374..ede54d42b46 100644
--- a/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs
+++ b/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs
@@ -251,6 +251,54 @@ namespace System.Collections.Generic
         }
 
         /// <summary>
+        ///  Removes the minimal element and then immediately adds the specified element with associated priority to the <see cref="PriorityQueue{TElement, TPriority}"/>,
+        /// </summary>
+        /// <param name="element">The element to add to the <see cref="PriorityQueue{TElement, TPriority}"/>.</param>
+        /// <param name="priority">The priority with which to associate the new element.</param>
+        /// <exception cref="InvalidOperationException">The queue is empty.</exception>
+        /// <returns>The minimal element removed before performing the enqueue operation.</returns>
+        /// <remarks>
+        ///  Implements an extract-then-insert heap operation that is generally more efficient
+        ///  than sequencing Dequeue and Enqueue operations: in the worst case scenario only one
+        ///  shift-down operation is required.
+        /// </remarks>
+        public TElement DequeueEnqueue(TElement element, TPriority priority)
+        {
+            if (_size == 0)
+            {
+                throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue);
+            }
+
+            (TElement Element, TPriority Priority) root = _nodes[0];
+
+            if (_comparer == null)
+            {
+                if (Comparer<TPriority>.Default.Compare(priority, root.Priority) > 0)
+                {
+                    MoveDownDefaultComparer((element, priority), 0);
+                }
+                else
+                {
+                    _nodes[0] = (element, priority);
+                }
+            }
+            else
+            {
+                if (_comparer.Compare(priority, root.Priority) > 0)
+                {
+                    MoveDownCustomComparer((element, priority), 0);
+                }
+                else
+                {
+                    _nodes[0] = (element, priority);
+                }
+            }
+
+            _version++;
+            return root.Element;
+        }
+
+        /// <summary>
         ///  Removes the minimal element from the <see cref="PriorityQueue{TElement, TPriority}"/>,
         ///  and copies it to the <paramref name="element"/> parameter,
         ///  and its associated priority to the <paramref name="priority"/> parameter.
diff --git a/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Generic.Tests.cs b/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Generic.Tests.cs
index 72169ac22bd..555fee2ba7d 100644
--- a/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Generic.Tests.cs
+++ b/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Generic.Tests.cs
@@ -93,7 +93,7 @@ namespace System.Collections.Tests
 
         #endregion
 
-        #region Enqueue, Dequeue, Peek, EnqueueDequeue
+        #region Enqueue, Dequeue, Peek, EnqueueDequeue, DequeueEnqueue
 
         [Theory]
         [MemberData(nameof(ValidCollectionSizes))]
@@ -197,6 +197,28 @@ namespace System.Collections.Tests
             AssertExtensions.CollectionEqual(expectedItems, queue.UnorderedItems, EqualityComparer<(TElement, TPriority)>.Default);
         }
 
+        [Theory]
+        [MemberData(nameof(ValidCollectionSizes))]
+        public void PriorityQueue_DequeueEnqueue(int count)
+        {
+            (TElement Element, TPriority Priority)[] itemsToEnqueue = CreateItems(count * 2).ToArray();
+            PriorityQueue<TElement, TPriority> queue = CreateEmptyPriorityQueue();
+            queue.EnqueueRange(itemsToEnqueue.Take(count));
+
+            var dequeuedItems = new List<(TElement Element, TPriority Priority)>();
+            foreach ((TElement element, TPriority priority) in itemsToEnqueue.Skip(count))
+            {
+                queue.TryPeek(out var dequeuedElement, out var dequeuedPriority);
+                dequeuedItems.Add((dequeuedElement, dequeuedPriority));
+                queue.DequeueEnqueue(element, priority);
+            }
+
+            Assert.Equal(dequeuedItems.Count, count);
+
+            IEnumerable<(TElement Element, TPriority Priority)> expectedItems = itemsToEnqueue.Where(item => !dequeuedItems.Contains(item, EqualityComparer<(TElement, TPriority)>.Default));
+            AssertExtensions.CollectionEqual(expectedItems, queue.UnorderedItems, EqualityComparer<(TElement, TPriority)>.Default);
+        }
+
         #endregion
 
         #region Clear
diff --git a/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Tests.cs b/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Tests.cs
index 12472626c7f..c7de89b2862 100644
--- a/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Tests.cs
+++ b/src/libraries/System.Collections/tests/Generic/PriorityQueue/PriorityQueue.Tests.cs
@@ -79,6 +79,55 @@ namespace System.Collections.Tests
         }
 
         [Fact]
+        public void PriorityQueue_EmptyCollection_DequeueEnqueue_ShouldThrowInvalidOperationException()
+        {
+            var queue = new PriorityQueue<int, int>();
+
+            Assert.Equal(0, queue.Count);
+            Assert.Throws<InvalidOperationException>(() => queue.DequeueEnqueue(1, 1));
+            Assert.Equal(0, queue.Count);
+        }
+
+        [Fact]
+        public void PriorityQueue_Generic_DequeueEnqueue_SmallerThanMin()
+        {
+            PriorityQueue<string, int> queue = CreateSmallPriorityQueue(out HashSet<(string, int)> enqueuedItems);
+
+            string actualElement = queue.DequeueEnqueue("zero", 0);
+
+            Assert.Equal("one", actualElement);
+            Assert.Equal("zero", queue.Dequeue());
+            Assert.Equal("two", queue.Dequeue());
+            Assert.Equal("three", queue.Dequeue());
+        }
+
+        [Fact]
+        public void PriorityQueue_Generic_DequeueEnqueue_LargerThanMin()
+        {
+            PriorityQueue<string, int> queue = CreateSmallPriorityQueue(out HashSet<(string, int)> enqueuedItems);
+
+            string actualElement = queue.DequeueEnqueue("four", 4);
+
+            Assert.Equal("one", actualElement);
+            Assert.Equal("two", queue.Dequeue());
+            Assert.Equal("three", queue.Dequeue());
+            Assert.Equal("four", queue.Dequeue());
+        }
+
+        [Fact]
+        public void PriorityQueue_Generic_DequeueEnqueue_EqualToMin()
+        {
+            PriorityQueue<string, int> queue = CreateSmallPriorityQueue(out HashSet<(string, int)> enqueuedItems);
+
+            string actualElement = queue.DequeueEnqueue("one-to-replace", 1);
+
+            Assert.Equal("one", actualElement);
+            Assert.Equal("one-to-replace", queue.Dequeue());
+            Assert.Equal("two", queue.Dequeue());
+            Assert.Equal("three", queue.Dequeue());
+        }
+
+        [Fact]
         public void PriorityQueue_Generic_Constructor_IEnumerable_Null()
         {
             (string, int)[] itemsToEnqueue = new(string, int)[] { (null, 0), ("one", 1) } ;