#![allow(dead_code)]

use std::any;
use std::fmt;
use std::marker::PhantomData;

type Link<T> = Option<*mut Node<T>>;

struct Node<T> {
  elem: T,
  prev: Link<T>,
  next: Link<T>,
}

#[derive(Debug)]
struct Deque<T> {
  head: Link<T>,
  tail: Link<T>,
  len: usize,
}

struct Iter<'a, T> {
  head: Link<T>,
  tail: Link<T>,
  _phd: PhantomData<&'a T>
}

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = &'a T;
    
  fn next(&mut self) -> Option<Self::Item> {
    unsafe {
      if let Some(node) = self.head {
        self.head = (*node).next;
        Some(&(*node).elem)
      } else {
        None
      }
    }
  }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
  fn next_back(&mut self) -> Option<&'a T> {
    unsafe {
      if let Some(node) = self.tail {
        self.tail = (*node).prev;
        Some(&(*node).elem)
      } else {
        None
      }
    }
  }
}

impl<T: fmt::Display + fmt::Debug> fmt::Display for Deque<T> {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    let type_name = any::type_name::<Self>()
                      .split("::")
                      .collect::<Vec<_>>()
                      .last()
                      .unwrap()
                      .to_string();       
    
    let mut v = Vec::<String>::new();

    for i in self.iter() {
      v.push(format!("{}", i));
    }
    
    let res = format!("{} ({}) [{}] ({:?}..{:?})", type_name, self.len, v.join(", "), self.peek_front(), self.peek_back());   
    write!(f, "{}", res)
   }
}

impl<T> Drop for Deque<T> {
  fn drop(&mut self) {
    while self.pop_front().is_some() {}
  }
}

impl<T> Deque<T> {
  fn new() -> Self {
    Self {
      head: None,
      tail: None,
      len: 0,
    }
  }
  
  fn from_vec(vec: Vec<T>) -> Self {
    let mut list = Self::new();
    list.extend(vec);
    list
  }
  
  fn extend(&mut self, vec: Vec<T>) {
    for i in vec {
      self.push_back(i);
    }
  }
  
  fn push_front(&mut self, elem: T) {
    unsafe {
      let node = Box::into_raw(Box::new(Node {
        elem,
        prev: None,
        next: None,
      }));
        
      if let Some(head) = self.head {
        (*head).prev = Some(node);
        (*node).next = Some(head);
      } else {
        self.tail = Some(node);
      }
        
      self.head = Some(node);
      self.len += 1;
    }
  }
  
  fn push_back(&mut self, elem: T) {
    unsafe {
      let node = Box::into_raw(Box::new(Node {
        elem,
        prev: None,
        next: None,
      }));
      
      if let Some(tail) = self.tail {
        (*node).prev = Some(tail);
        (*tail).next = Some(node);
      } else {
        self.head = Some(node);
      }
      
      self.tail = Some(node);
      self.len += 1;
    }
  }
  
  fn pop_front(&mut self) -> Option<T> {
    unsafe { 
      if let Some(head) = self.head {
        let mut boxed = Box::from_raw(head);
        let elem = boxed.elem;
      
        self.head = boxed.next.take();
      
        if let Some(head) = self.head {
          (*head).prev = None;
        } else {
          self.tail = None;
        }
      
        self.len -= 1;
        Some(elem)
      } else {
        None
      }
    }
  }
  
  fn pop_back(&mut self) -> Option<T> {
    unsafe {
      self.tail.map(|tail| {
        let mut boxed = Box::from_raw(tail);
        let elem = boxed.elem;
        
        self.tail = boxed.prev.take();
        
        if let Some(tail) = self.tail {
          (*tail).next = None;
        } else {
          self.head = None;
        }
        
        self.len -= 1;
        elem
      })
    }
  }
  
  fn peek_front(&self) -> Option<&T> {
    self.head.as_ref().map(|node| unsafe {
      &(*(*node)).elem
    })
  }

  fn peek_back(&self) -> Option<&T> {
    self.tail.as_ref().map(|node| unsafe {
      &(*(*node)).elem
    })
  }
  
  fn iter(&self) -> Iter<'_, T> {
    Iter {
      head: self.head,
      tail: self.tail,
      _phd: PhantomData,
    }
  }

  // insert a node at specified index 
  fn insert_at(&mut self, index: usize, elem: T) {
    unsafe {
      if self.len == 0 || index == 0 {
        self.push_front(elem);
        return;
      }
    
      if index >= self.len {
        self.push_back(elem);
        return;
      }
      
      // at this point, self.len > 1
      
      let new = Box::into_raw(Box::new(Node {
        elem,
        prev: None,
        next: None,
      }));
  
      // create a ptr to current node
      let mut cur = self.head.unwrap();
      
      // point cur to node at index
      for _ in 1..index {
        cur = (*cur).next.unwrap();
      }
    
      // create a ptr to cur.next
      let next = (*cur).next.unwrap();
    
      // cur <-> new
      (*cur).next = Some(new);
      (*new).prev = Some(cur);
  
      // new <-> next
      (*new).next = Some(next);
      (*next).prev = Some(new);
    
      // increment self.len
      self.len += 1;
    }
  }
  
  // insert a list at specified index
  fn splice_at(&mut self, index: usize, mut list: Self) {
    unsafe {
      if list.len == 0 {
        return;
      }
    
      if self.len == 0 {
        self.head = list.head.take();
        self.tail = list.tail.take();
        self.len = list.len;
        return;
      }
        
      if index == 0 {
        // list.tail <-> self.head
        (*(list.tail.unwrap())).next = self.head.take();
        (*(self.head.unwrap())).prev = list.tail.take();
        
        // self.head -> list.head
        self.head = list.head.take();
        
        // update self.len
        self.len += list.len;
        
        return;
      }
      
      if index >= self.len {
        // self.tail <-> list.head
        (*(list.head.unwrap())).prev = self.tail.take();
        (*(self.tail.unwrap())).next = list.head.take();
        
        // self.tail -> list.tail
        self.tail = list.tail.take();
        
        // update self.len
        self.len += list.len;
      
        return;  
      }
      
      // at this point, self.len > 1
      
      // create a ptr to current node
      let mut cur = self.head.unwrap();
      
      // point cur to node at index 
      for _ in 1..index {
        cur = (*cur).next.unwrap();
      }
      
      // create a ptr to cur.next
      let next = (*cur).next.unwrap();
      
      // cur <-> list.head
      (*(list.head.unwrap())).prev = Some(cur);
      (*cur).next = list.head.take();
      
      // list.tail <-> next
      (*(list.tail.unwrap())).next = Some(next);
      (*next).prev = list.tail.take();
      
      // update self.len
      self.len += list.len;
    }
  }
  
  fn concat(&mut self, list: Self) {
    self.splice_at(list.len, list);
  }
  
  fn cursor_mut(&mut self) -> CursorMut<'_, T> {
    CursorMut {
      list: self,
      cur: None,
      index: None,
    }
  }
}

struct CursorMut<'a, T> {
  list: &'a mut Deque<T>,
  cur: Link<T>,
  index: Option<usize>,
}

impl<T> CursorMut<'_, T> {
  fn current(&self) -> Option<&mut T> {
    self.cur.map(|node| unsafe {
      &mut (*node).elem
    })
  }
  
  fn index(&self) -> Option<usize> {
    self.index
  }
  
  fn move_next(&mut self) {
    unsafe {
      if self.list.len == 0 {
        return;
      }
      
      if self.cur.is_none() {
        self.cur = self.list.head;
        self.index = Some(0);
        return;
      }
      
      self.cur = (*self.cur.unwrap()).next;
        
      if self.cur.is_some() {
        self.index = Some(self.index.unwrap() + 1);
      } else {
        self.index = None;  
      }
    }
  }
  
  fn move_prev(&mut self) {
    unsafe {
      if self.list.len == 0 {
        return;
      }
      
      if self.cur.is_none() {
        self.cur = self.list.tail;
        self.index = Some(self.list.len - 1);
        return;
      };
      
      self.cur = (*self.cur.unwrap()).prev;
        
      if self.cur.is_some() {
        self.index = Some(self.index.unwrap() - 1);
      } else {
        self.index = None;  
      }
    }
  }
  
  fn split_before(&mut self) ->Deque<T> {
    unsafe {
      let mut new_list = Deque::<T>::new();
    
      if self.list.len < 2 {
        return new_list;
      }
       
      if self.cur.is_none() {
        return new_list;
      }
    
      if self.index == Some(0) {
        return new_list;
      }
    
      // res.head -> self.list.head
      new_list.head = self.list.head.take();
    
      // res.tail <-> cur.prev
      new_list.tail = (*self.cur.unwrap()).prev.take();
      (*new_list.tail.unwrap()).next = None;
    
      // set res.len
      new_list.len = self.index.unwrap();
      
      // self.list.head -> cur
      self.list.head = self.cur;
    
      // update self.list.len
      self.list.len -= self.index.unwrap();
      
      // update self.index
      self.index = Some(0);
    
      new_list
    }
  }
}

// driver code

fn main() {
  println!("An Unsafe Deque that uses\n  Option<*mut Node<T>>\n");
 
  let x = &[1, 2, 3];
  let y = x.to_vec();
   
  let mut l = Deque::from_vec(y);
  println!("{}\n", l);
  
  let mut cur = l.cursor_mut();
  
  for _ in 0..2 {
    cur.move_next();
  }
  println!(">>> cursor.current: {:?}\n", cur.current());
  
  let m = cur.split_before();
  println!("m = {}\n", m);
 
  for _ in 0..8 {
    cur.move_next();
    println!(">>> cursor.index  : {:?}\n", cur.index());
    println!(">>> cursor.current: {:?}\n", cur.current());
  }
  
  println!("l = {}\n", l);
    
  let vec: Vec<_> = l.iter().rev().map(|x| x * 10).collect();
  println!("vec: {:?}", vec);
    
  l.extend(vec![4, 5, 6]);
  println!("{}\n", l);
  
  let mut l = Deque::<i32>::new();
  println!("{}\n", l);
  
  l.extend(vec![1, 2, 3]);
  println!("{}\n", l);
   
  // new()
  let mut l = Deque::<i32>::new();
  println!(">>> Deque::<i32>::new()");
  println!("{}\n", l);
  
  assert_eq!(l.pop_front(), None);
  
  // iter()
  let mut iter = l.iter();
  for _ in 1..2 {
    println!(">>> iter.next()     : {:?}", iter.next());
    println!(">>> iter.next_back(): {:?}", iter.next_back());
  }
  println!("{}\n", l);
   
  // push_front() 
  for i in 1..5 {
    l.push_front(i);
    println!(">>> push_front({})", i);
    println!("{}\n", l);
  }
  
  // iter()
  let mut iter = l.iter();
  for _ in 1..6 {
    println!(">>> iter.next()     : {:?}", iter.next());
    println!(">>> iter.next_back(): {:?}", iter.next_back());
  }
  println!("{}\n", l);
  
  // pop_front()
  for _ in 1..6 {
    println!(">>> pop_front()\n{:?}", l.pop_front());
    println!("{}\n", l);
  }
  
  // push_back() 
  for i in (1..5).rev() {
    l.push_back(i);
    println!(">>> push_back({})", i);
    println!("{}\n", l);
  }
  
  // iter()
  let mut iter = l.iter();
  for _ in 1..6 {
    println!(">>> iter.next()     : {:?}", iter.next());
    println!(">>> iter.next_back(): {:?}", iter.next_back());
  }
  println!("{}\n", l);

    // pop_back()
  for _ in 1..6 {
    println!(">>> pop_back()\n{:?}", l.pop_back());
    println!("{}\n", l);
  }
  
  // insert_at()
  for i in 0..3 {
    println!(">>> insert_at({}, {})", i, i);
    l.insert_at(i, i as i32);
    println!("{}\n", l);
  }

  // insert_at()
  for i in (1..7).step_by(2) {
    println!(">>> insert_at({}, {})", i, i*10);
    l.insert_at(i, (i*10) as i32);
    println!("{}\n", l);
  }
    
  // new()
  let mut a = Deque::<i32>::new();
  println!(">>> Deque::<i32>::new()");
  println!("a = {}\n", a);

  // push_back() 
  for i in (0..5).step_by(4) {
    a.push_back(i);
    println!(">>> push_back({})", i);
    println!("a = {}\n", a);
  }
  
  // new()
  let mut b = Deque::<i32>::new();
  println!(">>> Deque::<i32>::new()");
  println!("b = {}\n", b);
  
  // push_back() 
  for i in 1..4 {
    b.push_back(i);
    println!(">>> push_back({})", i);
    println!("b = {}\n", b);
  }
  
  println!(">>> a.splice_at(1, b)");
  a.splice_at(1, b);
  println!("a = {}\n", a);
  
  
}