interval_map/
lib.rs

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

interval_map/
lib.rs
