package second_term.sixth_chapter;

import second_term.first_week.EmptyCollectionException;
import second_term.sixth_chapter.ElementNotFoundException;
import second_term.sixth_chapter.ListADT;
import second_term.third_week.LinearNode;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkedList<T> implements ListADT<T>, Iterable<T>
{
    protected int count;
    protected LinearNode<T> head, tail;
	protected int modCount;
    

    public LinkedList()
    {
        count = 0;
        head = tail = null;
		modCount = 0;
	}
    @Override
    public T removefirst() {
        if(isEmpty())
            throw new EmptyCollectionException("LinkedList");

        LinearNode <T> list=head;
        if(size()==1)
        {
            head=tail=null;

        }
        else {
            head=head.getNext();
        }
        count--;
        return  list.getElement();
    }

    @Override
    public T removeLast() throws EmptyCollectionException
    {
              if(isEmpty())
                  throw new EmptyCollectionException("LinkedList");

              LinearNode<T> list=tail;
              if(size()==1)
                  head=tail=null;
              else
              {
                  LinearNode list1=head;
                  while(list1.getNext().getNext()!=null)
                  {
                      list1=list1.getNext();
                  }
                  tail=list1;
                  tail.setNext(null);

              }
              count--;
              return list.getElement();
    }
   

    @Override
    public T remove(T targetElement) throws EmptyCollectionException,
            ElementNotFoundException
    {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");
      
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;
      
        while (current != null && !found)
            if (targetElement.equals(current.getElement()))
                found = true;
            else {
                previous = current;
                current = current.getNext();
            }

        if (!found)
            throw new ElementNotFoundException("LinkedList");
      
        if (size() == 1)  // 列表中只有一个元素
            head = tail = null;
        else if (current.equals(head))  // 目标在头部
            head = current.getNext();
        else if (current.equals(tail))  // 目标在尾部
        {
            tail = previous;
            tail.setNext(null);
        }
        else  // 目标在中间
            previous.setNext(current.getNext());
      
        count--;
		modCount++;
      
        return current.getElement();
    }

    @Override
    public T first() throws EmptyCollectionException
    {
        if(isEmpty())
            throw new EmptyCollectionException("LinkedList");

        return head.getElement();
    }

    @Override
    public T last() throws EmptyCollectionException
    {
       if(isEmpty())
           throw new EmptyCollectionException("LinkedList");

        return tail.getElement();
    }

    @Override
    public boolean contains(T targetElement) {
        boolean idea = false ;
        if (head==null)
            throw new EmptyCollectionException("LindedList");
        else{
            if (count == 1)
                idea=(head.getElement()==targetElement);
            else {
                LinearNode<T> current1 = head;
                LinearNode<T> list  = head.getNext();
                if (current1.getElement() == targetElement)
                    idea = true;
                else{
                    while(list.getElement()!=targetElement&&list.getNext()!=null)
                    { list =list.getNext(); }
                    if (list.getElement()==targetElement)
                        idea =true;
                }
            }
        }
        return idea;
    }
   

    @Override
    public boolean isEmpty()
    {
        if(count==0)
            return true;
        else
            return false;
    }


    @Override
    public int size()
    {
        return count;
    }


    @Override
    public String toString()
    {
        LinearNode<T>list=head;
         String result=""+list.getElement()+" ";

        while(list.getNext()!=null)
        {
            list=list.getNext();
            result+=list.getElement()+" ";
        }
        return result;
    }



    @Override
    public Iterator<T> iterator()
    {
        return new LinkedListIterator();
    }


	private class LinkedListIterator implements Iterator<T>
	{
		private int iteratorModCount;  // the number of elements in the collection
		private LinearNode<T> current;  // the current position

		public LinkedListIterator()
		{
			current = head;
			iteratorModCount = modCount;
		}
		

		@Override
        public boolean hasNext() throws ConcurrentModificationException
		{
			if (iteratorModCount != modCount) 
				throw new ConcurrentModificationException();
			
			return (current != null);
		}

		@Override
        public T next() throws ConcurrentModificationException
		{
			if (!hasNext())
				throw new NoSuchElementException();
			
			T result = current.getElement();
			current = current.getNext();
			return result;
		}

		@Override
        public void remove() throws UnsupportedOperationException
		{
			throw new UnsupportedOperationException();
		}
	}
	
}