Edit

[EDIT] FILE: RE_Rect.py

""" 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'])

CANCEL