text: """ Support functions for RE simplification.
  This module is intended for use by the RE module.
  It is in a separate module to keep RE itself cleaner
  since the algorithm, 'rectangle selection', is a quite
  separate part that depends on some tricky heuristics.
  
  The primary entry function is
  
  chooserects(lines, gauges)
  
  It chooses 'the best' rectangles from lines to base simplification on.
  A weight on atoms is given by gauges.
  
  pr() gives some example usages of chooserects.
  
  """
  
  from guppy.sets import immbitset, mutbitset, immbitrange
  
  
  class Rect(object):
      __slots__ = 'width', 'lines', 'gainmemo', 'lnos', 'all_lines', 'common_part'
  
      def __init__(self, width, lines):
          self.width = width
          self.lines = lines
          assert not (width and len(lines) == 1)
          self.gainmemo = {}
  
      def init2(self, lnobyid, all_lines):
          self.all_lines = all_lines
          self.lnos = immbitset([lnobyid[id(line)] for line in self.lines])
          self.common_part = self.get_common_part()
  
      def reducelines(self, lnos):
          # Reduce lines of self by removing some lines
          # Argument: lnos, a 'set' of line numbers to remove
  
          olnos = self.lnos
          lnos = olnos & ~lnos
          if lnos != olnos:
              self.lnos = lnos
              self.lines = [self.all_lines[lno] for lno in lnos]
          if len(lnos) == 1:
              self.width = len(self.lines[0])
  
      def get_lines(self, pickednos=0):
          lines = []
          for i in self.lnos & ~ pickednos:
              lines.append(self.all_lines[i])
          return lines
  
      def __repr__(self):
          return '<\n dir = %d\n width = %d\n lnos = %s\n lines = %s\n>' % (
              self.dir, self.width, list(self.lnos), self.lines)
  
  
  class LeftRect(Rect):
      __slots__ = ()
      dir = 0
  
      def get_common_part(self):
          return self.lines[0][:self.width]
  
      def get_uncommons(self, pickednos=0):
          uc = []
          for line in self.get_lines(pickednos):
              uc.append(line[self.width:])
          return uc
  
  
  class RightRect(Rect, object):
      __slots__ = ()
      dir = -1
  
      def get_common_part(self):
          lo = -self.width
          if lo == 0:
              return []
          return self.lines[0][lo:]
  
      def get_uncommons(self, pickednos=0):
          uc = []
          hi = -self.width
          if hi == 0:
              hi = None
          for line in self.get_lines(pickednos):
              uc.append(line[:hi])
          return uc
  
  
  def sum_gauge(gauge, lst):
      global hits, misses
      if gauge is None:
          return len(lst)
      else:
          gain = 0
          for x in lst:
              gain += gauge(x)
      return gain
  
  
  def cmp_gauged(xs, ys, gauges):
      for gauge in gauges:
          gx = sum_gauge(gauge, xs)
          gy = sum_gauge(gauge, ys)
          c = cmp(gx, gy)
          if c:
              return c
      return 0
  
  
  class InducedRect:
      def __init__(self, s, lines, lnos):
          self.s = s
          self.width = s.width
          self.all_lines = s.all_lines
          self.lines = lines
          self.lnos = lnos
  
  
  class InducedRightRect(InducedRect, RightRect):
      pass
  
  
  class InducedLeftRect(InducedRect, LeftRect):
      pass
  
  
  def brect(lines):
      if len(lines) <= 1:
          return [LeftRect(0, lines)]
      newrects = [LeftRect(0, lines), RightRect(0, lines)]
      donerects = []
      while newrects:
          oldrects = newrects
          newrects = []
          for r in oldrects:
              width = r.width
              while 1:
                  is_done = 0
                  d = {}
                  pos = width ^ r.dir
                  for line in r.lines:
                      if width < len(line):
                          d.setdefault(line[pos], []).append(line)
                      else:
                          is_done = 1
                  if is_done or len(d) != 1:
                      break
                  r.width = width = width + 1
              donerects.append(r)
              width += 1
              for k, v in list(d.items()):
                  if len(v) > 1:
                      new_r = r.__class__(width, v)
                      newrects.append(new_r)
  
      return donerects
  
  
  def choose(rects, lines=[], gauges=[None]):
      def induce(r):
          uncommons = r.get_uncommons()
          if len(uncommons) < 2:
              return
          irs = []
          for s in rects:
              if s.dir != r.dir:
                  continue
              pss = []
              uncs = s.get_uncommons(pickednos)
              lnos = s.lnos & ~pickednos
              assert len(uncs) == len(lnos)
              for unc, lno in zip(uncs, lnos):
                  if unc in uncommons:
                      pss.append(lno)
              if len(pss) == len(uncommons):
                  pslnos = immbitset(pss)
                  pss = [lines[lno] for lno in pss]
                  if s.dir == -1:
                      c = InducedRightRect
                  else:
                      c = InducedLeftRect
                  ir = c(s, pss, pslnos)
                  irs.append(ir)
  
          if irs:
              news.extend(irs)
  
      def overlap(r):
          rlnos = r.lnos
          tonews = []
          for s in rects:
              if s is r:
                  continue
              if s.dir != r.dir:
                  continue
              slnos = s.lnos
              if not (slnos & rlnos):
                  continue
              slnos &= ~ pickednos
              if not slnos:
                  # remove
                  continue
              scom = s.common_part
              if not scom:
                  continue
              for t in rects:
                  if t is s:
                      continue
                  if t.dir == s.dir:
                      continue
                  tlnos = t.lnos & ~pickednos
                  if (tlnos & rlnos):
                      continue
                  olnos = tlnos & slnos
                  if not olnos:
                      continue
                  if slnos == tlnos:
                      continue
                  tcom = t.common_part
                  if not tcom:
                      continue
                  c = cmp_gauged(scom, tcom, gauges)
                  if c > 0:
                      continue
  
                  break
  
              else:
                  # s is ok
                  tonews.append(s)
                  rects.remove(s)
          news.extend(tonews)
  
      def picknext():
          while 1:
              if news:
                  r = news[0]
                  del news[0]
              else:
                  r = None
                  for s in list(rects):
                      slnos = s.lnos - pickednos
                      if not slnos:
                          rects.remove(s)
                          continue
                      sn = len(slnos) - 1
                      sw = s.width
                      if r is not None:
                          if not sw:
                              break
                          if not sn:
                              continue
                          if rwn:
                              rmemo = r.gainmemo
                              smemo = s.gainmemo
                              c = 0
                              for gauge in gauges:
                                  try:
                                      gr = rmemo[gauge]
                                  except KeyError:
                                      gr = sum_gauge(gauge, r.common_part)
                                      rmemo[gauge] = gr
                                  gr *= rn
                                  try:
                                      gs = smemo[gauge]
                                  except KeyError:
                                      gs = sum_gauge(gauge, s.common_part)
                                      smemo[gauge] = gs
                                  gs *= sn
                                  c = gr - gs
                                  if c:
                                      break
                              if c >= 0:
                                  continue
                      r = s
                      rlnos = slnos
                      if not sw:
                          break
                      rn = sn
                      rw = sw
                      rwn = sn * sw
                  if r is not None:
                      rects.remove(r)
              if r is not None:
                  r.reducelines(pickednos)
                  if r.lnos:
                      return r
  
      def cmpinit(x):
          return x.width, x.dir, x.lnos[0]
  
      if gauges[0] is None:
          gauges = gauges[1:]
  
      lnobyid = dict([(id(line), i) for i, line in enumerate(lines)])
  
      orects = rects
      rects = list(orects)
  
      for r in rects:
          r.init2(lnobyid, lines)
  
      rects.sort(key=cmpinit, reverse=True)
  
      allnos = immbitrange(len(lines))
  
      pickednos = mutbitset()
      pickedrects = []
  
      news = []
      while pickednos != allnos:
          r = picknext()
          pickednos |= r.lnos
          pickedrects.append(r)
          induce(r)
          overlap(r)
  
      return pickedrects
  
  
  def chooserects(lines, gauges=[None]):
      rects = brect(lines)
      choosen = choose(rects, lines, gauges)
      return choosen
  
  
  def pr():
      x = chooserects(['abc', 'ade'])
      x = chooserects(['abc',
                       'abe',
                       'ace',
                       'xby'])
  
      print(x)
      x = chooserects(['ab1',
                       'ab2',
                       'ac3',
                       'ac4'])
  
      print(x)
  
      # Case where.. (from right).. :
      # the total gain of two rects (bfbf+cfcf = 4) is greater than the gain of another
      # overlapping rect (ffff == 3), although the individual gains are less (= 2).
      # But in this case at least, the end result should likely become the same
  
      x = chooserects([
          '1bf',
          '2bf',
          '3cf',
          '4cf'])
  
      print(x)
  
      # Case where it chooses twice..
  
      x = chooserects([
          'abc',
          'abd',
          'bcx',
          'bdy'
      ])
  
      print('TW', x)
  
      # Case where it didn't choose enough rects
  
      x = ([
          'abc',
          'abd',
          'e'
      ])
  
      print(chooserects(x))
  
      # Case where it should prefer one side or the other
      # i.e. left traditionally
  
      print(chooserects(['abc', 'axc']))
  
      # Case where it should give a width 0 rect
  
      print(chooserects(['a', '']))
  
      # Case with overlap
  
      print(chooserects(['abcd', 'abce', 'a', 'f']))
  
      # Case with induce
  
      print(chooserects(['abcd', 'abce', 'd', 'e']))
  
      print(chooserects(['auvw', 'buvw', 'a', 'b']))
      print(chooserects(['axuvw', 'bxuvw', 'axy', 'bxy', 'cy']))
  
  
  def tmany():
      for i in range(100):
          x = chooserects(['abc',
                           'abe',
                           'ace',
                           'xby'])
  