Range module

/*
 * A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.
 * A half-open interval [left, right) denotes all the real numbers x where left <= x < right.
 * Implement the RangeModule class:
 * RangeModule() Initializes the object of the data structure.
 * void addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
 * boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
 * void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).
 * Example 1:
 * Input
 * ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
 * [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
 * Output
 * [null, null, null, true, false, true]
 * Explanation
 * RangeModule rangeModule = new RangeModule();
 * rangeModule.addRange(10, 20);
 * rangeModule.removeRange(14, 16);
 * rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
 * rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
 * rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
 * Constraints:
 * 1 <= left < right <= 109
 * At most 104 calls will be made to addRange, queryRange, and removeRange.

 * struct RangeModule {

 * }


 * /** 
 *  * `&self` means the method takes an immutable reference.
 *  * If you need a mutable reference, change it to `&mut self` instead.
 *  */
 * impl RangeModule {

 *     fn new() -> Self {

 *     }

 *     fn add_range(&self, left: i32, right: i32) {

 *     }

 *     fn query_range(&self, left: i32, right: i32) -> bool {

 *     }

 *     fn remove_range(&self, left: i32, right: i32) {

 *     }
 * }
 */
use std::collections::BTreeMap;

struct RangeModule {
  ranges: BTreeMap<i32, i32>,
}

impl RangeModule {
  fn new() -> Self {
    RangeModule { ranges: BTreeMap::new() }
  }

  fn add_range(&mut self, left: i32, right: i32) {
    let mut l = left;
    let mut r = right;
    let mut to_remove: Vec<i32> = vec![];
    // Merge all intervals [a,b) where a <= r and b >= l (overlap or adjacent)
    for (&a, &b) in self.ranges.range(..=r) {
      if b >= l {
        l = l.min(a);
        r = r.max(b);
        to_remove.push(a);
      }
    }
    for k in to_remove { self.ranges.remove(&k); }
    self.ranges.insert(l, r);
  }

  fn query_range(&self, left: i32, right: i32) -> bool {
    if let Some((&_a, &b)) = self.ranges.range(..=left).next_back() {
      return b >= right;
    }
    false
  }

  fn remove_range(&mut self, left: i32, right: i32) {
    let mut to_remove: Vec<i32> = vec![];
    let mut to_add: Vec<(i32, i32)> = vec![];
    for (&a, &b) in self.ranges.range(..right) {
      if b > left {
        to_remove.push(a);
        if a < left { to_add.push((a, left)); }
        if b > right { to_add.push((right, b)); }
      }
    }
    for k in to_remove { self.ranges.remove(&k); }
    for (a, b) in to_add { self.ranges.insert(a, b); }
  }
}