/*
* CHANGE AND COMPLETE THE CODE WHERE NECESSARY
*
* AND
*
* ADAPT/ADD YOUR COMMENTS!!!!!!!!
*/
import java.util.Random;
/**
* IntListElem objects are elements of a IntList list.
*
* Informatik II - FS2009
* Uebungsserie 6
*
* @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.
*
* Informatik II - FS2009
* Uebungsserie 5, Aufgaben 1-3
*
* @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