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

use serde::{Deserialize, Serialize};
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.
#[derive(Debug, Deserialize, Serialize)]
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() }
    }

    /// Create a stable vec from a sorted (by id, T.0) vector. Don't use if you're
    /// not absolutely sure the data is valid.
    pub fn from_raw_unchecked(data: Vec<(usize, T)>) -> Self {
        Self { data }
    }

    /// 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
        }
    }

    /// Remove all data from this vec, leaving it like a StableVec created with `new` datawise.
    pub fn clear(&mut self) {
        self.data.clear()
    }

    /// Find the next free space in the vec. If there is space at the end, this will be preferred,
    /// otherwise low ids are. After checking this, `try_insert` will not fail and the returned
    /// id can be used to insert an item at that position.
    pub fn next_free(&self) -> usize {
        // Check if the item can be pushed at the end.
        if self.data.is_empty() {
            0
        } else if self.data.last().unwrap().0 < usize::MAX {
            self.data.last().unwrap().0
        } else {
            // Try to find a position in the vector that is still free, starting at the bottom.
            let mut prev_id = self.data.first().unwrap().0;
            for (_, (id, _)) in self.data.iter().enumerate().skip(1) {
                if *id > prev_id + 1 {
                    return *id - 1;
                }

                prev_id = *id;
            }

            panic!("There is no free space in the vector. This should never happen.");
        }
    }

    /// Attempts to insert the item at the given position. If there is no free space, an Err value
    /// will be returned.
    pub fn try_insert(&mut self, id: usize, item: T) -> Result<(), ()> {
        match self.find_pos(id) {
            // The item already exists, this is an error.
            Ok(_) => Err(()),
            Err(pos) => {
                self.data.insert(pos, (id, item));
                Ok(())
            }
        }
    }

    /// Tries to push the item into the vector, but if it doesn't work, it searches for an opening in
    /// the vector where no item currently is and places it there, favouring low ids (low ids contain
    /// potentially older changes).
    pub fn insert_anywhere(&mut self, item: T) -> usize {
        // Check if the item can be pushed at the end and do so if possible.
        if self.data.is_empty() || self.data.last().unwrap().0 < usize::MAX {
            self.push(item)
        } else {
            // Try to find a position in the vector that is still free, starting at the bottom.
            let mut prev_id = self.data.first().unwrap().0;
            for (place, (id, _)) in self.data.iter().enumerate().skip(1) {
                if *id > prev_id + 1 {
                    let id = *id - 1;
                    self.data.insert(place, (id, item));
                    return id;
                }

                prev_id = *id;
            }

            panic!("Unable to insert element. No space left in the vector.");
        }
    }

    // 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<T> Into<Vec<(usize, T)>> for StableVec<T> {
    fn into(self) -> Vec<(usize, T)> {
        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))
    }
}