goro 0.2.1

//    Kraken Dynamic Token List Allocator.
//    Copyright 2020 Michael Mestnik

//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Library General Public
//    License as published by the Free Software Foundation; either
//    version 2 of the License.

//    This library 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
//    Library General Public License for more details.

//    You should have received a copy of the GNU Library General Public
//    License along with this library; if not, write to the
//    Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
//    Boston, MA  02110-1301, USA.

//    Copyright 2020 Michael Mestnik

//    Licensed under the Apache License, Version 2.0 (the "License");
//    you may not use this file except in compliance with the License.
//    You may obtain a copy of the License at

//        http://www.apache.org/licenses/LICENSE-2.0

//    Unless required by applicable law or agreed to in writing, software
//    distributed under the License is distributed on an "AS IS" BASIS,
//    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//    See the License for the specific language governing permissions and
//    limitations under the License.

use std::collections::VecDeque;

pub trait Analyst: Sized {
    fn inc(&mut self);
    fn new_size(&mut self) -> usize;
    fn tick<I: Iterator, F>(&mut self, sizes: std::iter::Map<I, F>) -> Option<usize>
    where
        F: FnMut(I::Item) -> usize;
}

#[derive(Debug)]
pub struct DefaultAnalyst {
    allocation_size: usize,
    counter: usize,
    history: VecDeque<usize>,
}

impl DefaultAnalyst {
    fn new(allocation_size: usize, window_size: usize) -> Self {
        let mut history = VecDeque::with_capacity(window_size);
        history.resize(window_size, 0);
        Self {
            allocation_size,
            counter: 0,
            history,
        }
    }
}

impl Analyst for DefaultAnalyst {
    fn inc(&mut self) {
        self.counter += 1;
    }

    fn new_size(&mut self) -> usize {
        self.allocation_size
    }

    fn tick<I: Iterator, F>(&mut self, mut sizes: std::iter::Map<I, F>) -> Option<usize>
    where
        F: FnMut(I::Item) -> usize,
    {
        self.history.push_front(self.counter);
        self.counter = 0;
        let max = *self.history.iter().max().unwrap() + 1;
        self.history.pop_back();
        let size = sizes.next();
        if size.is_none()
            || sizes.count() > 1
            || size.unwrap() < max + self.allocation_size / 4
            || size.unwrap() > max + self.allocation_size + self.allocation_size / 2
        {
            Some(max + self.allocation_size / 2)
        } else {
            None
        }
    }
}

pub trait TokenList: Sized {
    type Error;
    type UserData;

    fn create(size: usize, user_data: &mut Self::UserData) -> Result<Self, Self::Error>;
    fn set_number(&mut self, number: usize);
    fn get_size(&self) -> usize {
        1
    }
}

struct Tokens<T> {
    inner: T,
    size: usize,
}

use std::fmt;
impl<T: fmt::Debug> fmt::Debug for Tokens<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "Tokens {{ inner: {:?}, size: {} }}",
            self.inner, self.size
        )
    }
}

#[derive(Debug)]
pub struct Vector<T: TokenList, S = DefaultAnalyst> {
    inner: Vec<Tokens<T>>,
    index: usize,
    index_ptr: usize,
    analyst: S,
    user_data: T::UserData,
}

impl<T: TokenList> Vector<T, DefaultAnalyst> {
    pub fn new(
        allocation_size: usize,
        window_size: usize,
        user_data: T::UserData,
    ) -> Result<Self, T::Error> {
        Self::new_with_analyst(DefaultAnalyst::new(allocation_size, window_size), user_data)
    }
}

impl<T: TokenList, S: Analyst> Vector<T, S> {
    pub fn new_with_analyst(mut analyst: S, mut user_data: T::UserData) -> Result<Self, T::Error> {
        let inner = T::create(analyst.new_size(), &mut user_data)?;
        let size = inner.get_size();
        Ok(Self {
            inner: vec![Tokens { inner, size }],
            index: 0,
            index_ptr: 0,
            analyst,
            user_data,
        })
    }

    pub fn get_token(&mut self) -> Result<(&mut T, usize), T::Error> {
        self.analyst.inc();
        if self.inner[self.index].size <= self.index_ptr {
            self.inner[self.index].inner.set_number(self.index_ptr);
            self.index += 1;
            if self.inner.len() <= self.index {
                let inner = T::create(self.analyst.new_size(), &mut self.user_data)?;
                let size = inner.get_size();
                self.inner.push(Tokens { inner, size });
                assert_eq!(self.inner.len() - 1, self.index);
            }
            self.index_ptr = 1;
            Ok((&mut self.inner[self.index].inner, 0))
        } else {
            let ret = self.index_ptr;
            self.index_ptr += 1;
            Ok((&mut self.inner[self.index].inner, ret))
        }
    }

    pub fn get_vector(&mut self) -> Vec<&mut T> {
        self.inner[self.index].inner.set_number(self.index_ptr);
        let mut ret = Vec::with_capacity(self.inner.len());
        self.inner
            .iter_mut()
            .take(self.index + 1)
            .for_each(|e| ret.push(&mut e.inner));
        ret
    }

    pub fn tick(&mut self) -> Result<(), T::Error> {
        self.index_ptr = 0;
        self.index = 0;
        if let Some(size) = self.analyst.tick(self.inner.iter().map(|e| e.size)) {
            let inner = T::create(size, &mut self.user_data)?;
            let size = inner.get_size();
            self.inner = vec![Tokens { inner, size }];
        }
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    struct Item(Vec<u32>);
    impl super::TokenList for Item {
        type Error = ();
        type UserData = ();

        fn create(size: usize, _user_data: &mut Self::UserData) -> Result<Self, Self::Error> {
            let mut inner = Vec::with_capacity(size);
            inner.resize(size, 0);
            Ok(Self(inner))
        }
        fn set_number(&mut self, _: usize) {}
        fn get_size(&self) -> usize {
            self.0.len()
        }
    }

    #[test]
    fn basic_counting() {
        let mut thing = super::Vector::<Item>::new(2, 3, ()).unwrap();
        assert_eq!(thing.get_token().unwrap().1, 0);
        assert_eq!(thing.get_token().unwrap().1, 1);
        assert_eq!(thing.get_token().unwrap().1, 0);
        assert_eq!(thing.get_token().unwrap().1, 1);
        assert_eq!(thing.get_token().unwrap().1, 0);
        thing.tick().unwrap();
        assert_eq!(thing.get_token().unwrap().1, 0);
        assert_eq!(thing.get_token().unwrap().1, 1);
        assert_eq!(thing.get_token().unwrap().1, 2);
        assert_eq!(thing.get_token().unwrap().1, 3);
        assert_eq!(thing.get_token().unwrap().1, 4);
        assert_eq!(thing.get_token().unwrap().1, 5);
        assert_eq!(thing.get_token().unwrap().1, 6);
        assert_eq!(thing.get_token().unwrap().1, 0);
        assert_eq!(thing.get_token().unwrap().1, 1);
        assert_eq!(thing.get_token().unwrap().1, 0);
        thing.tick().unwrap();
        assert_eq!(thing.get_token().unwrap().1, 0);
        assert_eq!(thing.get_token().unwrap().1, 1);
        assert_eq!(thing.get_token().unwrap().1, 2);
        assert_eq!(thing.get_token().unwrap().1, 3);
        assert_eq!(thing.get_token().unwrap().1, 4);
        assert_eq!(thing.get_token().unwrap().1, 5);
        assert_eq!(thing.get_token().unwrap().1, 6);
        assert_eq!(thing.get_token().unwrap().1, 7);
        assert_eq!(thing.get_token().unwrap().1, 8);
        assert_eq!(thing.get_token().unwrap().1, 9);
        assert_eq!(thing.get_token().unwrap().1, 10);
        assert_eq!(thing.get_token().unwrap().1, 11);
        assert_eq!(thing.get_token().unwrap().1, 0);
    }
}