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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
"""Utility classes and functions.
"""
from . import g
import weakref
def gen_shuffle(iter_obj):
sample = range(len(iter_obj))
while sample:
n = sample.pop(g.rng.randrange(len(sample)))
yield iter_obj[n]
def rn_seq(seq):
return g.rng.choice(seq)
def rn_exit(x, return_node=True):
initdr, stop = rn(3), 0
while stop < 4:
initdr = (initdr + 1) % 4
if ((initdr == 0 and not x.north) or (initdr == 1 and not x.east) or
(initdr == 2 and not x.south) or (initdr == 3 and not x.west)):
stop += 1
else:
if return_node:
return [x.north, x.east, x.south, x.west][initdr]
else:
return initdr
else:
return None
def rn(x=None, y=None):
if x is y is None:
return g.rng.randint(0, 1)
elif y is None:
if x == 0:
return 0
elif x >= 0:
return g.rng.randint(0, x - 1)
else:
return g.rng.randint(x, -x)
else:
return g.rng.randint(x, y)
def rn_node(allow_leave=0, region=0):
for n in gen_shuffle(g.nodes):
if n.locked: continue
if not allow_leave and n.region != region: continue
return n
def nsew(here, there):
if here.north is there: return 'north'
elif here.south is there: return 'south'
elif here.east is there: return 'east'
elif here.west is there: return 'west'
else: return 'somewhere'
def d(n, x):
return sum(g.rng.randint(1, x) for _ in xrange(n))
def coaligned(a, b):
return a.alignment.__cmp__(0) == b.alignment.__cmp__(0)
class WeakrefProperty(object):
__slots__ = 'propname',
def __init__(self, propname):
self.propname = propname
def __get__(self, obj, cls=None):
value = getattr(obj, self.propname)
if value is None:
return None
else:
return value()
def __set__(self, obj, value):
if value is None:
setattr(obj, self.propname, None)
else:
setattr(obj, self.propname, weakref.ref(value))
def __delete__(self, obj):
setattr(obj, self.propname, None)
class priorityDictionary(dict):
def __init__(self):
self.__heap = []
dict.__init__(self)
def smallest(self):
if len(self) == 0:
raise IndexError, "smallest of empty priorityDictionary"
heap = self.__heap
while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
lastItem = heap.pop()
insertionPoint = 0
while 1:
smallChild = 2*insertionPoint+1
if smallChild+1 < len(heap) and \
heap[smallChild] > heap[smallChild+1]:
smallChild += 1
if smallChild >= len(heap) or lastItem <= heap[smallChild]:
heap[insertionPoint] = lastItem
break
heap[insertionPoint] = heap[smallChild]
insertionPoint = smallChild
return heap[0][1]
def __iter__(self):
def iterfn():
while len(self) > 0:
x = self.smallest()
yield x
del self[x]
return iterfn()
def __setitem__(self,key,val):
dict.__setitem__(self,key,val)
heap = self.__heap
if len(heap) > 2 * len(self):
self.__heap = [(v,k) for k,v in self.iteritems()]
self.__heap.sort() # builtin sort likely faster than O(n) heapify
else:
newPair = (val,key)
insertionPoint = len(heap)
heap.append(None)
while insertionPoint > 0 and newPair < heap[(insertionPoint-1)//2]:
heap[insertionPoint] = heap[(insertionPoint-1)//2]
insertionPoint = (insertionPoint-1)//2
heap[insertionPoint] = newPair
def setdefault(self,key,val):
if key not in self:
self[key] = val
return self[key]
|