Conditional Selection: MarkovMatrix

/**
 * The {@link TypeOfMatrix} class provides a bass class for matrix types.
 * Overrides to {@link TypeOfMatrix#createMatrix(WriteableEntity, int)},
 * and {@link TypeOfMatrix#createState(MarkovMatrix, int)}
 * @author Charles Ames
 */
public abstract class TypeOfMatrix {
   private String name;
   private static SortedMap<String, TypeOfMatrix> matrixTypes = null;
   private static TypeOfMatrix defaultMatrixType = null;
   /**
    * Constructor for {@link TypeOfMatrix} instances.
    * @param name The instance name, which may not be null or blank and
    * which must be unique for each instance.
    */
   protected TypeOfMatrix(String name) {
      this.name = name;
      StringMethods.checkName(name, false, false);
      if (null == matrixTypes)
         matrixTypes = new TreeMap<String, TypeOfMatrix>();
      if (matrixTypes.containsKey(name))
         throw new IllegalArgumentException(
            "There is alreay a matrix type named " + name);
      matrixTypes.put(name, this);
   }
   /**
    * Get the name.
    * @return The assigned name.
    */
   public String getName() {
      return name;
   }
   @Override
   public String toString() {
      return name;
   }
   /**
    * Get the matrix types.
    * @return A collection of {@link TypeOfMatrix} instances,
    * indexed by type name.
    */
   public static SortedMap<String, TypeOfMatrix> getMatrixTypes() {
      return matrixTypes;
   }
   /**
    * Find the {@link TypeOfMatrix} instance with the indicated
    * name.
    * @param name The indicated name.
    * @return The {@link TypeOfMatrix} instance with the indicated
    * name.
    * @throws RuntimeException when no {@link TypeOfMatrix}
    * instance has the indicated name.
    */
   public static TypeOfMatrix find(String name) {
      TypeOfMatrix result;
      if (name.equals("Pitch"))
         result = matrixTypes.get("Notes");
      else
         result = matrixTypes.get(name);
      if (null == result)
         throw new RuntimeException(
            "Invalid matrix type [" + name + "]");
      return result;
   }
   /**
    * Test if a {@link TypeOfMatrix} instances exists
    * with the indicated name.
    * @param name The indicated name.
    * @return True if a {@link TypeOfMatrix} instances
    * exists with the indicated name; false otherwise.
    */
   public static boolean exists(String name) {
      if (null == matrixTypes) return false;
      TypeOfMatrix matrixType = matrixTypes.get(name);
      return (null != matrixType);
   }
   /**
    * Create a matrix whose class is an extension of
    * {@link MarkovMatrix}.
    * @param container The {@link WriteableEntity} to which
    * the matrix will belong.
    * @param order The number of previous states upon which
    * new-state selection is conditioned.
    * @return The newly created {@link MarkovMatrix} instance.
    */
   public abstract MarkovMatrix createMatrix(
         WriteableEntity container, int order);
   /**
    * Create a state whose class is an extension of {@link MarkovState}.
    * @param matrix The matrix to which the state will belong.
    * @param id The state id.
    * @return The newly created {@link MarkovState} instance.
    */
   public abstract MarkovState createState(MarkovMatrix matrix, int id);
   /**
    * Get a {@link TypeOfMatrix} instance named Default where
    * {@link TypeOfMatrix#createMatrix(WriteableEntity, int)}
    * returns a {@link MarkovMatrix} instance and {@link
    * TypeOfMatrix#createState(MarkovMatrix, int)}
    * returns a {@link MarkovState} instance.
    * @return The default {@link TypeOfMatrix} instance.
    */
   public static TypeOfMatrix getDefaultMatrixType() {
      if (null == defaultMatrixType) {
         defaultMatrixType = new TypeOfMatrix("Default") {
            @Override
            public MarkovMatrix createMatrix(
                  WriteableEntity container, int order) {
               MarkovMatrix matrix = new MarkovMatrix(container);
               matrix.setType(this);
               matrix.setOrder(order);
               return matrix;
            }
            @Override
            public MarkovState createState(
                  MarkovMatrix matrix, int id) {
               return new MarkovState(matrix, id);
            }

         };
      }
      return defaultMatrixType;
   }
}

/**
 * The {@link MarkovMatrix} class implements the matrix of conditional
 * probabilities (weights) which can be used to generate a Markov chain.
 * @author Charles Ames
 */
public class MarkovMatrix
extends WriteableEntity implements Indexer {
   /**
    * Modes of selecting successive states when generating a chain.
    * @author Charles Ames
    */
   public enum SelectionMode {
      /**
       * Choose next state by weighted randomness.
       */
      RANDOM {
         @Override
         protected void initializeUsages(MarkovMatrix markovMatrix) {
            // Do nothing
         }
         @Override
         protected MarkovTransition chooseNextTransition(MarkovMatrix matrix, double accent) {
            MarkovSource currentSource = matrix.getCurrentSource();
            if (null == currentSource)
               throw new RuntimeException("No previous source");
            MarkovTransition bestTransition = null;
            double transitionTotal = currentSource.getTransitionTotal();
            if (MathMethods.TINY > transitionTotal)
               throw new RuntimeException(
                  "No choosable transition from " + currentSource.getKey().toString());
            Collection<MarkovTransition> transitions = currentSource.getTransitions().values();
            double u = SharedRandomGenerator.getSingleton().getRandom().nextDouble();
            double chooser = u * transitionTotal;
            for (MarkovTransition transition : transitions) {
               double weight = transition.getWeight();
               if (chooser <= weight) {
                  bestTransition = transition;
                  break;
               }
               chooser -= weight;
            }
            if (null == bestTransition) {
               throw new RuntimeException(
                  "No choosable transition from " + currentSource.getKey().toString());
            }
            return bestTransition;
         }
      },
      /**
       * Choose next state by statistical feedback upon state usages.
       */
      BALANCED_STATES {
         @Override
         protected void initializeUsages(MarkovMatrix matrix) {
            for (MarkovState state : matrix.states.values()) {
               state.setUsage(0.);
            }
         }
         @Override
         protected MarkovTransition chooseNextTransition(MarkovMatrix matrix, double accent) {
            MarkovSource currentSource = matrix.getCurrentSource();
            if (null == currentSource)
               throw new RuntimeException("No previous source");
            MarkovTransition bestTransition = null;
            double transitionTotal = currentSource.getTransitionTotal();
            if (MathMethods.TINY > transitionTotal)
               throw new RuntimeException(
                  "No choosable transition from " + currentSource.getKey().toString());
            Collection<MarkovTransition> transitions = currentSource.getTransitions().values();
            double chooser = Double.MAX_VALUE;
            double bestWeight = 1.;
            double heterogeneity = matrix.getHeterogeneity();
            for (MarkovTransition transition : transitions) {
               MarkovState target = transition.getTarget();
               double weight = transition.getWeight() / transitionTotal;
               double u = SharedRandomGenerator.getSingleton().getRandom().nextDouble() - 0.5;
               double preference = target.getUsage() + ((accent + heterogeneity * u) / weight);
               if (preference < chooser) {
                  bestTransition = transition;
                  chooser = preference;
                  bestWeight = weight;
               }
            }
            if (null == bestTransition) {
               throw new RuntimeException(
                  "No choosable transition from " + currentSource.getKey().toString());
            }
            bestTransition.getTarget().incrementUsage(accent / bestWeight);
            matrix.normalizeStateUsages();
            return bestTransition;
         }
      },
      /**
       * Choose next state by statistical feedback upon transition usages.
       */
      BALANCED_TRANSITIONS {
         @Override
         protected void initializeUsages(MarkovMatrix matrix) {
            for (MarkovSource source : matrix.sources.values()) {
               for (MarkovTransition transition : source.getTransitions().values()) {
                  transition.setUsage(0.);
               }
            }
         }
         @Override
         protected MarkovTransition chooseNextTransition(MarkovMatrix matrix, double accent) {
            MarkovSource currentSource = matrix.getCurrentSource();
            if (null == currentSource)
               throw new RuntimeException("No previous source");
            MarkovTransition bestTransition = null;
            double transitionTotal = currentSource.getTransitionTotal();
            if (MathMethods.TINY > transitionTotal)
               throw new RuntimeException(
                  "No choosable transition from " + currentSource.getKey().toString());
            Collection<MarkovTransition> transitions = currentSource.getTransitions().values();
            double chooser = Double.MAX_VALUE;
            double bestWeight = 1.;
            double heterogeneity = matrix.getHeterogeneity();
            for (MarkovTransition transition : transitions) {
               double weight = transition.getWeight() / transitionTotal;
               double u = SharedRandomGenerator.getSingleton().getRandom().nextDouble() - 0.5;
               double preference = transition.getUsage() + ((accent + heterogeneity * u) / weight);
               if (preference < chooser) {
                  bestTransition = transition;
                  chooser = preference;
                  bestWeight = weight;
               }
            }
            if (null == bestTransition) {
               throw new RuntimeException(
                  "No choosable transition from " + currentSource.getKey().toString());
            }
            bestTransition.incrementUsage(accent / bestWeight);
            currentSource.normalizeTransitionUsages();
            return bestTransition;
         }
      };
      /**
       * Zero out the usage for each state.
       * @param matrix Which {@link MarkovMatrix} instance is initializing.
       */
      protected abstract void initializeUsages(MarkovMatrix matrix);
      /**
       * Choose the next transition available to the matrix's current source.
       * @param matrix Which {@link MarkovMatrix} instance is choosing.
       * @param accent Stress associated with the current sequence element.
       * @return The chosen {@link MarkovTransition} instance.
       */
      protected abstract MarkovTransition chooseNextTransition(MarkovMatrix matrix, double accent);
   }
   /**
    * Number of consecutive states to define matrix source.
    */
   private int order;
   /**
    * Type of matrix:
    */
   private TypeOfMatrix matrixType;
   /**
    * Stress for upcoming selection.
    */
   private double stress;
   private int cycleCount;
   private double sourceTotal;
   private double steadyStateTotal;
   private MarkovSource currentSource;
   //private boolean active;
   /**
    * Override flag.  When true, the initial state id of a generated chain
    * has been prescribed manually.  When false, the initial value will be
    * selected by the {@link #chooseFirst()} method.
    */
   private boolean override;
   /**
    * Maximum chain length.
    */
   private int maxChainLength;
   /**
    * Seed for the random number generator prior to generating a chain.  Must
    * not be negative.  When 0, the random seed is sampled from the system
    * clock.
    */
   private long seed;
   /**
    * Output file format.
    */
   private OutputFormat outputFormat;
   /**
    * Mode for selecting chain elements: {@link SelectionMode#RANDOM},
    * {@link SelectionMode#BALANCED_STATES}, or
    * {@link SelectionMode#BALANCED_TRANSITIONS}.
    */
   private SelectionMode selectionMode;
   /**
    * Controls bluntness of knife-edge for
    * {@link SelectionMode#BALANCED_STATES}
    * and {@link SelectionMode#BALANCED_TRANSITIONS} selection modes.
    * Must be positive.
    * Values significantly smaller than unity (e.g. 0.1) introduce
    * randomness only when choices are in balance.  Values on the order
    * of unity (or greater) increase chances of selecting over-
    * balanced choices.
    */
   private double heterogeneity;
   private IntArray scratchKey;
   private SortedMap<Integer, MarkovState> states;
   private SortedMap<IntArray, MarkovSource> sources;
   private boolean steadyStateAnalyzed;
   private int indexDigits = 1;
   private DecimalFormat indexFormat = new DecimalFormat("0");
   /**
    * Constructor for {@link MarkovMatrix} instances.
    * @param container The matrix container (may be null).
    */
   protected MarkovMatrix(WriteableEntity container) {
      super(container);
      this.setIDQuality(Entity.AttributeQuality.MODIFIABLE);
      this.setNameQuality(Entity.AttributeQuality.MODIFIABLE);
      this.order = Integer.MIN_VALUE;
      this.scratchKey = null;
      this.sourceTotal = 0.;
      this.states = new TreeMap<Integer, MarkovState>();
      this.sources = new TreeMap<IntArray, MarkovSource>();
      this.selectionMode = SelectionMode.RANDOM;
      this.steadyStateTotal = 0.;
      this.stress = 1.0;
      this.heterogeneity = 0.1;
      this.steadyStateAnalyzed = false;
      this.outputFormat = null;
      this.indexDigits = 1;
      this.indexFormat = new DecimalFormat("0");
      this.currentSource = null;
   }
   @Override
   public boolean setName(String name) {
      boolean result = false;
      String oldName = getOldName();
      if (name.equals(oldName)) return result;
      result = super.setName(name);
      return result;
   }
   /**
    * Setter for {@link #matrixType}.
    * @param matrixType The intended {@link #matrixType} value.
    * @throws UnsupportedOperationException when {@link #matrixType}
    * was previously initialized.
    */
   public void setType(TypeOfMatrix matrixType) {
      if (null != this.matrixType)
         throw new UnsupportedOperationException(
            "Matrix type previously initialized");
      if (null == matrixType)
         throw new IllegalArgumentException(
            "Null argument");
      this.matrixType = matrixType;
   }
   /**
    * Get the matrix type.
    * @return The assigned matrix type.
    */
   public TypeOfMatrix getType() {
      if (null == matrixType)
         throw new UninitializedException(
            "Matrix type uninitialized");
      return matrixType;
   }
   /**
    * Setter for {@link #order}.
    * @param order The intended {@link #order} value.
    * @throws IllegalArgumentException when the matrix order
    * is not positive.
    * @throws UnsupportedOperationException when {@link #order}
    * was previously initialized.
    */
   public void setOrder(int order) {
      if (Integer.MIN_VALUE != this.order)
         throw new UnsupportedOperationException(
            "Order previously initialized");
      if (1 > order)
         throw new IllegalArgumentException(
            "Argument not positive.");
      this.order = order;
      this.scratchKey = allocateSourceKey();
   }
   /**
    * Getter for {@link #order}.
    * @return The assigned {@link #order} value.
    * @throws UninitializedException when {@link #order}
    * has not been initialized.
    */
   public int getOrder() {
      if (Integer.MIN_VALUE == order)
         throw new UninitializedException(
            "Matrix order uninitialized");
      return order;
   }
   /**
    * Test if the matrix is first order.
    * @return True if the matrix is first order; false otherwise.
    * @throws UninitializedException when {@link #order} has not
    * been initialized.
    */
   public boolean isFirstOrder() {
      return 1 == getOrder();
   }
   /**
    * Getter for {@link #currentSource}.
    * @return The assigned {@link #currentSource} value.
    */
   protected MarkovSource getCurrentSource() {
      return currentSource;
   }
   /**
    * Setter for {@link #order}.
    * @param source The intended {@link #currentSource} value.
    */
   protected void setCurrentSource(MarkovSource source) {
      this.currentSource = source;
   }
   /**
    * Copy this matrix into the target container.
    * @param targetContainer The target container.
    * @param name The matrix name in the target container.
    * @return The newly created {@link MarkovMatrix} instance.
    */
   public MarkovMatrix copy(WriteableEntity targetContainer,
         String name) {
      getType().createMatrix(targetContainer, getOrder());
      MarkovMatrix target = new MarkovMatrix(targetContainer);
      target.setName(name);
      target.copyFrom(this, CopyOption.CLEAR);
      return target;
   }
   /**
    * Copy this matrix into the target container, using the same
    * name.
    * @param targetContainer The target container.
    * @return The newly created {@link MarkovMatrix} instance.
    */
   public MarkovMatrix copy(WriteableEntity targetContainer) {
      return copy(targetContainer, getName());
   }
   /**
    * Create an {@link IntArray} instance sized to the order of
    * this matrix.
    * @return The newly allocated {@link IntArray} instance.
    */
   public IntArray allocateSourceKey() {
      return new IntArray(getOrder());
   }
   /**
    * Find the {@link MarkovSource} instance corresponding to the
    * indicated sequence of states.
    * @param states The indicated sequence of states.
    * @return The {@link MarkovSource} instance corresponding
    * to the indicated sequence of states.
    * @throws IllegalArgumentException when the state array length
    * is incompatible with the matrix order.
    * @throws NoSuchObjectException when no source possesses the
    * indicated sequence of states.
    */
   public MarkovSource findSource(List<MarkovState> states) {
      if (states.size() != getOrder()) {
         throw new IllegalArgumentException(
            "State sequence length " + states.size()
            + " incompatible with matrix order " + order);
      }
      for (int position = 0; position < order; position++) {
         scratchKey.insertMember(states.get(position).getID(), position);
      }
      MarkovSource source = getSource(scratchKey);
      if (null == source)
         throw new NoSuchObjectException(
            "No source found with key " + scratchKey.toString());
      return source;
   }
   @Override
   public void makeDirty() {
      try {
         WriteableEntity container = (WriteableEntity)getContainer();
         container.makeDirty();
      }
      catch (NoSuchObjectException e) {
      }
      this.steadyStateAnalyzed = false;
   }
   /**
    * Check at least one state having no transitions to other
    * states.
    * @return true if one or more states cannot transition to
    * any other state; false otherwise.
    */
   public boolean hasTerminalState() {
      for (MarkovState state : states.values()) {
         if (state.isTerminal()) return true;
      }
      return false;
   }
   /**
    * Getter for {@link #override}.
    * @return The assigned {@link #override} value.
    */
   public boolean isOverride() {
      return override;
   }
   /**
    * Setter for {@link #override}.
    * @param override The intended {@link #override} value.
    */
   public void setOverride(boolean override) {
      this.override = override;
   }
   /**
    * Getter for {@link #maxChainLength}.
    * @return The assigned {@link #maxChainLength} value.
    */
   public int getMaxChainLength() {
      return maxChainLength;
   }

   /**
    * Setter for {@link #maxChainLength}.
    * @param limit The intended {@link #maxChainLength} value.
    * @return true if the value differs from the old value;
    * false otherwise.
    */
   public boolean setMaxChainLength(int limit) {
      boolean changed = false;
      if (this.maxChainLength != limit) {
         this.maxChainLength = limit;
         changed = true;
         makeDirty();
      }
      return changed;
   }
   /**
    * Getter for {@link #seed}.
    * @return The assigned {@link #seed} value.
    */
   public long getSeed() {
      return seed;
   }
   /**
    * Setter for {@link #seed}.
    * @param seed The intended {@link #seed} value.
    * @return true if the value differs from the old value;
    * false otherwise.
    */
   public boolean setSeed(long seed) {
      boolean changed = false;
      if (this.seed != seed) {
         this.seed = seed;
         makeDirty();
         changed = true;
      }
      return changed;
   }
   /**
    * Getter for {@link #outputFormat}.
    * @return The assigned {@link #outputFormat} value.
    */
   public final OutputFormat getOutputFormat() {
      return outputFormat;
   }
   /**
    * Setter for {@link #outputFormat}.
    * @param outputFormat The intended {@link #outputFormat}
    * value.
    * @return true if the value differs from the old value;
    * false otherwise.
    */
   public boolean setOutputFormat(OutputFormat outputFormat) {
      boolean changed = false;
      if (this.outputFormat != outputFormat) {
         this.outputFormat = outputFormat;
         makeDirty();
         changed = true;
      }
      return changed;
   }
   /**
    * Check if the indicated file is consistent with
    * {@link #outputFormat}.
    * @param file The indicated file.
    * @return True if the indicated file is consistent with
    * {@link #outputFormat}; false otherwise.
    */
   public final String checkFileExtension(File file) {
      String actualFileExtension = FileMethods.getFileExtension(file);
      String expectedFileExtension = getOutputFormat().getExtension();
      if (!expectedFileExtension.equals(actualFileExtension)) {
         throw new IllegalArgumentException(
            "File extension is [" + actualFileExtension
            + "], expected " + expectedFileExtension);
      }
      return actualFileExtension;
   }
   /**
    * Getter for {@link #selectionMode}.
    * @return The assigned {@link #selectionMode} value.
    */
   public SelectionMode getSelectionMode() {
      return selectionMode;
   }
   /**
    * Setter for {@link #selectionMode}.
    * @param selectionMode The intended {@link #selectionMode} value.
    * @return true if the value differs from the old value; false otherwise.
    */
   public boolean setSelectionMode(SelectionMode selectionMode) {
      boolean changed = false;
      if (this.selectionMode != selectionMode) {
         this.selectionMode = selectionMode;
         makeDirty();
         changed = true;
      }
      return changed;
   }
   /**
    * Getter for {@link #stress}.
    * @return The assigned {@link #stress} value.
    * @throws UninitializedException when the {@link #stress}
    * value is uninitialized.
    */
   public double getStress() {
      if (Double.isNaN(stress))
         throw new UninitializedException("Stress not initialized");
      return stress;
   }
   /**
    * Setter for {@link #stress}.
    * @param stress The intended {@link #stress} value.
    * @return True if {@link #stress} has changed; false otherwise.
    * @throws IllegalArgumentException when the argument is not positive.
    */
   public boolean setStress(double stress) {
      if (stress < MathMethods.TINY)
         throw new IllegalArgumentException(
            "Stress must be positive");
      if (this.stress != stress) {
         this.stress = stress;
         makeDirty();
         return true;
      }
      return false;
   }
   /**
    * Getter for {@link #heterogeneity}.
    * @return The assigned {@link #heterogeneity} value.
    */
   public double getHeterogeneity() {
      return heterogeneity;
   }
   /**
    * Setter for {@link #heterogeneity}.
    * @param heterogeneity The intended {@link #heterogeneity} value.
    * @return true if the value differs from the old value;
    * false otherwise.
    */
   public boolean setHeterogeneity(double heterogeneity) {
      if (heterogeneity < MathMethods.TINY)
         throw new IllegalArgumentException(
            "Heterogeneity must be positive");
      boolean changed = false;
      if (this.heterogeneity != heterogeneity)  {
         this.heterogeneity = heterogeneity;
         changed = true;
         makeDirty();
      }
      return changed;
   }

   @Override
   public int getLimit() {
      if (0 == states.size()) return 0;
      return states.lastKey() + 1;
   }
   /**
    * Get all matrix states.
    * @return A collection of {@link MarkovState} instances,
    * indexed by state id.
    */
   public SortedMap<Integer, MarkovState> getStates() {
      return states;
   }
   /**
    * Get all matrix sources.
    * @return A collection of {@link MarkovSource} instances,
    * indexed by state-id arrays.
    */
   public SortedMap<IntArray, MarkovSource> getSources() {
      return sources;
   }
   /**
    * Create a new {@link MarkovChain} instance.
    * @return The newly created {@link MarkovChain} instance.
    */
   public MarkovChain createChain() {
      return new MarkovChain(this);
   }
   /**
    * Get the matrix state with the indicated id.
    * @param id The indicated id.
    * @return The matrix state with the indicated id.
    * @throws NoSuchObjectException when there is no
    * state with the indicated id.
    */
   public MarkovState getState(int id) {
      MarkovState state = states.get(id);
      if (null == state) {
         throw new NoSuchObjectException(
            "There is no state with id [" + id + "]");
      }
      if (state.getID() != id)
         throw new RuntimeException("Programmer error");
      return state;
   }
   /**
    * Test if the matrix contains a state with the indicated id.
    * @param id The indicated id.
    * @return True if the matrix contains a state with the
    * indicated id; false otherwise.
    */
   public boolean hasState(int id) {
      return getStates().containsKey(id);
   }
   /**
    * Create a new state with the indicated id.
    * @param id The indicated id.
    * @return The newly created state.
    * @throws IllegalArgumentException when there is already a
    * state with the indicated id.
    */
   public MarkovState createState(int id) {
      if (hasState(id)) {
         throw new IllegalArgumentException(
            "There is already a state with id [" + id + "]");
      }
      MarkovState result = matrixType.createState(this, id);
      states.put(id, result);
      refreshIndexFormat();
      makeDirty();
      return result;
   }
   /**
    * Test if the number of digits in the number of states has changed
    * and, if so, rebuild the format to reflect this.
    */
   private void refreshIndexFormat() {
      int magnitude = states.size();
      int digits;
      if (0 == magnitude)
         digits = 1;
      else
         digits = 1 + (int) Math.floor(Math.log10(magnitude));
      if (indexDigits != digits) {
         indexDigits = digits;
         String pattern = StringUtils.repeat("0",digits);
         indexFormat = new DecimalFormat(pattern);
      }
   }
   /**
    * Getter for {@link #indexFormat}.
    * @return A {@link DecimalFormat} with enough 0-padded digits to
    * accommodate all state indices.
    */
   public DecimalFormat getIndexFormat() {
      return indexFormat;
   }
   /**
    * Remove the indicated state.
    * @param state The indicated state.
    */
   public void removeState(MarkovState state) {
      if (this != state.getContainer())
         throw new IllegalArgumentException(
            "State does not belong to this matrix");
      int id = state.getID();
      // first remove all transitions to the state that's going away
      for (MarkovSource source : sources.values()) {
         if (source.getTransitions().containsKey(id))
            source.removeTransition(id);
      }
      // next delete all sources that reference the state.
      Iterator<MarkovSource> iterator = sources.values().iterator();
      while (iterator.hasNext()) {
         MarkovSource source = iterator.next();
         if (source.getKey().contains(id)) {
            iterator.remove();
            source.dispose();
         }
      }
      states.remove(id);
      state.dispose();
      refreshIndexFormat();
      makeDirty();
   }
   /**
    * Remove the state with the indicated id.
    * @param id The indicated id.
    */
   public void removeState(int id) {
      MarkovState state = getState(id);
      removeState(state);
   }
   /**
    * Remove the indicated source.
    * @param source The indicated source.
    * @throws IllegalArgumentException when the argument is null.
    */
   public void removeSource(MarkovSource source) {
      if (null == source)
         throw new IllegalArgumentException("Null source");
      source.detach();
      source.dispose();
      makeDirty();
   }
   /**
    * Get an array covering all the {@link MarkovState} instances of
    * this matrix.
    * @return An array of {@link MarkovState} instances.
    */
   public MarkovState[] getStateArray() {
      int size = states.size();
      MarkovState[] result = new MarkovState[size];
      int index = 0;
      for (MarkovState state : states.values()) {
         result[index++] = state;
      }
      return result;
   }
   /**
    * Create a new {@link MarkovSource} instance from the indicated key.
    * @param key identifies a particular combination of states.
    * @return The newly created {@link MarkovSource} instance.
    * @throws RuntimeException When the particular combination of states
    * already exists.
    */
   public MarkovSource createSource(IntArray key) {
      MarkovSource source = new MarkovSource(this);
      for (int position = 0; position < order; position++) {
         int stateID = key.memberAt(position);
         MarkovState state = states.get(stateID);
         source.addState(state);
      }
      source.attach();
      return source;
   }
   /**
    * Get the matrix source with the indicated key.
    * @param key The indicated key.
    * @return The matrix source with the indicated id.
    * @throws NoSuchObjectException when there is no source with the indicated key.
    */
   public MarkovSource getSource(IntArray key) {
      if (null == key)
         throw new IllegalArgumentException("Null source key");
      MarkovSource source = sources.get(key);
      if (null == source) {
         throw new NoSuchObjectException(
            "There is no source with state sequence [" + key.toString() + "]");
      }
      return source;
   }
   /**
    * Enumerate undefined sources.
    * @param keys The receiving collection of {@link IntArray} instances.
    * The method starts out by clearing this list.
    */
   public void enumerateUndefinedSources(List<IntArray> keys) {
      keys.clear();
      enumerateUndefinedSources(keys, scratchKey.itemCount(), scratchKey);
   }
   /**
    * Enumerate undefined sources.
    * @param keys The receiving collection of {@link IntArray} instances.
    * The method starts out by clearing this list.
    * @param right How many key positions to fill.  May be
    * workingKey.itemCount when the rightmost state is unknown or
    * workingKey.itemCount-1 when the rightmost state has been filled
    * in to workingKey.
    * @param workingKey An {@link IntArray} instance whose array length
    * corresponds to the order of this matrix.
    * @throws IllegalArgumentException when the right argument is not either
    * workingKey.itemCount() or workingKey.itemCount()-1.
    */
   public void enumerateUndefinedSources(List<IntArray> keys,
         int right, IntArray workingKey) {
      SortedMap<Integer, MarkovState> states = getStates();
      int itemCount = workingKey.itemCount();
      if (right < itemCount - 1 || right > itemCount) {
         throw new IllegalArgumentException(
            "Right " + right + " itemCount " + itemCount);
      }
      if (0 == states.size()) return;
      int limit = states.lastKey();
      int iterationLimit = 0;
      int n = 1;
      for (int position = 0; position < right; position++) {
         n *= (limit+1);
         iterationLimit += n;
      }
      int position = 0;
      workingKey.insertMember(-1, position);
      int iterationCount = 0;
      boolean done = false;
      for (;;) {
         int stateID = workingKey.memberAt(position) + 1;
         workingKey.insertMember(stateID, position);
         while (stateID > limit) {
            --position;
            if (position < 0) {
               done = true;
               break;
            }
            stateID = workingKey.memberAt(position) + 1;
            workingKey.insertMember(stateID, position);
         }
         if (done) break;
         if (states.containsKey(stateID)) {
            ++position;
            if (position == right) {
               if (!sources.containsKey(workingKey)) {
                  IntArray undefinedKey = workingKey.copy();
                  keys.add(undefinedKey);
               }
               --position;
            }
            else {
               workingKey.insertMember(-1, position);
            }
         }
         if (++iterationCount > iterationLimit)
            throw new RuntimeException(
               "Iteration count exceeds limit of " + iterationLimit);
      }
   }
   /**
    * Get the next available state id.
    * @return The highest existing state id, plus 1.  0 if the matrix
    * presently has no states.
    */
   public int getNextStateID() {
      if (0 == states.size()) {
         return 0;
      }
      else {
         return states.lastKey() + 1;
      }
   }
   /**
    * Change the id of a state with the indicated old id to the
    * indicated new id.
    * @param oldID The indicated old id.
    * @param newID The indicated new id.
    */
   public void changeStateID(int oldID, int newID) {
      if (oldID == newID) return;
      if (!hasState(oldID))
         throw new IllegalArgumentException(
            "There is no state with id [" + oldID + "]");
      int maxID = getNextStateID();
      if (0 > newID || newID > maxID)
         throw new IllegalArgumentException(
            "New state id [" + newID + "] out of range from 0 to " + maxID);
      if (hasState(newID)) {
         throw new IllegalArgumentException(
            "There is already a state with id [" + newID + "]");
      }
      List<MarkovSource> affectedSources = new ArrayList<MarkovSource>();
      MarkovState state = getState(oldID);
      for (MarkovSource source : sources.values()) {
         boolean flag = false;
         for (int position = 0; position < order; position++) {
            if (state == source.getState(position)) {
               flag = true;
               break;
            }
         }
         if (flag) {
            affectedSources.add(source);
         }
      }
      states.remove(oldID);
      state.setID(newID);
      states.put(newID, state);
      for (MarkovSource source : affectedSources) {
         source.detach();
         source.attach();
      }
      for (MarkovSource source : sources.values()) {
         SortedMap<Integer, MarkovTransition> sourceTransitions = source.getTransitions();
         MarkovTransition transition = sourceTransitions.get(oldID);
         if (null != transition) {
            sourceTransitions.remove(oldID);
            sourceTransitions.put(newID, transition);
         }
      }
   }
   /**
    * Compact the state id's so that they start with 0 and continue without gaps.
    */
   public void resequenceStates() {
      if (0 == states.size()) return;
      int newID = 0;
      int firstID = states.firstKey();
      int lastID = states.lastKey();
      for (int oldID = firstID; oldID <= lastID; oldID++) {
         if (!hasState(oldID)) continue;
         changeStateID(oldID, newID);
         newID++;
      }
   }
   /**
    * Increase state id's by one, starting with the indicated value.
    * Use this method for closing in gaps after one or more states have been removed.
    * @param id The indicated value.
    */
   public void shiftStatesDown(int id) {
      int highID = id - 1;
      while (hasState(highID + 1)) ++highID;
      shiftStatesDown(id, highID);
   }
   protected void shiftStatesDown(int lowID, int highID) {
      if (lowID > highID) return;
      if (0 == states.size()) return;
      int nextID = highID + 1;
      for (int lastID = highID; lastID >= lowID; lastID--) {
         if (!hasState(lastID)) continue;
         changeStateID(lastID, nextID);
         nextID--;
      }
   }
   /**
    * Decrease state id's by one, starting with the indicated value.
    * Use this method to free up an id that you wish to assign to a new state.
    * @param id The indicated value.
    */
   public void shiftStatesUp(int id) {
      if (0 < states.size()) {
         shiftStatesUp(id, states.lastKey());
      }
   }
   protected void shiftStatesUp(int lowID, int highID) {
      if (lowID > highID) return;
      int lastID = Integer.MAX_VALUE;
      for (int nextID = lowID; nextID <= highID; nextID++) {
         if (!hasState(nextID)) {
            if (Integer.MAX_VALUE == lastID) lastID = nextID;
            continue;
         }
         if (Integer.MAX_VALUE > lastID) {
            changeStateID(nextID, lastID);
            lastID++;
         }
      }
   }
   /**
    * Dereference the state with the indicated old id and change to the new id.
    * This method enhances {@link #changeStateID(int, int)} by
    * pushing down any state already  using the new value.
    * @param oldID The state's original value.
    * @param newID The state's new value.
    */
   public void moveState(int oldID, int newID) {
      if (newID == oldID) return;
      MarkovState state = getState(oldID);
      if (null == state)
         throw new IllegalArgumentException("Invalid state id " + oldID);
      boolean shifted = false;
      if (hasState(newID)) {
         shiftStatesDown(newID);
         shifted = true;
      }
      changeStateID(state.getID(), newID);
      if (shifted) resequenceStates();
   }
   /**
    * Copy states, but NOT sources or transitions, from the source matrix
    * into the current matrix.
    * @param source The source matrix.
    * @param option Indicates how to handle overlaps between corresponding states.
    */
   public void copyStates(MarkovMatrix source, CopyOption option) {
      if (CopyOption.CLEAR == option)
      {
         states.clear();
      }
      for (MarkovState sourceState : source.states.values()) {
         int sourceID = sourceState.getID();
         MarkovState targetState;
         if (hasState(sourceID)) {
            if (CopyOption.OVERWRITE != option) continue;
            targetState = states.get(sourceID);
         }
         else {
            targetState = createState(sourceID);
         }
         targetState.copyObject(sourceState);
      }
   }
   /**
    * Copy sources, but NOT transitions, from the reference matrix into
    * the current matrix.
    * It is assumed that {@link #copyStates(MarkovMatrix, CopyOption)} has just
    * previously been called.
    * @param reference The source matrix.
    * @param option Indicates how to handle overlaps between corresponding states.
    */
   public void copySources(MarkovMatrix reference, CopyOption option) {
      if (CopyOption.CLEAR == option)
      {
         sources.clear();
      }
      for (MarkovSource referenceSource : reference.sources.values()) {
         IntArray key = referenceSource.getKey();
         MarkovSource targetSource = sources.get(key);
         if (null != targetSource) {
            if (CopyOption.OVERWRITE != option) continue;
            targetSource.detach();
         }
         else {
            targetSource = new MarkovSource(this);
         }
         for (int position = 0; position < order; position++) {
            int stateID = referenceSource.getState(position).getID();
            MarkovState state = states.get(stateID);
            targetSource.addState(state);
         }
         targetSource.attach();
      }
   }
   /**
    * Copy states and their transitions from the reference matrix into the current matrix.
    * @param reference The reference matrix.
    * @param option Indicates how to handle overlaps between corresponding
    * states or corresponding transitions.
    * @throws IllegalArgumentException When the reference matrix type is inconsistent.
    * @throws IllegalArgumentException When the reference matrix order is inconsistent.
    */
   public final void copyFrom(MarkovMatrix reference, CopyOption option) {
      if (getType() != reference.getType()) {
         throw new IllegalArgumentException("Inconsistent matrix type");
      }
      if (getOrder() != reference.getOrder()) {
         throw new IllegalArgumentException("Inconsistent matrix order");
      }
      setMaxChainLength(reference.getMaxChainLength());
      setSeed(reference.getSeed());
      setSelectionMode(reference.getSelectionMode());
      setHeterogeneity(reference.getHeterogeneity());
      outputFormat = reference.getOutputFormat();
      this.override = option.chooseField(reference.override, this.override);
      copyStates(reference, option);
      copySources(reference, option);
      for (MarkovSource source : sources.values()) {
         IntArray key = source.getKey();
         SortedMap<IntArray, MarkovSource> referenceSources = reference.getSources();
         if (referenceSources.containsKey(key)) {
            MarkovSource referenceSource = referenceSources.get(key);
            source.copyTransitions(referenceSource, option);
         }
      }
   }
   /**
    * Get the sum of all source starting weights.
    * @return The sum of all source starting weights.
    */
   public double getSourceTotal() {
      return sourceTotal;
   }
   protected void incrementStateTotal(double increment) {
      this.sourceTotal += increment;
   }
   /**
    * Choose a source randomly, based on the the matrix's source starting weights.
    * @return The selected source.
    * @throws RuntimeException when no source has a positive starting weight.
    */
   public MarkovSource chooseFirst() {
      double u = SharedRandomGenerator.getSingleton().getRandom().nextDouble();
      double chooser = u * sourceTotal;
      MarkovSource currentSource = null;
      for (MarkovSource source : sources.values()) {
         double weight = source.getWeight();
         if (chooser <= weight) {
            currentSource = source;
            break;
         }
         chooser -= weight;
      }
      if (null == currentSource)
         throw new RuntimeException("No choosable starting source");
      setCurrentSource(currentSource);
      return currentSource;
   }
   /**
    * Test if the argument is appropriate for use as a weight.
    * @param weight The method argument.
    * @throws IllegalArgumentException if the argument is not positive.
    */
   public static void checkWeight(double weight) {
      if (0. > weight) {
         throw new IllegalArgumentException("Weight may not be negative");
      }
   }
   /**
    * Determine if the selection cycle is ongoing.
    * @return True if the selection cycle is ongoing; false otherwise.
    */
   public boolean hasNextSource() {
      if (null == currentSource) return false;
      double transitionTotal = currentSource.getTransitionTotal();
      return MathMethods.TINY < transitionTotal;
   }
   /**
    * Choose next source, based on the selection mode and the current source's transition weights.
    * @return The selected next source.
    * @throws RuntimeException when the source has no positive transition weights.
    */
   public MarkovSource nextSource() {
      MarkovTransition bestTransition = getSelectionMode().chooseNextTransition(this, getStress());
      return getNextSource(bestTransition.getTarget());
   }
   /**
    * Get the {@link MarkovSource} instance which results from merging
    * the selected {@link MarkovState} instance with the previous {@link MarkovSource}.
    * @param nextState The selected {@link MarkovState} instance.
    * @return The new current {@link MarkovSource} instance.
    */
   public MarkovSource getNextSource(MarkovState nextState) {
      MarkovSource currentSource = getCurrentSource();
      deriveNextKey(scratchKey, currentSource.getKey(), nextState.getID());
      MarkovSource nextSource = sources.get(scratchKey);
      setCurrentSource(nextSource);
      return nextSource;
   }
   /**
    * Transfer all but the first id in fromKey to all but the rightmost position in destKey,
    * then fill in the rightmost position with newID.
    * @param destKey The destination key.
    * @param fromKey The reference key.
    * @param newID The newly selected state id.
    */
   public static void deriveNextKey(IntArray destKey, IntArray fromKey, int newID) {
      int order = destKey.itemCount();
      if (order != fromKey.itemCount())
         throw new IllegalArgumentException("Keys incompatible.");
      for (int position = 1; position < order; position++) {
         destKey.insertMember(fromKey.memberAt(position), position-1);
      }
      destKey.insertMember(newID, order-1);
   }
   /**
    * This method is called by {@link #next()}.
    */
   public void activate() {
      if (!override) {
         SharedRandomGenerator.getSingleton().getRandom().setSeed(seed);
         chooseFirst();
      }
   }
   /**
    * Generate a chain
    * @param chain The {@link MarkovChain} instance which will hold the resulting sequence of
    * {@link MarkovState} references.
    * @param progressMonitor The optional progress monitor, which monitors percent completion and which
    * calling processes can use to abort calculation.
    * @param firstSource The starting {@link MarkovSource} instance, which determines the opening
    * sequence of states.
    */
   public void generate(MarkovChain chain, ProgressMonitor progressMonitor, MarkovSource firstSource) {
      getSelectionMode().initializeUsages(this);
      int limit = getMaxChainLength();
      if (0 == limit) limit = Integer.MAX_VALUE;
      if (null != progressMonitor)  {
         progressMonitor.setActivityMessage("Generating chain");
         progressMonitor.setGoal(limit);
         progressMonitor.start();
      }
      chain.clear();
      SharedRandomGenerator.getSingleton().getRandom().setSeed(getSeed());
      MarkovSource source;
      if (null == firstSource) {
         source = chooseFirst();
      }
      else {
         source = firstSource;
      }
      int index = 0;
      for (int position = 0; position < this.getOrder(); position++) {
         MarkovState state = source.getState(position);
         chain.append(state);
         ++index;
      }
      while (isActive()) {
         if (null != progressMonitor) {
            if (!progressMonitor.setCurrent(index)) {
               break;
            }
         }
         MarkovTransition transition
            = getSelectionMode().chooseNextTransition(this, 1.);
         MarkovState target = transition.getTarget();
         getNextSource(target);
         chain.append(transition);
         if (++index >= limit) break;
      }
   }
   /**
    * Test if this matrix is in the process of generating a sequence.
    * @return True if this matrix is in the process of generating a sequence; false otherwise.
    */
   public boolean isActive() {
      if (null == currentSource) return false;
      return !currentSource.isTerminal();
   }
   @Override
   public Integer next() {
      if (null == currentSource) activate();
      if (!override)
         nextSource();
      int result = currentSource.getRightmostState().getID();
      override = false;
      return result;
   }
   /**
    * Get a text description identifying this matrix.
    * @return A text description identifying this matrix.
    */
   public String getText() {
      return super.getText();
   }
   /**
    * Get an HTML summary of state activity.
    * @return HTML-formatted text summarizing state activity.
    */
   public String getSteadyStateSummary() {
      if (!steadyStateAnalyzed)
         throw new UnsupportedOperationException("Unanalyzed matrix.");
      HtmlBuilder builder = new HtmlBuilder();
      builder.beginTable(null);
      builder.addTableCaption("<b>Steady-State Summary</b>", null);
      builder.beginTableHeader(null);
      builder.beginTableRow(null);
      builder.addTableHeaderCell("State", "align=\"left\"");
      builder.addTableHeaderCell("Weight", "align=\"right\"");
      builder.endTableRow();
      builder.endTableHeader();
      builder.beginTableBody(null);
      for (MarkovState state : getStates().values()) {
         builder.beginTableRow(null);
         builder.addTableCell(state.toString(), "align=\"left\"");
         builder.addTableCell(MathMethods.formatDouble(state.getSteadyStateWeight()/steadyStateTotal, 3), "align=\"right\"");
         builder.endTableRow();
      }
      builder.endTableBody();
      builder.endTable();
      return builder.toString();
   }
   /**
    * Describe this matrix as an HTML table.
    * @return A string of HTML-formatted text.
    */
   public String toHtml() {
      HtmlBuilder builder = new HtmlBuilder();
      builder.beginTable(null);
      appendTableHeader(builder);
      builder.beginTableBody(null);
      for (MarkovSource source : sources.values()) {
         source.appendHtmlRow(builder);
      }
      builder.endTableBody();
      builder.endTable();
      return builder.toString();
   }
   protected void appendTableHeader(HtmlBuilder builder) {
      builder.beginTableHeader(null);
      builder.beginTableRow(null);
      for (int position = 0; position < order; position++) {
         builder.addTableCell(null, null);
      }
      String attributes = "colspan=" + states.size();
      appendProbabilityHeaderCell(builder, 0, attributes);
      builder.endTableRow();
      builder.beginTableRow(null);
      for (int position = 0; position < order; position++) {
         int offset = position - order;
         appendProbabilityHeaderCell(builder, offset, null);
      }
      for (MarkovState state : states.values()) {
         builder.addTableHeaderCell(state.getObject().toString(), null);
      }
      builder.endTableRow();
      builder.endTableHeader();
   }
   protected static void appendProbabilityHeaderCell(
         HtmlBuilder builder, int offset, String attributes) {
      builder.beginTableHeaderCell(attributes);
      builder.append("<i>P</i>");
      builder.beginSubscript(null);
      builder.append("<i>k</i>");
      if (0 != offset)
         builder.append(Integer.toString(offset));
      builder.endSubscript();
      builder.endTableHeaderCell();
   }
   /**
    * Get steady-state analyzed flag.
    * @return True if steady-state analyzed; false otherwise.
    */
   public boolean isSteadyStateAnalyzed() {
      return steadyStateAnalyzed;
   }
   /**
    * Begin with equal numbers of each source.
    * Each iteration executes parallel transitions, one for each {@link MarkovSource}, to
    * discover how from source amounts flow into new source amounts.  The source amounts
    * are then summed by state.
    * @param limit Number of iterations.
    * @param progressMonitor The progress monitor, which monitors percent completion
    * and which calling processes can use to abort calculation.
    */
   public void analyzeSteadyStateAmounts(int limit, ProgressMonitor progressMonitor) {
      cycleCount = 0;
      initializeAmounts();
      iterateSteadyStateTransitions(limit, progressMonitor);
   }
   /**
    * Execute parallel transitions, one for each {@link MarkovSource}, to discover how
    * from source amounts flow into new source amounts.
    * Don't call this function without first calling {@link #setToAmounts(double)} with
    * an argument of unity.
    * @param limit Number of iterations.
    * @param progressMonitor The progress monitor, which monitors percent completion and which
    * calling processes can use to abort calculation.
    * @throws IllegalArgumentException when the limit is not positive.
    */
   public void iterateSteadyStateTransitions(int limit, ProgressMonitor progressMonitor) {
      if (1 > limit)
         throw new IllegalArgumentException("Iteration limit not positive");
      if (null != progressMonitor) {
         progressMonitor.setGoal(limit);
         progressMonitor.start();
      }
      for (int index = 0; index < limit; index++) {
         if (null != progressMonitor) {
            if (!progressMonitor.setCurrent(index)) break;
         }
         cycleSteadyStateTransitions();
         evaluateSteadyStateWeights();
      }
      if (null != progressMonitor) {
         if(progressMonitor.isRunning()) progressMonitor.complete();
      }
   }
   /**
    * Begin with equal numbers of each source.
    * Each iteration executes parallel transitions, one for each {@link MarkovSource}, to discover how
    * from source amounts flow into new source amounts.  Iterations continue until largest difference
    * between from amount and to amount satisfies threshold.
    * The source amounts are then summed by state.
    * @param threshold Maximum fromAmount/toAmount difference.
    * @param progressMonitor The optional progress monitor, which monitors percent completion and which
    * calling processes can use to abort calculation.
    */
   public void analyzeSteadyStateTransitions(double threshold, ProgressMonitor progressMonitor) {
      cycleCount = 0;
      initializeAmounts();
      boolean flag = false;
      int limit = 10 * states.size() * states.size();
      if (null != progressMonitor) {
         progressMonitor.setGoal(limit);
         progressMonitor.start();
      }
      for (int k = 1; k <= limit; k++) {
         if (null != progressMonitor) {
            if (!progressMonitor.setCurrent(k)) {
               progressMonitor.error("Killed by user.");
               return;
            }
         }
         cycleSteadyStateTransitions();
         flag = true;
         for (MarkovState state : states.values()) {
            double fromAmount = 0.;
            double toAmount = 0.;
            for (MarkovSource source : state.getSources().values()) {
               fromAmount += source.getFromAmount();
               toAmount += source.getToAmount();
            }
            double diff = Math.abs((fromAmount - toAmount) / toAmount);
            if (diff > threshold) {
               if (null != progressMonitor) {
                  String message = "Iteration " + k + " State " + state.toString()
                  + " diff " + MathMethods.formatDouble(diff, 3);
                  progressMonitor.setActivityMessage(message);
               }
               flag = false;
               break;
            }
         }
         if (flag) break;
      }
      evaluateSteadyStateWeights();
      if (null != progressMonitor) progressMonitor.complete();
   }
   private void cycleSteadyStateTransitions() {
      shiftAmounts();
      double fromTotal = 0.;
      for (MarkovSource fromSource : sources.values()) fromTotal += fromSource.getFromAmount();
      for (MarkovSource fromSource : sources.values()) {
         double transitionTotal = fromSource.getTransitionTotal();
         double fromAmount = fromSource.getFromAmount();
         if (0. == fromAmount) continue;
         for (MarkovTransition transition : fromSource.getTransitions().values()) {
            boolean flag = false;
            MarkovState toState = transition.getTarget();
            deriveNextKey(scratchKey, fromSource.getKey(), toState.getID());
            MarkovSource toSource = sources.get(scratchKey);
            double transitionWeight = transition.getWeight();
            if (0. < transitionWeight) {
               double toWeight = transitionWeight / transitionTotal;
               double toIncrement = fromAmount * toWeight;
               double toAmount = toSource.getToAmount() + toIncrement;
               toSource.setToAmount(toAmount);
               flag = true;
            }
            if (!flag)
               throw new RuntimeException(fromSource.getText() + " has no targets");
         }
      }
      int cycleLimit = 1000;
      if (++cycleCount > cycleLimit)
         throw new RuntimeException(
               "No steady-state convergence after " + cycleLimit + " iterations");
//      HtmlBuilder builder = new HtmlBuilder();
//      builder.beginTableRow(null);
//      builder.addTableCell(Integer.toString(cycleCount), null);
//      double total = 0.;
//      for (MarkovSource source : sources.values()) {
//         total += source.getToAmount();
//      }
//      for (MarkovSource source : sources.values()) {
//         builder.addTableCell(MathMethods.df3.format(source.getToAmount()/total), null);
//      }
//      builder.endTableRow();
//      System.out.print(builder.toString());
      double toTotal = 0.;
      for (MarkovSource toSource : sources.values()) {
         toTotal += toSource.getToAmount();
      }
      if (!MathMethods.haveSmallDifference(fromTotal, toTotal))
         throw new RuntimeException("From total " + fromTotal + " To total " + toTotal);
   }
   private void evaluateSteadyStateWeights() {
      for (MarkovState state : states.values()) {
         double weight = 0.;
         for (MarkovSource source : state.getSources().values()) {
            weight += source.getToAmount();
         }
         state.setSteadyStateWeight(weight);
      }
      this.steadyStateAnalyzed = true;
   }
   /**
    * Set all source to-amounts to the indicated value (usually zero).
    * @param amount The indicated value.
    */
   public void setToAmounts(double amount) {
      for (MarkovSource source : sources.values()) {
         source.setToAmount(amount);
      }
   }
   /**
    * Set all source to-amounts to the source's starting weight.
    */
   public void initializeAmounts() {
      for (MarkovSource source : sources.values()) {
         source.setToAmount(source.getWeight());
      }
   }
   protected void shiftAmounts() {
      for (MarkovSource source : sources.values()) {
         double amount = source.getToAmount();
         double weight = source.getWeight();
         if (weight > 0.) amount += (weight / source.getContainer().getSourceTotal());
         source.setFromAmount(amount);
         source.setToAmount(0.);
      }
   }
   /**
    * Adjust state usages so that they average to zero.
    */
   public void normalizeStateUsages() {
      double total = 0;
      for (MarkovState state : states.values()) {
         total += state.getUsage();
      }
      if (Math.abs(total) < MathMethods.TINY) return;
      double increment = -total / states.size();
      for (MarkovState state : states.values()) {
         state.incrementUsage(increment);
      }
   }
   /**
    * Get the steady-state total.
    * @return The steady-state total.
    */
   public double getSteadyStateTotal() {
      return steadyStateTotal;
   }
   protected void incrementSteadyStateTotal(double increment) {
      steadyStateTotal += increment;
   }
   @Override
   public boolean hasNext() {
      return hasNextSource();
   }
   @Override
   public boolean hasReset() {
      return true;
   }
   @Override
   public void reset() {
      throw new UnsupportedOperationException("Method not implemented");
   }
   /**
    * Get the smallest transition weight for any source in this matrix.
    * @return The smallest transition weight for any source in this matrix.
    */
   public MarkovTransition getRarestTransition() {
      if (!steadyStateAnalyzed) {
         throw new UnsupportedOperationException("Unanalyzed matrix.");
      }
      MarkovTransition result = null;
      double minWeight = Double.MAX_VALUE;
      for (MarkovState state : states.values()) {
         double totalAmount = state.getTotalToAmount();
         for (MarkovSource source : sources.values()) {
            double sourceWeight = source.getToAmount() / totalAmount;
            for (MarkovTransition transition : source.getTransitions().values()) {
               double weight = transition.getWeight();
               if (MathMethods.TINY > weight) continue;
               double transitionWeight = weight / source.getTransitionTotal();
               double jointWeight = sourceWeight * transitionWeight;
               if (jointWeight < minWeight) {
                  minWeight = jointWeight;
                  result = transition;
               }
            }
         }
      }
      return result;
   }
   /**
    * Convert the indicated text into a double-precision weight.
    * @param text The indicated text.
    * @return A double-precision value.
    */
   public static double parseWeightText(String text) {
      double result;
      try {
         result = Double.valueOf(text);
      }
      catch (NumberFormatException e) {
         String message = "Invalid weight [" + text + "]";
         throw new IllegalArgumentException(message);
      }
      if (0 > result) {
         String message = "Weight may not be negative";
         throw new IllegalArgumentException(message);
      }
      return result;
   }
   /**
    * Convert the indicated text into an integer index.
    * @param text The indicated text.
    * @return An integer index.
    */
   public static int parseIndexText(String text) {
      int result;
      try {
         result = Integer.valueOf(text);
      }
      catch (NumberFormatException e) {
         String message = "Invalid index [" + text + "]";
         throw new IllegalArgumentException(message);
      }
      if (0 >= result) {
         String message = "Index must be positive";
         throw new IllegalArgumentException(message);
      }
      return result;
   }
   /**
    * Dump an itemization of this matrix to standard out.
    */
   public void dump() {
      System.out.println(this.getClass().getSimpleName() + " source total " + getSourceTotal());
      SortedMap<Integer, MarkovState> matrixStates = getStates();
      for (int stateKey : matrixStates.keySet()) {
         MarkovState state =  matrixStates.get(stateKey);
         String stateClassName = state.getClass().getSimpleName();
         System.out.println("   " + stateClassName + " position " + stateKey + " id " + state.getID());
         SortedMap<IntArray, MarkovSource> stateSources = state.getSources();
         for (IntArray sourceKey : stateSources.keySet()) {
            MarkovSource source = stateSources.get(sourceKey);
            String sourceClassName = source.getClass().getSimpleName();
            System.out.println("   " + sourceClassName + " position " + sourceKey
               + " key " + source.getKey() + " weight " + source.getWeight()
               + " transition total " + source.getTransitionTotal());
            SortedMap<Integer, MarkovTransition> sourceTransitions = source.getTransitions();
            for (int targetKey : sourceTransitions.keySet()) {
               MarkovTransition transition = sourceTransitions.get(targetKey);
               String transitionClassName = transition.getClass().getSimpleName();
               MarkovState targetState = transition.getTarget();
               int targetID = targetState.getID();
               double targetWeight = transition.getWeight();
               System.out.println("         " + transitionClassName + " position "
                  + targetKey + " target " + targetID + " weight " + targetWeight);
            }
         }
      }
   }
   /**
    * Check the integrity of the matrix-wide source collection versus
    * the state-specific source collections.
    */
   public void checkIntegrity() {
      for (IntArray key : sources.keySet()) {
         MarkovSource source = sources.get(key);
         IntArray itemKey = source.getKey();
         if (!itemKey.equals(key))
            throw new RuntimeException(
               "Inconsistent keys [" + key + "] [" + itemKey + "]");
         int rightmostStateID = key.memberAt(key.itemCount()-1);
         MarkovState rightmostState = getState(rightmostStateID);
         SortedMap<IntArray, MarkovSource> stateSources = rightmostState.getSources();
         if (!stateSources.containsKey(key))
            throw new RuntimeException(
               "State " +  rightmostStateID + " has no source with key [" + key + "]");
         MarkovSource stateSource = stateSources.get(key);
         if (!stateSource.equals(source))
            throw new RuntimeException(
               "State " +  rightmostStateID + " has different source with key [" + key + "]");
      }
   }
   /**
    * Run this matrix, saving results in the indicated file.
    * @param chain An entity which receives the sequence of {@link MarkovState} references.
    * @param file The indicated file.
    * @param progressMonitor Allows the user interface to track the progress of the run and to
    * abort the run if desired.
    */
   public void run(MarkovChain chain, File file, ProgressMonitor progressMonitor) {
      throw new UnsupportedOperationException("Method not implemented");
   }
   @Override
   public double minGraphValue() {
      throw new UnsupportedOperationException("Method not supported");
   }
   @Override
   public double maxGraphValue() {
      throw new UnsupportedOperationException("Method not supported");
   }
}

/**
 * The {@link MarkovState} class defines a potential stage in the progress of a markov chain.  Each {@link MarkovState}
 * has a unique integer identifier.
 * @author Charles Ames
 */
public class MarkovState extends WriteableEntity {
   private Object object;
   private SortedMap<IntArray, MarkovSource> sources;
   /**
    * Steady state weight.  This weight is only valid after a call
    * either to {@link MarkovState#setSteadyStateWeight(double)} or to
    * {@link MarkovMatrix#analyzeSteadyStateAmounts(int, ProgressMonitor)}.
    */
   private double steadyStateWeight;
   private int count;
   private double usage;
   private static MarkovState[] stateArray;
   private IntArray scratchKey;
   private String displayText = null;

   protected MarkovState(MarkovMatrix matrix, int id) {
      super(matrix);
      setIDQuality(Entity.AttributeQuality.MODIFIABLE);
      setID(id);
      this.sources = new TreeMap<IntArray, MarkovSource>();
      if (null == scratchKey) {
         int order = matrix.getOrder();
         scratchKey = matrix.allocateSourceKey();
         stateArray = new MarkovState[order];
      }
      this.object = null;
      this.setSteadyStateWeight(1.);
      this.setUsage(0.);
   }
   @Override
   public void wipe() {
      object = null;
      sources = null;
      super.wipe();
   }
   @Override
   public String toString() {
      if (null == displayText) {
         Object o = getObject();
         if (null == o)
            displayText = "#" + (getID() + 1);
         else
            displayText = "#" + (getID() + 1) + " " + o.toString();
      }
      return displayText;
   }
   /**
    * Returns a representation of the state's object not including
    * the state id.
    * @return The object value description.
    */
   public String objectString() {
      return getObject().toString();
   }
   /**
    * Get the matrix to which this state belongs.
    * @return The matrix to which this state belongs.
    */
   public MarkovMatrix getContainer() {
      return (MarkovMatrix) super.getContainer();
   }
   /**
    * Get the sources with this as rightmost state.
    * @return A collection of {@link MarkovSource} instances, indexed by key.
    */
   public SortedMap<IntArray, MarkovSource> getSources() {
      return sources;
   }
   /**
    * Get the sole state source for a first-order matrix.
    * If the source does not exist, create it.
    * @return The sole state source for a first-order matrix.
    * @throws UnsupportedOperationException when the matrix is not first-order.
    */
   public MarkovSource getSoleSource() {
      if (!getContainer().isFirstOrder()) throw new UnsupportedOperationException("Weights accessible only for first-order matrices");
      if (0 == sources.size()) {
         createAllSources();
      }
      return sources.get(sources.firstKey());
   }
   @Override
   public boolean setID(int id) {
      if (0 > id)
         throw new IllegalArgumentException("Negative id");
      SortedMap<Integer, MarkovState> map = getContainer().getStates();
      int oldID = getOldID();
      if (oldID == id) return false;
      if (0 <= oldID)
         map.remove(oldID);
      super.setID(id);
      map.put(id, this);
      displayText = null;
      return true;
   }
   /**
    * Get the sum of the child {@link MarkovSource} to amounts.
    * @return The sum of the child {@link MarkovSource} to amounts.
    * @throws UnsupportedOperationException when the matrix is unanalyzed.
    */
   public double getTotalToAmount() {
      if (!getContainer().isSteadyStateAnalyzed())
         throw new UnsupportedOperationException("Unanalyzed matrix");
      double total = 0.;
      for (MarkovSource source : sources.values()) {
         total += source.getToAmount();
      }
      return total;
   }
   /**
    * Check for terminal condition; that is, having no transitions to other states.
    * @return true if this state can transition to any other state; false otherwise.
    */
   public boolean isTerminal() {
      // local sources collection contains only sources whose rightmost
      // state is itself.
      int sourceCount = sources.size();
      int terminalCount = 0;
      for (MarkovSource source : sources.values()) {
         if (source.isTerminal()) terminalCount++;
      }
      if (0 == terminalCount) return false;
      if (sourceCount == terminalCount) return true;
      throw new RuntimeException("State " + getID() + " has " + terminalCount + " terminal source of " + sourceCount);
   }
   /**
    * Get the object.
    * @return The assigned object.
    */
   public Object getObject() {
      return object;
   }
   /**
    * Set the object.
    * @param object The intended object.
    * @return True if the object changed; false otherwise.
    */
   public boolean setObject(Object object) {
      if (null == object)
         throw new IllegalArgumentException("Null object");
      boolean changed = false;
      if (null == this.object || !this.object.equals(object)) {
         this.object = object;
         changed = true;
         makeDirty();
         displayText = null;
      }
      return changed;
   }
   /**
    * Clear the object.
    */
   public void clearObject() {
      this.object = null;
   }
   /**
    * Copy the object from the indicated reference state.
    * @param reference The indicated reference state.
    */
   public void copyObject(MarkovState reference) {
      object = reference.object;
   }
   /**
    * Create sources for all approaches to this state;
    */
   public void createAllSources() {
      int length = scratchKey.itemCount();
      MarkovMatrix matrix = getContainer();
      if (1 == length) {
         scratchKey.insertMember(getID(), 0);
         if (!sources.containsKey(scratchKey)) {
            MarkovSource source = matrix.createSource(scratchKey);
            source.setWeight(1.);
         }
      }
      else {
         SortedMap<Integer, MarkovState> states = matrix.getStates();
         int limit = states.lastKey();
         int right = length - 1;
         scratchKey.insertMember(getID(), right);
         stateArray[right] = this;
         int position;
         for (position = 0; position < right; position++) {
            scratchKey.insertMember(0, position);
         }
         position = right - 1;
         for (;;) {
            int stateID = scratchKey.memberAt(position);
            scratchKey.insertMember(stateID + 1, position);
            MarkovState state = states.get(stateID);
            if (null != state) {
               stateArray[position] = state;
               if (0 > --position) {
                  if (!sources.containsKey(scratchKey)) {
                     MarkovSource source = matrix.createSource(scratchKey);
                     source.setWeight(1.);
                  }
               }
            }
            if (scratchKey.memberAt(position) >= limit) {
               if (++position >= right) break;
            }
         }
      }
   }
   /**
    * Enumerate undefined sources which approach this state;
    * @param keys The receiving collection of {@link IntArray} instances.  The method starts out by clearing this list.
    */
   public void enumerateUndefinedSources(List<IntArray> keys) {
      keys.clear();
      int length = scratchKey.itemCount();
      MarkovMatrix matrix = getContainer();
      int right = length - 1;
      scratchKey.insertMember(getID(), right);
      matrix.enumerateUndefinedSources(keys, right, scratchKey);
   }
   /**
    * Fill the destination list with all the sources which do not presently transition to the target state.
    * @param list The destination list
    * @param targetState The target state.
    */
   public void getUntargetedSourceArray(List<MarkovSource> list, MarkovState targetState) {
      list.clear();
      for (MarkovSource source : sources.values()) {
         boolean flag = false;
         for (MarkovTransition transition : source.getTransitions().values()) {
            if (targetState == transition.getTarget()) {
               flag = true;
               break;
            }
         }
         if (!flag)
         {
            list.add(source);
         }
      }
   }
   /**
    * Get the state with the next lower id.
    * @return The state with the next lower id.  Null if not found.
    */
   public MarkovState predecessor() {
      SortedMap<Integer, MarkovState> states = getContainer().getStates();
      int firstKey = states.firstKey();
      MarkovState result = null;
      int id = getID();
      for (int predecessorID = id; --predecessorID >= firstKey;) {
         result = states.get(predecessorID);
         if (null != result) break;
      }
      return result;
   }
   /**
    * Get the state with the next higher id.
    * @return The state with the next higher id.  Null if not found.
    */
   public MarkovState successor() {
      SortedMap<Integer, MarkovState> states = getContainer().getStates();
      int lastKey = states.lastKey();
      MarkovState result = null;
      int id = getID();
      for (int successorID = id; ++successorID <= lastKey;) {
         result = states.get(successorID);
         if (null != result) break;
      }
      return result;
   }
   /**
    * Setter for the steady state weight.
    * @param weight The intended steady-state weight.
    * @throws IllegalArgumentException when the weight is negative.
    */
   public void setSteadyStateWeight(double weight) {
      MarkovMatrix.checkWeight(weight);
      MarkovMatrix matrix = getContainer();
      matrix.incrementSteadyStateTotal(-this.steadyStateWeight);
      this.steadyStateWeight = weight;
      matrix.incrementSteadyStateTotal(this.steadyStateWeight);
   }
   /**
    * Getter for {@link #steadyStateWeight}.
    * @return The calculated {@link #steadyStateWeight} amount.
    */
   public double getSteadyStateWeight() {
      return steadyStateWeight;
   }
   /**
    * Getter for the state usage count.
    * @return The accumulated usage count.
    */
   public int getCount() {
      return count;
   }
   /**
    * Setter for the state usage count.
    * @param count The intended state usage count.
    */
   public void setCount(int count) {
      this.count = count;
   }
   /**
    * Increase state usage count by 1.
    */
   public void incrementCount() {
      this.count++;
   }
   /**
    * Getter for the state usage quantity.
    * @return The accumulated state usage quantity.
    */
   public double getUsage() {
      return usage;
   }
   /**
    * Setter for the state usage quantity.
    * @param usage The intended state usage quantity.
    */
   public void setUsage(double usage) {
      this.usage = usage;
   }
   /**
    * Increase state usage quantity by the indicated increment.
    * @param increment The indicated increment.
    */
   public void incrementUsage(double increment) {
      this.usage += increment;
   }
   /**
    * Increase usage by the accent times the reciprocal of the steady-state weight.
    * @param accent The contextual emphasis associated with the event.  Use 1 if unsure.
    * @throws IllegalArgumentException when accent is not positive.
    */
   public void updateSteadyStateUsage(double accent) {
      if (accent < MathMethods.TINY) throw new IllegalArgumentException("Accent not positive");
      incrementUsage(accent * getContainer().getSteadyStateTotal() / steadyStateWeight);
   }
}

/**
 * The {@link MarkovTransition} defines the probability (weight) that a source
 * state will make a transition to a target state.  Each {@link MarkovTransition} instance
 * combines a {@link MarkovSource} reference with a target {@link MarkovState} reference.
 * The combination of the {@link MarkovSource}'s unique {@link IntArray} and the target
 * {@link MarkovState}'s unique identifier must itself be unique.
 * @author Charles Ames
 */
public class MarkovTransition extends WriteableEntity {
   private MarkovState target;
   /**
    * The relative frequency (relative to other transitions from the same source)
    * of transitioning from the source to this particular target.
    */
   private double weight;
   private int count;
   private double usage;
   protected MarkovTransition(MarkovSource source, MarkovState target) {
      super(source);
      if (null == target)
         throw new IllegalArgumentException("Null target");
      this.target = target;
      this.weight = 0.;
   }
   @Override
   public void wipe() {
      target = null;
      super.wipe();
   }
   @Override
   public String getText() {
      return super.getText() + " [" + getContainer().getKey().toString()
         + ":" + target.getID() + "]";
   }
   @Override
   public MarkovSource getContainer() {
      return (MarkovSource) super.getContainer();
   }
   /**
    * Getter for {@link #weight}.
    * @return The assigned {@link #weight} value.
    */
   public double getWeight() {
      if (Double.isNaN(weight))
         throw new UninitializedException("Weight not initialized");
      return weight;
   }
   /**
    * Setter for {@link #weight}.
    * @param weight The intended {@link #weight} value.
    * @return True if the value changed; false otherwise.
    * @throws IllegalArgumentException when the argument is negative.
    */
   public boolean setWeight(double weight) {
      MarkovMatrix.checkWeight(weight);
      if (!MathMethods.haveSmallDifference(this.weight, weight)) {
         MarkovSource source = getContainer();
         source.incrementTransitionTotal(-this.weight);
         this.weight = weight;
         source.incrementTransitionTotal(this.weight);
         makeDirty();
         return true;
      }
      return false;
   }
   /**
    * Get the transition usage count.
    * @return The assigned transition usage count.
    */
   public int getCount() {
      return count;
   }
   /**
    * Set the transition usage count.
    * @param count The intended transition usage count.
    */
   public void setCount(int count) {
      this.count = count;
   }
   /**
    * Increment usage count by 1.
    */
   public void incrementCount() {
      this.count++;
   }
   /**
    * Get the transition usage.
    * @return The assigned transition usage.
    */
   public double getUsage() {
      return usage;
   }
   /**
    * Set the transition usage.
    * @param usage The intended transition usage.
    */
   public void setUsage(double usage) {
      this.usage = usage;
   }
   /**
    * Increase usage by the indicated increment.
    * @param increment The indicated increment.
    */
   public void incrementUsage(double increment) {
      this.usage += increment;
   }
   /**
    * Get the target state.
    * @return The target state.
    */
   public MarkovState getTarget() {
      return target;
   }
}

The type hierarchy for MarkovTransition is:

• MarkovTransition extends WriteableEntity

Each MarkovTransition instance is uniquely identified under a MarkovSource by its target field. This field references the MarkovState which will be returned by MarkovTransition.nextState(), should MarkovSource.chooseNextTransition() select this particular instance.

Guiding chooseNextTransition() in its selection process are the weight and usage fields.

The weight field influences all three selection modes; its value is normally established by a call to MarkovTransition.setWeight() during a matrix's construction phase. There is also the option of changing transition weights dynamically while the chain is being generated, but this option is not for the faint at heart.

The usage field is employed solely by SelectionMode.BALANCED_TRANSITIONS. This statistic advances each time the transition is selected.