class_docstr: Properties
  ==========
  
  [1] `0 \in \Omega` and `\tau(1) = \epsilon`
  [2] `\alpha^x = \beta \Leftrightarrow \beta^{x^{-1}} = \alpha`
  [3] If `\alpha^x = \beta`, then `H \tau(\alpha)x = H \tau(\beta)`
  [4] `\forall \alpha \in \Omega, 1^{\tau(\alpha)} = \alpha`
  
  References
  ==========
  
  .. [1] Holt, D., Eick, B., O'Brien, E.
         "Handbook of Computational Group Theory"
  
  .. [2] John J. Cannon; Lucien A. Dimino; George Havas; Jane M. Watson
         Mathematics of Computation, Vol. 27, No. 123. (Jul., 1973), pp. 463-490.
         "Implementation and Analysis of the Todd-Coxeter Algorithm"
class_docstr_tok: ["Properties","==========","[","1","]","`","0","\\in","\\Omega","`","and","`","\\tau","(","1",")","=","\\epsilon","`","[","2","]","`","\\alpha^x","=","\\beta","\\Leftrightarrow","\\beta^","{","x^","{","-1","}","}","=","\\alpha","`","[","3","]","If","`","\\alpha^x","=","\\beta","`",",","then","`","H","\\tau","(","\\alpha",")","x","=","H","\\tau","(","\\beta",")","`","[","4","]","`","\\forall","\\alpha","\\in","\\Omega",",","1^","{","\\tau","(","\\alpha",")","}","=","\\alpha","`","References","==========","..","[","1","]","Holt",",","D.",",","Eick",",","B.",",","O'Brien",",","E.","``","Handbook","of","Computational","Group","Theory","''","..","[","2","]","John","J.","Cannon",";","Lucien","A.","Dimino",";","George","Havas",";","Jane","M.","Watson","Mathematics","of","Computation",",","Vol",".","27",",","No",".","123",".","(","Jul.",",","1973",")",",","pp",".","463-490",".","``","Implementation","and","Analysis","of","the","Todd-Coxeter","Algorithm","''"]
docstr: ``scan`` performs a scanning process on the input ``word``.
  It first locates the largest prefix ``s`` of ``word`` for which
  `\alpha^s` is defined (i.e is not ``None``), ``s`` may be empty. Let
  ``word=sv``, let ``t`` be the longest suffix of ``v`` for which
  `\alpha^{t^{-1}}` is defined, and let ``v=ut``. Then three
  possibilities are there:
  
  1. If ``t=v``, then we say that the scan completes, and if, in addition
  `\alpha^s = \alpha^{t^{-1}}`, then we say that the scan completes
  correctly.
  
  2. It can also happen that scan does not complete, but `|u|=1`; that
  is, the word ``u`` consists of a single generator `x \in A`. In that
  case, if `\alpha^s = \beta` and `\alpha^{t^{-1}} = \gamma`, then we can
  set `\beta^x = \gamma` and `\gamma^{x^{-1}} = \beta`. These assignments
  are known as deductions and enable the scan to complete correctly.
  
  3. See ``coicidence`` routine for explanation of third condition.
  
  Notes
  =====
  
  The code for the procedure of scanning `\alpha \in \Omega`
  under `w \in A*` is defined on pg. 155 [1]
  
  See Also
  ========
  
  scan_c, scan_check, scan_and_fill, scan_and_fill_c
  
  Scan and Fill
  =============
  
  Performed when the default argument fill=True.
  
  Modified Scan
  =============
  
  Performed when the default argument modified=True
docstr_tok: ["``","scan","``","performs","a","scanning","process","on","the","input","``","word","``",".","It","first","locates","the","largest","prefix","``","s","``","of","``","word","``","for","which","`","\\alpha^s","`","is","defined","(","i.e","is","not","``","None","``",")",",","``","s","``","may","be","empty",".","Let","``","word=sv","``",",","let","``","t","``","be","the","longest","suffix","of","``","v","``","for","which","`","\\alpha^","{","t^","{","-1","}","}","`","is","defined",",","and","let","``","v=ut","``",".","Then","three","possibilities","are","there",":","1",".","If","``","t=v","``",",","then","we","say","that","the","scan","completes",",","and","if",",","in","addition","`","\\alpha^s","=","\\alpha^","{","t^","{","-1","}","}","`",",","then","we","say","that","the","scan","completes","correctly",".","2",".","It","can","also","happen","that","scan","does","not","complete",",","but","`","|u|=1","`",";","that","is",",","the","word","``","u","``","consists","of","a","single","generator","`","x","\\in","A","`",".","In","that","case",",","if","`","\\alpha^s","=","\\beta","`","and","`","\\alpha^","{","t^","{","-1","}","}","=","\\gamma","`",",","then","we","can","set","`","\\beta^x","=","\\gamma","`","and","`","\\gamma^","{","x^","{","-1","}","}","=","\\beta","`",".","These","assignments","are","known","as","deductions","and","enable","the","scan","to","complete","correctly",".","3",".","See","``","coicidence","``","routine","for","explanation","of","third","condition",".","Notes","=====","The","code","for","the","procedure","of","scanning","`","\\alpha","\\in","\\Omega","`","under","`","w","\\in","A","*","`","is","defined","on","pg",".","155","[","1","]","See","Also","========","scan_c",",","scan_check",",","scan_and_fill",",","scan_and_fill_c","Scan","and","Fill","=============","Performed","when","the","default","argument","fill=True",".","Modified","Scan","=============","Performed","when","the","default","argument","modified=True"]
code: def scan(self, alpha, word, y=None, fill=False, modified=False):
      r"""
      ``scan`` performs a scanning process on the input ``word``.
      It first locates the largest prefix ``s`` of ``word`` for which
      `\alpha^s` is defined (i.e is not ``None``), ``s`` may be empty. Let
      ``word=sv``, let ``t`` be the longest suffix of ``v`` for which
      `\alpha^{t^{-1}}` is defined, and let ``v=ut``. Then three
      possibilities are there:
  
      1. If ``t=v``, then we say that the scan completes, and if, in addition
      `\alpha^s = \alpha^{t^{-1}}`, then we say that the scan completes
      correctly.
  
      2. It can also happen that scan does not complete, but `|u|=1`; that
      is, the word ``u`` consists of a single generator `x \in A`. In that
      case, if `\alpha^s = \beta` and `\alpha^{t^{-1}} = \gamma`, then we can
      set `\beta^x = \gamma` and `\gamma^{x^{-1}} = \beta`. These assignments
      are known as deductions and enable the scan to complete correctly.
  
      3. See ``coicidence`` routine for explanation of third condition.
  
      Notes
      =====
  
      The code for the procedure of scanning `\alpha \in \Omega`
      under `w \in A*` is defined on pg. 155 [1]
  
      See Also
      ========
  
      scan_c, scan_check, scan_and_fill, scan_and_fill_c
  
      Scan and Fill
      =============
  
      Performed when the default argument fill=True.
  
      Modified Scan
      =============
  
      Performed when the default argument modified=True
  
      """
      # alpha is an integer representing a "coset"
      # since scanning can be in two cases
      # 1. for alpha=0 and w in Y (i.e generating set of H)
      # 2. alpha in Omega (set of live cosets), w in R (relators)
      A_dict = self.A_dict
      A_dict_inv = self.A_dict_inv
      table = self.table
      f = alpha
      i = 0
      r = len(word)
      b = alpha
      j = r - 1
      b_p = y
      if modified:
          f_p = self._grp.identity
      flag = 0
      while fill or flag == 0:
          flag = 1
          while i <= j and table[f][A_dict[word[i]]] is not None:
              if modified:
                  f_p = f_p * self.P[f][A_dict[word[i]]]
              f = table[f][A_dict[word[i]]]
              i += 1
          if i > j:
              if f != b:
                  if modified:
                      self.modified_coincidence(f, b, f_p**-1 * y)
                  else:
                      self.coincidence(f, b)
              return
          while j >= i and table[b][A_dict_inv[word[j]]] is not None:
              if modified:
                  b_p = b_p * self.P[b][self.A_dict_inv[word[j]]]
              b = table[b][A_dict_inv[word[j]]]
              j -= 1
          if j < i:
              # we have an incorrect completed scan with coincidence f ~ b
              # run the "coincidence" routine
              if modified:
                  self.modified_coincidence(f, b, f_p**-1 * b_p)
              else:
                  self.coincidence(f, b)
          elif j == i:
              # deduction process
              table[f][A_dict[word[i]]] = b
              table[b][A_dict_inv[word[i]]] = f
              if modified:
                  self.P[f][self.A_dict[word[i]]] = f_p**-1 * b_p
                  self.P[b][self.A_dict_inv[word[i]]] = b_p**-1 * f_p
              return
          elif fill:
              self.define(f, word[i], modified=modified)
  
imports: from sympy.combinatorics.free_groups import free_group
  from sympy.printing.defaults import DefaultPrinting
  from itertools import chain, product
  from bisect import bisect_left
label_desc: Use image node_id 11 for calling the CosetTable obj's underlying member method code with example usage: obj.scan(alpha, word, y, fill, modified) without return types