Struct nested_intervals::IntervalSet

pub struct IntervalSet { /* fields omitted */ }

IntervalSet

A collection of Range and associated ids (u32).

If no ids are supplied, default ones will be provided. Merging functions return sorted ids Little assumption is placed on the intervals, they may overlap and nest. They must be start <= end though.

Our ranges are like Rust ranges, left closed, right open.

Internal storage is sorted by (start, -end), which is enforced at construction time.

Methods

impl IntervalSet

pub fn new(intervals: &[Range<u32>]) -> Result<IntervalSet, NestedIntervalError>

Create an IntervalSet without supplying ids

ids will be 0..n in the order of the sorted intervals

pub fn new_with_ids(
    intervals: &[Range<u32>],
    ids: &[u32]
) -> Result<IntervalSet, NestedIntervalError>

Create an IntervalSet

Ids may be non-unique This consumes both the intervals and ids which should safe an allocation in the most common use case

pub fn len(&self) -> usize

How many intervals are there?

pub fn is_empty(&self) -> bool

Is the number of intervals 0?

pub fn has_overlap(
    &mut self,
    query: &Range<u32>
) -> Result<bool, NestedIntervalError>

Is there any interval overlapping with the query?

pub fn iter(&self) -> Zip<Iter<Range<u32>>, Iter<Vec<u32>>>

create an iterator over (Range<u32>, &vec![id]) tuples.

pub fn query_overlapping(&mut self, query: &Range<u32>) -> IntervalSet

retrieve a new IntervalSet with all intervals overlapping the query

pub fn any_overlapping(&self) -> bool

does this IntervalSet contain overlapping intervals?

pub fn overlap_status(&self) -> Vec<bool>

which intervals are overlapping?

Result is a Vec

pub fn any_nested(&mut self) -> bool

does this IntervalSet contain nested intervals?

pub fn remove_duplicates(&self) -> IntervalSet

remove intervals that have the same coordinates

Ids are not merged, the first set is being kept

pub fn remove_empty(&self) -> IntervalSet

remove empty intervals, ie. those with start == end

pub fn merge_hull(&self) -> IntervalSet

Merge overlapping & nested intervals to their outer bounds

Examples:

• 0..15, 10..20 -> 0..20
• 0..20, 3..5 -> 0..20

pub fn merge_connected(&self) -> IntervalSet

Merge intervals that are butted up against each other

This first induces a merge_hull()!

Examples:

• 0..15, 15..20 -> 0..20
• 0..15, 16..20, 20..30 > 0..15, 16..30

pub fn merge_drop(&self) -> IntervalSet

Remove all intervals that are overlapping or nested by simply dropping them.

Examples:

• 0..20, 10..15, 20..35, 30..40, 40..50 -> 40..50

Ids of the remaining intervals are unchanged

pub fn merge_split(&mut self) -> IntervalSet

Create fully disjoint intervals by splitting the existing ones based on their overlap.

Example:

• 0..20, 10..30 -> 0..10, 10..20, 20..30

Ids are merged, ie. in the above example, if the input ids are [[0], [1]], the output ids are [[0], [0,1], [1]]

merge_split on an already disjoint set is a no-op

pub fn find_closest_start_left(
    &mut self,
    pos: u32
) -> Option<(Range<u32>, Vec<u32>)>

find the interval with the closest start to the left of pos None if there are no intervals to the left of pos

pub fn find_closest_start_right(
    &mut self,
    pos: u32
) -> Option<(Range<u32>, Vec<u32>)>

find the interval with the closest start to the right of pos None if there are no intervals to the right of pos

pub fn find_closest_start(&mut self, pos: u32) -> Option<(Range<u32>, Vec<u32>)>

find the interval with the closest start to pos

None if the IntervalSet is empty On a tie, the left interval wins.

pub fn covered_units(&mut self) -> u32

how many units does this IntervalSet cover

pub fn mean_interval_size(&self) -> f64

What is the mean size of the intervals

pub fn invert(&self, lower_bound: u32, upper_bound: u32) -> IntervalSet

Invert the intervals in this set

Actual applied lower_bound is min(lower_bound, first_interval_start) Actual applied upper_bound is max(upper_bound, last_interval_end)

Examples

• invert([15..20], 0, 30) -> [0..15, 20..30]
• invert([15..20], 20, 30) -> [0..15, 20..30]

Ids are lost

pub fn filter_to_overlapping(&mut self, other: &mut IntervalSet) -> IntervalSet

Filter to those intervals that have an overlap in other.

pub fn filter_to_non_overlapping(
    &mut self,
    other: &mut IntervalSet
) -> IntervalSet

Filter to those intervals that have no overlap in other.

pub fn filter_to_overlapping_k_others(
    &mut self,
    others: &[&IntervalSet],
    min_k: u32
) -> IntervalSet

Filter to those intervals that have an overlap in at least k others.

pub fn filter_to_non_overlapping_k_others(
    &mut self,
    others: &[&IntervalSet],
    max_k: u32
) -> IntervalSet

Filter to those intervals that have an overlap in no more than k others

pub fn union(&self, others: Vec<&IntervalSet>) -> IntervalSet

Build the union of two IntervalSets

No merging is performed

Trait Implementations

impl Clone for IntervalSet

fn clone(&self) -> IntervalSet

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Eq for IntervalSet

impl PartialEq<IntervalSet> for IntervalSet

fn eq(&self, other: &IntervalSet) -> bool

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl Debug for IntervalSet

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

Formats the value using the given formatter.