commons.structs

1 # -*- mode: python; tab-width: 4; indent-tabs-mode: nil; py-indent-offset: 4; -*- 2 # vim:ft=python:et:sw=2:ts=2 3 4 """ 5 Data structures: Heaps, lists, queues, and Python hacks. 6 """ 7 8 import copy, heapq, itertools, sys, unittest 9 from commons.decs import recursion_guard

10 11 -class bidict( object ):

12 """Bi-directional dictionary; assumes 1:1 mappings."""

13 - def __init__( self ): self.a2b = {}; self.b2a = {}

14 - def add( self, a, b ): self.a2b[a] = b; self.b2a[b] = a

15 - def get_a( self, a ): return self.a2b[a]

16 - def get_b( self, b ): return self.b2a[b]

17 - def get_a_default( self, a, d = None ): return self.a2b.get(a,d)

18 - def get_b_default( self, b, d = None ): return self.b2a.get(b,d)

19 - def contains_a( self, a ): return a in self.a2b

20 - def contains_b( self, b ): return b in self.b2a

21 - def __len__( self ): return len( self.a2b )

22 - def items( self ): return self.a2b.iteritems()

23 - def a_values( self ): return self.a2b.keys()

24 - def b_values( self ): return self.b2a.keys()

25 - def clear( self ): self.a2b.clear(); self.b2a.clear()

26 - def remove_a( self, a ):

27 b = self.a2b.pop(a) 28 del self.b2a[b] 29 return b

30 - def remove_b( self, b ):

31 a = self.b2a.pop(b) 32 del self.a2b[a] 33 return a

34

35 -class idict( dict ):

36 """Case-insensitive string-keyed dictionary."""

37 - def __getitem__( self, k ):

38 return dict.__getitem__( self, k.lower() )

39 - def __setitem__( self, k, v ):

40 return dict.__setitem__( self, k.lower(), v )

41 - def __delitem__( self, k ):

42 return dict.__delitem__( self, k.lower() )

43

44 -class pprint_mixin(object):

45 'Mixin for pretty-printing free_structs.' 46 47 @recursion_guard("<...>")

48 - def __str__(self, nesting = 1):

49 attrs = [] 50 indentation = " " * nesting 51 for k, v in self.__dict__.iteritems(): 52 if not k.startswith("_"): 53 text = [indentation, k, " = "] 54 if isinstance(v, free_struct): 55 text.append(v.__str__(nesting + 1)) 56 else: 57 text.append(repr(v)) 58 attrs.append("".join(text)) 59 attrs.sort() 60 attrs.insert(0, self.__class__.__name__ + ":") 61 return "\n".join(attrs)

62

63 -class free_struct( object ):

64 """ 65 General-purpose Python object with a bunch of boilerplate utility 66 functionality built-in. Subclass-friendly. 67 """

68 - def __init__( self, d = {}, **args ):

69 self.__dict__.update( d ) 70 self.__dict__.update( args )

71 @recursion_guard("<...>")

72 - def __repr__( self ):

73 fields = ( '%s = %r' % ( name, value ) 74 for name, value in self.__dict__.iteritems() ) 75 return "%s(%s)" % ( self.__class__.__name__, ', '.join( fields ) )

76 - def __eq__( self, other ):

77 return type( self ) == type( other ) and \ 78 self.__dict__ == other.__dict__

79 - def __ne__(self, other): return not (self == other)

80 - def __add__(self, other):

81 """ 82 Return a copy of this but with additional attributes corresponding to 83 the items or attributes from the other operand, depending on if it's a 84 dict or an object, respectively. 85 """ 86 dup = copy.copy(self) 87 d = other if isinstance(other, dict) else other.__dict__ 88 dup.__dict__.update(d) 89 return dup

90 - def __radd__(self, other):

91 """ 92 Return a copy of this but with additional attributes corresponding to 93 the items or attributes from the other operand, depending on if it's a 94 dict or an object, respectively. 95 """ 96 dup = copy.copy(self) 97 d = other if isinstance(other, dict) else other.__dict__ 98 dup.__dict__.update(d) 99 return dup

100 - def __sub__(self, other):

101 """ 102 Return a copy of this but with the specified attributes removed. 103 """ 104 dup = copy.copy(self) 105 for attr in other: del dup[attr] 106 return dup

107

108 -class LazyObject( object ):

109 """ 110 An object whose attributes do nothing. 111 112 @todo: Unfortunate name; has nothing to do with lazy 113 evaluation. Check where this is used and try to rename it. 114 """

115 - def __getattr__( self, foo ):

116 return self.foo

117 - def foo( self, *args ):

118 pass

119

120 -class Enum:

121 """Create an enumerated type, then add var/value pairs to it. 122 The constructor and the method .ints(names) take a list of variable names, 123 and assign them consecutive integers as values. The method .strs(names) 124 assigns each variable name to itself (that is variable 'v' has value 'v'). 125 The method .vals(a=99, b=200) allows you to assign any value to variables. 126 A 'list of variable names' can also be a string, which will be .split(). 127 The method .end() returns one more than the maximum int value. 128 Example: opcodes = Enum("add sub load store").vals(illegal=255). 129 130 From U{http://norvig.com/python-iaq.html}. 131 132 @copyright: Peter Norvig""" 133

134 - def __init__(self, names=[]): self.ints(names)

135

136 - def set(self, var, val):

137 """Set var to the value val in the enum.""" 138 if var in vars(self).keys(): raise AttributeError("duplicate var in enum") 139 if val in vars(self).values(): raise ValueError("duplicate value in enum") 140 vars(self)[var] = val 141 return self

142

143 - def strs(self, names):

144 """Set each of the names to itself (as a string) in the enum.""" 145 for var in self._parse(names): self.set(var, var) 146 return self

147

148 - def ints(self, names):

149 """Set each of the names to the next highest int in the enum.""" 150 for var in self._parse(names): self.set(var, self.end()) 151 return self

152

153 - def vals(self, **entries):

154 """Set each of var=val pairs in the enum.""" 155 for (var, val) in entries.items(): self.set(var, val) 156 return self

157

158 - def end(self):

159 """One more than the largest int value in the enum, or 0 if none.""" 160 try: return max([x for x in vars(self).values() if type(x)==type(0)]) + 1 161 except ValueError: return 0

162

163 - def _parse(self, names):

164 ### If names is a string, parse it as a list of names. 165 if type(names) == type(""): return names.split() 166 else: return names

167

168 # Public domain 169 -class ListMixin(object):

170 """ 171 Defines all list operations from a small subset of methods. 172 173 Subclasses should define _get_element(i), _set_element(i, value), 174 __len__(), _resize_region(start, end, new_size) and 175 _constructor(iterable). Define __iter__() for extra speed. 176 177 The _get_element() and _set_element() methods are given indices with 178 0 <= i < len(self). 179 180 The _resize_region() method should resize the slice self[start:end] 181 so that it has size new_size. It is given indices such that 182 start <= end, 0 <= start <= len(self) and 0 <= end <= len(self). 183 The resulting elements in self[start:start+new_size] can be set to 184 None or arbitrary Python values. 185 186 The _constructor() method accepts an iterable and should return a 187 new instance of the same class as self, populated with the elements 188 of the given iterable. 189 190 From U{http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440656}. 191 192 @copyright: Connelly Barns 193 """

194 - def __cmp__(self, other):

195 return cmp(list(self), list(other))

196

197 - def __hash__(self):

198 raise TypeError('list objects are unhashable')

199

200 - def __iter__(self):

201 for i in xrange(len(self)): 202 yield self._get_element(i)

203

204 - def _tuple_from_slice(self, i):

205 """ 206 Get (start, end, step) tuple from slice object. 207 """ 208 (start, end, step) = i.indices(len(self)) 209 # Replace (0, -1, 1) with (0, 0, 1) (misfeature in .indices()). 210 if step == 1: 211 if end < start: 212 end = start 213 step = None 214 if i.step == None: 215 step = None 216 return (start, end, step)

217

218 - def _fix_index(self, i):

219 if i < 0: 220 i += len(self) 221 if i < 0 or i >= len(self): 222 raise IndexError('list index out of range') 223 return i

224

225 - def __getitem__(self, i):

226 if isinstance(i, slice): 227 (start, end, step) = self._tuple_from_slice(i) 228 if step == None: 229 indices = xrange(start, end) 230 else: 231 indices = xrange(start, end, step) 232 return self._constructor([self._get_element(i) for i in indices]) 233 else: 234 return self._get_element(self._fix_index(i))

235

236 - def __setitem__(self, i, value):

237 if isinstance(i, slice): 238 (start, end, step) = self._tuple_from_slice(i) 239 if step != None: 240 # Extended slice 241 indices = range(start, end, step) 242 if len(value) != len(indices): 243 raise ValueError(('attempt to assign sequence of size %d' + 244 ' to extended slice of size %d') % 245 (len(value), len(indices))) 246 for (j, assign_val) in enumerate(value): 247 self._set_element(indices[j], assign_val) 248 else: 249 # Normal slice 250 if len(value) != (end - start): 251 self._resize_region(start, end, len(value)) 252 for (j, assign_val) in enumerate(value): 253 self._set_element(start + j, assign_val) 254 else: 255 # Single element 256 self._set_element(self._fix_index(i), value)

257

258 - def __delitem__(self, i):

259 if isinstance(i, slice): 260 (start, end, step) = self._tuple_from_slice(i) 261 if step != None: 262 # Extended slice 263 indices = range(start, end, step) 264 # Sort indices descending 265 if len(indices) > 0 and indices[0] < indices[-1]: 266 indices.reverse() 267 for j in indices: 268 del self[j] 269 else: 270 # Normal slice 271 self._resize_region(start, end, 0) 272 else: 273 # Single element 274 i = self._fix_index(i) 275 self._resize_region(i, i + 1, 0)

276

277 - def __add__(self, other):

278 if isinstance(other, self.__class__): 279 ans = self._constructor(self) 280 ans += other 281 return ans 282 return list(self) + other

283

284 - def __mul__(self, other):

285 ans = self._constructor(self) 286 ans *= other 287 return ans

288

289 - def __radd__(self, other):

290 if isinstance(other, self.__class__): 291 ans = other._constructor(self) 292 ans += self 293 return ans 294 return other + list(self)

295

296 - def __rmul__(self, other):

297 return self * other

298

299 - def __iadd__(self, other):

300 self[len(self):len(self)] = other 301 return self

302

303 - def __imul__(self, other):

304 if other <= 0: 305 self[:] = [] 306 elif other > 1: 307 aux = list(self) 308 for i in xrange(other-1): 309 self.extend(aux) 310 return self

311

312 - def append(self, other):

313 self[len(self):len(self)] = [other]

314

315 - def extend(self, other):

316 self[len(self):len(self)] = other

317

318 - def count(self, other):

319 ans = 0 320 for item in self: 321 if item == other: 322 ans += 1 323 return ans

324

325 - def reverse(self):

326 for i in xrange(len(self)//2): 327 j = len(self) - 1 - i 328 (self[i], self[j]) = (self[j], self[i])

329

330 - def index(self, x, i=0, j=None):

331 if i != 0 or j is not None: 332 (i, j, ignore) = self._tuple_from_slice(slice(i, j)) 333 if j is None: 334 j = len(self) 335 for k in xrange(i, j): 336 if self._get_element(k) == x: 337 return k 338 raise ValueError('index(x): x not in list')

339

340 - def insert(self, i, x):

341 self[i:i] = [x]

342

343 - def pop(self, i=None):

344 if i == None: 345 i = len(self)-1 346 ans = self[i] 347 del self[i] 348 return ans

349

350 - def remove(self, x):

351 for i in xrange(len(self)): 352 if self._get_element(i) == x: 353 del self[i] 354 return 355 raise ValueError('remove(x): x not in list')

356 357 # Define sort() as appropriate for the Python version. 358 if sys.version_info[:3] < (2, 4, 0):

359 - def sort(self, cmpfunc=None):

360 ans = list(self) 361 ans.sort(cmpfunc) 362 self[:] = ans

363 else:

364 - def sort(self, cmpfunc=None, key=None, reverse=False):

365 ans = list(self) 366 if reverse == True: 367 ans.sort(cmpfunc, key, reverse) 368 elif key != None: 369 ans.sort(cmpfunc, key) 370 else: 371 ans.sort(cmpfunc) 372 self[:] = ans

373

374 - def __copy__(self):

375 return self._constructor(self)

376

377 - def __deepcopy__(self, memo={}):

378 ans = self._constructor([]) 379 memo[id(self)] = ans 380 ans[:] = copy.deepcopy(tuple(self), memo) 381 return ans

382 383 # Tracking idea from R. Hettinger's deque class. It's not 384 # multithread safe, but does work with the builtin Python classes.

385 - def __str__(self, track=[]):

386 if id(self) in track: 387 return '...' 388 track.append(id(self)) 389 ans = '%r' % (list(self),) 390 track.remove(id(self)) 391 return ans

392

393 - def __repr__(self):

394 return self.__class__.__name__ + '(' + str(self) + ')'

395

396 397 # Example usage: 398 399 -class TestList(ListMixin):

400 - def __init__(self, L=[]):

401 self.L = list(L)

402

403 - def _constructor(self, iterable):

404 return TestList(iterable)

405

406 - def __len__(self):

407 return len(self.L)

408

409 - def _get_element(self, i):

410 assert 0 <= i < len(self) 411 return self.L[i]

412

413 - def _set_element(self, i, x):

414 assert 0 <= i < len(self) 415 self.L[i] = x

416

417 - def _resize_region(self, start, end, new_size):

418 assert 0 <= start <= len(self) 419 assert 0 <= end <= len(self) 420 assert start <= end 421 self.L[start:end] = [None] * new_size

422

423 # Now TestList() has behavior identical to that of list(). 424 425 ############################################################################# 426 427 -class Heap(ListMixin):

428 """ 429 A list that maintains the heap invariant. 430 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440673 431 432 TODO using things like pop() is unsafe! they rely on the 433 unimplemented _get_element() 434 435 TODO things like popmin() produce poor error msgs (when empty) 436 """ 437

438 - def __init__(self, iterable=(), key=None):

439 ''' 440 @param iterable: An iterable over items to be added to the heap. 441 @param key: Specifies a function of one argument that is used to 442 extract a comparison key from each heap element. 443 ''' 444 self._key = key 445 self._lst = [] 446 self.extend(iterable) 447 heapq.heapify(self._lst)

448

449 - def peek( self ):

450 return self.get_element( 0 )

451

452 - def push(self, item):

453 '''Push the item onto the heap.''' 454 return heapq.heappush(self._lst, self._wrap(item))

455

456 - def popmin(self):

457 '''Pop the smallest item off the heap''' 458 return self._unwrap(heapq.heappop(self._lst))

459

460 - def replace(self, item):

461 '''Equivalent to "x = heap.popmin(); heap.push(); return x" but more 462 efficient. 463 ''' 464 return self._unwrap(heapq.heapreplace(self._lst, self._wrap(item)))

465

466 - def pushpop(self, item):

467 'Equivalent to "heap.push(); return heap.popmin()" but more efficient.' 468 if self and self[0] < item: 469 return self.replace(item) 470 return item

471

472 - def iterpop(self):

473 '''Return a destructive iterator over the heap's elements. 474 475 Each time next is invoked, it pops the smallest item from the heap. 476 ''' 477 while self: 478 yield self.popmin()

479 480 #---- overrided ListMixin methods ---------------------------------------- 481

482 - def constructor(self, iterable):

483 return self.__class__(iterable, self._key)

484

485 - def __len__(self):

486 return len(self._lst)

487

488 - def get_element(self, pos):

489 return self._unwrap(self._lst[pos])

490

491 - def __setitem__(self, pos, item):

492 if isinstance(pos, slice): 493 raise TypeError('Heap objects do no support slice setting') 494 pos = self._fix_index(pos) 495 item = self._wrap(item) 496 lst = self._lst 497 current = lst[pos] 498 lst[pos] = item 499 if item > current: # re-establish the heap invariant 500 heapq._siftup(lst, pos) 501 if lst[pos] != item: # item found its way below pos 502 return 503 while pos > 0: 504 parentpos = (pos - 1) >> 1 505 parent = lst[parentpos] 506 if parent <= item: 507 break 508 lst[pos] = parent 509 pos = parentpos 510 lst[pos] = item

511

512 - def __delitem__(self, pos):

513 if isinstance(pos, slice): 514 raise TypeError('Heap objects do no support slice deleting') 515 pos = self._fix_index(pos) 516 lst = self._lst 517 if pos == len(lst)-1: 518 del lst[-1] 519 else: 520 self[pos] = self.pop()

521

522 - def __iter__(self):

523 return itertools.imap(self._unwrap, self._lst)

524

525 - def __nonzero__(self):

526 return bool(self._lst)

527

528 - def __cmp__(self, other):

529 raise TypeError('Heap objects do not support comparison')

530

531 - def __eq__(self, other):

532 if not isinstance(other,Heap) or len(self) != len(other): 533 return False 534 for i,j in itertools.izip(self,other): 535 if i != j: return False 536 return True

537

538 - def __ne__(self,other):

539 return not self==other

540

541 - def count(self, item):

542 return self._lst.count()

543 544 append = push 545

546 - def insert(self, pos, item):

547 # ignore the position since it's not certain that it can preserve the 548 # heap invariant 549 self.push(item)

550

551 - def extend(self, other):

552 if self._key is not None: 553 other = itertools.imap(self._wrap, other) 554 push = heapq.heappush; lst = self._lst 555 for item in other: 556 push(lst,item)

557

558 - def sort(self):

559 lst = self._lst; pop = heapq.heappop 560 sorted = []; append = sorted.append 561 while lst: 562 append(pop(lst)) 563 self._lst = sorted

564

565 - def reverse(self):

566 raise TypeError('Heap objects do not support reversal')

567 568 #---- 'private' methods -------------------------------------------------- 569

570 - def _wrap(self, item):

571 if self._key is not None: 572 item = (self._key(item),item) 573 return item

574

575 - def _unwrap(self, item):

576 if self._key is not None: 577 item = item[1] 578 return item

579

580 -def dicts2structs(x):

581 """ 582 Given a tree of lists/dicts, perform a deep traversal to transform all the 583 dicts to structs. 584 """ 585 if type(x) == dict: 586 return free_struct( ( k, dicts2structs(v) ) for k,v in x.iteritems()) 587 elif type(x) == list: 588 return [dicts2structs(v) for v in x] 589 else: 590 return x

591

592 -def structs2dicts(x):

593 """ 594 Given a tree of lists/structs, perform a deep traversal to transform all 595 the structs to dicts. 596 """ 597 if type(x) == free_struct: 598 return dict( ( k, structs2dicts(v) ) for k,v in x.__dict__.iteritems() ) 599 elif type(x) == list: 600 return [structs2dicts(v) for v in x] 601 else: 602 return x

603

604 # 605 # Tests. 606 # 607 608 -class common_tests(unittest.TestCase):

609 - def test_dicts_structs(self):

610 dicts = { 611 'atom': 0, 612 'dict': { 'atom': 'atom', 'list': [1,2,3] }, 613 'list': [ 'atom', {'key': 'value'} ] 614 } 615 616 structs = dicts2structs(dicts) 617 self.assertEqual(structs.atom, dicts['atom']) 618 self.assertEqual(structs.dict.atom, dicts['dict']['atom']) 619 self.assertEqual(structs.dict.list, dicts['dict']['list']) 620 self.assertEqual(structs.list[0], dicts['list'][0]) 621 self.assertEqual(structs.list[1].key, dicts['list'][1]['key']) 622 623 dicts2 = structs2dicts(dicts) 624 self.assertEqual(dicts2['atom'], structs.atom) 625 self.assertEqual(dicts2['dict']['atom'], structs.dict.atom) 626 self.assertEqual(dicts2['dict']['list'], structs.dict.list) 627 self.assertEqual(dicts2['list'][0], structs.list[0]) 628 self.assertEqual(dicts2['list'][1]['key'], structs.list[1].key)

629 630 if __name__ == '__main__': 631 unittest.main() 632

Source Code for Module commons.structs