git.gag.com Git - debian/gnuradio/blob - grc/python/expr_utils.py

   1 """
   2 Copyright 2008, 2009 Free Software Foundation, Inc.
   3 This file is part of GNU Radio
   4
   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.
   9
  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.
  14
  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
  18 """
  19
  20 import string
  21 VAR_CHARS = string.letters + string.digits + '_'
  22
  23 class graph(object):
  24         """
  25         Simple graph structure held in a dictionary.
  26         """
  27
  28         def __init__(self): self._graph = dict()
  29
  30         def __str__(self): return str(self._graph)
  31
  32         def add_node(self, node_key):
  33                 if self._graph.has_key(node_key): return
  34                 self._graph[node_key] = set()
  35
  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)
  41
  42         def add_edge(self, src_node_key, dest_node_key):
  43                 self._graph[src_node_key].add(dest_node_key)
  44
  45         def remove_edge(self, src_node_key, dest_node_key):
  46                 self._graph[src_node_key].remove(dest_node_key)
  47
  48         def get_nodes(self): return self._graph.keys()
  49
  50         def get_edges(self, node_key): return self._graph[node_key]
  51
  52 def expr_split(expr):
  53         """
  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
  59         """
  60         toks = list()
  61         tok = ''
  62         quote = ''
  63         for char in expr:
  64                 if quote or char in VAR_CHARS:
  65                         if char == quote: quote = ''
  66                         tok += char
  67                 elif char in ("'", '"'):
  68                         toks.append(tok)
  69                         tok = char
  70                         quote = char
  71                 else:
  72                         toks.append(tok)
  73                         toks.append(char)
  74                         tok = ''
  75         toks.append(tok)
  76         return filter(lambda t: t, toks)
  77
  78 def expr_replace(expr, replace_dict):
  79         """
  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
  84         """
  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)
  90
  91 def get_variable_dependencies(expr, vars):
  92         """
  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
  97         """
  98         expr_toks = expr_split(expr)
  99         return set(filter(lambda v: v in expr_toks, vars))
 100
 101 def get_graph(exprs):
 102         """
 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
 106         """
 107         vars = exprs.keys()
 108         #get dependencies for each expression, load into graph
 109         var_graph = 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)
 114         return var_graph
 115
 116 def sort_variables(exprs):
 117         """
 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
 122         """
 123         var_graph = get_graph(exprs)
 124         sorted_vars = list()
 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())
 129                 assert indep_vars
 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)
 135
 136 def sort_objects(objects, get_id, get_expr):
 137         """
 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
 143         """
 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]
 151
 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