Restructure EntityMap interface

zhiburt · zhiburt · Dec 20, 2024 · Dec 21, 2024 · Dec 21, 2024 · Jan 3, 2025
commit 149d87e8185a5281a6e69640e69e693204855a86
diff --git a/papergrid/Cargo.toml b/papergrid/Cargo.toml
@@ -16,6 +16,7 @@ ansi = ["ansi-str", "ansitok"]
 unicode-width = "0.2"
 bytecount = "0.6"
 fnv = "1.0"
+rtree_rs = { git = "https://github.com/zhiburt/rtree.rs.git", rev = "654787dae883428a23de7d039e0b88b7d34790f7" }
 ansi-str = { version = "0.8", optional = true }
 ansitok = { version = "0.2", optional = true  }
 

diff --git a/papergrid/src/colors.rs b/papergrid/src/colors.rs
@@ -64,17 +64,16 @@ where
 #[cfg(feature = "std")]
 impl<C> Colors for crate::config::spanned::EntityMap<Option<C>>
 where
-    C: ANSIFmt,
+    C: ANSIFmt + PartialEq,
 {
     type Color = C;
 
     fn get_color(&self, pos: Position) -> Option<&Self::Color> {
-        self.get(pos.into()).as_ref()
+        self.get(pos).as_ref()
     }
 
     fn is_empty(&self) -> bool {
-        crate::config::spanned::EntityMap::is_empty(self)
-            && self.get(crate::config::Entity::Global).is_none()
+        self.is_empty() && self.as_ref().is_none()
     }
 }
 

diff --git a/papergrid/src/config/spanned/entity_map copy.rs b/papergrid/src/config/spanned/entity_map copy.rs
@@ -0,0 +1,156 @@
+use std::collections::HashMap;
+
+use rtree_rs::{RTree, Rect};
+
+use crate::config::{Entity, Position};
+
+/// A structure to keep information for [`Entity`] as a key.
+#[derive(Debug, Default, Clone, PartialEq, Eq)]
+pub struct EntityMap<T> {
+    // we have a global type to allocate in on stack.
+    // because most of the time no changes are made to the [`EntityMap`].
+    global: T,
+    // todo: Maybe maybe we shall check whether tree is getting too big and switch back to a 3 hash tables?
+    tree: RTree<2, usize, T>,
+}
+
+impl<T> EntityMap<T> {
+    /// Creates an empty [`EntityMap`].
+    pub fn new(global: T) -> Self
+    where
+        T: PartialEq,
+    {
+        Self {
+            global,
+            tree: RTree::new(),
+        }
+    }
+
+    /// Verifies whether anything was set beside a global entry.
+    pub fn is_empty(&self) -> bool
+    where
+        T: PartialEq,
+    {
+        self.tree.is_empty()
+    }
+
+    /// Get a value for an [`Entity`].
+    pub fn get(&self, pos: Position) -> &T
+    where
+        T: PartialEq,
+    {
+        if self.is_empty() {
+            return &self.global;
+        }
+
+        let (row, col) = pos;
+        let value = self
+            .tree
+            .search(Rect::new([row, col], [row, col]))
+            .last()
+            .map(|item| item.data);
+
+        value.unwrap_or(&self.global)
+    }
+
+    /// Removes a value for an [`Entity`].
+    pub fn remove(&mut self, entity: Entity)
+    where
+        T: PartialEq + Clone,
+    {
+        let mut new = RTree::new();
+
+        // todo: Rtree contribution to remove effectively
+
+        match entity {
+            Entity::Global => {}
+            Entity::Column(col) => {
+                for item in self.tree.iter() {
+                    if item.rect.min[1] != col && item.rect.max[1] != col {
+                        new.insert(item.rect, item.data.clone());
+                    }
+                }
+            }
+            Entity::Row(row) => {
+                for item in self.tree.iter() {
+                    if item.rect.min[0] != row && item.rect.max[0] != row {
+                        new.insert(item.rect, item.data.clone());
+                    }
+                }
+            }
+            Entity::Cell(row, col) => {
+                for item in self.tree.iter() {
+                    if item.rect.min != [row, col] && item.rect.max != [row, col] {
+                        new.insert(item.rect, item.data.clone());
+                    }
+                }
+            }
+        }
+
+        self.tree = new;
+    }
+
+    /// Set a value for an [`Entity`].
+    pub fn insert(&mut self, entity: Entity, value: T)
+    where
+        T: PartialEq,
+    {
+        match entity {
+            Entity::Column(col) => {
+                self.tree
+                    .insert(Rect::new([0, col], [usize::MAX, col]), value);
+            }
+            Entity::Row(row) => {
+                self.tree
+                    .insert(Rect::new([row, 0], [row, usize::MAX]), value);
+            }
+            Entity::Cell(row, col) => {
+                self.tree.insert(Rect::new([row, col], [row, col]), value);
+            }
+            Entity::Global => {
+                self.tree = RTree::new();
+                self.global = value
+            }
+        }
+    }
+}
+
+impl<T> From<EntityMap<T>> for HashMap<Entity, T>
+where
+    T: PartialEq + Clone,
+{
+    fn from(em: EntityMap<T>) -> Self {
+        let mut m = HashMap::new();
+        m.insert(Entity::Global, em.global);
+
+        for item in em.tree.iter() {
+            let value = item.data.clone();
+
+            let is_same_row = item.rect.min[0] == item.rect.max[0];
+            let is_same_column = item.rect.min[1] == item.rect.max[1];
+            let is_unbound_row = item.rect.min[0] == 0 && item.rect.max[0] == usize::MAX;
+            let is_unbound_column = item.rect.min[1] == 0 && item.rect.max[1] == usize::MAX;
+
+            let row = item.rect.min[0];
+            let col = item.rect.min[1];
+
+            if is_same_row && is_same_column {
+                m.insert(Entity::Cell(row, col), value);
+            } else if is_same_column && is_unbound_row {
+                m.insert(Entity::Column(col), value);
+            } else if is_same_row && is_unbound_column {
+                m.insert(Entity::Row(row), value);
+            } else {
+                unreachable!("must have never happen")
+            }
+        }
+
+        m
+    }
+}
+
+impl<T> AsRef<T> for EntityMap<T> {
+    fn as_ref(&self) -> &T {
+        &self.global
+    }
+}
diff --git a/papergrid/src/config/spanned/entity_map.rs b/papergrid/src/config/spanned/entity_map.rs
@@ -32,40 +32,29 @@ impl<T> EntityMap<T> {
     }
 
     /// Get a value for an [`Entity`].
-    pub fn get(&self, entity: Entity) -> &T {
-        if self.rows.is_empty() && self.columns.is_empty() && self.cells.is_empty() {
-            return &self.global;
-        }
-
-        match entity {
-            Entity::Column(col) => self.columns.get(&col).unwrap_or(&self.global),
-            Entity::Row(row) => self.rows.get(&row).unwrap_or(&self.global),
-            Entity::Cell(row, col) => {
-                // todo: optimize;
-                //
-                // Cause we can change rows/columns/cells separately we need to check them separately.
-                // But we often doing this checks in `Grid::fmt` and I believe if we could optimize it it could be beneficial.
-                //
-                // Haven't found a solution for that yet.
-                //
-                // I was wondering if there is a hash function like.
-                // Apparently it doesn't make sense cause we will reset columns/rows on cell insert which is not what we want.
-                //
-                // ```
-                // hash(column, row) == hash(column) == hash(row)
-                // ```
-                //
-                // ref: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/Sparse.html
-                // ref: https://users.rust-lang.org/t/make-hash-return-same-value-whather-the-order-of-element-of-a-tuple/69932/13
-
-                self.cells
-                    .get(&(row, col))
-                    .or_else(|| self.columns.get(&col))
-                    .or_else(|| self.rows.get(&row))
-                    .unwrap_or(&self.global)
-            }
-            Entity::Global => &self.global,
-        }
+    pub fn get(&self, (row, col): Position) -> &T {
+        // todo: optimize;
+        //
+        // Cause we can change rows/columns/cells separately we need to check them separately.
+        // But we often doing this checks in `Grid::fmt` and I believe if we could optimize it it could be beneficial.
+        //
+        // Haven't found a solution for that yet.
+        //
+        // I was wondering if there is a hash function like.
+        // Apparently it doesn't make sense cause we will reset columns/rows on cell insert which is not what we want.
+        //
+        // ```
+        // hash(column, row) == hash(column) == hash(row)
+        // ```
+        //
+        // ref: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/Sparse.html
+        // ref: https://users.rust-lang.org/t/make-hash-return-same-value-whather-the-order-of-element-of-a-tuple/69932/13
+
+        self.cells
+            .get(&(row, col))
+            .or_else(|| self.columns.get(&col))
+            .or_else(|| self.rows.get(&row))
+            .unwrap_or(&self.global)
     }
 
     /// Removes a value for an [`Entity`].
@@ -134,3 +123,9 @@ impl<T> From<EntityMap<T>> for HashMap<Entity, T> {
         m
     }
 }
+
+impl<T> AsRef<T> for EntityMap<T> {
+    fn as_ref(&self) -> &T {
+        &self.global
+    }
+}