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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
use crate::Error;
use std::{
    f64::consts::{E, PI},
    sync::Arc,
};

use crate::Elementary::{self, *};

impl<'a> From<&'a str> for Elementary {
    fn from(value: &'a str) -> Self {
        let value: String = value.split_whitespace().collect();
        Self::to_elementary(&value).unwrap()
    }
}
impl Elementary {
    fn split_function(value: &str) -> Vec<&str> {
        let mut interp_slice: Vec<&str> = value.split("").collect();
        // remove the first and last element because they are just empty string slices
        interp_slice.remove(0);
        interp_slice.pop();

        let mut chunks: Vec<&str> = Vec::new();
        let mut open_parenthesis = -1;

        let mut cut_index = 0;

        let mut skip = 0;
        for i in 0..interp_slice.len() {
            // if items need to be skipped (because of the implementation of constants)
            if skip > 0 {
                skip -= 1;
                continue;
            }

            if interp_slice[i] == "(" {
                // this is for the first case of an opening parenthesis. Note that we cannot start
                // at 0 since that would match the case for closing an outer parenthesis
                if open_parenthesis == -1 {
                    open_parenthesis = 1;
                } else {
                    // for all other cases, however, the number of open parentheses just goes up by
                    // one
                    open_parenthesis += 1;
                }
            } else if interp_slice[i] == ")" {
                open_parenthesis -= 1
            }

            // check if outer parenthesis has been closed
            if open_parenthesis == 0 {
                chunks.push(&value[cut_index..=i]);

                // set new cut index
                cut_index = i + 1;

                // reset parenthesis
                open_parenthesis = -1;
            }

            // detect operations and constants
            if open_parenthesis == -1 {
                if interp_slice[i] == "+"
                    || interp_slice[i] == "-"
                    || interp_slice[i] == "*"
                    || interp_slice[i] == "/"
                    || interp_slice[i] == "^"
                {
                    chunks.push(interp_slice[i]);
                    cut_index = i + 1;
                } else if interp_slice[i] == "!" {
                    chunks.push(&value[cut_index..=i]);
                    cut_index = i + 1;
                } else if interp_slice[i] == "x" {
                    chunks.push(&value[cut_index..=i]);
                    cut_index = i + 1;
                } else if interp_slice[i] == "e" {
                    chunks.push(&value[cut_index..=i]);
                    cut_index = i + 1;
                } else if interp_slice[i] == "pi" || interp_slice[i] == "π" {
                    chunks.push("pi");
                    cut_index = i + 1;
                } else {
                    // checking for numbers
                    if let Ok(_) = &value[cut_index..=i].parse::<f64>() {
                        // find the index at which the number ends
                        let mut last_index = i;
                        'index: for j in i + 1..=interp_slice.len() {
                            if let Ok(_) = &value[cut_index..j].parse::<f64>() {
                                last_index = j - 1;
                            } else {
                                break 'index;
                            }
                        }

                        // push the whole number
                        chunks.push(&value[cut_index..=last_index]);

                        // the next couple of indexes must be skipped in order to avoid parsing of
                        // individual digits
                        skip = last_index - i;
                        // by setting skip to the number of difference between the current index
                        // and the index at which the number ends
                        cut_index = last_index + 1;
                    }
                }
            }
        }

        if chunks.is_empty() {
            chunks.push(value);
        }

        chunks
    }

    fn to_elementary(string: &str) -> Result<Self, Error> {
        let strings = Self::split_function(string);

        let mut functions: Vec<ElemRef> = strings
            .clone()
            .iter()
            .map(|s| Self::parse_function(s).unwrap())
            .collect();

        let mut iteration = 0;

        // order of operations
        while functions.len() != 1 {
            if iteration >= 10000 {
                return Err(Error::ParseError(String::from(format!(
                    "Iteration limit reached while parsing function: {string}",
                ))));
            } else {
                iteration += 1;
            }
            // first in the order of operations is powers (seeing as parentheses are handled as a
            // separate case)
            if functions.contains(&ElemRef::Pow) {
                for i in (0..functions.len()).rev() {
                    // find the index of the last power (because we treat this case from right to
                    // left)
                    if i >= functions.len() {
                        continue;
                    }
                    if functions[i] == ElemRef::Pow {
                        let replacement_func = ElemRef::Function(Pow(
                            Arc::new(functions[i - 1].clone().convert()?),
                            Arc::new(functions[i + 1].clone().convert()?),
                        ));
                        functions.remove(i + 1);
                        functions.remove(i);
                        functions.remove(i - 1);
                        functions.insert(i - 1, replacement_func);
                    }
                }

                continue;
            }

            // the factorial function (x ↦ x!) is by convention written in "postfix" notation (i.e.
            // it taeks precedence over normal operations)
            if functions.contains(&ElemRef::Factorial) {
                iterate_operation(&mut functions, ElemRef::Factorial)?;
                continue;
            }

            // next up in the order of operations is multiplication
            if functions.contains(&ElemRef::Mul) {
                iterate_operation(&mut functions, ElemRef::Mul)?;
                continue;
            }

            // we also have to handle implied multiplication. Weather this is handled before or
            // after the explicit multiplication doesn't matter since multiplication is commutative
            // i.e. a*b = b*a

            // check if there is there are any instances of implied multiplication
            for i in 0..functions.len() {
                if i < functions.len() - 1 {
                    if let (ElemRef::Function(func1), ElemRef::Function(func2)) =
                        (&functions[i], &functions[i + 1])
                    {
                        // multiply the two together
                        let replacement_func = ElemRef::Function(Mul(
                            Arc::new(func1.to_owned()),
                            Arc::new(func2.to_owned()),
                        ));

                        // remove the functions and replace them with the multiplied function
                        functions.remove(i + 1);
                        functions.remove(i);
                        functions.insert(i, replacement_func);
                    }
                }
            }
            // next up is division
            if functions.contains(&ElemRef::Div) {
                iterate_operation(&mut functions, ElemRef::Div)?;
                continue;
            }

            // then addition
            if functions.contains(&ElemRef::Add) {
                iterate_operation(&mut functions, ElemRef::Add)?;
                continue;
            }

            // and lastly subtracion
            if functions.contains(&ElemRef::Sub) {
                iterate_operation(&mut functions, ElemRef::Sub)?;
                continue;
            }
        }

        functions
            .pop()
            .expect("Couldn't find a function to parse")
            .convert()
    }

    fn parse_function(string: &str) -> Result<ElemRef, Error> {
        let mut string = string.to_lowercase();

        // unwrap potential parentheses
        if &string[..1] == "(" {
            while &string[..1] == "(" {
                string = string[1..string.len() - 1].to_string();
            }
            return Ok(ElemRef::Function(Self::to_elementary(&string)?));
        }

        // check for special function (independent variable) x, and then check for constants
        if string == "x" {
            return Ok(ElemRef::Function(X));
        } else if let Ok(number) = string.parse::<f64>() {
            return Ok(ElemRef::Function(Con(number)));
        }

        match &string[..] {
            // check in order of operations
            "^" => Ok(ElemRef::Pow),
            "*" => Ok(ElemRef::Mul),
            "/" => Ok(ElemRef::Div),
            "+" => Ok(ElemRef::Add),
            "-" => Ok(ElemRef::Sub),
            // also constants
            "e" => Ok(ElemRef::Function(Con(E))),
            "pi" => Ok(ElemRef::Function(Con(PI))),
            "!" => Ok(ElemRef::Factorial),
            _ => {
                // if we do not have an operation, we must have a function consisting of a function
                // identifier and its contents
                let (func, cont) = split_first(&string, "(");

                // remove outer parenthesis
                let mut graphemes: Vec<&str> = cont.split("").collect();
                // remove the first and last character because they should be parentheses
                graphemes.remove(0);
                graphemes.pop();
                let cont: String = graphemes.iter().map(|x| *x).collect();

                match func {
                    "sin" => Ok(ElemRef::Function(Sin(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "cos" => Ok(ElemRef::Function(Cos(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "tan" => Ok(ElemRef::Function(Tan(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "sec" => Ok(ElemRef::Function(Sec(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "csc" => Ok(ElemRef::Function(Csc(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "cot" => Ok(ElemRef::Function(Cot(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "asin" => Ok(ElemRef::Function(Asin(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "acos" => Ok(ElemRef::Function(Acos(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "atan" => Ok(ElemRef::Function(Atan(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "sinh" => Ok(ElemRef::Function(Sinh(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "cosh" => Ok(ElemRef::Function(Cosh(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "tanh" => Ok(ElemRef::Function(Tanh(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "ln" => Ok(ElemRef::Function(Log(
                        Arc::new(Con(E)), //ln is equivalent to log base e of its contents
                        Arc::new(Self::to_elementary(&cont)?),
                    ))),
                    "abs" => Ok(ElemRef::Function(Abs(Arc::new(Self::to_elementary(
                        &cont,
                    )?)))),
                    "sqrt" => Ok(ElemRef::Function(Pow(
                        Arc::new(Self::to_elementary(&cont)?),
                        Arc::new(Con(0.5)),
                    ))),
                    _ => Err(Error::ParseError(format!(
                        "Function identifier '{func}' not recognized"
                    ))),
                }
            }
        }
    }
}

// all instances of an operation must be handled before the parsing method can move on to the next.
// This is to ensure that the order of operations is being upheld
fn iterate_operation(functions: &mut Vec<ElemRef>, operation: ElemRef) -> Result<(), Error> {
    if functions.contains(&operation) {
        for i in 0..functions.len() {
            if i >= functions.len() {
                continue;
            }

            if functions[i] == operation {
                let replacement_func = match operation {
                    ElemRef::Mul => ElemRef::Function(Mul(
                        Arc::new(functions[i - 1].clone().convert()?),
                        Arc::new(functions[i + 1].clone().convert()?),
                    )),
                    ElemRef::Div => ElemRef::Function(Div(
                        Arc::new(functions[i - 1].clone().convert()?),
                        Arc::new(functions[i + 1].clone().convert()?),
                    )),
                    ElemRef::Add => ElemRef::Function(Add(
                        Arc::new(functions[i + 1].clone().convert()?),
                        Arc::new(functions[i - 1].clone().convert()?),
                    )),
                    ElemRef::Sub => {
                        if i > 0 {
                            ElemRef::Function(Sub(
                                Arc::new(functions[i - 1].clone().convert()?),
                                Arc::new(functions[i + 1].clone().convert()?),
                            ))
                        } else {
                            ElemRef::Function(functions[i + 1].clone().convert()? * (-1 as f64))
                        }
                    }
                    ElemRef::Factorial => {
                        if i > 0 {
                            ElemRef::Function(Factorial(functions[i - 1].clone().convert()?.into()))
                        } else {
                            return Err(Error::ParseError(String::from(
                                "Factorial function must be applied to another function",
                            )));
                        }
                    }
                    _ => unimplemented!("No such operation"), // this point shouldn't be reached
                };

                if operation == ElemRef::Factorial {
                    println!("testing - {replacement_func:?}");
                    // the factorial notation is rather unique, because it always follows directly
                    // after the function upon which it acts.
                    functions.remove(i);
                    functions.remove(i - 1);
                    functions.insert(i - 1, replacement_func)
                } else {
                    // the operation itself as well as the functions surrounding it must be removed
                    functions.remove(i + 1);
                    functions.remove(i);
                    if i > 0 {
                        functions.remove(i - 1);
                        // the combined new function is inserted in the place of the previous functions
                        functions.insert(i - 1, replacement_func);
                    } else {
                        // this is strictly for when a negative number is implied as seen above
                        functions.insert(i, replacement_func)
                    }
                }
            }
        }
    }
    Ok(())
}

// enum to allow operations to be described as the same type without carrying two functions
#[derive(Debug, Clone, PartialEq)]
enum ElemRef {
    Function(Elementary),
    Pow,
    Mul,
    Div,
    Add,
    Sub,
    Factorial,
}
impl ElemRef {
    fn convert(self) -> Result<Elementary, Error> {
        match self {
            Self::Function(elem) => Ok(elem),
            _ => Err(Error::ParseError(String::from(
                "Cannot convert operation to elementary function",
            ))),
        }
    }
}

// splits the provided string at the first index where the specified identifier is found.
// if the identifier is not found, the string will be split at index 0
fn split_first<'a>(string: &'a String, indentifier: &'a str) -> (&'a str, &'a str) {
    let slice: Vec<&str> = string.split("").collect();

    let mut index = 0;
    // find index of first insance of the identifier

    for (i, s) in slice.iter().enumerate().take(string.len()) {
        if *s == indentifier {
            index = i;
            break;
        }
    }

    string.split_at(index - 1)
}