public class DoubleList {
	
	private DNode head;

	private class DNode {
		private Packet p;
		private DNode prev;
		private DNode next;
		
		//This constructor is called to create a node to add to the list
		private DNode (Packet p, DNode prev, DNode next) {
			setPacket(p);
			setPrev(prev);
			setNext(next);
		}
		
		//This constructor is called to set up the head node
		private DNode() { 
			this.p = null; this.prev = this; this.next = this;
		}
		
		//setters
		private void setNext(DNode n){ 
			next = n; 
		}
		private void setPrev(DNode p){ 
			prev = p; 
		}
		private void setPacket (Packet p) {
			this.p = p;
		}
	}
	//Constructor called to intialize the doubly linked list
	public DoubleList() {
		head = new DNode();
	}
	//Routine to find a node in a list give a packet id
	private DNode findNode(int packetID) {
    	DNode curr = head.next;
    	while(curr!=head && curr.p.getPkPacketID() != packetID)
    		curr = curr.next;
    	if (curr==head)    //  not found
    		return null;
    	else
    		return curr;
	}
	//pre - doubly linked list has been created
	//post - boolean value returned whether there are nodes
	//			on the list other than head.
	public boolean isEmpty () {
		return head.next == head;
	}
	
	//pre - doubly linked list has been created
	//post - returns null if the list is empty
	//			returns the packet in the first postion of the list
	public Packet removeNode() {
		if (isEmpty())
			return null;
		return removeNode(head.next);
	}
	
	//Routine to remove a node from the list
	private Packet removeNode(DNode curr) {
		curr.prev.setNext(curr.next);   // set the next of prev to the current next
		curr.next.setPrev(curr.prev);   // set the prev of next to the current prev
		return curr.p;
	}
	
	//pre - doubly linked list has been created
	//post - finds and removes a node from the list
	//			if a node containing the packetID is found,
	//			returns the pointer to the packet id
	//			If a node containing the packet id is not found, 
	//			Returns null.
	public Packet removeNode(int packetID){
    	DNode curr = findNode(packetID);
    	if (curr==null)
    		return null;
    	else 
    		return removeNode(curr);	
    }
	
	//pre - p is a valid packet
	//post - a node containing p has been added to the list.
	public void addNode (Packet p) {
		DNode d = new DNode(p,head.prev, head);
		head.prev.setNext(d);
		head.setPrev(d);	
	}
	
	//post - if the list is empty, it returns "List empty\n"
	//			if the list is not empty, it adds each packet to string along with
	//			a \n after the packet
	public String toString() {
		if (head.next == head)
			return "List empty\n";
		String s = "";
    	DNode curr = head.next;
    	while(curr!=head) {
    		s = s + curr.p + "\n";
    		curr = curr.next;
    	}
    	return s;
	}
	//Use this space for test cases
	public static void main (String[] args) {
		DoubleList s1 = new DoubleList();
		System.out.println (s1);
		Packet p1 = new Packet();
		p1.setPkPacketID(1);
		p1.setPkDestPort(0);
		p1.setPkServiceLevel(Packet.ServiceLevel.HIGH);
		p1.setPkPayload("asfasdf");
		s1.addNode(p1);
		System.out.println (s1);
		Packet p2 = new Packet();
		p2.setPkPacketID(2);
		p2.setPkDestPort(1);
		p2.setPkServiceLevel(Packet.ServiceLevel.NORMAL);
		p2.setPkPayload("asfasdf");
		s1.addNode(p2);
		System.out.println (s1);
		DoubleList d1 = new DoubleList();
		Packet p = d1.removeNode();
		System.out.println("Expected empty list\n" + d1);
		d1.addNode(p1);
		System.out.println("Expected single packet\n" + d1);
		d1.removeNode(p1.getPkPacketID());
		System.out.println ("Expected empty list\n" + d1);
		d1.addNode(p1);
		d1.addNode(p2);
		System.out.println ("Expected 2 packets\n" + d1);
		p = d1.removeNode();
		System.out.println ("Expected 1 packets\n" + d1);
		System.out.println("Expected packet 1\n" + p);
		p = d1.removeNode();
		System.out.println ("Expected empty list\n" + d1);
		System.out.println("Expected packet 2\n" + p);
		p = d1.removeNode();
		System.out.println ("Expected empty list\n" + d1);
		System.out.println("Expected null packet \n" + p);
		d1.addNode(p1);
		System.out.println ("\nTesting findNode");
		DNode dn = d1.findNode(p1.getPkPacketID());
		System.out.println ("Expected 1 packets\n" + d1);
		System.out.println("Expected packet 1\n" + dn.p);
		d1.removeNode(dn);
		System.out.println ("Expected empty list\n" + d1);
		System.out.println("Expected null packet \n" + p);
		
		
		
	}
}