#include <iostream>
using std::cout;
using std::endl;

// forward declaration of List class, so ListElement can make 
// it a friend.  NOTE: If List is a friend of ListElement, that
// means that the List class has access to the private members
// of the ListElement class, but no one else does (besides ListElement
// itself). 

class List;
class ListIterator;

class ListElement {
 friend class List;
 friend class ListIterator;
 public:
 ListElement(): next(this), prev(this), isHeader(true) {}
 ListElement(int i): item(i), isHeader(false) {}
 ~ListElement() {}  // default destructor
 private:
  int item;
  ListElement *next;    
  ListElement *prev;    
  bool isHeader;
};

class ListIterator {
 friend class List;
 public:
  ListIterator() : currentPtr(NULL) { }
  ListIterator operator++(){
               this->currentPtr->prev=this->currentPtr;
               this->currentPtr->next=this->currentPtr->next->next;              
               return *this;
               }  // advance iterator to the next list node; return value is iterator *after* advancing  
  ListIterator operator--(){
               this->currentPtr->next=this->currentPtr;
               this->currentPtr->prev=this->currentPtr->prev->prev;
               return *this;
               }  // advance iterator to the previous list node; return value is iterator *after* advancing
  ListIterator operator++(int){
                this->currentPtr->prev=this->currentPtr;
               this->currentPtr->next=this->currentPtr->next->next;              
               return *this;
               }  // advance iterator to the next list node; return value is iterator *before* advancing
  ListIterator operator--(int){
               this->currentPtr->next=this->currentPtr;
               this->currentPtr->prev=this->currentPtr->prev->prev;
               return *this;
               }  // advance iterator to the previous list node; return value is iterator *before* advancing
  int operator*(){
       if(currentPtr->isHeader){
                printf("error\n");
                exit(1); 
                }
        return currentPtr->item;                
      } // return contents pointed to by iterator; print "error\n"
        // and terminate program if iterator refers to header node
 private:
  ListElement *currentPtr;
};

class List {
  public:
    List(){
           listSize=0;
           }   // creates an empty list
    ~List(){
	ListIterator *nodePtr, *nextNodePtr;
	nodePtr->currentPtr = head;
	while (nodePtr->currentPtr != NULL)
	{
	nextNodePtr->currentPtr = nodePtr->currentPtr->next;
	delete nodePtr;
	nodePtr = nextNodePtr;
	}      
            }  // *must* deallocate the entire list
    List(const List &L){
       ListIterator lTemp;
	int value;          
       lTemp.currentPtr=L.head;
       while(lTemp.currentPtr->next!=L.head){
               lTemp.currentPtr=lTemp.currentPtr->next;
               ListElement *temp= new ListElement();
		 temp=lTemp.currentPtr;
               this->head->next=temp;
	        this->head->prev=temp;
		 temp->next=this->head;
		 temp->prev=this->head; 
               listSize++;
               }          
               }  // copy constructor (*must* be a deep copy)
    List & operator =(List &L){
		

         }  // *must* (deep) copy list, and must avoid memory leak

    // these are functions to set and test the list iterator
    void SetStartList(ListIterator &p) {p.currentPtr = head->next;}
    void SetEndList(ListIterator &p) {p.currentPtr = head->prev;}
    bool IsUndefined(ListIterator p) {return (p.currentPtr == head);}
    bool AtEndList(ListIterator p) {return (p.currentPtr == head);}
    bool AtStartList(ListIterator p) {return (p.currentPtr == head);}
    bool AtFirstNode(ListIterator p) {return (p.currentPtr == head->next);}
    bool AtLastNode(ListIterator p) {return (p.currentPtr == head->prev);}
    // Insert integer at the beginning of the list  
    void Prepend(int it){
         ListIterator p;    
	  p.currentPtr=this->head;	     
         ListElement *temp= new ListElement();  
         temp->item=it;
		      if(this->IsEmpty()){
                            this->head->next=temp;
				this->head->prev=temp;
				temp->next=this->head;
				temp->prev=this->head;   
                               }   
            else{
                    temp->prev=p.currentPtr;
                    temp->next=p.currentPtr->next;
                    p.currentPtr->next->prev=temp;
                    p.currentPtr->next=temp;
                    p.currentPtr=temp;
                    }

                 listSize++;
}
    // Insert integer at the end of the list
    void Append(int it){
            ListIterator p;
            p.currentPtr=this->head;
	     ListElement *temp= new ListElement();  
            temp->item=it;
		if(this->IsEmpty()){
                            this->head->next=temp;
				this->head->prev=temp;
				temp->next=this->head;
				temp->prev=this->head;   
                               }         
            else{ 
                    temp->next=p.currentPtr;
                    temp->prev=p.currentPtr->prev;
                    p.currentPtr->prev->next=temp;
                    p.currentPtr->prev=temp;
                    p.currentPtr=temp;
                    }
	 
                 listSize++;
}
    // Remove first integer from list, return through first parameter.
    // Success is set to true if original list is nonempty, false if empty
    void Pop(int &it, bool &success){
          if(IsEmpty()){
                             success=false;         
                   }  
          else{
               success=true;
               ListElement *temp= new ListElement(); 
               temp=this->head->next;
               it=temp->item;
               temp->next->prev=this->head;
               this->head->next=temp->next;
               temp->prev=NULL;
	           temp->next=NULL;
               }         
		listSize--;
          }    
    // Remove last integer from list, return through first parameter.
    // Success is set to true if original list is nonempty, false if empty
    void Pull(int &it, bool &success){
          if(IsEmpty()){
                             success=false;         
                   }  
          else{
               success=true;
               ListElement *temp= new ListElement(); 
               temp=this->head->prev;
               it=temp->item;
               temp->prev->next=this->head;
               this->head->prev=temp->prev;
               temp->prev=NULL;
	           temp->next=NULL;
               } 
		listSize--;        
          }      
    // Get first integer on list, return through first parameter
    // Success is set to true if original list is nonempty, false if empty
    void First(int &it, bool &success){
                   if(IsEmpty()){
                             success=false;         
                   }       
                   else{    
                   success=true;          
                   ListElement *temp= new ListElement();
                   temp=head->next;
                   it=temp->item;        
                   }
}
    // Get last integer on list, return through first parameter
    // Success is set to true if original list is nonempty, false if empty
    void Last(int &it, bool &success){
            if(IsEmpty()){
                             success=false;         
                   }       
                   else{    
                   success=true;          
                   ListElement *temp= new ListElement();
                   temp=head->prev;
                   it=temp->item;        
                   }
}
    // insert integer before list element referred to by p
    void InsertBefore(int it, ListIterator p){ //may need to check if 'p' is NULL
         ListElement *temp= new ListElement();  
         temp->item=it;
         if(p.currentPtr->prev==head){
                temp->prev=head;
                head->next=temp;
                temp->next=p.currentPtr;
                p.currentPtr->prev=temp;
                }   
         else{      
               temp->next=p.currentPtr->next;
               p.currentPtr->next->prev=temp;
               temp->prev=p.currentPtr;
               p.currentPtr->next=temp;
         }
         listSize++;
}
    // insert integer after list element referred to by p
    void InsertAfter(int it, ListIterator p){ //may need to check if 'p' is NULL
         ListElement *temp= new ListElement();  
         temp->item=it;
         if(p.currentPtr->next==head){
                temp->next=head;
                head->prev=temp;
                temp->prev=p.currentPtr;
                p.currentPtr->next=temp;
                }   
         else{        
                p.currentPtr->next->prev=temp;
                temp->next=p.currentPtr->next;
                p.currentPtr->next=temp;
                temp->prev=p.currentPtr;
         }
         listSize++;
}
    // delete list element referred to by p; print "error\n"
    // and exit if p refers to the header node
    // p is undefined after this function
    void Delete(ListIterator p){
            if(p.currentPtr==head){
                  printf("error\n");
                  exit(1);
                  }                             
            if(p.currentPtr->prev==head){
                 p.currentPtr->next->prev=head;
		         head->next=p.currentPtr->next;
		         p.currentPtr->next=NULL;
		         p.currentPtr->prev=NULL;
	        }
	        else if (p.currentPtr->next==head){
                 p.currentPtr->prev->next=head;
		         head->prev=p.currentPtr->prev;
		         p.currentPtr->prev=NULL;
		         p.currentPtr->next=NULL;
	}
	else
	{
	p.currentPtr->prev->next=p.currentPtr->next;
	p.currentPtr->next->prev=p.currentPtr->prev;
	p.currentPtr->next=NULL;
	p.currentPtr->prev=NULL;
	}
    listSize--;
    }
    // apply function "func" to each element on the list
    void MapFunction(void (*func)(int &)){
         ListIterator p;         
         this->AtFirstNode(p);
         for(int i=0;i<listSize;i++){
                 func(p.currentPtr->item);
                 p.currentPtr=p.currentPtr->next;
                 }
}     
    // returns true if list empty, false otherwise
    bool IsEmpty(){
         if(listSize==0){
         return true;
         }
         return false;
}
    int GetSize() {return listSize;}

    // must print out list elements, one per line
    void Print(){
         ListIterator p;
         p.currentPtr=this->head->next;         
         for(int i=0;i<listSize;i++){
                 cout << p.currentPtr->item << endl;
                 p.currentPtr=p.currentPtr->next;
                 }
}
  private:
    ListElement *head;
    int listSize;
};