downsample 0.0.4

use crate::{Aggregatable, Algorithm};
use alloc::vec::Vec;
use core::ops::Range;

#[derive(Debug, Clone, PartialEq)]
pub struct LevelMetadata {
    count: usize,
    relative_downsample: usize,
    algorithm: Algorithm,
}

#[derive(Debug, Clone, PartialEq)]
pub(crate) struct LevelMeta {
    range: Range<usize>,
    relative_downsample: usize,
    algorithm: Algorithm,
}

#[derive(Debug)]
pub(crate) struct Level {
    /// absolut value related to Storate::data, always within LevelMeta::range,
    /// marking the start of the aggregation_buffer
    aggregation_start: usize,
    /// absolut value related to Storate::data, always within LevelMeta::range,
    /// marking the oldest entry == the entry that will be overwritten next
    next: usize,
}

pub struct Storage<T> {
    /// partitioned [LA0,...,LA0,LA1,...,LA1,LA2,...]
    /// LA0 is space for data and overflow data, there is no specific position
    /// for each, as we dont want to move data unnecessarily the count of
    /// LA0 is the count of L0 plus A0.
    pub(crate) data:  Vec<T>,
    pub(crate) level: Vec<(LevelMeta, Level)>,
}

impl LevelMeta {
    pub(crate) fn new(range: Range<usize>, relative_downsample: usize, algorithm: Algorithm) -> Self {
        debug_assert!(
            range.len() >= relative_downsample,
            "range must include enough space to hold a full downsample buffer"
        );
        Self {
            range,
            relative_downsample,
            algorithm,
        }
    }

    #[inline(always)]
    /// start must be inside range
    /// index must be <= range len
    fn range_overflowing_add(range: &Range<usize>, start: usize, index: usize) -> usize {
        debug_assert!(range.contains(&start));
        debug_assert!(index < range.end - range.start);
        let result = start + index;
        if result >= range.end {
            result + range.start - range.end
        } else {
            result
        }
    }

    #[inline(always)]
    fn overflowing_add(&self, start: usize, index: usize) -> usize {
        Self::range_overflowing_add(&self.range, start, index)
    }
}

impl Level {
    pub(crate) fn new(meta: LevelMeta) -> Self {
        let start = meta.range.start;
        Level {
            aggregation_start: start,
            next: start,
        }
    }

    pub(crate) fn build(meta: LevelMeta) -> (LevelMeta, Self) { (meta.clone(), Self::new(meta)) }
}

impl<T> Storage<T>
where
    T: Default,
    T: Clone,
    T: Aggregatable<{ Algorithm::Average }>,
    T: Aggregatable<{ Algorithm::Min }>,
    T: Aggregatable<{ Algorithm::Max }>,
{
    #[inline(always)]
    fn push_level(&mut self, mut value: T, level: usize) -> Option<T> {
        // push level
        let (meta, level) = &mut self.level[level];
        core::mem::swap(&mut self.data[level.next], &mut value);
        level.next += 1;
        if level.next == meta.range.end {
            level.next = meta.range.start;
        }
        if level.next == level.aggregation_start {
            let r = level.aggregation_start..level.aggregation_start + meta.relative_downsample;
            level.aggregation_start = meta.overflowing_add(level.aggregation_start, meta.relative_downsample);
            let list = if r.end >= meta.range.end {
                let end = r.end - meta.range.end;
                let r1 = r.start..meta.range.end;
                let r2 = meta.range.start..meta.range.start + end;
                //println!("overflow detected {r1:?}, {r2:?}");
                //TODO: rather than cloned() just mark the original data as invalid and move it
                // out of vec via unsafe
                self.data[r1].iter().chain(self.data[r2].iter()).cloned()
            } else {
                //TODO: rather than cloned() just mark the original data as invalid and move it
                // out of vec via unsafe
                self.data[r].iter().chain(self.data[0..0].iter()).cloned()
            };
            let agg = match meta.algorithm {
                Algorithm::Average => Aggregatable::<{ Algorithm::Average }>::aggregate(list),
                Algorithm::Min => Aggregatable::<{ Algorithm::Min }>::aggregate(list),
                Algorithm::Max => Aggregatable::<{ Algorithm::Max }>::aggregate(list),
            };
            Some(agg)
        } else {
            None
        }
    }

    pub fn push(&mut self, mut value: T) {
        let mut level = 0;
        while let Some(overflow) = self.push_level(value, level) {
            value = overflow;
            level += 1;
            if level == self.level.len() {
                break;
            }
        }
    }

    pub fn level_metadata(&self, level: usize) -> Option<LevelMetadata> {
        self.level.get(level).map(|(m, _)| LevelMetadata {
            count: m.range.clone().count(),
            relative_downsample: m.relative_downsample,
            algorithm: m.algorithm.clone(),
        })
    }

    // TODO: get_level_data that returns 2 slices, but ordered by age, first slice
    // oldest -> wrap, second slice wrap -> newest

    // TODO: get_level_data that
    // returns 2 slices, but ordered by age, first slice oldest agregation -> wrap,
    // second slice wrap -> newest aggregation

    // TODO: add iterator functions for a level

    /// returns a reference to the whole level data not ordered by time
    /// Note: this also allows to read the buffer for aggregation
    pub fn get_level_data_unordered_raw(&self, level: usize) -> Option<&[T]> {
        if let Some((meta, _)) = self.level.get(level) {
            return Some(&self.data[meta.range.start..meta.range.end]);
        }
        None
    }

    /// return elements by level. where index=0 is the oldest entry in a level
    pub fn get_back_by_level(&self, level: usize, index: usize) -> Option<&T> {
        if let Some((meta, level)) = self.level.get(level) {
            if index >= meta.range.len() - meta.relative_downsample {
                return None;
            }
            let pos = meta.overflowing_add(level.next, index + meta.relative_downsample);
            return Some(&self.data[pos]); //safety, overflowing_add already panics if we are out of range
        }
        None
    }

    /// return elements by level. where index=0 is the oldest entry in a level
    /// Note: this also allows to read the buffer for aggregation
    pub fn get_back_by_level_raw(&self, level: usize, index: usize) -> Option<&T> {
        if let Some((meta, level)) = self.level.get(level) {
            if index >= meta.range.len() {
                return None;
            }
            let pos = meta.overflowing_add(level.next, index);
            return Some(&self.data[pos]); //safety, overflowing_add already panics if we are out of range
        }
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use alloc::vec;

    #[test]
    fn overflow_add() {
        let m = LevelMeta::new(3..5, 1, Algorithm::Average);
        assert_eq!(m.overflowing_add(3, 0), 3);
        assert_eq!(m.overflowing_add(3, 1), 4);

        let m = LevelMeta::new(2..6, 1, Algorithm::Average);
        assert_eq!(m.overflowing_add(4, 0), 4);
        assert_eq!(m.overflowing_add(4, 1), 5);
        assert_eq!(m.overflowing_add(4, 2), 2);
        assert_eq!(m.overflowing_add(4, 3), 3);
    }

    #[test]
    #[should_panic]
    fn overflow_add_panic1() {
        let m = LevelMeta::new(3..5, 1, Algorithm::Average);
        assert_eq!(m.overflowing_add(4, 2), 5);
    }

    #[test]
    #[should_panic]
    fn overflow_add_panic2() {
        let m = LevelMeta::new(3..5, 1, Algorithm::Average);
        assert_eq!(m.overflowing_add(3, 3), 5);
    }

    #[test]
    fn level_constructor() {
        let meta = LevelMeta {
            range: 0..5,
            relative_downsample: 2,
            algorithm: Algorithm::Average,
        };
        let level = Level::new(meta.clone());
        assert_eq!(meta.range, 0..5);
        assert_eq!(level.next, 0);
        assert_eq!(level.aggregation_start, 0);
        assert_eq!(meta.relative_downsample, 2);
        assert_eq!(meta.algorithm, Algorithm::Average);
    }

    #[test]
    fn never_panics() {
        let mut m = Storage {
            data:  vec![0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
            level: vec![
                Level::build(LevelMeta {
                    range: 0..5,
                    relative_downsample: 2,
                    algorithm: Algorithm::Average,
                }),
                Level::build(LevelMeta {
                    range: 5..10,
                    relative_downsample: 2,
                    algorithm: Algorithm::Average,
                }),
            ],
        };
        for i in 0..200000 {
            m.push(i as f32);
        }
    }

    #[test]
    fn low_level_push_test() {
        let mut m = Storage {
            data:  vec![0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
            level: vec![
                Level::build(LevelMeta {
                    range: 0..5,
                    relative_downsample: 2,
                    algorithm: Algorithm::Average,
                }),
                Level::build(LevelMeta {
                    range: 5..10,
                    relative_downsample: 0,
                    algorithm: Algorithm::Average,
                }),
            ],
        };
        m.push(1.0);
        assert_eq!(m.data, vec!(1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0));
        m.push(2.0);
        assert_eq!(m.data, vec!(1.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0));
        m.push(3.0);
        assert_eq!(m.data, vec!(1.0, 2.0, 3.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0));
        m.push(4.0);
        assert_eq!(m.data, vec!(1.0, 2.0, 3.0, 4.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0));
        m.push(5.0);
        assert_eq!(m.data, vec!(1.0, 2.0, 3.0, 4.0, 5.0, 1.5, 0.0, 0.0, 0.0, 0.0));
        m.push(6.0);
        assert_eq!(m.data, vec!(6.0, 2.0, 3.0, 4.0, 5.0, 1.5, 0.0, 0.0, 0.0, 0.0));
        m.push(7.0);
        assert_eq!(m.data, vec!(6.0, 7.0, 3.0, 4.0, 5.0, 1.5, 3.5, 0.0, 0.0, 0.0));
        m.push(8.0);
        assert_eq!(m.data, vec!(6.0, 7.0, 8.0, 4.0, 5.0, 1.5, 3.5, 0.0, 0.0, 0.0));
        m.push(9.0);
        assert_eq!(m.data, vec!(6.0, 7.0, 8.0, 9.0, 5.0, 1.5, 3.5, 5.5, 0.0, 0.0));
        m.push(0.0);
        assert_eq!(m.data, vec!(6.0, 7.0, 8.0, 9.0, 0.0, 1.5, 3.5, 5.5, 0.0, 0.0));
        m.push(1.5);
        assert_eq!(m.data, vec!(1.5, 7.0, 8.0, 9.0, 0.0, 1.5, 3.5, 5.5, 7.5, 0.0));
        m.push(2.5);
        assert_eq!(m.data, vec!(1.5, 2.5, 8.0, 9.0, 0.0, 1.5, 3.5, 5.5, 7.5, 0.0));
        m.push(3.5);
        assert_eq!(m.data, vec!(1.5, 2.5, 3.5, 9.0, 0.0, 1.5, 3.5, 5.5, 7.5, 4.5));
        m.push(4.5);
        assert_eq!(m.data, vec!(1.5, 2.5, 3.5, 4.5, 0.0, 1.5, 3.5, 5.5, 7.5, 4.5));
        m.push(5.5);
        assert_eq!(m.data, vec!(1.5, 2.5, 3.5, 4.5, 5.5, 2.0, 3.5, 5.5, 7.5, 4.5));
        m.push(6.5);
        assert_eq!(m.data, vec!(6.5, 2.5, 3.5, 4.5, 5.5, 2.0, 3.5, 5.5, 7.5, 4.5));
        m.push(7.5);
        assert_eq!(m.data, vec!(6.5, 7.5, 3.5, 4.5, 5.5, 2.0, 4.0, 5.5, 7.5, 4.5));
        m.push(8.5);
        assert_eq!(m.data, vec!(6.5, 7.5, 8.5, 4.5, 5.5, 2.0, 4.0, 5.5, 7.5, 4.5));
        m.push(9.5);
        assert_eq!(m.data, vec!(6.5, 7.5, 8.5, 9.5, 5.5, 2.0, 4.0, 6.0, 7.5, 4.5));
        m.push(0.0);
        assert_eq!(m.data, vec!(6.5, 7.5, 8.5, 9.5, 0.0, 2.0, 4.0, 6.0, 7.5, 4.5));
        m.push(1.0);
        assert_eq!(m.data, vec!(1.0, 7.5, 8.5, 9.5, 0.0, 2.0, 4.0, 6.0, 8.0, 4.5));
    }

    #[test]
    fn low_level_diff_algos_push_test() {
        let mut m = Storage {
            data:  vec![0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
            level: vec![
                Level::build(LevelMeta {
                    range: 0..3,
                    relative_downsample: 2,
                    algorithm: Algorithm::Average,
                }),
                Level::build(LevelMeta {
                    range: 3..6,
                    relative_downsample: 2,
                    algorithm: Algorithm::Min,
                }),
                Level::build(LevelMeta {
                    range: 6..8,
                    relative_downsample: 0,
                    algorithm: Algorithm::Average,
                }),
            ],
        };
        m.push(1.0);
        assert_eq!(m.data, vec!(1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0));
        m.push(2.0);
        assert_eq!(m.data, vec!(1.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0));
        m.push(3.0);
        assert_eq!(m.data, vec!(1.0, 2.0, 3.0, 1.5, 0.0, 0.0, 0.0, 0.0));
        m.push(4.0);
        assert_eq!(m.data, vec!(4.0, 2.0, 3.0, 1.5, 0.0, 0.0, 0.0, 0.0));
        m.push(5.0);
        assert_eq!(m.data, vec!(4.0, 5.0, 3.0, 1.5, 3.5, 0.0, 0.0, 0.0));
        m.push(6.0);
        assert_eq!(m.data, vec!(4.0, 5.0, 6.0, 1.5, 3.5, 0.0, 0.0, 0.0));
        m.push(7.0);
        assert_eq!(m.data, vec!(7.0, 5.0, 6.0, 1.5, 3.5, 5.5, 1.5, 0.0));
        m.push(8.0);
        assert_eq!(m.data, vec!(7.0, 8.0, 6.0, 1.5, 3.5, 5.5, 1.5, 0.0));
        m.push(9.0);
        assert_eq!(m.data, vec!(7.0, 8.0, 9.0, 7.5, 3.5, 5.5, 1.5, 0.0));
        m.push(0.0);
        assert_eq!(m.data, vec!(0.0, 8.0, 9.0, 7.5, 3.5, 5.5, 1.5, 0.0));
        m.push(1.5);
        assert_eq!(m.data, vec!(0.0, 1.5, 9.0, 7.5, 4.5, 5.5, 1.5, 5.5));
    }

    #[test]
    fn get_back_by_level() {
        let mut m = Storage {
            data:  vec![0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
            level: vec![
                Level::build(LevelMeta {
                    range: 0..5,
                    relative_downsample: 2,
                    algorithm: Algorithm::Average,
                }),
                Level::build(LevelMeta {
                    range: 5..10,
                    relative_downsample: 0,
                    algorithm: Algorithm::Average,
                }),
            ],
        };
        for i in 1..10 {
            m.push(i as f32);
        }
        assert_eq!(m.data, vec!(6.0, 7.0, 8.0, 9.0, 5.0, 1.5, 3.5, 5.5, 0.0, 0.0));
        assert_eq!(m.get_back_by_level_raw(0, 0), Some(&5.0));
        assert_eq!(m.get_back_by_level_raw(0, 1), Some(&6.0));
        assert_eq!(m.get_back_by_level_raw(0, 2), Some(&7.0));
        assert_eq!(m.get_back_by_level_raw(0, 3), Some(&8.0));
        assert_eq!(m.get_back_by_level_raw(0, 4), Some(&9.0));
        assert_eq!(m.get_back_by_level_raw(1, 0), Some(&0.0));
        assert_eq!(m.get_back_by_level_raw(1, 1), Some(&0.0));
        assert_eq!(m.get_back_by_level_raw(1, 2), Some(&1.5));
        assert_eq!(m.get_back_by_level_raw(1, 3), Some(&3.5));
        assert_eq!(m.get_back_by_level_raw(1, 4), Some(&5.5));
        assert_eq!(m.get_back_by_level_raw(1, 5), None);
        assert_eq!(m.get_back_by_level(0, 0), Some(&7.0));
        assert_eq!(m.get_back_by_level(0, 1), Some(&8.0));
        assert_eq!(m.get_back_by_level(0, 2), Some(&9.0));
        assert_eq!(m.get_back_by_level(0, 3), None);
        assert_eq!(m.get_back_by_level(0, 4), None);
        assert_eq!(m.get_back_by_level(1, 0), Some(&0.0));
        assert_eq!(m.get_back_by_level(1, 1), Some(&0.0));
        assert_eq!(m.get_back_by_level(1, 2), Some(&1.5));
        assert_eq!(m.get_back_by_level(1, 3), Some(&3.5));
        assert_eq!(m.get_back_by_level(1, 4), Some(&5.5));
    }

    #[test]
    fn get_level_data_unordered_raw() {
        let mut m = Storage {
            data:  vec![0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
            level: vec![
                Level::build(LevelMeta {
                    range: 0..5,
                    relative_downsample: 2,
                    algorithm: Algorithm::Average,
                }),
                Level::build(LevelMeta {
                    range: 5..10,
                    relative_downsample: 0,
                    algorithm: Algorithm::Average,
                }),
            ],
        };
        for i in 1..10 {
            m.push(i as f32);
        }
        assert_eq!(m.data, vec!(6.0, 7.0, 8.0, 9.0, 5.0, 1.5, 3.5, 5.5, 0.0, 0.0));
        assert_eq!(
            m.get_level_data_unordered_raw(0),
            Some([6.0, 7.0, 8.0, 9.0, 5.0].as_slice())
        );
        assert_eq!(
            m.get_level_data_unordered_raw(1),
            Some([1.5, 3.5, 5.5, 0.0, 0.0].as_slice())
        );
    }
}