/usr/lib/python2.7/dist-packages/suds/xsd/deplist.py is in python-suds 0.4.1-15.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 130 131 132 133 134 135 136 137 138 139 140 | # This program is free software; you can redistribute it and/or modify
# it under the terms of the (LGPL) GNU Lesser General Public License as
# published by the Free Software Foundation; either version 3 of the
# License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Library Lesser General Public License for more details at
# ( http://www.gnu.org/licenses/lgpl.html ).
#
# You should have received a copy of the GNU Lesser General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
# written by: Jeff Ortel ( jortel@redhat.com )
"""
The I{depsolve} module defines a class for performing dependancy solving.
"""
from logging import getLogger
from suds import *
log = getLogger(__name__)
class DepList:
"""
Dependancy solving list.
Items are tuples: (object, (deps,))
@ivar raw: The raw (unsorted) items.
@type raw: list
@ivar index: The index of (unsorted) items.
@type index: list
@ivar stack: The sorting stack.
@type stack: list
@ivar pushed: The I{pushed} set tracks items that have been
processed.
@type pushed: set
@ivar sorted: The sorted list of items.
@type sorted: list
"""
def __init__(self):
""" """
self.unsorted = []
self.index = {}
self.stack = []
self.pushed = set()
self.sorted = None
def add(self, *items):
"""
Add items to be sorted.
@param items: One or more items to be added.
@type items: I{item}
@return: self
@rtype: L{DepList}
"""
for item in items:
self.unsorted.append(item)
key = item[0]
self.index[key] = item
return self
def sort(self):
"""
Sort the list based on dependancies.
@return: The sorted items.
@rtype: list
"""
self.sorted = list()
self.pushed = set()
for item in self.unsorted:
popped = []
self.push(item)
while len(self.stack):
try:
top = self.top()
ref = top[1].next()
refd = self.index.get(ref)
if refd is None:
log.debug('"%s" not found, skipped', Repr(ref))
continue
self.push(refd)
except StopIteration:
popped.append(self.pop())
continue
for p in popped:
self.sorted.append(p)
self.unsorted = self.sorted
return self.sorted
def top(self):
"""
Get the item at the top of the stack.
@return: The top item.
@rtype: (item, iter)
"""
return self.stack[-1]
def push(self, item):
"""
Push and item onto the sorting stack.
@param item: An item to push.
@type item: I{item}
@return: The number of items pushed.
@rtype: int
"""
if item in self.pushed:
return
frame = (item, iter(item[1]))
self.stack.append(frame)
self.pushed.add(item)
def pop(self):
"""
Pop the top item off the stack and append
it to the sorted list.
@return: The popped item.
@rtype: I{item}
"""
try:
frame = self.stack.pop()
return frame[0]
except:
pass
if __name__ == '__main__':
a = ('a', ('x',))
b = ('b', ('a',))
c = ('c', ('a','b'))
d = ('d', ('c',))
e = ('e', ('d','a'))
f = ('f', ('e','c','d','a'))
x = ('x', ())
L = DepList()
L.add(c, e, d, b, f, a, x)
print [x[0] for x in L.sort()]
|