Merged changeset r9285:9377 from jblum/grc into trunk, with distcheck fixes

and local modifications.

Integrates previously separate GNU Radio Companion into top-level component
'grc'.  (Josh Blum)


git-svn-id: http://gnuradio.org/svn/gnuradio/trunk@9378 221aa14e-8319-0410-a670-987f0aec2ac5

1 files changed, 140 insertions, 0 deletions

diff --git a/grc/src/grc_gnuradio/utils/expr_utils.py b/grc/src/grc_gnuradio/utils/expr_utils.py
new file mode 100644
index 000000000..8253f018a
--- /dev/null
+++ b/grc/src/grc_gnuradio/utils/expr_utils.py
@@ -0,0 +1,140 @@
+"""
+Copyright 2008 Free Software Foundation, Inc.
+This file is part of GNU Radio
+
+GNU Radio Companion is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License
+as published by the Free Software Foundation; either version 2
+of the License, or (at your option) any later version.
+
+GNU Radio Companion is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+"""
+##@package grc_gnuradio.utils.expr_utils
+#Utility functions to comprehend variable expressions.
+#@author Josh Blum
+
+import string
+VAR_CHARS = string.letters + string.digits + '_'
+
+class graph(object):
+	"""!
+	Simple graph structure held in a dictionary.
+	"""
+
+	def __init__(self): self._graph = dict()
+
+	def __str__(self): return str(self._graph)
+
+	def add_node(self, node_key):
+		if self._graph.has_key(node_key): return
+		self._graph[node_key] = set()
+
+	def remove_node(self, node_key):
+		if not self._graph.has_key(node_key): return
+		for edges in self._graph.values():
+			if node_key in edges: edges.remove(node_key)
+		self._graph.pop(node_key)
+
+	def add_edge(self, src_node_key, dest_node_key):
+		self._graph[src_node_key].add(dest_node_key)
+
+	def remove_edge(self, src_node_key, dest_node_key):
+		self._graph[src_node_key].remove(dest_node_key)
+
+	def get_nodes(self): return self._graph.keys()
+
+	def get_edges(self, node_key): return self._graph[node_key]
+
+def expr_split(expr):
+	"""!
+	Split up an expression by non alphanumeric characters, including underscore.
+	Leave strings in-tact.
+	#TODO ignore escaped quotes, use raw strings.
+	@param expr an expression string
+	@return a list of string tokens that form expr
+	"""
+	toks = list()
+	tok = ''
+	quote = ''
+	for char in expr:
+		if quote or char in VAR_CHARS:
+			if char == quote: quote = ''
+			tok += char
+		elif char in ("'", '"'):
+			toks.append(tok)
+			tok = char
+			quote = char
+		else:
+			toks.append(tok)
+			toks.append(char)
+			tok = ''
+	toks.append(tok)
+	return filter(lambda t: t, toks)
+
+def expr_prepend(expr, vars, prepend):
+	"""!
+	Search for vars in the expression and add the prepend.
+	@param expr an expression string
+	@param vars a list of variable names
+	@param prepend the prepend string
+	@return a new expression with the prepend
+	"""
+	expr_splits = expr_split(expr)
+	for i, es in enumerate(expr_splits):
+		if es in vars: expr_splits[i] = prepend + es
+	return ''.join(expr_splits)
+
+def get_variable_dependencies(expr, vars):
+	"""!
+	Return a set of variables used in this expression.
+	@param expr an expression string
+	@param vars a list of variable names
+	@return a subset of vars used in the expression
+	"""
+	expr_toks = expr_split(expr)
+	return set(filter(lambda v: v in expr_toks, vars))
+
+def get_graph(exprs):
+	"""!
+	Get a graph representing the variable dependencies
+	@param exprs a mapping of variable name to expression
+	@return a graph of variable deps
+	"""
+	vars = exprs.keys()
+	#get dependencies for each expression, load into graph
+	var_graph = graph()
+	for var in vars: var_graph.add_node(var)
+	for var, expr in exprs.iteritems():
+		for dep in get_variable_dependencies(expr, vars):
+			var_graph.add_edge(dep, var)
+	return var_graph
+
+def sort_variables(exprs):
+	"""!
+	Get a list of variables in order of dependencies.
+	@param exprs a mapping of variable name to expression
+	@return a list of variable names
+	@throws AssertionError circular dependencies
+	"""
+	var_graph = get_graph(exprs)
+	sorted_vars = list()
+	#determine dependency order
+	while var_graph.get_nodes():
+		#get a list of nodes with no edges
+		indep_vars = filter(lambda var: not var_graph.get_edges(var), var_graph.get_nodes())
+		assert indep_vars
+		#add the indep vars to the end of the list
+		sorted_vars.extend(sorted(indep_vars))
+		#remove each edge-less node from the graph
+		for var in indep_vars: var_graph.remove_node(var)
+	return reversed(sorted_vars)
+
+if __name__ == '__main__':
+	for i in sort_variables({'x':'1', 'y':'x+1', 'a':'x+y', 'b':'y+1', 'c':'a+b+x+y'}): print i