use std::num::NonZeroUsize;
use std::ops::{Index, IndexMut};
use std::ops::{Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive};
use std::{slice, vec};

/// A `Vec<T>` wrapper with one-based indices allowing for memory layout optimization, e.g.
/// `Option<NonZeroUsize>` is the same size as `usize` (8 or 4 bytes on most platforms)
///
/// For detailed methods documentation, see [`Vec`](std::vec::Vec).
#[derive(Clone, Default, Debug, Eq, Hash, PartialEq)]
pub struct OneVec<T>(Vec<T>);

impl<T> OneVec<T> {
    /// Constructs a new, empty `OneVec<T>`.
    /// Does not allocate memory.
    pub fn new() -> OneVec<T> {
        OneVec(Vec::new())
    }

    /// Constructs a new, empty OneVec<T> with the specified capacity.
    pub fn with_capacity(capacity: usize) -> OneVec<T> {
        OneVec(Vec::with_capacity(capacity))
    }

    /// Creates a `OneVec<T>` from `Vec<T>`. This operation is a no-op.
    pub fn from_vec(vec: Vec<T>) -> OneVec<T> {
        OneVec(vec)
    }

    /// Returns the number of elements the vector can hold without reallocating.
    pub fn capacity(&self) -> usize {
        self.0.capacity()
    }

    /// Reserves capacity for at least additional more elements
    /// to be inserted in the given `OneVec<T>`.
    pub fn reserve(&mut self, additional: usize) {
        self.0.reserve(additional)
    }

    /// Reserves the minimum capacity for exactly additional more elements
    /// to be inserted in the given `OneVec<T>`.
    pub fn reserve_exact(&mut self, additional: usize) {
        self.0.reserve_exact(additional)
    }

    /// Shrinks the capacity of the vector as much as possible.
    pub fn shrink_to_fit(&mut self) {
        self.0.shrink_to_fit()
    }

    /// Shortens the vector, keeping the first len elements and dropping the rest.
    pub fn truncate(&mut self, len: usize) {
        self.0.truncate(len)
    }

    /// Extracts a slice containing the entire vector.
    pub fn as_slice(&self) -> &[T] {
        self.0.as_slice()
    }

    /// Extracts a mutable slice of the entire vector.
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self.0.as_mut_slice()
    }

    /// Consumes the `OneVec<T>`, returning the inner vector.
    pub fn into_vec(self) -> Vec<T> {
        self.0
    }

    /// Removes an element from the vector and returns it.
    pub fn swap_remove(&mut self, index: NonZeroUsize) -> T {
        self.0.swap_remove(index.get() - 1)
    }

    /// Inserts an element at position index within the vector,
    /// shifting all elements after it to the right.
    pub fn insert(&mut self, index: NonZeroUsize, element: T) {
        self.0.insert(index.get() - 1, element)
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    pub fn remove(&mut self, index: NonZeroUsize) -> T {
        self.0.remove(index.get() - 1)
    }

    /// Retains only the elements specified by the predicate.
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.0.retain(f)
    }

    /// Removes all but the first of consecutive elements in the vector
    /// that resolve to the same key.
    pub fn dedup_by_key<F, K>(&mut self, key: F)
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq,
    {
        self.0.dedup_by_key(key)
    }

    /// Removes all but the first of consecutive elements in the vector
    /// satisfying a given equality relation.
    pub fn dedup_by<F>(&mut self, same_bucket: F)
    where
        F: FnMut(&mut T, &mut T) -> bool,
    {
        self.0.dedup_by(same_bucket)
    }

    /// Appends an element to the back of a collection.
    pub fn push(&mut self, value: T) {
        self.0.push(value)
    }

    /// Removes the last element from a vector and returns it, or None if it is empty.
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop()
    }

    /// Moves all the elements of other into Self, leaving other empty.
    pub fn append(&mut self, other: &mut OneVec<T>) {
        self.0.append(&mut other.0)
    }

    /// Clears the vector, removing all values.
    pub fn clear(&mut self) {
        self.0.clear()
    }

    /// Returns the number of elements in the vector, also referred to as its 'length'.
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// Returns true if the vector contains no elements.
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// Splits the collection into two at the given index.
    ///
    /// Returns a newly allocated Self. self contains elements [0, at),
    /// and the returned Self contains elements [at, len).
    pub fn split_off(&mut self, at: NonZeroUsize) -> OneVec<T> {
        OneVec(self.0.split_off(at.get() - 1))
    }

    /// Returns an iterator over the vector.
    pub fn iter(&self) -> slice::Iter<T> {
        self.as_slice().iter()
    }

    /// Returns an iterator that allows modifying each value.
    pub fn iter_mut(&mut self) -> slice::IterMut<T> {
        self.as_mut_slice().iter_mut()
    }
}

impl<T> IntoIterator for OneVec<T> {
    type Item = T;
    type IntoIter = vec::IntoIter<T>;

    fn into_iter(self) -> vec::IntoIter<T> {
        self.0.into_iter()
    }
}

impl<T> Index<RangeFull> for OneVec<T> {
    type Output = [T];

    fn index(&self, _index: RangeFull) -> &[T] {
        self.as_slice()
    }
}

impl<T> IndexMut<RangeFull> for OneVec<T> {
    fn index_mut(&mut self, _index: RangeFull) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T> Index<Range<NonZeroUsize>> for OneVec<T> {
    type Output = [T];

    fn index(&self, index: Range<NonZeroUsize>) -> &[T] {
        self.as_slice()
            .index((index.start.get() - 1)..(index.end.get() - 1))
    }
}

impl<T> IndexMut<Range<NonZeroUsize>> for OneVec<T> {
    fn index_mut(&mut self, index: Range<NonZeroUsize>) -> &mut [T] {
        self.as_mut_slice()
            .index_mut((index.start.get() - 1)..(index.end.get() - 1))
    }
}

impl<T> Index<RangeInclusive<NonZeroUsize>> for OneVec<T> {
    type Output = [T];

    fn index(&self, index: RangeInclusive<NonZeroUsize>) -> &[T] {
        self.as_slice()
            .index((index.start().get() - 1)..=(index.end().get() - 1))
    }
}

impl<T> IndexMut<RangeInclusive<NonZeroUsize>> for OneVec<T> {
    fn index_mut(&mut self, index: RangeInclusive<NonZeroUsize>) -> &mut [T] {
        self.as_mut_slice()
            .index_mut((index.start().get() - 1)..=(index.end().get() - 1))
    }
}

impl<T> Index<RangeTo<NonZeroUsize>> for OneVec<T> {
    type Output = [T];

    fn index(&self, index: RangeTo<NonZeroUsize>) -> &[T] {
        self.as_slice().index(..(index.end.get() - 1))
    }
}

impl<T> IndexMut<RangeTo<NonZeroUsize>> for OneVec<T> {
    fn index_mut(&mut self, index: RangeTo<NonZeroUsize>) -> &mut [T] {
        self.as_mut_slice().index_mut(..(index.end.get() - 1))
    }
}

impl<T> Index<RangeToInclusive<NonZeroUsize>> for OneVec<T> {
    type Output = [T];

    fn index(&self, index: RangeToInclusive<NonZeroUsize>) -> &[T] {
        self.as_slice().index(..=(index.end.get() - 1))
    }
}

impl<T> IndexMut<RangeToInclusive<NonZeroUsize>> for OneVec<T> {
    fn index_mut(&mut self, index: RangeToInclusive<NonZeroUsize>) -> &mut [T] {
        self.as_mut_slice().index_mut(..=(index.end.get() - 1))
    }
}

impl<T> Index<RangeFrom<NonZeroUsize>> for OneVec<T> {
    type Output = [T];

    fn index(&self, index: RangeFrom<NonZeroUsize>) -> &[T] {
        self.as_slice().index((index.start.get() - 1)..)
    }
}

impl<T> IndexMut<RangeFrom<NonZeroUsize>> for OneVec<T> {
    fn index_mut(&mut self, index: RangeFrom<NonZeroUsize>) -> &mut [T] {
        self.as_mut_slice().index_mut((index.start.get() - 1)..)
    }
}

impl<T> Index<NonZeroUsize> for OneVec<T> {
    type Output = T;

    fn index(&self, index: NonZeroUsize) -> &T {
        &self.0[index.get() - 1]
    }
}

impl<T> IndexMut<NonZeroUsize> for OneVec<T> {
    fn index_mut(&mut self, index: NonZeroUsize) -> &mut T {
        &mut self.0[index.get() - 1]
    }
}