class_docstr: A TransitionMap maps an input event to a set of states.
  An input event is one of: a range of character codes,
  the empty string (representing an epsilon move), or one
  of the special symbols BOL, EOL, EOF.
  
  For characters, this implementation compactly represents
  the map by means of a list:
  
    [code_0, states_0, code_1, states_1, code_2, states_2,
      ..., code_n-1, states_n-1, code_n]
  
  where |code_i| is a character code, and |states_i| is a
  set of states corresponding to characters with codes |c|
  in the range |code_i| <= |c| <= |code_i+1|.
  
  The following invariants hold:
    n >= 1
    code_0 == -maxint
    code_n == maxint
    code_i < code_i+1 for i in 0..n-1
    states_0 == states_n-1
  
  Mappings for the special events '', BOL, EOL, EOF are
  kept separately in a dictionary.
class_docstr_tok: ["A","TransitionMap","maps","an","input","event","to","a","set","of","states",".","An","input","event","is","one","of",":","a","range","of","character","codes",",","the","empty","string","(","representing","an","epsilon","move",")",",","or","one","of","the","special","symbols","BOL",",","EOL",",","EOF",".","For","characters",",","this","implementation","compactly","represents","the","map","by","means","of","a","list",":","[","code_0",",","states_0",",","code_1",",","states_1",",","code_2",",","states_2",",","...",",","code_n-1",",","states_n-1",",","code_n","]","where","|code_i|","is","a","character","code",",","and","|states_i|","is","a","set","of","states","corresponding","to","characters","with","codes","|c|","in","the","range","|code_i|","<","=","|c|","<","=","|code_i+1|",".","The","following","invariants","hold",":","n",">","=","1","code_0","==","-maxint","code_n","==","maxint","code_i","<","code_i+1","for","i","in","0","..","n-1","states_0","==","states_n-1","Mappings","for","the","special","events","``",",","BOL",",","EOL",",","EOF","are","kept","separately","in","a","dictionary","."]
docstr: Search the list for the position of the split point for |code|,
  inserting a new split point if necessary. Returns index |i| such
  that |code| == |map[i]|.
docstr_tok: ["Search","the","list","for","the","position","of","the","split","point","for","|code|",",","inserting","a","new","split","point","if","necessary",".","Returns","index","|i|","such","that","|code|","==","|map","[","i","]","|","."]
code: def split(self, code, len=len, maxint=maxint):
      """
      Search the list for the position of the split point for |code|,
      inserting a new split point if necessary. Returns index |i| such
      that |code| == |map[i]|.
      """
      # We use a funky variation on binary search.
      map = self.map
      hi = len(map) - 1
      # Special case: code == map[-1]
      if code == maxint:
          return hi
      # General case
      lo = 0
      # loop invariant: map[lo] <= code < map[hi] and hi - lo >= 2
      while hi - lo >= 4:
          # Find midpoint truncated to even index
          mid = ((lo + hi) // 2) & ~1
          if code < map[mid]:
              hi = mid
          else:
              lo = mid
      # map[lo] <= code < map[hi] and hi - lo == 2
      if map[lo] == code:
          return lo
      else:
          map[hi:hi] = [code, map[hi - 1].copy()]
          # self.check() ###
          return hi
  
file_path: catboost/contrib/tools/cython/Cython/Plex/Transitions.py
imports: from __future__ import absolute_import
label_desc: Use image node_id 6 for calling the TransitionMap obj's underlying member method code with example usage: obj.split(code, len, maxint) and returns: hi, lo, hi