Struct CharPartition 

pub struct CharPartition { /* private fields */ }

Collection of disjoint character sets.

Each character set is an interval [a, b] where a <= b.

The character sets are sorted in increasing order so a partition of length n is a sequence

[a₀, b₀], [a₁, b₁], …, [a_n-1, b_n-1] where a_i <= b_i and b_i < a_i+1.

This divides the alphabet into n+1 classes C₀, …, C_n-1, and D:

• C_i = { x | a_i <= x <= b_i }
• D = complement of Union(C₀, …, C_n-1)

Each class in a partition can be identified by its ClassId:

• ClassId::Interval(i) denotes the class C_i, that is, the interval [a_i, b_i].
• ClassId::Complement denotes the complementary class D.

Implementations

impl CharPartition

pub fn len(&self) -> usize

Number of intervals in the partition

pub fn is_empty(&self) -> bool

Check whether the partition is empty (i.e., no intervals)

pub fn new() -> Self

Create an empty partition

pub fn from_set(c: &CharSet) -> Self

Partition with a single character set

Example

use aws_smt_strings::character_sets::*;

let p = CharPartition::from_set(&CharSet::range('a' as u32, 'b' as u32));
assert_eq!(p.len(), 1);
assert_eq!(p.get(0), ('a' as u32, 'b' as u32))

pub fn try_from_iter(iter: impl Iterator<Item = CharSet>) -> Result<Self, Error>

Build a partition from a CharSet iterator

Succeeds if the CharSets are pairwise disjoint. Fails otherwise.

Errors

If some CharSets have a non-empty intersection, return Err(Error::NonDisjointCharSets).

Example

use aws_smt_strings::character_sets::*;

let v = [
    CharSet::range(120, 400),
    CharSet::range(0, 10),
    CharSet::range(1000, 2000)];

let p = CharPartition::try_from_iter(v.into_iter().copied())?;
assert_eq!(p.len(), 3);
assert_eq!(p.get(0), (0, 10));
assert_eq!(p.get(1), (120, 400));
assert_eq!(p.get(2), (1000, 2000));

pub fn try_from_list(a: &[CharSet]) -> Result<Self, Error>

Build a partition from a list of CharSets

Succeeds if the CharSets in a are pairwise disjoint. Fails otherwise.

Errors

If some elements of a have a non-empty intersection, return Err(Error::NonDisjointCharSets).

Example

use aws_smt_strings::character_sets::*;

let v = [
    CharSet::range(120, 400),
    CharSet::range(0, 10),
    CharSet::range(1000, 2000)];

let p = CharPartition::try_from_list(&v)?;
assert_eq!(p.len(), 3);
assert_eq!(p.get(0), (0, 10));
assert_eq!(p.get(1), (120, 400));
assert_eq!(p.get(2), (1000, 2000));

pub fn push(&mut self, start: u32, end: u32)

Add the interval [start, end] at the end of the partition.

Requires start <= end and end <= MAX_CHAR. If the partition is not empty, start must also be larger than the end of the last interval in the partition.

Example

This constructs the two-interval partition ['0', '9'] ['Z', 'Z'].

use aws_smt_strings::character_sets::*;

let mut p = CharPartition::new();
p.push('0' as u32, '9' as u32);
p.push('Z' as u32, 'Z' as u32);

assert_eq!(p.len(), 2);
assert_eq!(p.get(0), ('0' as u32, '9' as u32));
assert_eq!(p.get(1), ('Z' as u32, 'Z' as u32));

pub fn get(&self, i: usize) -> (u32, u32)

Get the pair (start, end) of the i-the interval in the partition

Intervals are indexed from 0 to p.len() - 1 (inclusive).

• if i < p.len(), return the start and end of the i-th interval.
• if i >= p.len(), return the pair (MAX_CHAR+1, MAX_CHAR+1)

Example

use aws_smt_strings::character_sets::*;
use aws_smt_strings::smt_strings::MAX_CHAR;

// partition ['0', '9'] ['Z', 'Z']
let mut p = CharPartition::new();
p.push('0' as u32, '9' as u32);
p.push('Z' as u32, 'Z' as u32);

assert_eq!(p.get(0), ('0' as u32, '9' as u32)); // first interval
assert_eq!(p.get(3), (MAX_CHAR + 1, MAX_CHAR + 1)); // out-of-range index

pub fn interval(&self, i: usize) -> CharSet

Get the i-the interval in the partition as a CharSet.

Panics

If i is out of bound, that is, if i >= number of intervals in the partition.

Example

use aws_smt_strings::character_sets::*;

let mut p = CharPartition::new();
p.push('a' as u32, 'z' as u32);

assert_eq!(p.interval(0), CharSet::range('a' as u32, 'z' as u32));

pub fn start(&self, i: usize) -> u32

Get the start of the i-th interval

• return MAX_CHAR+1 if i is out of bound.

Example

use aws_smt_strings::character_sets::*;
use aws_smt_strings::smt_strings::MAX_CHAR;

let mut p = CharPartition::new();
p.push('a' as u32, 'z' as u32);

assert_eq!(p.start(0), 'a' as u32);
assert_eq!(p.start(1), MAX_CHAR+1);

pub fn end(&self, index: usize) -> u32

Get the end of the i-th interval

• return MAX_CHAR+1 if i is out of bound

Example

use aws_smt_strings::character_sets::*;
use aws_smt_strings::smt_strings::MAX_CHAR;

let mut p = CharPartition::new();
p.push('a' as u32, 'z' as u32);

assert_eq!(p.end(0), 'z' as u32);
assert_eq!(p.end(1), MAX_CHAR+1);

pub fn pick(&self, i: usize) -> u32

Pick an element in interval i

Panics

if i >= number of intervals in the partition

Example

use aws_smt_strings::character_sets::*;

let mut p = CharPartition::new();
p.push('a' as u32, 'z' as u32);

assert!('a' as u32 <= p.pick(0) && p.pick(0) <= 'z' as u32);

pub fn empty_complement(&self) -> bool

Check whether the complementary class is empty

Example

use aws_smt_strings::character_sets::*;
use aws_smt_strings::smt_strings::MAX_CHAR;

let mut p = CharPartition::new();
p.push(0, 127);
assert!(! p.empty_complement());
p.push(128, MAX_CHAR);
assert!(p.empty_complement());

pub fn pick_complement(&self) -> u32

Pick an element in the complementary class

• return MAX_CHAR+1 if the complementary class is empty

Example

use aws_smt_strings::character_sets::*;
use aws_smt_strings::smt_strings::MAX_CHAR;

// partition with a single interval ['a', 'z']
let p = CharPartition::from_set(&CharSet::range('a' as u32, 'z' as u32));

// the complementary class is the union of [0, 'a' - 1] and ['z' + 1, MAX_CHAR]
let x = p.pick_complement();
assert!(x < ('a' as u32) || ('z' as u32) < x && x <= MAX_CHAR);

pub fn valid_class_id(&self, cid: ClassId) -> bool

Check whether a class id is valid

Example

use aws_smt_strings::character_sets::*;

// partition with two intervals and three classes
let mut p = CharPartition::new();
p.push('0' as u32, '9' as u32);
p.push('Z' as u32, 'Z' as u32);

assert!(p.valid_class_id(ClassId::Interval(0)));
assert!(p.valid_class_id(ClassId::Interval(1)));
assert!(p.valid_class_id(ClassId::Complement));

assert!(! p.valid_class_id(ClassId::Interval(2)));

pub fn num_classes(&self) -> usize

Number of classes

Example

use aws_smt_strings::character_sets::*;

// partition with two intervals and three classes
let mut p = CharPartition::new();
p.push('0' as u32, '9' as u32);
p.push('Z' as u32, 'Z' as u32);

assert_eq!(p.num_classes(), 3);

pub fn pick_in_class(&self, cid: ClassId) -> u32

Pick an element in a class

• cid identifies the class: if cid = Interval(i) then pick in the i-th interval of p (intervals are indexed from 0 to p.len() - 1)
• if cid is Complement then pick in the complementary class

Panics

If cid is Interval(i) and i >= p.len() or cid is Complement and the complementary class is empty.

Example

use aws_smt_strings::character_sets::{ClassId::*, *};
use aws_smt_strings::smt_strings::MAX_CHAR;

let mut p = CharPartition::new();
p.push('0' as u32, '9' as u32);
p.push('Z' as u32, 'Z' as u32);

let x = p.pick_in_class(Interval(1));
assert_eq!(x, 'Z' as u32); // since interval 1 is ['Z', 'Z']

let y = p.pick_in_class(Complement);
assert!(0 <= y && y < ('0' as u32) ||
        ('9' as u32) < y && y < ('Z' as u32) ||
        ('Z' as u32) < y && y <= MAX_CHAR);

pub fn ranges(&self) -> impl Iterator<Item = &CharSet>

Iterator to go through all intervals in the partition

pub fn class_ids(&self) -> ClassIdIterator<'_>

Iterator to go through all valid class ids

pub fn picks(&self) -> PickIterator<'_>

Iterator to pick one character in each class (including the complementary class).

pub fn class_of_char(&self, x: u32) -> ClassId

Search for the class that contains a character

• Return Interval(i) if a_i <= x <= b_i
• Return Complement if x is not in any interval

pub fn interval_cover(&self, set: &CharSet) -> CoverResult

Search for an interval that covers a character set

The character set is an interval [a, b] where 0 <= a <= b <= MAX_CHAR.

• Return CoverResult::CoveredBy(i) if [a, b] is included in the i-th interval of the partition.
• Return CoverResult::DisjointFromAll if [a, b] does not overlap any interval in the partition.
• Return CoverResult::Overlaps if [a, b] overlaps some interval in the partition but it not contained in this interval.

Example

use aws_smt_strings::character_sets::*;

let p = CharPartition::from_set(&CharSet::range('0' as u32, '9' as u32));
let test1 = CharSet::range('4' as u32, '8' as u32);
let test2 = CharSet::range('a' as u32, 'z' as u32);
let test3 = CharSet::range('5' as u32, '?' as u32);

assert_eq!(p.interval_cover(&test1), CoverResult::CoveredBy(0));
assert_eq!(p.interval_cover(&test2), CoverResult::DisjointFromAll);
assert_eq!(p.interval_cover(&test3), CoverResult::Overlaps);

pub fn class_of_set(&self, s: &CharSet) -> Result<ClassId, Error>

Get the class id for a character set

• The class id is Interval(i) if the set is covered by interval [a_i, b_i] of the partition
• The class id is Complement if the set is covered by the partition’s complementary class
• Otherwise, the class id is not defined.

Error

If the class id is not defined for s, return Err(Error::AmbiguousCharSet)

pub fn good_char_set(&self, c: &CharSet) -> bool

Check whether character set c is consistent with the partition.

• return true if c is included in one partition’s class or if c is included in the partition’s complementary class.

Example

use aws_smt_strings::character_sets::*;

let p = CharPartition::from_set(&CharSet::range('0' as u32, '9' as u32));
let test1 = CharSet::range('4' as u32, '8' as u32);
let test2 = CharSet::range('a' as u32, 'z' as u32);
let test3 = CharSet::range('5' as u32, '?' as u32);

assert!(p.good_char_set(&test1));
assert!(p.good_char_set(&test2));
assert!(! p.good_char_set(&test3));

Trait Implementations

impl Clone for CharPartition

fn clone(&self) -> CharPartition

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for CharPartition

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

Formats the value using the given formatter.

impl Default for CharPartition

fn default() -> CharPartition

Returns the “default value” for a type.

impl Display for CharPartition

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

Formats the value using the given formatter.

impl PartialEq for CharPartition

fn eq(&self, other: &CharPartition) -> 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 Eq for CharPartition

impl StructuralPartialEq for CharPartition