//Author: Tianyi Zhou


import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;




public class URLinkedList<T> implements URList<T>{

    /**
     * create attributions
     * 
     */

    int size = 0;

    URNode<T> first;
    URNode<T> last;

    /**
     * Constructors for URLinkedList
     * 
     */
    public URLinkedList(){}
    /**
	 * 
	 * @param c collection added to the linkedlist at the beginning of initialization
	 * @see URLinkedList.addAll()
	 */
	@SuppressWarnings("unchecked")
    public URLinkedList(Collection<?> c){
		Collection<? extends T> d = (Collection<? extends T>)c;
		addAll(d);
    }



	//METHODS

	URNode<T> node(int index){
		URNode<T> x = first;
		for(int i = 0;i < index;i++)
			x = x.next();
		return x;
	}
	/**
	 * add item e to the first node in the linked list
	 * @param e
	 */
	public void addFirst(T e){
		URNode<T> original = first;
		URNode<T> newNode = new URNode<T>(e, null, original);
		first = newNode;
		if(original == null) 
			last = newNode;//if there's only e in the linkedlist, then the first is also the last
		else 
			original.setPrev(newNode);
		size++;
	}
	public void addLast(T e){
		URNode<T> original = last;
		URNode<T> newNode = new URNode<T>(e, original, null);
		last = newNode;
		if(original == null) 
			first = newNode; // if only e exist, then the last is also the first
		else
			original.setNext(newNode);
		size++;
	}
	/**
	 * peekFirst/peekLast reuturn the First/Last element in the list, pollFirst/pollLast remove the First/Last element in the list 
	 * after element returned
	 * @see URLinkedList.removeFirst()]
	 * @see URLinkedList.removeLast()
	 */
	public T peekFirst(){
		if(first == null) return null;
		return first.element();
	}
	public T peekLast(){
		if(last == null) return null;
		return last.element();
	}
	public T pollFirst(){
		if(first == null) return null;
		T element = first.element();
		removeFirst();
		return element;
	}
	public T pollLast(){
		if(last == null) return null;
		T element = last.element();
		removeLast();
		return element;
	}

    /**
	 * add element to the end of the list
	 * @param e element added
	 * @see URLinkedList.addLast()
	 */
	public boolean add(T e){
		addLast(e);
		return true;
    }
	/**
	 * add element to the specific location
	 * @param index index for insertion
	 * @param element element for insertion
	 * @throws indexOutOfBoundsException if index > 0 && index <= list's size
	 */
	public void add(int index, T element){
		if(!(index >= 0 && index <= size)){
			throw new IndexOutOfBoundsException("index has to be larger than 0 and smaller than list size");
		}
		if(index == size)
			addLast(element);
		else
			linkBefore(element, node(index));
	}
	public void linkBefore(T element, URNode<T> succNode){
		URNode<T> prev = succNode.prev();
		URNode<T> newNode = new URNode<>(element, prev, succNode);
		if(prev == null)
			first = newNode;
		else
			prev.setNext(newNode);
		size++;
	}

	/**
	 * Appends all of the elements in the specified collection to the end of this list,
	 * in the order that they are returned by the specified collection's iterator
	 * @param c collection of elements waiting to add
	 * @throws IndexOutOfBoundsException if requested index illegal
	 * @throws NullPointerException if collection is null
	 * */ 
	public boolean addAll(Collection<? extends T> c){
		return addAll(size, c);
	}

	@SuppressWarnings("unchecked")
	public boolean addAll(int index, Collection<? extends T> c){
		if(!(size >= 0 && size <= size)) throw new IndexOutOfBoundsException();
		if(c == null) throw new NullPointerException("added collection can't be null");

		Object[] other = c.toArray();
		int len = other.length;
		if(len == 0) return false;

		URNode<T> prev;
		URNode<T> succ;
		if(index == size){
			succ = null;
			prev = last;
		}else{
			succ = node(index);
			prev = succ.prev();
		}
		
		for(Object i: other){
			T e = (T) i;
			URNode<T> newNode = new URNode<>(e, prev, null);
			if(prev == null) first = newNode;
			else prev.setNext(newNode);
			prev = newNode;
		}
		if(succ == null) last = prev;
		else{
			prev.setNext(succ);
			succ.setPrev(prev);
		}
		size++;
		return true;
	}
	
	// Removes all of the elements from this list 
	public void clear(){
		for(URNode<T> x = first; x != null;){
			x.setPrev(null);
			x.setElement(null);
			x.setNext(null);
			URNode<T> next = x.next();
			x = next;
		}
		first = null;
		last = null;
		size = 0;
	}

	// Returns true if this list contains the specified element.
	public boolean contains(Object o){
		return indexOf(o) >= 0;
	}
	/**
	 * Check if all elements in specific colleciton contained within the list
	 * @see URLinkedList.contains(
	 * @see URLinkedlist.toArray()
	 */
	public boolean containsAll(Collection<?> c){
		Object[] d = c.toArray();
		for(Object i: d){
			if(!(contains(i))) return false;
		}
		if(c.size() > size) return false;
		else return true;
	}

	/**
	 * Compares if Object equals to the list
	 * @param o Object
	 * @see URLinkedList.toArray()
	 * @throws NullPointerExcpetion
	 * @throws ClassCastException
	 */
	public boolean equals(Object o){
		if(o == null) throw new NullPointerException("comparing object cannot be null");
		if(!(o instanceof URLinkedList<?>)) throw new ClassCastException("not the same instance");
		
		Collection<?> c = (Collection<?>)o;
		Object[] d = c.toArray();
		if(size != d.length) return false;
		int index = 0;
		for(URNode<T> x = first; x != null; x = x.next()){
			if(!x.element().equals(d[index])) return false;
		}
		return true;
	}

	/**
	 * Returns the element at the specified position in this list.
	 * @param index index returned
	 * @throws IndexOutOfBound if index illegal
	 * @see URNode.element()
	 */
	public T get(int index){
		if(!(index >= 0 && index <= size)) throw new IndexOutOfBoundsException("cannot get outOfBound index");
		return node(index).element();
	}

	/**
	 * return -1 if not found, otherwise return index where first element found
	 * @param o object searching for
	 * @see URNode.element()
	 */
	public int indexOf(Object o){
		int index = 0;
		if(o == null){
			for(URNode<T> x = first;x != null;){
				if(x.element()==null) return index;
				index++;
				x = x.next();
			}
		}else{
			for(URNode<T> x = first;x != null;){
				if(o.equals(x.element())) return index;
				index++;
				x = x.next();
			}
		}
		return -1;
	}

	// Returns true if this list contains no elements.
	public boolean isEmpty(){
		return size == 0;
	}

	
	/**
	 * All type of remove methods based on different parameters (Multiple overrides)
	 * @param index element index
	 */
	public T remove(int index){
		if(!(index >= 0 && index <= size)) throw new IndexOutOfBoundsException("Index out of bound");
		
		URNode<T> x = node(index);
		T element = x.element();
		URNode<T> prev = x.prev();//ROY,IS,MY,SUPERHERO
		URNode<T> next = x.next();
		
		prev.setNext(next);
		next.setPrev(prev);
		x.setNext(null);
		x.setPrev(null);
		x.setElement(null);
		size--;
		return element;

	}
	public T removeFirst(){
		URNode<T> f = first;
		if(f == null) throw new NoSuchElementException("this list is empty");
		else{
			T element = f.element();
			URNode<T> next = f.next();
			f.setElement(null);
			first = next;
			if(next == null) last = null;//if next is null, then after first removed, list be empty
			else next.setPrev(null);//if next not null, then next(now first)'s previous points to null(head)
			size--;
			return element;
		}
	}
	public T removeLast(){
		URNode<T> l = last;
		if(l==null) throw new NoSuchElementException("this list is empty");
		else{
			T element = l.element();
			URNode<T> prev = l.prev();
			l.setElement(null);//clean up element value
			last = prev;
			if(prev == null) first = null;
			else prev.setNext(null);//clean up node value
			size--;
			return element;
		}
	}
	/**
	 * Remove specific Object within the list
	 * @param o object
	 * @see URLinkedList.remove()
	 */
	public boolean remove(Object o){

		if(o == null) throw new IllegalArgumentException("Don't need to remove null");

		if(indexOf(o) >= 0){
			int index = indexOf(o);
			if(index == 0) removeFirst();
			else if(index == size-1) removeLast();
			else remove(index);
			return true;
		}
		else return false;
	}

	/**
	 * Removes all elements within the specific collection and return true
	 * if failed to remove any or partial elements in the list return false
	 * @param c specific collection
	 * @see URLinkedList.toArray()
	 * @see URLinkedList.contains()
	 * @see URLinkedList.remove()
	 * @throws NullPointerException
	 */
	public boolean removeAll(Collection<?> c){
		if(c == null) throw new NullPointerException("given collection is null");
		URNode<T> x = first;
		Object[] d = c.toArray();
		int len = d.length;
		int count = 0;
		for(;x != null;x = x.next()){
			T element = x.element();
			Object e = (Object) element;
			if(contains(e)){
				remove(e);
				count++;
			} 
		}
		if(count == len) return true;
		else return false;
	}

	/**
	 * Set index element to element, return the replaced (original) element
	 * @param index index of element
	 * @param element element want to replace
	 * @throws IndexOutOfBound 
	 */
	public T set(int index, T element){
		if(!(index >= 0 && index <=size)) throw new IndexOutOfBoundsException();

		URNode<T> x = node(index);
		T e = x.element();
		x.setElement(element);
		return e;
	}

	// Returns the number of elements in this list.
	public int size(){
		return size;
	}


	/**
	 * return a object array type containing all elements within the list
	 */
	public Object[] toArray(){
		Object[] arr = new Object[size];
		int index = 0;
		for(URNode<T> x = first; x != null; x = x.next()){
			arr[index] = x.element();
			index++;
		}
		return arr;
	}

	// Returns an iterator over the elements in this list in proper sequence.
	public Iterator<T> iterator(){
		
		return new Iterator<T>(){
			URNode<T> current = first;

			@Override
			public boolean hasNext(){
				return current != null;
			}

			@Override
			public T next(){
				if(hasNext()){
					T element = current.element();
					current = current.next();
					return element;
				}
				return null;
			}
			
		};
	}

	/**
	 * Return a subList between given indexes.
	 * @param fromIndex where the subList began
	 * @param toIndex where the subList ended
	 * @throws IndexOutOfBoundException
	 * @throws IllegalArgumentExcpetion
	 * @see URLinkedList.add()
	 */
	public URList<T> subList(int fromIndex, int toIndex){
		if(fromIndex < 0) throw new IndexOutOfBoundsException("index less than 0");
        if(toIndex > size) throw new IndexOutOfBoundsException("index provided larger than ArrayList's size");
        if(fromIndex > toIndex) throw new IllegalArgumentException("fromIndex cannot be larger than toIndex");
		URLinkedList<T> newList = new URLinkedList<>();
		for(int i = fromIndex; i < toIndex; i++){
			URNode<T> x = node(i);
			newList.add(x.element());
		}
		return newList;
	}


	public class URNode<E> { // Doubly linked list node

		private E e; // Value for this node
		private URNode<E> n; // Reference to next node in list
		private URNode<E> p; // Reference to previous node
	
		// Constructors
		URNode(E it, URNode<E> inp, URNode<E> inn) { e = it; p = inp; n = inn; }
		URNode(URNode<E> inp, URNode<E> inn) { p = inp; n = inn; }
	
		// Get and set methods for the data members
		public E element() { return e; } // Return the value
		public E setElement(E it) { return e = it; } // Set element value
		public URNode<E> next() { return n; } // Return next link
		public URNode<E> setNext(URNode<E> nextval) { return n = nextval; } // Set next link
		public URNode<E> prev() { return p; } // Return prev link
		public URNode<E> setPrev(URNode<E> prevval) { return p = prevval; } // Set prev link
	
	}
}