class_docstr: Records progress through the set of constraints for each item in the beam
  using a trie.
class_docstr_tok: ["Records","progress","through","the","set","of","constraints","for","each","item","in","the","beam","using","a","trie","."]
docstr: Reads in a token and advances the state. Here's how it works.
  
  We can advance to the next state if:
  - there is a matching child
  - its path isn't blocked
  
  A path is blocked when all constraints that are descendants of
  that node have already been generated, in the current state.
  
  If we are not able to advance from the current state, we "fall
  off the graph" and return to the root state. There, we again
  try to advance, checking the same criteria.
  
  In any case, when falling off the graph, we need to do some
  bookkeeping. We:
  - check whether any constraints were met (all prefixes of
    current state)
  - if one is found, mark it as completed
  - adjust visited nodes accordingly
docstr_tok: ["Reads","in","a","token","and","advances","the","state",".","Here","'s","how","it","works",".","We","can","advance","to","the","next","state","if",":","-","there","is","a","matching","child","-","its","path","is","n't","blocked","A","path","is","blocked","when","all","constraints","that","are","descendants","of","that","node","have","already","been","generated",",","in","the","current","state",".","If","we","are","not","able","to","advance","from","the","current","state",",","we","``","fall","off","the","graph","''","and","return","to","the","root","state",".","There",",","we","again","try","to","advance",",","checking","the","same","criteria",".","In","any","case",",","when","falling","off","the","graph",",","we","need","to","do","some","bookkeeping",".","We",":","-","check","whether","any","constraints","were","met","(","all","prefixes","of","current","state",")","-","if","one","is","found",",","mark","it","as","completed","-","adjust","visited","nodes","accordingly"]
code: def advance(self, token: int):
      """Reads in a token and advances the state. Here's how it works.
  
      We can advance to the next state if:
      - there is a matching child
      - its path isn't blocked
  
      A path is blocked when all constraints that are descendants of
      that node have already been generated, in the current state.
  
      If we are not able to advance from the current state, we "fall
      off the graph" and return to the root state. There, we again
      try to advance, checking the same criteria.
  
      In any case, when falling off the graph, we need to do some
      bookkeeping. We:
      - check whether any constraints were met (all prefixes of
        current state)
      - if one is found, mark it as completed
      - adjust visited nodes accordingly
      """
      token = int(token)
  
      next_state = None
      child = self.node[token]
      if (
          child is not None
          and self.generated[child] < child.num_constraints
      ):
          next_state = UnorderedConstraintState(child, copy_from=self)
  
      def rewind():
          """If we're mid-trie and an "illegal" token is chosen next, we need
          to reset our state to the root state. However, along the way, we need
          to check whether a prefix of the current trie state represents a state
          we could mark as completed.
          """
          node = self.node
          while node != self.root:
              if node.terminal and self.completed[node] < node.terminal:
                  next_state.completed[node] += 1
                  return
  
              next_state.generated[node] -= 1
              node = node.parent
  
      # Fall off the graph, check the root
      if next_state is None and token in self.root.next_tokens():
          child = self.root[token]
          # We can only traverse this edge if it's not saturated
          if self.generated[child] < child.num_constraints:
              next_state = UnorderedConstraintState(
                  child, copy_from=self
              )
          else:
              next_state = UnorderedConstraintState(
                  self.root, copy_from=self
              )
  
          # Rewind
          rewind()
  
      elif next_state is None:
          next_state = UnorderedConstraintState(
              self.root, copy_from=self
          )
          # Rewind
          rewind()
  
      return next_state
  
imports: from collections import Counter
  from typing import List, Optional, Set, Tuple
  import torch
label_desc: Use image node_id 15 for calling the UnorderedConstraintState obj's underlying member method code with example usage: obj.advance(token) and returns: next_state