#ifndef unrolled_h_
#define unrolled_h_
#ifndef iostream_h_
#define iostream_h_
#include <iostream>
#endif

const int NUM_ELEMENTS_PER_NODE=6;

template <class T>
class Node {
public:
  Node() : next_(NULL), prev_(NULL), num_elements(0) {};
  Node(const T& v);

  // REPRESENTATION
  T value_[NUM_ELEMENTS_PER_NODE];
  Node<T>* next_;
  Node<T>* prev_;
  unsigned int num_elements;
};

template <class T>
Node<T>::Node(const T& v) {
 next_=NULL;
 prev_=NULL;
 num_elements=1;
 value_[0]=v;                
}

//Definition of list_iterator, so UnrolledLL can use it
template <class T> class list_iterator;


template <class T>
class UnrolledLL {

public:

  UnrolledLL() : head_(NULL), tail_(NULL), size_(0) {}
  UnrolledLL(const UnrolledLL<T>& old) { this->copy_list(old); }
  ~UnrolledLL() { this->destroy_list(); }
  UnrolledLL& operator= (const UnrolledLL<T>& old);
    
  //Some basic functions           
  unsigned int size() const { return size_; }
  bool empty() const { return head_ == NULL; }
  void clear() { this->destroy_list(); }
  
  //Front, back
  const T& front() const { return head_->value_[0];  }
  T& front() { return head_->value_[0]; }
  const T& back() const { return tail_->value_[tail_->num_elements]; }
  T& back() { return tail_->value_[tail_->num_elements]; }
   
  //Entering new data 
  void push_front(const T& v);
  void pop_front();
  void push_back(const T& v);
  void pop_back();
  
  
  //Iterator functions
  typedef list_iterator<T> iterator;
  iterator begin() { return iterator(head_); }
  iterator end() { return iterator(end_); }
  list_iterator<T> erase(iterator itr);
  list_iterator<T> insert(iterator itr, T const& v);
  
  
private:
        
   void copy_list(const UnrolledLL<T>& old);
   void destroy_list();
        
   Node<T>* end_;
   Node<T>* head_;
   Node<T>* tail_;
   unsigned int size_;

};

template <class T>
list_iterator<T> UnrolledLL<T>::insert(iterator itr, T const& v)
{
   //Push front, if itr is at begin()
   if(itr==this->begin())
   {
      this->push_front(v);
      itr++;
      return itr;
   }
   //Push back, if itr is at end()
   if(itr==this->end())
   {
      this->push_back(v);
      return itr;
   }
   //If itr is at the beginning of a full node, create a new node
   if(itr.offset==0 && itr.ptr_->num_elements==NUM_ELEMENTS_PER_NODE)
   {
      Node<T>* temp=new Node<T>(v);
      temp->next_=itr.ptr_;
      temp->prev_=itr.ptr_->prev_;
      temp->prev_->next_=temp;
      itr.ptr_->prev_=temp;
      return itr;
   } 
   //If itr is somewhere else in a full node, create a new node
   if(itr.ptr_->num_elements==NUM_ELEMENTS_PER_NODE)
   {
      Node<T>* temp=new Node<T>(itr.ptr_->value_[NUM_ELEMENTS_PER_NODE-1]);
      int x;
      for(x=NUM_ELEMENTS_PER_NODE-1 ; x>=itr.offset ; x--)
         itr.ptr_->value_[x]=itr.ptr_->value_[x-1];
      itr.ptr_->value_[itr.offset-1]=v;
      return itr;
   }
   //If itr is in a node with room for the new element
   {
        int x;
        for(x=itr.ptr_->num_elements-1;x>=itr.offset ; x--)
           itr.ptr_->value_[x]=itr.ptr_->value_[x-1];
        itr.ptr_->value_[itr.offset-1]=v;
        itr.ptr_->num_elements=itr.ptr_->num_elements+1;
        return itr;
   }
}

template <class T>
list_iterator<T> UnrolledLL<T>::erase(iterator itr)
{
   //Size=1
   if(size_==1)
   {
      destroy_list();
      itr=NULL;
      return itr;
   }
   //Number of elements in node=1, head node
   if((itr.ptr_)->num_elements==1 && (itr.ptr_)==(this->head_))
   {
      head_=head_->next_;
      itr++;
      delete head_->prev_;
      head_->prev_=NULL;
      return itr;
   }
   //Number of elements in node=1, tail node
   if((itr.ptr_)->num_elements==1 && (itr.ptr_)==(this->tail_))
   {
      tail_=tail_->prev_;
      delete tail_->next_;
      tail_->next_=end_;
      end_->prev_=tail_;
      itr=NULL;
      return itr;                               
   }
   //First element
   if(itr.ptr_==(this->head_) && itr.offset==0)
   {
      this->pop_front();
      return itr;
   }
   //Last element
   if(itr.ptr_==(this->tail_) && itr.offset==(itr.ptr_)->num_elements-1)
   {
      this->pop_back();
      return itr;
   } 
   //Only one element in node
   if(itr.ptr_->num_elements==1)
   {
      itr++;
      itr.ptr_->prev_=itr.ptr_->prev_->prev_;
      delete itr.ptr_->prev_->next_;
      itr.ptr_->prev_->next_=itr.ptr_;
      return itr;
   }
   //Last element in node
   if(itr.offset==itr.ptr_->num_elements-1)
   {
      itr.ptr_->num_elements=itr.ptr_->num_elements-1;
      itr++;
      return itr;
   }
   //Normal case... More than one element in the node, not the last element in the node, and not the very first element in the list
   int x;
   for(x=itr.offset; x < itr.ptr_->num_elements;x++)
      itr.ptr_->value_[x]=itr.ptr_->value_[x+1];
   itr.ptr_->num_elements=itr.ptr_->num_elements-1;
   return itr;
   
}

template <class T>
UnrolledLL<T>& UnrolledLL<T>::operator= (const UnrolledLL<T>& old) {
  if (&old != this) {
    this->destroy_list();
    this->copy_list(old);
  }
  return *this;
}

template <class T>
void UnrolledLL<T>::copy_list(const UnrolledLL<T>& old)
{
     size_=old.size_;
     //empty list
     if(size_==0)
     {
         head_=tail_=end_=0;
         return;
     }
     //Create an appropritate number of nodes
     Node<T>* temp=new Node<T>;
     head_=tail_=temp;
     for(int x=0;x<((size_-1)/6);x++)
     {
        temp=new Node<T>;
        tail_->next_=temp;
        temp->prev_=tail_;
        tail_=temp;
     }
     end_=new Node<T>;
     end_->prev_=tail_;
     tail_->next_=end_;
     
     //The minimum number of nodes has been created; head_, tail_, and end_ point to the correct spots, now fill in values
     list_iterator<T> p=old.head_;
     list_iterator<T> q=this->begin();
     for(p;p != old.end_;p++)
     {
        *q=*p;
        q++;
     }
}

template <class T>
void UnrolledLL<T>::destroy_list()
{
   if(head_==tail_)
      delete head_;

   if(head_!=tail_)
   {
      list_iterator<T> p=head_;
      p++;
      for(p;p!=end_;p++)
      {
        delete (p.ptr_)->prev_;
      }
      delete p.ptr_;
   }
   
   delete end_;
   head_=NULL;
   tail_=NULL;
   end_=NULL;
}

template <class T>
std::ostream& operator<<(std::ostream& os, UnrolledLL<T> a)
{
   list_iterator<T> itr=a.begin();
   for(itr ; itr != a.end() ; itr++)
      os << *itr << " ";
   return os;
}

template <class T>
void UnrolledLL<T>::push_front(const T& v) {
     //If there is no Node in existence
     if(!tail_)
     {
        Node<T>* temp=new Node<T>(v);
        head_=tail_=temp;
        end_=new Node<T>;
        end_ -> prev_ = tail_;
        tail_ -> next_ = end_;
        size_++;
        return;
     }
     
     //If the current head Node is full
     if(head_ -> num_elements==NUM_ELEMENTS_PER_NODE)
     {
        Node<T>*temp=new Node<T>(v);
        head_ -> next_ = temp;
        temp -> prev_ = head_;
        head_=temp;
     }
     
     //If the current head Node has more room
     if(head_ -> num_elements<NUM_ELEMENTS_PER_NODE)
     {
        for(int x=head_->num_elements-1;x==0;x++)
        {
           head_ -> value_[x+1] = head_ -> value_[x];
        }
        head_ -> value_[0]=v;
        head_ -> num_elements = head_ -> num_elements + 1;
     }
}

template <class T>
void UnrolledLL<T>::pop_front() {
     //This is assuming there's a node in existence
     //Normal case, if head has more than one value
     if(head_ -> num_elements > 1)
     {
        for(int x=0;x< head_ -> num_elements; x++)
        {
           head_->value_[x]=head_->value_[x+1];
        }
        head_->num_elements=head_->num_elements-1;
     }
     //If head has only one value, but there are other nodes
     if(head_-> num_elements==1 && size_>1)
     {
        head_=head_->next_;
        delete head_->prev_;
        head_->prev_=NULL;
     }
     //If there's only one value total, everything goes to null
     if(size_==1)
     {
        delete head_;
        delete end_;
        head_=NULL;
        tail_=NULL;
        end_=NULL;
     }
     size_--;
}

template <class T>
void UnrolledLL<T>::pop_back() {
     //This is assuming there's a node in existance
     //Normal case, if tail has more than one value
     if(tail_ -> num_elements > 1)
     {
        tail_-> num_elements = tail_-> num_elements -1;
     }
     //If tail has only one value, but there are other nodes
     if(tail_-> num_elements==1 && size_>1)
     {
        tail_=tail_->prev_;
        delete tail_->next_;
        tail_->next_=end_;
        end_->prev_=tail_;
     }
     //If there's only one value total, everything goes to null
     if(size_==1)
     {
       delete head_;
       delete end_;
       head_=NULL;
       tail_=NULL;
       end_=NULL;
     }
     size_--;
}
       
     

template <class T>
void UnrolledLL<T>::push_back(const T& v) {
   //If there is no Node in existence
   if(!tail_)
   {
      Node<T>* temp=new Node<T>(v); 
      head_=tail_=temp;      
      end_=new Node<T>;
      end_ -> prev_ = tail_;
      tail_ -> next_ = end_;
   }
   //If the current tail Node is full
   if(tail_ -> num_elements==NUM_ELEMENTS_PER_NODE)
   {
      Node<T>* temp=new Node<T>(v);
      tail_ -> next_ = temp;
      temp -> prev_ = tail_;
      tail_=temp;
      tail_ -> next_ = end_;
      end_ -> prev_ = tail_;
   }
   //If the current tail Node has more room
   if(tail_ -> num_elements<NUM_ELEMENTS_PER_NODE)
   {
      tail_ -> value_[tail_ -> num_elements]=v;
      tail_ -> num_elements = tail_ -> num_elements++;
   }
   
   size_++;
}

template <class T>
class list_iterator
{
public:
   list_iterator() : ptr_(NULL), offset(0) {};
   list_iterator(Node<T>* p) : ptr_(p), offset(0) {};
   list_iterator(Node<T>* p, int q): ptr_(p), offset(q) {};
   list_iterator(list_iterator<T> const& old) : ptr_(old.ptr_) {}
  ~list_iterator() {};
  
    list_iterator<T> & operator=(const list_iterator<T> & old) { 
       ptr_ = old.ptr_;  return *this; }
    
   // dereferencing operator gives access to the value at the pointer
   T& operator*()  { return ptr_->value_[offset];  }
   
  // increment operator
  list_iterator<T> & operator++() { 
    if(offset==ptr_->num_elements-1)
    {
       ptr_ = ptr_->next_; 
       offset=0;
    }
    if(offset<ptr_->num_elements-1)
    {
       offset++;
    }
    return *this;
  }
  
  list_iterator<T> operator++(int) {
    list_iterator<T> temp(*this);
    if(offset==ptr_->num_elements-1)
    {
       ptr_ = ptr_->next_;
       offset=0;
    }
    if(offset<ptr_->num_elements-1)
    {
       offset++;
    }
    return temp;
  }

  // decrement operator
  list_iterator<T> & operator--() {
    if(offset==0)
    {
       ptr_ = ptr_->prev_;
       offset=ptr_->num_elements-1;
    }
    if(offset>0)
    {
       offset--;
    }
    return *this;
  }
  
  list_iterator<T> operator--(int) {
    list_iterator<T> temp(*this);
    if(offset==0)
    {
       ptr_=ptr_->prev_;
       offset=ptr_->num_elements-1;
    }
    if(offset>0)
    {
       offset--;
    }
    return *this;
  }
  
  friend class UnrolledLL<T>;
  
  // comparison
  friend bool operator==(const list_iterator<T>& l, const list_iterator<T>& r) {
    return l.ptr_ == r.ptr_; }
  friend bool operator!=(const list_iterator<T>& l, const list_iterator<T>& r) {
    return l.ptr_ != r.ptr_; }

private:
   Node<T>* ptr_;
   unsigned int offset;
};






#endif