package chapter06;

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

/**
 * @author LbZhang
 * @version 创建时间：2015年11月17日 下午8:12:14
 * @description 类说明
 */
public abstract class LinkedList<T> implements Iterable<T>, ListADT<T> {

	protected int count;
	protected LinearNode<T> head, tail;
	protected int modCount;

	/**
	 * Creates an empty list.
	 */
	public LinkedList() {
		count = 0;
		head = tail = null;
		modCount = 0;
	}

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

		LinearNode<T> current = head;// 当前的结点

		/**
		 * 是否相等
		 */
		if (size() == 1)
			head = tail = null;
		else
			head = current.getNext();//

		count--;
		modCount++;
		return current.getElement();
	}

	@Override
	public T removeLast() {
		if (isEmpty())
			throw new EmptyCollectionException("LinkedList");
		boolean found = false;
		// 使用两个引用遍历
		LinearNode<T> previous = null;// 前一结点的设置
		LinearNode<T> current = head;// 当前的结点

		// 找最后的结点
		while (current != null && !found) {
			if (current.equals(tail)) {
				found = true;
			} else {
				previous = current;
				current = current.getNext();
			}
		}
		/**
		 * 是否相等
		 */
		if (size() == 1)
			head = tail = null;
		else {
			tail = previous;
			tail.setNext(null);
		}
		count--;
		modCount++;

		return current.getElement();
	}

	@Override
	public T remove(T targetElement) {
		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) // only one element in the list
			head = tail = null;
		else if (current.equals(head)) // target is at the head
			head = current.getNext();
		else if (current.equals(tail)) // target is at the tail
		{
			tail = previous;
			tail.setNext(null);
		} else
			// target is in the middle
			previous.setNext(current.getNext());

		count--;
		modCount++;

		return current.getElement();
	}

	@Override
	public T first() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T last() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean contains(T target) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}

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

	/**
	 * 内部类 的实现iterator
	 * 
	 * @author MrLBZ
	 * 
	 */
	private class LinkedListIterator implements Iterator<T> {
		private int iteratorModCount; // the number of elements in the
		private LinearNode<T> current; // the current position

		/**
		 * 构造函数
		 */
		public LinkedListIterator() {
			current = head;
			iteratorModCount = modCount;
		}

		/**
		 * 判定是否还有下一个结点
		 */
		public boolean hasNext() throws ConcurrentModificationException {
			if (iteratorModCount != modCount)
				throw new ConcurrentModificationException();

			return (current != null);
		}

		/**
		 * 返回元素
		 */
		public T next() throws ConcurrentModificationException {
			if (!hasNext())
				throw new NoSuchElementException();

			T result = current.getElement();
			current = current.getNext();
			return result;
		}

		/**
		 * 移除元素
		 */
		public void remove() throws UnsupportedOperationException {
			throw new UnsupportedOperationException();
		}
	}
	public String toString()
	{
		int n = count;
		String result = "";
		LinearNode<T> current = head;
		while(n > 0){
			result += current.getElement()+" ";
			current = current.getNext();
			n--;
		}
		return result;
	}

}