/*
 * CHANGE AND COMPLETE THE CODE WHERE NECESSARY
 *
 * AND
 *
 * ADAPT/ADD YOUR COMMENTS!!!!!!!!
 */

import java.util.Random;

/**
 * IntListElem objects are elements of a IntList list. <br>
 *
 * Informatik II - FS2009 <br>
 * Uebungsserie 6 <br>
 *
 * @author Philipp Bolliger
 **/
class IntListElem {
    int value;
    IntListElem next; //reference to the next element of the list

    /**
     * IntListElem constructor
     *
     * @param  v  value of the element being created
     * @param  e  reference to the next element in the list
     **/
    public IntListElem( int v, IntListElem e ) {
        value = v;
        next = e;
    }
} //end class IntListElement

/**
 * The class IntList provides methods to create and use
 * lists of integer. <br>
 *
 * Informatik II - FS2009 <br>
 * Uebungsserie 5, Aufgaben 1-3 <br>
 *
 * @author Philipp Bolliger
 **/
public class IntList {

    private IntListElem first; //reference to the first element of the list

    /**
     * Creates an empty list
     */
    public IntList() {
        first = null;
    }

    /**
     * Tests whether a list is empty or not
     *
     *@return true if the list is empty, false otherwise
     **/
    public boolean empty() {
        return first == null;
    }

    /**
     * Adds an element at the top of the list
     *
     * @param  i  element to add
     **/
    public void addFirst( int i ) {
        first = new IntListElem( i, first );
    }

    /**
     * Adds an element to the end of the list
     *
     * @param  i  value of the element to add
     **/
    public void addLast( int i ) {
        IntListElem elem = new IntListElem( i, null );
        if ( first == null ) {
            first = elem;
        } else {
            IntListElem tmp = first;
            while ( tmp.next != null ) {
                tmp = tmp.next;
            }
            tmp.next = elem;
        }
    }

    /**
     * Removes and returns the first element of the list
     *
     * @return  the first element of the list
     **/
    public int removeFirst() throws Exception {
        if ( first == null ) {
            throw new Exception( "removeFirst() called on an empty list." );
        }
        int i = first.value;
        first = first.next;
        return i;
    }

    /**
     * Removes and returns the last element of the list
     *
     * @return  the last element of the list
     **/
    public int removeLast() throws Exception {
        int i = 0;
        if( first == null ) {
            // list is empty
            throw new Exception( "removeLast() called on an empty list." );

        } else if ( first.next == null ) {
            // list only has the first element
            i = first.value;
            first = null;
        } else {
            // list has more than one element
            IntListElem tmp = first;
            while ( tmp.next.next != null ) {
                tmp = tmp.next;
            }
            i = tmp.next.value;
            tmp.next = null;
        }
        return i;
    }

    /**
     * Returns a string containing the elements of a list
     * (Übungsserie 6, Aufgabe 2b)
     *
     * You are free to propose your own implementation for
     * this method!
     **/
    public String toString() {
        String str = "(";
        IntListElem elem = first;
        while( elem != null ) {
            str = str + elem.value;
            elem = elem.next;
            if (elem != null) str = str + ",";
        }
        str = str + ")";
        return str;
    }


    /**
     * Adds n (pseudo-)random elements to the top of the list
     *
     *@param  n  number of elements to add
     **/
    public void addRandomElements( int n ) {
        Random rnd = new Random();
        for ( int i = 0; i < n; i++ ) {
            int tmp = rnd.nextInt( 200 );
            addFirst( tmp );
        }
    }


    //THE FOLLOWING METHODS MUST BE MODIFIED WHEN SOLVING THE EXERCISE 3
    //FOR THE EXERCISE 2 YOU MUST MODIFY ONLY THE METHODS ABOVE.
    /**
     * Sorts a list of integer numbers.
     **/
    public void sortSelf() {
        IntList sorted = sort();
        first = sorted.first;
    }

    /**
     * Ceates a sorted list from an unsorted one.
     * After being sorted the original list is empty.
     *
     * @return reference to the (new) sorted list
     **/
    public IntList sort() {
        IntList list = new IntList();
        try {
            while ( !this.empty() ) {
                list.insertSorted( this.removeLast() );
            }
        } catch( Exception e ) {
            System.out.println( "Internal Error in method sort()." );
            e.printStackTrace();
            System.exit( 1 );
        }
        return list;
    }

    /**
     * Insert the element i in a ordered list in the correct position.
     * The elements in the list are supposed to be in ascending order
     *
     * @param  i  element to add
     **/
    private void insertSorted( int i ) {
        if ( first == null ) {
            // initial list is empty
            first = new IntListElem( i, null );
        } else {
            // initial list has at least one element
            if ( i < first.value ) {
                // add as first
                addFirst( i );
            } else {
                // add someplace after the first
                IntListElem elem = first;
                while ( elem.next != null ) {
                    if ( i < elem.next.value ) {
                        // insert between e and e.next
                        elem.next = new IntListElem( i, elem.next );
                        return;
                    }
                    elem = elem.next;
                } // end while()
                // end of list reached and not yet inserted: add last
                addLast( i );
            }
        }
    } // end insertSorted()
} // end class IntList