rb_interval_map/
interval.rs

1//! The `Interval` stored in `IntervalMap` and represents the interval [low, high)
2//!
3//! `interval_map` supports `insert`, `delete`, and `iter` fns. Traversal is performed in the order of `Interval<T>` . For instance, with intervals of type `Interval<u32>`:
4//! - [1,4)<[2,5), because 1<2
5//! - [1,4)<[1,5), because 4<5
6//!
7//! So the order of intervals in `IntervalMap` is [1,4)<[1,5)<[2,5).
8//!
9//! Currently, `interval_map` only supports half-open intervals, i.e., [...,...).
10
11use std::fmt::{Display, Formatter};
12
13#[cfg(feature = "serde")]
14use serde::{Deserialize, Deserializer, Serialize, Serializer};
15
16/// The interval stored in `IntervalMap` represents [low, high)
17#[non_exhaustive]
18#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
19pub struct Interval<T> {
20    /// Low value
21    pub low: T,
22    /// high value
23    pub high: T,
24}
25
26impl<T: Ord> Interval<T> {
27    /// Create a new `Interval`
28    ///
29    /// # Panics
30    ///
31    /// This method panics when low >= high
32    #[inline]
33    pub fn new(low: T, high: T) -> Self {
34        assert!(low < high, "invalid range");
35        Self { low, high }
36    }
37
38    /// Checks if self overlaps with other interval
39    #[inline]
40    pub fn overlaps(&self, other: &Self) -> bool {
41        self.high > other.low && other.high > self.low
42    }
43
44    /// Checks if self contains other interval
45    /// e.g. [1,10) contains [1,8)
46    #[inline]
47    pub fn contains(&self, other: &Self) -> bool {
48        self.low <= other.low && self.high > other.high
49    }
50
51    /// Checks if self contains a point
52    pub fn contains_point(&self, p: T) -> bool {
53        self.low <= p && self.high > p
54    }
55}
56
57impl<T: Display> Display for Interval<T> {
58    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
59        write!(f, "[{},{})", self.low, self.high)
60    }
61}
62
63/// Reference type of `Interval`
64#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
65pub struct IntervalRef<'a, T> {
66    /// Low value
67    low: &'a T,
68    /// high value
69    high: &'a T,
70}
71
72impl<'a, T: Ord> IntervalRef<'a, T> {
73    /// Create a new `IntervalRef`
74    ///
75    /// # Panics
76    ///
77    /// This method panics when low >= high
78    #[inline]
79    pub fn new(low: &'a T, high: &'a T) -> Self {
80        assert!(low < high, "invalid range");
81        Self { low, high }
82    }
83
84    /// Check if self overlaps with a `Interval<T>`
85    pub fn overlap(&self, other: &Interval<T>) -> bool {
86        self.high > &other.low && &other.high > self.low
87    }
88}
89
90#[cfg(feature = "serde")]
91impl<T: Serialize> Serialize for Interval<T> {
92    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
93        (&self.low, &self.high).serialize(serializer)
94    }
95}
96
97#[cfg(feature = "serde")]
98impl<'de, T> Deserialize<'de> for Interval<T>
99where
100    T: Deserialize<'de>,
101{
102    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
103        let (low, high) = <(T, T)>::deserialize(deserializer)?;
104        Ok(Interval { low, high })
105    }
106}
107
108#[cfg(test)]
109mod test {
110    use super::*;
111
112    #[test]
113    #[should_panic(expected = "invalid range")]
114    fn invalid_range_should_panic() {
115        let _interval = Interval::new(3, 1);
116    }
117
118    #[test]
119    fn test_interval_clone() {
120        let interval1 = Interval::new(1, 10);
121        let interval2 = interval1.clone();
122        assert_eq!(interval1, interval2);
123    }
124
125    #[test]
126    fn test_interval_compare() {
127        let interval1 = Interval::new(1, 10);
128        let interval2 = Interval::new(5, 15);
129        assert!(interval1 < interval2);
130        assert!(interval2 > interval1);
131        assert_eq!(interval1, Interval::new(1, 10));
132        assert_ne!(interval1, interval2);
133    }
134
135    #[test]
136    fn test_interval_hash() {
137        let interval1 = Interval::new(1, 10);
138        let interval2 = Interval::new(1, 10);
139        let interval3 = Interval::new(5, 15);
140        let mut hashset = std::collections::HashSet::new();
141        hashset.insert(interval1);
142        hashset.insert(interval2);
143        hashset.insert(interval3);
144        assert_eq!(hashset.len(), 2);
145    }
146
147    #[cfg(feature = "serde")]
148    #[test]
149    fn test_interval_serialize_deserialize() {
150        let interval = Interval::new(1, 10);
151        let serialized = serde_json::to_string(&interval).unwrap();
152        let deserialized: Interval<i32> = serde_json::from_str(&serialized).unwrap();
153        assert_eq!(interval, deserialized);
154    }
155}
rb_interval_map/interval.rs

rb_interval_map/
interval.rs
