[−][src]Trait peepmatic_automata::Output

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 { ... }
}

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

fn empty() -> Self

Construct the empty instance.

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

Get the shared prefix of two instances.

This must be commutative.

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

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

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

Concatenate a and b.

Loading content...

Provided methods

fn is_empty(&self) -> bool

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.

Loading content...

Implementations on Foreign Types

impl Output for u64[src]

impl<T> Output for Vec<T> where
    T: Clone + Eq + Hash, [src]

impl<T> Output for Box<[T]> where
    T: Clone + Eq + Hash, [src]

Loading content...

Implementors

Loading content...