nodesequence.java

Java数据结构开发包

  public void posInsertAfter( Position willBePredecessor, Position toInsert ) 
                              throws InvalidAccessorException {    
    if (contains(toInsert))
      throw new InvalidAccessorException
	("This container already contains that position.");

    // clear the caches
    positions_= null;
    elements_= null;
    
    FNSNode fwillbepred = castPosition(willBePredecessor);
    FNSNode ftoInsert=null;
    
    //we can't use castPosition because it SHOULD BE uncontained
    try{
      ftoInsert = (FNSNode)toInsert;
    }
    catch(ClassCastException cce){
      throw new InvalidAccessorException
	("Node to insert is of the wrong class.");
    }
    
    if(fwillbepred==tail_) { //We're de-facto inserting last
      ftoInsert.setNext(null);
      ftoInsert.setPrev(fwillbepred);
      ftoInsert.setContainer(this);
      
      fwillbepred.setNext(ftoInsert);

      tail_ = ftoInsert;
      if(head_ == null) 
	head_ = tail_;
    } else {//inserting somewhere in the middle
      ftoInsert.setNext(fwillbepred.next());
      fwillbepred.next().setPrev(ftoInsert);
      ftoInsert.setPrev(fwillbepred);
      fwillbepred.setNext(ftoInsert);
      ftoInsert.setContainer(this);
    }
    size_++;
  }

  /**
 * Make toInsert the 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
    * This method also clears the position cache.
    * O(1) time
    */
  public void posInsertAtRank( int rank, Position toInsert )
                               throws InvalidAccessorException {
    if (contains(toInsert))
      throw new InvalidAccessorException
	("This container already contains that position.");

    if (rank == 0)      { posInsertFirst(toInsert);return;}
    if (rank == size()) { posInsertLast (toInsert);return; }
    checkRank (rank);
    FNSNode n = (FNSNode)atRank(rank-1);
    posInsertAfter(n,toInsert);
  }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Object remove (Position p) throws InvalidAccessorException {
        FNSNode n = castPosition(p);
          FNSNode prev = n.prev();
        FNSNode next = n.next();

        // clear the cache
        positions_ = null;
	elements_ = null;

        Object retval = n.element();
        n.setContainer(null);

        // skip over the position we're removing.
        if(prev!=null) {
            prev.setNext(next);
        } else {
            head_ = next;
        }
        if(next!=null) {
            next.setPrev(prev);
        } else {
            tail_ = prev;
        }

        size_--;
        return retval;
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Object removeAfter(Position p) throws InvalidAccessorException {
        return remove(after(p));
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Object removeBefore(Position p) throws InvalidAccessorException {
        return remove(before(p));
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Object removeFirst() throws InvalidAccessorException {
        return remove(first());
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Object removeLast() throws InvalidAccessorException {
        return remove(last());
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Object removeAtRank(int i) throws InvalidAccessorException {
        return remove(atRank(i));
    }

  /**
    * O(1) time
    */
    public int size() {
        return size_;
    }
 
  /**
    * O(1) time
    */
  public Object replaceElement(Accessor a, Object newElement) 
                               throws InvalidAccessorException {
				 
    //clear the elements but not the positions cache
    elements_ = null;			
    FNSNode afns = castPosition(a);
    Object retval = afns.element();
    afns.setElement(newElement);
    return retval;
  }

  /**
    * O(1) time if the cache already exists
    * Otherwise O(N) to construct it
    */
  public PositionIterator positions(){
        // if the cache is invalid, create it
        if(positions_ == null) {
            positions_ = new Position[size_];
            FNSNode cur = head_;
            for(int i=0; i<size_; i++) {
                positions_[i] = cur;
                cur = cur.next();
            }
        }
        return new ArrayPositionIterator(positions_);
  }

  /**
    * O(1) time if the cache already exists
    * Otherwise O(N) to construct it
    */
  public ObjectIterator elements(){
        // if the cache is invalid, create it
        if(elements_ == null) {
            elements_ = new Object[size_];
            FNSNode cur = head_;
            for(int i=0; i<size_; i++) {
                elements_[i] = cur.element();
                cur = cur.next();
            }
        }
        return new ArrayObjectIterator(elements_);
  }

  /**
    * O(1) time
    */
  public boolean contains(Accessor a) throws InvalidAccessorException {
    if (a == null)
      throw new InvalidAccessorException
	("A null position cannot be contained.");
    else if (a instanceof FNSNode)
      return ((FNSNode)a).container() == this;
    else
      return false;
  }
  
  public String toString(){  
    return ToString.stringfor(this);
  }

    // Convenience methods

  /**
    * This method throws an exception if the Sequence is empty.
    * O(1) time
    */
    private final void checkEmpty() 
        throws EmptyContainerException {
            if(isEmpty()) throw new EmptyContainerException 
			    ("Sequence is empty");
        }

  /**
    * This method throws an exception if the rank is out of bounds
    * @param rank The rank to check
    * O(1) time
    */
    private final void checkRank(int rank) 
        throws BoundaryViolationException {
            if (rank < 0 || rank >= size_) throw new BoundaryViolationException
                ("Rank " +rank+ " out of range [0.."+size_+")");
        }								

  /**
    * This method throws an exception if the position is 
    * not a non-null FNSNode contained by this.
    * @param a The accessor to check
    * O(1) time
    */
  private final FNSNode castPosition(Accessor a) 
    throws InvalidAccessorException {

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

    FNSNode n; 
    try{
      n = (FNSNode)a;
    }
    catch (ClassCastException cce) {
      throw new InvalidAccessorException("Wrong class " + a.getClass() );
    }
    
    if (n.container() != this)
      throw new InvalidAccessorException("wrong container");
    
    return n;
  }
    


    
    // ------------------------------------------------------


    
    /**
     * This nested class is the node for NodeSequence.
     * It is Decorable, and a position.  It is public per request of mdh,
     * who hacked with it in the low-overhead implementation of
     * Graph.
     */
    
    public static class FNSNode extends HashtableDecorable
    implements Position {
	
	/**
	 * The nodes immediately before and after this one (may be null
	 * if this node is at an end of the Sequence)
	 * @serial
	 */
        private FNSNode next_, prev_;
	
	/**
	 * The container that this node belongs to
	 * (this makes O(1) time calls to contains() possible)
	 * @serial
	 */
        private InspectableContainer cont_;
	
	/**
	 * The element this position stores
	 * @serial
	 */
        private Object  elt_;
	
	/**
	 * Constructor for the Node. 
	 * @param prev The node before this one in the Sequence. (may be null)
	 * @param next The node after this one in the Sequence. (may be null)
	 * @param cont The node's container. (may be null)
	 * @param elt The node's element. (null if the element is really null)
	 */
        private FNSNode(FNSNode prev, FNSNode next,
		InspectableContainer cont, Object elt) {
            prev_ = prev; if(prev!=null) prev.setNext(this);
            next_ = next; if(next!=null) next.setPrev(this);
            cont_ = cont;
            elt_ = elt;
        }

      /**
	 * Default constructor for the Node. 
	 * @param elt The node's element. (null if the element is really null)
	 */
      public FNSNode(Object elt){
	prev_ = null;
	next_ = null;
	cont_ = null;
	elt_ = elt;
      }
	
        public final Object element() { 
            return elt_;
        }

	/**
	 * Gets the node after this one in the Sequence
	 * @return The node after this one in the Sequence
	 */
        final FNSNode next() { return next_; }
	
	/**
	 * Gets the node before this one in the Sequence
	 * @return The node before this one in the Sequence
	 */
        final FNSNode prev() { return prev_; }
	
	/**
	 * Sets the node after this one in the Sequence
	 * @param The node after this one in the Sequence
	 */
        private final void setNext(FNSNode n) { next_ = n; }
	
	/**
	 * Sets the node before this one in the Sequence
	 * @param The node before this one in the Sequence
	 */
        private final void setPrev(FNSNode p) { prev_ = p; }
	
	/**
	 * Sets the position's element
	 * @param elt The position's new element
	 */
	protected final void setElement(Object elt) {
            elt_ = elt;
        }
	
	/**
	 * Gets the position's container, for O(1) time implementation of contains()
	 * @return The position's container
	 */
	final InspectableContainer container() {
	    return cont_;
	}
	
	/**
	 * Sets the position's container, for O(1) time implementation of contains()
	 * @param c The position's container
	 */
	final void setContainer(InspectableContainer c){
	    cont_ = c;
	}
	
	public String toString(){
	    return ToString.stringfor(this);
	}
    }

}