// Copyright (c) 1996-2002 Brian D. Carlstrom

package bdc.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
    A DynamicArray is like ArrayList except that is exposes the underlying
    array.  DynamicArray is abstract so that clients can supply a method to
    allocate the array to be of a particular type.  This gets back some of
    the runtime type checking that ArrayList loses, and allows more concise
    enumeration.  Here is a sample concrete subclass:</P>
    
    <PRE>
        public class IntegerArray extends DynamicArray
        {
            public Object[] alloc (int size)
            {
                return new Integer[ size ];
            }

            public final Integer[] array ()
            {
                return (Integer[]) array;
            }
        }
    </PRE>
   
    <P>A use of IntegerArray might look like this:</P>

    <PRE>
        IntegerArray ia = new IntegerArray();
        ia.addElement (Constants.getInteger(1));
        ia.addElement (Constants.getInteger(2));

        Integer[] a = ia.array();
        for (int k = 0; k < v.inUse; k++) {
            doIntegerOp(a[k]);
        }
    </PRE>
    
    <P>Using ArrayList, each element access in the loop would entail a
    procedure call and a cast.</P>
*/

abstract public class DynamicArray
{
    private static final int GrowIncrement = 4;
    private static final int InitialSize = 4;

    /**
        The storage array.
        This member should be accessed directly for reading only
    */
    public Object[] array = null;

    /**
        The number of members that are currently used.  This is
        the logical length of the array.
        This member should be accessed directly only for reading.
    */
    public int inUse = 0;

    /**
        Create a DynamicArray with a default storage size.
    */
    public DynamicArray ()
    {
        this(InitialSize);
    }

    /**
        Create a new DynamicArray
        @param size The starting size of the storage array.
        A size of -1 creates an instance with no array allocated.
    */
    public DynamicArray (int size)
    {
        if (size != -1) {
            array = alloc(size);
        }
    }

    /**
        Replace the storage array.

        The new storage array has to be the right type or the next call to
        array() will cause a ClassCastException.  Must override in
        subclass if using the local array hack to get around the
        Netscape varifier bug involving casting of Object arrays.
        @param array The new array to use as storage
    */
    public void setArray (Object[] array)
    {
        this.array = array;
        this.inUse = array.length;
    }

    /**
        Change the size of the storage.
        The size cannot be decreased below the number of elements
        that are currently being used.
        @param size The new requested size
    */
    void setCapacity (int size)
    {
        if (size < inUse) {
                // don't slice out existing members
            size = inUse;
        }
        Object[] newArray = alloc(size);
        System.arraycopy(array, 0, newArray, 0, inUse);
        array = newArray;
    }

    /**
        Make sure there is room for additional elements.
        @param want The number of elements we want to have space for
        
    */
    public void makeRoomFor (int want)
    {
        int avail = array.length - inUse;

        if (want < avail) {
            return;
        }

        int proposedIncrease = array.length;

        if (want > avail + proposedIncrease) {
            setCapacity(array.length + want);
        }
        else {
            setCapacity(array.length + proposedIncrease);
        }
    }

    /**
        Add an element to the array.
        @param o The element to add

    */
    public void addElement (Object o)
    {
        if (inUse == array.length) {
            makeRoomFor(1);
        }
        array[inUse++] = o;
    }

    /**
        Add an element to the array, if it isn't in the array
        @param o The element to add.  If o is already in the array
        then it is not added.

    */
    public void addElementIfAbsent (Object o)
    {
        if (contains(o)) {
            return;
        }
        addElement(o);
    }

    /**
        Add an element to the array, if it isn't in the array
        @param o The element to add.  If o is already in the array
        then it is not added.  The == operator is used to
        compare elements.

    */
    public void addIdentical (Object x)
    {
        if (! containsIdentical(x)) {
            addElement(x);
        }
    }

    /**
        Add all the elements from another array.
        @param that The array that we will copy from

    */
    public void addElements (DynamicArray that)
    {
        if ((this.inUse + that.inUse) >= this.array.length) {
            makeRoomFor(that.inUse);
        }

        System.arraycopy(that.array, 0, this.array, inUse, that.inUse);
        this.inUse += that.inUse;
    }

    /**
        Add all the elements from another array.
        @param that The array that we will copy from

    */
    public void addElements (Object[] that)
    {
        if ((this.inUse + that.length) >= this.array.length) {
            makeRoomFor(that.length);
        }

        System.arraycopy(that, 0, this.array, inUse, that.length);
        this.inUse += that.length;
    }

    /**
        Check if the array contains an object.
        The == operator is used to compare objects
        @param x the object to check for
        @return true if the object is in the array

    */
    public boolean containsIdentical (Object x)
    {
        for (int i = 0; i < inUse; i++) {
            if (array[i] == x) {
                return true;
            }
        }
        return false;
    }

    /**
        Check if the array contains an object.
        @param x the object to check for
        @return true if the object is in the array

    */
    public boolean contains (Object x)
    {
        return -1 != indexOf(x);
    }

    /**
        Find the location of an object in the array
        @param x The object to look for
        @return the index of the object, or -1 if it is not found

    */
    public int indexOf (Object x)
    {
        for (int i = 0; i < inUse; i++) {
            if (x.equals(array[i])) {
                return i;
            }
        }
        return -1;
    }

    /**
        Return a copy of the underlying array sized to fit the number
        of allocated elements.
        @return The array copy

    */
    public Object[] arrayCopy ()
    {
        Object[] newArray = alloc(inUse);
        System.arraycopy(array, 0, newArray, 0, inUse);
        return newArray;
    }

    /**
        Make the allocated length equal the number of elements in use.
        @return the trimmed array.

    */
    public Object[] trim ()
    {
        if (this.array.length > this.inUse) {
            setCapacity(this.inUse);
        }

        return array;
    }

    /**
        Remove an element from the array
        @param index The index of the element to remove
        @return the removed object
        @throws ArrayIndexOutOfBoundsException when index is larger than the
        logical size of the array (inUse)

    */
    public Object removeElementAt (int index)
    {
        if (index >= inUse) {
            throw new ArrayIndexOutOfBoundsException(
                Fmt.S("%s >= %s",
                      Constants.getInteger(index),
                      Constants.getInteger(inUse)));
        }

        Object object = array[index];
        int copyCount = inUse - index - 1;
        if (copyCount > 0) {
            System.arraycopy(array, index + 1, array, index, copyCount);
        }

        inUse--;
        array[inUse] = null;

        return object;
    }

    /**
        Insert an object into the array
        @param element The object to be inserted
        @param index The location where the object should be inserted
        @throws ArrayIndexOutOfBoundsException when index is larger than the
        logical size of the array (inUse)

    */
    public void insertElementAt (Object element, int index)
    {
        if (index >= inUse + 1) {
            throw new ArrayIndexOutOfBoundsException(
                Fmt.S("%s >= %s",
                      Constants.getInteger(index),
                      Constants.getInteger(inUse)));
        }

        makeRoomFor(1);
        System.arraycopy(array, index, array, index + 1, inUse - index);
        array[index] = element;
        inUse++;
    }

    /**
        Allocate the storage array.
        Subclasses should override this, allocating an array of the correct type.
        @param size The size of the array to allocate
        @return The allocated array

    */
    abstract public Object[] alloc (int size);

    /**
        A static version of addElement for cases where all you've got
        is a Foo[]

    */
    public Object[] extend (Object[] a, Object x)
    {
        Object[] newArray = alloc(a.length + 1);
        System.arraycopy(a, 0, newArray, 0, a.length);
        newArray[a.length] = x;
        return newArray;
    }

    /**
        Convert to a string.
        toString() is called on each element individually and then
        a space is placed between each element.  The entire array
        is enclosed in parentheses
        @return the String representation of the Dynamic array

    */
    public String toString ()
    {
        FastStringBuffer result = new FastStringBuffer('(');
        for (int i = 0; i < inUse; i++) {
            result.append(array[i].toString());
            if (i+1 < inUse) {
                result.append(' ');
            }
        }
        result.append(')');
        return result.toString();
    }

    /**
        Convert to a List
        @return A vector version of the array

    */
    public List toList ()
    {
        this.trim();
        return new ArrayList(Arrays.asList(array));
    }
}