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

/*
 * Copyright (C) 2019  Oakes, Gregory <gregory.oakes@outlook.com>
 * Author: Oakes, Gregory <gregory.oakes@outlook.com>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

use num_traits::Num;
use std::{collections::VecDeque, ops::Deref};

pub struct Nibonacci<T> {
    memory: VecDeque<T>,
}

impl<T> Nibonacci<T>
where
    T: Num + Copy,
{
    /// Create a sequence which sums the last L elements to produce the next element
    /// where L is the length of the given signature. The signature elements are the
    /// first elements yielded.
    pub fn new<U>(signature: U) -> Self
    where
        U: IntoIterator,
        U::Item: Deref<Target = T>,
    {
        let mut nib: Nibonacci<T> = Nibonacci {
            memory: VecDeque::new(),
        };
        for sig_elem in signature {
            nib.memory.push_back(*sig_elem);
        }
        nib
    }
}

impl<T> Iterator for Nibonacci<T>
where
    T: Num + Copy,
{
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.memory
            .push_back(self.memory.iter().fold(T::zero(), |sum, i| sum + *i));
        self.memory.pop_front()
    }
}

/// Returns the first `n_elem` elements from a sequence which sums the last L elements to
/// produce the next element where L is the length of the given `signature`. The signature
/// elements are the first elements yielded.
pub fn nibonacci<T, U>(signature: U, n_elem: usize) -> Vec<T>
where
    T: Num + Copy,
    U: IntoIterator,
    U::Item: Deref<Target = T>,
{
    Nibonacci::new(signature).take(n_elem).collect()
}

#[cfg(test)]
mod tests {
    use crate::nibonacci;
    #[test]
    fn test_fibonacci() {
        assert_eq!(
            nibonacci(&[0, 1], 10),
            vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        );
    }

    #[test]
    fn test_tribonacci() {
        assert_eq!(
            nibonacci(&[0., 1., 1.], 10),
            vec![0., 1., 1., 2., 4., 7., 13., 24., 44., 81.]
        );
        assert_eq!(
            nibonacci(&[1., 0., 0.], 10),
            vec![1., 0., 0., 1., 1., 2., 4., 7., 13., 24.]
        );
        assert_eq!(
            nibonacci(&[0., 0., 0.], 10),
            vec![0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]
        );
        assert_eq!(
            nibonacci(&[1., 2., 3.], 10),
            vec![1., 2., 3., 6., 11., 20., 37., 68., 125., 230.]
        );
        assert_eq!(
            nibonacci(&[3., 2., 1.], 10),
            vec![3., 2., 1., 6., 9., 16., 31., 56., 103., 190.]
        );
        assert_eq!(nibonacci(&[1., 1., 1.], 1), vec![1.]);
        assert_eq!(nibonacci(&[300., 200., 100.], 0), vec![]);
        assert_eq!(
            nibonacci(&[0.5, 0.5, 0.5], 30),
            vec![
                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,
                1104.5, 2031.5, 3736.5, 6872.5, 12640.5, 23249.5, 42762.5, 78652.5, 144664.5,
                266079.5, 489396.5, 900140.5, 1655616.5, 3045153.5, 5600910.5, 10301680.5
            ]
        );
    }
}