/* File: TrailingPointerDemo.java
 *
 * Recall that to delete a node from a linked list, we need a pointer to the 
 * previous node, so that we can do a "deleteAfter."  A traditional way to
 * do this is to have two pointers - a "leader," and a "trailer" which is 
 * always one node behind the leader.  Then, when the leader finds the node 
 * to be deleted, we do a deleteAfter using the trailer.
 *
 * Note that deleting the "head" node is a special case (as shown).
 *
 * The TrailingPointerDemo class implements a very limited linked list of ints.
 * All clients can do is append ints and print the list. The class exists only
 * to demonstrate the "trailing pointer" technique, as shown in method 
 * removeNegatives()
 */

public class TrailingPointerDemo
{
    private Node head = null;		// pointer to first node of list

    // append a new node containing parameter x to the end of the list
    public void append(int x)
    {
        // create new Node with "info" portion pointing to x
        Node temp = new Node(x);

        if (head == null)		// if list is empty...
        {
            head = temp;		// ...put new Node at head of list.
        } 
        else				// else, append new node to end of list
        {
            lastNode().next = temp;  	// method returns pointer to last node
        }
    }  

    // remove all nodes that contain a negative int
    public void removeNegatives()
    {
        if (head == null)
        {
            return;   // if empty list, we're done
        }
        Node leader = head;		// point leader to 1st node
        Node trailer = head;		// point trailer to 1st node
        while (leader != null)		// repeat until all nodes visited...		
        {
            // if node pointed to by leader has a negative, delete it...
            if (leader.info < 0)
            {
                if (leader == head)	   // Special Case: deleting head node
                {
                    head = head.next;	   // ...remove it and update head
                    leader = head;	   // ...point leader to new head
                } 
                else			   // it's not the head node
                {
                    leader = leader.next;  // ...advance leader to next node
                    deleteAfter(trailer);  // ...remove the node
                }
            } 
            else  // otherwise, advance to next node
            {
                trailer = leader;
                leader = leader.next;
            }
        }
    }
 
    // delete the node AFTER the one pointed to by p
    private void deleteAfter(Node p)
    {
        Node temp = p.next;             // temp points to node to be removed
        p.next = temp.next;             // cut node out of the list
    }
    
    // return a pointer to the last node on the list or null if list is empty
    private Node lastNode()
    {
        if (head == null)
        {
            return null;
        }
        
        // here if list is not empty

        Node current = head;		// point "current" to first node
        while (current.next != null)	// while current is not at last node...
        {
           current = current.next;	// ...move to next node	
        }
        return current;			// return pointer to last node
    }

    // return a String containing the list
    public String toString()
    {
        if (head == null)
        {
            return "The list is empty!";
        }

        String out = "";
        Node temp = head; 		// start at head of list 
        while (temp != null) 		// while more nodes on list...
        {
            out += temp.info + "  ";	// ...concatenate current node info
            temp = temp.next;		// ...and move to next node
        }
        return out + "\n";
    }

    // ************* Definition of inner class Node *************	
    class Node
    {
        // instance var's			

        private int info;	// the data-bearing portion stores an int 
        private Node next;	// pointer to next Node on the list

        /*
         * Create a new Node with parameter x in the info portion
         */
        Node(int x)
        {
            info = x;
            next = null ;	// not necessary since default is null)
        }
    } // end of Node class definition ======================================
}

/*  Sample output from 2 runs:
 
Original list:   97  -70  39  0  18  -35  -53  -23  30  -51

Updated list:    97  39  0  18  30


Original list:   -87  -71  -52  -2  23  93  57  -47  97  59

Updated list:    23  93  57  97  59

*/