Package org.cis1200

Class MarkovChainIterator

java.lang.Object
org.cis1200.MarkovChainIterator
All Implemented Interfaces:
Iterator<String>
class MarkovChainIterator extends Object implements Iterator<String>
This inner class represents a "walk" through the Markov Chain as an Iterator that yields each token encountered during the walk.

A walk through the chain is determined by the given NumberGenerator, which picks from among the choices of tokens according to their probability distributions.

For example, given 

  ILLUSTRATIVE EXAMPLE MARKOV CHAIN:
  startTokens: { "a":2 }
  bigramFrequencies:
  "!":    { "and":1 }
  "?":    { "<END>":1 }
  "a":    { "banana":2  "chair":1  "table":1 }
  "and":  { "a":2 }
  "banana":   { "!":1  "?":1 }
  "chair":    { "<END>":1 }
  "table":    { "and":1 }
The sequence of numbers 0 2 0 determines the (valid) walk consisting of the three tokens "a", "chair", and END_TOKEN as follows:
  • The first 0 picks out "a" from among the startTokens. (Since "a" occurred with frequency 2, either 0 or 1 would yield "a".)
  • Next, the 2, picks out "chair" from the probability distribution over bigrams associated with "a" (0-1 map to "banana", 2 maps to "chair", and 3 maps to "table").
  • Finally, the last 0 picks out END_TOKEN from the bigrams associated with "chair".
See the documentation for pick in ProbabilityDistribution.pick(int) for more details.

  • Constructor Details

    • MarkovChainIterator

      MarkovChainIterator(ProbabilityDistribution<String> startTokens, Map<String,ProbabilityDistribution<String>> bigramFrequencies, NumberGenerator ng)
      Constructs an iterator that follows the path specified by the given NumberGenerator. The first token of the walk is chosen from startTokens by picking from that distribution using ng's first number. If the number generator can not provide a valid start index, or if there are no start tokens, any exceptions should be caught and the constructed Iterator should be empty (i.e., hasNext is always false).
      Parameters:
      startTokens - from the MarkovChain (assumed not null)
      bigramFrequencies - from the MarkovChain (assumed not null)
      ng - the number generator to use for this walk (assumed not null)

  • Method Details

    • hasNext

      public boolean hasNext()
      This method determines whether there is a next token in the Markov Chain based on the current state of the walk. Remember that the end of a sentence is denoted by the token END_TOKEN.

      Your solution should be very short.

      Specified by:
      hasNext in interface Iterator<String>
      Returns:
      true if next() will return a non-END_TOKEN String and false otherwise

    • next

      public String next()
      Specified by:
      next in interface Iterator<String>
      Returns:
      the next token in the MarkovChain's walk
      Throws:
      NoSuchElementException - if there are no more tokens on the walk through the chain (i.e. it has reached END_TOKEN), or if the number generator provides an invalid choice (e.g, an illegal argument for pick).