Re-structuring Project + scheduling updates

This is a big one--probably should have split it apart, but I'm feeling
lazy this morning.

* Organized the mess of header files in include/framework by splitting
them out into their own subdirectories, and renaming a few files to
remove redundancies introduced by the directory structure.

* Introduced a new framework/ShardRequirements.h header file for simpler
shard development. This header simply contains the necessary includes
from framework/* for creating shard files. This should help to remove
structural dependencies from the framework file structure and shards,
as well as centralizing the necessary framework files to make shard
development easier.

* Created a (currently dummy) SchedulerInterface, and make the scheduler
implementation a template parameter of the dynamic extension for easier
testing of various scheduling policies. There's still more work to be
done to fully integrate the scheduler (queries, multiple buffers), but
some more of the necessary framework code for this has been added as well.

* Adjusted the Task interface setup for the scheduler. The task structures
have been removed from ExtensionStructure and placed in their own header
file. Additionally, I started experimenting with using std::variant,
as opposed to inheritence, to implement subtype polymorphism on the
Merge and Query tasks. The scheduler now has a general task queue that
contains both, and std::variant, std::visit, and std::get are used to
manipulate them without virtual functions.

* Removed Alex.h, as it can't build anyway. There's a branch out there
containing the Alex implementation stripped of the C++20 stuff. So
there's no need to keep it here.

4 files changed, 306 insertions, 0 deletions

diff --git a/include/framework/interface/Query.h b/include/framework/interface/Query.h
new file mode 100644
index 0000000..46a1ce1
--- /dev/null
+++ b/include/framework/interface/Query.h
@@ -0,0 +1,35 @@
+/*
+ * include/framework/QueryInterface.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <vector>
+#include <concepts>
+#include "util/types.h"
+
+template <typename Q>
+concept QueryInterface = requires(Q q, void *p, std::vector<void*> &s) {
+
+/*
+    {q.get_query_state(p, p)} -> std::convertible_to<void*>;
+    {q.get_buffer_query_state(p, p)};
+    {q.query(p, p)};
+    {q.buffer_query(p, p)};
+    {q.merge()};
+    {q.delete_query_state(p)};
+*/
+    {Q::EARLY_ABORT} -> std::convertible_to<bool>;
+    {Q::SKIP_DELETE_FILTER} -> std::convertible_to<bool>;
+    //{Q::get_query_state(p, p)} -> std::convertible_to<void*>;
+    //{Q::get_buffer_query_state(p, p)} -> std::convertible_to<void*>;
+    {Q::process_query_states(p, s, p)};
+
+    {Q::delete_query_state(std::declval<void*>())} -> std::same_as<void>;
+    {Q::delete_buffer_query_state(p)};
+
+};
diff --git a/include/framework/interface/Record.h b/include/framework/interface/Record.h
new file mode 100644
index 0000000..1ef1984
--- /dev/null
+++ b/include/framework/interface/Record.h
@@ -0,0 +1,214 @@
+/*
+ * include/framework/RecordInterface.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 <cstring>
+#include <concepts>
+#include <cmath>
+
+#include "psu-util/hash.h"
+
+namespace de {
+
+template<typename R>
+concept RecordInterface = requires(R r, R s) {
+    { r < s } ->std::convertible_to<bool>;
+    { r == s } ->std::convertible_to<bool>;
+};
+
+template<typename R>
+concept WeightedRecordInterface = requires(R r) {
+    {r.weight} -> std::convertible_to<double>;
+};
+
+template<typename R>
+concept NDRecordInterface = RecordInterface<R> && requires(R r, R s) {
+    {r.calc_distance(s)} -> std::convertible_to<double>;
+};
+
+template <typename R>
+concept KVPInterface = RecordInterface<R> && requires(R r) {
+    r.key;
+    r.value;
+};
+
+template<typename R>
+concept AlexInterface = KVPInterface<R> && requires(R r) {
+    {r.key} -> std::convertible_to<size_t>;
+    {r.value} -> std::convertible_to<size_t>;
+};
+
+template<typename R>
+concept WrappedInterface = RecordInterface<R> && requires(R r, R s, bool b) {
+    {r.header} -> std::convertible_to<uint32_t>;
+     r.rec;
+    {r.set_delete()};
+    {r.is_deleted()} -> std::convertible_to<bool>;
+    {r.set_tombstone(b)};
+    {r.is_tombstone()} -> std::convertible_to<bool>;
+    {r < s} -> std::convertible_to<bool>;
+    {r == s} ->std::convertible_to<bool>;
+};
+
+template<RecordInterface R>
+struct Wrapped {
+    uint32_t header;
+    R rec;
+
+    inline void set_delete() {
+        header |= 2;
+    }
+
+    inline bool is_deleted() const {
+        return header & 2;
+    }
+
+    inline void set_tombstone(bool val=true) {
+        if (val) {
+            header |= val;
+        } else {
+            header &= 0;
+        }
+    }
+
+    inline bool is_tombstone() const {
+        return header & 1;
+    }
+
+    inline bool operator<(const Wrapped& other) const {
+        return rec < other.rec || (rec == other.rec && header < other.header);
+    }
+
+    inline bool operator==(const Wrapped& other) const {
+        return rec == other.rec;
+    }
+
+};
+
+template <typename K, typename V>
+struct Record {
+    K key;
+    V value;
+    uint32_t header = 0;
+
+       inline bool operator<(const Record& other) const {
+        return key < other.key || (key == other.key && value < other.value);
+    }
+
+    inline bool operator==(const Record& other) const {
+        return key == other.key && value == other.value;
+    }
+};
+
+template <typename K, typename V, typename W>
+struct WeightedRecord {
+    K key;
+    V value;
+    W weight = 1;
+
+    inline bool operator==(const WeightedRecord& other) const {
+        return key == other.key && value == other.value;
+    }
+
+   inline bool operator<(const WeightedRecord& other) const {
+        return key < other.key || (key == other.key && value < other.value);
+    }
+};
+
+
+template <typename V, size_t D=2>
+struct CosinePoint{
+    V data[D];
+
+    inline bool operator==(const CosinePoint& other) const {
+        for (size_t i=0; i<D; i++) {
+            if (data[i] != other.data[i]) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    // lexicographic order
+    inline bool operator<(const CosinePoint& other) const {
+        for (size_t i=0; i<D; i++) {
+            if (data[i] < other.data[i]) {
+                return true;
+            } else if (data[i] > other.data[i]) {
+                return false;
+            }
+        }
+
+        return false;
+    }
+
+    inline double calc_distance(const CosinePoint& other) const {
+
+        double prod = 0;
+        double asquared = 0;
+        double bsquared = 0;
+
+        for (size_t i=0; i<D; i++) {
+            prod += data[i] * other.data[i];
+            asquared += data[i]*data[i];
+            bsquared += other.data[i]*other.data[i];
+        }
+
+        return prod / std::sqrt(asquared * bsquared);
+    }
+};
+
+
+template <typename V, size_t D=2>
+struct EuclidPoint{
+    V data[D];
+
+    inline bool operator==(const EuclidPoint& other) const {
+        for (size_t i=0; i<D; i++) {
+            if (data[i] != other.data[i]) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    // lexicographic order
+    inline bool operator<(const EuclidPoint& other) const {
+        for (size_t i=0; i<D; i++) {
+            if (data[i] < other.data[i]) {
+                return true;
+            } else if (data[i] > other.data[i]) {
+                return false;
+            }
+        }
+
+        return false;
+    }
+
+    inline double calc_distance(const EuclidPoint& other) const {
+        double dist = 0;
+        for (size_t i=0; i<D; i++) {
+            dist += (data[i] - other.data[i]) * (data[i] - other.data[i]);
+        }
+        
+        return std::sqrt(dist);
+    }
+};
+
+template<RecordInterface R>
+struct RecordHash {
+    size_t operator()(R const &rec) const {
+        return psudb::hash_bytes((std::byte *) &rec, sizeof(R));
+    }
+};
+
+}
diff --git a/include/framework/interface/Scheduler.h b/include/framework/interface/Scheduler.h
new file mode 100644
index 0000000..1445e90
--- /dev/null
+++ b/include/framework/interface/Scheduler.h
@@ -0,0 +1,31 @@
+/*
+ * include/framework/QueryInterface.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <vector>
+#include <concepts>
+#include "framework/interface/Record.h"
+#include "util/types.h"
+
+template <typename S>
+concept SchedulerInterface = requires(S s, size_t i, void *vp) {
+    {S(i, i)};
+//    {s.schedule_merge(vp, vp)};
+    
+/*
+    {q.get_query_state(p, p)} -> std::convertible_to<void*>;
+    {q.get_buffer_query_state(p, p)};
+    {q.query(p, p)};
+    {q.buffer_query(p, p)};
+    {q.merge()};
+    {q.delete_query_state(p)};
+*/
+    //{Q::get_query_state(p, p)} -> std::convertible_to<void*>;
+    //{Q::get_buffer_query_state(p, p)} -> std::convertible_to<void*>;
+};
diff --git a/include/framework/interface/Shard.h b/include/framework/interface/Shard.h
new file mode 100644
index 0000000..ea58b2a
--- /dev/null
+++ b/include/framework/interface/Shard.h
@@ -0,0 +1,26 @@
+/*
+ * include/framework/ShardInterface.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <concepts>
+
+#include "util/types.h"
+#include "framework/interface/Record.h"
+
+namespace de {
+
+//template <template<typename> typename S, typename R>
+template <typename S>
+concept ShardInterface = requires(S s, void *p, bool b) {
+    //{s.point_lookup(r, b) } -> std::same_as<R*>;
+    {s.get_record_count()} -> std::convertible_to<size_t>;
+    {s.get_memory_usage()} -> std::convertible_to<size_t>;
+};
+
+}