drng/
lib.rs

1//! A disjoint range implementation.
2
3#![warn(missing_docs)]
4
5#[cfg(test)]
6extern crate quickcheck;
7#[cfg(test)]
8#[macro_use(quickcheck)]
9extern crate quickcheck_macros;
10
11mod range;
12pub use range::{range_compare, Range, RangeCompareResult, SimpleRange};
13
14/// An explanation of why an overlap error occurred while inserting to a
15/// [`DisjointRange`].
16#[allow(dead_code)]
17#[derive(Debug)]
18pub struct OverlapError {
19    kind: RangeCompareResult,
20}
21
22/// Possible errors when inserting a range to a [`DisjointRange`].
23#[derive(Debug)]
24pub enum AddError {
25    /// Insertion erred because the range to insert overlaps with an existing
26    /// range in [`DisjointRange`].
27    OverlapRange(OverlapError),
28    /// Insertion failed because the provided parameters does not form a vaild
29    /// range (e.g., when the start value is greater than the end value).
30    BadRange,
31}
32
33/// An enumeration of inclusive / exclusiveness on both ends of a range.
34#[derive(Debug, PartialEq, Eq, Copy, Clone)]
35pub enum RangeMode {
36    /// Range where the start and end are inclusive (i.e., [start..end]).
37    Inclusive,
38    /// Range where the start and end are exclusive (i.e., (start..end)).
39    Exclusive,
40    /// Range where the start is exclusive and the end is inclusive
41    /// (i.e., (start..end]).
42    StartExclusive,
43    /// Range where the start is inclusive and the end is exclusive
44    /// (i.e., [start..end)).
45    EndExclusive,
46}
47
48/// A data structure holding a disjoint set of ranges.
49///
50/// The following code snippet represents a set of ranges:
51///
52/// ```rust
53/// use drng::{DisjointRange, RangeMode};
54/// let mut dr = DisjointRange::new(RangeMode::Inclusive);
55///
56/// // not drawn to scale
57/// // 0.......[35..90][91..110]..[115, 120]
58///
59/// dr.add(35, 90).unwrap();
60/// dr.add(91, 110).unwrap();
61/// dr.add(115, 120).unwrap();
62///
63/// assert!(dr.includes(35));
64/// assert!(!dr.includes(113));
65/// ```
66pub struct DisjointRange {
67    inner: DisjointRangeInner<SimpleRange>,
68    mode: RangeMode,
69}
70
71impl DisjointRange {
72    /// Constructs a new [`DisjointRange`].
73    pub fn new(mode: RangeMode) -> Self {
74        Self {
75            inner: DisjointRangeInner::default(),
76            mode,
77        }
78    }
79
80    /// Adds a range to this [`DisjointRange`].
81    pub fn add(&mut self, min: usize, max: usize) -> Result<(), AddError> {
82        match SimpleRange::new(min, max, self.mode) {
83            Err(_) => Err(AddError::BadRange),
84            Ok(r) => self.inner.add(r),
85        }
86    }
87
88    /// Checks whether the given value falls into one of the ranges.
89    pub fn includes(&self, value: usize) -> bool {
90        self.inner.includes(value)
91    }
92
93    /// Checks if the data structure contains the provided value.
94    ///
95    /// If yes, return the range that contains this value.
96    pub fn lookup(&self, value: usize) -> Option<&SimpleRange> {
97        self.inner.lookup(value)
98    }
99
100    /// Iterates this [`DisjointRange`] in range-ascending order.
101    pub fn iter(&self) -> DisjointRangeIter<'_, SimpleRange> {
102        self.inner.iter()
103    }
104}
105
106struct DisjointRangeInner<R: Range> {
107    ranges: Vec<R>,
108}
109
110impl<R: Range> Default for DisjointRangeInner<R> {
111    fn default() -> Self {
112        Self { ranges: Vec::new() }
113    }
114}
115
116impl<R: Range> DisjointRangeInner<R> {
117    fn add(&mut self, range: R) -> Result<(), AddError> {
118        for (i, range_curr) in self.ranges.iter().enumerate() {
119            match range_compare(&range, range_curr) {
120                RangeCompareResult::GreaterNoOverlap => continue,
121                RangeCompareResult::LessThanNoOverlap => {
122                    self.ranges.insert(i, range);
123                    return Ok(());
124                }
125                r => return Err(AddError::OverlapRange(OverlapError { kind: r })),
126            }
127        }
128
129        self.ranges.push(range);
130
131        Ok(())
132    }
133
134    fn includes(&self, value: usize) -> bool {
135        self.lookup(value).is_some()
136    }
137
138    fn lookup(&self, value: usize) -> Option<&R> {
139        self.ranges.iter().find(|r| r.includes(value))
140    }
141
142    fn iter(&self) -> DisjointRangeIter<'_, R> {
143        DisjointRangeIter::new(self)
144    }
145}
146
147/// Iterates a [`DisjointRange`].
148pub struct DisjointRangeIter<'a, R: Range> {
149    dr: &'a DisjointRangeInner<R>,
150    curr: usize,
151}
152
153impl<'a, R: Range> DisjointRangeIter<'a, R> {
154    fn new(dr: &'a DisjointRangeInner<R>) -> DisjointRangeIter<'a, R> {
155        Self { dr, curr: 0 }
156    }
157}
158
159impl<'a, R: Range> Iterator for DisjointRangeIter<'a, R> {
160    type Item = &'a R;
161
162    fn next(&mut self) -> Option<Self::Item> {
163        match self.dr.ranges.get(self.curr) {
164            Some(range) => {
165                self.curr += 1;
166                Some(range)
167            }
168            None => None,
169        }
170    }
171}
172
173#[cfg(test)]
174use quickcheck::{Arbitrary, Gen};
175#[cfg(test)]
176use rand::Rng;
177
178#[cfg(test)]
179impl Arbitrary for RangeMode {
180    fn arbitrary(_g: &mut Gen) -> RangeMode {
181        let num: usize = rand::thread_rng().gen_range(0..3);
182        match num {
183            0 => RangeMode::Inclusive,
184            1 => RangeMode::Exclusive,
185            2 => RangeMode::StartExclusive,
186            3 => RangeMode::EndExclusive,
187            _ => unreachable!(),
188        }
189    }
190}
191
192#[cfg(test)]
193mod tests {
194    use super::*;
195    use quickcheck::{quickcheck, TestResult};
196    use rand::{thread_rng, Rng};
197
198    #[quickcheck]
199    fn prop_add_valid_range(min: usize, max: usize) -> TestResult {
200        let mut dr = DisjointRange::new(RangeMode::Inclusive);
201        match dr.add(min, max) {
202            Ok(_) => TestResult::from_bool(min <= max),
203            Err(_) => TestResult::discard(),
204        }
205    }
206
207    #[quickcheck]
208    fn prop_add_valid_ranges(ranges: Vec<(usize, usize)>) -> TestResult {
209        if ranges.len() < 10_000 {
210            return TestResult::discard();
211        }
212
213        let mut dr = DisjointRange::new(RangeMode::Inclusive);
214        for (min, max) in ranges {
215            if dr.add(min, max).is_err() {
216                return TestResult::discard();
217            }
218        }
219
220        TestResult::from_bool(
221            dr.iter()
222                .zip(dr.iter().skip(1))
223                .all(|(prev, curr)| curr.min() > prev.max()),
224        )
225    }
226
227    #[quickcheck]
228    fn prop_find_range_value(min: usize, max: usize) -> TestResult {
229        let mut dr = DisjointRange::new(RangeMode::Inclusive);
230        match dr.add(min, max) {
231            Err(_) => TestResult::discard(),
232            Ok(_) => {
233                if max == usize::MAX {
234                    return TestResult::discard();
235                }
236                const NUM_SAMPLES: usize = 100;
237                let mut rng = thread_rng();
238                TestResult::from_bool(
239                    (0..NUM_SAMPLES)
240                        .map(|_| rng.gen_range(min..(max + 1)))
241                        .all(|x| dr.lookup(x).is_some()),
242                )
243            }
244        }
245    }
246
247    #[test]
248    fn create_basic_dr() {
249        let sorted_sequence = [
250            [100, 200],
251            [222, 235],
252            [20000, 22322],
253            [34330, 50000],
254            [60000, 700000],
255        ];
256        let mut dr = DisjointRange::new(RangeMode::Inclusive);
257        insert_ranges(&mut dr, &sorted_sequence);
258        assert_range_sequence(&dr, &sorted_sequence);
259    }
260
261    #[test]
262    fn add_overlapping_range_errs() {
263        let mut dr = DisjointRange::new(RangeMode::Inclusive);
264        dr.add(100, 200).unwrap();
265        assert_insert_overlaps(dr.add(90, 111), RangeCompareResult::OverlapLower);
266        assert_insert_overlaps(dr.add(100, 123), RangeCompareResult::Contained);
267        assert_insert_overlaps(dr.add(140, 160), RangeCompareResult::Contained);
268        assert_insert_overlaps(dr.add(188, 200), RangeCompareResult::Contained);
269        assert_insert_overlaps(dr.add(100, 200), RangeCompareResult::Equal);
270        assert_insert_overlaps(dr.add(100, 300), RangeCompareResult::Contains);
271        assert_insert_overlaps(dr.add(73, 2000), RangeCompareResult::Contains);
272        assert_insert_overlaps(dr.add(180, 222), RangeCompareResult::OverlapUpper);
273        assert_insert_overlaps(dr.add(200, 222), RangeCompareResult::OverlapUpper);
274    }
275
276    #[test]
277    fn add_invalid_inclusive_range() {
278        let mut dr = DisjointRange::new(RangeMode::Inclusive);
279        assert_add_bad_range_errs(dr.add(100, 80));
280        assert!(dr.add(50, 50).is_ok());
281    }
282
283    #[test]
284    fn add_invalid_end_exclusive_range() {
285        let mut dr = DisjointRange::new(RangeMode::EndExclusive);
286        assert!(dr.add(9, 10).is_ok());
287        assert_add_bad_range_errs(dr.add(100, 80));
288        assert_add_bad_range_errs(dr.add(50, 50));
289    }
290
291    #[test]
292    fn add_invalid_start_exclusive_range() {
293        let mut dr = DisjointRange::new(RangeMode::StartExclusive);
294        assert!(dr.add(9, 10).is_ok());
295        assert_add_bad_range_errs(dr.add(100, 80));
296        assert_add_bad_range_errs(dr.add(50, 50));
297    }
298
299    #[test]
300    fn add_invalid_exclusive_range() {
301        let mut dr = DisjointRange::new(RangeMode::Exclusive);
302        assert_add_bad_range_errs(dr.add(100, 80));
303        assert_add_bad_range_errs(dr.add(50, 50));
304        assert_add_bad_range_errs(dr.add(49, 50));
305        assert!(dr.add(48, 50).is_ok());
306    }
307
308    #[test]
309    fn add_unordered_ranges() {
310        let mut dr = DisjointRange::new(RangeMode::Inclusive);
311        insert_ranges(
312            &mut dr,
313            &[
314                [100, 200],
315                [30, 50],
316                [1, 2],
317                [60, 66],
318                [500, 555],
319                [343, 444],
320            ],
321        );
322        assert_range_sequence(
323            &dr,
324            &[
325                [1, 2],
326                [30, 50],
327                [60, 66],
328                [100, 200],
329                [343, 444],
330                [500, 555],
331            ],
332        );
333    }
334
335    #[test]
336    fn end_exclusive_dr() {
337        let mut dr = DisjointRange::new(RangeMode::EndExclusive);
338        insert_ranges(
339            &mut dr,
340            &[
341                [100, 200],
342                [99, 100],
343                [98, 99],
344                [30, 50],
345                [50, 70],
346                [70, 90],
347                [211, 212],
348                [209, 211],
349            ],
350        );
351        assert_range_sequence(
352            &dr,
353            &[
354                [30, 50],
355                [50, 70],
356                [70, 90],
357                [98, 99],
358                [99, 100],
359                [100, 200],
360                [209, 211],
361                [211, 212],
362            ],
363        );
364    }
365
366    #[test]
367    fn find_value_in_range() {
368        let mut dr = DisjointRange::new(RangeMode::EndExclusive);
369
370        dr.add(100, 200).unwrap();
371        assert!(dr.includes(100));
372        assert!(dr.includes(105));
373        assert!(dr.includes(199));
374        assert!(!dr.includes(200));
375        assert!(!dr.includes(201));
376        assert!(!dr.includes(3));
377        assert!(!dr.includes(30000));
378    }
379
380    #[test]
381    fn lookup_range() {
382        let mut dr = DisjointRange::new(RangeMode::EndExclusive);
383
384        insert_ranges(&mut dr, &[[100, 200], [300, 4500]]);
385
386        let found_fst = dr.lookup(199).unwrap();
387        assert_range_min_max(found_fst, 100, 200);
388
389        assert!(dr.lookup(200).is_none());
390        assert!(dr.lookup(248).is_none());
391
392        let found_snd = dr.lookup(344).unwrap();
393        assert_range_min_max(found_snd, 300, 4500);
394    }
395
396    fn insert_ranges(dr: &mut DisjointRange, seq: &[[usize; 2]]) {
397        seq.iter().for_each(|[min, max]| {
398            dr.add(*min, *max)
399                .unwrap_or_else(|_| panic!("failed to insert min: {}, max: {}", min, max));
400        })
401    }
402
403    fn assert_range_sequence(dr: &DisjointRange, seq: &[[usize; 2]]) {
404        let mut dr_iter = dr.iter();
405        let mut deq_iter = seq.iter();
406
407        loop {
408            match dr_iter.next() {
409                None => match deq_iter.next() {
410                    None => break,
411                    Some(r) => panic!(
412                        "Reached disjoint range end while the expected \
413                               next range is {:?}",
414                        r
415                    ),
416                },
417                Some(got) => match deq_iter.next() {
418                    None => panic!(
419                        "Disjoint range longer than expected; \
420                                   got {:?} while expected sequence ended",
421                        got
422                    ),
423                    Some([expected_min, expected_max]) => {
424                        assert_range_min_max(got, *expected_min, *expected_max)
425                    }
426                },
427            }
428        }
429    }
430
431    fn assert_range_min_max(range: &dyn Range, min: usize, max: usize) {
432        assert_eq!(range.min(), min);
433        assert_eq!(range.max(), max);
434    }
435
436    fn assert_add_bad_range_errs(add_result: Result<(), AddError>) {
437        match add_result {
438            Ok(_) => panic!("add bad range should fail"),
439            Err(e) => match e {
440                AddError::BadRange => (),
441                _ => panic!("expected bad range, got {:?}", e),
442            },
443        }
444    }
445
446    fn assert_insert_overlaps(add_result: Result<(), AddError>, kind: RangeCompareResult) {
447        match add_result {
448            Ok(_) => panic!("expected add to fail"),
449            Err(e) => match e {
450                AddError::OverlapRange(x) => assert_eq!(x.kind, kind),
451                _ => panic!("expected overlap range error, got {:?}", e),
452            },
453        }
454    }
455}
drng/lib.rs

drng/
lib.rs
