//! Stable vec is a vector that guarantees its content access position does not change.

use std::ops::Deref;
use std::slice::IterMut;

/// Works like Vec, but with an additional field, where the position information is saved. Does not
/// support inserting elements in arbitrary positions, since that may shift the data. Removing data
/// in the middle is fine, however.
pub struct StableVec<T> {
    data: Vec<(usize, T)>,
}

/// Mutable iterator over a stable vector. Similar to enumerate, but since only the elements actually
/// in the vector are iterated there can be holes in the enumeration (i -> i+1 not guaranteed).
pub struct IdIterMut<'a, T> {
    internal: IterMut<'a, (usize, T)>,
}

impl<T> StableVec<T> {
    /// Create a new, empty StableVec
    pub fn new() -> Self {
        Self { data: Vec::new() }
    }

    /// Add an item to the end of the vector. Returns its stable id. (`len()-1 != last_element_id`)
    pub fn push(&mut self, item: T) -> usize {
        if self.data.is_empty() {
            self.data.push((0, item));
            0
        } else {
            let id = self.data.last().unwrap().0 + 1;
            self.data.push((id, item));
            id
        }
    }

    // Find the internal position of the given id in `O(log n)`
    fn find_pos(&self, id: usize) -> Result<usize, usize> {
        self.data.binary_search_by(|x| x.0.cmp(&id))
    }

    /// Get the item with the given id from the vec, if it exists. Unlike in a normal vec, this is
    /// not `O(1)` but `O(log n)`.
    pub fn get(&self, id: usize) -> Option<&T> {
        match self.find_pos(id) {
            Ok(pos) => Some(&self.data[pos].1),
            Err(_) => None,
        }
    }

    /// Get the item with the id mutably. Like `get()` this is also `O(log n)`
    pub fn get_mut(&mut self, id: usize) -> Option<&mut T> {
        match self.find_pos(id) {
            Ok(pos) => Some(&mut self.data[pos].1),
            Err(_) => None,
        }
    }

    /// Remove the item with the given id from the vector, returning it, if it existed.
    pub fn remove(&mut self, id: usize) -> Option<T> {
        match self.find_pos(id) {
            Ok(pos) => Some(self.data.remove(pos).1),
            Err(_) => None,
        }
    }

    /// Create an id enumerating iterator over the StableVec.
    pub fn id_iter_mut(&mut self) -> IdIterMut<'_, T> {
        IdIterMut::new(&mut self.data)
    }
}

impl<T> Default for StableVec<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> Deref for StableVec<T> {
    type Target = Vec<(usize, T)>;

    fn deref(&self) -> &Self::Target {
        &self.data
    }
}

impl<'a, T> IdIterMut<'a, T> {
    pub(super) fn new(id_vec: &'a mut [(usize, T)]) -> Self {
        Self {
            internal: id_vec.iter_mut(),
        }
    }
}

impl<'a, T> Iterator for IdIterMut<'a, T> {
    type Item = (usize, &'a mut T);

    fn next(&mut self) -> Option<Self::Item> {
        self.internal.next().map(|(id, item)| (*id, item))
    }
}

impl<'a, T> DoubleEndedIterator for IdIterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.internal.next_back().map(|(id, item)| (*id, item))
    }
}