From a86cb9330289f5fa1d957cce8b9a54c2de6d46fb Mon Sep 17 00:00:00 2001
From: Chris Mikkelson <cmikk@fsi.io>
Date: Fri, 3 May 2024 00:54:15 -0500
Subject: [PATCH] Seekable: relax Ord requirement on keys

This allows implementations to return Result<> types to propagate
errors. Those errors will need to be handled prior to merging
or coalescing.
---
 src/seekable.rs          |  4 +++-
 src/seekable/coalesce.rs |  2 ++
 src/seekable/merge.rs    | 51 +++++++++++++++++++++++++++++++---------
 3 files changed, 45 insertions(+), 12 deletions(-)

diff --git a/src/seekable.rs b/src/seekable.rs
index a5c9162..94aa316 100644
--- a/src/seekable.rs
+++ b/src/seekable.rs
@@ -8,7 +8,7 @@ use merge::Merger;
 pub use vec::SeekableVec;
 
 pub trait Seekable: Sized {
-    type Key: Ord;
+    type Key;
     type Value;
 
     fn next(&mut self) -> Option<(Self::Key, Self::Value)>;
@@ -24,6 +24,7 @@ pub trait Seekable: Sized {
     fn merge<L>(iter: L) -> Merger<Self>
     where
         L: Iterator<Item = Self>,
+        Self::Key: Ord,
     {
         merge::merge(iter)
     }
@@ -31,6 +32,7 @@ pub trait Seekable: Sized {
     fn coalesce<F>(self, cf: F) -> Coalesce<Self, F>
     where
         F: FnMut(&Self::Key, Self::Value, Self::Value) -> Self::Value,
+        Self::Key: PartialEq,
     {
         coalesce::coalesce(self, cf)
     }
diff --git a/src/seekable/coalesce.rs b/src/seekable/coalesce.rs
index 527b9c1..55c006d 100644
--- a/src/seekable/coalesce.rs
+++ b/src/seekable/coalesce.rs
@@ -26,6 +26,7 @@ where
 impl<S, F> IntoIterator for Coalesce<S, F>
 where
     S: Seekable,
+    S::Key: PartialEq,
     F: FnMut(&S::Key, S::Value, S::Value) -> S::Value,
 {
     type Item = (S::Key, S::Value);
@@ -38,6 +39,7 @@ where
 impl<S, F> Seekable for Coalesce<S, F>
 where
     S: Seekable,
+    S::Key: PartialEq,
     F: FnMut(&S::Key, S::Value, S::Value) -> S::Value,
 {
     type Key = S::Key;
diff --git a/src/seekable/merge.rs b/src/seekable/merge.rs
index fb9860a..adbcf14 100644
--- a/src/seekable/merge.rs
+++ b/src/seekable/merge.rs
@@ -6,18 +6,25 @@ use std::collections::BinaryHeap;
 pub struct Merger<S>
 where
     S: Seekable,
+    S::Key: Ord,
 {
     active: BinaryHeap<MergerEnt<S>>,
     ended: Vec<S>,
 }
 
-struct MergerEnt<S: Seekable> {
+struct MergerEnt<S: Seekable>
+where
+    S::Key: Ord,
+{
     cur_item: RefCell<(S::Key, S::Value)>,
     rest: S,
 }
 
-impl<S: Seekable> Eq for MergerEnt<S> {}
-impl<S: Seekable> PartialEq for MergerEnt<S> {
+impl<S: Seekable> Eq for MergerEnt<S> where S::Key: Ord {}
+impl<S: Seekable> PartialEq for MergerEnt<S>
+where
+    S::Key: Ord,
+{
     fn eq(&self, other: &Self) -> bool {
         let sent = self.cur_item.borrow();
         let oent = other.cur_item.borrow();
@@ -30,13 +37,19 @@ impl<S: Seekable> PartialEq for MergerEnt<S> {
 // for MergerEnt<S> vs. S::Key. We do this instead of using
 // std::cmp::Reverse to avoid the additional packing/unpacking
 // boilerplate.
-impl<S: Seekable> PartialOrd for MergerEnt<S> {
+impl<S: Seekable> PartialOrd for MergerEnt<S>
+where
+    S::Key: Ord,
+{
     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-	Some(self.cmp(other))
+        Some(self.cmp(other))
     }
 }
 
-impl<S: Seekable> Ord for MergerEnt<S> {
+impl<S: Seekable> Ord for MergerEnt<S>
+where
+    S::Key: Ord,
+{
     fn cmp(&self, other: &Self) -> Ordering {
         let sent = self.cur_item.borrow();
         let oent = other.cur_item.borrow();
@@ -44,7 +57,10 @@ impl<S: Seekable> Ord for MergerEnt<S> {
     }
 }
 
-impl<S: Seekable> MergerEnt<S> {
+impl<S: Seekable> MergerEnt<S>
+where
+    S::Key: Ord,
+{
     fn new(mut source: S) -> Option<MergerEnt<S>> {
         Some(MergerEnt {
             cur_item: RefCell::new(source.next()?),
@@ -61,6 +77,7 @@ pub fn merge<L, S>(sources: L) -> Merger<S>
 where
     L: Iterator<Item = S>,
     S: Seekable,
+    S::Key: Ord,
 {
     Merger {
         active: BinaryHeap::from(
@@ -73,7 +90,10 @@ where
     }
 }
 
-impl<S: Seekable> IntoIterator for Merger<S> {
+impl<S: Seekable> IntoIterator for Merger<S>
+where
+    S::Key: Ord,
+{
     type Item = (S::Key, S::Value);
     type IntoIter = Iter<Self>;
     fn into_iter(self) -> Self::IntoIter {
@@ -81,7 +101,10 @@ impl<S: Seekable> IntoIterator for Merger<S> {
     }
 }
 
-fn heap_reset<S: Seekable>(m: &mut Merger<S>, key: &S::Key) {
+fn heap_reset<S: Seekable>(m: &mut Merger<S>, key: &S::Key)
+where
+    S::Key: Ord,
+{
     let mut active = Vec::<MergerEnt<S>>::new();
     let mut ended = Vec::<S>::new();
     while let Some(e) = m.active.pop() {
@@ -104,7 +127,10 @@ fn heap_reset<S: Seekable>(m: &mut Merger<S>, key: &S::Key) {
 }
 
 // forward seek within the heap
-fn heap_seek<S: Seekable>(m: &mut Merger<S>, key: &S::Key) -> Option<()> {
+fn heap_seek<S: Seekable>(m: &mut Merger<S>, key: &S::Key) -> Option<()>
+where
+    S::Key: Ord,
+{
     loop {
         let mut head = m.active.peek_mut()?;
         if head.cur_item.borrow().0 >= *key {
@@ -122,7 +148,10 @@ fn heap_seek<S: Seekable>(m: &mut Merger<S>, key: &S::Key) -> Option<()> {
     None
 }
 
-impl<S: Seekable> Seekable for Merger<S> {
+impl<S: Seekable> Seekable for Merger<S>
+where
+    S::Key: Ord,
+{
     type Key = S::Key;
     type Value = S::Value;
 
-- 
2.50.1