use std::marker;
use std::mem;
use std::slice;

use crate::storage::{Storage, OneToNStorage, IntoIter, IntoIterMut, SliceView, SliceViewMut};
use densevec::DenseVec;
use crate::sync::{ReadGuardRef, WriteGuardRef};
use crate::utils::*;

//TODO: implement parallel storage

#[derive(Clone, Copy, Debug)]
pub struct Group{
    first_index: usize,
    len: usize,
}

#[derive(Clone, Copy, Debug)]
pub struct GroupChanged{
    first_index: usize,
    len: usize,
    changed: bool,
}

pub trait GroupExt: Copy {
    fn new(first_index: usize, len: usize) -> Self where Self: Sized;
    fn first_index(&self) -> usize;
    fn len(&self) -> usize;
    fn offset(&mut self, pos: isize);
    fn resize(&mut self, newlen: usize);
    fn changed_mut(&mut self) -> Option<&mut bool>;
    fn changed(&self) -> bool;
    fn mark_changed(&mut self);
}

impl GroupExt for Group{
    #[inline]
    fn new(first_index: usize, len: usize) -> Self where Self: Sized{
        Group{
            first_index,
            len,
        }
    }

    #[inline]
    fn first_index(&self) -> usize{
        self.first_index
    }

    #[inline]
    fn len(&self) -> usize{
        self.len
    }

    #[inline]
    fn offset(&mut self, pos: isize){
        self.first_index = (self.first_index as isize + pos) as usize
    }

    #[inline]
    fn resize(&mut self, newlen: usize){
        self.len = newlen
    }

    #[inline]
    fn changed_mut(&mut self) -> Option<&mut bool>{
        None
    }

    #[inline]
    fn changed(&self) -> bool{
        false
    }

    #[inline]
    fn mark_changed(&mut self){}
}

impl GroupExt for GroupChanged{
    #[inline]
    fn new(first_index: usize, len: usize) -> Self where Self: Sized{
        GroupChanged{
            first_index,
            len,
            changed: false,
        }
    }

    #[inline]
    fn first_index(&self) -> usize{
        self.first_index
    }

    #[inline]
    fn len(&self) -> usize{
        self.len
    }

    #[inline]
    fn offset(&mut self, pos: isize){
        self.first_index = (self.first_index as isize + pos) as usize
    }

    #[inline]
    fn resize(&mut self, newlen: usize){
        self.len = newlen
    }

    #[inline]
    fn changed_mut(&mut self) -> Option<&mut bool>{
        Some(&mut self.changed)
    }

    #[inline]
    fn changed(&self) -> bool{
        self.changed
    }

    #[inline]
    fn mark_changed(&mut self){
        self.changed = true;
    }
}

pub type DenseOneToNVec<T> = _DenseOneToNVec<T, Group>;
pub type ChangeDenseOneToNVec<T> = _DenseOneToNVec<T, GroupChanged>;

pub struct _DenseOneToNVec<T, G>{
    vec: Vec<T>,
    index: DenseVec<G>,
    ids: Vec<usize>,
}

impl<'a, T: 'a, G: GroupExt + 'a> OneToNStorage<'a,T> for _DenseOneToNVec<T,G>{
    fn insert_slice<I: IntoIterator<Item = T>>(&mut self, guid: usize, t: I){
        let needs_update;
        let insert_len;
        {
            let group = self.index.entry(guid)
                .or_insert(G::new(self.vec.len(), 0));
            if group.len() != 0 {
                group.mark_changed()
            }
            let prev_len = self.vec.len();
            if prev_len == group.first_index() {
                self.vec.extend(t.into_iter());
                self.ids.extend(prev_len .. self.vec.len());
                insert_len = self.vec.len() - prev_len;
                let newlen = group.len() + insert_len;
                group.resize(newlen);
                needs_update = false;
            }else{
                let rest = self.vec.split_off(group.first_index() + group.len());
                self.vec.extend(t.into_iter().chain(rest));
                insert_len = self.vec.len() - prev_len;
                let newlen = group.len() + insert_len;
                group.resize(newlen);
                self.ids.extend(prev_len..self.vec.len());
                needs_update = true;
            }
        }

        if needs_update {
            //TODO: can this be optimized by not going thorugh all groups?
            let group = unsafe{ *self.index.get_unchecked(guid) };
            for other_group in self.index.values_mut() {
                if other_group.first_index() > group.first_index() {
                    other_group.offset(insert_len as isize);
                }
            }
        }
    }

    unsafe fn get_slice(&self, guid: usize) -> SliceView<T> {
        let slice = self.index.get_unchecked(guid);
        // &self.vec[slice.first_index..slice.first_index + slice.len]

        let ptr = self.vec.as_ptr().offset(slice.first_index() as isize);
        SliceView{
            slice: slice::from_raw_parts(ptr, slice.len()),
            might_changed: slice.changed()
        }
    }

    unsafe fn get_slice_mut(&mut self, guid: usize) -> SliceViewMut<T> {
        let slice = self.index.get_unchecked_mut(guid);
        // &mut self.vec[slice.first_index..slice.first_index + slice.len]

        let ptr = self.vec.as_mut_ptr().offset(slice.first_index() as isize);
        SliceViewMut{
            slice: slice::from_raw_parts_mut(ptr, slice.len()),
            might_changed: slice.changed_mut(),
        }
    }
}



impl<'a, T: 'a, G: GroupExt + 'a> Storage<'a, T> for _DenseOneToNVec<T, G>{
    type Get = SliceView<'a,T>;
    type GetMut = SliceViewMut<'a,T>;
    type DerefTarget = [T];
    type IdedIter = IdedIter<'a, T, G>;
    type Iter = Iter<'a, T, G>;
    type IterMut = IterMut<'a, T, G>;

    fn new() -> _DenseOneToNVec<T, G>{
        _DenseOneToNVec{
            vec: vec![],
            index: DenseVec::new(),
            ids: vec![],
        }
    }

    fn with_capacity(capacity: usize) -> _DenseOneToNVec<T, G>{
        _DenseOneToNVec{
            vec: Vec::with_capacity(capacity),
            index: DenseVec::new(),
            ids: vec![],
        }
    }

    fn insert(&mut self, guid: usize, t: T){
        let needs_update;
        {
            let group = self.index.entry(guid)
                .or_insert(G::new(self.vec.len(), 0));
            if group.len() != 0 {
                group.mark_changed()
            }
            self.vec.insert(group.first_index() + group.len(), t);
            let newlen = group.len() + 1;
            group.resize(newlen);
            self.ids.push(self.vec.len() - 1);
            needs_update = group.first_index() + group.len() < self.vec.len();
        }

        //TODO: can this be optimized by not going thorugh all groups?
        if needs_update {
            let group = unsafe{ *self.index.get_unchecked(guid) };
            for other_group in self.index.values_mut() {
                if other_group.first_index() > group.first_index() {
                    other_group.offset(1);
                }
            }
        }
    }

    fn remove(&mut self, guid: usize){
        if let Some(group) = self.index.remove(guid) {
            self.vec.drain(group.first_index() .. group.first_index() + group.len()).count();
            for i in group.first_index() .. group.first_index() + group.len(){
                if let Some(i) = self.ids.iter().position(|id| *id == i){
                    self.ids.remove(i);
                }
            }
            //TODO: can this be optimized by not going thorugh all groups?
            for other_group in self.index.values_mut() {
                if other_group.first_index() > group.first_index() {
                    other_group.offset(-(group.len() as isize));
                }
            }
        }
    }

    unsafe fn get(&self, guid: usize) -> SliceView<'a,T>{
        mem::transmute(self.get_slice(guid))
    }

    unsafe fn get_mut(&mut self, guid: usize) -> SliceViewMut<'a,T>{
        mem::transmute(self.get_slice_mut(guid))
    }

    unsafe fn fast_get(&self, guid: usize) -> SliceView<'a,T>{
        mem::transmute(self.get_slice(guid))
    }

    unsafe fn fast_get_mut(&mut self, guid: usize) -> SliceViewMut<'a,T>{
        mem::transmute(self.get_slice_mut(guid))
    }

    fn fast_index(&self, guid: usize) -> usize{
        guid
    }

    fn guid_from_fast_index(&self, idx: usize) -> usize{
        idx
    }

    fn contains(&self, guid: usize) -> bool{
        self.index.contains_key(guid)
    }

    fn iter(&self) -> Self::Iter{
        unsafe{
            Iter{
                storage: delete_lifetime(&self.vec),
                it: mem::transmute::<densevec::Values<G>, densevec::Values<G>>(self.index.values()),
                _marker: marker::PhantomData,
            }
        }
    }

    fn iter_mut(&mut self) -> Self::IterMut{
        unsafe{
            IterMut{
                storage: delete_lifetime_mut(&mut self.vec),
                it: mem::transmute::<densevec::ValuesMut<G>, densevec::ValuesMut<G>>(self.index.values_mut()),
                _marker: marker::PhantomData,
            }
        }
    }

    fn ided_iter(&self) -> Self::IdedIter{
        unsafe{
            IdedIter{
                storage: delete_lifetime(&self.vec),
                it: mem::transmute::<densevec::Iter<usize, G>, densevec::Iter<usize, G>>(self.index.iter()),
                _marker: marker::PhantomData,
            }
        }
    }
}


// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a, G: GroupExt + 'a> ParStorage<'a, T> for _DenseOneToNVec<T,G>
// where
//     T: Sync + Send,
//     G: Sync,
//     Self::Get: Send,
//     Self::GetMut: Send
// {
//     type ParIter = ParOneToNDenseIter<'a, T, G>;
//     type ParIterMut = ParOneToNDenseIterMut<'a, T, G>;

//     fn par_iter(&self) -> Self::ParIter{
//         ParOneToNDenseIter{
//             iter: unsafe{ mem::transmute::<
//                 rayon::slice::Iter<G>,
//                 rayon::slice::Iter<G>>(self.index.par_values()) },
//             storage: ReadGuardRef::new(ReadGuard::Reference(self)),
//         }
//     }

//     fn par_iter_mut(&mut self) -> Self::ParIterMut{
//         let iter = unsafe{ mem::transmute::<slice::IterMut<G>, slice::IterMut<G>>(self.index.values_mut()) };
//         ParOneToNDenseIterMut{
//             iter,
//             storage: ReadGuardRef::new(ReadGuard::Reference(self)),
//         }
//     }
// }


pub struct IdedIter<'a, T: 'a, G>{
    storage: &'a Vec<T>,
    it: densevec::Iter<'a, usize, G>,
    _marker: marker::PhantomData<&'a T>,
}

impl<'a, T: 'a, G: GroupExt> Iterator for IdedIter<'a, T, G>{
    type Item = (usize, SliceView<'a,T>);
    fn next(&mut self) -> Option<(usize, SliceView<'a,T>)>{
        self.it.next().map(|(id, group)| {
            // let v = &mut self.storage.vec[group.first_index..group.first_index + group.len];
            // unsafe{mem::transmute::<&mut [T], &mut [T]>(v)}
            unsafe{
                let ptr = self.storage.as_ptr().offset(group.first_index() as isize);
                (id, SliceView{
                    slice: slice::from_raw_parts(ptr, group.len()) ,
                    might_changed: group.changed()
                })
            }
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<'a, T: 'a, G: GroupExt> ExactSizeIterator for IdedIter<'a, T, G>{
    #[inline]
    fn len(&self) -> usize {
        self.it.len()
    }
}

pub struct Iter<'a, T: 'a, G>{
    storage: &'a Vec<T>,
    it: densevec::Values<'a, G>,
    _marker: marker::PhantomData<&'a T>,
}

impl<'a, T: 'a, G: GroupExt> Iterator for Iter<'a, T, G>{
    type Item = SliceView<'a,T>;
    fn next(&mut self) -> Option<SliceView<'a,T>>{
        self.it.next().map(|group| {
            // let v = &mut self.storage.vec[group.first_index..group.first_index + group.len];
            // unsafe{mem::transmute::<&mut [T], &mut [T]>(v)}
            unsafe{
                let ptr = self.storage.as_ptr().offset(group.first_index() as isize);
                SliceView{
                    slice: slice::from_raw_parts(ptr, group.len()),
                    might_changed: group.changed(),
                }
            }
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

pub struct IterMut<'a, T: 'a, G>{
    storage: &'a mut Vec<T>,
    it: densevec::ValuesMut<'a, G>,
    _marker: marker::PhantomData<&'a T>,
}

impl<'a, T: 'a, G: GroupExt> Iterator for IterMut<'a, T, G>{
    type Item = SliceViewMut<'a,T>;
    fn next(&mut self) -> Option<SliceViewMut<'a,T>>{
        self.it.next().map(|group| {
            // let v = &mut self.storage.vec[group.first_index..group.first_index + group.len];
            // unsafe{mem::transmute::<&mut [T], &mut [T]>(v)}
            unsafe{
                let ptr = self.storage.as_mut_ptr().offset(group.first_index() as isize);
                SliceViewMut{
                    slice: slice::from_raw_parts_mut(ptr, group.len()),
                    might_changed: group.changed_mut(),
                }
            }
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<'a, T: 'a, G: GroupExt> ExactSizeIterator for IterMut<'a, T, G>{
    #[inline]
    fn len(&self) -> usize {
        self.it.len()
    }
}

pub struct OneToNDenseIter<'a, T: 'a, G>{
    storage: ReadGuardRef<'a, _DenseOneToNVec<T, G>>,
    it: densevec::Values<'a, G>,
}

impl<'a, T: 'a, G: GroupExt> Iterator for OneToNDenseIter<'a, T, G>{
    type Item = SliceView<'a,T>;
    fn next(&mut self) -> Option<SliceView<'a,T>>{
        self.it.next().map(|group| {
            let v = &self.storage.vec[group.first_index() .. group.first_index() + group.len()];
            SliceView{
                slice: unsafe{mem::transmute::<&[T], &[T]>(v)},
                might_changed: group.changed(),
            }
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<'a, T: 'a, G: GroupExt> ExactSizeIterator for OneToNDenseIter<'a, T, G>{
    #[inline]
    fn len(&self) -> usize {
        self.it.len()
    }
}

impl<'a, T, G: GroupExt> IntoIter for ReadGuardRef<'a, _DenseOneToNVec<T, G>>{
    type Iter = OneToNDenseIter<'a, T, G>;
    fn into_iter(self) -> OneToNDenseIter<'a, T, G>{
        let it = unsafe{ mem::transmute::<densevec::Values<G>, densevec::Values<G>>(self.index.values()) };
        OneToNDenseIter{
            it,
            storage: self,
        }
    }
}

pub struct OneToNDenseIterMut<'a, T: 'a, G>{
    storage: WriteGuardRef<'a, _DenseOneToNVec<T, G>>,
    it: densevec::ValuesMut<'a, G>,
}

impl<'a, T: 'a, G: GroupExt> Iterator for OneToNDenseIterMut<'a, T, G>{
    type Item = SliceViewMut<'a, T>;
    fn next(&mut self) -> Option<SliceViewMut<'a, T>>{
        self.it.next().map(|group| {
            // let v = &mut self.storage.vec[group.first_index..group.first_index + group.len];
            // unsafe{mem::transmute::<&mut [T], &mut [T]>(v)}
            unsafe{
                let ptr = self.storage.vec.as_mut_ptr().offset(group.first_index() as isize);
                SliceViewMut{
                    slice: slice::from_raw_parts_mut(ptr, group.len()),
                    might_changed: group.changed_mut(),
                }
            }
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<'a, T: 'a, G: GroupExt> ExactSizeIterator for OneToNDenseIterMut<'a, T, G>{
    #[inline]
    fn len(&self) -> usize {
        self.it.len()
    }
}


impl<'a, T, G: GroupExt> IntoIterMut for WriteGuardRef<'a, _DenseOneToNVec<T, G>>{
    type IterMut = OneToNDenseIterMut<'a, T, G>;
    fn into_iter_mut(mut self) -> OneToNDenseIterMut<'a, T, G>{
        let it = unsafe{ mem::transmute::<densevec::ValuesMut<G>, densevec::ValuesMut<G>>(self.index.values_mut()) };
        OneToNDenseIterMut{
            it,
            storage: self,
        }
    }
}

// #[cfg(feature = "parallel_iter")]
// pub struct ParOneToNDenseIter<'a, T: 'a + Sync, G: Sync>{
//     storage: ReadGuardRef<'a, _DenseOneToNVec<T,G>>,
//     iter: rayon::slice::Iter<'a, G>,
// }

// #[cfg(feature = "parallel_iter")]
// unsafe impl<'a, T: 'a + Sync, G: Sync> Send for ParOneToNDenseIter<'a, T, G>{}

// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a + Sync, G: GroupExt + Sync> ParallelIterator for ParOneToNDenseIter<'a, T, G>{
//     type Item = SliceView<'a,T>;
//     #[inline]
//     fn drive_unindexed<C>(self, consumer: C) -> C::Result
//         where C: UnindexedConsumer<Self::Item>
//     {
//         let vec = &self.storage.vec;
//         self.iter
//             .map(|group| {
//                 //&vec[group.first_index..group.first_index + group.len]

//                 unsafe{
//                     let ptr = vec.as_ptr().offset(group.first_index() as isize);
//                     SliceView{
//                         slice: slice::from_raw_parts(ptr, group.len()),
//                         changed: group.changed(),
//                     }
//                 }
//             })
//             .drive_unindexed(consumer)
//     }
// }

// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a + Sync, G: GroupExt + Sync> IndexedParallelIterator for ParOneToNDenseIter<'a, T, G>{
//     fn len(&self) -> usize {
//         self.storage.index.len()
//     }

//     fn drive<C>(self, consumer: C) -> C::Result
//         where C: Consumer<Self::Item>
//     {
//         let vec = &self.storage.vec;
//         self.iter
//             .map(move |group| {
//                 //&vec[group.first_index..group.first_index + group.len]

//                 unsafe{
//                     let ptr = vec.as_ptr().offset(group.first_index() as isize);
//                     SliceView{
//                         slice: slice::from_raw_parts(ptr, group.len()),
//                         changed: group.changed(),
//                     }
//                 }
//             })
//             .drive(consumer)
//     }

//     fn with_producer<CB>(self, callback: CB) -> CB::Output
//         where CB: ProducerCallback<Self::Item>
//     {
//         let vec = &self.storage.vec;
//         self.iter
//             .map(move |group| {
//                 //&vec[group.first_index..group.first_index + group.len]

//                 unsafe{
//                     let ptr = vec.as_ptr().offset(group.first_index() as isize);
//                     SliceView{
//                         slice: slice::from_raw_parts(ptr, group.len()),
//                         changed: group.changed(),
//                     }
//                 }
//             })
//             .with_producer(callback)
//     }
// }

// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a + Sync, G: GroupExt + Sync> IntoParIter for ReadGuardRef<'a, _DenseOneToNVec<T, G>>{
//     type Iter = ParOneToNDenseIter<'a, T, G>;
//     fn into_pariter(self) -> ParOneToNDenseIter<'a, T, G>{
//         ParOneToNDenseIter{
//             iter: unsafe{ mem::transmute::<
//                 rayon::slice::Iter<G>,
//                 rayon::slice::Iter<G>>(self.index.par_values()) },
//             storage: self,
//         }
//     }
// }


// #[cfg(feature = "parallel_iter")]
// pub struct ParOneToNDenseIterMut<'a, T: 'a + Sync>{
//     storage: RwLockWriteGuard<'a, DenseOneToNVec<T>>,
//     iter: rayon::slice::Iter<'a,Group>,
// }

// #[cfg(feature = "parallel_iter")]
// unsafe impl<'a, T: 'a + Sync> Send for ParOneToNDenseIterMut<'a, T>{}

// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a + Sync + Send> ParallelIterator for ParOneToNDenseIterMut<'a, T>{
//     type Item = &'a mut [T];
//     #[inline]
//     fn drive_unindexed<C>(self, consumer: C) -> C::Result
//         where C: UnindexedConsumer<Self::Item>
//     {
//         let vec: &mut Vec<T> = unsafe{ mem::transmute(&mut self.storage.vec) };
//         self.iter
//             .map(|group| &mut vec[group.first_index..group.first_index + group.len])
//             .drive_unindexed(consumer)
//     }
// }

// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a + Sync> IndexedParallelIterator for ParOneToNDenseIterMut<'a, T>{
//     fn len(&self) -> usize {
//         self.storage.index.len()
//     }

//     fn drive<C>(self, consumer: C) -> C::Result
//         where C: Consumer<Self::Item>
//     {
//         let vec: &Vec<T> = unsafe{ mem::transmute(&self.storage.vec) };
//         self.iter
//             .map(move |group| &vec[group.first_index..group.first_index + group.len])
//             .drive(consumer)
//     }

//     fn with_producer<CB>(self, callback: CB) -> CB::Output
//         where CB: ProducerCallback<Self::Item>
//     {
//         let vec: &Vec<T> = unsafe{ mem::transmute(&self.storage.vec) };
//         self.iter
//             .map(move |group| &vec[group.first_index..group.first_index + group.len])
//             .with_producer(callback)
//     }
// }

// #[cfg(feature = "parallel_iter")]
// impl<'a, T: 'a + Sync> IntoParIter for RwLockWriteGuard<'a, DenseOneToNVec<T>>{
//     type Iter = ParOneToNDenseIter<'a, T>;
//     fn into_pariter(self) -> ParOneToNDenseIter<'a, T>{
//         ParOneToNDenseIter{
//             iter: unsafe{ mem::transmute(self.index.par_values()) },
//             storage: self,
//         }
//     }
// }