// This file is part of ICU4X. For terms of use, please see the file

// called LICENSE at the top level of the ICU4X source tree

// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).

use alloc::vec;

use alloc::vec::Vec;

use core::fmt;

use core::iter::FromIterator;

use core::ops::Deref;

use super::FlexZeroSlice;

use super::FlexZeroVec;

/// The fully-owned variant of [`FlexZeroVec`]. Contains all mutation methods.

// Safety invariant: the inner bytes must deref to a valid `FlexZeroSlice`

#[derive(Clone, PartialEq, Eq)]

pub struct FlexZeroVecOwned(Vec<u8>);

impl FlexZeroVecOwned {

    /// Creates a new [`FlexZeroVecOwned`] with zero elements.

    pub fn new_empty() -> Self {

        Self(vec![1])

    }

    /// Creates a [`FlexZeroVecOwned`] from a [`FlexZeroSlice`].

    pub fn from_slice(other: &FlexZeroSlice) -> FlexZeroVecOwned {

        // safety: the bytes originate from a valid FlexZeroSlice

        Self(other.as_bytes().to_vec())

    }

    /// Obtains this [`FlexZeroVecOwned`] as a [`FlexZeroSlice`].

    pub fn as_slice(&self) -> &FlexZeroSlice {

        let slice: &[u8] = &self.0;

        unsafe {

            // safety: the slice is known to come from a valid parsed FlexZeroSlice

            FlexZeroSlice::from_byte_slice_unchecked(slice)

        }

    }

    /// Mutably obtains this `FlexZeroVecOwned` as a [`FlexZeroSlice`].

    pub(crate) fn as_mut_slice(&mut self) -> &mut FlexZeroSlice {

        let slice: &mut [u8] = &mut self.0;

        unsafe {

            // safety: the slice is known to come from a valid parsed FlexZeroSlice

            FlexZeroSlice::from_byte_slice_mut_unchecked(slice)

        }

    }

    /// Converts this `FlexZeroVecOwned` into a [`FlexZeroVec::Owned`].

    #[inline]

    pub fn into_flexzerovec(self) -> FlexZeroVec<'static> {

        FlexZeroVec::Owned(self)

    }

    /// Clears all values out of this `FlexZeroVecOwned`.

    #[inline]

    pub fn clear(&mut self) {

        *self = Self::new_empty()

    }

    /// Appends an item to the end of the vector.

    ///

    /// # Panics

    ///

    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.

    ///

    /// # Examples

    ///

    /// ```

    /// use zerovec::vecs::FlexZeroVec;

    ///

    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();

    /// zv.to_mut().push(33);

    /// assert_eq!(zv.to_vec(), vec![22, 44, 66, 33]);

    /// ```

    pub fn push(&mut self, item: usize) {

        let insert_info = self.get_insert_info(item);

        self.0.resize(insert_info.new_bytes_len, 0);

        let insert_index = insert_info.new_count - 1;

        self.as_mut_slice().insert_impl(insert_info, insert_index);

    }

    /// Inserts an element into the middle of the vector.

    ///

    /// Caution: Both arguments to this function are of type `usize`. Please be careful to pass

    /// the index first followed by the value second.

    ///

    /// # Panics

    ///

    /// Panics if `index > len`.

    ///

    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.

    ///

    /// # Examples

    ///

    /// ```

    /// use zerovec::vecs::FlexZeroVec;

    ///

    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();

    /// zv.to_mut().insert(2, 33);

    /// assert_eq!(zv.to_vec(), vec![22, 44, 33, 66]);

    /// ```

    pub fn insert(&mut self, index: usize, item: usize) {

        #[allow(clippy::panic)] // panic is documented in function contract

        if index > self.len() {

            panic!("index {} out of range {}", index, self.len());

        }

        let insert_info = self.get_insert_info(item);

        self.0.resize(insert_info.new_bytes_len, 0);

        self.as_mut_slice().insert_impl(insert_info, index);

    }

    /// Inserts an element into an ascending sorted vector

    /// at a position that keeps the vector sorted.

    ///

    /// # Panics

    ///

    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.

    ///

    /// # Examples

    ///

    /// ```

    /// use zerovec::vecs::FlexZeroVecOwned;

    ///

    /// let mut fzv = FlexZeroVecOwned::new_empty();

    /// fzv.insert_sorted(10);

    /// fzv.insert_sorted(5);

    /// fzv.insert_sorted(8);

    ///

    /// assert!(Iterator::eq(fzv.iter(), [5, 8, 10].iter().copied()));

    /// ```

    pub fn insert_sorted(&mut self, item: usize) {

        let index = match self.binary_search(item) {

            Ok(i) => i,

            Err(i) => i,

        };

        let insert_info = self.get_insert_info(item);

        self.0.resize(insert_info.new_bytes_len, 0);

        self.as_mut_slice().insert_impl(insert_info, index);

    }

    /// Removes and returns the element at the specified index.

    ///

    /// # Panics

    ///

    /// Panics if `index >= len`.

    ///

    /// # Examples

    ///

    /// ```

    /// use zerovec::vecs::FlexZeroVec;

    ///

    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();

    /// let removed_item = zv.to_mut().remove(1);

    /// assert_eq!(44, removed_item);

    /// assert_eq!(zv.to_vec(), vec![22, 66]);

    /// ```

    pub fn remove(&mut self, index: usize) -> usize {

        #[allow(clippy::panic)] // panic is documented in function contract

        if index >= self.len() {

            panic!("index {} out of range {}", index, self.len());

        }

        let remove_info = self.get_remove_info(index);

        // Safety: `remove_index` is a valid index

        let item = unsafe { self.get_unchecked(remove_info.remove_index) };

        let new_bytes_len = remove_info.new_bytes_len;

        self.as_mut_slice().remove_impl(remove_info);

        self.0.truncate(new_bytes_len);

        item

    }

    /// Removes and returns the last element from an ascending sorted vector.

    ///

    /// If the vector is not sorted, use [`FlexZeroVecOwned::remove()`] instead. Calling this

    /// function would leave the FlexZeroVec in a safe, well-defined state; however, information

    /// may be lost and/or the equality invariant might not hold.

    ///

    /// # Panics

    ///

    /// Panics if `self.is_empty()`.

    ///

    /// # Examples

    ///

    /// ```

    /// use zerovec::vecs::FlexZeroVec;

    ///

    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();

    /// let popped_item = zv.to_mut().pop_sorted();

    /// assert_eq!(66, popped_item);

    /// assert_eq!(zv.to_vec(), vec![22, 44]);

    /// ```

    ///

    /// Calling this function on a non-ascending vector could cause surprising results:

    ///

    /// ```

    /// use zerovec::vecs::FlexZeroVec;

    ///

    /// let mut zv1: FlexZeroVec = [444, 222, 111].iter().copied().collect();

    /// let popped_item = zv1.to_mut().pop_sorted();

    /// assert_eq!(111, popped_item);

    ///

    /// // Oops!

    /// assert_eq!(zv1.to_vec(), vec![188, 222]);

    /// ```

    pub fn pop_sorted(&mut self) -> usize {

        #[allow(clippy::panic)] // panic is documented in function contract

        if self.is_empty() {

            panic!("cannot pop from an empty vector");

        }

        let remove_info = self.get_sorted_pop_info();

        // Safety: `remove_index` is a valid index

        let item = unsafe { self.get_unchecked(remove_info.remove_index) };

        let new_bytes_len = remove_info.new_bytes_len;

        self.as_mut_slice().remove_impl(remove_info);

        self.0.truncate(new_bytes_len);

        item

    }

}

impl Deref for FlexZeroVecOwned {

    type Target = FlexZeroSlice;

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

        self.as_slice()

    }

}

impl fmt::Debug for FlexZeroVecOwned {

    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {

        write!(f, "{:?}", self.to_vec())

    }

}

impl From<&FlexZeroSlice> for FlexZeroVecOwned {

    fn from(other: &FlexZeroSlice) -> Self {

        Self::from_slice(other)

    }

}

impl FromIterator<usize> for FlexZeroVecOwned {

    /// Creates a [`FlexZeroVecOwned`] from an iterator of `usize`.

    fn from_iter<I>(iter: I) -> Self

    where

        I: IntoIterator<Item = usize>,

    {

        let mut result = FlexZeroVecOwned::new_empty();

        for item in iter {

            result.push(item);

        }

        result

    }

}

#[cfg(test)]

mod test {

    use super::*;

    fn check_contents(fzv: &FlexZeroSlice, expected: &[usize]) {

        assert_eq!(fzv.len(), expected.len(), "len: {fzv:?} != {expected:?}");

        assert_eq!(

            fzv.is_empty(),

            expected.is_empty(),

            "is_empty: {fzv:?} != {expected:?}"

        );

        assert_eq!(

            fzv.first(),

            expected.first().copied(),

            "first: {fzv:?} != {expected:?}"

        );

        assert_eq!(

            fzv.last(),

            expected.last().copied(),

            "last:  {fzv:?} != {expected:?}"

        );

        for i in 0..(expected.len() + 1) {

            assert_eq!(

                fzv.get(i),

                expected.get(i).copied(),

                "@{i}: {fzv:?} != {expected:?}"

            );

        }

    }

    #[test]

    fn test_basic() {

        let mut fzv = FlexZeroVecOwned::new_empty();

        assert_eq!(fzv.get_width(), 1);

        check_contents(&fzv, &[]);

        fzv.push(42);

        assert_eq!(fzv.get_width(), 1);

        check_contents(&fzv, &[42]);

        fzv.push(77);

        assert_eq!(fzv.get_width(), 1);

        check_contents(&fzv, &[42, 77]);

        // Scale up

        fzv.push(300);

        assert_eq!(fzv.get_width(), 2);

        check_contents(&fzv, &[42, 77, 300]);

        // Does not need to be sorted

        fzv.insert(1, 325);

        assert_eq!(fzv.get_width(), 2);

        check_contents(&fzv, &[42, 325, 77, 300]);

        fzv.remove(3);

        assert_eq!(fzv.get_width(), 2);

        check_contents(&fzv, &[42, 325, 77]);

        // Scale down

        fzv.remove(1);

        assert_eq!(fzv.get_width(), 1);

        check_contents(&fzv, &[42, 77]);

    }

    #[test]

    fn test_build_sorted() {

        let nums: &[usize] = &[0, 50, 0, 77, 831, 29, 89182, 931, 0, 77, 712381];

        let mut fzv = FlexZeroVecOwned::new_empty();

        for num in nums {

            fzv.insert_sorted(*num);

        }

        assert_eq!(fzv.get_width(), 3);

        check_contents(&fzv, &[0, 0, 0, 29, 50, 77, 77, 831, 931, 89182, 712381]);

        for num in nums {

            let index = fzv.binary_search(*num).unwrap();

            fzv.remove(index);

        }

        assert_eq!(fzv.get_width(), 1);

        check_contents(&fzv, &[]);

    }

}