Source Code for Module gofer.agent.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   
 22 -class DepList: 
 23      """ 
 24      Dependency solving list. 
 25      Items are tuples: (object, (deps,)) 
 26      @ivar unsorted: The raw (unsorted) items. 
 27      @type unsorted: list 
 28      @ivar index: The index of (unsorted) items. 
 29      @type index: list 
 30      @ivar stack: The sorting stack. 
 31      @type stack: list 
 32      @ivar pushed: The I{pushed} set tracks items that have been 
 33          processed. 
 34      @type pushed: set 
 35      @ivar sorted: The sorted list of items. 
 36      @type sorted: list 
 37      """ 
 38   
 39 -    def __init__(self): 
 40          """ """ 
 41          self.unsorted = [] 
 42          self.index = {} 
 43          self.stack = [] 
 44          self.pushed = set() 
 45          self.sorted = None 
 46           
 47 -    def add(self, *items): 
 48          """ 
 49          Add items to be sorted. 
 50          @param items: One or more items to be added. 
 51          @type items: I{item} 
 52          @return: self 
 53          @rtype: L{DepList} 
 54          """ 
 55          for item in items: 
 56              self.unsorted.append(item) 
 57              key = item[0] 
 58              self.index[key] = item 
 59          return self 
 60           
 61 -    def sort(self): 
 62          """ 
 63          Sort the list based on dependencies. 
 64          @return: The sorted items. 
 65          @rtype: list 
 66          """ 
 67          self.sorted = list() 
 68          self.pushed = set() 
 69          for item in self.unsorted: 
 70              popped = [] 
 71              self.push(item)             
 72              while len(self.stack): 
 73                  try: 
 74                      top = self.top() 
 75                      ref = top[1].next() 
 76                      refd = self.index.get(ref) 
 77                      if refd is None: 
 78                          continue 
 79                      self.push(refd) 
 80                  except StopIteration: 
 81                      popped.append(self.pop()) 
 82                      continue 
 83              for p in popped: 
 84                  self.sorted.append(p) 
 85          self.unsorted = self.sorted 
 86          return self.sorted 
 87       
 88 -    def top(self): 
 89          """ 
 90          Get the item at the top of the stack. 
 91          @return: The top item. 
 92          @rtype: (item, iter) 
 93          """ 
 94          return self.stack[-1] 
 95       
 96 -    def push(self, item): 
 97          """ 
 98          Push and item onto the sorting stack. 
 99          @param item: An item to push. 
100          @type item: I{item} 
101          @return: The number of items pushed. 
102          @rtype: int 
103          """ 
104          if item in self.pushed: 
105              return 
106          frame = (item, iter(item[1])) 
107          self.stack.append(frame) 
108          self.pushed.add(item) 
109       
110 -    def pop(self): 
111          """ 
112          Pop the top item off the stack and append 
113          it to the sorted list. 
114          @return: The popped item. 
115          @rtype: I{item} 
116          """ 
117          try: 
118              frame = self.stack.pop() 
119              return frame[0] 
120          except Exception: 
121              pass 
122   
123   
124  if __name__ == '__main__': 
125      a = ('a', ('x',)) 
126      b = ('b', ('a',)) 
127      c = ('c', ('a','b')) 
128      d = ('d', ('c',)) 
129      e = ('e', ('d','a')) 
130      f = ('f', ('e','c','d','a')) 
131      x = ('x', ()) 
132      L = DepList() 
133      L.add(c, e, d, b, f, a, x) 
134      print [x[0] for x in L.sort()] 
135