| OLD | NEW |
| 1 # Copyright (c) 2012 Google Inc. All rights reserved. | 1 # Copyright (c) 2012 Google Inc. All rights reserved. |
| 2 # Use of this source code is governed by a BSD-style license that can be | 2 # Use of this source code is governed by a BSD-style license that can be |
| 3 # found in the LICENSE file. | 3 # found in the LICENSE file. |
| 4 | 4 |
| 5 from __future__ import with_statement | 5 from __future__ import with_statement |
| 6 | 6 |
| 7 import collections | 7 import collections |
| 8 import errno | 8 import errno |
| 9 import filecmp | 9 import filecmp |
| 10 import os.path | 10 import os.path |
| (...skipping 478 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 489 return key in self.map | 489 return key in self.map |
| 490 | 490 |
| 491 def add(self, key): | 491 def add(self, key): |
| 492 if key not in self.map: | 492 if key not in self.map: |
| 493 end = self.end | 493 end = self.end |
| 494 curr = end[1] | 494 curr = end[1] |
| 495 curr[2] = end[1] = self.map[key] = [key, curr, end] | 495 curr[2] = end[1] = self.map[key] = [key, curr, end] |
| 496 | 496 |
| 497 def discard(self, key): | 497 def discard(self, key): |
| 498 if key in self.map: | 498 if key in self.map: |
| 499 key, prev, next = self.map.pop(key) | 499 key, prev_item, next_item = self.map.pop(key) |
| 500 prev[2] = next | 500 prev_item[2] = next_item |
| 501 next[1] = prev | 501 next_item[1] = prev_item |
| 502 | 502 |
| 503 def __iter__(self): | 503 def __iter__(self): |
| 504 end = self.end | 504 end = self.end |
| 505 curr = end[2] | 505 curr = end[2] |
| 506 while curr is not end: | 506 while curr is not end: |
| 507 yield curr[0] | 507 yield curr[0] |
| 508 curr = curr[2] | 508 curr = curr[2] |
| 509 | 509 |
| 510 def __reversed__(self): | 510 def __reversed__(self): |
| 511 end = self.end | 511 end = self.end |
| 512 curr = end[1] | 512 curr = end[1] |
| 513 while curr is not end: | 513 while curr is not end: |
| 514 yield curr[0] | 514 yield curr[0] |
| 515 curr = curr[1] | 515 curr = curr[1] |
| 516 | 516 |
| 517 def pop(self, last=True): | 517 # The second argument is an addition that causes a pylint warning. |
| 518 def pop(self, last=True): # pylint: disable=W0221 |
| 518 if not self: | 519 if not self: |
| 519 raise KeyError('set is empty') | 520 raise KeyError('set is empty') |
| 520 key = self.end[1][0] if last else self.end[2][0] | 521 key = self.end[1][0] if last else self.end[2][0] |
| 521 self.discard(key) | 522 self.discard(key) |
| 522 return key | 523 return key |
| 523 | 524 |
| 524 def __repr__(self): | 525 def __repr__(self): |
| 525 if not self: | 526 if not self: |
| 526 return '%s()' % (self.__class__.__name__,) | 527 return '%s()' % (self.__class__.__name__,) |
| 527 return '%s(%r)' % (self.__class__.__name__, list(self)) | 528 return '%s(%r)' % (self.__class__.__name__, list(self)) |
| (...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 578 return | 579 return |
| 579 visited.add(node) | 580 visited.add(node) |
| 580 visiting.add(node) | 581 visiting.add(node) |
| 581 for neighbor in get_edges(node): | 582 for neighbor in get_edges(node): |
| 582 Visit(neighbor) | 583 Visit(neighbor) |
| 583 visiting.remove(node) | 584 visiting.remove(node) |
| 584 ordered_nodes.insert(0, node) | 585 ordered_nodes.insert(0, node) |
| 585 for node in sorted(graph): | 586 for node in sorted(graph): |
| 586 Visit(node) | 587 Visit(node) |
| 587 return ordered_nodes | 588 return ordered_nodes |
| OLD | NEW |