Source Code for Module suds.xsd.deplist

  1  # This program is free software; you can redistribute it and/or modify 
  2  # it under the terms of the (LGPL) GNU Lesser General Public License as 
  3  # published by the Free Software Foundation; either version 3 of the  
  4  # License, or (at your option) any later version. 
  5  # 
  6  # This program is distributed in the hope that it will be useful, 
  7  # but WITHOUT ANY WARRANTY; without even the implied warranty of 
  8  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
  9  # GNU Library Lesser General Public License for more details at 
 10  # ( http://www.gnu.org/licenses/lgpl.html ). 
 11  # 
 12  # You should have received a copy of the GNU Lesser General Public License 
 13  # along with this program; if not, write to the Free Software 
 14  # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 
 15  # written by: Jeff Ortel ( jortel@redhat.com ) 
 16   
 17  """ 
 18  The I{depsolve} module defines a class for performing dependancy solving. 
 19  """ 
 20   
 21  from logging import getLogger 
 22  from suds import * 
 23   
 24  log = getLogger(__name__) 
 25   
 26   
 27 -class DepList: 
 28      """ 
 29      Dependancy solving list. 
 30      Items are tuples: (object, (deps,)) 
 31      @ivar raw: The raw (unsorted) items. 
 32      @type raw: list 
 33      @ivar index: The index of (unsorted) items. 
 34      @type index: list 
 35      @ivar stack: The sorting stack. 
 36      @type stack: list 
 37      @ivar pushed: The I{pushed} set tracks items that have been 
 38          processed. 
 39      @type pushed: set 
 40      @ivar sorted: The sorted list of items. 
 41      @type sorted: list 
 42      """ 
 43   
 44 -    def __init__(self): 
 45          """ """ 
 46          self.unsorted = [] 
 47          self.index = {} 
 48          self.stack = [] 
 49          self.pushed = set() 
 50          self.sorted = None 
 51           
 52 -    def add(self, *items): 
 53          """ 
 54          Add items to be sorted. 
 55          @param items: One or more items to be added. 
 56          @type items: I{item} 
 57          @return: self 
 58          @rtype: L{DepList} 
 59          """ 
 60          for item in items: 
 61              self.unsorted.append(item) 
 62              key = item[0] 
 63              self.index[key] = item 
 64          return self 
 65           
 66 -    def sort(self): 
 67          """ 
 68          Sort the list based on dependancies. 
 69          @return: The sorted items. 
 70          @rtype: list 
 71          """ 
 72          self.sorted = list() 
 73          self.pushed = set() 
 74          for item in self.unsorted: 
 75              popped = [] 
 76              self.push(item)             
 77              while len(self.stack): 
 78                  try: 
 79                      top = self.top() 
 80                      ref = top[1].next() 
 81                      refd = self.index.get(ref) 
 82                      if refd is None: 
 83                          log.debug('"%s" not found, skipped', Repr(ref)) 
 84                          continue 
 85                      self.push(refd) 
 86                  except StopIteration: 
 87                      popped.append(self.pop()) 
 88                      continue 
 89              for p in popped: 
 90                  self.sorted.append(p) 
 91          self.unsorted = self.sorted 
 92          return self.sorted 
 93       
 94 -    def top(self): 
 95          """ 
 96          Get the item at the top of the stack. 
 97          @return: The top item. 
 98          @rtype: (item, iter) 
 99          """ 
100          return self.stack[-1] 
101       
102 -    def push(self, item): 
103          """ 
104          Push and item onto the sorting stack. 
105          @param item: An item to push. 
106          @type item: I{item} 
107          @return: The number of items pushed. 
108          @rtype: int 
109          """ 
110          if item in self.pushed: 
111              return 
112          frame = (item, iter(item[1])) 
113          self.stack.append(frame) 
114          self.pushed.add(item) 
115       
116 -    def pop(self): 
117          """ 
118          Pop the top item off the stack and append 
119          it to the sorted list. 
120          @return: The popped item. 
121          @rtype: I{item} 
122          """ 
123          try: 
124              frame = self.stack.pop() 
125              return frame[0] 
126          except: 
127              pass 
128   
129   
130  if __name__ == '__main__': 
131      a = ('a', ('x',)) 
132      b = ('b', ('a',)) 
133      c = ('c', ('a','b')) 
134      d = ('d', ('c',)) 
135      e = ('e', ('d','a')) 
136      f = ('f', ('e','c','d','a')) 
137      x = ('x', ()) 
138      L = DepList() 
139      L.add(c, e, d, b, f, a, x) 
140      print [x[0] for x in L.sort()] 
141