// Copyright 2020 The Exonum Team
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! An implementation of an array list of items.
//!
//! The given section contains methods related to `ListIndex` and the iterator
//! over the items of this list.

use std::marker::PhantomData;

use crate::{
    access::{Access, AccessError, FromAccess},
    indexes::iter::{Entries, IndexIterator, Values},
    views::{IndexAddress, IndexState, IndexType, RawAccess, RawAccessMut, View, ViewWithMetadata},
    BinaryValue,
};

/// A list of items where elements are added to the end of the list and are
/// removed starting from the end of the list.
///
/// Access to the elements is obtained using the indexes of the list items.
/// `ListIndex` implements an array list, storing the elements as values and
/// using `u64` as an index. `ListIndex` requires that elements implement the
/// [`BinaryValue`] trait.
///
/// [`BinaryValue`]: ../trait.BinaryValue.html
#[derive(Debug)]
pub struct ListIndex<T: RawAccess, V> {
    base: View<T>,
    state: IndexState<T, u64>,
    _v: PhantomData<V>,
}

impl<T, V> FromAccess<T> for ListIndex<T::Base, V>
where
    T: Access,
    V: BinaryValue,
{
    fn from_access(access: T, addr: IndexAddress) -> Result<Self, AccessError> {
        let view = access.get_or_create_view(addr, IndexType::List)?;
        Ok(Self::new(view))
    }
}

impl<T, V> ListIndex<T, V>
where
    T: RawAccess,
    V: BinaryValue,
{
    fn new(view: ViewWithMetadata<T>) -> Self {
        let (base, state) = view.into_parts();
        Self {
            base,
            state,
            _v: PhantomData,
        }
    }

    /// Returns an element at the indicated position or `None` if the indicated
    /// position is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    /// assert_eq!(None, index.get(0));
    ///
    /// index.push(42);
    /// assert_eq!(Some(42), index.get(0));
    /// ```
    pub fn get(&self, index: u64) -> Option<V> {
        self.base.get(&index)
    }

    /// Returns the last element of the list or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    /// assert_eq!(None, index.last());
    ///
    /// index.push(42);
    /// assert_eq!(Some(42), index.last());
    /// ```
    pub fn last(&self) -> Option<V> {
        match self.len() {
            0 => None,
            l => self.get(l - 1),
        }
    }

    /// Returns `true` if the list contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    /// assert!(index.is_empty());
    ///
    /// index.push(42);
    /// assert!(!index.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the number of elements in the list.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    /// assert_eq!(0, index.len());
    ///
    /// index.push(10);
    /// assert_eq!(1, index.len());
    ///
    /// index.push(100);
    /// assert_eq!(2, index.len());
    /// ```
    pub fn len(&self) -> u64 {
        self.state.get().unwrap_or_default()
    }

    /// Returns an iterator over the list values.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// index.extend([1, 2, 3, 4, 5].iter().cloned());
    ///
    /// for val in index.iter() {
    ///     println!("{}", val);
    /// }
    /// ```
    pub fn iter(&self) -> Values<'_, V> {
        self.index_iter(None).skip_keys()
    }

    /// Returns an iterator over the list values starting from the specified position.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// index.extend([1, 2, 3, 4, 5].iter().cloned());
    ///
    /// for val in index.iter_from(3) {
    ///     println!("{}", val);
    /// }
    /// ```
    pub fn iter_from(&self, from: u64) -> Values<'_, V> {
        self.index_iter(Some(&from)).skip_keys()
    }
}

impl<T, V> ListIndex<T, V>
where
    T: RawAccessMut,
    V: BinaryValue,
{
    /// Appends an element to the back of the list.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// index.push(1);
    /// assert!(!index.is_empty());
    /// ```
    pub fn push(&mut self, value: V) {
        let len = self.len();
        self.base.put(&len, value);
        self.set_len(len + 1)
    }

    /// Removes the last element from the list and returns it, or returns `None`
    /// if the list is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// assert_eq!(None, index.pop());
    /// index.push(1);
    /// assert_eq!(Some(1), index.pop());
    /// ```
    pub fn pop(&mut self) -> Option<V> {
        match self.len() {
            0 => None,
            l => {
                let v = self.base.get(&(l - 1));
                self.base.remove(&(l - 1));
                self.set_len(l - 1);
                v
            }
        }
    }

    /// Extends the list with the contents of an iterator.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    /// assert!(index.is_empty());
    ///
    /// index.extend([1, 2, 3].iter().cloned());
    /// assert_eq!(3, index.len());
    /// ```
    pub fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = V>,
    {
        let mut len = self.len();
        for value in iter {
            self.base.put(&len, value);
            len += 1;
        }
        self.set_len(len);
    }

    /// Shortens the list, keeping the indicated number of first `len` elements
    /// and dropping the rest.
    ///
    /// If `len` is greater than the current state of the list, this has no effect.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// index.extend([1, 2, 3, 4, 5].iter().cloned());
    /// assert_eq!(5, index.len());
    /// index.truncate(3);
    /// assert_eq!(3, index.len());
    /// ```
    pub fn truncate(&mut self, len: u64) {
        // TODO: Optimize this. (ECR-175)
        while self.len() > len {
            self.pop();
        }
    }

    /// Changes a value at the specified position.
    ///
    /// # Panics
    ///
    /// Panics if the indicated position (`index`) is equal to or greater than
    /// the current state of the list.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// index.push(1);
    /// assert_eq!(Some(1), index.get(0));
    ///
    /// index.set(0, 10);
    /// assert_eq!(Some(10), index.get(0));
    /// ```
    pub fn set(&mut self, index: u64, value: V) {
        if index >= self.len() {
            panic!(
                "index out of bounds: \
                 the len is {} but the index is {}",
                self.len(),
                index
            );
        }
        self.base.put(&index, value)
    }

    /// Clears the list, removing all values.
    ///
    /// # Notes
    ///
    /// Currently, this method is not optimized to delete a large set of data. During the execution of
    /// this method, the amount of allocated memory is linearly dependent on the number of elements
    /// in the index.
    ///
    /// # Examples
    ///
    /// ```
    /// use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ListIndex};
    ///
    /// let db = TemporaryDB::new();
    /// let fork = db.fork();
    /// let mut index = fork.get_list("name");
    ///
    /// index.push(1);
    /// assert!(!index.is_empty());
    ///
    /// index.clear();
    /// assert!(index.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.base.clear();
        self.state.unset();
    }

    fn set_len(&mut self, len: u64) {
        self.state.set(len)
    }
}

impl<'a, T, V> IntoIterator for &'a ListIndex<T, V>
where
    T: RawAccess,
    V: BinaryValue,
{
    type Item = V;
    type IntoIter = Values<'a, V>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<T, V> IndexIterator for ListIndex<T, V>
where
    T: RawAccess,
    V: BinaryValue,
{
    type Key = u64;
    type Value = V;

    fn index_iter(&self, from: Option<&u64>) -> Entries<'_, u64, V> {
        Entries::new(&self.base, from)
    }
}

#[cfg(test)]
mod tests {
    use super::{ListIndex, RawAccessMut};
    use crate::{
        access::{AccessExt, CopyAccessExt},
        Database, Fork, TemporaryDB,
    };

    fn list_index_methods(list_index: &mut ListIndex<&Fork, i32>) {
        assert!(list_index.is_empty());
        assert_eq!(0, list_index.len());
        assert!(list_index.last().is_none());
        assert_eq!(None, list_index.pop());

        let extended_by = vec![45, 3422, 234];
        list_index.extend(extended_by);
        assert!(!list_index.is_empty());
        assert_eq!(Some(45), list_index.get(0));
        assert_eq!(Some(3422), list_index.get(1));
        assert_eq!(Some(234), list_index.get(2));
        assert_eq!(3, list_index.len());

        list_index.set(2, 777);
        assert_eq!(Some(777), list_index.get(2));
        assert_eq!(Some(777), list_index.last());
        assert_eq!(3, list_index.len());

        let mut extended_by_again = vec![666, 999];
        for el in &extended_by_again {
            list_index.push(*el);
        }
        assert_eq!(Some(666), list_index.get(3));
        assert_eq!(Some(999), list_index.get(4));
        assert_eq!(5, list_index.len());
        extended_by_again[1] = 1001;
        list_index.extend(extended_by_again);
        assert_eq!(7, list_index.len());
        assert_eq!(Some(1001), list_index.last());

        assert_eq!(Some(1001), list_index.pop());
        assert_eq!(6, list_index.len());

        list_index.truncate(3);

        assert_eq!(3, list_index.len());
        assert_eq!(Some(777), list_index.last());

        list_index.clear();
        assert_eq!(0, list_index.len());
    }

    fn list_index_iter(list_index: &mut ListIndex<&Fork, u8>) {
        list_index.extend(vec![1_u8, 2, 3]);

        assert_eq!(list_index.iter().collect::<Vec<_>>(), vec![1, 2, 3]);
        assert_eq!(list_index.iter_from(0).collect::<Vec<_>>(), vec![1, 2, 3]);
        assert_eq!(list_index.iter_from(1).collect::<Vec<_>>(), vec![2, 3]);
        assert_eq!(list_index.iter_from(3).count(), 0);
    }

    fn list_index_clear_in_family(db: &dyn Database, x: u32, y: u32, merge_before_clear: bool) {
        #[allow(clippy::needless_pass_by_value)]
        // ^-- better for type inference: we want `T == &Fork`, not `T == Fork`.
        fn list<T>(index: u32, view: T) -> ListIndex<T, String>
        where
            T: RawAccessMut,
        {
            view.get_list(("family", &index))
        }

        assert_ne!(x, y);
        let mut fork = db.fork();

        // Write data to both indexes.
        {
            let mut index = list(x, &fork);
            index.push("foo".to_owned());
            index.push("bar".to_owned());
        }
        {
            let mut index = list(y, &fork);
            index.push("baz".to_owned());
            index.push("qux".to_owned());
        }

        if merge_before_clear {
            db.merge_sync(fork.into_patch()).expect("merge");
            fork = db.fork();
        }

        // Clear the index with the lower family key.
        {
            let mut index = list(x, &fork);
            index.clear();
        }

        // The other index should be unaffected.
        {
            let index = list(x, &fork);
            assert!(index.is_empty());
            let index = list(y, &fork);
            assert_eq!(
                index.iter().collect::<Vec<_>>(),
                vec!["baz".to_owned(), "qux".to_owned()]
            );
        }

        // ...even after fork merge.
        db.merge_sync(fork.into_patch()).expect("merge");
        let snapshot = db.snapshot();
        let index: ListIndex<_, String> = snapshot.get_list(("family", &x));
        assert!(index.is_empty());
        let index: ListIndex<_, String> = snapshot.get_list(("family", &y));
        assert_eq!(
            index.iter().collect::<Vec<_>>(),
            vec!["baz".to_owned(), "qux".to_owned()]
        );
    }

    // Parameters for the `list_index_clear_in_family` test.
    const FAMILY_CLEAR_PARAMS: &[(u32, u32, bool)] =
        &[(0, 5, false), (5, 0, false), (1, 7, true), (7, 1, true)];

    const IDX_NAME: &str = "idx_name";

    #[test]
    fn test_list_index_methods() {
        let db = TemporaryDB::new();
        let fork = db.fork();
        let mut list_index = fork.get_list(IDX_NAME);
        list_index_methods(&mut list_index);
    }

    #[test]
    fn test_list_index_in_family_methods() {
        let db = TemporaryDB::new();
        let fork = db.fork();
        let mut list_index = fork.get_list((IDX_NAME, &vec![1]));
        list_index_methods(&mut list_index);
    }

    #[test]
    fn test_list_index_iter() {
        let db = TemporaryDB::new();
        let fork = db.fork();
        let mut list_index = fork.get_list(IDX_NAME);
        list_index_iter(&mut list_index);
    }

    #[test]
    fn test_list_index_in_family_iter() {
        let db = TemporaryDB::new();
        let fork = db.fork();
        let mut list_index = fork.get_list((IDX_NAME, &vec![1]));
        list_index_iter(&mut list_index);
    }

    #[test]
    fn test_list_index_clear_in_family() {
        for &(x, y, merge_before_clear) in FAMILY_CLEAR_PARAMS {
            let db = TemporaryDB::new();
            list_index_clear_in_family(&db, x, y, merge_before_clear);
        }
    }

    #[test]
    fn restore_after_no_op_initialization() {
        let db = TemporaryDB::new();
        let fork = db.fork();
        fork.get_list::<_, u32>(IDX_NAME);
        let list: ListIndex<_, u32> = fork.readonly().get_list(IDX_NAME);
        assert!(list.is_empty());
    }

    #[test]
    fn after_clearing_and_flushing() {
        let db = TemporaryDB::new();
        let fork = db.fork();
        {
            let mut list = fork.get_list::<_, u32>(IDX_NAME);
            list.extend(vec![1, 2]);
        }
        db.merge(fork.into_patch()).unwrap();

        let mut fork = db.fork();
        {
            let mut list = fork.get_list::<_, u32>(IDX_NAME);
            list.clear();
            list.push(3);
        }
        fork.flush();

        let list = fork.get_list::<_, u32>(IDX_NAME);
        assert_eq!(list.len(), 1);
        assert_eq!(list.get(0), Some(3));
        assert_eq!(list.get(1), None);
        assert_eq!(list.iter().collect::<Vec<_>>(), vec![3]);
    }
}
