Initial revision
[blender.git] / intern / python / modules / mcf / utils / dsort.py
1 nullval = (1,)
2
3 class DSort:
4         '''
5         A "dependency" sorting class, used to order elements
6         according to declared "dependencies" (many-to-one relationships)
7         Is not a beautiful algo, but it works (or seems to)
8         Requires hashable values for all elements.
9         
10         This is a quick hack, use at your own risk!
11         
12         Basic usage:
13                 Create a DSort mysorter
14                 for each element q which is part of the set to sort, call:
15                         mysorter.rule( dsort.nullval, q)
16                         # this is not strictly necessary for elements which are
17                         # dependent on other objects, but it is necessary for
18                         # those which are not.  Generally it's easiest to call
19                         # the null rule for each element.
20                 for each rule x depends on y, call:
21                         mysorter.rule( x, y)
22                 when _all_ rules are entered, call
23                 try:
24                         sortedlist = mysorter.sort()
25                 except ValueError:
26                         handle recursive dependencies here...
27                 
28                 
29         For an example of real-life use, see the VRML lineariser.
30         
31         '''
32         def __init__(self, recurseError=None ):
33                 self.dependon = {nullval:[0]}
34                 self.recurseError = recurseError
35         def rule( self, depon, deps):
36                 '''
37                 Register a "rule".  Both elements must be hashable values.
38                 See the class' documentation for usage.
39                 '''
40 #               print '''registering rule:''', depon, deps
41                 if self.dependon.has_key( deps ) and depon is not nullval:
42                         self.dependon[ deps ].append( depon )
43                 elif depon is not nullval:
44                         self.dependon[ deps ] = [-1, depon]
45                 elif not self.dependon.has_key( deps ):
46                         self.dependon[ deps ] = [-1 ]
47         def sort( self ):
48                 '''
49                 Get the sorted results as a list
50                 '''
51                 for key, value in self.dependon.items():
52                         self._dsort( key, value)
53                 temp = []
54                 for key, value in self.dependon.items():
55                         temp.append( (value[0], key) )
56                 temp.sort()
57                 temp.reverse()
58                 temp2 = []
59                 for x,y in temp:
60                         temp2.append( y )
61                 # following adds the elements with no dependencies
62                 temp2[len(temp2):] = self.dependon[ nullval ][1:]
63                 return temp2
64         def _dsort( self, key, value ):
65                 if value[0] == -2:
66                         if self.recurseError:
67                                 raise ValueError, '''Dependencies were recursive!'''
68                         else:
69                                 if __debug__:
70                                         print '''Recursive dependency discovered and ignored in dsort.Dsort._dsort on %s:%s'''%(key, value)
71                                 return 1 # we know it has at least one reference...
72                 elif value[0] == -1: # haven't yet calculated this rdepth
73                         value[0] = -2
74                         tempval = [0]
75                         for x in value[1:]:
76                                 try:
77                                         tempval.append( 1 + self._dsort( x, self.dependon[x]) )
78                                 except KeyError:
79                                         self.dependon[ nullval ].append( x ) # is an unreferenced element
80                                         tempval.append( 1 )
81                         value[0] = max( tempval )
82                         return value[0]
83                 else:
84                         return value[0]
85 '''
86 from mcf.utils import dsort
87 >>> x = dsort.DSort()
88 >>> map( x.rule, [1,2,2,4,5,4], [2,3,4,5,6,3] )
89 [None, None, None, None, None, None]
90 >>> x.sort()
91 '''