From 076e104b8672924c3d80cd1da2fdb5ebee1766ac Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Thu, 24 Aug 2023 17:00:31 -0400
Subject: Migrated over to using psudb-common utilities/headers

---
 include/ds/PriorityQueue.h | 162 ---------------------------------------------
 1 file changed, 162 deletions(-)
 delete mode 100644 include/ds/PriorityQueue.h

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

diff --git a/include/ds/PriorityQueue.h b/include/ds/PriorityQueue.h
deleted file mode 100644
index 4612eef..0000000
--- a/include/ds/PriorityQueue.h
+++ /dev/null
@@ -1,162 +0,0 @@
-/*
- * include/ds/BloomFilter.h
- *
- * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
- *                    Dong Xie <dongx@psu.edu>
- *
- * All rights reserved. Published under the Modified BSD License.
- *
- */
-#pragma once
-
-#include <vector>
-#include <cassert>
-
-namespace de {
-
-template <typename R>
-struct queue_record {
-    const R *data;
-    size_t version;
-};
-
-template <typename R>
-class standard_minheap {
-public:
-    standard_minheap(R *baseline) {}
-    inline bool operator()(const R* a, const R* b) {
-        return *a < *b;
-    }
-};
-
-template <typename R>
-class standard_maxheap {
-public:
-    standard_maxheap(R *baseline) {}
-    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, R* cmp_baseline=nullptr) : data(size), tail(0), cmp(cmp_baseline) {}
-
-    ~PriorityQueue() = default;
-
-    size_t size() const {
-        return tail;
-    }
-
-    void pop() {
-        assert(this->tail != 0);
-
-        // If there is only one element, just decrement the
-        // tail.
-        if (this->size() == 1) {
-            this->tail--;
-            return;
-        }
-
-        swap(0, --this->tail);
-
-        ssize_t idx = 0;
-        ssize_t child_idx;
-
-        while ((child_idx = min_child(idx)) != -1 && heap_cmp(child_idx, idx)) {
-            swap(idx, child_idx);
-            idx = child_idx;
-        }
-    }
-
-    void push(const R* record, size_t version=0) {
-        assert(tail != this->data.size());
-
-        size_t new_idx = this->tail++;
-        this->data[new_idx] = {record, version};
-
-        while (new_idx != 0 && !heap_cmp(parent(new_idx), new_idx)) {
-            swap(parent(new_idx), new_idx);
-            new_idx = parent(new_idx);
-        }
-    }
-
-
-    queue_record<R> peek(size_t depth=0) {
-        ssize_t idx = 0;
-        size_t cur_depth = 0;
-
-        while (cur_depth != depth) {
-            idx = min_child(idx);
-            assert(idx != -1);
-            cur_depth++;
-        }
-
-        return this->data[idx];
-    }
-
-private:
-    std::vector<queue_record<R>> data;
-    CMP cmp;
-    size_t tail;
-    R *baseline;
-
-    /*
-     * Swap the elements at position a and position
-     * b within the heap
-     */
-    inline void swap(size_t a, size_t b) {
-        if (a == b) return;
-
-        queue_record temp = this->data[a];
-        this->data[a] = this->data[b];
-        this->data[b] = temp;
-    }
-
-    inline size_t left_child(size_t idx) {
-        return 2 * idx + 1;
-    }
-
-    inline size_t right_child(size_t idx) {
-        return 2 * idx + 2;
-    }
-
-    inline size_t parent(size_t idx) {
-        return (idx - 1) / 2;
-    }
-
-    inline ssize_t min_child(size_t idx) {
-        ssize_t left = left_child(idx) < tail ? left_child(idx) : -1;
-        ssize_t right = right_child(idx) < tail ? right_child(idx) : -1;
-
-        if (left == -1 && right == -1) {
-            return -1;
-        } else if (left == -1) {
-            return right;
-        } else  if (right == -1) {
-            return left;
-        }
-
-        return (heap_cmp(left, right)) ? left : right;
-    }
-
-    inline bool heap_cmp(size_t a, size_t b) {
-        if (data[a].data != data[b].data) {
-            return cmp(data[a].data, data[b].data);
-        } else if (data[a].version != data[b].version) {
-            return data[a].version < data[b].version;
-        }
-
-        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