ActiveX Programming Unleashed CD/AXU.iso/jgl_1_1/jgl_1_1.exe/src/Array.java

Java Source | 1996-09-12 | 24.4 KB | 798 lines

// Copyright(c) 1996 ObjectSpace, Inc.
// Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.

package jgl;

import java.util.Enumeration;

/**
 * An Array is a sequence that is very similar to a regular array except that it
 * can expand to accomodate new elements.
 * <p>
 * An Array is the simplest kind of JGL container. In addition to the common container
 * functions described earlier in this book, an Array includes functions for accessing
 * its extremities, appending, inserting, erasing, and adjusting its capacity.
 * <p>
 * The underlying architecture of Arrays makes them ideal for storing elements whose
 * order is significant and where fast numeric indexing is important. Inserting elements
 * anywhere except at the end of an Array is slow, so they should not be used where
 * this kind of operation is common. If inserting is common, consider using a List or
 * a Deque instead.
 * <p>
 * The implementation store elements in a contiguous linear memory space so that
 * index-based access is very quick. When an Array's originally allocated memory space
 * is exceeded, its elements are copied into a new memory space that is larger than the
 * old space and then the old space is deallocated. For efficiency, memory is typically
 * allocated in units of the machine's page size.
 * <p>
 * If an insertion causes reallocation, all iterators and references are invalidated;
 * otherwise, only the iterators and references after the insertion point are invalidated.
 * Inserting a single element into an Array is linear in the distance from the insertion
 * point to the end of the array. The amortized complexity over the lifetime of an Array
 * of inserting a single element at its end is constant. Insertion of multiple elements
 * into an Array with a single call of the insert member is linear in the sum of the
 * number of elements plus the distance to the end of the Array. In other words, it is
 * much faster to insert many elements into the middle of an Array at once than to do the
 * insertion one at a time.
 * <p>
 * A remove invalidates all of the iterators and references after the point of the remove.
 * <p>
 * @see jgl.Sequence
 * @see jgl.examples.ArrayExamples
 * @version 1.1
 * @author ObjectSpace, Inc.
 */

public class Array implements Sequence
  {
  Object myStorage[]; // My storage.
  int myLength; // The number of objects I currently contain.
  static final int DEFAULT_SIZE = 10;

  /**
   * Construct myself to be an empty Array.
   */
  public Array()
    {
    myStorage = new Object[ DEFAULT_SIZE ];
    }

  /**
   * Construct myself to contain a specified number of null elements.
   * @param size The number of elements to contain.
   * @exception java.lang.IllegalArgumentException If size is negative.
   */
  public Array( int size )
    {
    if( size < 0 )
      throw new IllegalArgumentException( "Attempt to create an Array with a negative size" );

    myLength = size;
    myStorage = new Object[ myLength ];
    }

  /**
   * Construct myself to contain a specified number of elements set to
   * a particular object.
   * @param size The number of elements to contain.
   * @param object The initial value of each element.
   * @exception java.lang.IllegalArgumentException If size is negative.
   */
  public Array( int size, Object object )
    {
    this( size );

    for( int i = 0; i < myLength; i++ )
      myStorage[ i ] = object;
    }

  /**
   * Construct myself to use a specified array as my initial storage.
   * @param The array to use as initial storage.
   */
  public Array( Object array[] )
    {
    myStorage = array;
    myLength = array.length;
    }

  /**
   * Construct myself to be a shallow copy of an existing Array.
   * @param array The Array to copy.
   */
  public Array( Array array )
    {
    this( array.myLength );
    System.arraycopy( array.myStorage, 0, myStorage, 0, myLength );
    }

  /**
   * Return a shallow copy of myself.
   */
  public synchronized Object clone()
    {
    return new Array( this );
    }

  /**
   * Return true if I'm equal to another object.
   * @param object The object to compare myself against.
   */
  public boolean equals( Object object )
    {
    return object instanceof Array && equals( (Array) object );
    }

  /**
   * Return true if I contain the same items in the same order as
   * another Array. Use equals() to compare the individual elements.
   * @param array The Array to compare myself against.
   */
  public synchronized boolean equals( Array array )
    {
    return Comparing.equal( this, array );
    }

  /**
   * Return my hash code for support of hashing containers
   */
  public int hashCode()
    {
    return Hashing.orderedHash( this );
    }


  /**
   * Return a string that describes me.
   */
  public synchronized String toString()
    {
    return Printing.toString( this, "Array" );
    }

  /**
   * Become a shallow copy of an existing Array.
   * @param array The Array that I shall become a shallow copy of.
   */
  public synchronized void copy( Array array )
    {
    if( this == array )
      return;

    if( array.myLength > myStorage.length )
      {
      myStorage = new Object[ array.myLength ];
      System.arraycopy( array.myStorage, 0, myStorage, 0, array.myLength );
      }
    else if( myLength > array.myLength )
      {
      System.arraycopy( array.myStorage, 0, myStorage, 0, array.myLength );

      for( int i = array.myLength; i < myLength; i++ )
        myStorage[ i ] = null; // To allow garbage collection.
      }
    else
      {
      System.arraycopy( array.myStorage, 0, myStorage, 0, array.myLength );
      }

    myLength = array.myLength;
    }

  /**
   * Copy my elements into the specified array.
   * The number of items that are copied is equal to the smaller of my
   * length and the size of the specified array.
   * @param array The array that I shall copy my elements into.
   */
  public synchronized void copyTo( Object[] array )
    {
    if( myLength < array.length )
      System.arraycopy( myStorage, 0, array, 0, myLength );
    else
      System.arraycopy( myStorage, 0, array, 0, array.length );
    }

  /**
   * Return true if I contain no entries.
   */
  public boolean isEmpty()
    {
    return myLength == 0;
    }

  /**
   * Return the number of entries that I contain.
   */
  public int size()
    {
    return myLength;
    }

  /**
   * Return the maximum number of entries that I can contain.
   */
  public int maxSize()
    {
    return Allocator.maxSize();
    }

  /**
   * Return the number of elements that I contain without allocating more
   * internal storage.
   */
  public int capacity()
    {
    return myStorage.length;
    }

  /**
   * Return my last item.
   * @exception jgl.InvalidOperationException If the Array is empty.
   */
  public synchronized Object back()
    {
    if( myLength == 0 )
      throw new InvalidOperationException( "Array is empty" );

    return myStorage[ myLength - 1 ];
    }

  /**
   * Return my first item.
   * @exception jgl.InvalidOperationException If the Array is empty.
   */
  public synchronized Object front()
    {
    if( myLength == 0 )
      throw new InvalidOperationException( "Array is empty" );

    return myStorage[ 0 ];
    }

  /**
   * Return the element at the specified index.
   * @param index The index.
   * @exception java.lang.IndexOutOfBoundsException If the index is invalid.
   */
  public synchronized Object at( int index )
    {
    if( /* index < 0 || */ index >= myLength )
      throw new IndexOutOfBoundsException( "Attempt to access index " + index + " when valid range is 0.." + (myLength - 1) );

    return myStorage[ index ];
    }

  /**
   * Set the element at the specified index to a particular object.
   * @param index The index.
   * @param object The object.
   * @exception java.lang.IndexOutOfBoundsException If the index is invalid.
   */
  public synchronized void put( int index, Object object )
    {
    if( /* index < 0 || */ index >= myLength )
      throw new IndexOutOfBoundsException( "Attempt to access index " + index + " when valid range is 0.." + (myLength - 1) );

    myStorage[ index ] = object;
    }

  /**
   * Remove all of my elements.
   */
  public synchronized void clear()
    {
    myStorage = new Object[ DEFAULT_SIZE ];
    myLength = 0;
    }

  /**
   * Remove the element at a particular position.
   * @param pos An enumeration positioned at the element to remove.
   * @exception IllegalArgumentException is the Enumeration isn't an
   * ArrayIterator for this Array object.
   */
  public void remove( Enumeration pos )
    {
    if( ! (pos instanceof ArrayIterator) )
      throw new IllegalArgumentException( "Enumeration not an ArrayIterator" );

    if( ((ArrayIterator)pos).myArray != this )
      throw new IllegalArgumentException( "Enumeration not for this Array " );

    remove( ((ArrayIterator)pos).myIndex );
    }

  /**
   * Remove the element at a particular index.
   * @param index The index of the element to remove.
   * @exception java.lang.IndexOutOfBoundsException If the index is invalid.
   */
  public synchronized void remove( int index )
    {
    if( index < 0 || index >= myLength )
      throw new IndexOutOfBoundsException( "Attempt to access index " + index + " when valid range is 0.." + (myLength - 1) );

    System.arraycopy( myStorage, index + 1, myStorage, index, myLength - index - 1 );
    myStorage[ --myLength ] = null;
    }

  /**
   * Remove the elements in the specified range.
   * @param first An Enumeration positioned at the first element to remove.
   * @param last An Enumeration positioned immediately after the last element to remove.
   * @exception IllegalArgumentException is the Enumeration isn't an
   * ArrayIterator for this Array object.
   */
  public void remove( Enumeration first, Enumeration last )
    {
    if( ( ! (first instanceof ArrayIterator) ) ||
        ( ! (last instanceof ArrayIterator) ) )
      throw new IllegalArgumentException( "Enumeration not an ArrayIterator" );

    if( ( ((ArrayIterator)first).myArray != this ) ||
        ( ((ArrayIterator)last).myArray != this ) )
      throw new IllegalArgumentException( "Enumeration not for this Array " );

    remove( ((ArrayIterator)first).myIndex, ((ArrayIterator)last).myIndex - 1 );
    }

  /**
   * Remove the elements within a range of indices.
   * @param first The index of the first element to remove.
   * @param last The index of the last element to remove.
   * @exception java.lang.IndexOutOfBoundsException If either index is invalid.
   */
  public synchronized void remove( int first, int last )
    {
    if( last < first )
      return;

    checkRange( first, last );
    int amount = last - first + 1;
    System.arraycopy( myStorage, last + 1, myStorage, first, myLength - last - 1 );

    for( int i = myLength - amount; i < myLength; i++ )
      myStorage[ i ] = null;

    myLength -= amount;
    }

  /**
   * Remove and return my last element.
   * @exception jgl.InvalidOperationException If the Array is empty.
   */
  public synchronized Object popBack()
    {
    if( myLength == 0 )
      throw new InvalidOperationException( "Array is empty" );

    Object r = myStorage[ --myLength ];
    myStorage[ myLength ] = null;
    return r;
    }

  /**
   * Add an object after my last element.  Returns null.
   * This function is a synonym for pushBack().
   * @param object The object to add.
   */
  public synchronized Object add( Object object )
    {
    if( myLength == myStorage.length )
      {
      Object[] tmp = getNextStorage();
      System.arraycopy( myStorage, 0, tmp, 0, myLength );
      myStorage = tmp;
      }

    myStorage[ myLength++ ] = object;
    return null;
    }

  /**
   * Add an object after my last element.
   * @param The object to add.
   */
  public void pushBack( Object object )
    {
    add( object );
    }

  /**
   * Insert an object at a particular position and return an iterator
   * positioned at the new element.
   * @param pos An iterator positioned at the element that the object will be inserted immediately before.
   * @param object The object to insert.
   */
  public ArrayIterator insert( ArrayIterator pos, Object object )
    {
    insert( pos.myIndex, object );
    return new ArrayIterator( this, pos.myIndex );
    }

  /**
   * Insert an object at a particular index.
   * @param index The index of the element that the object will be inserted immediately before.
   * @param object The object to insert.
   * @exception java.lang.IndexOutOfBoundsException If the index is invalid.
   */
  public synchronized void insert( int index, Object object )
    {
    if( index > myLength )
      throw new IndexOutOfBoundsException( "Attempt to insert at index " + index + " when valid range is 0.." + myLength );

    if( myLength != myStorage.length )
      {
      if( index != myLength )
        System.arraycopy( myStorage, index, myStorage, index + 1, myLength - index );
      }
    else
      {
      Object[] tmp = getNextStorage();
      System.arraycopy( myStorage, 0, tmp, 0, index );
      System.arraycopy( myStorage, index, tmp, index + 1, myLength - index );
      myStorage = tmp;
      }

    myStorage[ index ] = object;
    ++myLength;
    }

  /**
   * Insert multiple objects at a particular position.
   * @param pos An iterator positioned at the element that the objects will be inserted immediately before.
   * @param n The number of objects to insert.
   * @param object The object to insert.
   */
  public void insert( ArrayIterator pos, int n, Object object )
    {
    insert( pos.myIndex, n, object );
    }

  /**
   * Insert multiple objects at a particular index.
   * @param index The index of the element that the objects will be inserted immediately before.
   * @param object The object to insert.
   * @exception java.lang.IndexOutOfBoundsException If the index is invalid.
   * @exception java.lang.IllegalArgumentException If the number of objects is negative.
   */
  public synchronized void insert( int index, int n, Object object )
    {
    if( index < 0 || index > myLength )
      throw new IndexOutOfBoundsException( "Attempt to insert at index " + index + " when valid range is 0.." + myLength );

    if( n < 0 )
      throw new IllegalArgumentException( "Attempt to insert a negative number of objects." );

    if( n == 0 )
      return;

    if( myStorage.length - myLength >= n )
      {
      System.arraycopy( myStorage, index, myStorage, index + n, myLength - index );
      }
    else
      {
      Object[] tmp = getNextStorage( n );
      System.arraycopy( myStorage, 0, tmp, 0, index );
      System.arraycopy( myStorage, index, tmp, index + n, myLength - index );
      myStorage = tmp;
      }

    for( int i = index; i < index + n; i++ )
      myStorage[ i ] = object;

    myLength += n;
    }

  /**
   * Insert a sequence of objects at a particular location.
   * @param pos The location of the element that the objects will be inserted immediately before.
   * @param first An iterator positioned at the first element to insert.
   * @param last An iterator positioned immediately after the last element to insert.
   */
  public void insert( ArrayIterator pos, ForwardIterator first, ForwardIterator last )
    {
    insert( pos.myIndex, first, last );
    }

  /**
   * Insert a sequence of objects at a particular index.
   * @param index The index of the element that the objects will be inserted immediately before.
   * @param first An iterator positioned at the first element to insert.
   * @param last An iterator positioned immediately after the last element to insert.
   */
  public synchronized void insert( int index, ForwardIterator first, ForwardIterator last )
    {
    int n = first.distance( last );

    if( n == 0 )
      return;

    ForwardIterator firstx = (ForwardIterator) first.clone();

    if( myStorage.length - myLength >= n )
      {
      System.arraycopy( myStorage, index, myStorage, index + n, myLength - index );
      }
    else
      {
      Object[] tmp = getNextStorage();
      System.arraycopy( myStorage, 0, tmp, 0, index );
      System.arraycopy( myStorage, index, tmp, index + n, myLength - index );
      myStorage = tmp;
      }

    for( int i = index; i < index + n; i++ )
      myStorage[ i ] = firstx.nextElement();

    myLength += n;
    }

  /**
   * Swap my contents with another Array.
   * @param array The Array that I will swap my contents with.
   */
  public synchronized void swap( Array array )
    {
    int oldSize = myLength;
    Object oldStorage[] = myStorage;

    myLength = array.myLength;
    myStorage = array.myStorage;

    array.myLength = oldSize;
    array.myStorage = oldStorage;
    }

  /**
   * Return an Enumeration of my components.
   */
  public Enumeration elements()
    {
    return new ArrayIterator( this, 0 );
    }

  /**
   * Return an iterator positioned at my first item.
   */
  public ArrayIterator begin()
    {
    return new ArrayIterator( this, 0 );
    }

  /**
   * Return an iterator positioned immediately after my last item.
   */
  public ArrayIterator end()
    {
    return new ArrayIterator( this, myLength );
    }

  /**
   * Return an iterator positioned at my first item.
   */
  public ForwardIterator start()
    {
    return new ArrayIterator( this, 0 );
    }

  /**
   * Return an iterator positioned immediately after my last item.
   */
  public ForwardIterator finish()
    {
    return new ArrayIterator( this, myLength );
    }

  /**
   * If my storage space is currently larger than my total number of elements,
   * reallocate the elements into a storage space that is exactly the right size.
   */
  public synchronized void trimToSize()
    {
    if( myLength < myStorage.length )
      {
      Object oldData[] = myStorage;
      myStorage = new Object[ myLength ];
      System.arraycopy( oldData, 0, myStorage, 0, myLength );
      }
    }

  /**
   * Pre-allocate enough space to hold a specified number of elements.
   * This operation does not change the value returned by size().
   * @param n The amount of space to pre-allocate.
   * @exception java.lang.IllegalArgumentException If the specified size is negative.
   */
  public synchronized void ensureCapacity( int n )
    {
    if( n < 0 )
      throw new IllegalArgumentException( "Attempt to reserve a negative size." );

    if( myStorage.length < n )
      {
      Object[] tmp = new Object[ n ];

      if( myLength > 0 )
        System.arraycopy( myStorage, 0, tmp, 0, myLength );

      myStorage = tmp;
      }
    }

  /**
   * Remove and return my first element.
   * @exception jgl.InvalidOperationException If the Array is empty.
   */
  public synchronized Object popFront()
    {
    if( myLength == 0 )
      throw new InvalidOperationException( "Array is empty" );

    Object result = myStorage[ 0 ];
    remove( 0 );
    return result;
    }

  /**
   * Insert an object in front of my first element.
   * @param object The object to insert.
   */
  public void pushFront( Object object )
    {
    insert( 0, object );
    }

  /**
   * Remove all elements that match a particular object and return the numbers of
   * objects that were removed.
   * @param object The object to remove.
   */
  public synchronized int remove( Object object )
    {
    return remove( 0, myLength - 1, object );
    }

  /**
   * Remove all elements within a range of indices that match a particular object
   * and return the number of objects that were removed.
   * @param first The index of the first object to consider.
   * @param last The index of the last object to consider.
   * @param object The object to remove.
   * @exception java.lang.IndexOutOfBoundsException If either index is invalid.
   */
  public synchronized int remove( int first, int last, Object object )
    {
    if( last < first )
      return 0;

    checkRange( first, last );
    ArrayIterator firstx = new ArrayIterator( this, first );
    ArrayIterator lastx = new ArrayIterator( this, last + 1 );
    ArrayIterator finish = (ArrayIterator) Removing.remove( firstx, lastx, object );
    int n = finish.distance( lastx );
    remove( finish.myIndex, last );
    return n;
    }

  /**
   * Replace all elements that match a particular object with a new value and return
   * the number of objects that were replaced.
   * @param oldValue The object to be replaced.
   * @param newValue The value to substitute.
   */
  public synchronized int replace( Object oldValue, Object newValue )
    {
    return Replacing.replace( this, oldValue, newValue );
    }

  /**
   * Replace all elements within a range of indices that match a particular object
   * with a new value and return the number of objects that were replaced.
   * @param first The index of the first object to be considered.
   * @param last The index of the last object to be considered.
   * @param oldValue The object to be replaced.
   * @param newValue The value to substitute.
   * @exception java.lang.IndexOutOfBoundsException If either index is invalid.
   */
  public synchronized int replace( int first, int last, Object oldValue, Object newValue )
    {
    if( last < first )
      return 0;

    checkRange( first, last );
    return Replacing.replace( new ArrayIterator( this, first ), new ArrayIterator( this, last + 1 ), oldValue, newValue );
    }

  /**
   * Return the number of objects that match a particular value.
   * @param object The object to count.
   */
  public synchronized int count( Object object )
    {
    return Counting.count( this, object );
    }

  /**
   * Return the number of objects within a particular range of indices that match a
   * particular value.
   * @param first The index of the first object to consider.
   * @param last The index of the last object to consider.
   * @exception java.lang.IndexOutOfBoundsException If either index is invalid.
   */
  public synchronized int count( int first, int last, Object object )
    {
    if( last < first )
      return 0;

    checkRange( first, last );
    return Counting.count( new ArrayIterator( this, first ), new ArrayIterator( this, last + 1 ), object );
    }

  /**
   * Return the index of the first object that matches a particular value, or -1
   * if the object is not found.
   * @param object The object to find.
   */
  public int indexOf( Object object )
    {
    return indexOf( 0, myLength - 1, object );
    }

  /**
   * Return the index of the first object within a range of indices that match a
   * particular object, or -1 if the object is not found.
   * @param first The index of the first object to consider.
   * @param last The index of the last object to consider.
   * @param object The object to find.
   * @exception java.lang.IndexOutOfBoundsException If either index is invalid.
   */
  public synchronized int indexOf( int first, int last, Object object )
    {
    if( last < first )
      return -1;

    checkRange( first, last );
    int index = ((ArrayIterator) Finding.find( new ArrayIterator( this, first ), new ArrayIterator( this, last + 1 ), object )).myIndex;
    return index == last + 1 ? -1 : index;
    }

  /**
   * Return true if I contain a particular object.
   * @param object The object in question.
   */
  public boolean contains( Object object )
    {
    return indexOf( object ) != -1;
    }

  private void checkRange( int lo, int hi )
    {
    if( lo < 0 || lo >= myLength )
      throw new IndexOutOfBoundsException( "Attempt to access index " + lo + " when valid range is 0.." + (myLength - 1) );

    if( hi < 0 || hi >= myLength )
      throw new IndexOutOfBoundsException( "Attempt to access index " + hi + " when valid range is 0.." + (myLength - 1) );
    }

  private Object[] getNextStorage()
    {
    // double storage until 2K, then increment in 2K blocks from then on
    int newSize = myLength > 2000 ? myLength + 2000 : myLength * 2;
    if( newSize == 0 )
      newSize = 1;
    Object[] tmp = new Object[ newSize ];
    return tmp;
    }

  private Object[] getNextStorage( int n )
    {
    int newSize = myLength + n;
    Object[] tmp = new Object[ myLength + ( n > myLength ? n : myLength ) ];
    return tmp;
    }
  }