arraysequence.java

Java数据结构开发包

    broken.
   */
  private final void circularPositionsArrayCopy(Position[] array2){ 

    // if there are no Positions in the Sequence, then nothing to copy
    if (size_ == 0){
      return;
    }

    // find out how many indices from first Pos to end of array (inclusive)
    int numberFromFirst = array_size_ - first_;
    
    // if this number >= size_ then no wrapping required, so do basic copy
    if (numberFromFirst >= size_){
      System.arraycopy(positions_, first_, array2, 0, size_);
    }
    else{// wrapping is required
      //first copy the portion starting at positions_[first_]
      System.arraycopy(positions_, first_, array2, 0, numberFromFirst);
      //now copy the last portion of the Seq (which starts at positions_[0])
      System.arraycopy(positions_, 0, array2, numberFromFirst,
		       size_ - numberFromFirst);
    }
  }



  /*
    Shift all Positions between rank1 and rank2 (inclusive) to be 
    one index lower in the array.
  */
  private final void shiftPositionsMinusOne(int rank1, int rank2){

    // number of Positions to shift
    int numToShift = rank2 - rank1 + 1;

    if (numToShift == 0){
      return;
    }

    int pos1Index = (first_+rank1)%array_size_;
    int pos2Index = (first_+rank2)%array_size_;

    int newPos1Index = (pos1Index-1+array_size_)%array_size_;

    // if it's an easy case, where we can do it in one chunk....
    if (pos2Index >= pos1Index &&
	pos1Index > 0){
      System.arraycopy(positions_, pos1Index, positions_, newPos1Index, numToShift);
    }

    else{//we have to copy the Sequence in parts, because of the wrap-around
      
      // find out how many indices from first Pos to end of array (inclusive)
      int numberFromFirst = (array_size_ - pos1Index)%array_size_;

      // System.out.println("numberFromFirst = " + numberFromFirst);
//       System.out.println("pos1Index = " + pos1Index);
//       System.out.println("pos2Index = " + pos2Index);
//       System.out.println("newPos1Index = " + newPos1Index);


      // copy the portion of the Seq starting at positions_[pos1Index]
      System.arraycopy(positions_, pos1Index, positions_, newPos1Index,
		       numberFromFirst);

      // now move a lone Position from beginning of array to end
      positions_[array_size_-1] = positions_[0];

      // now move the portion of the Seq starting at positions_[1]
      int numLeftToMove = numToShift - numberFromFirst - 1;
      System.arraycopy(positions_, 1, positions_, 0, numLeftToMove);
    }

    // ** This chunk of code is what the above madness replaced
    // for (int i=rank1; i<=rank2; i++){
    //       int oldIndex = (first_+i)%array_size_;
    //       int newIndex = (oldIndex-1+array_size_)%arraySize;// = oldIndex-1
    //       positions_[newIndex] = positions_[oldIndex];
    // }
    // ** end old chunk of code
    // I am keeping it here in case we find out that the compiler can do this
    // sort of thing more efficiently than we can by hand.

    //now clean out the last space (maybe unnecessary, but good for memory)
    int lastIndex = (first_+rank2)%array_size_;
    positions_[lastIndex] = null;
  }



  /*
    Shift all Positions between rank1 and rank2 (inclusive) to be one
    index higher in the array.
  */
  private final void shiftPositionsPlusOne(int rank1, int rank2){

    //number of Positions to shift
    int numToShift = rank2 - rank1 + 1;

    if (numToShift == 0){
      return;
    }

    int pos1Index = (first_+rank1)%array_size_;
    int pos2Index = (first_+rank2)%array_size_;

    int newPos1Index = (pos1Index+1)%array_size_;

    // if it's an easy case, where we can do it in one chunk...
    if (pos2Index >= pos1Index && 
	pos2Index < array_size_-1){// last Pos won't fall off end of array
      System.arraycopy(positions_, pos1Index, positions_, newPos1Index,
		       numToShift);
    }

    else{//we have to copy the Sequence in parts, because of the wrap-around
      
      // find out how many indices from beginning of array to rank2 pos (inclusive)
      int numAtFront = (pos2Index + 1)%array_size_;
      
     //  System.out.println("numAtFront = " + numAtFront);
//       System.out.println("pos1Index = " + pos1Index);
//       System.out.println("pos2Index = " + pos2Index);
//       System.out.println("newPos1Index = " + newPos1Index);

      // copy portion of array starting at positions_[0]
      System.arraycopy(positions_, 0, positions_, 1, numAtFront);

      // now move a lone Position from end of array to beginning
      positions_[0] = positions_[array_size_-1];

      // now move the portion of the array starting at rank1 pos
      int numLeftToMove = numToShift - 1 - numAtFront;
      System.arraycopy(positions_, pos1Index, positions_, newPos1Index, 
		       numLeftToMove);
    }

    // ** This chunk of code is what the above madness replaced
    //  for (int i=rank2; i>=rank1; i--){
    //       int oldIndex = (first_+i)%array_size_;
    //       int newIndex = (oldIndex+1)%array_size_;
    //       positions_[newIndex] = positions_[oldIndex];
    //  }
    // ** end old chunk of code
    // I am keeping it here in case we find out that the compiler can do this
    // sort of thing more efficiently than we can by hand.

    //now clean out the first space (maybe unnecessary, but good for memory)
    int firstIndex = (first_+rank1)%array_size_;
    positions_[firstIndex] = null;
  }



  /*
    Checks for null, and attempts to cast a Position to an ArrayPos.
  */
  private final ArrayPos castPosition(Accessor a) throws
    InvalidAccessorException{

    if (a==null)
      throw new InvalidAccessorException("null accessor");

    ArrayPos apos;
    try{
      apos = (ArrayPos)a;
    }
    catch (ClassCastException cce){
      throw new InvalidAccessorException("Wrong class " + a.getClass());
    }
    
    return apos;
  }



  private final void checkEmpty() throws EmptyContainerException{
    if (isEmpty())
      throw new EmptyContainerException("Sequence is empty");
  }



  /*
    This helper method should be used only when 
    1. The Position has already been cast successfully to an ArrayPos.
    2. The ArrayPos is not null.
    3. The speicified rank is within bounds.
    4. the ArrayPos is not already contained by this container.
  */
  private final void safePosInsertAtRank(int rank, ArrayPos apos){
       
    ensureCapacity();//ensures array is large enough; if not, doubles capacity

    if (isEmpty()){
      safePosInsertOnly(apos);
      return;
    }

    if (rank>(size_/2)){//if rank is nearer to the end of the sequence
      //move everything after rank up one index
      shiftPositionsPlusOne(rank, size_-1);
    }
    else{// rank is in first half of sequence
      //move front part of the sequence
      shiftPositionsMinusOne(0, rank-1);

      // adjust first_ index
      // Use modulo arithmetic. But add array_size_ first, because the -1
      // in this expression could result in an array index of -1 (illegal)
      first_ = (first_-1+array_size_)%array_size_;
    }
    
    //now stick the new Position in proper rank/index
    positions_[(first_+rank)%array_size_] = apos;
    apos.setRank(rank);
    apos.setContainer(this);

    size_++;

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

    //adjust the ranks of all Positions at ranks higher than the added pos
    for (int j=rank+1; j<size_; j++){
      positions_[(first_+j)%array_size_].setRank(j);
    }
  }



  private final void safePosInsertOnly(ArrayPos apos){
    positions_[0] = apos;
    apos.setRank(0);
    apos.setContainer(this);
    size_ = 1;
    first_ = 0;

    //invalidate the caches
    cPos_ = null;
    cElts_ = null;
  }

  

  /*
    Verifies that pos is contained by this container, and casts it to ArrayPos.
    Also ensures that pos is not null.
  */
  private final ArrayPos verifyContained(Accessor pos) throws
    InvalidAccessorException{
    ArrayPos apos = castPosition(pos);
    if (apos.container() != this){
      throw new InvalidAccessorException("Position not contained by this Sequence");
    }
    return apos;
  }



  /*
    Verifies that pos is _not_ contained by this, and casts it to an ArrayPos.
    Also ensures that pos is not null.
  */
  private final ArrayPos verifyUncontained(Accessor pos) throws
    InvalidAccessorException{
    ArrayPos apos = castPosition(pos);
    if (apos.container() == this){
      throw new InvalidAccessorException("Position is already contained by this Sequence");
    }
    return apos;
  }
  


  /**
    * This nested class is the Position for ArraySequence.
    * It is Decorable, and a Position.
    */

  private static class ArrayPos extends HashtableDecorable
    implements Position {


    /**
      * The container that this ArrayPos belongs to.
      * (This makes O(1) calls to contains() possible)
      */
    private InspectableContainer cont_;

    /** 
      * This ArrayPos's rank in the Sequence.
      */
    private int rank_;

    /**
      * The element this Position stores
      */
    private Object elt_;


    /**
      * Constructor for the ArrayPos.
      * @param elt The Position's element.
      */
    ArrayPos(Object elt){
      elt_ = elt;
    }


    public final Object element(){
      return elt_;
    }


    public String toString(){
      return ToString.stringfor(this);
    }


    /**
      * Gets the Position's container, for O(1) implementation of contains()
      * @return The Position's container
      */
    final InspectableContainer container(){
      return cont_;
    }


    /**
      * Sets the Position's container, for O(1) implementation of contains()
      * @param The Position's container
      */
    final void setContainer(InspectableContainer c){
      cont_ = c;
    }


    /**
      * Sets the Position's element
      * @param The Position's new element
      */
    final void setElement(Object elt){
      elt_ = elt;
    }

    
    /**
      * Gets the Position's rank in the Sequence.
      */
    final int rank(){
      return rank_;
    }


    /**
      * Sets the Position's rank in the Sequence.
      * @param rank The Position's new rank.
      */
    final void setRank(int rank){
      rank_ = rank;
    }
  }


}