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.
23 VAR_CHARS = string.letters + string.digits + '_'
27 Simple graph structure held in a dictionary.
30 def __init__(self): self._graph = dict()
32 def __str__(self): return str(self._graph)
34 def add_node(self, node_key):
35 if self._graph.has_key(node_key): return
36 self._graph[node_key] = set()
38 def remove_node(self, node_key):
39 if not self._graph.has_key(node_key): return
40 for edges in self._graph.values():
41 if node_key in edges: edges.remove(node_key)
42 self._graph.pop(node_key)
44 def add_edge(self, src_node_key, dest_node_key):
45 self._graph[src_node_key].add(dest_node_key)
47 def remove_edge(self, src_node_key, dest_node_key):
48 self._graph[src_node_key].remove(dest_node_key)
50 def get_nodes(self): return self._graph.keys()
52 def get_edges(self, node_key): return self._graph[node_key]
56 Split up an expression by non alphanumeric characters, including underscore.
57 Leave strings in-tact.
58 #TODO ignore escaped quotes, use raw strings.
59 @param expr an expression string
60 @return a list of string tokens that form expr
66 if quote or char in VAR_CHARS:
67 if char == quote: quote = ''
69 elif char in ("'", '"'):
78 return filter(lambda t: t, toks)
80 def expr_prepend(expr, vars, prepend):
82 Search for vars in the expression and add the prepend.
83 @param expr an expression string
84 @param vars a list of variable names
85 @param prepend the prepend string
86 @return a new expression with the prepend
88 expr_splits = expr_split(expr)
89 for i, es in enumerate(expr_splits):
90 if es in vars: expr_splits[i] = prepend + es
91 return ''.join(expr_splits)
93 def get_variable_dependencies(expr, vars):
95 Return a set of variables used in this expression.
96 @param expr an expression string
97 @param vars a list of variable names
98 @return a subset of vars used in the expression
100 expr_toks = expr_split(expr)
101 return set(filter(lambda v: v in expr_toks, vars))
103 def get_graph(exprs):
105 Get a graph representing the variable dependencies
106 @param exprs a mapping of variable name to expression
107 @return a graph of variable deps
110 #get dependencies for each expression, load into graph
112 for var in vars: var_graph.add_node(var)
113 for var, expr in exprs.iteritems():
114 for dep in get_variable_dependencies(expr, vars):
115 var_graph.add_edge(dep, var)
118 def sort_variables(exprs):
120 Get a list of variables in order of dependencies.
121 @param exprs a mapping of variable name to expression
122 @return a list of variable names
123 @throws AssertionError circular dependencies
125 var_graph = get_graph(exprs)
127 #determine dependency order
128 while var_graph.get_nodes():
129 #get a list of nodes with no edges
130 indep_vars = filter(lambda var: not var_graph.get_edges(var), var_graph.get_nodes())
132 #add the indep vars to the end of the list
133 sorted_vars.extend(sorted(indep_vars))
134 #remove each edge-less node from the graph
135 for var in indep_vars: var_graph.remove_node(var)
136 return reversed(sorted_vars)
138 if __name__ == '__main__':
139 for i in sort_variables({'x':'1', 'y':'x+1', 'a':'x+y', 'b':'y+1', 'c':'a+b+x+y'}): print i