Skip to main content

Module gaps

range_set_blaze

Module gaps 

Source
Expand description

§Ranges and gaps

RangeSetBlaze and RangeMapBlaze store integers as a sorted list of ranges instead of individual integers, and they always merge neighboring or overlapping ranges as you insert. So a RangeSetBlaze built from 1..=3 and 7..=10 holds exactly those two ranges — no more, no fewer. Everything else — 4..=6, and everything below 1 or above 10 — is a gap: a run of integers not covered by any range.

§Table of Contents

§RangeSetBlaze

§range_at: only present ranges

Suppose you want to find which range a value belongs to. RangeSetBlaze::range_at returns the maximal range containing value:

use range_set_blaze::RangeSetBlaze;

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
assert_eq!(set.range_at(2), Some(1..=3));

What if the value isn’t in any range? range_at returns None:

use range_set_blaze::RangeSetBlaze;

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
assert_eq!(set.range_at(5), None); // 5 is in the gap between the two ranges

§range_or_gap_at: present range or gap

What if you want the gap itself, instead of None? RangeSetBlaze::range_or_gap_at always returns the maximal range containing value, as (range, bool) where true means present:

use range_set_blaze::RangeSetBlaze;

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
assert_eq!(set.range_or_gap_at(5), (4..=6, false)); // the gap between the two ranges

A gap also extends to the domain’s own bounds, so a query below the first range or above the last one returns the leading or trailing gap:

use range_set_blaze::RangeSetBlaze;

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
assert_eq!(set.range_or_gap_at(i8::MIN), (i8::MIN..=0, false));
assert_eq!(set.range_or_gap_at(i8::MAX), (11..=i8::MAX, false));

§fill_gaps: fill gaps with false

RangeSetBlaze::fill_gaps builds a new RangeMapBlaze<T, bool> with an entry for every integer, not just the ones in the original set: true for values that were present, false for values that were in a gap.

use range_set_blaze::{RangeMapBlaze, RangeSetBlaze};

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
let filled_set = set.fill_gaps();
assert_eq!(
    filled_set,
    RangeMapBlaze::from_iter([
        (i8::MIN..=0, false),
        (1..=3, true),
        (4..=6, false),
        (7..=10, true),
        (11..=i8::MAX, false),
    ])
);

§Streaming fill_gaps for RangeSetBlaze

If the whole materialized RangeMapBlaze is not needed, SortedDisjoint::fill_gaps streams the same result lazily from a set stream such as set.ranges(), yielding (range, bool) and including the leading and trailing gaps:

use range_set_blaze::{RangeSetBlaze, SortedDisjoint};

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
let mut set_stream = set.ranges().fill_gaps();
assert_eq!(set_stream.next(), Some((i8::MIN..=0, false)));
assert_eq!(set_stream.next(), Some((1..=3, true)));
assert_eq!(set_stream.next(), Some((4..=6, false)));
assert_eq!(set_stream.next(), Some((7..=10, true)));
assert_eq!(set_stream.next(), Some((11..=i8::MAX, false)));
assert_eq!(set_stream.next(), None);

§RangeMapBlaze

§range_at: only mapped ranges

What if this is a map instead of a set? RangeMapBlaze::range_at works the same way, returning the maximal range and its value:

use range_set_blaze::RangeMapBlaze;

let map = RangeMapBlaze::from_iter([(1_i8..=3, "red"), (7..=10, "blue")]);
assert_eq!(map.range_at(2), Some((1..=3, &"red")));
assert_eq!(map.range_at(5), None); // 5 is in the gap between the two ranges

§range_or_gap_at: mapped range or gap

RangeMapBlaze::range_or_gap_at is the map counterpart of range_or_gap_at above: it always returns the maximal range containing key, as (range, Option<&V>) where Some means mapped:

use range_set_blaze::RangeMapBlaze;

let map = RangeMapBlaze::from_iter([(1_i8..=3, "red"), (7..=10, "blue")]);
assert_eq!(map.range_or_gap_at(5), (4..=6, None)); // the gap between the two ranges
assert_eq!(map.range_or_gap_at(8), (7..=10, Some(&"blue")));

§fill_gaps: fill gaps with None

RangeMapBlaze::fill_gaps builds a new RangeMapBlaze<T, Option<V>> with an entry for every integer, not just the ones in the original map: Some(value) for keys that were mapped, None for keys that were in a gap.

use range_set_blaze::RangeMapBlaze;

let map = RangeMapBlaze::from_iter([(1_i8..=3, "red"), (7..=10, "blue")]);
let filled_map = map.fill_gaps();
assert_eq!(
    filled_map,
    RangeMapBlaze::from_iter([
        (i8::MIN..=0, None),
        (1..=3, Some("red")),
        (4..=6, None),
        (7..=10, Some("blue")),
        (11..=i8::MAX, None),
    ])
);

§Streaming fill_gaps for RangeMapBlaze

If the whole materialized RangeMapBlaze is not needed, SortedDisjointMap::fill_gaps streams the same result lazily from a map stream such as map.range_values(), yielding (range, Option<&V>) and borrowing the original values instead of cloning them:

use range_set_blaze::{RangeMapBlaze, SortedDisjointMap};

let map = RangeMapBlaze::from_iter([(1_i8..=3, "red"), (7..=10, "blue")]);
let mut map_stream = map.range_values().fill_gaps();
assert_eq!(map_stream.next(), Some((i8::MIN..=0, None)));
assert_eq!(map_stream.next(), Some((1..=3, Some(&"red"))));
assert_eq!(map_stream.next(), Some((4..=6, None)));
assert_eq!(map_stream.next(), Some((7..=10, Some(&"blue"))));
assert_eq!(map_stream.next(), Some((11..=i8::MAX, None)));
assert_eq!(map_stream.next(), None);

§A filled map has an entry for every integer

After fill_gaps, false/None are just ordinary values sitting in the map — the map itself now has a key for every integer, with no gaps left at all. This matters if you then apply the ! (complement) operator, since ! on a RangeMapBlaze means “the keys not in this map,” not “flip each bool/Option value.” Because a filled map already has every key, its complement is always empty — it does not flip true to false:

use range_set_blaze::RangeSetBlaze;

let set = RangeSetBlaze::from_iter([1_i8..=3, 7..=10]);
let filled_set = set.fill_gaps();
assert!((!filled_set).is_empty()); // not the Boolean negation you might expect

Structs§

FillGapsIter
An iterator that fills the gaps in a sorted, disjoint set stream.
FillGapsIterMap
An iterator that fills the gaps in a sorted, disjoint map stream.