Trait peepmatic_automata::Output[−][src]

pub trait Output: Sized + Eq + Hash + Clone {
    fn empty() -> Self;

    fn prefix(a: &Self, b: &Self) -> Self;

    fn difference(a: &Self, b: &Self) -> Self;

    fn concat(a: &Self, b: &Self) -> Self;

    fn is_empty(&self) -> bool { ... }
}
Expand description

An output type for a transducer automata.

Not every type can be the output of a transducer. For correctness (not memory safety) each type that implements this trait must satisfy the following laws:

  1. concat(empty(), x) == x – concatenating something with the empty instance produces that same something.

  2. prefix(a, b) == prefix(b, a) – taking the prefix of two instances is commutative.

  3. prefix(empty(), x) == empty() – the prefix of any value and the empty instance is the empty instance.

  4. difference(concat(a, b), a) == b – concatenating a prefix value and then removing it is the identity function.

Example

Here is an example implementation for unsigned integers:

use peepmatic_automata::Output;

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct MyInt(u64);

impl Output for MyInt {
    // The empty value is zero.
    fn empty() -> Self {
        MyInt(0)
    }

    // The prefix of two values is their min.
    fn prefix(a: &MyInt, b: &MyInt) -> Self {
        std::cmp::min(*a, *b)
    }

    // The difference is subtraction.
    fn difference(a: &MyInt, b: &MyInt) -> Self {
        MyInt(a.0 - b.0)
    }

    // Concatenation is addition.
    fn concat(a: &MyInt, b: &MyInt) -> Self {
        MyInt(a.0 + b.0)
    }
}

// Law 1
assert_eq!(
    MyInt::concat(&MyInt::empty(), &MyInt(5)),
    MyInt(5),
);

// Law 2
assert_eq!(
    MyInt::prefix(&MyInt(3), &MyInt(5)),
    MyInt::prefix(&MyInt(5), &MyInt(3))
);

// Law 3
assert_eq!(
    MyInt::prefix(&MyInt::empty(), &MyInt(5)),
    MyInt::empty()
);

// Law 4
assert_eq!(
    MyInt::difference(&MyInt::concat(&MyInt(2), &MyInt(3)), &MyInt(2)),
    MyInt(3),
);

Required methods

Construct the empty instance.

Get the shared prefix of two instances.

This must be commutative.

When b is a prefix of a, get the remaining suffix of a that is not shared with b.

Concatenate a and b.

Provided methods

Is this the empty instance?

The default implementation constructs the empty instance and then checks if self is equal to it. Override this default if you can provide a better implementation.

Implementations on Foreign Types

Implementors