2 Copyright 2008 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
19 ##@package grc_gnuradio.utils.expr_utils
20 #Utility functions to comprehend variable expressions.
24 VAR_CHARS = string.letters + string.digits + '_'
28 Simple graph structure held in a dictionary.
31 def __init__(self): self._graph = dict()
33 def __str__(self): return str(self._graph)
35 def add_node(self, node_key):
36 if self._graph.has_key(node_key): return
37 self._graph[node_key] = set()
39 def remove_node(self, node_key):
40 if not self._graph.has_key(node_key): return
41 for edges in self._graph.values():
42 if node_key in edges: edges.remove(node_key)
43 self._graph.pop(node_key)
45 def add_edge(self, src_node_key, dest_node_key):
46 self._graph[src_node_key].add(dest_node_key)
48 def remove_edge(self, src_node_key, dest_node_key):
49 self._graph[src_node_key].remove(dest_node_key)
51 def get_nodes(self): return self._graph.keys()
53 def get_edges(self, node_key): return self._graph[node_key]
57 Split up an expression by non alphanumeric characters, including underscore.
58 Leave strings in-tact.
59 #TODO ignore escaped quotes, use raw strings.
60 @param expr an expression string
61 @return a list of string tokens that form expr
67 if quote or char in VAR_CHARS:
68 if char == quote: quote = ''
70 elif char in ("'", '"'):
79 return filter(lambda t: t, toks)
81 def expr_prepend(expr, vars, prepend):
83 Search for vars in the expression and add the prepend.
84 @param expr an expression string
85 @param vars a list of variable names
86 @param prepend the prepend string
87 @return a new expression with the prepend
89 expr_splits = expr_split(expr)
90 for i, es in enumerate(expr_splits):
91 if es in vars: expr_splits[i] = prepend + es
92 return ''.join(expr_splits)
94 def get_variable_dependencies(expr, vars):
96 Return a set of variables used in this expression.
97 @param expr an expression string
98 @param vars a list of variable names
99 @return a subset of vars used in the expression
101 expr_toks = expr_split(expr)
102 return set(filter(lambda v: v in expr_toks, vars))
104 def get_graph(exprs):
106 Get a graph representing the variable dependencies
107 @param exprs a mapping of variable name to expression
108 @return a graph of variable deps
111 #get dependencies for each expression, load into graph
113 for var in vars: var_graph.add_node(var)
114 for var, expr in exprs.iteritems():
115 for dep in get_variable_dependencies(expr, vars):
116 var_graph.add_edge(dep, var)
119 def sort_variables(exprs):
121 Get a list of variables in order of dependencies.
122 @param exprs a mapping of variable name to expression
123 @return a list of variable names
124 @throws AssertionError circular dependencies
126 var_graph = get_graph(exprs)
128 #determine dependency order
129 while var_graph.get_nodes():
130 #get a list of nodes with no edges
131 indep_vars = filter(lambda var: not var_graph.get_edges(var), var_graph.get_nodes())
133 #add the indep vars to the end of the list
134 sorted_vars.extend(sorted(indep_vars))
135 #remove each edge-less node from the graph
136 for var in indep_vars: var_graph.remove_node(var)
137 return reversed(sorted_vars)
139 if __name__ == '__main__':
140 for i in sort_variables({'x':'1', 'y':'x+1', 'a':'x+y', 'b':'y+1', 'c':'a+b+x+y'}): print i