Struct intspan::IntSpan

pub struct IntSpan { /* private fields */ }

IntSpan handles of sets containing integer spans.

SYNOPSIS

use intspan::IntSpan;

let mut ints = IntSpan::new();
for i in vec![1, 2, 3, 5, 7, 9] {
    ints.add_n(i);
}
ints.add_pair(100, 10000);
ints.remove_n(1000);

let expected = "1-3,5,7,9,100-999,1001-10000";
assert_eq!(ints.to_string(), expected);
assert_eq!(ints.cardinality(), 9906);
assert_eq!(ints.is_empty(), false);
assert_eq!(ints.is_universal(), false);
assert_eq!(ints.is_infinite(), false);
assert_eq!(ints.is_finite(), true);
assert_eq!(ints.is_pos_inf(), false);
assert_eq!(ints.is_neg_inf(), false);

let ints = IntSpan::from("1-3,5,7,9,100-999,1001-10000");
assert_eq!(ints.to_string(), "1-3,5,7,9,100-999,1001-10000");
assert_eq!(ints.cardinality(), 9906);

DESCRIPTION

IntSpan (ints for abbr.) represents sets of integers as a number of inclusive ranges, for example 1-10,19-23,45-48. Because many of its operations involve linear searches of the list of ranges its overall performance tends to be proportional to the number of distinct ranges. This is fine for small sets but suffers compared to other possible set representations (bit vectors, hash keys) when the number of ranges grows large.

This module also represents sets as ranges of values but stores those ranges in order and uses a binary search for many internal operations so that overall performance tends towards O log N where N is the number of ranges.

The internal representation used by this module is extremely simple: a set is represented as a list of integers. Integers in even numbered positions (0, 2, 4 etc) represent the start of a run of numbers while those in odd numbered positions represent the ends of runs. As an example the set (1, 3-7, 9, 11, 12) would be represented internally as (1, 2, 3, 8, 11, 13).

Sets may be infinite - assuming you’re prepared to accept that infinity is actually no more than a fairly large integer. Specifically the constants neg_inf and pos_inf are defined to be (-2^31+1) and (2^31-2) respectively. To create an infinite set invert an empty one:

let mut ints = IntSpan::new();
ints.invert();
let expected = format!("{}-{}", ints.get_neg_inf(), ints.get_pos_inf());
assert_eq!(ints.to_string(), expected);
assert_eq!(ints.is_empty(), false);
assert_eq!(ints.is_universal(), true);
assert_eq!(ints.is_infinite(), true);
assert_eq!(ints.is_finite(), false);
assert_eq!(ints.is_pos_inf(), true);
assert_eq!(ints.is_neg_inf(), true);

Sets need only be bounded in one direction - for example this is the set of all positive integers (assuming you accept the slightly feeble definition of infinity we’re using):

let mut ints = IntSpan::new();
ints.add_pair(1, ints.get_pos_inf());
let expected = format!("{}-{}", 1, ints.get_pos_inf());
assert_eq!(ints.to_string(), expected);
assert_eq!(ints.is_empty(), false);
assert_eq!(ints.is_universal(), false);
assert_eq!(ints.is_infinite(), true);
assert_eq!(ints.is_finite(), false);
assert_eq!(ints.is_pos_inf(), true);
assert_eq!(ints.is_neg_inf(), false);

This Rust crate is ported from the Java class jintspan and the Perl module AlignDB::IntSpan, which contains many codes from Set::IntSpan, Set::IntSpan::Fast and Set::IntSpan::Island.

Implementations

impl IntSpan

INTERFACE: Set creation and contents

pub fn new() -> Self

pub fn from(runlist: &str) -> Self

pub fn from_pair(lower: i32, upper: i32) -> Self

pub fn get_pos_inf(&self) -> i32

Returns the constant of POS_INF

Typically used to construct infinite sets

pub fn get_neg_inf(&self) -> i32

Returns the constant of NEG_INF

Typically used to construct infinite sets

pub fn clear(&mut self)

Clears all contents of ints

pub fn edge_size(&self) -> usize

pub fn span_size(&self) -> usize

pub fn to_vec(&self) -> Vec<i32>

pub fn contains(&self, n: i32) -> bool

pub fn min(&self) -> i32

pub fn max(&self) -> i32

impl IntSpan

INTERFACE: Span contents

pub fn spans(&self) -> Vec<(i32, i32)>

Returns the runs in IntSpan, as a vector of Tuple(lower, upper)

let ints = intspan::IntSpan::from("1-2,4-7");
assert_eq!(ints.spans(), vec![(1, 2), (4, 7)]);

pub fn ranges(&self) -> Vec<i32>

Returns the runs in IntSpan, as a vector of lower, upper

let ints = intspan::IntSpan::from("1-2,4-7");
assert_eq!(ints.ranges(), vec![1, 2, 4, 7]);

pub fn runs(&self) -> Vec<String>

Returns the runs in IntSpan, as a vector of String

let ints = intspan::IntSpan::from("1-2,4-7");
assert_eq!(ints.runs(), vec!["1-2".to_string(), "4-7".to_string()]);

pub fn intses(&self) -> Vec<IntSpan>

Returns the runs in IntSpan, as a vector of IntSpan

let ints = intspan::IntSpan::from("1-2,4-7");
assert_eq!(ints.intses().iter().map(|e| e.to_string()).collect::<Vec<String>>(),
    vec!["1-2".to_string(), "4-7".to_string()]);

impl IntSpan

INTERFACE: Set cardinality

pub fn cardinality(&self) -> i32

pub fn is_empty(&self) -> bool

pub fn is_neg_inf(&self) -> bool

pub fn is_pos_inf(&self) -> bool

pub fn is_infinite(&self) -> bool

pub fn is_finite(&self) -> bool

pub fn is_universal(&self) -> bool

impl IntSpan

INTERFACE: Member operations (mutate original set)

pub fn add_pair(&mut self, lower: i32, upper: i32)

pub fn add_n(&mut self, n: i32)

pub fn add_ranges(&mut self, ranges: &[i32])

pub fn merge(&mut self, other: &Self)

pub fn add_vec(&mut self, ints: &[i32])

pub fn add_runlist(&mut self, runlist: &str)

pub fn invert(&mut self)

pub fn remove_pair(&mut self, lower: i32, upper: i32)

pub fn remove_n(&mut self, n: i32)

pub fn remove_ranges(&mut self, ranges: &[i32])

pub fn subtract(&mut self, other: &Self)

pub fn remove_vec(&mut self, array: &[i32])

pub fn remove_runlist(&mut self, runlist: &str)

impl IntSpan

INTERFACE: Set binary operations (create new set)

pub fn copy(&self) -> Self

pub fn union(&self, other: &Self) -> Self

pub fn complement(&self) -> Self

pub fn diff(&self, other: &Self) -> Self

pub fn intersect(&self, other: &Self) -> Self

pub fn xor(&self, other: &Self) -> Self

impl IntSpan

INTERFACE: Set relations

pub fn equals(&self, other: &Self) -> bool

pub fn subset(&self, other: &Self) -> bool

pub fn superset(&self, other: &Self) -> bool

impl IntSpan

INTERFACE: Indexing

pub fn at(&self, index: i32) -> i32

Returns the index-th element of set, indices start from 1.

Negative indices count backwards from the end of the set.

pub fn index(&self, element: i32) -> i32

Returns the index of an element in the set, indices start from 1

pub fn slice(&self, from: i32, to: i32) -> IntSpan

impl IntSpan

INTERFACE: Spans Ops

pub fn cover(&self) -> Self

pub fn holes(&self) -> Self

pub fn inset(&self, n: i32) -> Self

pub fn trim(&self, n: i32) -> Self

pub fn pad(&self, n: i32) -> Self

pub fn excise(&self, min_len: i32) -> Self

pub fn fill(&self, max_len: i32) -> Self

pub fn banish(&self, start: i32, end: i32) -> Self

Removes elements inside the range, and all elements greater than this range are shifted towards the negative direction

impl IntSpan

INTERFACE: Inter-set OPs

pub fn overlap(&self, other: &Self) -> i32

Returns the size of intersection of two sets.

set.overlap(&other) equivalent to set.intersect(&other).cardinality()

let set = IntSpan::from("1");
let other = IntSpan::from("1");
assert_eq!(set.overlap(&other), 1);
let other = IntSpan::from("2");
assert_eq!(set.overlap(&other), 0);
let set = IntSpan::from("1-5");
let other = IntSpan::from("1-10");
assert_eq!(set.overlap(&other), 5);
let set = IntSpan::from("1-5,6");
let other = IntSpan::from("6-10");
assert_eq!(set.overlap(&other), 1);

pub fn distance(&self, other: &Self) -> i32

Returns the distance between sets, measured as follows.

• If the sets overlap, then the distance is negative and given by - set.overlap(&other)

• If the sets do not overlap, $d is positive and given by the distance on the integer line between the two closest islands of the sets.

let set = IntSpan::from("1");
let other = IntSpan::from("1");
assert_eq!(set.distance(&other), -1);
let other = IntSpan::from("");
assert_eq!(set.distance(&other), 0);
let other = IntSpan::from("2");
assert_eq!(set.distance(&other), 1);

let set = IntSpan::from("1-5");
let other = IntSpan::from("1-10");
assert_eq!(set.distance(&other), -5);
let other = IntSpan::from("10-15");
assert_eq!(set.distance(&other), 5);
let set = IntSpan::from("1-5,6");
let other = IntSpan::from("6-10");
assert_eq!(set.distance(&other), -1);

let set = IntSpan::from("1-5,10-15");
let other = IntSpan::from("5-9");
assert_eq!(set.distance(&other), -1);
let other = IntSpan::from("6");
assert_eq!(set.distance(&other), 1);
let other = IntSpan::from("7");
assert_eq!(set.distance(&other), 2);
let other = IntSpan::from("7-9");
assert_eq!(set.distance(&other), 1);
let other = IntSpan::from("16-20");
assert_eq!(set.distance(&other), 1);
let other = IntSpan::from("17-20");
assert_eq!(set.distance(&other), 2);

impl IntSpan

INTERFACE: Islands

pub fn find_islands_n(&self, val: i32) -> IntSpan

Returns an ints equals to the island containing the integer

If the integer is not in the ints, an empty ints is returned

let tests = vec![
    ("1-5", 1, "1-5"),
    ("1-5,7", 1, "1-5"),
    ("1-5,7", 6, "-"),
    ("1-5,7", 7, "7"),
    ("1-5,7-8", 7, "7-8"),
    ("1-5,8", 7, "-"),
];

for (runlist, val, exp_ints) in &tests {
    let ints = IntSpan::from(runlist);

    let res = ints.find_islands_n(*val);

    assert_eq!(res.to_string().as_str(), *exp_ints);
}

pub fn find_islands_ints(&self, other: &Self) -> IntSpan

Returns an ints containing all islands intersecting other

If ints and other don’t intersect, an empty ints is returned

let tests = vec![
    ("1-8", "7-8", "1-8"),
    ("1-5,7-8", "7-8", "7-8"),
    ("1-5,8-9", "7-8", "8-9"),
    ("1-5,8-9,11-15", "9-11", "8-9,11-15"),
];

for (runlist, other, exp_ints) in &tests {
    let ints = IntSpan::from(runlist);
    let other = IntSpan::from(other);

    let res = ints.find_islands_ints(&other);

    assert_eq!(res.to_string().as_str(), *exp_ints);
}

impl IntSpan

INTERFACE: Aliases

pub fn size(&self) -> i32

pub fn runlist(&self) -> String

pub fn elements(&self) -> Vec<i32>

Trait Implementations

impl Clone for IntSpan

fn clone(&self) -> IntSpan

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Default for IntSpan

fn default() -> IntSpan

Returns the “default value” for a type.

impl Display for IntSpan

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

Formats the value using the given formatter.