commit 686dea983125e899ab2e86c5970b9921a30bf9b1
parent 01171ff9d798a271a116ebec06deeeaaf373434c
Author: kernelkind <kernelkind@gmail.com>
Date: Tue, 19 Aug 2025 16:50:50 -0400
move `HybridSet` to own file
Signed-off-by: kernelkind <kernelkind@gmail.com>
Diffstat:
4 files changed, 104 insertions(+), 103 deletions(-)
diff --git a/crates/notedeck_columns/src/actionbar.rs b/crates/notedeck_columns/src/actionbar.rs
@@ -3,10 +3,8 @@ use crate::{
nav::{RouterAction, RouterType},
route::Route,
timeline::{
- thread::{
- selected_has_at_least_n_replies, InsertionResponse, NoteSeenFlags, ThreadNode, Threads,
- },
- ThreadSelection, TimelineCache, TimelineKind,
+ thread::{selected_has_at_least_n_replies, NoteSeenFlags, ThreadNode, Threads},
+ InsertionResponse, ThreadSelection, TimelineCache, TimelineKind,
},
view_state::ViewState,
};
diff --git a/crates/notedeck_columns/src/timeline/hybrid_set.rs b/crates/notedeck_columns/src/timeline/hybrid_set.rs
@@ -0,0 +1,99 @@
+use std::{
+ collections::{BTreeSet, HashSet},
+ hash::Hash,
+};
+
+use crate::timeline::MergeKind;
+
+/// Affords:
+/// - O(1) contains
+/// - O(log n) sorted insertion
+pub struct HybridSet<T> {
+ reversed: bool,
+ lookup: HashSet<T>, // fast deduplication
+ ordered: BTreeSet<T>, // sorted iteration
+}
+
+impl<T> Default for HybridSet<T> {
+ fn default() -> Self {
+ Self {
+ reversed: Default::default(),
+ lookup: Default::default(),
+ ordered: Default::default(),
+ }
+ }
+}
+
+pub enum InsertionResponse {
+ AlreadyExists,
+ Merged(MergeKind),
+}
+
+impl<T: Copy + Ord + Eq + Hash> HybridSet<T> {
+ pub fn insert(&mut self, val: T) -> InsertionResponse {
+ if !self.lookup.insert(val) {
+ return InsertionResponse::AlreadyExists;
+ }
+
+ let front_insertion = match self.ordered.iter().next() {
+ Some(first) => (val >= *first) == self.reversed,
+ None => true,
+ };
+
+ self.ordered.insert(val); // O(log n)
+
+ InsertionResponse::Merged(if front_insertion {
+ MergeKind::FrontInsert
+ } else {
+ MergeKind::Spliced
+ })
+ }
+}
+
+impl<T: Eq + Hash> HybridSet<T> {
+ pub fn contains(&self, val: &T) -> bool {
+ self.lookup.contains(val) // O(1)
+ }
+}
+
+impl<T> HybridSet<T> {
+ pub fn iter(&self) -> HybridIter<'_, T> {
+ HybridIter {
+ inner: self.ordered.iter(),
+ reversed: self.reversed,
+ }
+ }
+
+ pub fn new(reversed: bool) -> Self {
+ Self {
+ reversed,
+ ..Default::default()
+ }
+ }
+}
+
+impl<'a, T> IntoIterator for &'a HybridSet<T> {
+ type Item = &'a T;
+ type IntoIter = HybridIter<'a, T>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+pub struct HybridIter<'a, T> {
+ inner: std::collections::btree_set::Iter<'a, T>,
+ reversed: bool,
+}
+
+impl<'a, T> Iterator for HybridIter<'a, T> {
+ type Item = &'a T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.reversed {
+ self.inner.next_back()
+ } else {
+ self.inner.next()
+ }
+ }
+}
diff --git a/crates/notedeck_columns/src/timeline/mod.rs b/crates/notedeck_columns/src/timeline/mod.rs
@@ -26,11 +26,13 @@ use std::{rc::Rc, time::SystemTime};
use tracing::{debug, error, info, warn};
pub mod cache;
+mod hybrid_set;
pub mod kind;
pub mod route;
pub mod thread;
pub use cache::TimelineCache;
+pub use hybrid_set::{HybridSet, InsertionResponse};
pub use kind::{ColumnTitle, PubkeySource, ThreadSelection, TimelineKind};
#[derive(Copy, Clone, Eq, PartialEq, Debug, Default)]
diff --git a/crates/notedeck_columns/src/timeline/thread.rs b/crates/notedeck_columns/src/timeline/thread.rs
@@ -1,8 +1,3 @@
-use std::{
- collections::{BTreeSet, HashSet},
- hash::Hash,
-};
-
use egui_nav::ReturnType;
use egui_virtual_list::VirtualList;
use enostr::{NoteId, RelayPool};
@@ -13,7 +8,7 @@ use notedeck::{NoteCache, NoteRef, UnknownIds};
use crate::{
actionbar::{process_thread_notes, NewThreadNotes},
multi_subscriber::ThreadSubs,
- timeline::MergeKind,
+ timeline::hybrid_set::HybridSet,
};
use super::ThreadSelection;
@@ -33,99 +28,6 @@ pub enum ParentState {
Parent(NoteId),
}
-/// Affords:
-/// - O(1) contains
-/// - O(log n) sorted insertion
-pub struct HybridSet<T> {
- reversed: bool,
- lookup: HashSet<T>, // fast deduplication
- ordered: BTreeSet<T>, // sorted iteration
-}
-
-impl<T> Default for HybridSet<T> {
- fn default() -> Self {
- Self {
- reversed: Default::default(),
- lookup: Default::default(),
- ordered: Default::default(),
- }
- }
-}
-
-pub enum InsertionResponse {
- AlreadyExists,
- Merged(MergeKind),
-}
-
-impl<T: Copy + Ord + Eq + Hash> HybridSet<T> {
- pub fn insert(&mut self, val: T) -> InsertionResponse {
- if !self.lookup.insert(val) {
- return InsertionResponse::AlreadyExists;
- }
-
- let front_insertion = match self.ordered.iter().next() {
- Some(first) => (val >= *first) == self.reversed,
- None => true,
- };
-
- self.ordered.insert(val); // O(log n)
-
- InsertionResponse::Merged(if front_insertion {
- MergeKind::FrontInsert
- } else {
- MergeKind::Spliced
- })
- }
-}
-
-impl<T: Eq + Hash> HybridSet<T> {
- pub fn contains(&self, val: &T) -> bool {
- self.lookup.contains(val) // O(1)
- }
-}
-
-impl<T> HybridSet<T> {
- pub fn iter(&self) -> HybridIter<'_, T> {
- HybridIter {
- inner: self.ordered.iter(),
- reversed: self.reversed,
- }
- }
-
- pub fn new(reversed: bool) -> Self {
- Self {
- reversed,
- ..Default::default()
- }
- }
-}
-
-impl<'a, T> IntoIterator for &'a HybridSet<T> {
- type Item = &'a T;
- type IntoIter = HybridIter<'a, T>;
-
- fn into_iter(self) -> Self::IntoIter {
- self.iter()
- }
-}
-
-pub struct HybridIter<'a, T> {
- inner: std::collections::btree_set::Iter<'a, T>,
- reversed: bool,
-}
-
-impl<'a, T> Iterator for HybridIter<'a, T> {
- type Item = &'a T;
-
- fn next(&mut self) -> Option<Self::Item> {
- if self.reversed {
- self.inner.next_back()
- } else {
- self.inner.next()
- }
- }
-}
-
impl ThreadNode {
pub fn new(parent: ParentState) -> Self {
Self {
