arraysequence.java

Java数据结构开发包

/*
  Copyright (c) 1999, 2000 Brown University, Providence, RI
  
                            All Rights Reserved
  
  Permission to use, copy, modify, and distribute this software and its
  documentation for any purpose other than its incorporation into a
  commercial product is hereby granted without fee, provided that the
  above copyright notice appear in all copies and that both that
  copyright notice and this permission notice appear in supporting
  documentation, and that the name of Brown University not be used in
  advertising or publicity pertaining to distribution of the software
  without specific, written prior permission.
  
  BROWN UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR ANY PARTICULAR PURPOSE.  IN NO EVENT SHALL BROWN
  UNIVERSITY BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  PERFORMANCE OF THIS SOFTWARE.
*/

package jdsl.core.ref;

import jdsl.core.api.*;

/**
  * A Sequence implemented on top of an array. <p>
  *
  * In this design, the Sequence's Positions keep track of their ranks 
  * in the Sequence, making all atRank(int) operations O(1) time. 
  * The Positions also keep track of their Container (the Sequence), 
  * so the Sequence's contains(Accessor) method takes O(1) time.
  
  * <p>
  * The array is used in a circular fashion -- the first Position in
  * the Sequence can occupy any index in the array, and the Sequence's
  * subsequent Positions may wrap around the end of the array to occupy
  * indices at the front of the array. 
  * Insertion and removal operations generally take O(n) time.
  * When items are inserted into or removed from the Sequence, Positions
  * must be shifted up or down the array to make room for the new Position.
  * In these cases, the design of the shifting operation ensures that 
  * the minimum number of Positions are moved around. In any insertion
  * or removal operation, no more than n/2 Positions will be shifted
  * in the array (where n is the total number of items in the Sequence). 
  * The methods insertFirst(Obj), insertLast(Obj), posInsertFirst(Pos), 
  * posInsertLast(Pos), removeFirst(), and removeLast() generally take
  * O(1) time, since no internal shifting is required. But when the
  * array has to be reallocated and copied, these methods take O(n) time.
  
  * <p>
  * The capacity of the Sequence is equal to the capacity of the 
  * underlying array. Whenever the size of the Sequence becomes equal to 
  * the size of the underlying array, the next insertion operation will
  * cause the array to double in size. The load factor of the array is the
  * ratio of the number of elements stored in the array to the capacity of 
  * the array. The capacity of the array is possibly halved when the load
  * factor of the array falls below 0.25. 
  * The initial capacity of the array is 16 (or the capacity in the constructor).
  * The maximum capacity of the array is 2^26. If a client attempts to
  * exceed this maximum, a ContainerFullException is thrown.
  
  * <p>
  * This ArraySequence incorporates the iterator caching optimization:
  * calls to iterator-returning methods are amortized
  * O(n/k) time if called k times between 
  * modifications of the sequence. This is accomplished by making a list of
  * the Positions of the sequence whenever iterating through
  * the list is necessary, and using it until there is a modification
  * to the Sequence. <p>
  *
 * @author Lucy Perry (lep)
 * @author Mark Handy (mdh)
 * @author Jitchaya Buranahirun (jbr)
 * @author Benoit Hudson (bh)
 * @author Ryan Shaun Baker (rsb)
  *
  * @version JDSL 2.1.1 
  */
public class ArraySequence extends AbstractPositionalContainer
implements Sequence {
  


  /**
    * The stored size of the Sequence -- modified on insertion or removal.
    */
  private int size_;


  /**
    * The size of the underlying array
    */
  private int array_size_;


  /**
    * Index of the first Position of the Sequence
    */
  private int first_;


  /**
    * Underlying array for Positions
    */
  private ArrayPos positions_[];

  /**
    * Cache for Positions; Discarded upon modification.
    */
  private Position cPos_[];

  /**
    * Cache for elements; Discarded upon modification.
    */
  private Object cElts_[];

  /**
    * Initial capacity for the Sequence & underlying array.
    * The array will never shrink below this capacity.
    */
  private int init_cap_;


  /**
    * Whether the array should be halved when the load factor of the 
    * array is less than or equal to 0.25.
    */
  private boolean permit_shrinkage_;


  /**
    * This is used to ensure that the array never shrinks until 
    * it has overflowed at least once.
    */
  private boolean array_has_grown_;



  // **** some constants ****
  private static final int MAX_CAPACITY = 1 << 26;// == 2^26
  private static final int SHRINK_LOAD_FACTOR = 4;

  // **** some default vals -- client can override w/ special constructors ****
  private static final int DEFAULT_INIT_CAP = 16;
  private static final boolean DEFAULT_PERMIT_SHRINKAGE = true;



  /**
    * The default constructor for ArraySequence
    * Initial array capacity defaults to 16.
    * The array is shrinkable by default.
    */
  public ArraySequence(){
    super();
    init(DEFAULT_INIT_CAP, DEFAULT_PERMIT_SHRINKAGE);
  }


  /**
    * Creates an empty Sequence. 
    * Uses the given initial capacity for the array.
    */
  public ArraySequence(int initialCapacity){
    super();
    int realCap = initCapacity(initialCapacity);
    init(realCap, DEFAULT_PERMIT_SHRINKAGE);
  }


  /**
    * Creates an empty Sequence.
    * Lets the client specify non-shrinkable.
    * Uses default inital array capacity of 16.
    */
  public ArraySequence(boolean permitShrinkage){
    super();
    init(DEFAULT_INIT_CAP, permitShrinkage);
  }


  /**
    * Creates an empty Sequence.
    * Lets the client specify the array's initial capacity,
    * and whether the array is shrinkable.
    */
  public ArraySequence(int initialCapacity, boolean permitShrinkage){
    int realCap = initCapacity(initialCapacity);
    init(realCap, permitShrinkage);
  }
    

  /*
    A service method used by the constructors.
  */
  private final void init(int initialCapacity, boolean permitShrinkage){
    size_ = 0;
    first_ = -1;

    positions_ = new ArrayPos[initialCapacity];  
    array_size_ = initialCapacity;
    init_cap_ = initialCapacity;
    permit_shrinkage_ = permitShrinkage;
    array_has_grown_ = false;//array has not grown yet
  }


  /*
    A service method to deal w/ a user-inputted inital array capacity.
  */
  private final int initCapacity(int initialCapacity)
    throws IllegalArgumentException{
      if (initialCapacity > MAX_CAPACITY){
	throw new IllegalArgumentException("initialCapacity must be no greater"
					   + " than 2^30");
      }
      else{
	// approximate initialCapacity with the closest power of 2
	// greater than initialCapacity; this could be done more
	// efficiently with a binary search on an array storing all the
	// powers of 2 between 1 and 2^30
	int ic = 1;
	while (ic < initialCapacity)
	  ic <<= 1;
	return ic;
      }
  }
    


  /**
    * Returns an empty ArraySequence.
    * O(1) time.
    */
  public Container newContainer(){
    return new ArraySequence(init_cap_, permit_shrinkage_);
  }

  
  /**
    * O(1) time.
    */
  public Position first() throws EmptyContainerException{
    checkEmpty();
    return positions_[first_];
  }


  /**
    * O(1) time.
    */
  public Position last() throws EmptyContainerException {
    checkEmpty();
    // Use modulo arithmetic. But add array_size_ first, because the -1
    // in this expression could result in an array index of -1 (illegal)
    int lastIndex = (first_+size_-1+array_size_)%array_size_;
    return positions_[lastIndex];
  }


  /**
    * O(1) time.
    */
  public boolean isFirst (Position p) throws InvalidAccessorException{
    // check that p != null, and that p is contained in this Sequence
    verifyContained(p); // throws IAE if null or from another container
    return p == positions_[first_];
  }


  /**
    * O(1) time.
    */
  public boolean isLast (Position p) throws InvalidAccessorException{
    // check that p != null, and that p is contained in this Sequence
    verifyContained(p); // throws IAE if null or from another container

    // Use modulo arithmetic. But add array_size_ first, because the -1
    // in this expression could result in an array index of -1 (illegal)
    int lastIndex = (first_+size_-1+array_size_)%array_size_;
    return p == positions_[lastIndex];
  }


  /**
    * O(1) time.
    */
  public Position atRank (int rank) throws BoundaryViolationException{
    if (rank<0 || rank>=size_){
      throw new BoundaryViolationException("Invalid rank.");
    }
    return positions_[(first_+rank)%array_size_];
  }


  /**
    * O(1) time.
    */
  public int rankOf (Position p) throws InvalidAccessorException{

    ArrayPos apos = verifyContained(p); // thows IAE if p is null,
    // or if p is not contained in this Sequence. Also converts to ArrayPos

    return apos.rank();
  }


  /**
    * O(1) time.
    */
  public Position before (Position p) throws 
    InvalidAccessorException, BoundaryViolationException{ 

      ArrayPos apos = verifyContained(p);// thows IAE if p is null,
      // or if p is not contained in this Sequence. Also converts to ArrayPos

      int rank = apos.rank()-1;
      if (rank<0)
	throw new BoundaryViolationException("Can't get before of first");

      return positions_[(first_+rank)%array_size_];
  }


  /**
    * O(1) time.
    */
  public Position after (Position p) throws
    InvalidAccessorException, BoundaryViolationException{

      ArrayPos apos = verifyContained(p);// thows IAE if p is null,
      // or if p is not contained in this Sequence. Also converts to ArrayPos

      int rank = apos.rank() + 1;
      if (rank>=size_)
	throw new BoundaryViolationException("Can't get after of last");

      return positions_[(first_+rank)%array_size_];
  }


  /**
    * This method also clears the Position and element caches.
    * O(n) time, where n is the number of elements in the Sequence.
    * In fact, at most n/2 Positions are shifted in one execution of 
    * insertBefore(p,elt).
    */
  public Position insertBefore (Position p, Object elt)
    throws InvalidAccessorException{ 
      return insertAtRank(rankOf(p), elt);
  }



  /**
    * This method also clears the Position and element caches.
    * O(n) time.
    * In fact, at most n/2 Positions will be shiften in one execution of
    * insertAfter(p,elt).
    */
  public Position insertAfter (Position p, Object elt)
    throws InvalidAccessorException{
      return insertAtRank(rankOf(p)+1, elt);
  }


  /**