import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

/**A double-side queue implemented with a singly-linked list
 * @author CIS121 Staff
 *
 * @param <K>
 */
public class MyDeque<K>{
	
	private SinglyLinkedList<K> list;
	
	/**Constructor
	 * @param list the head of a singly-linked list (a {@link SinglyLinkedList}
	 * object)
	 */
	public MyDeque(SinglyLinkedList<K> list){
		this.list = list;
	}
	
	/**Add an element to the front of this Deque
	 * @param k the element to add
	 */
	public void addFront(K k){
		list = new SinglyLinkedList<K>(list,k);
	}
	
	/**Add an element to the rear of this list
	 * @param k
	 */
	public void addRear(K k){
		SinglyLinkedList<K> tail = list;
		while(tail.getNext() != null)
			tail = tail.getNext();
		tail.setNext(new SinglyLinkedList<K>(k));
	}
	
	/**Remove and return the front element (dequeue)
	 * @return the front element of this deque
	 */
	public K removeFront(){
		if(list == null)
			return null;
		SinglyLinkedList<K> head = list;
		list = list.getNext();
		return head.getElement();
	}
	
	/**Remove and return the last element
	 * @return the last element in this deque
	 */ 
	public K removeRear(){
		SinglyLinkedList<K> tail = list;
		SinglyLinkedList<K> before_tail = null;
		//For the case where the head is null.
		if(tail==null){
			list = null;
			return null;
		}
		//For the case where there is only a single element in the list.
		else if(tail.getNext()==null){
			SinglyLinkedList<K> tail_and_head = list;
			list = null;
			return tail_and_head.getElement();
		}
		//For all other cases.
		while(tail.getNext()!= null){
			before_tail = tail;
			tail = tail.getNext();
		}
		before_tail.setNext(null);
		return tail.getElement();
	}
	
	/** Returns the number of elements in this deque
	 * @return the number of elements in this deque
	 */
	public int size(){
		int size;
		SinglyLinkedList<K> tail = list;
		if(tail!=null)
			size = 1;
		else size = 0;
		while(tail.getNext()!= null){
			tail=tail.getNext();
			size++;
		}
		return size;	
	}
	
	public static void main(String args[]){
		Deque<Integer> real = new LinkedList<Integer>();
		MyDeque<Integer> my = new MyDeque<Integer>(new SinglyLinkedList<Integer>(1));
		real.add(1);
		Random rand = new Random();
		for (int ii = 0; ii < 1000; ii++){
			if(ii%2==0){
				int add = rand.nextInt();
				real.add(add);
				my.addRear(add);
			}
			else{
				int add = rand.nextInt();
				real.addFirst(add);
				my.addFront(add);
			}
		}
		System.out.println("real:"+real.remove()+"||my:"+my.removeFront());
		for(int ii=0 ; ii < 1000; ii++){
			if(ii%2==0){
				int real_int = real.removeLast();
				int my_int = my.removeRear();
				if(real_int != my_int)
					System.out.println("real:"+real_int+"||my:"+my_int);
				
			}
			else{
				int add = rand.nextInt();
				real.add(add);
				my.addRear(add);
			}
		}
		System.out.println("real:"+real.remove()+"||my:"+my.removeFront());
		if(real.size()!=my.size())
			System.out.println("not equal!! size");
		while(real.size()>0){
			int real_int = real.removeLast();
			int my_int = my.removeRear();
			if(real_int != my_int)
				System.out.println("real:"+real_int+"||my:"+my_int);
				break;
			}
		}
	}