1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#!/usr/bin/python3
from collections import namedtuple
from heapq import heappush, heappop
import itertools
# A simple priority queue based on the heapq class.
class PQueue(object):
REMOVED = '<removed-task>' # placeholder for a removed task
def __init__(self):
self.pq = [] # list of entries arranged in a heap
self.entry_finder = {} # mapping of tasks to entries
self.counter = itertools.count() # unique sequence count
self.size = 0
def push(self, task, priority=0):
'Add a new task or update the priority of an existing task'
if task in self.entry_finder:
self.remove(task)
else:
self.size += 1
entry = [priority, next(self.counter), task]
self.entry_finder[task] = entry
heappush(self.pq, entry)
def remove(self, task):
'Mark an existing task as REMOVED. Raise KeyError if not found.'
entry = self.entry_finder.pop(task)
entry[-1] = self.REMOVED
self.size -= 1
def pop(self):
'Remove and return the lowest priority task. Raise KeyError if empty.'
while self.pq:
priority, count, task = heappop(self.pq)
if task is not self.REMOVED:
del self.entry_finder[task]
self.size -= 1
return task
return None
def __len__(self):
return self.size
# Stores a token's type and value, and optionally the position of the first
# character in the lexed stream.
class Token(namedtuple('Token', ['type', 'val', 'pos'])):
__slots__ = ()
# Custom constructor to support default parameters.
def __new__(cls, type, val='', pos=None):
return super(Token, cls).__new__(cls, type, val, pos)
def __str__(self):
return self.val
# Ignore position when comparing tokens. There is probably a cleaner way of
# doing these.
__eq__ = lambda x, y: x[0] == y[0] and x[1] == y[1]
__ne__ = lambda x, y: x[0] != y[0] or x[1] != y[1]
__lt__ = lambda x, y: tuple.__lt__(x[0:2], y[0:2])
__le__ = lambda x, y: tuple.__le__(x[0:2], y[0:2])
__ge__ = lambda x, y: tuple.__ge__(x[0:2], y[0:2])
__gt__ = lambda x, y: tuple.__gt__(x[0:2], y[0:2])
# Only hash token's value (we don't care about position, and types are
# determined by values).
def __hash__(self):
return hash(self[1])
# Return [n]th line in [text].
def get_line(text, n):
lines = text.split('\n')
if n >= 0 and n < len(lines):
return lines[n]
return None
# Indent each line in [text] by [indent] spaces.
def indent(text, indent=2):
return '\n'.join([' '*indent+line for line in text.split('\n')])
|
