/**  
    FILE:           LinkedList.java
    AUTHOR:         Cheng, Jeff
    LAST CHANGE:    3-22-02
    PURPOSE:        a doubly-linked list, actually a quadruply-linked 
                    list but we are only concerned with previous and 
                    next links in this class.
                    Note that we may extend class SkipList from this
                    class, and that Java actually provides a linked
                    list for us: at java.util.LinkedList.
    FUNCTIONS:      LinkedList()-----> set head = null
                    LinkedList(size) ---> create a list of size x with 
                    randomly chosen items, whose value >= 0 and <= 5 * size
                    createAndSearch(size, x)--> create a list with size nodes
                    and search for x randomly chosen nodes, and ouput the 
                    time needed for list creation and searching, each.
                    Nodes getHead()----------> returns head
                    printInReverse(node)-----> prints node values in reverse
                    insert(node)-------------> insert a node in sorted order
                    printList()--------------> print the value inside each node
                    search(key)-----------------> search for a node containing
                    the key sought, return node with value == -1 if not found
                    showRelationships()--------> for each node, prints out the
                    node before and after if there exists one, otherwise prints 
                    out a warning message.
    CREDIT:         Adapted from Professor Matloff's
                    Java tutorial, UC Davis.
    COPYRIGHT:      You may use, modify, or distribute my code for 
                    non-commerical use only; you must cite me, Jeff Cheng, 
                    as the source. 
*/
    
package lists;

public class LinkedList{
    private static Nodes head;
    
    public int count;
    
    public LinkedList(){
        count = 0;
        head = null;
        }

    /*  create a linked list of a particular size.
        The values in the nodes are randomly chosen.*/
    public LinkedList(int size){
        /*  maximum value is 5 times list size
            searching becomes prohibitive as soon as
            the maximum value increases */
        head = null;
        int MAX_VALUE = 5 * size;
        for (int i = 0; i < size; i++){
            Nodes node = new Nodes((int)(Math.random()*MAX_VALUE));
            insert(node);}
            }

    /*  serach returns the node if the node containing
        the value sought is found, otherwise return -1*/
    public Nodes search(int key){
        for (Nodes n = head; n != null; n = n.getNext()){
            if (key == n.getValue()){
                return new Nodes(n.getValue());}
            }
        return new Nodes(-1);
        }
    
    /*  inserting Nodes in a sorted manner.
        insert sets head = node if number of nodes == 0
        otherwise if number of nodes == 1, e.g. head = a node
        then if node < head, prepend the node; 
        if node <= head, append the node.
        Otherwise, number of nodes >= 3, if the node being inserted
        is between values, say inserting 5 between 6 and 7,
        change variables accordingly,
        or if the node being inserted >= node with current max
        value, append the node at the end of the list.*/
    public void insert(Nodes node){
        
        count++;
        
        /*  if the list is empty, let head "points" to node */
        if (head == null){
            head = node;
            return;
        }
        /*  otherwise, if the node is less than head, simply insert
            head after the node */
        if (node.getValue() < head.getValue()){
            node.setNext(head);
            head.setPrevious(node);
            head = node;
            return;
        }
        /*  otherwise, if the node is greater or equal to head,
            and there is currently only one node in the list, 
            simply insert after head */
        else if (head.getNext() == null){
            head.setNext(node);
            node.setPrevious(head);
            return;}
            
       /*   if number of nodes >= 3, then we need to see if the node
            is between two node values e.g. insert 7 in between 3 and 9.*/
      for (Nodes n = head; n.getNext() != null; n = n.getNext()){
        //  if the node's value is between 2 nodes
        if (node.getValue() < n.getNext().getValue()){
            node.setNext(n.getNext());
            n.getNext().setPrevious(node);
            node.setPrevious(n);
            n.setNext(node);
            return;}
        /*  otherwise the node is the node with value >= node with 
            current max value. Insert the node after the entire list */
        else if (n.getNext().getNext() == null){
            n.getNext().setNext(node);
            node.setPrevious(n.getNext());
            return;}
        }
    }
    
    /*  create and search builds a linked list of specified listSize, 
        and search for x randomly chosen nodes, and displays the time 
        needed to do the work.
        Note:   nodes can only contain values between 0 and 5 times 
                the listSize e.g.if listSize = 100; 0 <= value <= 500*/
    public static void createAndSearch(int listSize, int x){
        //  to keep track of time needed to do something
        boolean DEBUG = false;
        int MAX_VALUE = 5 * listSize;
        long timeBegan = 0;
        long timeFinished = 0;
        long timeNeeded = 0;
        
        timeBegan = System.currentTimeMillis();
        //  create a linked list of a specified listSize                
        LinkedList aLinkedList = new LinkedList(listSize);
        
        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\n\t Time needed to generate a linked list "+
        "of listSize " + listSize + " = " + timeNeeded + " milliseconds.");
        
        timeBegan = System.currentTimeMillis();
        
        //  search for x randomly chosen nodes
        for (int i = 0; i < x; i++){
            aLinkedList.search((int)(Math.random()*MAX_VALUE));}
        
        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\t Searching for " + x 
        + " randomly chosen nodes " + "took = " + 
        timeNeeded + " milliseconds.");
        
        if (DEBUG){
            aLinkedList.printList();
            aLinkedList.showRelationships();
        }
        }
    
    /*  in case that we need to pass in head as an argument.
        Not recommended, however. */
    public static Nodes getHead(){ return head;}
    
    //  given head, print the node values in reverse recursively.
    public static void printInReverse(Nodes startHere){
    Nodes n = startHere;
    if (n == null){ // empty list 
        return; }    
    else if (n.getNext() == null){  // only one-node list 
        System.out.println(n.getValue());}    
    else { printInReverse(n.getNext());
           System.out.println(n.getValue());} }
    
    /*  utility functions to print out values
        not needed to display output in class lists
        Walks through the entire list, and prints out the
        values contained in each node */
    public void printList(){
        //  if the list is empty, we are done.
        if (head == null){
            return;}
        /*  otherwise, print the values one-by-one until we reach the
            end of the list. e.g. null*/
        for (Nodes n = head; n != null; n = n.getNext()){
            System.out.println(n.getValue());}
        }

    /*  showRelationships() goes through the entire linked list,
        and prints out for each node, the node before, after,
        above, and below it, if not null.
        If it is null, prints out a warning message.*/
    public void showRelationships(){
        for (Nodes n = head; n != null; n = n.getNext()){
            // get previous node
            if (n.getPrevious() != null){
                System.out.println("Previous: "+n.getPrevious().getValue());}
            else if (n.getPrevious() == null){
                System.out.println("Previous: null; logic error.");}
            // get next node                
            if (n.getNext() != null){
                System.out.println("Next: "+n.getNext().getValue());}
            else if (n.getNext() == null){
                System.out.println("Next: null; logic error.");}
            // get above node                
            if (n.getAbove() != null){
                System.out.println("Above: "+n.getAbove().getValue());}
            else if (n.getAbove() == null){
                System.out.println("Above: null; logic error.");}
            // get below node                
            if (n.getBelow() != null){
                System.out.println("Below: "+n.getBelow().getValue());}
            else if (n.getBelow() == null){
                System.out.println("Below: null; logic error.");}
            }
        }
}