nodesequence.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 based on a doubly-linked-list implementation.<p>
 *
 * It incorporates the iterator caching optimization:<br>
 * calls to iterator() 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>
 *
 * This implementation does not use fictitious positions at the
 * beginning or end of the Sequence, and the head and tail node have
 * null pointers past the beginning or end of the Sequence. <p>
 *
 * The non-interface methods for inserting positions are implemented
 * separately in order to allow greater constant-factor efficiency
 * and comprehensibility in
 * the Sequence insertion methods and to allow later separation of their
 * functionality.
 * @author Benoit Hudson
 * @author Mark Handy
 * @author Andrew Schwerin
 * @author Ryan Shaun Baker
 * @version JDSL 2.1.1 
 */
public class NodeSequence extends AbstractPositionalContainer 
  implements Sequence {


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

  /**
    * The first and last nodes of the Sequence
    */
    private FNSNode tail_, head_;

  /**
    * Cache for positions and elements; discarded upon modification
    */
    private Position positions_[] = null;
    private Object elements_[] = null;


  /**
    * The default constructor for NodeSequence, as well as the only one.
    */
    public NodeSequence() {
        super();
    }
    public Container newContainer() {
        return new NodeSequence();
    }

   
  /**
    * O(1) time
    */
    public Position first() throws EmptyContainerException {
        checkEmpty();
        return head_;
    }

  /**
    * O(1) time
    */
    public Position last() throws EmptyContainerException {
        checkEmpty();
        return tail_;
    }


  /**
    * O(1) time
    */
    public boolean isFirst (Position p) throws InvalidAccessorException {
        castPosition (p);
        return (p==head_);
    }

  /**
    * O(1) time
    */
    public boolean isLast (Position p) throws InvalidAccessorException  {
        castPosition (p);
        return (p==tail_);
    }

  /**
    * O(1) time if the positions_ cache is valid (no modifications since
    * cache was generated)
    * O(N) if cache is invalid (must traverse up to half of Sequence)
    */
    public Position atRank (int rank) throws BoundaryViolationException {
        checkRank (rank);

        // if the positions_ cache is valid, we can return in O(1) time
        if(positions_!=null) {
            return positions_[rank];
        }

        // otherwise, iterate through the list
        else {
	  //we save half of N by going from the appropriate end
	  if (rank<=size()/2){
            FNSNode cur = head_;
            for(int i=0; i<rank; i++)  {
                cur = cur.next();
            }
            return cur;
	  }
	  else{
            FNSNode cur = tail_;
            for(int i=size()-1; i>rank; i--)  {
                cur = cur.prev();
            }
            return cur;
	  }
	    
        }
    }

  /**
    * O(1) time if the positions_ cache is valid (no modifications since
    * cache was generated)
    * O(N) if cache is invalid (must traverse rank elements of Sequence)
    */ 
    public int rankOf (Position p) throws InvalidAccessorException {
        FNSNode n = castPosition(p);

        // if the positions_ cache is valid, we can iterate through an array
        if(positions_!=null) {
            for(int i=0; i<positions_.length; i++) {
                if(positions_[i]==p) return i;
            }
            // to placate the compiler:
            throw new RuntimeException
                ("Internal error: "+p+" is valid but not found");
        } else {
            // otherwise, iterate through the list (backwards)
            int rank=0;
            while(n!=head_) { rank++; n = n.prev(); }
            return rank;
        }
    }    

  /**
    * O(1) time
    */
    public Position before (Position p) throws InvalidAccessorException { 
      FNSNode n = castPosition(p);
      if(n==head_) 
	throw new BoundaryViolationException("At first element");
      return n.prev();
    }

  /**
    * O(1) time
    */
    public Position after (Position p) throws InvalidAccessorException {
      FNSNode n = castPosition(p);
      if(n==tail_) 
	throw new BoundaryViolationException("At last element");
      return n.next();
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Position insertBefore (Position p, Object elt)
                                  throws InvalidAccessorException  { 
	Position nu = new FNSNode(elt);
	posInsertBefore(p, nu);
        return nu;
    } 

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Position insertFirst(Object elt) throws InvalidAccessorException {
  	Position nu = new FNSNode(elt);
	if (isEmpty())
	  posInsertOnly(nu);
	else
	  posInsertBefore(head_, nu);
        return nu; 
    } 

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Position insertAfter (Position p, Object elt)
        throws InvalidAccessorException {
	  Position nu = new FNSNode(elt);
	  posInsertAfter(p, nu);
	  return nu;
    }

  /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Position insertLast(Object elt)
        throws InvalidAccessorException {
	  Position nu = new FNSNode(elt);
	  if (isEmpty())
	    posInsertOnly(nu);
	  else
	    posInsertAfter(tail_, nu);
	  return nu; 
        }

   /**
    * This method also clears the position cache.
    * O(1) time
    */
    public Position insertAtRank (int rank, Object elt)
           throws InvalidAccessorException, BoundaryViolationException  {
        if (rank == 0)      { return insertFirst(elt); }
        if (rank == size()) { return insertLast (elt); }
        checkRank (rank);
        return insertAfter(atRank(rank-1),elt);
    }

  /**
    * This method inserts a position into an empty Sequence.
    * It also clears the position cache
    * @param toInsert The Position to Insert
    * O(1) time
    */
  private void posInsertOnly(Position toInsert) 
                              throws InvalidAccessorException{
    try{
      FNSNode toins = (FNSNode)toInsert;
      head_ = toins;
      tail_ = toins;
      size_ = 1;
      toins.setContainer(this);
      toins.setPrev(null);
      toins.setNext(null);
      positions_ = null;
      elements_ = null;
    }
    catch(ClassCastException cce){
      throw new InvalidAccessorException
	("Wrong class " + toInsert.getClass() );
    }
  }


   /**
 * Make 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
    * This method also clears the position cache.
    * O(1) time
    */
  public void posInsertFirst( Position toInsert ) 
                              throws InvalidAccessorException {
    if (isEmpty())
      posInsertOnly(toInsert);
    else
      posInsertBefore(head_, toInsert);
  }

  /**
 * Make 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
    * This method also clears the position cache.
    * O(1) time
    */
  public void posInsertLast( Position toInsert ) 
                             throws InvalidAccessorException {
    if (isEmpty())
      posInsertOnly(toInsert);
    else
      posInsertAfter(tail_, toInsert);
  }

  /**
 * Make 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 if willBeSuccessor
 * is invalid for one of the usual invalid-position reasons
    * This method also clears the position cache.
    * O(1) time
    */
  public void posInsertBefore( Position willBeSuccessor, Position toInsert ) 
                               throws InvalidAccessorException {

    if (contains(toInsert))
      throw new InvalidAccessorException
	("This container already contains that position.");

    // clear the caches
    positions_= null;
    elements_= null;
    
    FNSNode fwillbesucc = castPosition(willBeSuccessor);
    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(fwillbesucc==head_) { //We're de-facto inserting first
      ftoInsert.setPrev(null);
      ftoInsert.setNext(fwillbesucc);
      ftoInsert.setContainer(this);
      
      fwillbesucc.setPrev(ftoInsert);

      head_ = ftoInsert;
      if(tail_ == null) 
	tail_ = head_;
    } else {//inserting somewhere in the middle
      ftoInsert.setPrev(fwillbesucc.prev());
      fwillbesucc.prev().setNext(ftoInsert);
      ftoInsert.setNext(fwillbesucc);
      fwillbesucc.setPrev(ftoInsert);
      ftoInsert.setContainer(this);
    }
    size_++;
  }
  
  /**
 * Make toInsert the successor of willBePredecessor
 * @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 if willBePredecessor
 * is invalid for one of the usual invalid-position reasons
    * This method also clears the position cache.
    * O(1) time
    */