// This is the file to include in your code if you want access to the
// complete LList template class

// First, get the declaration for the base list class


// Linked list implementation
template <class Elem> class LList {
private:
  CLink<Elem>* head;       // Pointer to list header
  CLink<Elem>* tail;       // Pointer to last Elem in list 
  CLink<Elem>* fence;      // Last element on left side
  int leftcnt;            // Size of left partition
  int rightcnt;           // Size of right partition
  void init() {           // Intialization routine
    fence = tail = head = new CLink<Elem>;
    leftcnt = rightcnt = 0;
  }
 
 
// Return link nodes to free store 
void removeall() {   
    while(head != NULL) {
      fence = head;
      head = head->next;
      delete fence;
    }
  }
public:

  LList() { init(); }

  ~LList() { removeall(); }  // Destructor

  void clear() { removeall(); init(); }
  

 
 // Insert at front of right partition  
  bool insert(const Elem&) 
 {
  fence->next = new CLink<Elem>(item, fence->next);  
  if (tail == fence) tail = fence->next;  // New tail
  rightcnt++;
  return true;
}

  

// Append Elem to end of the list 
  bool append(const Elem& item)
 {
  tail = tail->next = new CLink<Elem>(item, NULL);
  rightcnt++;
  return true;
}
  

  
// Remove and return first Elem in right partition  移除fence指針指向元素的下一個元素
 bool remove(Elem& it) {
  if (fence->next == NULL) return false; // Empty right
  it = fence->next->element;       // Remember value
  CLink<Elem>* ltemp = fence->next; // Remember link node
  fence->next = ltemp->next;       // Remove from list
  if (tail == ltemp) tail = fence; // Reset tail
  delete ltemp;                    // Reclaim space
  rightcnt--;
  return true;
}


 
 bool is_empty()
{ 
  if(head->next==NULL)  return true;
  else return false;
}


 void setStart()
    { fence = head; rightcnt += leftcnt; leftcnt = 0; }
 
 
 
 void setEnd()
    { fence = tail; leftcnt += rightcnt; rightcnt = 0; }
 

 
 // Move fence one step left; no change if left is empty 
  void prev()
{
  CLink<Elem>* temp = head;
  if (fence == head) return; // No previous Elem
  while (temp->next!=fence) temp=temp->next;
  fence = temp;
  leftcnt--; rightcnt++;
} 

  

  void next()
{
    if (fence != tail) // Don't move fence if right empty
      { fence = fence->next; rightcnt--; leftcnt++; }
}
  
  int leftLength() const  { return leftcnt; }
  
  int rightLength() const { return rightcnt; }
 
 


// Set the size of left partition to pos  
  bool setPos(int pos)
{
  if ((pos < 0) || (pos > rightcnt+leftcnt)) return false;
  fence = head;
  for(int i=0; i<pos; i++) fence = fence->next;
  return true;
}

 
  

bool getValue(Elem& it) const {
    if(rightLength() == 0) return false;
    it = fence->next->element;
    return true;
  }
  
  
  
bool  Locate(Elem& it)
{
 fence= head;
 while((fence->next != NULL)&&(fence->next->element!=it))  fence=fence->next;
 if( fence->next==NULL) return false;
 else return true;
 }

};