/ A List of fixed size.

public class ArrayList implements List {

    // The default capacity for an ArrayList.
    private static int defaultCapacity = 100;
    // The contents of my ArrayList.
    private Keyed[] contents;
    // Parallel to the contents array, indicating which items are marked as
    // deleted.
    private boolean[] marked;
    // The last item deleted from my ArrayList.
    private int last;

    /* Representation Invariant
     * ------------------------
     * - For 0 <= i < contents.length:
     *       If marked[i] is false, contents[i] is an element in the list.
     *       If marked[i] is true, contents[i] is either null, or is a
     *                           former element that has been deleted.  In
     *                           either case, the spot may be used for
     *                           insertion.

     * - contents.length == marked.length
     *
     * - If last == -1, 
     *       we haven't deleted anything since the last time we constructed,
     *       undeleted, or compacted (whichever came last).
     *   Otherwise, 
     *       last is the index of the last deleted item and marked[last] = true.
     */



    // Construct a new ArrayList with capacity spots to hold things.
    // Precondition: capacity >= 0.

    public ArrayList (int capacity) {
       
        contents = new Keyed[capacity];
        marked = new boolean[capacity];

        // Nothing is in the list yet, so treat each entry as if it has been
	// marked deleted.
        for (int i=0; i<capacity; i++) {
            marked[i] = true;
        }

        // Nothing has been deleted yet.
        last = -1;
    }



    // Construct a new ArrayList with the default capacity.

    public ArrayList () {
        this(defaultCapacity);
    }



    // Add o to my ArrayList, unless there is already an object with the same 
    // key in my list.  Return whether or not o was added.
    // Throws an ArrayListFullException if it doesn't fit.

    public boolean add (Keyed o) throws ArrayListFullException {

        // Where to insert o.  So far, we don't have a spot.
        int where = -1;
       
        // Whether an object with the same key is already in my list.
        boolean alreadyThere = false;

        // Go from end to beginning, looking for an available spot and
	// remember it in where.  
        for (int i=contents.length-1; i >= 0; i--) {

            if (marked[i]) {
                // The spot contains junk, so don't look at its contents for 
                // a matching key, or you may accidentally think o is already 
		// in the list.

                // If this spot is where the last-deleted item is, don't
                // reuse it; but if it's some other deleted item, we can.
                if (last != i) {
                    where = i;
                }
            } else {
                 // The ith spot is not marked -- i.e., it contains something
                 // that's still in the list.
                 if (contents[i].getKey() == o.getKey()) {
		     // This spot is not junk and its content matches the
		     // key for o.  Since o's key is already there, we don't 
		     // need to insert it, so stop looking for a place to
		     // insert.
                     alreadyThere = true;
                     break;
                 }
            }
        }  
	// Assertion: if alreadyThere is false, where is the *first* 
	// spot where we could insert o.
       
        if (alreadyThere) {
	    // o's key is already in the list.  Just return false to show
	    // we didn't insert it.
            return false;
        } else {
	    // o needs to be inserted.
            if (where == -1) {
	        // But there's no room for it.
                throw new ArrayListFullException();
            } else {
	        // There's room, and where tells us where to put it.
		// Do so (and indicate that o is NOT marked deleted.)
		// Return true to show we did insert it.
                contents[where] = o;
                marked[where] = false;
                return true;
            }
        }
    }



    // Returns the index of the object with key "key" in my list, or -1 if
    // there isn't one.

    private int find (double key) {

        // Look through my entire contents for a matching key.
        for (int i=0; i<contents.length; i++) {
            if (! marked[i]) {
                if (contents[i].getKey() == key) { 
		    // An entry that has not been deleted matches key.
		    // Return it's index.
                    return i;
                }
            }
        }

        // We failed to find a match, so return -1.
        return -1;
    }



    // Return whether or not my list contains an object with key "key".
    public boolean contains (double key) {
     
        return (find(key) != -1);
    }



    // Deletes the object with key "key" in my list.
    // Precondition: contains(key) must be true.

    public void delete (double key) {

        // Find where the matching object is, and mark it deleted.  Also,
	// remember that this was the last thing we deleted.
        int position = find(key);
        marked[position] = true;
        last = position;
    }



    // Undelete the last thing that was deleted, if possible.  That is, put 
    // it back into the list.  
    // Undeleting is possible iff there has been one ore more deletes since
    // we constructed, compacted, or undeleted (whichever happened last).
    // Returns whether or not the undelete was done.

    public boolean undelete () {

        if (last == -1) {
            // We have no record of a last thing deleted, so we can't undelete.
            return false;
        } else {
	    // Undelete the last thing deleted by saying it has not bee
	    // marked deleted.
            marked[last] = false;
	    // We don't know the previous thing deleted, so undeleted cannot
	    // be done again -- until something else has been deleted.
            last = -1;
            return true;
        }
    }



    // Returns the object in my list with key "key".
    // Precondition: contains(key) must be true.

    public Keyed get (double key) {

        // Find where that object is and then return it.
        int position = find(key);
        return contents[position];
    }



    // Returns the size of my list, that is, the number of things in me.

    public int size () {

	// Count up the number of unmarked things in my contents array.
        int count=0;
        for (int i=0; i < contents.length; i++) {
            if (! marked[i]) {
                count++;
            }
        }
        return count;
    }



    // Compress my entries into the smallest possible space.

    public void compact () {

        // The number of actual (undeleted) items in me is my true size.
	// Make a new contents array that big.
        Keyed[] newContents = new Keyed[size()];
	// Where to insert the next item into newContents.
        int nextInsert = 0;

        // Go through my contents and copy over every undeleted item into
	// newContents.
        for (int i=0; i < contents.length; i++) {
            if (! marked[i]) {
                newContents[nextInsert] = contents[i];
                nextInsert++;
            }
        }

        // Make a new marked array of the exact right size also, and set
	// everything to unmarked, since nothing has been deleted yet from
	// my compacted contents.
        boolean[] newMarked = new boolean[newContents.length];
        for (int i=0; i < newContents.length; i++) {
            newMarked[i] = false;
        }
        
	// Make the smaller me the real thing.
        contents = newContents;
        marked = newMarked;

	// No deleted items have been kept, so undeleting is impossible
	// (until something gets deleted).
        last = -1;

    }


    // Move every entry from other into my list.
    // Throws an ArrayListFullException if they don't all fit.

    public void include (ArrayList other) throws ArrayListFullException {

	// Go through other's contents and add every undeleted item to my
	// list.
        for (int i=0; i < other.contents.length; i++) {
            if (! other.marked[i]) {
                add(other.contents[i]);
            }
        }
	// Take all of other's entries out of other.  They're all mine now.
        other.reset();
    }



    // Make me empty.

    public void reset () {

	// Mark every entry deleted.
        for (int i=0; i < contents.length; i++) {
            marked[i] = true;
        }
    }



    // Return a string representing my contents.

    public String toString () {

        StringBuffer sb = new StringBuffer();
	    // Go through my contents and append all undeleted entries to
	    // the string we'll return.
            for (int i=0; i < contents.length; i++) {
                if (! marked[i]) {
                    sb.append(contents[i] + "\n");
                }
            }
        return new String(sb);
    }
   
   
 
    // For testing only.
    // Prints out what's in every spot in in my contents and marked arrays.

    private void peek () {

        for (int i=0; i<contents.length; i++) {
            System.out.print("     " + i + ": " + marked[i]);
            if (! marked[i]) {
                System.out.println(" -->" + contents[i]);
            } else {
                System.out.println("");
            }
        }
    } 



    // A very short driver that shows a bit about how you can use an
    // ArrayList.  You should replace this with a driver that does thorough
    // testing.

    public static void main (String [] args) throws ArrayListFullException {

        ArrayList l = new ArrayList(25);
        CalEntry c1 = new CalEntry(98, 6, 1, 1137, "Baby born!");
        l.add(c1);
        // For question 1, trace everything up to this point.

        
        CalEntry c2 = new CalEntry(00, 9, 11, 1000, "Term starts");
        l.add(c2);
        CalEntry c3 = new CalEntry(00, 9, 11, 1000, "First 148 lecture");
        l.add(c3);
        System.out.println("The list contains:\n" + l);
        // Delete the entry with c2's key.
        l.delete(c2.getKey());
        // Change the text of the entry with c1's key.  Change it to
        // "William born!".
        ((CalEntry)(l.get(c1.getKey()))).setText("William born!");
        System.out.println("The list now contains:\n" + l);

    }
}