pub struct IntSpan { /* private fields */ }
Expand description
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§
source§impl IntSpan
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
sourcepub fn get_pos_inf(&self) -> i32
pub fn get_pos_inf(&self) -> i32
Returns the constant of POS_INF
Typically used to construct infinite sets
sourcepub fn get_neg_inf(&self) -> i32
pub fn get_neg_inf(&self) -> i32
Returns the constant of NEG_INF
Typically used to construct infinite sets
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
source§impl IntSpan
impl IntSpan
INTERFACE: Span contents
sourcepub fn spans(&self) -> Vec<(i32, i32)>
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)]);
sourcepub fn ranges(&self) -> Vec<i32>
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]);
source§impl IntSpan
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
source§impl IntSpan
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)
source§impl IntSpan
impl IntSpan
INTERFACE: Indexing
sourcepub fn at(&self, index: i32) -> i32
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.
sourcepub fn index(&self, element: i32) -> i32
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
source§impl IntSpan
impl IntSpan
INTERFACE: Spans Ops
source§impl IntSpan
impl IntSpan
INTERFACE: Inter-set OPs
sourcepub fn overlap(&self, other: &Self) -> i32
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);
sourcepub fn distance(&self, other: &Self) -> i32
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);
source§impl IntSpan
impl IntSpan
INTERFACE: Islands
sourcepub fn find_islands_n(&self, val: i32) -> IntSpan
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);
}
sourcepub fn find_islands_ints(&self, other: &Self) -> IntSpan
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);
}