multiple_dimensions_table.py

# -*- coding: utf-8 -*-
import re

class MultipleDimensionsTable(object):

    def __init__(self):
        self.src = []

    def _convert(self, i, j, vs):
        v = vs[i][j]
        t = type(v)
        if t == float or t == int:
            return float(v)
        if t == str or t == unicode:
            if v == '^': return self._convert(i-1, j, vs)
            if v == 'v': return self._convert(i+1, j, vs)
            if v == '<': return self._convert(i, j-1, vs)
            if v == '>': return self._convert(i, j+1, vs)
            r = re.match(r'^([\d\.]+)$', v)

            if r:
                return float(v)
            r = re.match(r'^\@(\d*)$', v)
            if r:
                ref = r.group(1)
                return self._convert(int(ref), j, vs)
            r = re.match(r'^(\d*)~(\d*)$', v)
            if r:
                s, e = r.group(1), r.group(2)
                s = float(s) if s != '' else float('-inf')
                e = float(e) if e != '' else float('+inf')
                return (s, e, )

    def _order_by_accuracy(self):
        def comp(_a, _b):
            a = _a[0]
            b = _b[0]
            if len(a) != len(b): return 1 if len(b) > len(a) else -1
            _inf = float('-inf')
            inf = float('inf')
            inf_a = 0
            dirty_inf_a = 0
            area_a = 1
            for x in a:
                if type(x) != tuple: continue
                (min, max) = x
                if min == _inf and max == inf:
                    inf_a+=1
                    continue
                if min == _inf or  max == inf:
                    dirty_inf_a+=1
                    continue
                w = ((max - min) + 1)
                area_a = area_a * w
            inf_b = 0
            dirty_inf_b = 0
            area_b = 1
            for x in b:
                if type(x) != tuple: continue
                (min, max) = x
                if min == _inf and max == inf:
                    inf_b+=1
                    continue
                if min == _inf or  max == inf:
                    dirty_inf_b+=1
                    continue
                w = ((max - min) + 1)
                area_b = area_b * w
            if inf_a != inf_b:             return 1 if inf_a > inf_b else -1
            if dirty_inf_a != dirty_inf_b: return 1 if dirty_inf_a > dirty_inf_b else -1
            return area_a - area_b

        # use my qsort because sorted() in python3 doesn't support cmp parameter.
        def qsort(list, fn):
            if list == []: return []
            else:
                pivot = list[0]
                lesser  = qsort([x for x in list[1:] if fn(x, pivot) < 0], fn)
                greater = qsort([x for x in list[1:] if 0 <= fn(x, pivot)], fn)
                return lesser + [pivot] + greater

        self.src = qsort(self.src, comp)

    def set(self, cond):
        cond_list = [cond]
        c = []
        l = len(cond)
        v = cond[l-1]
        for j in xrange(0, l-1):
            c.append(self._convert(0, j, cond_list))
        self.src.append((c, v, ))
        self._order_by_accuracy()

    def bulk_set(self, cond_list):
        for i in xrange(0, len(cond_list)):
            cond = cond_list[i]
            c = []
            l = len(cond)
            v = cond[l-1]
            for j in xrange(0, l-1):
                c.append(self._convert(i, j, cond_list))
            self.src.append((c, v, ))
        self._order_by_accuracy()

    def get(self, points, _default=None):
        plen = len(points)
        for s in self.src:
            cond = s[0]
            val  = s[1]
            clen = len(cond)
            for i in xrange(0, clen):
                if plen <= i: return val
                c = cond[i]
                p = points[i]
                if type(c) == tuple:
                    if not (c[0] <= p and p <= c[1]): break
                else:
                    if not (c == p): break
            else:
                return val
        return _default


def test():
    tbl = MultipleDimensionsTable()
    v = '''
~       , 0~9       , @9               , 1500~            , 50,
^       , 10~       , ~                , 0~299            , 100,
@0      , @0        , 0~99             , ^                , 300,
^       , <         , >                , ~                , 0,
~       , @7        , ^                , 300~1499         , 75,
0~100   , @0        , ^                , @1               , 200,
~       , ^         , ^                , ^                , 150,
@3      , @9        , ^                , <                , 1,
~       , 0~9       , ^                , @4               , 100,
~       , @1        , ^                , 1500~            , 33,
'''
    vs = filter(
        lambda a: a != [],
        map(lambda l: filter(
                lambda a: a != '',
                map(lambda c: c.strip(), l.split(','))), v.split('\n')))
    tbl.bulk_set(vs)
    inf = float('inf')
    _inf = float('-inf')
    if tbl.src != [([(_inf, inf), (0.0, 9.0), (0, 99.0), (0.0, 299.0)], '300'),
                   ([(0, 100), (0.0, 9.0), (_inf, inf), (0.0, 299.0)], '200'),
                   ([(_inf, inf), (0.0, 9.0), (_inf, inf), (0.0, 299.0)], '150'),
                   ([(_inf, inf), (0.0, 9.0), (_inf, inf), (300.0, 1499.0)], '100'),
                   ([(_inf, inf), (0.0, 9.0), (_inf, inf), (1500.0, inf)], '50'),
                   ([(_inf, inf), (10.0, inf), (_inf, inf), (0.0, 299.0)], '100'),
                   ([(_inf, inf), (10.0, inf), (_inf, inf), (300.0, 1499.0)], '75'),
                   ([(_inf, inf), (10.0, inf), (_inf, inf), (1500.0, inf)], '33'),
                   ([(_inf, inf), (10.0, inf), (_inf, inf), (_inf, inf)], '1'),
                   ([(_inf, inf), (_inf, inf), (_inf, inf), (_inf, inf)], '0')]:
        raise Exception('src is wrong. ' + str(tbl.src))
    if (tbl.get((10, 10, 1000, 322)) != '75' or
        tbl.get((10, 10, 1000, 0)) != '100' or
        tbl.get((10, 10, 1000, -10)) != '1'):
        raise Exception('get() is wrong.')
    print 'OK'

if __name__ == '__main__':
    test()