nekolib/ds/
interval_map.rs

1//! 区間から値への対応づけ。
2
3use std::cmp::Ordering::{self, Equal, Greater, Less};
4use std::collections::BTreeMap;
5use std::fmt::{self, Debug};
6use std::ops::Bound::{Excluded, Included, Unbounded};
7use std::ops::RangeBounds;
8
9#[derive(Clone, Copy, Eq, PartialEq)]
10enum Left<T> {
11    NegInfinity,
12    Closed(T),
13    Open(T),
14}
15
16#[derive(Clone, Copy, Eq, PartialEq)]
17enum Right<T> {
18    Open(T),
19    Closed(T),
20    PosInfinity,
21}
22
23impl<T: Debug> Debug for Left<T> {
24    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
25        match self {
26            Left::NegInfinity => write!(f, "(-oo"),
27            Left::Closed(x) => write!(f, "[{:?}", x),
28            Left::Open(x) => write!(f, "({:?}", x),
29        }
30    }
31}
32
33impl<T: Debug> Debug for Right<T> {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            Right::Open(x) => write!(f, "{:?})", x),
37            Right::Closed(x) => write!(f, "{:?}]", x),
38            Right::PosInfinity => write!(f, "oo)"),
39        }
40    }
41}
42
43impl<T> Left<T> {
44    pub fn inner(&self) -> Option<&T> {
45        match self {
46            Left::Open(x) | Left::Closed(x) => Some(x),
47            Left::NegInfinity => None,
48        }
49    }
50}
51
52impl<T> Right<T> {
53    pub fn inner(&self) -> Option<&T> {
54        match self {
55            Right::PosInfinity => None,
56            Right::Closed(x) | Right::Open(x) => Some(x),
57        }
58    }
59}
60
61impl<T: Ord> Ord for Left<T> {
62    fn cmp(&self, other: &Self) -> Ordering {
63        use Left::{Closed, NegInfinity, Open};
64        match (self, other) {
65            (NegInfinity, NegInfinity) => Equal,
66            (NegInfinity, _) => Less,
67            (_, NegInfinity) => Greater,
68            (Closed(x), Open(y)) if x == y => Less,
69            (Open(x), Closed(y)) if x == y => Greater,
70            _ => self.inner().unwrap().cmp(other.inner().unwrap()),
71        }
72    }
73}
74
75impl<T: Ord> PartialOrd for Left<T> {
76    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
77        Some(self.cmp(other))
78    }
79}
80
81impl<T: Ord> Ord for Right<T> {
82    fn cmp(&self, other: &Self) -> Ordering {
83        use Right::{Closed, Open, PosInfinity};
84        match (self, other) {
85            (PosInfinity, PosInfinity) => Equal,
86            (_, PosInfinity) => Less,
87            (PosInfinity, _) => Greater,
88            (Open(x), Closed(y)) if x == y => Less,
89            (Closed(x), Open(y)) if x == y => Greater,
90            _ => self.inner().unwrap().cmp(other.inner().unwrap()),
91        }
92    }
93}
94
95impl<T: Ord> PartialOrd for Right<T> {
96    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
97        Some(self.cmp(other))
98    }
99}
100
101#[derive(Clone, Copy, Eq, PartialEq)]
102pub struct Interval<T> {
103    left: Left<T>,
104    right: Right<T>,
105}
106
107impl<T: Debug> Debug for Interval<T> {
108    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
109        write!(f, "{:?}, {:?}", self.left, self.right)
110    }
111}
112
113impl<T: Ord> Ord for Interval<T> {
114    fn cmp(&self, other: &Self) -> Ordering {
115        self.left.cmp(&other.left).then_with(|| self.right.cmp(&other.right))
116    }
117}
118
119impl<T: Ord> PartialOrd for Interval<T> {
120    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
121        Some(self.cmp(other))
122    }
123}
124
125impl<T: Ord + Clone> Interval<T> {
126    pub fn from_bounds(b: impl RangeBounds<T>) -> Self {
127        let left = match b.start_bound() {
128            Unbounded => Left::NegInfinity,
129            Included(x) => Left::Closed(x.clone()),
130            Excluded(x) => Left::Open(x.clone()),
131        };
132        let right = match b.end_bound() {
133            Excluded(x) => Right::Open(x.clone()),
134            Included(x) => Right::Closed(x.clone()),
135            Unbounded => Right::PosInfinity,
136        };
137        Self { left, right }
138    }
139}
140
141impl<T: Ord> Interval<T> {
142    pub fn inf(&self) -> Option<&T> { self.left.inner() }
143    pub fn sup(&self) -> Option<&T> { self.right.inner() }
144
145    pub fn is_empty(&self) -> bool {
146        match (&self.left, &self.right) {
147            (Left::NegInfinity, _) => false,
148            (_, Right::PosInfinity) => false,
149            (Left::Closed(x), Right::Closed(y)) => x > y,
150            _ => self.inf().unwrap() >= self.sup().unwrap(),
151        }
152    }
153    pub fn intersects(&self, other: &Self) -> bool {
154        let (left, right) =
155            if self < other { (self, other) } else { (other, self) };
156        match (&right.left, &left.right) {
157            (Left::NegInfinity, _) => true,
158            (_, Right::PosInfinity) => true,
159            (Left::Closed(x), Right::Closed(y)) => x <= y,
160            _ => right.inf().unwrap() < left.sup().unwrap(),
161        }
162    }
163    pub fn is_connected_with(&self, other: &Self) -> bool {
164        let (left, right) =
165            if self < other { (self, other) } else { (other, self) };
166        match (&right.left, &left.right) {
167            (Left::NegInfinity, _) => true,
168            (_, Right::PosInfinity) => true,
169            (Left::Open(x), Right::Open(y)) => x < y,
170            _ => right.inf().unwrap() <= left.sup().unwrap(),
171        }
172    }
173    pub fn is_subset_of(&self, other: &Self) -> bool {
174        //      [--- self ---]
175        // [------- other -------]
176        other.left <= self.left && self.right <= other.right
177    }
178    pub fn is_superset_of(&self, other: &Self) -> bool {
179        // [------- self -------]
180        //    [--- other ---]
181        self.left <= other.left && other.right <= self.right
182    }
183
184    pub fn intersection(self, other: Self) -> Option<Interval<T>> {
185        let (left, right) =
186            if self < other { (self, other) } else { (other, self) };
187        Some(Interval { left: right.left, right: left.right })
188            .filter(|it| !it.is_empty())
189    }
190    pub fn connection(self, other: Self) -> Option<Interval<T>> {
191        let (left, right) =
192            if self < other { (self, other) } else { (other, self) };
193        if !left.is_connected_with(&right) {
194            return None;
195        }
196        Some(Interval { left: left.left, right: right.right })
197    }
198}
199
200impl<T: Ord + Clone> Interval<T> {
201    pub fn intersection_minus(
202        self,
203        other: Self,
204    ) -> (Option<Interval<T>>, Vec<Interval<T>>) {
205        if !self.intersects(&other) {
206            return (None, vec![self]);
207        }
208        if self.is_subset_of(&other) {
209            return (Some(self), vec![]);
210        }
211        if self.is_superset_of(&other) {
212            // [-----   self   ------]
213            //     [-- other ---]
214            // ======================
215            // [mi][intersection][nus]
216            let isx = other.clone();
217            let Interval { left: ll, right: lr } = self;
218            let Interval { left: rl, right: rr } = other;
219            let minus_left = {
220                let tmp = match rl {
221                    Left::NegInfinity => None,
222                    Left::Closed(x) => Some(Right::Open(x)),
223                    Left::Open(x) => Some(Right::Closed(x)),
224                };
225                tmp.map(|right| Interval { left: ll, right })
226                    .filter(|it| !it.is_empty())
227            };
228            let minus_right = {
229                let tmp = match rr {
230                    Right::Open(x) => Some(Left::Closed(x)),
231                    Right::Closed(x) => Some(Left::Open(x)),
232                    Right::PosInfinity => None,
233                };
234                tmp.map(|left| Interval { left, right: lr })
235                    .filter(|it| !it.is_empty())
236            };
237
238            let isx = if isx.is_empty() { None } else { Some(isx) };
239            let minus: Vec<_> =
240                minus_left.into_iter().chain(minus_right).collect();
241            return (isx, minus);
242        }
243        let swap = self > other;
244        let (left, right) = if swap { (other, self) } else { (self, other) };
245        // [--- self ---]
246        //          [--- other ---]
247        // ========================
248        // [ minus ][isx]
249        let Interval { left: ll, right: lr } = left;
250        let Interval { left: rl, right: rr } = right;
251        let minus = if swap {
252            let left = match lr.clone() {
253                Right::Open(x) => Left::Closed(x),
254                Right::Closed(x) => Left::Open(x),
255                Right::PosInfinity => unreachable!(),
256            };
257            Interval { left, right: rr }
258        } else {
259            let right = match rl.clone() {
260                Left::NegInfinity => unreachable!(),
261                Left::Closed(x) => Right::Open(x),
262                Left::Open(x) => Right::Closed(x),
263            };
264            Interval { left: ll, right }
265        };
266        let isx = Interval { left: rl, right: lr };
267        (Some(isx), vec![minus])
268    }
269}
270
271/// 区間から値への対応づけ。
272///
273/// # Examples
274/// `todo!()`
275#[derive(Clone)]
276pub struct IntervalMap<K, V> {
277    inner: BTreeMap<Interval<K>, V>,
278}
279
280impl<K: Ord + Clone, V: Eq + Clone> IntervalMap<K, V> {
281    /// $S\\gets\\emptyset$ で初期化する。
282    pub fn new() -> Self { Self { inner: BTreeMap::new() } }
283
284    /// $S=\\emptyset$ を返す。
285    pub fn is_empty(&self) -> bool { self.inner.is_empty() }
286
287    /// 区間 `b` 中の各 $k$ に対して $S\\xleftarrow{\\cup} (k\\mapsto v)$ で更新する。
288    pub fn insert<B: RangeBounds<K>>(&mut self, b: B, v: V) {
289        let mut it = Interval::from_bounds(b);
290        if it.is_empty() || self.contains_internal(&it, &v) {
291            return;
292        }
293        self.remove_internal(it.clone());
294        self.connect(&mut it, &v);
295        self.inner.insert(it, v);
296    }
297
298    /// 区間 `b` 中の各 $k$ に対して $S\\xleftarrow{\\setminus} (k\\mapsto\\bullet)$
299    /// で更新する。
300    pub fn remove<B: RangeBounds<K>>(&mut self, b: B) -> Vec<(Interval<K>, V)> {
301        let it = Interval::from_bounds(b);
302        if it.is_empty() {
303            return vec![];
304        }
305        self.remove_internal(it)
306    }
307
308    fn contains_internal(&self, it: &Interval<K>, v: &V) -> bool {
309        // it の superset である区間が含まれており、その値が v なら true
310        (self.inner.range(it..).next())
311            .into_iter()
312            .chain(self.inner.range(..it).next_back())
313            .any(|(ki, vi)| ki.is_superset_of(it) && vi == v)
314    }
315
316    fn remove_internal(&mut self, it: Interval<K>) -> Vec<(Interval<K>, V)> {
317        let mut rm = self.remove_subset_of(&it);
318        rm.extend(self.remove_intersection_of(it));
319        rm.sort_unstable_by(|l, r| l.0.cmp(&r.0));
320        rm
321    }
322
323    fn remove_subset_of(&mut self, it: &Interval<K>) -> Vec<(Interval<K>, V)> {
324        // it の subset である区間を削除し、それを返す
325        let rm: Vec<_> = (self.inner.range(it..))
326            .take_while(|(ki, _)| ki.is_subset_of(it))
327            .chain(
328                (self.inner.range(..it).rev())
329                    .take_while(|(ki, _)| ki.is_subset_of(it)),
330            )
331            .map(|(ki, vi)| (ki.clone(), vi.clone()))
332            .collect();
333        for (k, _) in &rm {
334            self.inner.remove(k);
335        }
336        rm
337    }
338
339    fn remove_intersection_of(
340        &mut self,
341        it: Interval<K>,
342    ) -> Vec<(Interval<K>, V)> {
343        // it と intersection を持つ区間を削除し、それを返す。
344        // ただし、it の subset はすでに削除済みとする
345        let mut rm = vec![];
346        if let Some((ki, _)) = self.inner.range(&it..).next() {
347            if it.intersects(ki) {
348                let ki = ki.clone();
349                let vi = self.inner.remove(&ki).unwrap();
350                let (isx, minus) = ki.intersection_minus(it.clone());
351                for k in minus {
352                    self.inner.insert(k, vi.clone());
353                }
354                rm.push((isx.unwrap(), vi));
355            }
356        }
357        if let Some((ki, _)) = self.inner.range(..&it).next_back() {
358            if it.intersects(ki) {
359                let ki = ki.clone();
360                let vi = self.inner.remove(&ki).unwrap();
361                let (isx, minus) = ki.intersection_minus(it);
362                for k in minus {
363                    self.inner.insert(k, vi.clone());
364                }
365                rm.push((isx.unwrap(), vi));
366            }
367        }
368        rm
369    }
370
371    fn connect(&mut self, it: &mut Interval<K>, v: &V) {
372        // it の両隣にくる区間の値が v であればそれらを削除し、
373        // it につなげる。
374        if let Some((ki, vi)) = self.inner.range(&*it..).next() {
375            if vi == v && it.is_connected_with(ki) {
376                let ki = ki.clone();
377                self.inner.remove(&ki);
378                it.right = ki.right;
379            }
380        }
381        if let Some((ki, vi)) = self.inner.range(..&*it).next_back() {
382            if vi == v && it.is_connected_with(ki) {
383                let ki = ki.clone();
384                self.inner.remove(&ki);
385                it.left = ki.left;
386            }
387        }
388    }
389
390    /// $T\\subseteq S$ かつ `b` を含む $T$ があれば、その $T$
391    /// および対応する値を返す。
392    pub fn superset_of<B: RangeBounds<K>>(
393        &self,
394        b: B,
395    ) -> Option<(&Interval<K>, &V)> {
396        let it = Interval::from_bounds(b);
397        if self.inner.is_empty() || it.is_empty() {
398            return None;
399        }
400        (self.inner.range(..&it).next_back().into_iter())
401            .chain(self.inner.range(&it..).next())
402            .find(|(ki, _)| ki.is_superset_of(&it))
403    }
404
405    pub fn iter(
406        &self,
407    ) -> impl Iterator<Item = (&Interval<K>, &V)> + DoubleEndedIterator + '_
408    {
409        self.inner.iter()
410    }
411}
412
413impl<'a, K: Ord, V: Eq> IntoIterator for &'a IntervalMap<K, V> {
414    type Item = (&'a Interval<K>, &'a V);
415    type IntoIter = std::collections::btree_map::Iter<'a, Interval<K>, V>;
416    fn into_iter(self) -> Self::IntoIter { self.inner.iter() }
417}
418
419impl<K: Ord, V: Eq> IntoIterator for IntervalMap<K, V> {
420    type Item = (Interval<K>, V);
421    type IntoIter = std::collections::btree_map::IntoIter<Interval<K>, V>;
422    fn into_iter(self) -> Self::IntoIter { self.inner.into_iter() }
423}
424
425impl<K: Ord + Debug, V: Debug> Debug for IntervalMap<K, V> {
426    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
427        fmt.debug_map().entries(self.inner.iter()).finish()
428    }
429}
nekolib/ds/interval_map.rs

nekolib/ds/
interval_map.rs
