turing_machine_rs/program/core.rs
1use std::fmt::{Display, Error, Formatter};
2use std::mem::replace;
3
4use crate::instruction::{Head, Instruction, Move, State};
5use crate::program::Extend;
6use crate::{Symbol, With};
7
8/// [`Program`] is a vector-based struct with a limited API for changing
9/// and extending but no API for removing and shrinking. The [`Program`]
10/// for the Turing machine has a constant size that equals to
11/// `(STATES.count() - 1) * (ALPHABET.count())`.
12///
13/// If you want to extend the program, you can use the [`Extend::extend`] method,
14/// but you should be sure that this program can accept all these instructions.
15///
16/// # Example
17/// ```rust
18/// extern crate turing_machine_rs;
19/// use turing_machine_rs::instruction::{Move, State};
20/// use turing_machine_rs::machines::Classic;
21/// use turing_machine_rs::program::{Extend, Program};
22/// use turing_machine_rs::state::Tape;
23/// use turing_machine_rs::TuringMachine;
24///
25/// fn main() -> Result<(), String> {
26/// let alphabet = vec!['t', 'e', 's', 'n', 'i', 'c', 'e', '_'];
27/// let mut program = Program::new(alphabet, State(4));
28/// program.extend([
29/// (1, 't', 2, 'n', Move::Right),
30/// (2, 'e', 3, 'i', Move::Right),
31/// (3, 's', 4, 'c', Move::Right),
32/// (4, 't', 0, 'e', Move::None),
33/// // Revers
34/// (1, 'n', 2, 't', Move::Right),
35/// (2, 'i', 3, 'e', Move::Right),
36/// (3, 'c', 4, 's', Move::Right),
37/// (4, 'e', 0, 't', Move::None),
38/// ])?;
39/// let machine = Classic::new(program, '_')?;
40///
41/// let test = Tape::from("test");
42/// let nice = machine.translate_nrm(test.clone())?;
43/// println!(
44/// "{} {}!",
45/// String::from_iter(nice.as_vec()),
46/// String::from_iter(test.as_vec())
47/// );
48/// Ok(())
49/// }
50/// ```
51#[derive(Clone, Debug, PartialEq, Eq)]
52pub struct Program<S: Symbol> {
53 container: Vec<Instruction<S>>,
54 alphabet: Vec<S>,
55 l_state: State,
56}
57
58impl<S: Symbol> Program<S> {
59 #[rustfmt::skip]
60 /// Constructs a new [`Program`] with the vector [`Vec<S>`]
61 /// and the last state [`State`].
62 ///
63 /// [`Program`] has a limited size by definition, so it can only hold `(STATES.count() - 1) * (ALPHABET.count())` [`Instruction`]s.
64 pub fn new(alphabet: Vec<S>, l_state: State) -> Self {
65 let capacity = alphabet.len() * l_state.0;
66 let container = Vec::with_capacity(capacity);
67 Program { alphabet, container, l_state }
68 }
69
70 /// Returns an [`Vec`] alphabet reference.
71 ///
72 /// Zero cost method.
73 pub fn alphabet(&self) -> &Vec<S> {
74 &self.alphabet
75 }
76
77 /// Returns [`Ok(Some)`] when [`Head`] is in the program,
78 /// [`Ok(None)`] when [`Head`] is not in the program
79 /// and [`Err(String)`] when [`Head`] [`State`] is large
80 /// then the [`Program`] last state.
81 pub fn get(&self, head: &Head<S>) -> Result<Option<&Instruction<S>>, String> {
82 if self.l_state < head.state {
83 return Err(format!(
84 "get error: required state {} is large then largest {}",
85 head.state, self.l_state
86 ));
87 }
88 Ok(self
89 .container
90 .iter()
91 .find(|inst: &&Instruction<S>| &inst.head == head))
92 }
93
94 /// Returns [`State`] the program last state.
95 pub fn l_state(&self) -> State {
96 self.l_state
97 }
98
99 #[rustfmt::skip]
100 /// Inserts [`Instruction`] in the [`Program`].
101 ///
102 /// Returns [`Err(String)`] when [`Head`] [`State`] equals to `0`,
103 /// [`Head`] or [`Tail`] symbols are not in the [`Program`] alphabet
104 /// or the [`Program`] last state is less then [`Head`] or [`crate::instruction::Tail`] states.
105 ///
106 /// Otherwise returns another [`Ok(Some(Instruction))`] when the [`Head`]
107 /// already is in the [`Program`] and set inserting [`Instruction`]
108 /// or [`Ok(None)`] when the [`Instruction`] is not in the [`Program`].
109 ///
110 /// The [`Option`] is very useful in the collision check.
111 pub fn insert(&mut self, inst: Instruction<S>) -> Result<Option<Instruction<S>>, String> {
112 if inst.head.state == State(0) {
113 return Err(format!(
114 "set error: instruction {} cannot have 0 state in head",
115 inst
116 ));
117 }
118 if !self.alphabet.contains(&inst.head.symbol)
119 || !self.alphabet.contains(&inst.tail.symbol) {
120 return Err(format!(
121 "set error: instruction {} not for program with alphabet {:?}",
122 inst, &self.alphabet
123 ));
124 }
125 if self.l_state < inst.head.state || self.l_state < inst.tail.state {
126 return Err(format!(
127 "set error: instruction {} have states which is large then program largest state {}",
128 inst, self.l_state
129 ));
130 }
131 let position = self
132 .container
133 .iter()
134 .position(|cand: &Instruction<S>| cand.head == inst.head);
135 match position {
136 Some(index) => Ok(Some(replace(&mut self.container[index], inst))),
137 None => {
138 self.container.push(inst);
139 Ok(None)
140 }
141 }
142 }
143}
144
145impl<S: Symbol> With<Program<S>> for Program<S> {
146 type Output = Result<Program<S>, String>;
147
148 /// Returns a new [`Program`] by merging this program with another according to these rules:
149 /// 1. All [`crate::instruction::Tail`] parts of [`Instruction`]s for this [`Program`]
150 /// will changes their [`State`]s to `self.l_state` if [`crate::instruction::Tail`]
151 /// [`State`] equals to `0`.
152 /// 2. All [`Head`] parts of [`Instruction`]s for another [`Program`] will
153 /// increase (or shift) their [`State`]s by `self.l_state`.
154 /// 3. All [`crate::instruction::Tail`] parts of [`Instruction`]s
155 /// for another program will also increase (or shift) by `self.l_state`
156 /// but only if [`crate::instruction::Tail`] [`State`] not equals to `0`.
157 /// 4. A new [`Program`] `l_state` is set to `self.l_state + other.l_state`.
158 fn with(&self, other: &Program<S>) -> Result<Program<S>, String> {
159 if self.alphabet != other.alphabet {
160 return Err(format!(
161 "extend error: alphabet {:?} and {:?} must be equal",
162 &self.alphabet, &other.alphabet
163 ));
164 }
165 let mut program = Program::new(self.alphabet.clone(), self.l_state + other.l_state);
166 // `self` and `other` are `Program` instances so it doesn't need to use insert method.
167 let extension = self.container.iter().map(|inst| match inst.tail.state {
168 State(0) => {
169 let mut inst = inst.clone();
170 inst.tail.state = self.l_state + State(1);
171 inst
172 }
173 _ => inst.clone(),
174 });
175 program.container.extend(extension);
176
177 let extension = other.container.iter().map(|inst| {
178 let mut inst = inst.clone();
179 inst.head.state += self.l_state;
180 inst.tail.state += match inst.tail.state {
181 State(0) => State(0),
182 _ => self.l_state,
183 };
184 inst
185 });
186 program.container.extend(extension);
187
188 Ok(program)
189 }
190}
191
192impl<S: Symbol, I> Extend<I> for Program<S>
193where
194 I: IntoIterator<Item = (usize, S, usize, S, Move)>,
195{
196 /// Extends the [`Program`] by tuples of ([`usize`], [`Symbol`], [`usize`],
197 /// [`Symbol`], [`Move`]) the first two elements are going to [`Head`]
198 /// and the last three are going to [`crate::instruction::Tail`].
199 ///
200 /// Returns [`Ok(())`] when the [`Program`] is extended successfully
201 /// and the [`Err(String)`] otherwise.
202 ///
203 /// # Warning
204 /// When the [`Instruction`] can be inserted into the [`Program`]
205 /// the extending interrupt.
206 fn extend(&mut self, iterable: I) -> Result<(), String> {
207 for (h_state, h_symbol, t_state, t_symbol, t_movement) in iterable {
208 self.insert(Instruction::build(
209 State(h_state),
210 h_symbol,
211 State(t_state),
212 t_symbol,
213 t_movement,
214 ))?;
215 }
216 Ok(())
217 }
218}
219
220impl<S: Symbol> Display for Program<S> {
221 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
222 use std::any::type_name;
223
224 write!(
225 f,
226 "Program<{}> {{ alphabet {:?} instuctions: {}, l_state: {} }}",
227 type_name::<S>(),
228 self.alphabet,
229 self.container.len(),
230 self.l_state
231 )
232 }
233}