// Michael Tartaglia
// ListSort: List data structure that sorts items as they're entered into
//		an array


public class ListSort
{
   private ListNode head, tail;
   private int length;
   private boolean isFlipped = false;

	// CONSTRUCTOR
   public ListSort() {
      head = tail = null;
      length = 0;
   }

	// LENGTH RELATED METHODS
   public int length() {return length;}
   public boolean isEmpty() {return length == 0;}

	// ITEM ADDTION METHOD
   public void addItem(double x) {
      ListNode curNode, toAdd = new ListNode(x);	// CURRENT AND NEW NODE POINTERS
      checkIfFlipped();					// ENSURE THAT LIST IS IN ASCENDING ORDER
      if (length == 0) head = tail = toAdd;	// IF NEW NODE WILL BE FIRST IN LIST
      else if (x >= tail.data()) {	// ELSE IF ITEM IS > TAIL'S ITEM
         tail.setNext(toAdd);
         toAdd.setPrev(tail);
         tail = toAdd;
      } else if (x <= head.data()) {	// ELSE IF ITEM IS < HEAD'S ITEM
         toAdd.setNext(head);
         head.setPrev(toAdd);
         head = toAdd;
      } else {				// ELSE IF ITEM BELONGS SOMEWHERE IN BETWEEN
         curNode = head;
         while (x > curNode.data()) curNode = curNode.next();	// FIND SPOT FOR ITEM
         toAdd.setPrev(curNode.prev());	// SET PREV
         toAdd.setNext(curNode);				// SET NEXT
         (curNode.prev()).setNext(toAdd);	// SET PREV'S NEXT AS CURRENT ITEM TO ADD
         curNode.setPrev(toAdd);				// SET NEXT'S PREV AS CURRENT ITEM TO ADD
      }
	   ++length;	// INCREASE LENGTH
   }

	// ITEM DELETION METHOD
   public void removeItem(double x) {
      ListNode curNode = head;	// CURRENT MARKER
      checkIfFlipped();				// ENSURE LIST IS IN ASCENDING ORDER
      int index = 0;					// INDEX
      boolean foundItem = false;	// FOUND ITEM BOOLEAN
      while (!foundItem && index < length) {	// SEARCH FOR ITEM
         if (curNode.data() == x) foundItem = true;
         else {
            curNode = curNode.next();
            ++index;
         }
      }
      if (foundItem) {			// REMOVE ITEM
         if (length == 1) {	// ... IF 1 ITEM IS IN LIST
            tail = head = null;
         } else if (curNode == head) {	// IF ITEM TO REMOVE IS HEAD
            head = curNode.next();
            head.setPrev(null);
         } else if (curNode == tail) {	// IF ITEM IS TAIL
            tail = curNode.prev();
            tail.setNext(null);
         } else {								// IF ITEM LIES IN BETWEEN
            (curNode.next()).setPrev(curNode.prev());
            (curNode.prev()).setNext(curNode.next());
         }
         curNode.setNext(null);			// SET POINTERS ACCORDINGLY
         curNode.setPrev(null);
         curNode = null;
         --length;		// DECREASE LENGTH
      }
   }

	// ITEM DELETION METHOD REMOVING ALL INSTANCES OF x IN LIST
   public void removeAllOfItem(double x) {
      while (doesItemExist(x)) removeItem(x);
   }

	// ITEM EXISTENCE CHECKER, RETURNING BOOLEAN
   public boolean doesItemExist(double x) {
      boolean exists = false;
      int index = 0;
      ListNode curNode = head;
      while (!exists && index < length) {
         if (curNode.data() == x) exists = true;
         else {
            curNode = curNode.next();
            ++index;
         }
      }
      return exists;
   }

	// LIST REVERSER, SWAPPING FIRST AND LAST, SECOND WITH SECOND LAST, AND SO ON
   public void flip() {
      double tempData;
      ListNode tempHead = head, tempTail = tail;
      for (int i = 0; i < length/2; ++i) {
         tempData = tempHead.data();
         tempHead.setData(tempTail.data());
         tempTail.setData(tempData);
         tempHead = tempHead.next();
         tempTail = tempTail.prev();
      }
      isFlipped = true;
   }

	// RETURNS ITEM AT POSITION pos
   public double itemAt(int pos) {
      ListNode temp = head;
      for (int i = 0; i < pos; ++i) temp = temp.next();
      return temp.data();
   }

	// CHECK IF LIST IS IN DESCENDING ORDER, & IF SO, REVERSE AGAIN
   private void checkIfFlipped() {
      if (isFlipped) {
         flip();
         isFlipped = false;
      }
   }

}




class ListNode {
   private ListNode p, n;		// PREVIOUS & NEXT NODE POINTERS
   private double x;				// DATA HELD IN NODE

	// NODE CONSTRUCTOR
   public ListNode(double a) {
      p = n = null;
      x = a;
   }

   public ListNode prev() {return p;}	// RETURN PREVIOUS' POINTER
   public ListNode next() {return n;}	// RETURN NEXT'S POINTER
   public double data() {return x;}		// RETURN DATA IN THIS NODE
   public void setPrev(ListNode L) {p = L;}	// SET PREV
   public void setNext(ListNode L) {n = L;}	// SET NEXT
   public void setData(double a) {x = a;}		// SET DATA

}