Add TPriorityQueue::PopValue

ce37597283b1508bdba021056c149fe16feb1c69

2 files changed, 45 insertions, 1 deletions

diff --git a/util/generic/queue.h b/util/generic/queue.h
index 012ac80082..ade2c07544 100644
--- a/util/generic/queue.h
+++ b/util/generic/queue.h
@@ -48,6 +48,14 @@ public:
         this->c.clear();
     }
 
+    inline T PopValue() {
+        Y_ASSERT(!this->empty());
+        std::pop_heap(Container().begin(), Container().end(), this->comp);
+        T value = std::move(Container().back());
+        this->c.pop_back();
+        return value;
+    }
+
     inline S& Container() Y_LIFETIME_BOUND {
         return this->c;
     }
diff --git a/util/generic/queue_ut.cpp b/util/generic/queue_ut.cpp
index a33399e104..43ba89559a 100644
--- a/util/generic/queue_ut.cpp
+++ b/util/generic/queue_ut.cpp
@@ -1,6 +1,7 @@
 #include "queue.h"
+#include "deque.h"
 #include "list.h"
-#include "vector.h"
+#include "ptr.h"
 
 #include <library/cpp/testing/unittest/registar.h>
 
@@ -152,6 +153,41 @@ Y_UNIT_TEST_SUITE(TYQueueTest) {
         UNIT_ASSERT(q.empty());
     }
 
+    struct THolderWithPriority {
+        THolderWithPriority(const TString& value, int priority)
+            : Value(MakeHolder<TString>(value))
+            , Priority(priority)
+        {
+        }
+
+        THolder<TString> Value; // THolder to test move-ctor
+        int Priority;
+
+        std::weak_ordering operator<=>(const THolderWithPriority& other) const noexcept {
+            return Priority <=> other.Priority;
+        }
+    };
+
+    Y_UNIT_TEST(pqueue5) {
+        // Test move-and-pop
+        TPriorityQueue<THolderWithPriority> q;
+
+        UNIT_ASSERT(q.empty());
+        q.emplace("min", 1);
+        q.emplace("max", 3);
+        q.emplace("middle", 2);
+
+        auto value = q.PopValue().Value;
+        UNIT_ASSERT(*value == "max");
+
+        value = q.PopValue().Value;
+        UNIT_ASSERT(*value == "middle");
+
+        value = q.PopValue().Value;
+        UNIT_ASSERT(*value == "min");
+        UNIT_ASSERT(q.empty());
+    }
+
     Y_UNIT_TEST(queue1) {
         TQueue<int, TList<int>> q;