// Copyright 2019-2020 Ian Jackson
// SPDX-License-Identifier: AGPL-3.0-or-later
// There is NO WARRANTY.

//! deque (double-ended queue) with stable element indices
//! ------------------------------------------------------
//!
//! ```
//! # use vecdeque_stableix::Deque;
//! let mut deque = Deque::new();
//! let pushed_a : i64 = deque.push_back('a');
//! let pushed_b = deque.push_back('b');
//! assert_eq!(deque.get(pushed_a), Some(&'a'));
//! assert_eq!(deque.pop_front(), Some('a'));
//! assert_eq!(deque[pushed_b], 'b'); // would panic if it had been removed
//! ```
//!
//! Index type
//! ----------
//!
//! You can use a suitable signed integer type, eg. `i64`, as the
//! element index.  It is important that it doesn't overflow ---
//! see below.
//!
//! You may have to specify the index type explicitly:
//! ```
//! # use vecdeque_stableix::Deque;
//! let mut deque : Deque<_,i64> = Deque::new();
//! deque.push_front(42);
//! assert_eq!(deque.front(), Some(&42));
//! ```
//!
//! Index stabiliy
//! --------------
//! This `Deque` is implemented by adding a front counter to
//! `std::vec_deque::VecDeque`.  The abstraction is rather thin.
//! Methods are provided to access the individual parts.  If you
//! use them, you may invalidate your existing indices, so that
//! they no longer point to the same elements.
//!
//! If this happens, your program will still be memory-safe,
//! but it may function incorrectly.
//!
//! Methods with this xxx
//!
//! Panics, and index overflow
//! --------------------------
//! This library will panic if the index type overflows.
//! This can occur if you push more than 2^n values
//! through the queue, where n is the size of your integer type.
//!
//! If you prefer to wrap, reusing element indices rather than
//! panicing, you can `impl Offset` for a newtype containing
//! an unsigned type, and performs wrapping arithmetic.
//!
//! It would be possible to provide non-panicing library entrypoints,
//! which return errors instead.  Patches for that welcome.

use std::collections::VecDeque;
use std::convert::{TryInto,TryFrom};
use std::ops::{Neg,Index,IndexMut};
use std::fmt::Debug;
use num_traits::{Zero,One,CheckedAdd,CheckedSub};

/// Double-ended queue with stable indices
#[derive(Clone,Debug,Hash)]
pub struct Deque<T,I:Offset> {
  advanced : I, // how many more pop_front than push_front
  v : VecDeque<T>,
}

/// Types that can be used as an index for a Deque.
///
/// The (fallible) operations required are a very limited subset of
/// arithmetic, combined with conversion between `Offset` and `usize`.
///
/// The provided generic implementation covers `isize`, `i64`, etc.
pub trait Offset : Clone + Debug + Neg + PartialEq + Eq {
  /// Should return `None` on overflow.
  /// Currently, this will cause the library to panic,
  /// but that may not always be the case.
  fn try_increment(&mut self) -> Option<()>;
  /// Should return `None` on overflow.
  /// Currently, this will cause the library to panic,
  /// but that may not always be the case.
  fn try_decrement(&mut self) -> Option<()>;
  fn zero() -> Self;

  /// Should return `Some(input - self)`, or `None` on overflow.
  ///
  /// Overflows can easily happen with a very old index, if the index
  /// type is bigger than `usize`; this is handled gracefully by the
  /// library.
  /// So `index_input` **must not panic** on overflow.
  fn index_input(&self, input: Self) -> Option<usize>;

  /// Should return `Some(output + self)`.
  ///
  /// Should return `None` on overflow;
  /// Currently, this will cause the library to panic,
  /// but that may not always be the case.
  fn index_output(&self, inner: usize) -> Option<Self>;
}

impl<T> Offset for T where T
  : Clone + Debug + Neg + PartialEq + Eq
  + Zero
  + One
  + CheckedAdd
  + CheckedSub
  + TryInto<usize>
  + TryFrom<usize>
{
  fn try_increment(&mut self) -> Option<()> {
    *self = self.checked_add(&One::one())?;
    Some(())
  }
  fn try_decrement(&mut self) -> Option<()>  {
    *self = self.checked_sub(&One::one())?;
    Some(())
  }
  fn index_input(&self, input: Self) -> Option<usize> {
    input.checked_sub(&self)?.try_into().ok()
  }
  fn index_output(&self, output: usize) -> Option<Self> {
    self.checked_add(&output.try_into().ok()?)
  }
  fn zero() -> Self { Zero::zero() }
}

impl<T, I:Offset> Index<I> for Deque<T,I> {
  type Output = T;
  fn index(&self, i : I) -> &T { self.get(i).unwrap() }
}
impl<T, I:Offset> IndexMut<I> for Deque<T,I> {
  fn index_mut(&mut self, i : I) -> &mut T { self.get_mut(i).unwrap() }
}

impl<T, I:Offset> Default for Deque<T,I> {
  fn default() -> Self { Self::new() }
}

/// Iterator over elements of a `Deque`
pub struct Iter<'v, T, I:Offset> {
  i : I,
  j : I,
  v : &'v Deque<T,I>,
}
impl<'v, T, I:Offset> Iterator for Iter<'v,T,I> {
  type Item = (I,&'v T);
  fn next(&mut self) -> Option<Self::Item> {
    if self.i == self.j { return None }
    let i = self.i.clone();
    let r = (i.clone(), self.v.get(i)?);
    self.i.try_increment().unwrap();
    Some(r)
  }
}
impl<'v, T, I:Offset> DoubleEndedIterator for Iter<'v,T,I> {
  fn next_back(&mut self) -> Option<Self::Item> {
    if self.i == self.j { return None }
    self.j.try_decrement().unwrap();
    let j = self.j.clone();
    let r = (j.clone(), self.v.get(j)?);
    Some(r)
  }
}

impl<'v, T, I:Offset> IntoIterator
  for &'v Deque<T,I> {
  type Item = (I, &'v T);
  type IntoIter = Iter<'v,T,I>;
  fn into_iter(self) -> Iter<'v,T,I> {
    Iter {
      i : self.front_index(),
      j : self.end_index(),
      v : self,
    }
  }
}

impl<T, I:Offset> Deque<T,I> {
  pub fn new() -> Self { Deque {
    advanced : Offset::zero(),
    v : VecDeque::new(),
  } }
  /// Like `VecDeque::with_capacity`
  pub fn with_capacity(cap : usize) -> Self {
    Deque {
      advanced : Offset::zero(),
      v : VecDeque::with_capacity(cap),
    }
  }

  pub fn len(&self) -> usize { self.v.len() }
  pub fn is_empty(&self) -> bool { self.v.is_empty() }

  pub fn front    (&    self) -> Option<&    T> { self.v.front    () }
  pub fn back     (&    self) -> Option<&    T> { self.v.back     () }
  pub fn front_mut(&mut self) -> Option<&mut T> { self.v.front_mut() }
  pub fn back_mut (&mut self) -> Option<&mut T> { self.v.back_mut () }

  /// Returns the element with index `i`, if it is still in the deque.
  pub fn get(&self, i : I) -> Option<&T> {
    self.v.get( self.advanced.index_input(i)? )
  }
  pub fn get_mut(&mut self, i : I) -> Option<&mut T> {
    self.v.get_mut( self.advanced.index_input(i)? )
  }

  /// **Panics** on index overflow.
  pub fn push_front(&mut self, e : T) -> I {
    let p = 0;
    self.v.push_front(e);
    self.advanced.try_decrement().unwrap();
    self.advanced.index_output(p).unwrap()
  }
  /// **Panics** on index overflow.
  pub fn push_back(&mut self, e : T) -> I {
    let p = self.v.len();
    self.v.push_back(e);
    self.advanced.index_output(p).unwrap()
  }

  /// **Panics** on index overflow.
  pub fn pop_front(&mut self) -> Option<T> {
    let r = self.v.pop_front()?;
    self.advanced.try_increment().unwrap();
    Some(r)
  }
  /// **Panics** on index overflow.
  // Actually, it can't panic, but that's not part of the API.
  pub fn pop_back(&mut self) -> Option<T> {
    let r = self.v.pop_back()?;
    Some(r)
  }

  /// Removes the element with index `i`, by replacing it with the
  /// eleement from the front.  Invalidates the index of the front
  /// element element (now `i` refers to that) but leaves other
  /// indices valid.  **Panics** on index overflow.
  pub fn swap_remove_front(&mut self, i: I) -> Option<T> {
    let r = self.v.swap_remove_front( self.advanced.index_input(i)? )?;
    self.advanced.try_increment().unwrap();
    Some(r)
  }
  /// Removes the element with index `i`, by replacing it with the
  /// eleement from the back.  Invalidates the index of the back
  /// element (now `i` refers to that), but leaves other indices
  /// valid.  **Panics** on index overflow.
  pub fn swap_remove_back(&mut self, i: I) -> Option<T> {
    let r = self.v.swap_remove_back( self.advanced.index_input(i)? )?;
    Some(r)
  }

  /// The index of the first item the deque.  If the queue is
  /// empty, this is the same as `end_index`.
  pub fn front_index(&self) -> I {
    self.advanced.index_output(0).unwrap()
  }
  /// The index just after the end of the qeue.  I.e., the index that
  /// would be assigned to a new element added with `push_back`.
  /// **Panics** on index overflow.
  pub fn end_index(&self) -> I {
    self.advanced.index_output(self.len()).unwrap()
  }

  /// `I` is how many more times `pop_front` has been called than
  /// `push_back`.
  pub fn counter(&self) -> &I { &self.advanced }
  /// Modifying this invalidates all indices.
  pub fn counter_mut(&mut self) -> &mut I { &mut self.advanced }

  /// Allos access to the `VecDeque` inside this `Deque`
  pub fn inner(&self) -> &VecDeque<T> { &self.v }
  /// Mutable access to the `VecDeque` inside this `Dequeu`.
  /// Adding/removing elements at the front of of the `VecDeque`
  /// invalidates all indices.
  pub fn inner_mut(&mut self) -> &mut VecDeque<T> { &mut self.v }
  pub fn into_parts(self) -> (I, VecDeque<T>) {
    (self.advanced, self.v)
  }
  pub fn from_parts(advanced: I, v: VecDeque<T>) -> Self {
    Self { advanced, v }
  }
  pub fn as_parts(&self) -> (&I, &VecDeque<T>) {
    (&self.advanced, &self.v)
  }
  /// Modifying the parts inconsistently will invalidate indices.
  pub fn as_mut_parts(&mut self) -> (&mut I, &mut VecDeque<T>) {
    (&mut self.advanced, &mut self.v)
  }
}

#[cfg(test)]
impl<I:Offset> Deque<char,I> {
  fn chk(&self) -> String {
    let s : String = self.inner().iter().collect();
    format!("{:?} {} {}", self.front_index(), self.len(), &s)
  }
}

#[test]
fn with_i8() {
  let mut siv : Deque<char,i8> = Default::default();

  assert_eq!(None, siv.pop_front());
  assert_eq!(None, siv.pop_back());

  for (i, c) in ('a'..='g').enumerate() {
    let j = siv.push_back(c);
    assert_eq!(i, j as usize);
  }
  assert_eq!('d', siv[ 3]);
  assert_eq!(-1, siv.push_front('Z'));
  assert_eq!( 7, siv.push_back('H'));
  assert_eq!("-1 9 ZabcdefgH", siv.chk());
  assert_eq!('Z', siv[-1]);
  assert_eq!('d', siv[ 3]);

  assert_eq!(None, siv.swap_remove_front(-2));
  assert_eq!(None, siv.swap_remove_back(10));

  assert_eq!(Some('Z'), siv.pop_front());
  assert_eq!(Some('H'), siv.pop_back());
  assert_eq!("0 7 abcdefg", siv.chk());

  assert_eq!(Some('c'), siv.swap_remove_front(2));
  assert_eq!("1 6 badefg", siv.chk());

  assert_eq!(Some('d'), siv.swap_remove_back(3));
  assert_eq!("1 5 bagef", siv.chk());

  *siv.get_mut(4).unwrap() = 'E';
  assert_eq!("1 5 bagEf", siv.chk());

  assert_eq!(6, siv.end_index());

  let (a,v) = siv.into_parts();
  let mut siv = Deque::from_parts(a,v);
  assert_eq!("1 5 bagEf", siv.chk());

  siv.inner_mut()[0] = 'B';
  assert_eq!("1 5 BagEf", siv.chk());

  let mut l = vec![];
  for ent in &siv { l.push(ent); }
  assert_eq!("[(1, 'B'), (2, 'a'), (3, 'g'), (4, 'E'), (5, 'f')]",
             format!("{:?}", &l));

  let mut l = vec![];
  for ent in siv.into_iter().rev() { l.push(ent); }
  assert_eq!("[(5, 'f'), (4, 'E'), (3, 'g'), (2, 'a'), (1, 'B')]",
             format!("{:?}", &l));
}

#[test]
fn with_isize() {
  // Mostly this is to check it compiles with isize and something
  // with Drop etc.
  let mut siv = <Deque<String,isize>>::new();
  siv.push_back("s".to_owned());
}

#[test]
fn with_big() {
  #[cfg(target_pointer_width="16")]
  let a = 123 * 1_000_000_i32;

  #[cfg(target_pointer_width="32")]
  let a = 123 * 1_000_000_000_000_000_i64;

  #[cfg(target_pointer_width="64")]
  let a = 123 * 1_000_000_000_000_000_000_000_000_000_000_i128;

  // point of this test is to check that we do cope properly
  // with `advance` values that don't fit in usize
  assert_eq!(None, usize::try_from(a).ok());

  let v : VecDeque<char> = Default::default();
  let mut siv = Deque::from_parts(a,v);
  siv.push_back('a');
  siv.push_back('b');
  assert_eq!('a', *siv.front().unwrap());
  assert_eq!('b', *siv.back ().unwrap());
  *siv.front_mut().unwrap() = 'A';
  *siv.back_mut() .unwrap() = 'B';
  assert_eq!(format!("{} 2 AB", &a), siv.chk());
  assert_eq!(None, siv.get(0));
}