Package gofer :: Package agent :: Module deplist
[hide private]
[frames] | no frames]

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