// This file is part of the uutils coreutils package.
//
// (c) Rolf Morel <rolfmorel@gmail.com>
//
// For the full copyright and license information, please view the LICENSE
// file that was distributed with this source code.
// spell-checker:ignore (ToDO) inval
use std::cmp::max;
use std::str::FromStr;
use crate::display::Quotable;
#[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
pub struct Range {
pub low: usize,
pub high: usize,
}
impl FromStr for Range {
type Err = &'static str;
/// Parse a string of the form `a-b` into a `Range`
///
/// ```
/// use std::str::FromStr;
/// use uucore::ranges::Range;
/// assert_eq!(Range::from_str("5"), Ok(Range { low: 5, high: 5 }));
/// assert_eq!(Range::from_str("4-"), Ok(Range { low: 4, high: usize::MAX - 1 }));
/// assert_eq!(Range::from_str("-4"), Ok(Range { low: 1, high: 4 }));
/// assert_eq!(Range::from_str("2-4"), Ok(Range { low: 2, high: 4 }));
/// assert!(Range::from_str("0-4").is_err());
/// assert!(Range::from_str("4-2").is_err());
/// assert!(Range::from_str("-").is_err());
/// assert!(Range::from_str("a").is_err());
/// assert!(Range::from_str("a-b").is_err());
/// ```
fn from_str(s: &str) -> Result<Self, &'static str> {
fn parse(s: &str) -> Result<usize, &'static str> {
match s.parse::<usize>() {
Ok(0) => Err("fields and positions are numbered from 1"),
Ok(n) => Ok(n),
Err(_) => Err("failed to parse range"),
}
}
Ok(match s.split_once('-') {
None => {
let n = parse(s)?;
Self { low: n, high: n }
}
Some(("", "")) => return Err("invalid range with no endpoint"),
Some((low, "")) => Self {
low: parse(low)?,
high: usize::MAX - 1,
},
Some(("", high)) => Self {
low: 1,
high: parse(high)?,
},
Some((low, high)) => {
let (low, high) = (parse(low)?, parse(high)?);
if low <= high {
Self { low, high }
} else {
return Err("high end of range less than low end");
}
}
})
}
}
impl Range {
pub fn from_list(list: &str) -> Result<Vec<Self>, String> {
let mut ranges = Vec::new();
for item in list.split(&[',', ' ']) {
let range_item = FromStr::from_str(item)
.map_err(|e| format!("range {} was invalid: {}", item.quote(), e))?;
ranges.push(range_item);
}
Ok(Self::merge(ranges))
}
/// Merge any overlapping ranges
///
/// Is guaranteed to return only disjoint ranges in a sorted order.
fn merge(mut ranges: Vec<Self>) -> Vec<Self> {
ranges.sort();
// merge overlapping ranges
for i in 0..ranges.len() {
let j = i + 1;
// The +1 is a small optimization, because we can merge adjacent Ranges.
// For example (1,3) and (4,6), because in the integers, there are no
// possible values between 3 and 4, this is equivalent to (1,6).
while j < ranges.len() && ranges[j].low <= ranges[i].high + 1 {
let j_high = ranges.remove(j).high;
ranges[i].high = max(ranges[i].high, j_high);
}
}
ranges
}
}
pub fn complement(ranges: &[Range]) -> Vec<Range> {
let mut prev_high = 0;
let mut complements = Vec::with_capacity(ranges.len() + 1);
for range in ranges {
if range.low > prev_high + 1 {
complements.push(Range {
low: prev_high + 1,
high: range.low - 1,
});
}
prev_high = range.high;
}
if prev_high < usize::MAX - 1 {
complements.push(Range {
low: prev_high + 1,
high: usize::MAX - 1,
});
}
complements
}
/// Test if at least one of the given Ranges contain the supplied value.
///
/// Examples:
///
/// ```
/// let ranges = uucore::ranges::Range::from_list("11,2,6-8").unwrap();
///
/// assert!(!uucore::ranges::contain(&ranges, 0));
/// assert!(!uucore::ranges::contain(&ranges, 1));
/// assert!(!uucore::ranges::contain(&ranges, 5));
/// assert!(!uucore::ranges::contain(&ranges, 10));
///
/// assert!(uucore::ranges::contain(&ranges, 2));
/// assert!(uucore::ranges::contain(&ranges, 6));
/// assert!(uucore::ranges::contain(&ranges, 7));
/// assert!(uucore::ranges::contain(&ranges, 8));
/// assert!(uucore::ranges::contain(&ranges, 11));
/// ```
pub fn contain(ranges: &[Range], n: usize) -> bool {
for range in ranges {
if n >= range.low && n <= range.high {
return true;
}
}
false
}
#[cfg(test)]
mod test {
use super::{complement, Range};
fn m(a: Vec<Range>, b: &[Range]) {
assert_eq!(Range::merge(a), b);
}
fn r(low: usize, high: usize) -> Range {
Range { low, high }
}
#[test]
fn merging() {
// Single element
m(vec![r(1, 2)], &[r(1, 2)]);
// Disjoint in wrong order
m(vec![r(4, 5), r(1, 2)], &[r(1, 2), r(4, 5)]);
// Two elements must be merged
m(vec![r(1, 3), r(2, 4), r(6, 7)], &[r(1, 4), r(6, 7)]);
// Two merges and a duplicate
m(
vec![r(1, 3), r(6, 7), r(2, 4), r(6, 7)],
&[r(1, 4), r(6, 7)],
);
// One giant
m(
vec![
r(110, 120),
r(10, 20),
r(100, 200),
r(130, 140),
r(150, 160),
],
&[r(10, 20), r(100, 200)],
);
// Last one joins the previous two
m(vec![r(10, 20), r(30, 40), r(20, 30)], &[r(10, 40)]);
m(
vec![r(10, 20), r(30, 40), r(50, 60), r(20, 30)],
&[r(10, 40), r(50, 60)],
);
// Merge adjacent ranges
m(vec![r(1, 3), r(4, 6)], &[r(1, 6)]);
}
#[test]
fn complementing() {
// Simple
assert_eq!(complement(&[r(3, 4)]), vec![r(1, 2), r(5, usize::MAX - 1)]);
// With start
assert_eq!(
complement(&[r(1, 3), r(6, 10)]),
vec![r(4, 5), r(11, usize::MAX - 1)]
);
// With end
assert_eq!(
complement(&[r(2, 4), r(6, usize::MAX - 1)]),
vec![r(1, 1), r(5, 5)]
);
// With start and end
assert_eq!(complement(&[r(1, 4), r(6, usize::MAX - 1)]), vec![r(5, 5)]);
}
}