From 72bdba182d24ec8fd93d1d2b9bbe54aa57ff0e5d Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Mon, 17 Jul 2023 16:05:04 -0400
Subject: PriorityQueue: generalized priority queue comparison operation

Generalized the comparison used for the priority queue to enable its use
within the KNN query code.
---
 include/ds/PriorityQueue.h | 34 ++++++++++++++++++++++++++++++----
 1 file changed, 30 insertions(+), 4 deletions(-)

(limited to 'include/ds/PriorityQueue.h')

diff --git a/include/ds/PriorityQueue.h b/include/ds/PriorityQueue.h
index a1bfd0a..a8e9ba5 100644
--- a/include/ds/PriorityQueue.h
+++ b/include/ds/PriorityQueue.h
@@ -21,6 +21,22 @@ struct queue_record {
 };
 
 template <typename R>
+class standard_minheap {
+public:
+    inline bool operator()(const R* a, const R* b) {
+        return *a < *b;
+    }
+};
+
+template <typename R>
+class standard_maxheap {
+public:
+    inline bool operator()(const R* a, const R* b) {
+        return *a > *b;
+    }
+};
+
+template <typename R, typename CMP=standard_minheap<R>>
 class PriorityQueue {
 public:
     PriorityQueue(size_t size) : data(size), tail(0) {}
@@ -79,6 +95,7 @@ public:
 
 private:
     std::vector<queue_record<R>> data;
+    CMP cmp;
     size_t tail;
 
     /*
@@ -122,11 +139,20 @@ private:
 
     inline bool heap_cmp(size_t a, size_t b) {
         if (data[a].data != data[b].data) {
-            return *(data[a].data) < *(data[b].data);
-        } else if (data[a].version != data[b].version)
+            return cmp(data[a].data, data[b].data);
+        } else if (data[a].version != data[b].version) {
             return data[a].version < data[b].version;
-        else return data[a].data->is_tombstone() && data[b].data->is_tombstone();
-    }
+        }
 
+        constexpr bool has_tombstone = requires(const R &r) {
+            r.is_tombstone();
+        };
+
+        if constexpr (has_tombstone) {
+            return data[a].data->is_tombstone() && data[b].data->is_tombstone();
+        } else {
+            return false;
+        }
+    }
 };
 }
-- 
cgit v1.2.3