// ----
// List
// ----
public final class List
{ // immutable
private final long first;
private final List rest;
/**
* O(1) in space
* O(1) in time
* preconditions: none
* Add a new List to the end
* @param first a long
* @return a list of long of length one
*/
public List(long first)
{ this(first, null);}
/**
* O(1) in space
* O(1) in time
* preconditions: none
* Add a new List to the end with value 'first'
* @param first a long
* @param rest a list
* @return a list of long of length one more than 'rest'
*/
public List(long first, List rest)
{ this.first = first;
this.rest = rest;
}
/**
* O(1) in space
* O(1) in time
* Return the value stored in a List
* @param x a list
* @return the first element of the list
*/
public static long first(List x)
{ return x.first; }
/**
* O(1) in space
* O(1) in time
* Return the List that follows from another
* @param x a list
* @return the rest of the list
*/
public static List rest(List x)
{ return x.rest;}
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Check to see if 2 Lists are equal
* @param x a list
* @param y a list
* @return true if 'x' and 'y' are equal, false otherwise
*/
public static boolean equal(List x, List y)
{
// base cases
if (x == y) // do x and y point to the same List?
return true;
if ((x == null) || (y == null)) // if 1 is null but x != y, then they are not equal
return false;
if (first(x) != first(y)) // if the value of the current node in x does not equal the value of
return false; // the current node in y, then they are not equal
return equal( rest(x), rest(y) ); // go to the next node in the lists and repeat
}
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Return the length of a List
* @param x a list
* @return the length of the list
*/
public static int length(List x)
{
// base case
if (x == null) // if x is null, then it doesnt have a length
return 0;
return 1 + length( rest(x) ); // go to the next node and keep track of how many times you recursed
}
// ---
// sum
// ---
/**
* O(n) in space
* O(n) in time
* preconditions: x != null
* Go through the List and compute the sum of the value in all the nodes
* @param x A List that will be traversed to get the sum
* @return the sum of the list
*/
public static long sum(List x)
{
assert (x != null): "Violation of precondition: List.sum()";
// base condition
if( rest(x) == null )
return first(x);
// recursively add the current value in the node with the value of the next node
return first(x) + sum( rest(x) );
}
// -------
// product
// -------
/**
* O(n) in space
* O(n) in time
* preconditions: x != null
* Go through the List and compute the product of the value in all the nodes
* @param x a List to traverse
* @return the product of the list
*/
public static long product(List x)
{
assert (x != null): "Violation of precondition: List.product()";
// base case
if( rest(x) == null ) // we must look ahead. Keep multiplying the values while we dont hit a null
return first(x);
return first(x) * product( rest(x) ); // return this value multiplied with the values of the successors
}
// ---
// max
// ---
/**
* O(n) in space
* O(n) in time
* preconditions: x != null
* Traverse through the list and compute the maximum value
* @param x a List to traverse
* @return the maximum value of the list
*/
public static long max(List x)
{
assert (x != null): "Violation of precondition: List.max()";
// base case
if(rest(x) == null) // keep returning the value of the current node while we dont hit a null
return first(x);
long tmp = max( rest(x) ); // store the maximum of what we have computed so far here
return tmp > first(x) ? tmp: first(x); // return only the maximum value
}
// ---
// min
// ---
/**
* O(n) in space
* O(n) in time
* preconditions: x != null
* Traverse through the list and compute the minimum value
* @param x a List to traverse
* @return the minimum value of the list
*/
public static long min(List x)
{
assert (x != null): "Violation of precondition: List.min()";
// base case
if(rest(x) == null) // keep returning the value of the current node while we dont hit a null
return first(x);
long tmp = min( rest(x) ); // store the minimum of what we have computed so far here
return first(x) < tmp? first(x): tmp; // return only the minimum value
}
// -------
// reverse
// -------
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Return a List such that its entries are in reverse order of the passed List
* @param x a list to reverse
* @return a List in reverse order
*/
public static List reverse(List x)
{
// if x==null, then there isn't anything to reverse
if( x == null )
return null;
// if x has only 1 value, then just return x
if( rest(x) == null )
return x;
// recurse through the list and store
return reverse( rest(x), new List( first(x) ));
}
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Store the reverse of a List into another
* @param x a List to reverse
* @param result a List holding the reversed x
* @return a List
*/
private static List reverse(List x, List result) // helper method!!
{
// base case, if x is null then we just return result
if( x == null)
return result;
// else, go to the next List in x and add a new List to result
return reverse( rest(x), new List( first(x), result));
}
// ------
// member
// ------
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Traverse through a List and determine whether it contains 'l'
* @param l a long value to search for
* @param x a list to traverse
* @return true if l is in x, false otherwise
*/
public static boolean member(long l, List x)
{
// base case
if(x == null) // if x is null, then l cannot possibly be in x
return false;
if( first(x) == l ) // have we found l?
return true;
return member(l, rest(x) ); // check the next node
}
// -----------
// concatenate
// -----------
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Create a List that is the union of x and y
* @param x a list that will be joined with y
* @param y a list to append to x
* @return a list that is the concatentation of x and y
*/
public static List concatenate(List x, List y)
{
if(x == null) // if x==null, then we only need to return y
return y;
if(y == null) // if y==null, then we only need to return x
return x;
// go through List x until we hit a null, keep creating a new list and return it to concat with x
return new List( first(x) , concatenate( rest(x) , y) );
}
// ------
// insert
// ------
/**
* O(n) in space
* O(n^2) in time
* preconditions: x is sorted
* Insert v into a sort List x
* @param v the element to insert
* @param x the List object to insert v into
* @return a List object with v inserted into x at the right place in the sorted List x
* @see concatenate()
*/
public static List insert(long v, List x)
{
// if x is null, return a List of v
if(x == null)
return new List(v);
// if v is <= than the first element in x, then simply create a new List
// with v as the front value with x after
if( v <= first(x))
return new List(v, x);
// recurse through the list and concatenate until we can place v some where
// after that, concatenate everything back
return concatenate(new List(first(x)), insert(v, rest(x)) );
}
// -------------
// insertionSort
// -------------
/**
* O(n^2) in space
* O(n^2) in time
* preconditions: none
* Return a List in sorted order
* @param x a list that will be sorted
* @return the list x in sorted order
* @see insert()
*/
public static List insertionSort(List x)
{ // if x is null, return null, else recursively sort x and return it
return (x == null)? null: insert(first(x), insertionSort( rest(x) )); // isnt this nice :) ?
}
// ---------
// partition
// ---------
/**
* O(n) in space
* O(n) in time
* preconditions: x != null
* Seperate all elements less-equal and greater-than into a Pair object
* @param v the pivot for which to seperate the elements
* @param x the List containing the elements to partition
* @return a pair of lists, elements <= 'v', and elements >= 'v'
* @see concatenate()
*/
public static Pair partition(long v, List x)
{ return partition(v, x, null, null); // partition the List and return a Pair object
}
/**
* Helper method
* O(n) in space
* O(n) in time
* preconditions: x != null
* Do the actual partitioning for partition()
* @param v the pivot
* @param x the List containing the elements to partition
* @param fst A List to store all elements less-equal to the pivot
* @param snd A List to store all elements greater-than to the pivot
* @return A Pair containing fst and snd
* @see concatenate()
*/
private static Pair partition(long v, List x, List fst, List snd)
{
// base case, if we hit the end of x, create a Pair object with fst and snd, and return it
if( x == null)
return new Pair(fst, snd);
// determine whether to put in fst
if(first(x) < v)
fst = concatenate(fst, new List( first(x) ));
else // or in snd
snd = concatenate(snd, new List( first(x) ));
// call partition on the next element
return partition(v, rest(x), fst, snd);
}
// ---------
// quicksort
// ---------
/**
* O(logN) in space
* O(NlogN) in time
* Sort a List using the quicksort algorithm
* @param x a List to sort
* @return a List x in sorted order
* @see partition(), concatenate()
*/
public static List quicksort(List x)
{
// base case: if x is null or x only has value in it, ten we just return x as is
if(x == null)
return x;
if(rest(x) == null )
return new List( first(x) );
final long pivot = first(x); // step 1: choose a pivot
Pair p = partition(pivot, x); // step 2: partition the List
//System.out.println(toString(p.first) + " | " + toString(p.second));
return concatenate( quicksort(p.first), new List(first(p.second), quicksort( rest(p.second) ))); // step 3: bring the two partitions into one
}
// -----
// split
// -----
/**
* O(n) in space
* O(n) in time
* preconditions: none
* Split a List into 2 independent Lists to be stored in a Pair
* @param x a List to split
* @return a Pair object that will be contain the splitted List
*/
public static Pair split(List x)
{
Pair returnPair = new Pair(null, null); // create the Pair that will contain the splitted list
if(x != null) // if x==null then we dont do anything but return an empty Pair
returnPair.first = split(0, length(x) / 2, x, returnPair); // else we store everything that is in x, until its halfway point, into our
// returnPair object
return returnPair;
}
/**
* O(n) in space
* O(n) in time
* preconditions: x != null and pair != null
* @param location where in the list are we to start splitting
* @param length how far we want to split
* @param x the List to split
* @param pair We to return the first and second Lists that were splitted from x
* @return a Pair object containing the 2 List objects splitted from x
*/
private static List split(int location, int length, List x, Pair pair)
{
assert (x != null && pair != null): "Violation of precondition: List.split()";
// if there arent anymore List objects, then we know that we have reached the end
if( rest(x) == null) {
pair.second = new List( first(x) );
return null;
}
// if we hit the end of where we want to split the List, then we assign everything after that to the 2nd List in our Pair object
if(location == length) {
pair.second = new List( first(x), rest(x) );
return null;
}
// create a new List such that it keep splitting x and a location++ to the one we are on now
return new List( first(x), split( location + 1, length, rest(x), pair));
}
// -----
// merge
// -----
/**
* O(n) in space
* O(n) in time
* preconditions: x and y are sorted
* Return a List that is the result of merging 2 sorted Lists into 1
* @param x a List that will be merged with another List
* @param y the other List to be merged
* @return the merge of 'x' and 'y'
*/
public static List merge(List x, List y)
{ return merge(x, y, null); // merge x and y
}
/**
* O(n) in space
* O(n) in time
* preconditions: x and y are sorted
* Helper method for the merge() method
* @param x a List that will be merged with another List
* @param y the other List to be merged
* @param storage A list to store the sorted merge of x and y
* @return the merge of 'x' and 'y'
* @see concatenate()
*/
private static List merge(List x, List y, List storage)
{
if(x == null) { // if x is null, then we just concat what we have so far with y and return it
storage = concatenate(storage, y);
return storage;
}
if(y == null) { // // if y is null, then we just concat what we have so far with x and return it
storage = concatenate(storage, x);
return storage;
}
if(first(x) <= first(y)) { // decide who appears first in the merged List
storage = concatenate(storage, new List(first(x)));
return merge(rest(x), y, storage); // keep reading from x
}
// else, we store the other way around
storage = concatenate(storage, new List(first(y)));
return merge(x, rest(y), storage); // and keep reading from y
}
// ---------
// mergeSort
// ---------
/**
* O(n) in space
* O(NlogN) in time
* preconditions: x and y are sorted
* Return a sorted List
* @param x a List to sort on
* @return x in sorted order
* @see split(), merge()
*/
public static List mergeSort(List x)
{
// base case: if x or the the next List in x is null, then return x
if( x == null || rest(x) == null)
return x;
Pair p = split(x); // divide x into 2 sublists
List a = mergeSort(p.first); // divide the 1st sublist
List b = mergeSort(p.second); // divide the 2nd sublist
return merge( a, b ); // merge them all together
}
// --------
// toString
// --------
/**
* O(n) in space
* O(n) in time
* precondition: none
* Return the contents of a List as a String
* @param x a List
* @return a String representation of the list
*/
public static String toString(List x)
{ return "(" + toString2(x) + ")";}
private static String toString2(List x)
{
if (x == null)
return "";
if (rest(x) == null)
return first(x) + "";
return first(x) + ", " + toString2(rest(x));
}
}
// ----
// Pair
// ----
final class Pair
{
public List first;
public List second;
public Pair(List first, List second)
{
this.first = first;
this.second = second;
}
public boolean equals(Object that)
{ // const
if (this == that)
return true;
if (!(that instanceof Pair))
return false;
final Pair x = (Pair) that;
return List.equal(first, x.first) && List.equal(second, x.second);
}
}