#range #no-std #set

no-std ranges

This crate provides a generic alternative to core/std ranges, set-operations to work with them and a range set that can efficiently store them with the least amount of memory possible

4 releases

0.3.3 May 22, 2021
0.3.2 Jan 4, 2021
0.3.1 Aug 30, 2020
0.3.0 Jun 23, 2020
0.1.0 Jan 13, 2020

#54 in Algorithms

Download history 276/week @ 2021-09-25 275/week @ 2021-10-02 194/week @ 2021-10-09 388/week @ 2021-10-16 300/week @ 2021-10-23 132/week @ 2021-10-30 201/week @ 2021-11-06 572/week @ 2021-11-13 196/week @ 2021-11-20 50/week @ 2021-11-27 64/week @ 2021-12-04 90/week @ 2021-12-11 145/week @ 2021-12-18 99/week @ 2021-12-25 75/week @ 2022-01-01 72/week @ 2022-01-08

399 downloads per month

LGPL-3.0-or-later

340KB
7K SLoC

Ranges

Docs Crates.io License Deps.rs Build Status Code Coverage

Matrix

Ranges is a generic replacement for the core/std range types.

Overview

GenericRange

This is the main replacement for core/std ranges with provided From implementations. The only difference is, that T needs to implement Domain and consequently Ord.

The start needs to be less or equal to end to uphold certain guarantees and allow for more optimization.

Ranges

This is a vector-backed range/interval set storing generic ranges in a ordered and always disjoint fashion.

Domain

This is the helper trait that defines the properties of a type and the domain it is in. It is already implemented for all primitive integers, char and bool. Additionally there are implementations using feature gates for noisy_float and num-bigint.

The default implementation of this trait is written in a way, that continuous types need no further code (except, if applicable, their min- and maximum). Discrete-only methods panic by default and are never called by the library if the DISCRETE constant is false (which it is by default).

Examples

More examples can be found in the documentation.

GenericRange
  • from core/std ranges:
    use ranges::GenericRange;
    
    let generic = GenericRange::from(1..5);
    assert_eq!(generic.start_bound(), Bound::Included(&1));
    assert_eq!(generic.end_bound(), Bound::Excluded(&5));
    
  • overlapping union:
    use ranges::{GenericRange, OperationResult};
    
    let range = GenericRange::from(0..10);
    let range2 = 5..=15;
    
    assert_eq!(range | range2, OperationResult::Single((0..=15).into()));
    
Ranges
  • find contained intersecting ranges:
    use ranges::Ranges;
    
    let ranges = Ranges::from(vec![0..5, 10..20, 25..30, 45..50]);
    assert_eq!(ranges.find_intersecting_ranges(&(7..47).into()), Some((1, 3)));
    
  • contains an item:
    use ranges::Ranges;
    
    let ranges = Ranges::from(vec![0..3, 5..10]);
    assert!(ranges.contains(&2));
    assert!(ranges.contains(&7));
    assert!(!ranges.contains(&4));
    
Domain

Example implementation for a Domain allowing only values between 0 and 100:

use ranges::Domain;

struct LimitedInt(u8);

impl LimitedInt {
    const MIN: u8 = 0;
    const MAX: u8 = 100;
}

impl Domain for LimitedInt {
    fn predecessor(&self) -> Option<Self> {
        match self {
            Self::MIN => None,
            _ => Some(self - 1),
        }
    }

    fn successor(&self) -> Option<Self> {
        match self {
            Self::MAX => None,
            _ => Some(self + 1),
        }
    }

    fn minimum() -> Bound<Self> {
        Bound::Included(Self::MIN)
    }


    fn maximum() -> Bound<Self> {
        Bound::Included(Self::MAX)
    }
}

#[test]
fn clamp_to_domain() {
    let range = GenericRange::<LimitedInt>::from(0..200);
    assert!(range, (0..=100).into());
}

Notes

The feature arbitrary allows creating arbitrary GenericRanges and Ranges which will always uphold the guarantees described above e.g. for use in fuzzers.

Dependencies

~0–530KB
~11K SLoC

(`