Given a list of objects, reorder them so that the constains specified by 'add_pair' are satisfied. The algorithm was adopted from an awk script by Nikita Youshchenko (yoush at cs dot msu dot su)
(self, objects)
| 35 | self.constraints_.append ((first, second)) |
| 36 | |
| 37 | def order (self, objects): |
| 38 | """ Given a list of objects, reorder them so that the constains specified |
| 39 | by 'add_pair' are satisfied. |
| 40 | |
| 41 | The algorithm was adopted from an awk script by Nikita Youshchenko |
| 42 | (yoush at cs dot msu dot su) |
| 43 | """ |
| 44 | # The algorithm used is the same is standard transitive closure, |
| 45 | # except that we're not keeping in-degree for all vertices, but |
| 46 | # rather removing edges. |
| 47 | result = [] |
| 48 | |
| 49 | if not objects: |
| 50 | return result |
| 51 | |
| 52 | constraints = self.__eliminate_unused_constraits (objects) |
| 53 | |
| 54 | # Find some library that nobody depends upon and add it to |
| 55 | # the 'result' array. |
| 56 | obj = None |
| 57 | while objects: |
| 58 | new_objects = [] |
| 59 | while objects: |
| 60 | obj = objects [0] |
| 61 | |
| 62 | if self.__has_no_dependents (obj, constraints): |
| 63 | # Emulate break ; |
| 64 | new_objects.extend (objects [1:]) |
| 65 | objects = [] |
| 66 | |
| 67 | else: |
| 68 | new_objects.append (obj) |
| 69 | obj = None |
| 70 | objects = objects [1:] |
| 71 | |
| 72 | if not obj: |
| 73 | raise BaseException ("Circular order dependencies") |
| 74 | |
| 75 | # No problem with placing first. |
| 76 | result.append (obj) |
| 77 | |
| 78 | # Remove all containts where 'obj' comes first, |
| 79 | # since they are already satisfied. |
| 80 | constraints = self.__remove_satisfied (constraints, obj) |
| 81 | |
| 82 | # Add the remaining objects for further processing |
| 83 | # on the next iteration |
| 84 | objects = new_objects |
| 85 | |
| 86 | return result |
| 87 | |
| 88 | def __eliminate_unused_constraits (self, objects): |
| 89 | """ Eliminate constraints which mention objects not in 'objects'. |
no test coverage detected