2 Copyright 2008, 2009 Free Software Foundation, Inc.
3 This file is part of GNU Radio
5 GNU Radio Companion is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 as published by the Free Software Foundation; either version 2
8 of the License, or (at your option) any later version.
10 GNU Radio Companion is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
21 VAR_CHARS = string.letters + string.digits + '_'
25 Simple graph structure held in a dictionary.
28 def __init__(self): self._graph = dict()
30 def __str__(self): return str(self._graph)
32 def add_node(self, node_key):
33 if self._graph.has_key(node_key): return
34 self._graph[node_key] = set()
36 def remove_node(self, node_key):
37 if not self._graph.has_key(node_key): return
38 for edges in self._graph.values():
39 if node_key in edges: edges.remove(node_key)
40 self._graph.pop(node_key)
42 def add_edge(self, src_node_key, dest_node_key):
43 self._graph[src_node_key].add(dest_node_key)
45 def remove_edge(self, src_node_key, dest_node_key):
46 self._graph[src_node_key].remove(dest_node_key)
48 def get_nodes(self): return self._graph.keys()
50 def get_edges(self, node_key): return self._graph[node_key]
54 Split up an expression by non alphanumeric characters, including underscore.
55 Leave strings in-tact.
56 #TODO ignore escaped quotes, use raw strings.
57 @param expr an expression string
58 @return a list of string tokens that form expr
64 if quote or char in VAR_CHARS:
65 if char == quote: quote = ''
67 elif char in ("'", '"'):
76 return filter(lambda t: t, toks)
78 def expr_replace(expr, replace_dict):
80 Search for vars in the expression and add the prepend.
81 @param expr an expression string
82 @param replace_dict a dict of find:replace
83 @return a new expression with the prepend
85 expr_splits = expr_split(expr)
86 for i, es in enumerate(expr_splits):
87 if es in replace_dict.keys():
88 expr_splits[i] = replace_dict[es]
89 return ''.join(expr_splits)
91 def get_variable_dependencies(expr, vars):
93 Return a set of variables used in this expression.
94 @param expr an expression string
95 @param vars a list of variable names
96 @return a subset of vars used in the expression
98 expr_toks = expr_split(expr)
99 return set(filter(lambda v: v in expr_toks, vars))
101 def get_graph(exprs):
103 Get a graph representing the variable dependencies
104 @param exprs a mapping of variable name to expression
105 @return a graph of variable deps
108 #get dependencies for each expression, load into graph
110 for var in vars: var_graph.add_node(var)
111 for var, expr in exprs.iteritems():
112 for dep in get_variable_dependencies(expr, vars):
113 if dep != var: var_graph.add_edge(dep, var)
116 def sort_variables(exprs):
118 Get a list of variables in order of dependencies.
119 @param exprs a mapping of variable name to expression
120 @return a list of variable names
121 @throws AssertionError circular dependencies
123 var_graph = get_graph(exprs)
125 #determine dependency order
126 while var_graph.get_nodes():
127 #get a list of nodes with no edges
128 indep_vars = filter(lambda var: not var_graph.get_edges(var), var_graph.get_nodes())
130 #add the indep vars to the end of the list
131 sorted_vars.extend(sorted(indep_vars))
132 #remove each edge-less node from the graph
133 for var in indep_vars: var_graph.remove_node(var)
134 return reversed(sorted_vars)
136 def sort_objects(objects, get_id, get_expr):
138 Sort a list of objects according to their expressions.
139 @param objects the list of objects to sort
140 @param get_id the function to extract an id from the object
141 @param get_expr the function to extract an expression from the object
142 @return a list of sorted objects
144 id2obj = dict([(get_id(obj), obj) for obj in objects])
145 #map obj id to expression code
146 id2expr = dict([(get_id(obj), get_expr(obj)) for obj in objects])
147 #sort according to dependency
148 sorted_ids = sort_variables(id2expr)
149 #return list of sorted objects
150 return [id2obj[id] for id in sorted_ids]
152 if __name__ == '__main__':
153 for i in sort_variables({'x':'1', 'y':'x+1', 'a':'x+y', 'b':'y+1', 'c':'a+b+x+y'}): print i