Struct RangeMap

Source

pub struct RangeMap<K, V> { /* private fields */ }

Expand description

A map to control intervals that have same values.

Implementations§

Source §

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

Source

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 252)

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

Source

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 286)

282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }

Source

pub fn contains_key(&self, key: &K) -> bool
where K: Clone + Ord,

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

Source

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)

37    pub fn contains_key(&self, key: &K) -> bool
38    where
39        K: Clone + Ord,
40    {
41        self.get(key).is_some()
42    }

Source

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)

44    pub fn get(&self, key: &K) -> Option<&V>
45    where
46        K: Clone + Ord,
47    {
48        self.get_range_value(key).map(|(_, v)| v)
49    }
50    /// Returns the range-value pair corresponding to the key.
51    pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>
52    where
53        K: Clone + Ord,
54    {
55        self.get_right_if(key, |r, _| key == &r.0)
56            .or_else(|| self.get_left_if(key, |r, _| key < &r.1))
57    }
58    /// Inserts values into the specified range.
59    pub fn insert(&mut self, range: (K, K), value: V)
60    where
61        K: Clone + Ord,
62        V: Clone + Eq,
63    {
64        self.insert_with(range, value, |_, _| {});
65    }
66    /// Insert values and operate old range-value pairs.
67    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
68    where
69        K: Clone + Ord,
70        V: Clone + Eq,
71        F: FnMut((K, K), V),
72    {
73        if range.0 >= range.1 {
74            return;
75        }
76        let mut ins_range = range.clone();
77        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
78            range.0 < r.1 || range.0 == r.1 && &value == v
79        }) {
80            if range.1 < r.1 {
81                if value == v {
82                    ins_range = r;
83                } else {
84                    self.map.insert((r.0, range.0.clone()), v.clone());
85                    self.map.insert((range.1.clone(), r.1), v.clone());
86                }
87                f(range.clone(), v);
88            } else {
89                if value == v {
90                    ins_range.0 = r.0;
91                } else {
92                    self.map.insert((r.0, range.0.clone()), v.clone());
93                }
94                if range.0 < r.1 {
95                    f((range.0.clone(), r.1), v);
96                }
97            }
98        }
99        let mut wait = None;
100        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
101            ins_range.1 = r.1;
102        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
103            if value == v {
104                ins_range.1 = r.1;
105            } else {
106                self.map.insert((range.1.clone(), r.1), v.clone());
107            }
108            wait = Some(((r.0, range.1.clone()), v));
109        }
110        let mut f = self.drain_with_inner(range, f);
111        if let Some((r, v)) = wait {
112            f(r, v);
113        }
114        self.map.insert(ins_range, value);
115    }
116    /// Remove values contained in the range.
117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }

Source

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 242)

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

Source

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)

59    pub fn insert(&mut self, range: (K, K), value: V)
60    where
61        K: Clone + Ord,
62        V: Clone + Eq,
63    {
64        self.insert_with(range, value, |_, _| {});
65    }
66    /// Insert values and operate old range-value pairs.
67    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
68    where
69        K: Clone + Ord,
70        V: Clone + Eq,
71        F: FnMut((K, K), V),
72    {
73        if range.0 >= range.1 {
74            return;
75        }
76        let mut ins_range = range.clone();
77        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
78            range.0 < r.1 || range.0 == r.1 && &value == v
79        }) {
80            if range.1 < r.1 {
81                if value == v {
82                    ins_range = r;
83                } else {
84                    self.map.insert((r.0, range.0.clone()), v.clone());
85                    self.map.insert((range.1.clone(), r.1), v.clone());
86                }
87                f(range.clone(), v);
88            } else {
89                if value == v {
90                    ins_range.0 = r.0;
91                } else {
92                    self.map.insert((r.0, range.0.clone()), v.clone());
93                }
94                if range.0 < r.1 {
95                    f((range.0.clone(), r.1), v);
96                }
97            }
98        }
99        let mut wait = None;
100        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
101            ins_range.1 = r.1;
102        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
103            if value == v {
104                ins_range.1 = r.1;
105            } else {
106                self.map.insert((range.1.clone(), r.1), v.clone());
107            }
108            wait = Some(((r.0, range.1.clone()), v));
109        }
110        let mut f = self.drain_with_inner(range, f);
111        if let Some((r, v)) = wait {
112            f(r, v);
113        }
114        self.map.insert(ins_range, value);
115    }
116    /// Remove values contained in the range.
117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }
302    /// Inserts into the specified range.
303    pub fn insert(&mut self, range: (T, T))
304    where
305        T: Clone + Ord,
306    {
307        self.insert_with(range, |_| {});
308    }
309    /// Insert and operate old range.
310    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
311    where
312        T: Clone + Ord,
313        F: FnMut((T, T)),
314    {
315        self.map.insert_with(range, (), |r, _| f(r))
316    }

Source

pub fn remove(&mut self, range: (K, K))
where K: Clone + Ord, V: Clone,

Remove values contained in the range.

Source

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)

51    pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>
52    where
53        K: Clone + Ord,
54    {
55        self.get_right_if(key, |r, _| key == &r.0)
56            .or_else(|| self.get_left_if(key, |r, _| key < &r.1))
57    }
58    /// Inserts values into the specified range.
59    pub fn insert(&mut self, range: (K, K), value: V)
60    where
61        K: Clone + Ord,
62        V: Clone + Eq,
63    {
64        self.insert_with(range, value, |_, _| {});
65    }
66    /// Insert values and operate old range-value pairs.
67    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
68    where
69        K: Clone + Ord,
70        V: Clone + Eq,
71        F: FnMut((K, K), V),
72    {
73        if range.0 >= range.1 {
74            return;
75        }
76        let mut ins_range = range.clone();
77        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
78            range.0 < r.1 || range.0 == r.1 && &value == v
79        }) {
80            if range.1 < r.1 {
81                if value == v {
82                    ins_range = r;
83                } else {
84                    self.map.insert((r.0, range.0.clone()), v.clone());
85                    self.map.insert((range.1.clone(), r.1), v.clone());
86                }
87                f(range.clone(), v);
88            } else {
89                if value == v {
90                    ins_range.0 = r.0;
91                } else {
92                    self.map.insert((r.0, range.0.clone()), v.clone());
93                }
94                if range.0 < r.1 {
95                    f((range.0.clone(), r.1), v);
96                }
97            }
98        }
99        let mut wait = None;
100        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
101            ins_range.1 = r.1;
102        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
103            if value == v {
104                ins_range.1 = r.1;
105            } else {
106                self.map.insert((range.1.clone(), r.1), v.clone());
107            }
108            wait = Some(((r.0, range.1.clone()), v));
109        }
110        let mut f = self.drain_with_inner(range, f);
111        if let Some((r, v)) = wait {
112            f(r, v);
113        }
114        self.map.insert(ins_range, value);
115    }
116    /// Remove values contained in the range.
117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }
302    /// Inserts into the specified range.
303    pub fn insert(&mut self, range: (T, T))
304    where
305        T: Clone + Ord,
306    {
307        self.insert_with(range, |_| {});
308    }
309    /// Insert and operate old range.
310    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
311    where
312        T: Clone + Ord,
313        F: FnMut((T, T)),
314    {
315        self.map.insert_with(range, (), |r, _| f(r))
316    }
317    /// Remove items contained in the range.
318    pub fn remove(&mut self, range: (T, T))
319    where
320        T: Clone + Ord,
321    {
322        self.drain_with(range, |_| {});
323    }
324    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
325    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
326    where
327        T: Clone + Ord,
328        F: FnMut(&(T, T)) -> bool,
329    {
330        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
331    }

Source

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)

51    pub fn get_range_value(&self, key: &K) -> Option<(&(K, K), &V)>
52    where
53        K: Clone + Ord,
54    {
55        self.get_right_if(key, |r, _| key == &r.0)
56            .or_else(|| self.get_left_if(key, |r, _| key < &r.1))
57    }
58    /// Inserts values into the specified range.
59    pub fn insert(&mut self, range: (K, K), value: V)
60    where
61        K: Clone + Ord,
62        V: Clone + Eq,
63    {
64        self.insert_with(range, value, |_, _| {});
65    }
66    /// Insert values and operate old range-value pairs.
67    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
68    where
69        K: Clone + Ord,
70        V: Clone + Eq,
71        F: FnMut((K, K), V),
72    {
73        if range.0 >= range.1 {
74            return;
75        }
76        let mut ins_range = range.clone();
77        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
78            range.0 < r.1 || range.0 == r.1 && &value == v
79        }) {
80            if range.1 < r.1 {
81                if value == v {
82                    ins_range = r;
83                } else {
84                    self.map.insert((r.0, range.0.clone()), v.clone());
85                    self.map.insert((range.1.clone(), r.1), v.clone());
86                }
87                f(range.clone(), v);
88            } else {
89                if value == v {
90                    ins_range.0 = r.0;
91                } else {
92                    self.map.insert((r.0, range.0.clone()), v.clone());
93                }
94                if range.0 < r.1 {
95                    f((range.0.clone(), r.1), v);
96                }
97            }
98        }
99        let mut wait = None;
100        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
101            ins_range.1 = r.1;
102        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
103            if value == v {
104                ins_range.1 = r.1;
105            } else {
106                self.map.insert((range.1.clone(), r.1), v.clone());
107            }
108            wait = Some(((r.0, range.1.clone()), v));
109        }
110        let mut f = self.drain_with_inner(range, f);
111        if let Some((r, v)) = wait {
112            f(r, v);
113        }
114        self.map.insert(ins_range, value);
115    }
116    /// Remove values contained in the range.
117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }
302    /// Inserts into the specified range.
303    pub fn insert(&mut self, range: (T, T))
304    where
305        T: Clone + Ord,
306    {
307        self.insert_with(range, |_| {});
308    }
309    /// Insert and operate old range.
310    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
311    where
312        T: Clone + Ord,
313        F: FnMut((T, T)),
314    {
315        self.map.insert_with(range, (), |r, _| f(r))
316    }
317    /// Remove items contained in the range.
318    pub fn remove(&mut self, range: (T, T))
319    where
320        T: Clone + Ord,
321    {
322        self.drain_with(range, |_| {});
323    }
324    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
325    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
326    where
327        T: Clone + Ord,
328        F: FnMut(&(T, T)) -> bool,
329    {
330        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
331    }
332    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
333    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
334    where
335        T: Clone + Ord,
336        F: FnMut(&(T, T)) -> bool,
337    {
338        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
339    }

Source

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)

67    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
68    where
69        K: Clone + Ord,
70        V: Clone + Eq,
71        F: FnMut((K, K), V),
72    {
73        if range.0 >= range.1 {
74            return;
75        }
76        let mut ins_range = range.clone();
77        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
78            range.0 < r.1 || range.0 == r.1 && &value == v
79        }) {
80            if range.1 < r.1 {
81                if value == v {
82                    ins_range = r;
83                } else {
84                    self.map.insert((r.0, range.0.clone()), v.clone());
85                    self.map.insert((range.1.clone(), r.1), v.clone());
86                }
87                f(range.clone(), v);
88            } else {
89                if value == v {
90                    ins_range.0 = r.0;
91                } else {
92                    self.map.insert((r.0, range.0.clone()), v.clone());
93                }
94                if range.0 < r.1 {
95                    f((range.0.clone(), r.1), v);
96                }
97            }
98        }
99        let mut wait = None;
100        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
101            ins_range.1 = r.1;
102        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
103            if value == v {
104                ins_range.1 = r.1;
105            } else {
106                self.map.insert((range.1.clone(), r.1), v.clone());
107            }
108            wait = Some(((r.0, range.1.clone()), v));
109        }
110        let mut f = self.drain_with_inner(range, f);
111        if let Some((r, v)) = wait {
112            f(r, v);
113        }
114        self.map.insert(ins_range, value);
115    }
116    /// Remove values contained in the range.
117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }
302    /// Inserts into the specified range.
303    pub fn insert(&mut self, range: (T, T))
304    where
305        T: Clone + Ord,
306    {
307        self.insert_with(range, |_| {});
308    }
309    /// Insert and operate old range.
310    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
311    where
312        T: Clone + Ord,
313        F: FnMut((T, T)),
314    {
315        self.map.insert_with(range, (), |r, _| f(r))
316    }
317    /// Remove items contained in the range.
318    pub fn remove(&mut self, range: (T, T))
319    where
320        T: Clone + Ord,
321    {
322        self.drain_with(range, |_| {});
323    }
324    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
325    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
326    where
327        T: Clone + Ord,
328        F: FnMut(&(T, T)) -> bool,
329    {
330        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
331    }
332    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
333    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
334    where
335        T: Clone + Ord,
336        F: FnMut(&(T, T)) -> bool,
337    {
338        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
339    }
340    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
341    pub fn pop_left_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
342    where
343        T: Clone + Ord,
344        F: FnMut(&(T, T)) -> bool,
345    {
346        self.map.pop_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
347    }

Source

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)

67    pub fn insert_with<F>(&mut self, range: (K, K), value: V, mut f: F)
68    where
69        K: Clone + Ord,
70        V: Clone + Eq,
71        F: FnMut((K, K), V),
72    {
73        if range.0 >= range.1 {
74            return;
75        }
76        let mut ins_range = range.clone();
77        if let Some((r, v)) = self.pop_left_if(&range.0, |r, v| {
78            range.0 < r.1 || range.0 == r.1 && &value == v
79        }) {
80            if range.1 < r.1 {
81                if value == v {
82                    ins_range = r;
83                } else {
84                    self.map.insert((r.0, range.0.clone()), v.clone());
85                    self.map.insert((range.1.clone(), r.1), v.clone());
86                }
87                f(range.clone(), v);
88            } else {
89                if value == v {
90                    ins_range.0 = r.0;
91                } else {
92                    self.map.insert((r.0, range.0.clone()), v.clone());
93                }
94                if range.0 < r.1 {
95                    f((range.0.clone(), r.1), v);
96                }
97            }
98        }
99        let mut wait = None;
100        if let Some((r, _)) = self.pop_right_if(&range.1, |r, v| range.1 == r.0 && &value == v) {
101            ins_range.1 = r.1;
102        } else if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
103            if value == v {
104                ins_range.1 = r.1;
105            } else {
106                self.map.insert((range.1.clone(), r.1), v.clone());
107            }
108            wait = Some(((r.0, range.1.clone()), v));
109        }
110        let mut f = self.drain_with_inner(range, f);
111        if let Some((r, v)) = wait {
112            f(r, v);
113        }
114        self.map.insert(ins_range, value);
115    }
116    /// Remove values contained in the range.
117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }
302    /// Inserts into the specified range.
303    pub fn insert(&mut self, range: (T, T))
304    where
305        T: Clone + Ord,
306    {
307        self.insert_with(range, |_| {});
308    }
309    /// Insert and operate old range.
310    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
311    where
312        T: Clone + Ord,
313        F: FnMut((T, T)),
314    {
315        self.map.insert_with(range, (), |r, _| f(r))
316    }
317    /// Remove items contained in the range.
318    pub fn remove(&mut self, range: (T, T))
319    where
320        T: Clone + Ord,
321    {
322        self.drain_with(range, |_| {});
323    }
324    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
325    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
326    where
327        T: Clone + Ord,
328        F: FnMut(&(T, T)) -> bool,
329    {
330        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
331    }
332    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
333    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
334    where
335        T: Clone + Ord,
336        F: FnMut(&(T, T)) -> bool,
337    {
338        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
339    }
340    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
341    pub fn pop_left_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
342    where
343        T: Clone + Ord,
344        F: FnMut(&(T, T)) -> bool,
345    {
346        self.map.pop_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
347    }
348    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
349    pub fn pop_right_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
350    where
351        T: Clone + Ord,
352        F: FnMut(&(T, T)) -> bool,
353    {
354        self.map.pop_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
355    }

Source

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)

117    pub fn remove(&mut self, range: (K, K))
118    where
119        K: Clone + Ord,
120        V: Clone,
121    {
122        self.drain_with(range, |_, _| {});
123    }
124    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
125    pub fn get_left_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
126    where
127        K: Clone + Ord,
128        F: FnMut(&(K, K), &V) -> bool,
129    {
130        self.map
131            .range(..(key.clone(), key.clone()))
132            .next_back()
133            .filter(|(r, v)| pred(r, v))
134    }
135    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
136    pub fn get_right_if<F>(&self, key: &K, mut pred: F) -> Option<(&(K, K), &V)>
137    where
138        K: Clone + Ord,
139        F: FnMut(&(K, K), &V) -> bool,
140    {
141        self.map
142            .range((key.clone(), key.clone())..)
143            .next()
144            .filter(|(r, v)| pred(r, v))
145    }
146    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
147    pub fn pop_left_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
148    where
149        K: Clone + Ord,
150        F: FnMut(&(K, K), &V) -> bool,
151    {
152        match self.get_left_if(key, pred) {
153            Some((r, _)) => {
154                let r = r.clone();
155                let v = self.map.remove(&r).unwrap();
156                Some((r, v))
157            }
158            None => None,
159        }
160    }
161    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
162    pub fn pop_right_if<F>(&mut self, key: &K, pred: F) -> Option<((K, K), V)>
163    where
164        K: Clone + Ord,
165        F: FnMut(&(K, K), &V) -> bool,
166    {
167        match self.get_right_if(key, pred) {
168            Some((r, _)) => {
169                let r = r.clone();
170                let v = self.map.remove(&r).unwrap();
171                Some((r, v))
172            }
173            None => None,
174        }
175    }
176    /// Operate and consume range-value pairs in range when no overlapping.
177    fn drain_with_inner<F>(&mut self, range: (K, K), mut f: F) -> F
178    where
179        K: Clone + Ord,
180        F: FnMut((K, K), V),
181    {
182        while let Some((r, _)) = self
183            .map
184            .range((range.0.clone(), range.0.clone())..(range.1.clone(), range.1.clone()))
185            .next()
186        {
187            let r = r.clone();
188            let v = self.map.remove(&r).unwrap();
189            f(r, v);
190        }
191        f
192    }
193    /// Operate and consume range-value pairs in range.
194    pub fn drain_with<F>(&mut self, range: (K, K), mut f: F)
195    where
196        K: Clone + Ord,
197        V: Clone,
198        F: FnMut((K, K), V),
199    {
200        if let Some((r, v)) = self.pop_left_if(&range.0, |r, _| range.0 < r.1) {
201            if range.1 < r.1 {
202                f(range.clone(), v.clone());
203                self.map.insert((range.1.clone(), r.1), v.clone());
204            } else {
205                f((range.0.clone(), r.1), v.clone());
206            }
207            self.map.insert((r.0, range.0.clone()), v);
208        }
209        let mut wait = None;
210        if let Some((r, v)) = self.pop_left_if(&range.1, |r, _| range.1 < r.1) {
211            wait = Some(((r.0, range.1.clone()), v.clone()));
212            self.map.insert((range.1.clone(), r.1), v);
213        }
214        let mut f = self.drain_with_inner(range, f);
215        if let Some((r, v)) = wait {
216            f(r, v);
217        }
218    }
219    pub fn iter(&self) -> btree_map::Iter<'_, (K, K), V> {
220        self.map.iter()
221    }
222    pub fn iter_mut(&mut self) -> btree_map::IterMut<'_, (K, K), V> {
223        self.map.iter_mut()
224    }
225    pub fn keys(&self) -> btree_map::Keys<'_, (K, K), V> {
226        self.map.keys()
227    }
228    pub fn values(&self) -> btree_map::Values<'_, (K, K), V> {
229        self.map.values()
230    }
231    pub fn values_mut(&mut self) -> btree_map::ValuesMut<'_, (K, K), V> {
232        self.map.values_mut()
233    }
234}
235impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
236where
237    K: Clone + Ord,
238    V: Clone + Eq,
239{
240    fn extend<T: IntoIterator<Item = ((K, K), V)>>(&mut self, iter: T) {
241        for (range, value) in iter {
242            self.insert(range, value);
243        }
244    }
245}
246impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
247where
248    K: Clone + Ord,
249    V: Clone + Eq,
250{
251    fn from_iter<T: IntoIterator<Item = ((K, K), V)>>(iter: T) -> Self {
252        let mut map = Self::new();
253        map.extend(iter);
254        map
255    }
256}
257
258/// A set to control intervals.
259#[derive(Debug, Clone)]
260pub struct RangeSet<T> {
261    map: RangeMap<T, ()>,
262}
263impl<T> Default for RangeSet<T>
264where
265    T: Ord,
266{
267    fn default() -> Self {
268        Self {
269            map: Default::default(),
270        }
271    }
272}
273impl<T> RangeSet<T> {
274    /// Makes a new, empty `RangeSet`.
275    pub fn new() -> Self
276    where
277        T: Ord,
278    {
279        Default::default()
280    }
281    /// Clears the set, removing all elements.
282    pub fn clear(&mut self)
283    where
284        T: Ord,
285    {
286        self.map.clear();
287    }
288    /// Returns true if the set contains a key.
289    pub fn contains(&self, key: &T) -> bool
290    where
291        T: Clone + Ord,
292    {
293        self.get_range(key).is_some()
294    }
295    /// Returns the range corresponding to the key.
296    pub fn get_range(&self, key: &T) -> Option<&(T, T)>
297    where
298        T: Clone + Ord,
299    {
300        self.map.get_range_value(key).map(|(r, _)| r)
301    }
302    /// Inserts into the specified range.
303    pub fn insert(&mut self, range: (T, T))
304    where
305        T: Clone + Ord,
306    {
307        self.insert_with(range, |_| {});
308    }
309    /// Insert and operate old range.
310    pub fn insert_with<F>(&mut self, range: (T, T), mut f: F)
311    where
312        T: Clone + Ord,
313        F: FnMut((T, T)),
314    {
315        self.map.insert_with(range, (), |r, _| f(r))
316    }
317    /// Remove items contained in the range.
318    pub fn remove(&mut self, range: (T, T))
319    where
320        T: Clone + Ord,
321    {
322        self.drain_with(range, |_| {});
323    }
324    /// Get a left neighboring range of `[key, key)` if the predicate is satisfied.
325    pub fn get_left_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
326    where
327        T: Clone + Ord,
328        F: FnMut(&(T, T)) -> bool,
329    {
330        self.map.get_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
331    }
332    /// Get a right neighboring range of `[key, key)` if the predicate is satisfied.
333    pub fn get_right_if<F>(&self, key: &T, mut pred: F) -> Option<&(T, T)>
334    where
335        T: Clone + Ord,
336        F: FnMut(&(T, T)) -> bool,
337    {
338        self.map.get_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
339    }
340    /// Pop a left neighboring range of `[key, key)` if the predicate is satisfied.
341    pub fn pop_left_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
342    where
343        T: Clone + Ord,
344        F: FnMut(&(T, T)) -> bool,
345    {
346        self.map.pop_left_if(key, |r, _| pred(r)).map(|(r, _)| r)
347    }
348    /// Pop a right neighboring range of `[key, key)` if the predicate is satisfied.
349    pub fn pop_right_if<F>(&mut self, key: &T, mut pred: F) -> Option<(T, T)>
350    where
351        T: Clone + Ord,
352        F: FnMut(&(T, T)) -> bool,
353    {
354        self.map.pop_right_if(key, |r, _| pred(r)).map(|(r, _)| r)
355    }
356    /// Operate and consume in range.
357    pub fn drain_with<F>(&mut self, range: (T, T), mut f: F)
358    where
359        T: Clone + Ord,
360        F: FnMut((T, T)),
361    {
362        self.map.drain_with(range, |r, _| f(r));
363    }

Source

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

Source

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

Source

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

Examples found in repository ?

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

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

Source

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

Source

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

Trait Implementations§

Source §

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

Source §

fn clone(&self) -> RangeMap<K, V>

Returns a duplicate of the value. Read more

1.0.0 · Source§

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

Performs copy-assignment from source. Read more

Source §

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

Source §

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

Formats the value using the given formatter. Read more

Source §

impl<K, V> Default for RangeMap<K, V>
where K: Ord,

Source §

fn default() -> Self

Returns the “default value” for a type. Read more

Source §

impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where K: Clone + Ord, V: Clone + Eq,

Source §

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

Extends a collection with the contents of an iterator. Read more

Source §

fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

Source §

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. Read more

Source §

impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where K: Clone + Ord, V: Clone + Eq,

Source §

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

Creates a value from an iterator. Read more

Auto Trait Implementations§

§

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

§

impl<K, V> RefUnwindSafe for RangeMap<K, V>
where V: RefUnwindSafe, K: RefUnwindSafe,

§

impl<K, V> UnwindSafe for RangeMap<K, V>
where V: RefUnwindSafe, K: RefUnwindSafe,

Blanket Implementations§

Source §

impl<T> Any for T
where T: 'static + ?Sized,

Source §

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

Source §

impl<T> Borrow<T> for T
where T: ?Sized,

Source §

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

Source §

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source §

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

Source §

impl<T> CloneToUninit for T
where T: Clone,

Source §

unsafe fn clone_to_uninit(&self, dest: *mut u8)

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

Performs copy-assignment from self to dest. Read more

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

impl<T, U> Into for T
where U: From<T>,

Source §

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source §

impl<T> ToOwned for T
where T: Clone,

Source §

type Owned = T

The resulting type after obtaining ownership.

Source §

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more

Source §

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more

Source §

impl<T, U> TryFrom for T
where U: Into<T>,

Source §

type Error = Infallible

The type returned in the event of a conversion error.

Source §

fn try_from(value: U) -> Result<T, <T as TryFrom>::Error>

Performs the conversion.

Source §

impl<T, U> TryInto for T
where U: TryFrom<T>,

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

fn try_into(self) -> Result<U, >::Error>

Performs the conversion.

Struct RangeMapCopy item path

Implementations§

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

pub fn new() -> Selfwhere K: Ord,

pub fn clear(&mut self)where K: Ord,

pub fn contains_key(&self, key: &K) -> boolwhere K: Clone + Ord,

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

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

pub fn insert(&mut self, range: (K, K), value: V)where K: Clone + Ord, V: Clone + Eq,

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),

pub fn remove(&mut self, range: (K, K))where K: Clone + Ord, V: Clone,

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,

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,

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,

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,

pub fn drain_with<F>(&mut self, range: (K, K), f: F)where K: Clone + Ord, V: Clone, F: FnMut((K, K), V),

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>

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) -> RangeMap<K, V>

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

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

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

impl<K, V> Default for RangeMap<K, V>where K: Ord,

fn default() -> Self

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)

fn extend_one(&mut self, item: A)

fn extend_reserve(&mut self, additional: usize)

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

Auto Trait Implementations§

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

impl<K, V> RefUnwindSafe for RangeMap<K, V>where V: RefUnwindSafe, K: RefUnwindSafe,

impl<K, V> Send for RangeMap<K, V>where V: Send, K: Send,

impl<K, V> Sync for RangeMap<K, V>where V: Sync, K: Sync,

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

impl<K, V> UnwindSafe for RangeMap<K, V>where V: RefUnwindSafe, K: RefUnwindSafe,

Blanket Implementations§

impl<T> Any for Twhere T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for Twhere T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> CloneToUninit for Twhere T: Clone,

unsafe fn clone_to_uninit(&self, dest: *mut u8)

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for Twhere U: From<T>,

fn into(self) -> U

impl<T> ToOwned for Twhere T: Clone,

type Owned = T

fn to_owned(&self) -> T

fn clone_into(&self, target: &mut T)

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Struct RangeMap

pub fn new() -> Self
where K: Ord,

pub fn clear(&mut self)
where K: Ord,

pub fn contains_key(&self, key: &K) -> bool
where K: Clone + Ord,

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

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

pub fn insert(&mut self, range: (K, K), value: V)
where K: Clone + Ord, V: Clone + Eq,

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),

pub fn remove(&mut self, range: (K, K))
where K: Clone + Ord, V: Clone,

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,

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,

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,

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,

pub fn drain_with<F>(&mut self, range: (K, K), f: F)
where K: Clone + Ord, V: Clone, F: FnMut((K, K), V),

impl<K, V> Default for RangeMap<K, V>
where K: Ord,

impl<K, V> Extend<((K, K), V)> for RangeMap<K, V>
where K: Clone + Ord, V: Clone + Eq,

impl<K, V> FromIterator<((K, K), V)> for RangeMap<K, V>
where K: Clone + Ord, V: Clone + Eq,

impl<K, V> RefUnwindSafe for RangeMap<K, V>
where V: RefUnwindSafe, K: RefUnwindSafe,

impl<K, V> Send for RangeMap<K, V>
where V: Send, K: Send,

impl<K, V> Sync for RangeMap<K, V>
where V: Sync, K: Sync,

impl<K, V> UnwindSafe for RangeMap<K, V>
where V: RefUnwindSafe, K: RefUnwindSafe,

impl<T> Any for T
where T: 'static + ?Sized,

impl<T> Borrow<T> for T
where T: ?Sized,

impl<T> BorrowMut<T> for T
where T: ?Sized,

impl<T> CloneToUninit for T
where T: Clone,

impl<T, U> Into<U> for T
where U: From<T>,

impl<T> ToOwned for T
where T: Clone,

impl<T, U> TryFrom<U> for T
where U: Into<T>,

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,