coordinate compression and ArqSpec documentation on point queries

EbTech · EbTech · commit f5c35436d0d8 · 2020-08-16T16:17:43.000-07:00
diff --git a/README.md b/README.md
@@ -44,11 +44,11 @@ Rather than try to persuade you with words, this repository aims to show by exam
 ## Contents
 
 - [Basic graph representations](src/graph/mod.rs): adjacency lists, disjoint set union
-- [Elementary Graph algorithms](src/graph/util.rs): minimum spanning tree, Euler path, Dijkstra's algorithm, DFS iteration
+- [Elementary graph algorithms](src/graph/util.rs): minimum spanning tree, Euler path, Dijkstra's algorithm, DFS iteration
 - [Network flows](src/graph/flow.rs): Dinic's blocking flow, Hopcroft-Karp bipartite matching, min cost max flow
 - [Connected components](src/graph/connectivity.rs): 2-edge-, 2-vertex- and strongly connected components, bridges, articulation points, topological sort, 2-SAT
-- [Associative range query](src/range_query): known colloquially as *segtrees*, and Mo's query square root decomposition
-- [GCD Math](src/math/mod.rs): canonical solution to Bezout's identity
+- [Associative range query](src/range_query): known colloquially as *segtrees*, coordinate compression, and Mo's query square root decomposition
+- [Number thery](src/math/mod.rs): canonical solution to Bezout's identity, Miller's primality test
 - [Arithmetic](src/math/num.rs): rational and complex numbers, linear algebra, safe modular arithmetic
 - [FFT](src/math/fft.rs): fast Fourier transform, number theoretic transform, convolution
 - [Scanner](src/scanner.rs): utility for reading input data ergonomically
diff --git a/src/range_query/mod.rs b/src/range_query/mod.rs
@@ -6,11 +6,53 @@ pub use dynamic_arq::{ArqView, DynamicArq};
 pub use specs::ArqSpec;
 pub use static_arq::StaticArq;
 
+/// A simple data structure for coordinate compression
+pub struct SparseIndex {
+    coords: Vec<i64>
+}
+
+impl SparseIndex {
+    /// Build an index, given the full set of coordinates to compress.
+    pub fn new(mut coords: Vec<i64>) -> Self {
+        coords.sort_unstable();
+        coords.dedup();
+        Self { coords }
+    }
+
+    /// Return Ok(i) if the coordinate q appears at index i
+    /// Return Err(i) if q appears between indices i-1 and i
+    pub fn compress(&self, q: i64) -> Result<usize, usize> {
+        self.coords.binary_search(&q)
+    }
+}
+
 #[cfg(test)]
 mod test {
     use super::specs::*;
     use super::*;
 
+    #[test]
+    fn test_coord_compress() {
+        let mut coords = vec![16, 99, 45, 18];
+        let index = SparseIndex::new(coords.clone());
+
+        coords.sort_unstable();
+        for (i, q) in coords.into_iter().enumerate() {
+            assert_eq!(index.compress(q - 1), Err(i));
+            assert_eq!(index.compress(q), Ok(i));
+            assert_eq!(index.compress(q + 1), Err(i + 1));
+        }
+    }
+
+    #[test]
+    fn test_range_compress() {
+        let queries = vec![(0, 10), (10, 19), (20, 29)];
+        let coords = queries.iter().flat_map(|&(i, j)| vec![i, j + 1]).collect();
+        let index = SparseIndex::new(coords);
+        
+        assert_eq!(index.coords, vec![0, 10, 11, 20, 30]);
+    }
+
     #[test]
     fn test_rmq() {
         let mut arq = StaticArq::<AssignMin>::new(&[0; 10]);
diff --git a/src/range_query/specs.rs b/src/range_query/specs.rs
@@ -15,15 +15,23 @@ pub trait ArqSpec {
     /// Must satisfy the Identity Law:
     /// For all a, op(a, identity()) = op(identity(), a) = a
     fn identity() -> Self::S;
-    /// For point query / eager updates, compose() can be unimplemented!()
-    /// For range query / lazy updates, it must satisfy the Composition Law:
+    /// Must satisfy the Composition Law:
     /// For all f,g,a, apply(compose(f, g), a) = apply(f, apply(g, a))
     fn compose(f: &Self::F, g: &Self::F) -> Self::F;
-    /// For point query / eager updates, apply() can assume it acts on a leaf.
-    /// For range query / lazy updates, it must satisfy the Distributive Law:
-    /// For all f,a,b, apply(f, op(a, b)) = op(apply(f, a), apply(f, b))
+    /// Must satisfy the Distributive Law:
+    /// For all f,a,b, apply(f, op(a, b), s+t) = op(apply(f, a, s), apply(f, b, t))
     /// The `size` parameter makes this law easier to satisfy in certain cases.
     fn apply(f: &Self::F, a: &Self::S, size: i64) -> Self::S;
+
+    // The following relaxations to the laws may apply.
+    // If only point updates are made, the Composition and Distributive Laws
+    // no longer apply.
+    // - compose() is never called, so it can be left unimplemented!().
+    // - apply() is only ever called on leaves, i.e., with size == 1.
+    // If only point queries are made, the Associative and Distributive Laws
+    // no longer apply.
+    // - op()'s result only matters when identity() is an argument.
+    // - apply()'s result only matters on leaves, i.e., with size == 1.
 }
 
 /// Range Minimum Query (RMQ), a classic application of ARQ.
@@ -109,7 +117,8 @@ impl ArqSpec for SupplyDemand {
     fn compose(_: &Self::F, _: &Self::F) -> Self::F {
         unimplemented!()
     }
-    fn apply(&(p_add, o_add): &Self::F, &(p, o, _): &Self::S, _: i64) -> Self::S {
+    fn apply(&(p_add, o_add): &Self::F, &(p, o, _): &Self::S, s: i64) -> Self::S {
+        assert_eq!(s, 1);
         let p = p + p_add;
         let o = o + o_add;
         (p, o, p.min(o))
