• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
78%
SHARE
TWEET

# allyourcode

a guest Apr 29th, 2009 385 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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] )
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
151.             return newLab
152.         else:
153.             self._labels[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.
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:
282.
284.         self.assertArity(tup)
285.         ## update all tables
286.         for val, tab in zip(tup, self._tables):
288.
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
RAW Paste Data
Top