/*
 * T01n03.java:  An incomplete implementation of a reasonably generic
 *   (doubly-linked) Linked List class, including implementations of a 
 *   Node class and an Iterator class.  This is an updated version of
 *   T01n01.java, using Java 1.5's Generics.
 *
 * This file contains these classes and methods:
 *
 *    T01n03 -- Contains the main method, which is just a simple program
 *              that exercises the other classes a bit.
 *    LList -- A doubly-linked list of Node objects.  Consists of 
 *            these methods and classes:
 *        LList() -- the constructor of an empty list
 *        size1() -- computes the number of nodes in the list w/o using an
 *            iterator
 *        size2() -- computes the number of nodes in the list using an
 *            iterator
 *        appendDouble(T) -- adds an object to the end of the linked list
 *        anIterator() -- creates an Iterator for the list from the
 *            LLIterator inner class
 *        LLIterator -- An inner class of LList that implements Java's
 *            Iterator interface.  In particular, next() and hasNext() are
 *            are implemented; the optional remove() method is not. 
 *    Node -- A simple class of three instance variables and their getters
 *            and setters:
 *        getPrevious() -- returns a reference to the Node preceding this one
 *        getNext() -- returns a reference to the Node succeeding this one
 *        getData() -- returns a reference to the object to which this node
 *            refers
 *        setPrevious(Node) -- changes current node's previous reference to
 *            refer to the given Node reference
 *        setNext(Node) -- changes current node's next reference to refer
 *            to the given Node reference
 *        setData(T) -- causes the node to love and cherish the 
 *            given object as its new data item
 *
 *  Obviously, the available methods of the LList class are inadequate
 *  for a 'real' Linked List class, but the purpose of this example is to
 *  demonstrate how to create such a class.  With this framework in place,
 *  additional methods can be added easily.
 *
 *  Finally, be aware that Java includes the LinkedList class, so writing one's
 *  own is rarely necessary.  See the next example program to see Java's
 *  version in action.  For that matter, Java has an iterator for lists
 *  called ListIterator that is much more capable that the basic Iterator
 *  interface.
 */

import java.util.*;

public class T01n03
{
    public static void main (String [] args)
    {
        LList<Double> list;
        Iterator<Double> sequence;

        list = new LList<Double>();

        System.out.println("The list contains " + list.size1() + " items.");

        list.append(new Double (3.1415));
        list.append(new Double (6.2830));

        System.out.print("The list contains " + list.size2() + " items:  ");

                /* Use the list's iterator to help print the list content */

        sequence = list.anIterator();
        while (sequence.hasNext()) {
            Double object = sequence.next();
            System.out.print(object + "  ");
        }
        System.out.println();
    }
}


class LList<T>
{
    private Node<T> head,        // references the first node in the list
                    tail;        // references the last node in the list

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

            /* size1() -- To figure the # of items in the list, this method
             * uses the traditional 'travelling pointer' method to visit
             * each list node in turn.  This is the way to do the job if
             * an iterator is not available.
             */

    public int size1 ()
    {
        int count = 0;
        Node<T> ptr = head;

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

        return count;
    }

            /* size2() -- Does the same job as does size1(), but uses an
             * iterator.  The big difference is that we don't need to
             * reference a Node object directly; the iterator encapsulates
             * those details, making knowledge of the list representation
             * unnecessary.
             */

    public int size2 ()
    {
        int count = 0;
        T tmp = null;
        Iterator<T> sequence = anIterator();

        while (sequence.hasNext()) {
            count++;
            tmp = sequence.next();
        }

        return count;
    }

            /* append(T) -- 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 (T object)
    {
        Node<T> newNode = new Node<T> (object);

        newNode.setNext(null);
        newNode.setPrevious(tail);

        if (head == null) {            // this new node will be the only node
            head = tail = newNode;
        } else {                       // just need to attach to old last node
            tail.setNext(newNode);
            tail = newNode;
        }
    }

            /* anIterator() -- creates and returns an Iterator for the list
             */

    public Iterator<T> anIterator()
    {
        return new LLIterator();
    }

            /* The class LLIterator.  This is an inner (nested) class, meaning
             * that it is declared within the declaration of another class.
             * The idea is that this iterator is specific to this particular
             * list class, and as such does not need to be visible to
             * any other class.  LList supplies a method that creates
             * an iterator for whomever wants one, and the supplied iterator
             * has all necessary interface commands; nothing else is needed.
             */

    private class LLIterator implements Iterator<T>
    {
        Node<T> position;            // to keep track of the current position

        public LLIterator()
        {
            position = null;      // initially, start 'before' the list
        }

                /* next() -- advance to the next object in the list and
                 * return a reference to it.
                 */

        public T next()
        {
           if (!hasNext())        //  if we try to run off the end of the list
               throw new NoSuchElementException();

           if (position == null) {     // if this is 1st time next() is called
               position = head;
           } else {
               position = position.getNext();
           }

           return position.getData();
        }

                /* hasNext() -- test to see if the list contains any more
                 * items over which we might iterate (or, test to see if
                 * next() would succeed if called).
                 */

        public boolean hasNext()
        {
            if (position == null) {    // if we have not yet begun to iterate
                if (head != null) {    // if the list isn't empty
                    return true;
                } else {
                    return false;
                }
            } else {
                if (position.getNext() != null) {
                    return true;
                } else {
                    return false;
                }
            }
        }

                /* remove() -- Story time:  Java's Iterator interface must
                 * be implemented with three methods:  next(), hasNext(),
                 * and remove().  remove() is optional, but the compiler
                 * will complain if you don't define it.  So, in this
                 * context 'optional' means that you have to include it
                 * as a method, but it doesn't have to do anything.  Of
                 * course, it would be nice to let the poor programmer
                 * know that remove() isn't actually working, and so the
                 * exception is thrown.
                 */

        public void remove()
        {
            throw new UnsupportedOperationException();
        }

    }

}

        /* The Node class.  Not much to say:  A LList is a group of
         * dynamically allocated nodes, each containing the data to be
         * stored (in this case, a Generic reference) and information
         * necessary to relate nodes to each other (references to preceding
         * and succeeding nodes).  Nodes don't do anything other than
         * permit the outside world to look at their values and change
         * their values.  Yes, we could have made the instance variables
         * public and done away with the getters and setters, but that's
         * bad form.
         */

class Node<T>
{
    private Node<T> prev;
    private T data;
    private Node<T> next;


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

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

            /* The getters */

    public Node<T> getPrevious ()
    {
        return prev;
    }

    public T getData ()
    {
        return data;
    }

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

            /* The setters */

    public void setPrevious (Node<T> node)
    {
        prev = node;
    }

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

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

}