//! The purpose of "persist-o-vec" is to:
//!
//! - prevent reallocation
//! - re-use freed slots fast
//! - only iter over used slots
//!
//! As such, you must allocate what you need before use up to the maximum determined
//! by the chosen indexer feature. In future there will be an option to increase
//! the capacity if required.
//!
//! ## features available
//!
//! The features available are for the size of the indexing type used internally. This
//! dictates how much extra storage is used for `Vec<T>`. The default is a `u16` which
//! means a possible 2 bytes * 2 per `T`. The maximum entries per Vec for each type are:
//!
//! - `u8` = 256
//! - `u16` = 65026
//! - `u32` = 4228250626
//! - `u64` = 17878103347812890625
//!
//! **WIP!**

use std::cmp::Ordering;
use std::mem::size_of;

#[cfg(feature = "capacity_u8_len")]
type INDEXER = u8;
#[cfg(feature = "capacity_u16_len")]
type INDEXER = u16;
#[cfg(feature = "capacity_u32_len")]
type INDEXER = u32;
#[cfg(feature = "capacity_u64_len")]
type INDEXER = u64;

/// Iteration will not always be in order
#[derive(Clone, Default)]
pub struct Persist<T> {
    entries: Vec<Option<T>>,
    /// contains the indexes to `None` slots
    free: Vec<INDEXER>,
    /// contains the indexes to used slots
    used: Vec<INDEXER>,
}

impl<T> Persist<T> {
    /// Allocate with capacity.
    ///
    /// This is the only way to create a new persistent vec.
    ///
    /// # Panics
    ///
    /// Will panic if the selected capacity is larger than the ability for
    /// `Persist` to internally index in to
    #[inline]
    pub fn with_capacity(capacity: usize) -> Persist<T> {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        if capacity > limit {
            panic!("Selected capacity is larger than ability to index");
        }

        Persist {
            entries: (0..capacity).map(|_| None).collect(),
            free: (0..capacity as INDEXER).rev().collect(),
            used: Vec::with_capacity(capacity),
        }
    }

    /// Allocate with capacity and fill with values produced by a closure
    ///
    /// This is a secondary way to create a new persistent vec and is a good way
    /// to do so if you know the storage needs to be filled.
    ///
    /// # Panics
    ///
    /// Will panic if the selected capacity is larger than the ability for
    /// `Persist` to internally index in to
    #[inline]
    pub fn with_capacity_filled_by<F>(capacity: usize, func: F) -> Persist<T>
    where
        F: Fn() -> T,
    {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        if capacity > limit {
            panic!("Selected capacity is larger than ability to index");
        }

        Persist {
            entries: (0..capacity).map(|_| Some(func())).collect(),
            free: Vec::with_capacity(capacity),
            used: (0..capacity as INDEXER).collect(),
        }
    }

    /// Allocate with capacity and fill with values copied from slice
    ///
    /// # Panics
    ///
    /// Will panic if the selected capacity is larger than the ability for
    /// `Persist` to internally index in to
    #[inline]
    pub fn with_capacity_from(capacity: usize, slice: &[T]) -> Persist<T>
    where
        T: Clone,
    {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        if capacity > limit {
            panic!("Selected capacity is larger than ability to index");
        }

        Persist {
            entries: (0..capacity).map(|i| Some(slice[i].clone())).collect(),
            free: (slice.len() as INDEXER..capacity as INDEXER)
                .rev()
                .collect(),
            used: (0..slice.len() as INDEXER).collect(),
        }
    }

    /// Reserve extra capacity. This may move the allocations and invalidate any
    /// pointers that are held to stored data.
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        if self.entries.len() + additional > limit {
            panic!("Additional capacity is larger than ability to index");
        }

        let old_cap = self.entries.len();
        let new_cap = self.entries.len() + additional;
        self.entries.reserve_exact(additional);
        for _ in old_cap..new_cap {
            self.entries.push(None)
        }
        for i in old_cap..new_cap {
            self.insert_free_record(i as INDEXER);
        }
    }

    /// Returns the actual used length regardless of capacity
    #[inline]
    pub fn len(&self) -> usize {
        self.used.len()
    }

    #[inline]
    pub fn clear(&mut self) {
        let capacity = self.entries.capacity();
        for entry in self.entries.iter_mut() {
            *entry = None;
        }
        self.free = (0..capacity as INDEXER).rev().collect();
        self.used.clear();
    }

    #[inline]
    pub fn get(&self, index: usize) -> Option<&T> {
        if let Some(value) = self.entries.get(index) {
            return value.as_ref();
        }
        None
    }

    #[inline]
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if let Some(value) = self.entries.get_mut(index) {
            return value.as_mut();
        }
        None
    }

    /// Check if there is a value at this index
    #[inline]
    pub fn is_index_live(&self, index: usize) -> bool {
        if let Some(value) = self.entries.get(index) {
            if value.is_some() {
                return true;
            }
        }
        false
    }

    // TODO: feature to expand/reallocate if required
    /// Push `T` on to storage.
    ///
    /// A push is not guaranteed to push in any
    /// particular order if the internal storage has empty locations (typical after
    /// many `remove`). For this reason it will return the index pushed to.
    ///
    /// Returns `None` if there are no free slots left
    #[inline]
    pub fn push(&mut self, value: T) -> Option<usize> {
        if let Some(free_idx) = self.free.pop() {
            self.entries[free_idx as usize] = Some(value);
            // keep self.used ordered
            self.insert_used_record(free_idx);
            return Some(free_idx as usize);
        }
        None
    }

    /// Insert `T` at location. Returns existing value in that location or `None`.
    ///
    /// # Panics
    ///
    /// Will panic is the index is out of range
    #[inline]
    pub fn insert(&mut self, index: usize, value: T) -> Option<T> {
        // check if used first
        if self.entries[index].is_none() {
            if let Ok(free_idx) = self.free.binary_search_by(|probe| {
                // swap ordering so order is big-to-little
                if *probe > index as INDEXER {
                    return Ordering::Less;
                } else if *probe < index as INDEXER {
                    return Ordering::Greater;
                }
                Ordering::Equal
            }) {
                let loc = self.free.remove(free_idx);
                self.insert_used_record(loc);
            }
        }
        let mut entry = Some(value);
        std::mem::swap(&mut self.entries[index], &mut entry);
        return entry;
    }

    /// We need to keep the free records in reverse order so we can generally push
    /// items to the first free slot in ordering from 0-n
    fn insert_free_record(&mut self, index: INDEXER) {
        if let Some(idx) = self
            .free
            .binary_search_by(|probe| {
                // swap ordering so order is big-to-little
                if *probe > index {
                    return Ordering::Less;
                }
                Ordering::Greater
            })
            // we should never find the value we need so use what err returns
            .err()
        {
            self.free.insert(idx, index);
        };
    }

    fn insert_used_record(&mut self, index: INDEXER) {
        // we should never find the value we need so use what err returns
        if let Some(idx) = self.used.binary_search(&index).err() {
            self.used.insert(idx, index);
        };
    }

    /// Pop the last value in the `Persist`
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        if let Some(index) = self.used.pop() {
            let value = std::mem::take(&mut self.entries[index as usize]);
            self.insert_free_record(index);
            return value;
        }
        None
    }

    /// Remove the item at this index and return it if it exists. Does not shift
    /// elements after it to the left.
    #[inline]
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if self.entries[index].is_some() {
            if let Ok(pos) = self.used.binary_search(&(index as INDEXER)) {
                let i = self.used.remove(pos);
                self.insert_free_record(i);
            }
        }
        return std::mem::take(&mut self.entries[index]);
    }

    #[inline]
    pub fn iter(&self) -> Iter<T> {
        Iter {
            entries: &self.entries,
            used: &self.used,
            used_index: 0,
        }
    }

    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            entries: &mut self.entries,
            used: &self.used,
            used_index: 0,
        }
    }
}

#[derive(Debug)]
pub struct Iter<'a, T> {
    entries: &'a [Option<T>],
    used: &'a [INDEXER],
    used_index: usize,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    #[inline]
    fn next(&mut self) -> Option<&'a T> {
        if self.used_index == self.used.len() {
            return None;
        }

        unsafe {
            let index = *self.used.get_unchecked(self.used_index) as usize;
            let value = self.entries.get_unchecked(index).as_ref();
            self.used_index += 1;
            value
        }
    }
}

#[derive(Debug)]
pub struct IterMut<'a, T> {
    entries: &'a mut [Option<T>],
    used: &'a [INDEXER],
    used_index: usize,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    #[inline]
    fn next(&mut self) -> Option<&'a mut T> {
        if self.used_index == self.used.len() {
            return None;
        }

        unsafe {
            let index = *self.used.get_unchecked(self.used_index) as usize;

            // Only used indexes are ever accessed
            let value = self.entries.get_unchecked_mut(index) as *mut Option<T>;
            self.used_index += 1;
            // working around the lifetime elision issue here
            (*value).as_mut()
        }
    }
}

/// Total capacity will be set from the length of the slice
impl<T: Clone> From<&[T]> for Persist<T> {
    fn from(s: &[T]) -> Persist<T> {
        let capacity = s.len();
        Persist::with_capacity_from(capacity, s)
    }
}

/// Total capacity will be set from the length of the slice
impl<T: Clone> From<&mut [T]> for Persist<T> {
    fn from(s: &mut [T]) -> Persist<T> {
        let capacity = s.len();
        Persist::with_capacity_from(capacity, s)
    }
}

#[cfg(test)]
mod tests {
    use crate::{Persist, INDEXER};
    use std::mem::size_of;

    #[test]
    fn with_capacity() {
        let p: Persist<u32> = Persist::with_capacity(10);
        assert_eq!(p.entries.capacity(), 10);
    }

    #[test]
    fn return_none_if_push_when_full() {
        let mut p: Persist<u32> = Persist::with_capacity(30);

        for i in 0..30 {
            assert!(p.push(i).is_some());
        }

        assert!(p.push(31).is_none());
    }

    #[test]
    fn get() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        let two = p.get(1).unwrap();
        assert_eq!(*two, 14);
    }

    #[test]
    fn get_mut() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        {
            let two = p.get_mut(1).unwrap();
            *two *= 2;
        }
        let two = p.get(1).unwrap();
        assert_eq!(*two, 28);
    }

    #[test]
    fn index_validation() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);

        assert!(p.is_index_live(0));
        assert!(p.is_index_live(1));
        assert!(!p.is_index_live(3));
    }

    #[test]
    fn reserve() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        assert_eq!(p.free.len(), 7);
        assert_eq!(p.entries.len(), 10);

        p.reserve(10);

        assert_eq!(p.free.len(), 17);
        assert_eq!(p.entries.len(), 20);
    }

    #[test]
    fn clear() {
        let p: Persist<u32> = Persist::with_capacity(10);
        assert_eq!(p.free.len(), 10);
        assert_eq!(p.free[9], 0);
        assert_eq!(p.free[0], 9);
    }

    #[test]
    fn pop() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        assert_eq!(p.used.len(), 3);
        assert_eq!(p.free.len(), 7);

        p.pop();

        assert_eq!(p.used.len(), 2);
        assert_eq!(p.free.len(), 8);
    }

    #[test]
    fn remove() {
        #[derive(Debug, PartialOrd, PartialEq)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(50);

        for i in 0..50 {
            p.push(Heading { x: i });
        }
        assert_eq!(p.used.len(), 50);

        let r = p.remove(10);
        assert_eq!(r, Some(Heading { x: 10 }));
        assert!(p.entries[10].is_none());
        assert_eq!(p.used.len(), 49);
        assert_eq!(p.free.len(), 1);

        let r = p.remove(20);
        assert_eq!(r, Some(Heading { x: 20 }));
        assert!(p.entries[20].is_none());
        assert_eq!(p.used.len(), 48);
        assert_eq!(p.free.len(), 2);

        let r = p.remove(30);
        assert_eq!(r, Some(Heading { x: 30 }));
        assert!(p.entries[30].is_none());
        assert_eq!(p.used.len(), 47);
        assert_eq!(p.free.len(), 3);

        let r = p.remove(22);
        assert_eq!(r, Some(Heading { x: 22 }));
        assert!(p.entries[22].is_none());
        assert_eq!(p.used.len(), 46);
        assert_eq!(p.free.len(), 4);
    }

    #[test]
    fn insert() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        assert_eq!(p.used.len(), 3);
        assert_eq!(p.free.len(), 7);

        let previous = p.insert(0, 16).unwrap();
        assert_eq!(previous, 13);
        assert_eq!(p.get(0), Some(&16));
        assert_eq!(p.free.len(), 7);
        assert_eq!(p.used.len(), 3);

        assert!(p.insert(5, 17).is_none());
        assert_eq!(p.get(5), Some(&17));
        assert_eq!(p.free.len(), 6);
        assert_eq!(p.used.len(), 4);
    }

    #[test]
    fn iter() {
        #[derive(Debug)]
        struct Heading {
            x: usize,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(10);

        p.push(Heading { x: 13 });
        p.push(Heading { x: 14 });
        p.push(Heading { x: 15 });
        assert_eq!(p.used.len(), 3);

        let mut accum = 0;
        for (i, x) in p.iter().enumerate() {
            assert_eq!(x.x, 13 + i);
            accum += x.x;
        }
        assert_eq!(accum, 42);
    }

    #[test]
    fn iter_mut() {
        #[derive(Debug)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(10);

        p.push(Heading { x: 6 });
        p.push(Heading { x: 6 });
        p.push(Heading { x: 6 });
        assert_eq!(p.used.len(), 3);

        for x in p.iter_mut() {
            x.x += 1;
        }

        for x in p.iter() {
            assert_eq!(x.x, 7);
        }
    }

    #[test]
    fn iter_over_removed() {
        #[derive(Debug, PartialOrd, PartialEq)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(50);

        for i in 0..50 {
            p.push(Heading { x: i });
        }
        assert_eq!(p.used.len(), 50);

        let r = p.remove(10);
        assert_eq!(r, Some(Heading { x: 10 }));
        assert!(p.entries[10].is_none());

        let r = p.remove(20);
        assert_eq!(r, Some(Heading { x: 20 }));
        assert!(p.entries[20].is_none());

        let r = p.remove(30);
        assert_eq!(r, Some(Heading { x: 30 }));
        assert!(p.entries[30].is_none());

        for head in p.iter() {
            assert_ne!(head.x, 10);
            assert_ne!(head.x, 20);
            assert_ne!(head.x, 30);
        }
    }

    #[cfg(feature = "capacity_u8_len")]
    #[test]
    #[should_panic]
    fn panic_if_cap_gt_u8() {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        let _: Persist<u8> = Persist::with_capacity(limit + 1);
    }

    #[cfg(feature = "capacity_u16_len")]
    #[test]
    #[should_panic]
    fn panic_if_cap_gt_u16() {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        // actual addressing is 0 to 65025, so bump up by 1
        let _: Persist<u8> = Persist::with_capacity(limit + 1);
    }

    #[cfg(feature = "capacity_u32_len")]
    #[test]
    #[should_panic]
    fn panic_if_cap_gt_u32() {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        let _: Persist<u8> = Persist::with_capacity(limit + 1);
    }

    #[cfg(feature = "capacity_u64_len")]
    #[test]
    #[should_panic]
    fn panic_if_cap_gt_u64() {
        let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
        let _: Persist<u8> = Persist::with_capacity(limit + 1);
    }

    #[cfg(feature = "capacity_u16_len")]
    #[test]
    fn populate() {
        const LIMIT: usize = 65025;

        let mut persist = Persist::with_capacity(LIMIT);
        for _ in 0..LIMIT {
            persist.push(10);
        }

        for i in 0..LIMIT {
            persist.remove(i);
        }
    }

    #[test]
    fn pst_remove_and_push() {
        #[cfg(feature = "capacity_u8_len")]
        const LIMIT: usize = 255; //65025;
        #[cfg(any(
            feature = "capacity_u16_len",
            feature = "capacity_u32_len",
            feature = "capacity_u64_len"
        ))]
        const LIMIT: usize = 10_000; //65025;

        struct Velocity(f32);

        let mut persist = Persist::with_capacity(LIMIT);
        assert_eq!(persist.free.len(), LIMIT);

        for _ in 0..LIMIT {
            persist.push(Velocity(1.0));
        }
        assert_eq!(persist.used.len(), LIMIT);

        let mut a = 0.0;
        for _ in 0..100 {
            let b = persist.remove(9).unwrap();
            a += b.0;
            let b = persist.remove(20).unwrap();
            a += b.0;
            let b = persist.remove(77).unwrap();
            a += b.0;
            let b = persist.remove(4).unwrap();
            a += b.0;
            let b = persist.remove(100).unwrap();
            a += b.0;
            let b = persist.remove(200).unwrap();
            a += b.0;
            let b = persist.remove(222).unwrap();
            a += b.0;

            persist.push(Velocity(1.0));
            persist.push(Velocity(1.0));
            persist.push(Velocity(1.0));
            persist.push(Velocity(1.0));
            persist.push(Velocity(1.0));
            persist.push(Velocity(1.0));
            persist.push(Velocity(1.0));
        }
    }

    #[test]
    fn from_slice_reserve() {
        let ar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let mut persist = Persist::from(&ar[..]);
        assert_eq!(persist.len(), 10);
        persist.reserve(10);
        assert_eq!(persist.len(), 10);
        assert_eq!(persist.entries.len(), 20);
    }

    #[test]
    #[should_panic]
    fn panic_out_of_bounds() {
        let ar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let mut persist = Persist::from(&ar[..]);
        assert_eq!(persist.len(), 10);
        persist.insert(10, 10);
    }

    #[test]
    fn insert_at_end() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.insert(9, 15);

        let x = p.get(9).unwrap();
        assert_eq!(*x, 15);

        let mut accum = 0;
        for (i, v) in p.iter().enumerate() {
            assert_eq!(i, 0);
            assert_eq!(*v, 15);
            accum += 1;
        }
        assert_eq!(accum, 1);

        let mut accum = 0;
        for (i, v) in p.iter_mut().enumerate() {
            assert_eq!(i, 0);
            assert_eq!(*v, 15);
            accum += 1;
        }
        assert_eq!(accum, 1);
    }
}