/*
 * T12n03.java:  This is an incomplete linked list class.  The features of
 *   interest for this lecture topic are the recursive sequential search
 *   and list reversal methods.  More detailed comments may be found ahead
 *   of those methods.
 */

import java.util.*;

public class T12n03
{
    public static void main (String [] args)
    {
        LList<Double> list1 = new LList<Double>();

        System.out.print("The list contains " + list1.size() + " items:  ");
        list1.display();

        System.out.print("Searching for 5:  ");
        if (list1.search(5.0))
            System.out.println("Glorious Success!");
        else 
            System.out.println("bitter failure.");

        list1.append(5.0);
        list1.append(10.0);
        list1.append(15.0);
        list1.append(20.0);
        list1.append(25.0);
        list1.append(30.0);

        System.out.print("\nThe list now contains " +list1.size()+ " items:  ");
        list1.display();

        System.out.print("Searching for 5:  ");
        if (list1.search(5.0))
            System.out.println("Glorious Success!");
        else 
            System.out.println("bitter failure.");

        System.out.print("Searching for 15:  ");
        if (list1.search(15.0))
            System.out.println("Glorious Success!");
        else 
            System.out.println("bitter failure.");

        System.out.print("Searching for 30:  ");
        if (list1.search(30.0))
            System.out.println("Glorious Success!");
        else 
            System.out.println("bitter failure.");

        System.out.print("Searching for 24:  ");
        if (list1.search(24.0))
            System.out.println("Glorious Success!");
        else 
            System.out.println("bitter failure.");


                // Testing reverse

        LList<Integer> list2 = new LList<Integer>(), revList;

        System.out.print("\nThe list contains " + list2.size() + " items:  ");
        list2.display();

        System.out.print("Reversing empty list:  ");
        list2.display();
        revList = list2.reverse();
        System.out.print("The reversed list contains " 
                       + revList.size() + " items:  ");
        revList.display();

        list2.append(11);

        System.out.print("\nReversing one-item list:  ");
        list2.display();
        revList = list2.reverse();
        System.out.print("The reversed list contains " 
                       + revList.size() + " items:  ");
        revList.display();

        list2.append(12);

        System.out.print("\nReversing two-item list:  ");
        list2.display();
        revList = list2.reverse();
        System.out.print("The reversed list contains " 
                       + revList.size() + " items:  ");
        revList.display();

        list2.append(13);
        list2.append(14);

        System.out.print("\nReversing four-item list:  ");
        list2.display();
        revList = list2.reverse();
        System.out.print("The reversed list contains " 
                       + revList.size() + " items:  ");
        revList.display();

    }
}


class LList<E>
{
    private Node<E> head;           // references the first node in the list

    public LList()
    {
        head = null;             // initially, the list is empty
    }

    public LList(Node<E> head)
    {
        this.head = head;        // Start with the given node
    }


            /* search() -- Recursively travel the list members and return
             * true if a node containing the given target value is found.
             * If the target is not found, false is returned.
             *
             * Because we start a search on behalf of the entire LList object,
             * and the recursive solution needs to treat sublists as linked
             * lists, we need a helper method to hold the recursion.  Because
             * the helper has need of list nodes that are not available to
             * external methods, we keep it private.
             */
    
    public boolean search (E target)
    {
        return search(head,target);    // Hand-off to the helper method
    }

    private boolean search (Node<E> head, E target)
    {
        if (head == null)      // Base Case 1: Can't find target in empty list
            return false;

        if (target.equals(head.getData()))  // Base Case 2: Is target 1st node?
            return true;

        return (search(head.getNext(),target));  // General Case:  Look in rest
    }


            /* reverse() -- Create a new LList that holds the same content
             * as this list, but in reverse order.  Like search(), we need 
             * a public "storefront" method and a private "helper" method.
             *
             * If you look this over and ask, "Why doesn't reverse() just
             * call append()?", you need to think in a little more depth
             * about the environment in which append() operates.
             */
    
    public LList<E> reverse ()
    {
        return new LList<E> (reverse(head));
    }
    
    public Node<E> reverse (Node<E> head)
    {
        if (head == null) {   // Base Case:  Reverse of empty list is empty
            return null;
        } else {             // General Case: Reverse all but 1st, append 1st

                // reverse list consisting of nodes 2 ... n

            Node<E> rest = reverse(head.getNext());

                // append head node's data to end of reversed list

            Node<E> newNode = new Node<E> (head.getData());
            newNode.setNext(null);

            if (rest == null) {
                rest = newNode;
            } else {
                Node<E> temp = rest;
                while (temp.getNext() != null) {
                    temp = temp.getNext();
                }
                temp.setNext(newNode);
            }

                // return completed reversed list

            return rest;
        }
    }


            /* display() -- Travel the list members and display the
             * content of each.  It's not a great idea to code
             * such a method within the list class (having just one way to
             * display the content isn't flexible), but as our current
             * list has very few operations, we'll settle for this.
             */
    
    public void display ()
    {
        Node<E> temp = head;
        while (temp != null) {
            System.out.print(temp.getData() + "  ");
            temp = temp.getNext();
        }
        System.out.println();
    }


            /* size() -- To figure the # of items in the list, this method
             * uses the traditional 'travelling pointer' method to visit
             * each list node in turn.
             */

    public int size ()
    {
        int count = 0;
        Node<E> ptr = head;

        while (ptr != null) {
            count++;
            ptr = ptr.getNext();
        }

        return count;
    }

            /* append(Object) -- attaches the given object (well, attaches
             * a Node object containing a copy of the given object reference)
             * to the end of the list.  Note that append may be appending to
             * the end of a list, or may be placing the first node in the
             * list.
             */

    public void append (E object)
    {
        Node<E> newNode = new Node<E> (object);

        newNode.setNext(null);         // a new node will always be the last

        if (head == null) {            // this new node will be the only node
            head = newNode;
        } else {                       // need to attach to old last node
            Node<E> temp = head;
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            temp.setNext(newNode);
        }
    }

}

        /* The Node class.  Not much to say:  A LList is a group of
         * dynamically allocated nodes, each containing the data to be
         * stored and information necessary to relate nodes to each
         * other (a reference to the succeeding node).  Nodes don't do
         * anything other than permit the outside world to look at
         * their values and change their values.
         */

class Node<E>
{
    private E data;
    private Node<E> next;

    public Node ()
    {
        next = null;
        data = null;
    }

    public Node (E object)
    {
        data = object;
        next = null;
    }


            /* The getters */

    public       E  getData () { return data; }

    public Node<E>  getNext () { return next; }


            /* The setters */

    public void      setData (E object)     { data = object; }

    public void      setNext (Node<E> node) { next = node; }

}