// Linked lists in Java, first version

class node
{
  int head;  
  node tail;

  node(int h, node t)  // constructor
  { head=h;  tail=t; }

    void print()
    {
	for(node i=this;i!=null;i=i.tail)
	    System.out.print(i.head+" ");
	System.out.print("\n");
    }

    public String toString()    // separate computation from io.
    {
	String s = "";
	for(node i=this;i!=null;i=i.tail)
	    s = s+i.head+" ";
	return s;
    }
    

  boolean member(int x) // determine if x is in list
  {
    node i = this;
    boolean answer = false;
    while (i!=null && !answer) 
      {
	if (i.head == x) answer = true;
	i = i.tail;
      }
    return answer;
  }

  /* alternative, recursive definition of member: */
 boolean memb(int x) { return x==head || (tail!=null && tail.memb(x)); }
 
 int length()
  {  if (tail==null) return 1; else return 1+tail.length(); }

 // static version
 static int length(node n)
    {
        if (n==null) return 0; else return 1+length(n.tail);
    }


  void add(int x) // add new integer to end of list
  {
    node i = this;
    while (i.tail != null)  i = i.tail;
    i.tail = new node(x,null);
  }

  int get(int n) throws Exception // get nth element starting from this node
  {
    node i = this;
    for(;n>0 && i!=null; i=i.tail, n--);
    if (i == null) throw new Exception("index out of bounds");
    else return i.head;
  }


    // function to count the number of occurrences of an element x in a
    // list:
    int count(int x)
    {
	int cx = 0;  // counter register
	node current = this;
	while (current!=null) 
	    {
		if (current.head == x) cx++;
		current=current.tail; 
	    }
	return cx;
    }
    // can you do this recursively?   //// class exercise.
    int countr(int x)
    {
	int cx = 0;
	if (head==x) cx++;
	if (tail==null) return cx; else return cx + tail.countr(x);
    }

    // function to reverse a list (constructive)
  node reverse()
    {
	node stack = null;
	for(node i=this; i!=null; i=i.tail) 
	    stack = new node(i.head,stack);
	return stack;
    }
    // this function is constructive because it doesn't change "this" list:
    // it constructs a brand new list.

    // reverse list L non-destructively and statically, stack==null initially
    private static node rev(node L, node stack)
    {
	if (L==null) return stack;
	else return rev(L.tail,new node(L.head,stack));
    }
    public node reverse2() { return rev(this,null); }

    node drev()  // destructive reverse
    {
	node previous = null;
	node current = this;
	node temp = null;
	while (current.tail!=null)
	    {
		temp = current.tail; // remember before overwrite
		current.tail = previous;
		previous = current;
		current = temp;
	    }
	// at this point, current points to last node, but it hasn't been
	// linked yet to current:
	current.tail = previous;
	return current;
    }



    // insert node with value x at position n.  Here, we need to be
    // careful since the position may be 0, which is the front of the list.
    // Because of this case, we need to return a pointer to the list, because
    // the first element of the list can change.
    node insert(int x, int n) 
    {
	if (n==0) return new node(x,tail);  // special case
	node current = this;
	while (n>1 && current!=null) {current=current.tail; n--;}
	// at this point, if current is null, then we've gone off the deep end.
	if (current!=null) current.tail = new node(x,current.tail);
	else throw new Error("list index error");
	return this;   // the original "this" still points to the front of list
    }
    // there is still a "vulnerability" here, can you spot it? (n<0)
    // Another way is to implement it in the stack class.


    // delete node at position n, again, first node can change, so must return.
    // note that this is destructive. (not constructing a new list).
    node delete(int n)
    {
	if (n==0) return tail; // special case
	node current= this;
	while (n>1 && current.tail!=null) {current=current.tail; n--;}
	// at this point, current.tail may be null, in which case there's
	// nothing to delete.
	if (current.tail!=null) 
	    current.tail = current.tail.tail;
	return this;
    }// delete.


    // delete the first cell with head==x from the list (destructive)
    node deletefirst(int x)
    {
	if (head==x) return tail; // special case
	node current = this.tail;
	node previous = this;
	while (current!=null && current.head!=x)
	    {
		previous = current;
		current=current.tail;
	    }
	if (current!=null) // element to be deleted found
	    previous.tail = current.tail;
	return this;
    }

    // delete until everything between this node and last node
    // in list with same head
    void cut()
    {
	node current =this.tail;
	node candidate = null;
	while (current!=null)
	    {
		if (current.head==head) candidate = current;
		current = current.tail;
	    }
	if (candidate!=null) tail = candidate.tail;
    }
} // class node


public class first
{

public static void main(String[] argv) 
{
  try
      {
  node N = new node(2, new node(4, new node(6, null)));
  N.add(8);
  System.out.println("the third element is "+N.get(2));
  System.out.println(N.memb(5));
  N.print();
  N = N.deletefirst(6);   
  N = N.drev();
  N.print();

  // gui operation:
  plaingui G = new plaingui(0,0,400,400);
  G.println(N.toString());

  String command = "blah";
  while (!command.equals("quit"))
      {
	  command = G.getinput("enter list command:");
	  String[] parse = command.split("\\s"); // split among white space
	  if (parse[0].equals("add")) 
	      N.add(Integer.parseInt(parse[1]));
	  if (parse[0].equals("delete"))
	      N = N.deletefirst(Integer.parseInt(parse[1]));
	  G.println(N.toString());
      }// while
  G.dispose(); // destroys window when done.
  
      }
  catch (Exception e) {System.out.println(e);}
}

} // class first

/* talk about how to write gas station part 3:

1. instead of head, just add tail pointer to gasstation class.
2. make type of head gas station. i.e, the head is a pointer to a
   gas station object.
*/