Struct Alphabet 

pub struct Alphabet { /* private fields */ }

A finite set of characters from the SMT-LIB alphabet, represented as a normalized set of disjoint CharRanges.

An Alphabet models a subset of the SMT-LIB character domain [0x0000, 0x2FFFF]. Internally, it is represented as a sorted list of CharRanges, where each range is:

• non-empty,
• non-overlapping with other ranges,
• and not adjacent to any other range.

Normalization

The internal representation is kept normalized at all times:

• Ranges are kept in ascending order by start character.
• Overlapping or adjacent ranges are merged automatically upon insertion.
• The internal structure is stored in a Vec of CharRanges.

Example

use smt_str::alphabet::{Alphabet, CharRange};

let mut a = Alphabet::default();
a.insert(CharRange::new('a', 'f'));

// Overlapping range is merged
a.insert(CharRange::new('d', 'h'));
assert_eq!(a.iter_ranges().count(), 1);

// Adjacent range is also merged
a.insert(CharRange::new('h', 'k'));
assert_eq!(a.iter_ranges().count(), 1);

Set Operations

This type supports the following set operations, each returning a new normalized Alphabet:

• union: characters in either alphabet.
• intersect: characters common to both alphabets.
• subtract: characters in self but not in the other alphabet.
• complement: all characters not in the current alphabet (with respect to the SMT-LIB character domain).

All set operations are performed in O(n + m) time, where n and m are the number of ranges in the two alphabets.

Implementations

impl Alphabet

pub fn full() -> Self

Returns the full alphabet, containing all characters in the SMT-LIB alphabet.

pub fn empty() -> Self

Returns an empty alphabet.

pub fn is_empty(&self) -> bool

Check if the alphabet is empty.

Example

use smt_str::alphabet::Alphabet;
let alphabet = Alphabet::empty();
assert!(alphabet.is_empty());

pub fn len(&self) -> usize

The number of characters in the alphabet. This is the sum of the number of characters in each range in the alphabet. If the alphabet is empty, the length is zero.

Example

use smt_str::alphabet::{Alphabet, CharRange};

let mut alphabet = Alphabet::default();
alphabet.insert(CharRange::new('a', 'd')); // 4 characters
alphabet.insert(CharRange::new('x', 'z')); // 3 characters
assert_eq!(alphabet.len(), 7);

pub fn contains(&self, c: impl Into<SmtChar>) -> bool

Check if a character is in the alphabet. Requires O(log n) time where n is the number of ranges in the alphabet.

Example

use smt_str::alphabet::{Alphabet, CharRange};

let mut alphabet = Alphabet::default();
alphabet.insert(CharRange::new('a', 'd'));
assert!(alphabet.contains('a'));
assert!(alphabet.contains('d'));
assert!(alphabet.contains('c'));
assert!(!alphabet.contains('e'));

pub fn insert(&mut self, new: CharRange)

Inserts a new character range into the alphabet, merging it with any overlapping or adjacent ranges.

The internal representation is kept normalized: all ranges are non-overlapping, non-adjacent, and sorted by starting character. This means that if the inserted range touches or overlaps existing ranges, it will be merged into a single contiguous range.

Keeping this invariant requires O(n) time for insertion, where n is the number of existing ranges in the alphabet.

Inserting an empty range has no effect.

Examples

use smt_str::alphabet::{Alphabet, CharRange};

let mut a = Alphabet::default();
a.insert(CharRange::new('a', 'c'));
a.insert(CharRange::new('d', 'f')); // Adjacent: merged into ['a','f']

let ranges: Vec<_> = a.iter_ranges().collect();
assert_eq!(ranges, vec![CharRange::new('a', 'f')]);

pub fn insert_char(&mut self, c: impl Into<SmtChar>)

Insert a new character in the alphabet. Equivalent to insert(CharRange::singleton(c)). See insert for more details.

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

Computes the union of two alphabets and returns the result.

The union contains all characters that appear in either self or other.

This method performs a single linear pass over the ranges in both alphabets to merge overlapping and adjacent ranges. Requires O(n + m) space and time, where n and m are the number of ranges in the two alphabets.

The resulting Alphabet preserves the invariant that its character ranges are sorted and normalized, i.e., non-overlapping and non-adjacent.

Examples

use smt_str::alphabet::{Alphabet, CharRange};

let mut a1 = Alphabet::default();
a1.insert(CharRange::new('a', 'c'));

let mut a2 = Alphabet::default();
a2.insert(CharRange::new('d', 'f'));

let union = a1.union(&a2);

let mut iter = union.iter_ranges();
assert_eq!(iter.next(), Some(CharRange::new('a', 'f'))); // merged
assert_eq!(iter.next(), None);

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

Computes the intersection of two alphabets and returns the result.

The result contains all characters that are present in both self and other. This implementation performs a linear-time merge over the sorted range lists and computes pairwise intersections of overlapping ranges. Hence, the function needs O(n + m) time and O(min(n,m)) space, where n and m are the number of ranges in the two alphabets.

The result is guaranteed to be sorted, non-overlapping, and non-adjacent.

Example

use smt_str::alphabet::{Alphabet, CharRange};
use smt_str::SmtChar;

let mut a1 = Alphabet::default();
a1.insert(CharRange::new('a', 'd'));
a1.insert(CharRange::new('x', 'z'));

let mut a2 = Alphabet::default();
a2.insert(CharRange::new('c', 'f'));
a2.insert(CharRange::new('y', 'z'));
     
let intersection = a1.intersect(&a2);

let mut iter = intersection.iter_ranges();
assert_eq!(iter.next(), Some(CharRange::new('c', 'd')));
assert_eq!(iter.next(), Some(CharRange::new('y', 'z')));
assert_eq!(iter.next(), None);

pub fn complement(&self) -> Self

Computes the complement of the alphabet with respect to the full SMT-LIB character set.

The result contains all characters that are not present in this alphabet.
That is, if this alphabet contains characters A, the complement contains the set [0x0000, 0x2FFFF] \ A.

Computing the complement is done in a single pass over the ranges in the alphabet. It requires O(n) time and space, where n is the number of ranges in the alphabet.

The output is a normalized Alphabet with non-overlapping, non-adjacent and sorted ranges.

Example

use smt_str::alphabet::{Alphabet, CharRange};
use smt_str::SmtChar;

let mut a = Alphabet::default();
a.insert(CharRange::new('a', 'd'));
a.insert(CharRange::new('x', 'z'));

let complement = a.complement();

let mut iter = complement.iter_ranges();
assert_eq!(iter.next(), Some(CharRange::new(SmtChar::from(0), SmtChar::from('a').saturating_prev())));
assert_eq!(iter.next(), Some(CharRange::new(SmtChar::from('d').saturating_next(), SmtChar::from('x').saturating_prev())));
assert_eq!(iter.next(), Some(CharRange::new(SmtChar::from('z').saturating_next(), SmtChar::MAX)));
assert_eq!(iter.next(), None);

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

Computes the set difference self \ other and returns a new Alphabet.

The result contains all characters that are present in self but not in other.

This operation is analogous to set difference and preserves normalization (sorted, non-overlapping, non-adjacent ranges). It needs O(n + m) and O(n + m) space, where n and m are the number of ranges in the two alphabets.

Example

use smt_str::alphabet::{Alphabet, CharRange};

let mut a = Alphabet::default();
a.insert(CharRange::new('a', 'f'));

let mut b = Alphabet::default();
b.insert(CharRange::new('c', 'd'));

let diff = a.subtract(&b);
let expected = [CharRange::new('a', 'b'), CharRange::new('e', 'f')];

let ranges: Vec<_> = diff.iter_ranges().collect();
assert_eq!(ranges, expected);

pub fn iter_ranges(&self) -> impl Iterator<Item = CharRange> + '_

Return an iterator over the ranges in the alphabet.

pub fn iter(&self) -> impl Iterator<Item = SmtChar> + '_

Return an iterator over all characters in the alphabet.

Trait Implementations

impl Arbitrary for Alphabet

fn arbitrary(g: &mut Gen) -> Self

Return an arbitrary value.

fn shrink(&self) -> Box<dyn Iterator<Item = Self>>

Return an iterator of values that are smaller than itself.

impl Clone for Alphabet

fn clone(&self) -> Alphabet

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Alphabet

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

Formats the value using the given formatter.

impl Default for Alphabet

fn default() -> Alphabet

Returns the “default value” for a type.

impl Display for Alphabet

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

Formats the value using the given formatter.

impl From<CharRange> for Alphabet

fn from(r: CharRange) -> Self

Converts to this type from the input type.

impl FromIterator<CharRange> for Alphabet

fn from_iter<T: IntoIterator<Item = CharRange>>(iter: T) -> Self

Creates a value from an iterator.

impl FromIterator<SmtChar> for Alphabet

fn from_iter<T: IntoIterator<Item = SmtChar>>(iter: T) -> Self

Creates a value from an iterator.

impl PartialEq for Alphabet

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

impl StructuralPartialEq for Alphabet