Struct RangeMap 

pub struct RangeMap<K, V> {
    map: BTreeMap<(K, K), V>,
}

A map to control intervals that have same values.

Fields

map: BTreeMap<(K, K), V>

Implementations

impl<K, V> RangeMap<K, V>

pub fn new() -> Self

where K: Ord,

Makes a new, empty RangeMap.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 255)

    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }

pub fn clear(&mut self)

where K: Ord,

Clears the map, removing all elements.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 289)

    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }

pub fn contains_key(&self, key: &K) -> bool

where K: Clone + Ord,

Returns true if the map contains a value for the key.

pub fn get(&self, key: &K) -> Option<&V>

where K: Clone + Ord,

Returns a reference to the value corresponding to the key.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 41)

    pub fn contains_key(&self, key: &K) -> bool
    where
        K: Clone + Ord,
    {
        self.get(key).is_some()
    }

pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>

where K: Clone + Ord,

Returns the range-value pair corresponding to the key.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 48)

    pub fn get(&self, key: &K) -> Option<&V>
    where
        K: Clone + Ord,
    {
        self.get_range_value(key).map(|(_, v)| v)
    }
    /// Returns the range-value pair corresponding to the key.
    pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
    {
        self.get_right_if(key, |r, _| key == &r.0)
            .or_else(|| self.get_left_if(key, |r, _| key < &r.1))
    }
    /// Inserts values into the specified range.
    pub fn insert(&mut self, range: (K, K), value: V)
    where
        K: Clone + Ord,
        V: Clone + Eq,
    {
        self.insert_with(range, value, |_, _| {});
    }
    /// Insert values and operate old range-value pairs.
    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }

pub fn insert(&mut self, range: (K, K), value: V)

where K: Clone + Ord, V: Clone + Eq,

Inserts values into the specified range.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 245)

    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }

pub fn insert_with<F>(&mut self, range: (K, K), value: V, f: F)

where K: Clone + Ord, V: Clone + Eq, F: FnMut((K, K), V),

Insert values and operate old range-value pairs.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 64)

    pub fn insert(&mut self, range: (K, K), value: V)
    where
        K: Clone + Ord,
        V: Clone + Eq,
    {
        self.insert_with(range, value, |_, _| {});
    }
    /// Insert values and operate old range-value pairs.
    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }
    /// Inserts into the specified range.
    pub fn insert(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.insert_with(range, |_| {});
    }
    /// Insert and operate old range.
    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.insert_with(range, (), |r, _| f(r))
    }

pub fn remove(&mut self, range: (K, K))

where K: Clone + Ord, V: Clone,

Remove values contained in the range.

pub fn get_left_if<F>(&self, key: &K, pred: F) -> Option<(&(K, K), &V)>

where K: Clone + Ord, F: FnMut(&(K, K), &V) -> bool,

Get a left neighboring range of [key, key) if the predicate is satisfied.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 56)

    pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
    {
        self.get_right_if(key, |r, _| key == &r.0)
            .or_else(|| self.get_left_if(key, |r, _| key < &r.1))
    }
    /// Inserts values into the specified range.
    pub fn insert(&mut self, range: (K, K), value: V)
    where
        K: Clone + Ord,
        V: Clone + Eq,
    {
        self.insert_with(range, value, |_, _| {});
    }
    /// Insert values and operate old range-value pairs.
    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }
    /// Inserts into the specified range.
    pub fn insert(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.insert_with(range, |_| {});
    }
    /// Insert and operate old range.
    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.insert_with(range, (), |r, _| f(r))
    }
    /// Remove items contained in the range.
    pub fn remove(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.drain_with(range, |_| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }

pub fn get_right_if<F>(&self, key: &K, pred: F) -> Option<(&(K, K), &V)>

where K: Clone + Ord, F: FnMut(&(K, K), &V) -> bool,

Get a right neighboring range of [key, key) if the predicate is satisfied.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 55)

    pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
    {
        self.get_right_if(key, |r, _| key == &r.0)
            .or_else(|| self.get_left_if(key, |r, _| key < &r.1))
    }
    /// Inserts values into the specified range.
    pub fn insert(&mut self, range: (K, K), value: V)
    where
        K: Clone + Ord,
        V: Clone + Eq,
    {
        self.insert_with(range, value, |_, _| {});
    }
    /// Insert values and operate old range-value pairs.
    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }
    /// Inserts into the specified range.
    pub fn insert(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.insert_with(range, |_| {});
    }
    /// Insert and operate old range.
    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.insert_with(range, (), |r, _| f(r))
    }
    /// Remove items contained in the range.
    pub fn remove(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.drain_with(range, |_| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }

pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>

where K: Clone + Ord, F: FnMut(&(K, K), &V) -> bool,

Pop a left neighboring range of [key, key) if the predicate is satisfied.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (lines 77-79)

    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }
    /// Inserts into the specified range.
    pub fn insert(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.insert_with(range, |_| {});
    }
    /// Insert and operate old range.
    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.insert_with(range, (), |r, _| f(r))
    }
    /// Remove items contained in the range.
    pub fn remove(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.drain_with(range, |_| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.pop_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }

pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>

where K: Clone + Ord, F: FnMut(&(K, K), &V) -> bool,

Pop a right neighboring range of [key, key) if the predicate is satisfied.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 100)

    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }
    /// Inserts into the specified range.
    pub fn insert(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.insert_with(range, |_| {});
    }
    /// Insert and operate old range.
    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.insert_with(range, (), |r, _| f(r))
    }
    /// Remove items contained in the range.
    pub fn remove(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.drain_with(range, |_| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.pop_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.pop_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }

fn drain_with_inner<F>(&mut self, range: (K, K), f: F) -> F

where K: Clone + Ord, F: FnMut((K, K), V),

Operate and consume range-value pairs in range when no overlapping.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 110)

    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
    where
        K: Clone + Ord,
        V: Clone + Eq,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        let mut ins_range = range.clone();
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
            range.0 < r.1 || range.0 == r.1 && &value == v
        }) {
            if range.1 < r.1 {
                if value == v {
                    ins_range = r;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                    self.map.insert((range.1.clone(), r.1), v.clone());
                }
                f(range.clone(), v);
            } else {
                if value == v {
                    ins_range.0 = r.0;
                } else {
                    self.map.insert((r.0, range.0.clone()), v.clone());
                }
                if range.0 < r.1 {
                    f((range.0.clone(), r.1), v);
                }
            }
        }
        let mut wait = None;
        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
            ins_range.1 = r.1;
        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            if value == v {
                ins_range.1 = r.1;
            } else {
                self.map.insert((range.1.clone(), r.1), v.clone());
            }
            wait = Some(((r.0, range.1.clone()), v));
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
        self.map.insert(ins_range, value);
    }
    /// Remove values contained in the range.
    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }

pub fn drain_with<F>(&mut self, range: (K, K), f: F)

where K: Clone + Ord, V: Clone, F: FnMut((K, K), V),

Operate and consume range-value pairs in range.

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 122)

    pub fn remove(&mut self, range: (K, K))
    where
        K: Clone + Ord,
        V: Clone,
    {
        self.drain_with(range, |_, _| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range(..(key.clone(), key.clone()))
            .next_back()
            .filter(|(r, v)| pred(r, v))
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        self.map
            .range((key.clone(), key.clone())..)
            .next()
            .filter(|(r, v)| pred(r, v))
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_left_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
    where
        K: Clone + Ord,
        F: FnMut(&(K, K), &V) -> bool,
    {
        match self.get_right_if(key, pred) {
            Some((r, _)) => {
                let r = r.clone();
                let v = self.map.remove(&r).unwrap();
                Some((r, v))
            }
            None => None,
        }
    }
    /// Operate and consume range-value pairs in range when no overlapping.
    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
    where
        K: Clone + Ord,
        F: FnMut((K, K), V),
    {
        while let Some((r, _)) = self
            .map
            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
            .next()
        {
            let r = r.clone();
            let v = self.map.remove(&r).unwrap();
            f(r, v);
        }
        f
    }
    /// Operate and consume range-value pairs in range.
    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
    where
        K: Clone + Ord,
        V: Clone,
        F: FnMut((K, K), V),
    {
        if range.0 >= range.1 {
            return;
        }
        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
            if range.1 < r.1 {
                f(range.clone(), v.clone());
                self.map.insert((range.1.clone(), r.1), v.clone());
            } else {
                f((range.0.clone(), r.1), v.clone());
            }
            self.map.insert((r.0, range.0.clone()), v);
        }
        let mut wait = None;
        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
            wait = Some(((r.0, range.1.clone()), v.clone()));
            self.map.insert((range.1.clone(), r.1), v);
        }
        let mut f = self.drain_with_inner(range, f);
        if let Some((r, v)) = wait {
            f(r, v);
        }
    }
    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
        self.map.iter()
    }
    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
        self.map.iter_mut()
    }
    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
        self.map.keys()
    }
    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
        self.map.values()
    }
    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
        self.map.values_mut()
    }
}
impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
        for (range, value) in iter {
            self.insert(range, value);
        }
    }
}
impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where
    K: Clone + Ord,
    V: Clone + Eq,
{
    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

/// A set to control intervals.
#[derive(Debug, Clone)]
pub struct RangeSet<T> {
    map: RangeMap<T, ()>,
}
impl<T> Default for RangeSet<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}
impl<T> RangeSet<T> {
    /// Makes a new, empty `RangeSet`.
    pub fn new() -> Self
    where
        T: Ord,
    {
        Default::default()
    }
    /// Clears the set, removing all elements.
    pub fn clear(&mut self)
    where
        T: Ord,
    {
        self.map.clear();
    }
    /// Returns true if the set contains a key.
    pub fn contains(&self, key: &T) -> bool
    where
        T: Clone + Ord,
    {
        self.get_range(key).is_some()
    }
    /// Returns the range corresponding to the key.
    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
    where
        T: Clone + Ord,
    {
        self.map.get_range_value(key).map(|(r, _)| r)
    }
    /// Inserts into the specified range.
    pub fn insert(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.insert_with(range, |_| {});
    }
    /// Insert and operate old range.
    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.insert_with(range, (), |r, _| f(r))
    }
    /// Remove items contained in the range.
    pub fn remove(&mut self, range: (T, T))
    where
        T: Clone + Ord,
    {
        self.drain_with(range, |_| {});
    }
    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_left_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.pop_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
    pub fn pop_right_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
    where
        T: Clone + Ord,
        F: FnMut(&(T, T)) -> bool,
    {
        self.map.pop_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
    }
    /// Operate and consume in range.
    pub fn drain_with<F>(&mut self, range: (T, T), mut f: F)
    where
        T: Clone + Ord,
        F: FnMut((T, T)),
    {
        self.map.drain_with(range, |r, _| f(r));
    }

pub fn iter(&self) -> Iter<'_, (K, K), V>

pub fn iter_mut(&mut self) -> IterMut<'_, (K, K), V>

pub fn keys(&self) -> Keys<'_, (K, K), V>

Examples found in repository

crates/competitive/src/data_structure/range_map.rs (line 368)

    pub fn iter(&self) -> btree_map::Keys<'_, (T, T), ()> {
        self.map.keys()
    }

pub fn values(&self) -> Values<'_, (K, K), V>

pub fn values_mut(&mut self) -> ValuesMut<'_, (K, K), V>

Trait Implementations

impl<K: Clone, V: Clone> Clone for RangeMap<K, V>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for RangeMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for RangeMap<K, V>

where K: Ord,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>

where K: Clone + Ord, V: Clone + Eq,

fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>

where K: Clone + Ord, V: Clone + Eq,

fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self

Creates a value from an iterator.