arraysequence.java

Java数据结构开发包

    * This method also clears the Position and element caches.
    * O(1) time in the general case.
    * O(n) time if the array size must be doubled because of overflow.
    */
  public Position insertFirst(Object elt) throws InvalidAccessorException{
    return insertAtRank(0, elt);
  } 


  /**
    * This method also clears the Position and element caches.
    * O(1) time in the general case.
    * O(n) time if the array size must be doubled because of overflow.
    */
  public Position insertLast(Object elt)
    throws InvalidAccessorException{
      return insertAtRank(size(), elt);
  }


  /**
    * This method also clears the Position and element caches.
    * O(1) time if rank==0 or rank==size_, except in overflow cases.
    * O(n) time in the general case.
    */
  public Position insertAtRank (int rank, Object elt)
    throws InvalidAccessorException, BoundaryViolationException{
      ArrayPos apos = new ArrayPos(elt);
      if (rank<0 || rank>size_){
	throw new BoundaryViolationException("Invalid rank");
      }
      safePosInsertAtRank(rank, apos);
      return apos;
  }


  /**
    * Makes toInsert the first Position of this Sequence.
    * @param toInsert Position of a compatible type for this Sequence
    * @exception InvalidAccessorException if toInsert is already contained,
    * or is of an incompatible type, or is null
    * This method also clears the Position and element caches.
    * O(1) time in the general case.
    * O(n) time if the array size must be doubled because of overflow.
    */
  public void posInsertFirst( Position toInsert ) 
    throws InvalidAccessorException{
      posInsertAtRank(0, toInsert);
  }


  /**
    * Makes toInsert the last Position of this Sequence.
    * @param toInsert Position of a compatible type for this Sequence
    * @exception InvalidAccessorException if toInsert is already contained,
    * or is of an incompatible type, or is null
    * This method also clears the Position and element caches.
    * O(1) time in the general case.
    * O(n) time if the array size must be doubled because of overflow.
    */
  public void posInsertLast( Position toInsert ) 
    throws InvalidAccessorException{
      posInsertAtRank(size_, toInsert);
  }


  /**
    * Makes toInsert the predecessor of willBeSuccessor.
    * @param willBeSuccessor a Position in this Sequence
    * @param toInsert Position of a compatible type for this Sequence
    * @exception InvalidAccessorException if toInsert is already contained,
    * or is of an incompatible type, or is null; or if willBeSuccessor is 
    * null, incompatible, or not contained
    * This method also clears the Position and element caches.
    * O(n) time.
    */
  public void posInsertBefore( Position willBeSuccessor, Position toInsert ) 
    throws InvalidAccessorException{
      posInsertAtRank(rankOf(willBeSuccessor), toInsert);
  }


  /**
    * Makes toInsert the predecessor of willBeSuccessor.
    * @param willBePredecessor a Position in this Sequence
    * @param toInsert Position of a compatible type for this Sequence
    * @exception InvalidAccessorException if toInsert is already contained,
    * or is of an incompatible type, or is null; or if willBePredecessor is 
    * null, incompatible, or not contained
    * This method also clears the Position and element caches.
    * O(n) time.
    */
  public void posInsertAfter( Position willBePredecessor, Position toInsert ) 
    throws InvalidAccessorException{    
      posInsertAtRank(rankOf(willBePredecessor) + 1, toInsert);
  }


  /**
    * Makes toInsert to rank'th Position in this Sequence.
    * @param rank for n the size of this Sequence, rank must be in [0,n]
    * @param toInsert Position of a compatible type for this Sequence
    * @exception InvalidAccessorException if toInsert is already contained,
    * or is of an incompatible type, or is null
    * This method also clears the Position and element caches.
    * O(1) time if rank==0 or rank==size_ and no array overflow occurs.
    * O(n) time otherwise.
    */
  public void posInsertAtRank( int rank, Position toInsert )
    throws InvalidAccessorException{
      
      ArrayPos apos = verifyUncontained(toInsert);

      if (rank<0 || rank>size_){
	throw new BoundaryViolationException("Rank " +rank+ " out of bounds.");
      }
      safePosInsertAtRank(rank, apos);
  }


  /**
    * This method also clears the Position and element caches.
    * O(1) time if p is first or last, and no shrinkage of the array is needed.
    * O(n) otherwise.
    */
  public Object remove(Position p) throws InvalidAccessorException{
    ArrayPos apos = verifyContained(p);
    int removedRank = apos.rank();
    Object toReturn = apos.element();

    apos.setContainer(null);//Position now knows it's out of this Container
    apos.setRank(-1);//just for safety -- we want its rank to be unusable

    if (removedRank>(size_/2)){//if removed pos is nearer the end
      //move last part of the sequence
      shiftPositionsMinusOne(removedRank+1, size_-1);
      //downshifts Positions in array
    }
    
    else{// removed pos is nearer the front 
      //move front part of sequence
      shiftPositionsPlusOne(0, removedRank-1);
      //shifts Positions 1 index forward 
      first_ = (first_+1)%array_size_;//adjust the first_ index
    }

    size_--;
      
    //now reset the rank of all Positions at ranks higher than removed pos
    for (int j=removedRank; j<size_; j++){
      positions_[(first_+j)%array_size_].setRank(j);//update rank
    }

    //clear out the caches
    cPos_ = null;
    cElts_ = null;

    ensureLoadFactor();//shrink the array if load factor is too low

    return toReturn;
  }


  /**
    * This method also clears the Position and element caches.
    * O(n) time.
    */
  public Object removeAfter(Position p) throws
    InvalidAccessorException, BoundaryViolationException{
    return remove(after(p));
  }


  /**
    * This method also clears the Position and element caches.
    * O(n) time.
    */
  public Object removeBefore(Position p) throws
    InvalidAccessorException, BoundaryViolationException {
    return remove(before(p));
  }


  /**
    * This method also clears the Position and element caches.
    * O(1) time, except in cases where the array size must be halved, to 
    * maintain a load factor of at least 0.25.
    */
  public Object removeFirst() throws EmptyContainerException {
    checkEmpty();
    return remove(first());
  }


  /**
    * This method also clears the Position and element caches.
    * O(1) time, except in cases where the array size must be halved, to 
    * maintain a load factor of at least 0.25.
    */
  public Object removeLast() throws EmptyContainerException {
    checkEmpty();
    return remove(last());
  }


  /**
    * This method also clears the Position and element caches.
    * O(n) time.
    */
  public Object removeAtRank(int i) throws BoundaryViolationException {
    return remove(atRank(i));
  }


  /**
    * O(1) time.
    */
  public int size() {
    return size_;
  } 


  /**
    * This method also invalidates the elements cache.
    * O(1) time.
    */
  public Object replaceElement(Accessor a, Object newElement) 
    throws InvalidAccessorException{
      
      ArrayPos apos = verifyContained(a);// checks that a is not null,
      // and that it is an ArrayPos contained in this Sequence.
      // Throws IAE otherwise.

      Object toReturn = apos.element();
      apos.setElement(newElement);

      //invalid the elements cache.  You can't change the element in the cache,
      //since that would change the values in existing iterators which are
      //currently in use.
      cElts_ = null;

      return toReturn;
  }


  /**
    * O(1) time if the cache already exitsts.
    * Otherwise O(n) time to construct it.
    */
  public PositionIterator positions(){
    //if cache is invalid, create it
    if (cPos_ == null){
      cPos_ = new Position[size_];
      circularPositionsArrayCopy(cPos_);
    }
    return new ArrayPositionIterator(cPos_);
  }



  /**
    * O(1) time if the cache already exists.
    * Otherwise O(n) time to construct it.
    */
  public ObjectIterator elements(){
    //if cache is invalid, but there is a Positions cache, then create it from
    //the Positions cache.  Otherwise iterate through the sequence, and get all
    //the Positions.
    if( cElts_ == null ){
      cElts_ = new Object[size_];
      if( cPos_ != null ){
	for ( int i = 0 ; i < cElts_.length; ++i ){
	  cElts_[i] = cPos_[i].element();
	}
      }
      else{
	for (int i=0; i<size_; i++){
	  cElts_[i] = positions_[(first_+i)%array_size_].element();
	}
      }
    }
    return new ArrayObjectIterator(cElts_);
  }



  /**
    * O(1) time.
    */
  public boolean contains(Accessor a) throws InvalidAccessorException{
    if (a == null){
      throw new InvalidAccessorException("null accessor");
    }
    ArrayPos apos;
    try{
      apos = (ArrayPos)a;
    }
    catch(ClassCastException cce){
      return false;
    }
    return (apos.container() == this);
  }



  /**
    * O(n) time.
    */
  public String toString(){
    return ToString.stringfor(this);
  }


  /**
    * A public convenience method that allows the user to 
    * toggle the shrinkability of the array.
    * O(1) time.
    */
  public void setArrayShrinkability(boolean permitShrinkage){
    permit_shrinkage_ = permitShrinkage;
  }



  //*************Auxillary methods************************


  /* 
     Makes sure the array is large enough; if not, double the capacity.
   */
  private final void ensureCapacity(){
    if (size_ >= positions_.length){//if array needs to grow
      if (size_ > MAX_CAPACITY/2){
	throw new FullContainerException("Maximum capacity of the Sequence exceeded.");
      }
      //reallocate array to twice its current size
      ArrayPos[] p2 = new ArrayPos[positions_.length*2];
      circularPositionsArrayCopy(p2);
      array_size_ = positions_.length*2;
      first_ = 0;
      positions_ = p2;
      array_has_grown_ = true;
    }
  }

  /* 
     Makes sure the load factor of the array is greater than
     SHRINK_LOAD_FACTOR; if not, halve the capacity.
  */
  private final void ensureLoadFactor(){
    if (permit_shrinkage_ &&
	array_has_grown_ &&
	size_ <= positions_.length/SHRINK_LOAD_FACTOR &&
	positions_.length >= 2*init_cap_){
      // halve the array capacity
      ArrayPos[] p2 = new ArrayPos[positions_.length/2];
      circularPositionsArrayCopy(p2);
      array_size_ = positions_.length/2;
      first_ = 0;
      positions_ = p2;
    }
  }



  /*
    Copies all Positions from the original array into second array passed
    in. Uses system.arraycopy method, but must first divide original array
    into two portions to deal w/ wraparound property.
    
    Assume that array2 is big enough, which should be the case if nothing is