more ways to initialize and merge trees with DynamicArq

EbTech · EbTech · commit 47fa6f6a64ea · 2019-08-05T16:31:25.000-07:00
diff --git a/src/range_query/dynamic_arq.rs b/src/range_query/dynamic_arq.rs
@@ -24,7 +24,7 @@ impl<T: ArqSpec> DynamicArqNode<T> {
         Self {
             val,
             app: None,
-            down: (0, 0),
+            down: (usize::max_value(), usize::max_value()),
         }
     }
 
@@ -50,31 +50,65 @@ pub struct DynamicArq<T: ArqSpec> {
 }
 
 impl<T: ArqSpec> DynamicArq<T> {
-    pub fn new(
-        l_bound: i64,
-        r_bound: i64,
-        is_persistent: bool,
-        initializer: Box<dyn Fn(i64, i64) -> T::M>,
-    ) -> (Self, ArqView) {
-        let val = initializer(l_bound, r_bound);
-        let nodes = vec![DynamicArqNode::new(val)];
-        let arq = Self {
-            nodes,
+    /// Initializes the data structure without creating any nodes.
+    /// The initializer f must satisfy: f(l, r) = T::op(f(l, m), f(m+1, r))
+    pub fn new(is_persistent: bool, initializer: Box<dyn Fn(i64, i64) -> T::M>) -> Self {
+        Self {
+            nodes: vec![],
             is_persistent,
             initializer,
-        };
-        let root_view = (0, l_bound, r_bound);
-        (arq, root_view)
+        }
     }
 
-    pub fn new_with_identity(l_bound: i64, r_bound: i64, is_persistent: bool) -> (Self, ArqView) {
+    /// Initializes the data structure without creating any nodes.
+    pub fn new_with_identity(is_persistent: bool) -> Self {
         let initializer = Box::new(|_, _| T::identity());
-        Self::new(l_bound, r_bound, is_persistent, initializer)
+        Self::new(is_persistent, initializer)
+    }
+
+    /// Lazily builds a tree over the range [l_bound, r_bound].
+    pub fn build_using_initializer(&mut self, l_bound: i64, r_bound: i64) -> ArqView {
+        let view = (self.nodes.len(), l_bound, r_bound);
+        let val = (self.initializer)(l_bound, r_bound);
+        self.nodes.push(DynamicArqNode::new(val));
+        view
+    }
+
+    /// Builds a tree whose leaves are set to a given non-empty slice.
+    pub fn build_from_slice(&mut self, init_val: &[T::M]) -> ArqView {
+        if init_val.len() == 1 {
+            let view = (self.nodes.len(), 0, 0);
+            let val = T::op(&T::identity(), &init_val[0]);
+            self.nodes.push(DynamicArqNode::new(val));
+            return view;
+        }
+        let m = (init_val.len() + 1) / 2;
+        let (l_init, r_init) = init_val.split_at(m);
+        let l_view = self.build_from_slice(l_init);
+        let r_view = self.build_from_slice(r_init);
+        self.merge_equal_sized(l_view, r_view)
+    }
+
+    /// Merges two balanced subtrees into a single tree with a 0-indexed view.
+    pub fn merge_equal_sized(&mut self, l_view: ArqView, r_view: ArqView) -> ArqView {
+        let l_len = l_view.2 - l_view.1 + 1;
+        let r_len = r_view.2 - r_view.1 + 1;
+        assert!(l_len == r_len || l_len == r_len + 1);
+
+        let view = (self.nodes.len(), 0, l_len + r_len - 1);
+        let root = DynamicArqNode {
+            val: T::identity(),
+            app: None,
+            down: (l_view.0, r_view.0),
+        };
+        self.nodes.push(root);
+        self.pull(view.0);
+        view
     }
 
     pub fn push(&mut self, (p, l, r): ArqView) -> (ArqView, ArqView) {
         let m = (l + r) / 2;
-        if self.nodes[p].down.0 == 0 {
+        if self.nodes[p].down.0 == usize::max_value() {
             let l_val = (self.initializer)(l, m);
             let r_val = (self.initializer)(m + 1, r);
             self.nodes.push(DynamicArqNode::new(l_val));
diff --git a/src/range_query/mod.rs b/src/range_query/mod.rs
@@ -13,7 +13,7 @@ mod test {
 
     #[test]
     fn test_rmq() {
-        let mut arq = StaticArq::<AssignMin>::new(vec![0; 10]);
+        let mut arq = StaticArq::<AssignMin>::new(&[0; 10]);
 
         assert_eq!(arq.query(0, 9), 0);
 
@@ -27,7 +27,8 @@ mod test {
     #[test]
     fn test_dynamic_rmq() {
         let initializer = Box::new(|_, _| 0);
-        let (mut arq, view) = DynamicArq::<AssignMin>::new(0, 9, false, initializer);
+        let mut arq = DynamicArq::<AssignMin>::new(false, initializer);
+        let view = arq.build_using_initializer(0, 9);
 
         assert_eq!(arq.query(view, 0, 9), 0);
 
@@ -41,7 +42,8 @@ mod test {
     #[test]
     fn test_persistent_rmq() {
         let initializer = Box::new(|_, _| 0);
-        let (mut arq, mut view) = DynamicArq::<AssignMin>::new(0, 9, true, initializer);
+        let mut arq = DynamicArq::<AssignMin>::new(true, initializer);
+        let mut view = arq.build_using_initializer(0, 9);
 
         let at_init = view;
         view = arq.modify(view, 2, 4, &-5);
@@ -56,7 +58,7 @@ mod test {
 
     #[test]
     fn test_range_sum() {
-        let mut arq = StaticArq::<AssignSum>::new(vec![(0, 1); 10]);
+        let mut arq = StaticArq::<AssignSum>::new(&[(0, 1); 10]);
 
         assert_eq!(arq.query(0, 9), (0, 10));
 
@@ -70,7 +72,8 @@ mod test {
     #[test]
     fn test_dynamic_range_sum() {
         let initializer = Box::new(|l, r| (0, 1 + r - l));
-        let (mut arq, view) = DynamicArq::<AssignSum>::new(0, 9, false, initializer);
+        let mut arq = DynamicArq::<AssignSum>::new(false, initializer);
+        let view = arq.build_using_initializer(0, 9);
 
         assert_eq!(arq.query(view, 0, 9), (0, 10));
 
@@ -83,7 +86,7 @@ mod test {
 
     #[test]
     fn test_supply_demand() {
-        let mut arq = StaticArq::<SupplyDemand>::new(vec![(0, 0, 0); 10]);
+        let mut arq = StaticArq::<SupplyDemand>::new(&[(0, 0, 0); 10]);
 
         arq.modify(1, 1, &(25, 100));
         arq.modify(3, 3, &(100, 30));
@@ -94,7 +97,8 @@ mod test {
 
     #[test]
     fn test_dynamic_supply_demand() {
-        let (mut arq, view) = DynamicArq::<SupplyDemand>::new_with_identity(0, 9, false);
+        let mut arq = DynamicArq::<SupplyDemand>::new_with_identity(false);
+        let view = arq.build_using_initializer(0, 9);
 
         arq.modify(view, 1, 1, &(25, 100));
         arq.modify(view, 3, 3, &(100, 30));
@@ -106,7 +110,7 @@ mod test {
     #[test]
     fn test_binary_search_rmq() {
         let vec = vec![2, 1, 0, -1, -2, -3, -4, -5];
-        let mut arq = StaticArq::<AssignMin>::new(vec);
+        let mut arq = StaticArq::<AssignMin>::new(&vec);
         let first_neg = static_arq::first_negative(&mut arq);
 
         arq.modify(3, 7, &0);
@@ -116,11 +120,26 @@ mod test {
         assert_eq!(first_neg_zeros, None);
     }
 
+    #[test]
+    fn test_dynslice_binary_search_rmq() {
+        let vec = vec![2, 1, 0, -1, -2, -3, -4, -5];
+        let mut arq = DynamicArq::<AssignMin>::new_with_identity(false);
+        let view = arq.build_from_slice(&vec);
+        let first_neg = dynamic_arq::first_negative(&mut arq, view);
+
+        arq.modify(view, 3, 7, &0);
+        let first_neg_zeros = dynamic_arq::first_negative(&mut arq, view);
+
+        assert_eq!(first_neg, Some(3));
+        assert_eq!(first_neg_zeros, None);
+    }
+
     #[test]
     fn test_dynamic_binary_search_rmq() {
         let initializer = Box::new(|_, r| 2 - r);
         let (l_bound, r_bound) = (0, 1_000_000_000_000_000_000);
-        let (mut arq, view) = DynamicArq::<AssignMin>::new(l_bound, r_bound, false, initializer);
+        let mut arq = DynamicArq::<AssignMin>::new(false, initializer);
+        let view = arq.build_using_initializer(l_bound, r_bound);
         let first_neg = dynamic_arq::first_negative(&mut arq, view);
 
         arq.modify(view, 2, r_bound - 1, &0);
diff --git a/src/range_query/static_arq.rs b/src/range_query/static_arq.rs
@@ -21,10 +21,10 @@ pub struct StaticArq<T: ArqSpec> {
 
 impl<T: ArqSpec> StaticArq<T> {
     /// Initializes a static balanced tree on top of the given sequence.
-    pub fn new(init_val: Vec<T::M>) -> Self {
+    pub fn new(init_val: &[T::M]) -> Self {
         let size = init_val.len();
         let mut val = (0..size).map(|_| T::identity()).collect::<Vec<_>>();
-        val.append(&mut { init_val });
+        val.extend(init_val.iter().map(|v| T::op(&T::identity(), v)));
         let app = vec![None; size];
 
         let mut arq = Self { val, app };
diff --git a/src/scanner.rs b/src/scanner.rs
@@ -86,8 +86,8 @@ mod test {
 
     #[test]
     fn test_in_memory_io() {
-        let cursor = io::Cursor::new("50 8");
-        let mut scan = Scanner::new(cursor);
+        let input = "50 8".as_bytes();
+        let mut scan = Scanner::new(input);
         let mut out = String::new();
         use std::fmt::Write; // needed for writeln!()
 
@@ -100,8 +100,8 @@ mod test {
 
     #[test]
     fn test_in_memory_unsafe() {
-        let cursor = io::Cursor::new("50 8");
-        let mut scan = UnsafeScanner::new(cursor);
+        let input = "50 8".as_bytes();
+        let mut scan = UnsafeScanner::new(input);
         let mut out = String::new();
         use std::fmt::Write; // needed for writeln!()
 
diff --git a/tests/codeforces343d.rs b/tests/codeforces343d.rs
@@ -1,7 +1,7 @@
 //! Solves [Water Tree](http://codeforces.com/contest/343/problem/D).
 //! To make a self-contained file for contest submission, dump each desired
 //! module's contents directly here instead of the use statements.
-//! Also, replace io::Cursor with io::stdin as shown in scanner.rs.
+//! Also, use the commented code in main() to employ standard I/O.
 extern crate contest_algorithms;
 use contest_algorithms::graph::Graph;
 use contest_algorithms::range_query::{specs::AssignSum, StaticArq};
@@ -62,8 +62,7 @@ fn dfs(
 #[test]
 fn main() {
     use std::fmt::Write;
-    let cursor = std::io::Cursor::new(SAMPLE_INPUT);
-    let mut scan = Scanner::new(cursor);
+    let mut scan = Scanner::new(SAMPLE_INPUT.as_bytes());
     let mut out = String::new();
     /* To read/write with stdin/stdout instead:
         use std::io::{self, Write};
@@ -85,7 +84,7 @@ fn main() {
     let mut p = vec![0; n];
     dfs(&tree, 0, &mut l, &mut r, &mut p, &mut 0);
 
-    let mut arq = StaticArq::<AssignSum>::new(vec![(0, 1); n + 1]);
+    let mut arq = StaticArq::<AssignSum>::new(&vec![(0, 1); n + 1]);
     let q = scan.token::<usize>();
     for _ in 0..q {
         let c = scan.token::<usize>();
