1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

/*
    Appellation: specs <module>
    Contrib: FL03 <jo3mccain@icloud.com>
    Description: ... Summary ...
*/
use contained_core::states::Stateful;
use contained_core::{ArrayLike, Include, Insert};
use std::collections::{BTreeSet, HashSet};

use crate::instructions::Move;
use crate::{State, Tape};

/// [Alphabet] describes an immutable set of [Symbolic] elements
pub trait Alphabet<S: Symbolic> {
    /// [Alphabet::default_symbol]
    fn default_symbol(&self) -> S {
        Default::default()
    }
    /// Returns true if the symbol is in the alphabet
    fn is_viable(&self, symbol: &S) -> bool;
}

impl<S: Symbolic> Alphabet<S> for Vec<S> {
    fn is_viable(&self, symbol: &S) -> bool {
        self.contains(symbol)
    }

    fn default_symbol(&self) -> S {
        if let Some(entry) = self.first() {
            entry.clone()
        } else {
            Default::default()
        }
    }
}

impl<S: Symbolic> Alphabet<S> for BTreeSet<S> {
    fn is_viable(&self, symbol: &S) -> bool {
        self.contains(symbol)
    }
    fn default_symbol(&self) -> S {
        if let Some(entry) = self.first() {
            entry.clone()
        } else {
            Default::default()
        }
    }
}

impl<S: Symbolic> Alphabet<S> for HashSet<S> {
    fn is_viable(&self, symbol: &S) -> bool {
        self.contains(symbol)
    }

    fn default_symbol(&self) -> S {
        if let Some(entry) = self.iter().next() {
            entry.clone()
        } else {
            Default::default()
        }
    }
}

/// [Scope] describes the focus of the [crate::turing::Turing]
pub trait Scope<S: Symbolic>: Include<S> + Insert<usize, S> + Stateful<State> {
    /// [Scope::current] returns the current element of the [Scope] on the [Tape]
    fn current(&self) -> S {
        self.tape()
            .get(self.cursor())
            .expect("Index is out of bounds...")
            .clone()
    }
    /// [Scope::cursor] returns the current position of the [Scope] on the [Tape]
    fn cursor(&self) -> usize;
    /// [Scope::set_index] sets the current position of the [Scope] on the [Tape]
    fn set_index(&mut self, index: usize);
    /// [Scope::set_symbol] sets the current element of the [Scope] on the [Tape]
    fn set_symbol(&mut self, elem: S);
    /// [Move::Left] inserts a new element at the start of the tape if the current position is 0
    /// [Move::Right] inserts a new element at the end of the tape if the current position equals the total number of cells
    /// [Move::Stay] does nothing
    fn shift(&mut self, shift: Move, elem: S) {
        let index = self.cursor();

        match shift {
            // If the current position is 0, insert a new element at the top of the vector
            Move::Left if self.cursor() == 0 => {
                self.include(elem);
            }
            Move::Left => {
                self.set_index(index - 1);
            }
            Move::Right => {
                self.set_index(index + 1);

                if self.cursor() == self.tape().len() {
                    self.include(elem);
                }
            }
            Move::Stay => {}
        }
    }
    /// [Scope::tape] returns the [Tape] of the [Scope]
    fn tape(&self) -> Tape<S>;
}

/// Simple trait for compatible symbols
pub trait Symbolic:
    Clone + Default + Eq + Ord + std::fmt::Debug + std::fmt::Display + std::hash::Hash
{
}

impl<T> Symbolic for T where
    T: Clone + Default + Eq + Ord + std::fmt::Debug + std::fmt::Display + std::hash::Hash
{
}

/// [Translate] is a trait that allows for the translation of a machine's memory
pub trait Translate<S: Symbolic> {
    type Error;

    fn translate(&mut self, tape: Tape<S>) -> Result<Tape<S>, Self::Error>;
}

/// [Turing] describes a programmable Turing machine
pub trait Turing<S: Symbolic>: Translate<S> {
    type Scope: Scope<S>;

    /// [Turing::execute]
    fn execute(&mut self) -> Result<&Self, Self::Error>;
    /// [Turing::execute_once]
    fn execute_once(&mut self) -> Result<&Self, Self::Error>;
    /// [Turing::execute_until]
    fn execute_until(&mut self, until: impl Fn(&Self::Scope) -> bool)
        -> Result<&Self, Self::Error>;
}

/// [With] describes a simple means of concating several objects together
pub trait With<T> {
    /// [With::Output] must be a superposition of self and T
    type Output;

    /// [With::with] accepts an owned instance of the given type and returns a [With::Output] instance
    fn with(&self, other: &T) -> Self::Output;
}

/// [TryWith] is a trait that describes a means of trying to concate several objects together
pub trait TryWith<T> {
    type Output;
    type Error;

    fn try_with(&self, other: &T) -> Result<Self::Output, Self::Error>;
}