////////////////////////////////////////////////////////////////
//
// Lab7
//
////////////////////////////////////////////////////////////////

public class Lab7 {

    public static void main (String[] args) {
	new IStack0Test (new ListStack0()).go();
	new IStack0Test (new ArrayStack0()).go();
	new IStackTest (new ListStack()).go();
	new IStackTest (new ArrayStack()).go();
    }

}

////////////////////////////////////////////////////////////////
//
// ISelector
//
////////////////////////////////////////////////////////////////

interface ISelector {
    boolean select (Object x);   // do we want the given object?
}

////////////////////////////////////////////////////////////////
//
// IComparator
//
// This is essentially the same as java.util.Comparator,
// which ProfessorJ probably doesn't support.
//
////////////////////////////////////////////////////////////////

interface IComparator {

    // Returns a negative int if x is regarded as less than y,
    // zero if x is regarded as equal to y,
    // a positive int if x is regarded as greater than y.

    int compare (Object x, Object y);
}

////////////////////////////////////////////////////////////////
//
// IRange
//
////////////////////////////////////////////////////////////////

interface IRange {

    // Do any elements remain to be generated?
    boolean hasMore(); 

    // Return the current element being generated.
    Object current(); 

    // Skip the current element and go on to the remaining ones, if any.
    void next(); 

}

////////////////////////////////////////////////////////////////
//
// AList - reusable classes for representing lists of objects
//
// We have been developing these classes throughout the semester.
//
////////////////////////////////////////////////////////////////

abstract class AList {

    // Is this list empty?
    public abstract boolean isEmpty ();

    // Assuming this list is not empty, what is its first element?
    public abstract Object first ();

    // Assuming this list is not empty, what are its remaining elements?
    public abstract AList rest ();

    // Returns an IRange that generates the elements of this list in order.
    public IRange iterator () {
        return new ListRanger (this);
    }

    // How many elements are in this list?
    public int length () {
        if (this.isEmpty())
	    return 0;
	else return 1 + this.rest().length();
    }

    // Return the elements of this list as a list in reverse order.
    public AList reverse () {
	IRange ir = this.iterator();
	AList result = new MTList();
	for ( ; ir.hasMore(); ir.next()) {
	    result = new ConsList (ir.current(), result);
	}
	return result;
    }

    // Does this list contain the given object?
    public boolean contains (Object x) {
	boolean result = false;
	for (IRange ir = this.iterator(); ir.hasMore(); ir.next()) {
	    if (ir.current().equals (x))
		result = true;
	}
	return result;
    }

    // Is this list equal to that one?
    public boolean equals (Object that) {
        IRange ir1 = this.iterator();
        IRange ir2 = ((AList) that).iterator();
	boolean equalSoFar = true;

	for ( ; equalSoFar && ir1.hasMore() && ir2.hasMore(); ) {
	    if (ir1.current() != ir2.current())
		equalSoFar = false;
	    ir1.next();
	    ir2.next();
	}

	// The loop terminated because at least one of these is true:
	// -- equalSoFar is false (we found unequal elements)
	// -- ir1 has no more elements to generate
	// -- ir2 has no more elements to generaet

	if (ir1.hasMore() != ir2.hasMore())
	    return false;
	else return equalSoFar;
    }

    // Return the selected elements of this list.
    public abstract AList filter (ISelector is);

    // Return the elements of this list in the specified order.
    public abstract AList sort (IComparator ic);

    // Insert the given object in front of the first element of
    // this list that is larger than it according to the IComparator.
    abstract AList insert (Object x, IComparator ic);
}

class MTList extends AList {
    public MTList () { }

    public boolean isEmpty () { return true; }

    public Object first () { throw new RuntimeException (ERRORMSG); }
    public AList rest () { throw new RuntimeException (ERRORMSG); }

    // This is how constants are declared in Java.
    static final String ERRORMSG
	= "The first and rest methods aren't defined on empty lists.";

    public AList filter (ISelector is) { return this; }

    public AList sort (IComparator ic) { return this; }

    AList insert (Object x, IComparator ic) {
        return new ConsList (x, this);
    }
}

class ConsList extends AList {
    Object fst;    // the first element of this list
    AList rst;     // the rest of this list

    public ConsList (Object fst, AList rst) {
        this.fst = fst;
        this.rst = rst;
    }

    public boolean isEmpty () { return false; }

    public Object first () { return this.fst; }
    public AList rest () { return this.rst; }

    public AList filter (ISelector is) {
	if (is.select (this.fst))
	    return new ConsList (this.fst, this.rst.filter (is));
	else return this.rst.filter(is);
    }

    public AList sort (IComparator ic) {
	return this.rst.sort (ic).insert (this.fst, ic);
    }

    AList insert (Object x, IComparator ic) {
	if (ic.compare (x, this.fst) <= 0)
	    return new ConsList (x, this);
	else return new ConsList (this.fst, this.rst.insert (x, ic));
    }
}

class ListRanger implements IRange {

    AList contents;  // the list of elements that remain to be generated

    ListRanger (AList contents) {
	this.contents = contents;
    }

    public boolean hasMore () {
        return ! this.contents.isEmpty();
    }

    public Object current () {
	return this.contents.first();
    }

    public void next () {
        this.contents = this.contents.rest();
    }

}

////////////////////////////////////////////////////////////////
//
// tests for AList and ListRanger
//
////////////////////////////////////////////////////////////////

class TestLists implements Testable {

    String s1 = "one";
    String s2 = "two";
    String s3 = "three";
    String s4 = "four";
    String s5 = "five";

    TestLists () { }

    void go () {
        Tester tester = new Tester ();
        tester.runTests (this);
    }

    public void tests (Tester t) {
        AList mt1 = new MTList();
	AList mt2 = new MTList();

	AList l1 = new ConsList (s1, mt1);
	AList l2 = new ConsList (s2, mt2);

	AList lst5 = new ConsList (s5, mt2);
	AList lst4 = new ConsList (s4, lst5);
	AList lst3 = new ConsList (s3, lst4);
	AList lst2 = new ConsList (s2, lst3);
	AList lst1 = new ConsList (s1, lst2);

	AList list5 = new ConsList (s5, mt1);
	AList list4 = new ConsList (s4, list5);
	AList list3 = new ConsList (s4, list4);  // note difference!
	AList list2 = new ConsList (s2, list3);
	AList list1 = new ConsList (s1, list2);

	// s1 through s5 in alphabetical order
	AList alpha = new ConsList (s2, mt1);
	alpha = new ConsList (s3, alpha);
	alpha = new ConsList (s1, alpha);
	alpha = new ConsList (s4, alpha);
	alpha = new ConsList (s5, alpha);

	t.test (mt1.isEmpty(), true);
	t.test (mt2.isEmpty(), true);
	t.test (l1.isEmpty(), false);
	t.test (lst1.isEmpty(), false);

	t.test (l1.first(), s1);
	t.test (lst2.first(), s2);

	t.test (l1.rest().isEmpty(), true);
	t.test (lst4.rest().isEmpty(), false);
	t.test (lst4.rest().first(), s5);

	IRange ir0 = mt2.iterator();
	t.test (ir0.hasMore(), false);

	IRange ir1 = lst1.iterator();
	t.test (ir1.hasMore(), true);
	t.test (ir1.current(), s1);
	t.test (ir1.current(), s1);
	ir1.next();
	t.test (ir1.hasMore(), true);
	t.test (ir1.current(), s2);
	ir1.next();
	t.test (ir1.hasMore(), true);
	t.test (ir1.current(), s3);
	ir1.next();
	t.test (ir1.hasMore(), true);
	t.test (ir1.current(), s4);
	ir1.next();
	t.test (ir1.hasMore(), true);
	t.test (ir1.current(), s5);
	t.test (ir1.current(), s5);
	ir1.next();
	t.test (ir1.hasMore(), false);

	t.test (mt1.length(), 0);
	t.test (lst5.length(), 1);
	t.test (lst4.length(), 2);
	t.test (lst1.length(), 5);

	t.test (mt1.equals (mt2), true);
	t.test (l1.equals (l1), true);
	t.test (l1.equals (l2), false);
	t.test (lst4.equals (list4), true);
	t.test (lst3.equals (list3), false);
	t.test (lst1.equals (list1), false);
	t.test (list1.equals (list1), true);

	t.test (list1.rest().equals (list2), true);
	t.test (list3.rest().equals (lst4), true);

	t.test (mt1.reverse().equals (mt2), true);
	t.test (l1.reverse().first(), s1);
	t.test (l1.reverse().length(), 1);
	t.test (lst1.reverse().first(), s5);
	t.test (lst1.reverse().reverse().equals (lst1), true);

	t.test (mt1.contains (s1), false);
	t.test (l1.contains (s1), true);
	t.test (l2.contains (s1), false);
	t.test (lst1.contains (s1), true);
	t.test (lst1.contains (s5), true);
	t.test (list1.contains (s3), false);

	ISelector is1 = new ISelector () {
		public boolean select (Object x) { return true; }
	    };
	ISelector is2 = new ISelector () {
		public boolean select (Object x) { return false; }
	    };
	ISelector is3 = new ISelector () {
		public boolean select (Object x) {
		    return ((String) x).charAt (0) == 'f';
		}
	    };
	t.test (mt1.filter (is1).isEmpty(), true);
	t.test (lst1.filter (is1).equals (lst1), true);
	t.test (lst1.filter (is2).equals (mt1), true);
	t.test (lst1.filter (is3).length(), 2);
	t.test (lst1.filter (is3).first(), s4);
	t.test (lst1.filter (is3).rest().first(), s5);

	IComparator ic1 = new IComparator () {
		public int compare (Object x, Object y) {
		    return ((String) x).compareTo (y);
		}
	    };
	IComparator ic2 = new IComparator () {
		public int compare (Object x, Object y) {
		    return ((String) y).compareTo (x);
		}
	    };
	t.test (mt1.sort (ic1).isEmpty(), true);
	t.test (lst1.sort (ic1).length(), 5);
	t.test (lst1.sort (ic1).equals (alpha), true);
	t.test (lst1.sort (ic2).equals (alpha.reverse()), true);
    }
}

////////////////////////////////////////////////////////////////
//
// Tester
//
////////////////////////////////////////////////////////////////

interface Testable {
    void tests (Tester t);
}

class Tester {

    int n;
    int errors;

    Tester () { this.n = 1; this.errors = 0; }

    void runTests (Testable f) {
	n = 1;
	try {
	    f.tests (this);
	}
	catch (Throwable e) {
	    System.out.println ("Threw exception during test " + n);
	    System.out.println (e);
	}
	finally {
	    done();
	}
    }

    void test (boolean b1, boolean b2) {
	test (b1 == b2);
    }

    void test (int i, int j) {
	test (i == j);
    }

    void test (Object s1, String s2) {
	test (s2.equals (s1));
    }

    void test (boolean b) {
	if (! b) {
	    System.out.println ("***** Failed test " + n + " *****");
	    errors = errors + 1;
	}
	n = n + 1;
    }

    void done () {
	if (errors > 0)
	    System.out.print ("Failed " + errors + " out of ");
        else
	    System.out.print ("Passed all ");
	System.out.println (n + " tests.");
    }

}

////////////////////////////////////////////////////////////////
//
// ATune
//
////////////////////////////////////////////////////////////////

// An ATune represents an audio recording of some kind.

abstract class ATune {

    String title;          // the name of the recording
    String artist;         // the perpetrator of the recording
    int[] bits;            // the content of the recording

}

// A MIDI is an ATune in Musical Instrument Digital Interface format.
// See http://en.wikipedia.org/wiki/MIDI_file for more details.
//
// Example:
// int[] bits1 = new int[914] {1297377380, 6, 1, 67128660, 1919614976, ...};
// ATune theLeaRig = new MIDI ("The Lea Rig", "Robert Burns", bits1);

class MIDI extends ATune {

    MIDI (String title, String artist, int[] bits) {
        this.title = title;
        this.artist = artist;
        this.bits = bits;
    }

}

// A MP3 is an ATune in MPEG Audio Layer 3 format.
// See http://en.wikipedia.org/wiki/MP3 for more details.
//
// Example:
// int[] bits2 = new int[729612] {1229206275, 0, 24532048, 1160839168 ...};
// ATune elegie = new MP3 ("Elegie", "Jules Massenet", bits2);

class MP3 extends ATune {

    MP3 (String title, String artist, int[] bits) {
        this.title = title;
        this.artist = artist;
        this.bits = bits;
    }

}

// A WAV is an ATune in WAVEform audio format.  For more details, see
// http://www.wordiq.com/cgi-bin/knowledge/lookup.cgi?title=WAV
//
// Example:
// int[] bits3 = new int [9746111] {1380533830, 4107948546, 1463899717, ...};
// ATune storekeeper = new WAV ("Storekeeper", "James McMurtry", bits3);

class WAV extends ATune {

    WAV (String title, String artist, int[] bits) {
        this.title = title;
        this.artist = artist;
        this.bits = bits;
    }

}

////////////////////////////////////////////////////////////////
//
// IStack0
//
////////////////////////////////////////////////////////////////

// An IStack0 represents a mutable stack of objects.

interface IStack0 {

    // Is this stack empty?
    boolean isEmpty ();

    // Pushes the given object onto this stack.
    void push (Object x);

    // Pops the topmost object off this stack and returns it.
    Object pop ();
}

// An IStack0Test tests an implementation of IStack0.
//
// Examples:
// new IStack0Test (new ListStack0()).go();
// new IStack0Test (new ArrayStack0()).go();

class IStack0Test implements Testable {

    IStack0 stk;  // the IStack0 to be tested

    IStack0Test (IStack0 stk) { this.stk = stk; }

    // The IStack0 to be tested should be empty when go is called.

    void go () {
	Tester tester = new Tester ();
	tester.runTests (this);
    }

    String s1 = "one";
    String s2 = "two";
    String s3 = "three";
    String s4 = "four";
    String s5 = "five";
    int big = 1000;

    public void tests (Tester t) {
	t.test (stk.isEmpty(), true);
	stk.push (s1);
	t.test (stk.isEmpty(), false);
	t.test (stk.pop(), s1);
	t.test (stk.isEmpty(), true);
	stk.push (s1);
	stk.push (s2);
	stk.push (s3);
	t.test (stk.pop(), s3);
	t.test (stk.pop(), s2);
	t.test (stk.pop(), s1);
	t.test (stk.isEmpty(), true);
	stk.push (s5);
	stk.push (s4);
	for (int i = 0; i < big; i = i + 1)
	    stk.push (s1);
	for (int i = 0; i < big; i = i + 1) {
	    t.test (stk.isEmpty(), false);
	    t.test (stk.pop(), s1);
	}
	t.test (stk.isEmpty(), false);
	t.test (stk.pop(), s4);
	t.test (stk.isEmpty(), false);
	t.test (stk.pop(), s5);
	t.test (stk.isEmpty(), true);
    }
}

////////////////////////////////////////////////////////////////
//
// Two different implementations of IStack0
//
////////////////////////////////////////////////////////////////

// A ListStack0 represents its state as an AList.
//
// Example:
// IStack0 s0 = new ListStack0();

class ListStack0 implements IStack0 {

    // state.first() is the topmost element.
    AList state;

    ListStack0 () { this.state = new MTList(); }

    public boolean isEmpty () {
        return this.state.isEmpty();
    }

    public void push (Object x) {
	this.state = new ConsList (x, this.state);
    }

    public Object pop () {
	Object x = this.state.first();
	this.state = this.state.rest();
	return x;
    }

}


// An ArrayStack0 represents its state as an array.
//
// Example:
// IStack0 s0 = new ArrayStack0();

class ArrayStack0 implements IStack0 {

    // the number of elements in the stack
    int count;

    // state [count-1] is the topmost element
    Object[] state;

    // Constants.

    // the initial size of the state array
    static final int INITIAL_CAPACITY = 5;

    // the expansion factor to use when the state overflows
    static final int EXPANSION_FACTOR = 2;

    ArrayStack0 () {
	this.count = 0;
	this.state = new Object[INITIAL_CAPACITY];
    }

    public boolean isEmpty () {
        return this.count == 0;
    }

    public void push (Object x) {
	if (count >= state.length)
	    this.expandCapacity();
	this.state[this.count] = x;
	this.count = this.count + 1;
    }

    public Object pop () {
	Object x = this.state[this.count-1];
	this.count = this.count - 1;
	return x;
    }

    // Increases the capacity of this stack's state array.

    void expandCapacity () {
	Object[] oldarray = this.state;
	this.state = new Object [EXPANSION_FACTOR * this.count];
	for (int i = 0; i < this.count; i = i + 1)
	    this.state[i] = oldarray[i];
    }

}

////////////////////////////////////////////////////////////////
//
// IStack
//
////////////////////////////////////////////////////////////////

// An IStack represents a mutable stack of objects.

interface IStack extends IStack0 {

    // Returns an IRange that generates the elements of this stack,
    // in order beginning with the topmost.
    IRange iterator();
}

// An IStackTest tests an implementation of IStack.
//
// Examples:
// new IStackTest (new ListStack()).go();
// new IStackTest (new ArrayStack()).go();

class IStackTest extends IStack0Test implements Testable {

    IStackTest (IStack stk) { super (stk); }

    // The IStack to be tested should be empty when go is called.

    void go () {
	Tester tester = new Tester ();
	tester.runTests (this);
    }

    public void tests (Tester t) {
	super.tests(t);
	stk.push (s5);
	stk.push (s4);
	for (int i = 0; i < big; i = i + 1)
	    stk.push (s1);
	IRange ir = ((IStack) stk).iterator();
	for (int i = 0; i < big; i = i + 1) {
	    t.test (ir.hasMore());
	    t.test (ir.current(), s1);
	    ir.next();
	}
	t.test (ir.hasMore(), true);
	t.test (ir.current(), s4);
	ir.next();
	t.test (ir.hasMore(), true);
	t.test (ir.current(), s5);
	ir.next();
	t.test (ir.hasMore(), false);
    }
}

////////////////////////////////////////////////////////////////
//
// Two different implementations of IStack0
//
////////////////////////////////////////////////////////////////

// A ListStack represents its state as an AList.
//
// Example:
// IStack stk = new ListStack();

class ListStack extends ListStack0 implements IStack {

    ListStack () { this.state = new MTList(); }

    public IRange iterator () {
	return new ListRanger (this.state);
    }
}


// An ArrayStack represents its state as an array.
//
// Example:
// IStack stk = new ArrayStack();

class ArrayStack extends ArrayStack0 implements IStack {

    ArrayStack () {
	this.count = 0;
	this.state = new Object[INITIAL_CAPACITY];
    }

    public IRange iterator () {
	return new ReverseArrayRange (this.trimmedState());
    }

    // Returns a trimmed copy of this stack's state array.

    Object[] trimmedState () {
	Object[] newarray = new Object [this.count];
	for (int i = 0; i < this.count; i = i + 1)
	    newarray[i] = this.state[i];
	return newarray;
    }
}

// A ReverseArrayRange generates the elements of an array in reverse order.

class ReverseArrayRange implements IRange {

    Object[] things;       // the objects to be generated
    int count;             // how many objects remain to be generated

    ReverseArrayRange (Object[] things) {
	this.things = things;
	this.count = things.length;
    }

    public boolean hasMore() { return this.count > 0; }

    public Object current() { return this.things [count - 1]; }

    public void next() { this.count = this.count - 1; }

}