// A List of fixed size.

public class ArrayList implements List {

    private static int def = 100;
    private Keyed[] contents;
    private boolean[] bool;
    private int num;

    

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

        for (int i=0; i<capacity; i++) {
            bool[i] = true;
        }

        num = -1;
    }



    public ArrayList () {
        // Students: The following line calls the ArrayList constructor
        // above -- the one which takes an int argument.
        this(def);
    }



    public boolean add (Keyed o) throws ArrayListFullException {

        int j = -1;
        boolean flag = false;

        for (int i=contents.length-1; i >= 0; i--) {

            if (bool[i]) {
                if (num != i) {
                    j = i;
                }
            } else {
                 if (contents[i].getKey() == o.getKey()) {
                     flag = true;
                     break;
                 }
            }
        }  
       
        if (flag) {
              return false;
        } else {
            if (j == -1) {
                throw new ArrayListFullException();
            } else {
                contents[j] = o;
                bool[j] = false;
                return true;
            }
        }
    }



    private int find (double key) {

        for (int i=0; i<contents.length; i++) {
            if (! bool[i]) {
                if (contents[i].getKey() == key) { 
                    return i;
                }
            }
        }

        return -1;
    }



    public boolean contains (double key) {
     
        return (find(key) != -1);
    }



    public void delete (double key) {

        int position = find(key);
        bool[position] = true;
        num = position;
    }



    // Undelete the last thing that was deleted.  That is, put it back
    // into the list.  

    public boolean undelete () {

        if (num == -1) {
            return false;
        } else {
            bool[num] = false;
            num = -1;
            return true;
        }
    }



    public Keyed get (double key) {

        int position = find(key);
        return contents[position];
    }



    public int size () {

        int count=0;
        for (int i=0; i < contents.length; i++) {
            if (! bool[i]) {
                count++;
            }
        }
        return count;
    }



    public void compact () {

        Keyed[] new1 = new Keyed[size()];
        int n = 0;

        for (int i=0; i < contents.length; i++) {
            if (! bool[i]) {
                new1[n] = contents[i];
                n++;
            }
        }

        boolean[] new2 = new boolean[new1.length];
        for (int i=0; i < new1.length; i++) {
            new2[i] = false;
        }
        
        contents = new1;
        bool = new2;
        num = -1;

    }



    public void include (ArrayList other) throws ArrayListFullException {

        for (int i=0; i < other.contents.length; i++) {
            if (! other.bool[i]) {
                add(other.contents[i]);
            }
        }
        other.reset();
    }



    public void reset () {

        for (int i=0; i < contents.length; i++) {
            bool[i] = true;
        }
    }



    public String toString () {

        StringBuffer sb = new StringBuffer();
            for (int i=0; i < contents.length; i++) {
                if (! bool[i]) {
                    sb.append(contents[i] + "\n");
                }
            }
        return new String(sb);
    }
   
   
 
    // For testing only.

    private void peek () {

        for (int i=0; i<contents.length; i++) {
            System.out.print("     " + i + ": " + bool[i]);
            if (! bool[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);
    }
}