Struct AlphabetPartitionMap 

pub struct AlphabetPartitionMap<T: Clone> { /* private fields */ }

A partitioning of the SMT-LIB alphabet into disjoint character ranges, each associated with a value of type T.

See the module-level documentation for details.

/// # Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p = AlphabetPartitionMap::empty();
p.insert(CharRange::new('a', 'f'), 1).unwrap();
p.insert(CharRange::new('g', 'z'), 2).unwrap();

assert_eq!(p.len(), 2);
assert_eq!(p.get(&CharRange::new('a', 'f')), Some(&1));

Implementations

impl<T: Clone> AlphabetPartitionMap<T>

pub fn empty() -> Self

Creates a new, empty partitioning.

The resulting partitioning contains no character ranges.

Example

use smt_str::alphabet::partition::AlphabetPartitionMap;
let p: AlphabetPartitionMap<i32> = AlphabetPartitionMap::empty();
assert!(p.is_empty());
assert_eq!(p.len(), 0);

pub fn singleton(r: CharRange, v: T) -> Self

Creates a partitioning map containing a single character range with the given associated value.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let range = CharRange::new('a', 'z');
let partitioning = AlphabetPartitionMap::singleton(range.clone(), 1);
assert_eq!(partitioning.len(), 1);
assert_eq!(partitioning.get(&range), Some(&1));

pub fn insert(&mut self, range: CharRange, v: T) -> Result<(), CharRange>

Attempts to insert a character range with an associated value into the partitioning.

This method checks whether the given range overlaps with any existing range in the partitioning. If there is no overlap, the range is inserted and Ok(()) is returned. If the range overlaps with an existing partition, insertion is rejected and the conflicting range is returned in Err.

This operation runs in O(n + log n) time, where n is the number of partitions. If overlap checks are not necessary, use insert_unchecked for faster insertion.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut partitioning = AlphabetPartitionMap::empty();

let range = CharRange::new('a', 'z');
assert_eq!(partitioning.insert(range.clone(), 1), Ok(()));
assert_eq!(partitioning.get(&range), Some(&1));

// Overlapping range cannot be inserted
assert_eq!(
    partitioning.insert(CharRange::new('m', 'p'), 1),
    Err(CharRange::new('a', 'z'))
);

pub fn insert_unchecked(&mut self, range: CharRange, v: T)

Inserts a character range with its associated value into the partitioning without checking for overlaps.

This method assumes that the given range does not overlap with any existing partition. If this assumption is violated, the internal becomes invalid.

Runs in O(log n) time, where n is the number of existing partitions.

Use this method only when you are certain that the inserted range does not conflict with existing ones. For safe insertion with overlap checks, use insert.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut partitioning = AlphabetPartitionMap::empty();
partitioning.insert_unchecked(CharRange::new('a','z'), 0);
assert_eq!(partitioning.get(&CharRange::new('a','z')), Some(&0));

// Overlapping insertion is allowed, but the partitioning becomes invalid
partitioning.insert_unchecked(CharRange::new('m','p'), 1);
assert_eq!(partitioning.get(&CharRange::new('m','p')), Some(&1));
assert!(!partitioning.valid());

pub fn get(&self, range: &CharRange) -> Option<&T>

Returns a reference to the value associated with the given character range, if it exists.

Only exact matches are returned. That is, the given range must match a range in the map exactly.

Runs in O(log n) time, where n is the number of stored partitions.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut partitioning = AlphabetPartitionMap::empty();
let range = CharRange::new('a', 'z');
partitioning.insert_unchecked(range, 42);

assert_eq!(partitioning.get(&CharRange::new('a', 'z')), Some(&42));
assert_eq!(partitioning.get(&CharRange::new('a', 'm')), None); // no partial match

pub fn remove(&mut self, range: CharRange) -> Option<T>

Removes the given range from the partitioning.

Only removes ranges that exactly match an existing partition. Subranges or overlapping ranges will not be removed.

Returns the associated value if the range was present, or None otherwise.

Runs in O(log n) time, where n is the number of partitions.

Examples

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut partitioning = AlphabetPartitionMap::empty();
partitioning.insert_unchecked(CharRange::new('a', 'z'), 0);

// Exact match can be removed
assert_eq!(partitioning.remove(CharRange::new('a', 'z')), Some(0));

// Subrange does not match exactly
assert_eq!(partitioning.remove(CharRange::new('a', 'm')), None);

pub fn len(&self) -> usize

Returns the number of partitions in the partitioning.

pub fn is_empty(&self) -> bool

Returns trueprecisely if the partitioning is empty.

pub fn refine<F>(&self, other: &Self, f: F) -> Self

where F: Fn(&T, &T) -> T,

Computes the coarsest common refinement of two partitionings.

Given two partitionings self: P and other: Q, this returns a new partitioning R such that every range r ∈ R is the intersection of:

• a range in P and a range in Q, or
• a range in P and a range in the complement of Q, or
• a range in Q and a range in the complement of P

In other words, R is the coarsest partitioning that is a common refinement of P and Q.

The associated value for each r ∈ R is determined as follows:

• If r is contained in a range p ∈ P and disjoint from all ranges in Q, its value is P(p).
• If r is contained in a range q ∈ Q and disjoint from all ranges in P, its value is Q(q).
• If r is the intersection of p ∈ P and q ∈ Q, its value is f(P(p), Q(q)).

Arguments

• other — the partitioning to refine with
• f — a function used to merge values when ranges from both partitionings overlap

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p1 = AlphabetPartitionMap::empty();
p1.insert_unchecked(CharRange::new('a', 'z'), 1);

let mut p2 = AlphabetPartitionMap::empty();
p2.insert_unchecked(CharRange::new('b', 'c'), 2);

let refined = p1.refine(&p2, |a, b| a + b);

let mut iter = refined.iter();
assert_eq!(iter.next(), Some((&CharRange::new('a', 'a'), &1)));
assert_eq!(iter.next(), Some((&CharRange::new('b', 'c'), &3)));
assert_eq!(iter.next(), Some((&CharRange::new('d', 'z'), &1)));
assert_eq!(iter.next(), None);

pub fn refine_single<F>(&self, range: CharRange, val: T, f: F) -> Self

where F: Fn(&T, &T) -> T,

Refines the partitioning with a single character range and associated value.

This is a convenience method that creates a singleton partitioning and invokes [refine] with it. The result is equivalent to refining self with a partitioning containing only the given range.

See refine for the semantics of refinement.

Arguments

• range — the range to refine with
• val — the value associated with the range
• f — the merge function used when range overlaps with an existing range

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p = AlphabetPartitionMap::empty();
p.insert_unchecked(CharRange::new('a', 'z'), 1);

let refined = p.refine_single(CharRange::new('b', 'c'), 2, |a, b| a + b);

let mut iter = refined.iter();
assert_eq!(iter.next(), Some((&CharRange::new('a', 'a'), &1)));
assert_eq!(iter.next(), Some((&CharRange::new('b', 'c'), &3)));
assert_eq!(iter.next(), Some((&CharRange::new('d', 'z'), &1)));
assert_eq!(iter.next(), None);

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

Returns an iterator over the character ranges and associated values in the partitioning.

The iterator yields pairs of CharRange and references to their associated values, in ascending order of ranges.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p = AlphabetPartitionMap::empty();
p.insert_unchecked(CharRange::new('a', 'c'), 1);
p.insert_unchecked(CharRange::new('x', 'z'), 2);

let mut iter = p.iter();
assert_eq!(iter.next(), Some((&CharRange::new('a', 'c'), &1)));
assert_eq!(iter.next(), Some((&CharRange::new('x', 'z'), &2)));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> impl Iterator<Item = (&CharRange, &mut T)> + '_

Returns an iterator over the character ranges and mutable references to their associated values.

The iterator yields pairs of CharRange and mutable references to their associated values, in ascending order of ranges. This allows modifying the values in-place.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p = AlphabetPartitionMap::empty();
p.insert_unchecked(CharRange::new('a', 'c'), 1);
p.insert_unchecked(CharRange::new('x', 'z'), 2);

for (_, value) in p.iter_mut() {
    *value += 1;
}

let mut iter = p.iter();
assert_eq!(iter.next(), Some((&CharRange::new('a', 'c'), &2)));
assert_eq!(iter.next(), Some((&CharRange::new('x', 'z'), &3)));
assert_eq!(iter.next(), None);

pub fn overlaps(&self, range: CharRange) -> Option<(&CharRange, &T)>

Checks whether the given character range overlaps with any existing partition in the map.

Returns the first overlapping (CharRange, value) pair if any overlap exists; otherwise returns None.

This method performs a linear scan over all ranges and runs in O(n) time, where n is the number of partitions. TODO: Could be optimized to O(log n) using binary search.

Arguments

• range: The CharRange to test for overlap.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p = AlphabetPartitionMap::empty();
p.insert_unchecked(CharRange::new('a', 'z'), 1);

assert!(p.overlaps(CharRange::new('m', 'p')).is_some());
assert!(p.overlaps(CharRange::new('0', '9')).is_none());

pub fn valid(&self) -> bool

Returns true if the partitioning is valid, i.e., if no two character ranges overlap. This property holds as long as insert_unchecked is not used to insert overlapping ranges.

This method checks that for every pair of consecutive ranges (r1, r2), the end of r1 is strictly less than the start of r2. This ensures that the partitioning forms a set of non-overlapping ranges.

Runs in O(n) time, where n is the number of partitions.

Example

use smt_str::alphabet::{partition::AlphabetPartitionMap, CharRange};

let mut p = AlphabetPartitionMap::empty();
p.insert_unchecked(CharRange::new('a', 'f'), 1);
p.insert_unchecked(CharRange::new('g', 'z'), 2);
assert!(p.valid());

// Overlapping range leads to invalid partitioning
p.insert_unchecked(CharRange::new('e', 'h'), 3);
assert!(!p.valid());

Trait Implementations

impl<T: Clone + Clone> Clone for AlphabetPartitionMap<T>

fn clone(&self) -> AlphabetPartitionMap<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Clone> Debug for AlphabetPartitionMap<T>

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

Formats the value using the given formatter.

impl<T: Default + Clone> Default for AlphabetPartitionMap<T>

fn default() -> AlphabetPartitionMap<T>

Returns the “default value” for a type.

impl<T: Display + Clone> Display for AlphabetPartitionMap<T>

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

Formats the value using the given formatter.

impl<T: Clone> IntoIterator for AlphabetPartitionMap<T>

type Item = (CharRange, T)

The type of the elements being iterated over.

type IntoIter = IntoIter<CharRange, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.