Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

allyourcode

By: a guest on Apr 29th, 2009  |  syntax: Python  |  size: 9.80 KB  |  views: 172  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. from itertools import chain
  2.  
  3. EPSILON = object()
  4.  
  5. class GNFA:
  6.     """
  7.    tests:
  8.    >>> a = GNFA('a', ['ab1'], set('b'))
  9.    >>> a.pre('a')
  10.    set([])
  11.    >>> a.post('a')
  12.    set(['b'])
  13.    >>> a.pre('b')
  14.    set(['a'])
  15.    >>> a.post('b')
  16.    set([])
  17.    """
  18.  
  19.     def __init__(self, startState, transitions, finalStates):
  20.         ## infer state set from transitions
  21.         self.states = set()
  22.         self.states.update(q for q, r, lab in transitions)
  23.         self.states.update(r for q, r, lab in transitions)
  24.  
  25.         assert startState in self.states
  26.         self.startState  = startState
  27.  
  28.         self._labels = dict(((q, r), lab) for q, r, lab in transitions)
  29.  
  30.         self.transitions = Index(transitions, 'start end label'.split())
  31.  
  32.         assert finalStates <= self.states
  33.         self.finalStates = finalStates
  34.  
  35.     def __str__(self):
  36.         return ("startState  => %(startState)s\n"
  37.                 "transitions => %(transitions)s\n"
  38.                 "finalStates => %(finalStates)s" %
  39.                 self.__dict__ )
  40.  
  41.     def re(self):
  42.         """
  43.        test:
  44.        >>> a = GNFA('a', ['ab1'], set('b'))
  45.        >>> a.re()
  46.        '1'
  47.  
  48.        >>> import re
  49.        >>> a2 = GNFA('a', ['ab1', 'ba1', 'ac0', 'ca0', 'bd0', 'db0', 'cd1', 'dc1'], set('b'))
  50.        >>> eo = re.compile(a2.re() + '$')
  51.        >>> def binary(n):
  52.         ...     if n == 0: return '0'
  53.         ...     digits = []
  54.         ...     while n:
  55.         ...             if n % 2: digits.append('1')
  56.         ...             else: digits.append('0')
  57.         ...             n >>= 1
  58.         ...     return ''.join(reversed(digits))
  59.        >>> binary(0)
  60.        '0'
  61.        >>> binary(1)
  62.        '1'
  63.        >>> binary(2)
  64.        '10'
  65.        >>> binary(3)
  66.        '11'
  67.        >>> binary(4)
  68.        '100'
  69.        >>> binary(5)
  70.        '101'
  71.        >>> binary(6)
  72.        '110'
  73.        >>> binary(7)
  74.        '111'
  75.        >>> def eo_p(s): return s.count('1') % 2 == 1 and s.count('0') % 2 == 0
  76.        ...
  77.        >>> for n in range(10000):
  78.         ...     s = binary(n)
  79.         ...     if eo_p(s) != bool(eo.match(s)):
  80.         ...             print n
  81.         ...             break
  82.        ...
  83.        """
  84.         normalized = self.normalized()
  85.  
  86.         ## rip states in self from normalized
  87.         for q in self.states:
  88.             normalized.irip(q)
  89.  
  90.         ## return single remaining label in normlized
  91.         res = list(normalized._labels.values())
  92.         assert len(res) == 1
  93.         return res[0]
  94.  
  95.     def normalized(self):
  96.         startState = object()  # construct a new start and end states
  97.         finalState = object()
  98.  
  99.         ## add transitions from new start state and to new end state
  100.         transitions = set(self.transitions)
  101.         transitions.add( (startState, self.startState, EPSILON) )
  102.         transitions.update((f, finalState, EPSILON) for f in self.finalStates)
  103.  
  104.         return GNFA(startState, transitions, set([finalState]))
  105.  
  106.     def irip(self, q):
  107.         """
  108.        tests:
  109.        >>> a = GNFA('a', ['ab0', 'bc0'], set(['c']))
  110.        >>> a.irip('b')
  111.        >>> print a
  112.        startState  => a
  113.        transitions => set([('a', 'c', '00')])
  114.        finalStates => set(['c'])
  115.        >>> a._labels
  116.        {('a', 'c'): '00'}
  117.        """
  118.         pre  = self.pre(q)
  119.         post = self.post(q)
  120.         selfLoop = self._labels.get( (q,q), EPSILON )
  121.  
  122.         ## add new new transitions corresponding to paths going through q
  123.         for p in pre:
  124.             for r in post:
  125.                 lab = reConcat(self._labels[p,q],
  126.                                reStar(selfLoop),
  127.                                self._labels[q,r] )
  128.                 self.addTransition(p, r, lab)
  129.  
  130.         self.removeState(q)
  131.  
  132.     def addTransition(self, q, r, lab):
  133.         """
  134.        test:
  135.        >>> a = GNFA('a', ['ab1'], set('b'))
  136.        >>> a.addTransition('a', 'b', 'the world is ending')
  137.        '(1|the world is ending)'
  138.        >>> print a
  139.        startState  => a
  140.        transitions => set([('a', 'b', '(1|the world is ending)')])
  141.        finalStates => set(['b'])
  142.        >>> a._labels
  143.        {('a', 'b'): '(1|the world is ending)'}
  144.        """
  145.         if (q, r) in self._labels:
  146.             oldLab = self._labels[q,r]
  147.             newLab = reUnion(oldLab, lab)          # union labels
  148.             self._labels[q,r] = newLab             # update self._labels with new label
  149.             self.transitions.remove(q, r, oldLab)  # update self.transitions with new transition
  150.             self.transitions.add(q, r, newLab)
  151.             return newLab
  152.         else:
  153.             self._labels[q,r] = lab
  154.             self.transitions.add(q, r, lab)
  155.             return lab
  156.  
  157.     def removeState(self, q):
  158.         """
  159.        tests:
  160.        >>> a = GNFA('a', ['ab1'], set('b'))
  161.        >>> a.removeState('b')
  162.        >>> print a
  163.        startState  => a
  164.        transitions => set([])
  165.        finalStates => set([])
  166.        >>> a._labels
  167.        {}
  168.        """
  169.         if q == self.startState:
  170.             raise ValueError('Cannot remove the start state.')
  171.  
  172.         pre = self.pre(q)
  173.         for p in pre:
  174.             lab = self._labels[p,q]
  175.             self.transitions.remove(p, q, lab)
  176.             del self._labels[p,q]
  177.  
  178.         post = self.post(q)
  179.         for r in post:
  180.             lab = self._labels[q,r]
  181.             self.transitions.remove(q, r, lab)
  182.             del self._labels[q,r]
  183.  
  184.         if (q,q) in self._labels:
  185.             lab = self._labels[q,q]
  186.             self.transitions.remove(q, q, lab)
  187.             del self._labels[q,q]
  188.  
  189.         self.finalStates.discard(q)  # discard succeeds even if q does not exist
  190.  
  191.     def pre(self, q):
  192.         """Returns a set of predecessors.
  193.  
  194.        Result does not include argument.
  195.        """
  196.         return self.transitions.project1(
  197.             self.transitions.select(1, q),
  198.             'start' ) - set([q])
  199.  
  200.     def post(self, q):
  201.         """Returns a set of successors.
  202.  
  203.        Result does not include argument.
  204.        """
  205.         return self.transitions.project1(
  206.             self.transitions.select(0, q),
  207.             'end' ) - set([q])
  208.  
  209. class Index:
  210.     """
  211.    tests:
  212.    >>> i = Index(['abc', 'adc', 'bbb'])
  213.  
  214.    >>> i.select(0, 'crazy')
  215.    set([])
  216.    >>> i.select(1, 'crazy')
  217.    set([])
  218.    >>> i.select(2, 'crazy')
  219.    set([])
  220.  
  221.    >>> i.select(0, 'a')
  222.    set([('a', 'b', 'c'), ('a', 'd', 'c')])
  223.    >>> i.select(0, 'b')
  224.    set([('b', 'b', 'b')])
  225.    >>> i.select(1, 'b')
  226.    set([('b', 'b', 'b'), ('a', 'b', 'c')])
  227.    >>> i.select(2, 'c')
  228.    set([('a', 'b', 'c'), ('a', 'd', 'c')])
  229.  
  230.    >>> i.removeTuple('bbb')
  231.    >>> print i
  232.    set([('a', 'b', 'c'), ('a', 'd', 'c')])
  233.    """
  234.  
  235.     def __init__(self, tuples, columnNames=None):
  236.         ## set self.columnNames and determine arity
  237.         if columnNames is None:
  238.             arity, tuples = inferArity(tuples)
  239.             self.columnNames = columnNames = range(arity)
  240.         else:
  241.             self.columnNames = columnNames
  242.             arity = len(columnNames)
  243.  
  244.         ## for determining column number
  245.         self._columnName2columnNumber = dict((name, n) for n, name in enumerate(columnNames))
  246.  
  247.         self._tables = [{} for x in range(arity)]  # initialize indeces
  248.         self.update(tuples)  # populate indeces
  249.  
  250.     def getArity(self): return len(self.columnNames)
  251.  
  252.     arity = property(getArity)
  253.  
  254.     def __iter__(self):
  255.         return chain(*self._tables[0].values())
  256.  
  257.     def __str__(self):
  258.         return str(set(iter(self)))
  259.  
  260.     def select(self, col, val):
  261.         return self._tables[self.columnNumber(col)].get(val, set())
  262.  
  263.     def project(self, tuples, *cols):
  264.         cols = map(self.columnNumber, cols)
  265.         return set(tuple(tup[i] for i in cols) for tup in tuples)
  266.  
  267.     def project1(self, tuples, col):
  268.         col = self.columnNumber(col)
  269.         return set(tup[col] for tup in tuples)
  270.  
  271.     def columnNumber(self, col):
  272.         try:
  273.             return self._columnName2columnNumber[col]
  274.         except KeyError as ex:
  275.             if isinstance(col, int):
  276.                 return col
  277.             raise
  278.  
  279.     def update(self, tuples):
  280.         for tup in tuples:
  281.             self.addTuple(tup)
  282.  
  283.     def add(self, *tup):
  284.         self.assertArity(tup)
  285.         ## update all tables
  286.         for val, tab in zip(tup, self._tables):
  287.             tab.setdefault(val, set()).add(tup)
  288.  
  289.     def addTuple(self, tup):
  290.         self.add(*tup)
  291.  
  292.     def remove(self, *tup):
  293.         """Removes the tuple.
  294.  
  295.        Tuple must exist.
  296.        """
  297.         self.assertArity(tup)
  298.         ## remove from all tables
  299.         for val, tab in zip(tup, self._tables):
  300.             tab[val].remove(tup)
  301.  
  302.     def removeTuple(self, tup):
  303.         self.remove(*tup)
  304.  
  305.     def assertArity(self, tup):
  306.         if len(tup) != self.arity:
  307.             raise ValueError("%d arguments given to an Index with arity %d." %
  308.                              (len(tup), self.arity) )
  309.  
  310. def reConcat(*res):
  311.     """
  312.    tests:
  313.    >>> reConcat('a', 'b')
  314.    'ab'
  315.    >>> reConcat('a', EPSILON)
  316.    'a'
  317.    """
  318.     return ''.join(re for re in res if re is not EPSILON)
  319.  
  320. def reUnion(*res):
  321.     """
  322.    tests:
  323.    >>> reUnion('a', 'b')
  324.    '(a|b)'
  325.    >>> reUnion('a', EPSILON)
  326.    '(a)'
  327.    """
  328.     return '(' + '|'.join(re for re in res if re is not EPSILON) + ')'
  329.  
  330. def reStar(re):
  331.     """
  332.    tests:
  333.    >>> reStar('a')
  334.    '(a)*'
  335.    >>> reStar(EPSILON) is EPSILON
  336.    True
  337.    """
  338.     if re is EPSILON:
  339.         return EPSILON
  340.     else:
  341.         return '(%s)*' % re
  342.  
  343. def inferArity(tuples):
  344.     tup, rest = first(tuples)
  345.     return len(tup), chain((tup,), rest)
  346.  
  347. def first(seq):
  348.     """Returns the first element, and an iterator with the remaining elements.
  349.  
  350.    If there is no first element, throw StopIteration.
  351.    """
  352.     it = iter(seq)
  353.     return it.next(), it