Struct DisjointIntervals 

pub struct DisjointIntervals<T> { /* private fields */ }

互いに素な区間を管理するデータ構造

Implementations

impl<T> DisjointIntervals<T>

where T: Ord + Clone + Copy,

pub fn new() -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn iter(&self) -> impl Iterator<Item = Range<T>>

pub fn insert<U, F>(&mut self, interval: Range<T>, init: U, f: F) -> U

where F: FnMut(U, InsertItem<T>) -> U,

区間を追加する

初期値 init, 関数 f による畳み込み結果を返す

Examples

use disjoint_intervals::{DisjointIntervals, InsertItem};

let mut intervals = DisjointIntervals::<i32>::new();
intervals.insert(-10..5, (), |_, _| ());
let overlapped = intervals.insert(0..10, 0, |acc, item| {
    if let InsertItem::Overlap(item) = item {
       acc + (item.end - item.start)
    } else {
       acc
    }
});
assert_eq!(overlapped, 5);

assert_eq!(intervals.iter().collect::<Vec<_>>(), vec![-10..10]);

pub fn remove<U, F>(&mut self, interval: Range<T>, init: U, f: F) -> U

where F: FnMut(U, RemoveItem<T>) -> U,

区間を削除する

初期値 init, 関数 f による畳み込み結果を返す

Examples

use disjoint_intervals::{DisjointIntervals, RemoveItem};

let mut intervals = DisjointIntervals::<i32>::new();
intervals.insert(-10..5, (), |_, _| ());
let removed = intervals.remove(-5..10, 0, |acc, item| {
    if let RemoveItem::Remove(item) = item {
       acc + (item.end - item.start)
    } else {
       acc
    }
});
assert_eq!(removed, 10);

assert_eq!(intervals.iter().collect::<Vec<_>>(), vec![-10..-5]);

pub fn ge(&self, x: T) -> Option<Range<T>>

x 以上の開始点を持つ最初の区間を返す

Examples

use disjoint_intervals::DisjointIntervals;

let mut intervals = DisjointIntervals::<i32>::new();
intervals.insert(0..5, (), |_, _| ());
intervals.insert(10..15, (), |_, _| ());

assert_eq!(intervals.ge(0), Some(0..5));
assert_eq!(intervals.ge(3), Some(10..15));
assert_eq!(intervals.ge(15), None);

pub fn le(&self, x: T) -> Option<Range<T>>

x 以下の開始点を持つ最後の区間を返す

Examples

use disjoint_intervals::DisjointIntervals;

let mut intervals = DisjointIntervals::<i32>::new();
intervals.insert(0..5, (), |_, _| ());
intervals.insert(10..15, (), |_, _| ());

assert_eq!(intervals.le(12), Some(10..15));
assert_eq!(intervals.le(10), Some(10..15));
assert_eq!(intervals.le(5), Some(0..5));
assert_eq!(intervals.le(-1), None);

Trait Implementations

impl<T: Clone> Clone for DisjointIntervals<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for DisjointIntervals<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for DisjointIntervals<T>

where T: Ord + Clone + Copy,

fn default() -> Self

Returns the “default value” for a type.

impl<T: PartialEq> PartialEq for DisjointIntervals<T>

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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for DisjointIntervals<T>

impl<T> StructuralPartialEq for DisjointIntervals<T>