Struct ranges::Ranges

pub struct Ranges<T: Domain> { /* fields omitted */ }

A range set storing GenericRanges in the most memory-optimal fashion possible.

The two guarantees of storing ranges disjoint and sorted allows for the following optimizations:

• keeping them ordered, upper and lower bounds for searches can be used to keep the search space as small as possible
• storing them disjoint is a by-product of automatically merging newly inserted ranges, which additionally helps to reduce reindexing of the internal vector

Implementations

impl<T: Domain> Ranges<T>

#[must_use]pub fn contains(&self, item: &T) -> bool

Returns true if the given item is contained in any of the internal disjoint ranges.

Note

In contrast to the GenericRange constructor, item values will not be clamped to the domain and immediately return false if outside of it.

Example

use ranges::Ranges;

let ranges = Ranges::from(vec![0..3, 5..10]);
assert!(ranges.contains(&2));
assert!(ranges.contains(&7));
assert!(!ranges.contains(&4));

impl<T: Domain> Ranges<T>

#[must_use]pub fn difference<R>(self, other: R) -> Self where
    R: Into<Self>, 

Calculates the relative complement (difference) of two ranges.

Examples

Overlapping ranges:

use ranges::Ranges;

let ranges1 = Ranges::from(0..5);
let ranges2 = 3..8;

 assert_eq!(ranges1 - ranges2, (0..3).into());

Equal ranges:

use ranges::Ranges;

let ranges1 = Ranges::from(0..10);
let ranges2 = 0..10;

assert!((ranges1 - ranges2).is_empty());

impl<T: Domain> Ranges<T>

pub fn insert<R>(&mut self, range: R) -> bool where
    R: Into<GenericRange<T>>, 

Returns true if any element or the internal vector was modified to accommodate range. This means false is returned if and only if nothing has changed.

Examples

Empty:

use ranges::Ranges;

let mut ranges = Ranges::new();
assert!(ranges.insert(0..3));
assert_eq!(ranges, (0..3).into())

Collision with internal expansion of existing entry:

use ranges::Ranges;

let mut ranges = Ranges::from(0..3);
assert!(ranges.insert(2..5));
assert_eq!(ranges, (0..5).into())

No change in internal vector:

use ranges::Ranges;

let mut ranges = Ranges::from(0..10);
assert!(!ranges.insert(3..7));
assert_eq!(ranges, (0..10).into())

impl<T: Domain> Ranges<T>

#[must_use]pub fn intersect<R>(self, other: R) -> Self where
    R: Into<Self>, 

Calculates the intersection of two ranges.

Examples

Single overlapping ranges:

use ranges::Ranges;

let ranges1 = Ranges::from(0..5);
let ranges2 = 3..8;

assert_eq!(ranges1 & ranges2, (3..5).into());

Multiple overlapping ranges:

use ranges::{GenericRange, Ranges};

let ranges1 = Ranges::from(0..9);
let ranges2 = Ranges::from(vec![-1..3, 6..11]);

assert_eq!(ranges1 & ranges2, vec![0..3, 6..9].into())

impl<T: Domain> Ranges<T>

#[must_use]pub fn invert(self) -> Self

Inverts the range set.

Examples

Empty set:

use ranges::Ranges;

assert_eq!(!Ranges::<usize>::new(), Ranges::full());

Single entry:

use ranges::{GenericRange, Ranges};

let ranges = Ranges::from(0..10);
assert_eq!(
    !ranges,
    vec![GenericRange::new_less_than(0), GenericRange::new_at_least(10)].into()
);

Multiple entries:

use ranges::{GenericRange, Ranges};

let ranges = Ranges::from(vec![GenericRange::from(0..10), (15..=20).into()]);
assert_eq!(
    !ranges,
    vec![
        GenericRange::new_less_than(0),
        (10..15).into(),
        GenericRange::new_greater_than(20)
    ].into()
);

impl<T: Domain> Ranges<T>

pub fn remove<R>(&mut self, range: R) -> bool where
    R: Into<GenericRange<T>>, 

Returns true if any element or the internal vector was modified to remove range. This means false is returned if and only if nothing has changed.

Examples

Empty set.

use ranges::Ranges;

let mut ranges = Ranges::new();
assert!(!ranges.remove(0..3));

Single entry but no collision.

use ranges::Ranges;

let mut ranges = Ranges::from(0..3);
assert!(!ranges.remove(5..10));
assert_eq!(ranges, (0..3).into())

Single entry with collision in the middle.

use ranges::{GenericRange, Ranges};

let mut ranges = Ranges::from(0..10);
assert!(ranges.remove(2..5));
assert_eq!(ranges, vec![0..2, 5..10].into())

impl<T: Domain> Ranges<T>

#[must_use]pub fn symmetric_difference<R>(self, other: R) -> Self where
    R: Into<Self>, 

Calculates the relative complement (difference) of two ranges.

Examples

Empty range.

use ranges::Ranges;

let ranges1 = Ranges::new();
let ranges2 = 0..10;

assert_eq!(ranges1 ^ ranges2, (0..10).into());

Touching ranges.

use ranges::Ranges;

let ranges1 = Ranges::from(0..3);
let ranges2 = 3..8;

assert_eq!(ranges1 ^ ranges2, (0..8).into());

Overlapping multiple ranges.

use ranges::{GenericRange, Ranges};

let ranges1 = Ranges::from(vec![0..5, 6..9]);
let ranges2 = 3..8;

assert_eq!(
    ranges1 ^ ranges2,
    vec![0..3, 5..6, 8..9].into()
);

impl<T: Domain> Ranges<T>

#[must_use]pub fn union<R>(self, other: R) -> Self where
    R: Into<Self>, 

Calculates the union of two ranges.

Examples

Empty and single-entry ranges.

use ranges::Ranges;

let ranges1 = Ranges::new();
let ranges2 = 0..10;

assert_eq!(ranges1 | ranges2, (0..10).into());

Disjoint ranges.

use ranges::Ranges;

let ranges1 = Ranges::from(0..3);
let ranges2 = 5..8;

assert_eq!(ranges1 | ranges2, vec![0..3, 5..8].into());

Overlapping ranges.

use ranges::Ranges;

let ranges1 = Ranges::from(vec![0..5, 6..9]);
let ranges2 = 3..8;

assert_eq!(ranges1 | ranges2, (0..9).into());

impl<T: Domain> Ranges<T>

#[must_use]pub fn new() -> Self

Creates a new empty Ranges with an initial capacity of 0.

#[must_use]pub fn with_capacity(capacity: usize) -> Self

Initializes the underlying vector with a given capacity.

#[must_use]pub fn full() -> Self

Initializes the underlying vector with a single full range.

#[must_use]pub fn is_full(&self) -> bool where
    T: PartialEq, 

Returns true if the whole domain is in this range.

#[must_use]pub fn len(&self) -> usize

Returns the amount of saved disjoint ranges.

#[must_use]pub fn is_empty(&self) -> bool

Returns true if there are no ranges and we have an empty set.

#[must_use]pub fn find_intersecting_ranges(
    &self,
    other: &GenericRange<T>
) -> Option<(usize, usize)>

Find the GenericRanges in self which at least touch other.

Since other is a GenericRange (i.e. contiguous), the overlapping ranges must all be consecutive. Therefore, this only returns the indices of the first and last ranges which overlap.

This returns a (start, end) pair of indices into self.ranges.

Example

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)))

#[must_use]pub fn as_slice(&self) -> &[GenericRange<T>]

Returns the internal vector of GenericRanges as a slice.

Trait Implementations

impl<T, I> Add<I> for Ranges<T> where
    I: Into<GenericRange<T>>,
    T: Domain, 

This calls self.insert(other).

type Output = Self

The resulting type after applying the + operator.

#[must_use]fn add(self, rhs: I) -> Self::Output

Performs the + operation.

impl<T, I> AddAssign<I> for Ranges<T> where
    I: Into<GenericRange<T>>,
    T: Domain, 

This calls self.insert(other).

fn add_assign(&mut self, rhs: I)

Performs the += operation.

impl<T: Domain> AsRef<Vec<GenericRange<T>>> for Ranges<T>

fn as_ref(&self) -> &Vec<GenericRange<T>>

Performs the conversion.

impl<T: Binary + Domain> Binary for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, I> BitAnd<I> for Ranges<T> where
    I: Into<Ranges<T>>,
    T: Domain, 

This calls self.intersect(other).

type Output = Self

The resulting type after applying the & operator.

#[must_use]fn bitand(self, rhs: I) -> Self::Output

Performs the & operation.

impl<T: Domain> BitAndAssign<Ranges<T>> for Ranges<T>

This calls self.intersect(other) and replaces self with the result.

fn bitand_assign(&mut self, rhs: Ranges<T>)

Performs the &= operation.

impl<T, I> BitOr<I> for Ranges<T> where
    I: Into<Ranges<T>>,
    T: Domain, 

This calls self.union(other).

type Output = Self

The resulting type after applying the | operator.

#[must_use]fn bitor(self, rhs: I) -> Self::Output

Performs the | operation.

impl<T, I> BitOrAssign<I> for Ranges<T> where
    I: Into<Ranges<T>>,
    T: Domain, 

This calls self.union(other) and replaces self with the result.

fn bitor_assign(&mut self, rhs: I)

Performs the |= operation.

impl<T, I> BitXor<I> for Ranges<T> where
    I: Into<Ranges<T>>,
    T: Domain, 

This calls self.symmetric_difference(other).

type Output = Self

The resulting type after applying the ^ operator.

#[must_use]fn bitxor(self, rhs: I) -> Self::Output

Performs the ^ operation.

impl<T, I> BitXorAssign<I> for Ranges<T> where
    I: Into<Ranges<T>>,
    T: Domain, 

This calls self.symmetric_difference(other) and replaces self with the result.

fn bitxor_assign(&mut self, rhs: I)

Performs the ^= operation.

impl<T: Clone + Domain> Clone for Ranges<T>

fn clone(&self) -> Ranges<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Domain> Debug for Ranges<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default + Domain> Default for Ranges<T>

fn default() -> Ranges<T>

Returns the "default value" for a type.

impl<T: Display + Domain> Display for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Eq + Domain> Eq for Ranges<T>

impl<T: Domain, U> From<U> for Ranges<T> where
    U: Into<GenericRange<T>>, 

#[must_use]fn from(r: U) -> Self

Performs the conversion.

impl<T: Domain, U> From<Vec<U>> for Ranges<T> where
    U: Into<GenericRange<T>>, 

#[must_use]fn from(v: Vec<U>) -> Self

Performs the conversion.

impl<T: Domain> FromIterator<GenericRange<T>> for Ranges<T>

fn from_iter<I: IntoIterator<Item = GenericRange<T>>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Hash + Domain> Hash for Ranges<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<T: LowerExp + Domain> LowerExp for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: LowerHex + Domain> LowerHex for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Domain> Not for Ranges<T>

This calls self.invert().

type Output = Self

The resulting type after applying the ! operator.

#[must_use]fn not(self) -> Self::Output

Performs the unary ! operation.

impl<T: Octal + Domain> Octal for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialEq + Domain> PartialEq<Ranges<T>> for Ranges<T>

fn eq(&self, other: &Ranges<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Ranges<T>) -> bool

This method tests for !=.

impl<T: Pointer + Domain> Pointer for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Domain> StructuralEq for Ranges<T>

impl<T: Domain> StructuralPartialEq for Ranges<T>

impl<T, I> Sub<I> for Ranges<T> where
    I: Into<GenericRange<T>>,
    T: Domain, 

This calls self.remove(other).

type Output = Self

The resulting type after applying the - operator.

#[must_use]fn sub(self, rhs: I) -> Self::Output

Performs the - operation.

impl<T: Domain> Sub<Ranges<T>> for Ranges<T>

This calls self.difference(other).

type Output = Self

The resulting type after applying the - operator.

#[must_use]fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<T, I> SubAssign<I> for Ranges<T> where
    I: Into<GenericRange<T>>,
    T: Domain, 

This calls self.remove(other).

fn sub_assign(&mut self, rhs: I)

Performs the -= operation.

impl<T: Domain> SubAssign<Ranges<T>> for Ranges<T>

This calls self.difference(other) and replaces self with the result.

fn sub_assign(&mut self, rhs: Ranges<T>)

Performs the -= operation.

impl<T: UpperExp + Domain> UpperExp for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: UpperHex + Domain> UpperHex for Ranges<T>

Non-Debug formatting uses interval notation and formats the bound values according to the given formatting arguments.

Note

Unless disabled by using the - formatting argument, a whitespace will be printed after the bound separator. Because there is currently no use for -, it will have no effect on the underlying bound values. This might change if requested or core/std makes use of it.

Examples

Single entries. These are formatted like a single GenericRange.

use ranges::Ranges;

assert_eq!(format!("{}", Ranges::from(1..2)), "{1}");
assert_eq!(format!("{}", Ranges::from(1..=2)), "[1, 2]");
assert_eq!(format!("{}", Ranges::from(42..)), "[42, 2147483647]");
assert_eq!(format!("{:03}", Ranges::from(1..2)), "{001}");
assert_eq!(format!("{:02X}", Ranges::from(1..=10)), "[01, 0A]");
assert_eq!(format!("{:-#}", Ranges::from(42..=100)), "[42,100]");

Multiple entries. ∅ is used for an empty set and ∪ is used to concatenate disjoint entries.

use ranges::Ranges;

let mut ranges = Ranges::from(..6);
ranges.insert(7..=7);
ranges.insert(9..=9);
ranges.insert(15..);
assert_eq!(
    format!("{}", ranges),
    "[-2147483648, 6) \u{222a} {7, 9} \u{222a} [15, 2147483647]"
);

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.