subranges 0.3.3

Library to manage non-interssecting integer intervals
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

use std::{cmp, fmt, ops::Range};

/// Represent integer interval.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Interval {
    start: u64,
    length: u64,
}

impl Interval {
    /// Create new interval [`start`; start + length).
    pub fn new(start: u64, length: u64) -> Self {
        Self { start, length }
    }

    /// Length of interval. Count of integers in `self`.
    pub fn len(&self) -> u64 {
        self.length
    }

    /// True if self.len() == 0.
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    /// First intager in `self`.
    pub fn start(&self) -> u64 {
        self.start
    }

    /// Integer after last integer in `self`.
    pub fn end(&self) -> u64 {
        self.start + self.length
    }

    /// Return `true` if `self` contains `p`. Else `false`.
    pub fn contains(&self, p: u64) -> bool {
        p >= self.start && p < self.end()
    }

    /// Test if `other` has got common integers with `self`.
    pub fn intersect(&self, other: &Self) -> bool {
        let connected = self.connect(other);
        connected.length < (self.length + other.length)
    }

    /// Return `true` if no integers between `self` and `other` exists.
    pub fn near(&self, other: &Self) -> bool {
        let connected = self.connect(other);
        connected.length <= (self.length + other.length)
    }

    /// Return interval from min `start` to max `end`.
    pub fn connect(&self, other: &Self) -> Self {
        let min_start = cmp::min(self.start, other.start);
        let max_end = cmp::max(self.end(), other.end());
        Interval::new(min_start, max_end - min_start)
    }

    /// Split `self` into two intervals.
    /// First - `[self.start; self.start + length)`, second - `[self.start + length; self.end)`.
    /// # Panics
    /// * Panics if `length` > `self.length`
    pub fn split(&self, length: u64) -> (Self, Self) {
        let left = Self::new(self.start, length);
        let right = Self::new(self.start + length, self.length - length);
        (left, right)
    }

    /// If intervals is near, return their union. Else `None`.
    pub fn try_join(&self, other: &Self) -> Option<Self> {
        match self.near(other) {
            true => Some(self.connect(other)),
            false => None,
        }
    }

    /// Return iterator over integers in `self`.
    pub fn iter(&self) -> impl Iterator<Item = u64> {
        self.start()..self.end()
    }
}

impl From<Range<u64>> for Interval {
    fn from(r: Range<u64>) -> Self {
        Interval::new(r.start, r.end - r.start)
    }
}

impl fmt::Display for Interval {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "[{}, {})", self.start(), self.end())
    }
}

#[cfg(test)]
mod tests {
    use crate::interval::Interval;

    #[test]
    fn connect() {
        let i1 = Interval::new(0, 10);
        let i2 = Interval::new(15, 10);
        let conn = i1.connect(&i2);
        assert_eq!(conn.start(), i1.start());
        assert_eq!(conn.end(), i2.end());

        let conn_refl = i2.connect(&i1);
        assert_eq!(conn, conn_refl);
    }

    #[test]
    fn split() {
        let i = Interval::new(0, 10);
        let sp = 3;
        let (s1, s2) = i.split(sp);
        assert_eq!(s1.start(), i.start());
        assert_eq!(s1.len(), sp);
        assert_eq!(s2.len(), i.len() - s1.len());
        assert_eq!(s2.start(), s1.end())
    }

    #[test]
    fn join() {
        let i1 = Interval::new(0, 10);
        let i2 = Interval::new(5, 10);
        let i3 = Interval::new(20, 10);
        let join = i1.try_join(&i2).unwrap();
        assert_eq!(join.start(), i1.start());
        assert_eq!(join.end(), i2.end());

        let join_refl = i2.try_join(&i1).unwrap();
        assert_eq!(join, join_refl);

        assert!(i1.try_join(&i3).is_none());
        assert!(i3.try_join(&i1).is_none());
    }

    #[test]
    fn test_iter() {
        let i = Interval::new(0, 3);
        let mut iter = i.iter();
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), None);
    }
}