nibonacci/
lib.rs

1/*
2 * Copyright (C) 2019  Oakes, Gregory <gregory.oakes@outlook.com>
3 * Author: Oakes, Gregory <gregory.oakes@outlook.com>
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 */
18
19use num_traits::Num;
20use std::{collections::VecDeque, ops::Deref};
21
22pub struct Nibonacci<T> {
23    memory: VecDeque<T>,
24}
25
26impl<T> Nibonacci<T>
27where
28    T: Num + Copy,
29{
30    /// Create a sequence which sums the last L elements to produce the next element
31    /// where L is the length of the given signature. The signature elements are the
32    /// first elements yielded.
33    pub fn new<U>(signature: U) -> Self
34    where
35        U: IntoIterator,
36        U::Item: Deref<Target = T>,
37    {
38        let mut nib: Nibonacci<T> = Nibonacci {
39            memory: VecDeque::new(),
40        };
41        for sig_elem in signature {
42            nib.memory.push_back(*sig_elem);
43        }
44        nib
45    }
46}
47
48impl<T> Iterator for Nibonacci<T>
49where
50    T: Num + Copy,
51{
52    type Item = T;
53    fn next(&mut self) -> Option<Self::Item> {
54        self.memory
55            .push_back(self.memory.iter().fold(T::zero(), |sum, i| sum + *i));
56        self.memory.pop_front()
57    }
58}
59
60/// Returns the first `n_elem` elements from a sequence which sums the last L elements to
61/// produce the next element where L is the length of the given `signature`. The signature
62/// elements are the first elements yielded.
63pub fn nibonacci<T, U>(signature: U, n_elem: usize) -> Vec<T>
64where
65    T: Num + Copy,
66    U: IntoIterator,
67    U::Item: Deref<Target = T>,
68{
69    Nibonacci::new(signature).take(n_elem).collect()
70}
71
72#[cfg(test)]
73mod tests {
74    use crate::nibonacci;
75    #[test]
76    fn test_fibonacci() {
77        assert_eq!(
78            nibonacci(&[0, 1], 10),
79            vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
80        );
81    }
82
83    #[test]
84    fn test_tribonacci() {
85        assert_eq!(
86            nibonacci(&[0., 1., 1.], 10),
87            vec![0., 1., 1., 2., 4., 7., 13., 24., 44., 81.]
88        );
89        assert_eq!(
90            nibonacci(&[1., 0., 0.], 10),
91            vec![1., 0., 0., 1., 1., 2., 4., 7., 13., 24.]
92        );
93        assert_eq!(
94            nibonacci(&[0., 0., 0.], 10),
95            vec![0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]
96        );
97        assert_eq!(
98            nibonacci(&[1., 2., 3.], 10),
99            vec![1., 2., 3., 6., 11., 20., 37., 68., 125., 230.]
100        );
101        assert_eq!(
102            nibonacci(&[3., 2., 1.], 10),
103            vec![3., 2., 1., 6., 9., 16., 31., 56., 103., 190.]
104        );
105        assert_eq!(nibonacci(&[1., 1., 1.], 1), vec![1.]);
106        assert_eq!(nibonacci(&[300., 200., 100.], 0), vec![]);
107        assert_eq!(
108            nibonacci(&[0.5, 0.5, 0.5], 30),
109            vec![
110                0.5, 0.5, 0.5, 1.5, 2.5, 4.5, 8.5, 15.5, 28.5, 52.5, 96.5, 177.5, 326.5, 600.5,
111                1104.5, 2031.5, 3736.5, 6872.5, 12640.5, 23249.5, 42762.5, 78652.5, 144664.5,
112                266079.5, 489396.5, 900140.5, 1655616.5, 3045153.5, 5600910.5, 10301680.5
113            ]
114        );
115    }
116}