--- /dev/null
+/**
+ * @file colorize.cpp
+ * Uses colors to analyze dependencies among sub expressions
+ */
+
+
+#include "colorize.h"
+#include "signals.hh"
+
+using namespace std;
+
+// static funvtions needed to implement splitDependance
+
+static int allocateColor(Tree exp); ///< allocate a new unique color for exp
+static void colorize(Tree exp, int color); ///< add color information to exp and all its subtrees
+static void uncolorize(Tree exp); ///< remove color information
+static void listMultiColoredExp(Tree exp, set<Tree>& lst); ///< list multicolored subexpressions of exp
+
+
+
+/**
+ * Analyze a set of expressions to discover its dependencies that is subexpressions
+ * common to at least two of these expressions
+ * @param exps set of expressions to analyze
+ * @param post resulting set of post expressions
+ * @param pre resulting set of pre expressions
+ */
+void splitDependance(const set<Tree>& exps, set<Tree>& post, set<Tree>& pre)
+{
+ set<Tree>::const_iterator e;
+ for (e= exps.begin(); e != exps.end(); e++) {
+ colorize(*e, allocateColor(*e));
+ }
+
+ pre.clear();
+ for (e = exps.begin(); e != exps.end(); e++) {
+ listMultiColoredExp(*e, pre);
+ }
+
+ post.clear();
+ set_difference(exps.begin(), exps.end(), pre.begin(), pre.end(), inserter(post, post.begin()));
+
+ for (e = exps.begin(); e != exps.end(); e++) {
+ uncolorize(*e);
+ }
+}
+
+//------------------------------------------- IMPLEMENTATION (level 1)-----------------------------------------------------
+
+static void addColor(Tree exp, int color); ///< a color to the colors of exp
+static bool hasColor(Tree exp, int color); ///< true if exp is already colored with color
+static int colorsCount(Tree exp); ///< returns the number of colors of exp
+static void clearColors(Tree exp); ///< remove the color property of exp
+
+/**
+ * Allocate a unique color (an integer) for an expression.
+ * by converting its address into an integer
+ */
+int allocateColor(Tree exp)
+{
+// return int(exp);
+ static map<Tree,int> colorMap;
+ static int nextFreeColor = 1;
+ int& color = colorMap[exp];
+ if (!color)
+ color = nextFreeColor++;
+ return color;
+}
+
+/**
+ * Add a color to all the expression tree
+ */
+void colorize(Tree exp, int color)
+{
+ if (! hasColor(exp, color)) {
+ addColor(exp, color);
+ vector<Tree> v;
+ int n = getSubSignals(exp, v, false);
+ for (int i=0; i<n; i++) colorize(v[i], color);
+ }
+}
+
+/**
+ * Remove the colors of an expression tree
+ */
+void uncolorize(Tree exp)
+{
+ if (colorsCount(exp) > 0) {
+ clearColors(exp);
+ vector<Tree> v;
+ int n = getSubSignals(exp, v, false);
+ for (int i=0; i<n; i++) uncolorize(v[i]);
+ }
+}
+
+/**
+ * Make a set of the multicolored sub-expressions
+ */
+void listMultiColoredExp(Tree exp, set<Tree>& lst)
+{
+ assert(colorsCount(exp) > 0);
+ if (colorsCount(exp) > 1) {
+ // we have found a multicolored expression
+ lst.insert(exp);
+ } else {
+ // it is a monocolored expression
+ // we search its subexpressions
+ vector<Tree> v;
+ int n = getSubSignals(exp, v, false);
+ for (int i=0; i<n; i++) {
+ listMultiColoredExp(v[i], lst);
+ }
+ }
+}
+
+//------------------------------------------- IMPLEMENTATION (level 2)-----------------------------------------------------
+
+Tree COLORPROPERTY = tree(symbol("ColorProperty"));
+
+/**
+ * set the color-set property of sig
+ * @param sig the signal we want to type
+ * @param t the type of the signal
+ */
+void setColorProperty(Tree sig, set<int>* colorset)
+{
+ setProperty(sig, COLORPROPERTY, tree((void*)colorset));
+}
+
+
+/**
+ * retrieve the color-set property of sig
+ * @param sig the signal we want to know the color-set property
+ */
+set<int>* getColorProperty(Tree sig)
+{
+ Tree tt;
+ if (!getProperty(sig, COLORPROPERTY, tt)) {
+ return 0;
+ } else {
+ return (set<int>*)tree2ptr(tt);
+ }
+}
+
+
+
+
+/**
+ * Add a color to the colorset of exp. Create an empty
+ * coloset if needed.
+ * @param sig the signal we want to color
+ * @param color the color used
+ */
+void addColor(Tree exp, int color)
+{
+ set<int>* cset = getColorProperty(exp);
+ if (cset == 0) {
+ cset = new set<int>();
+ setColorProperty(exp, cset);
+ }
+ cset->insert(color);
+}
+
+
+/**
+ * Test if exp as color in its colorset
+ * @param sig the signal we want to test
+ * @param color the color to test
+ * @return true if color is member of the colorset of sig
+ */
+bool hasColor(Tree exp, int color)
+{
+ set<int>* cset = getColorProperty(exp);
+ if (cset==0) {
+ return false;
+ } else {
+ return cset->find(color) != cset->end();
+ }
+}
+
+
+/**
+ * Count the number of colors of exp
+ * @param exp the expression we want to count the colors
+ * @return the number of elements in the color set or 0
+ */
+static int colorsCount(Tree exp)
+{
+ set<int>* cset = getColorProperty(exp);
+ if (cset==0) {
+ return 0;
+ } else {
+ return cset->size();
+ }
+}
+
+
+/**
+ * Count the number of colors of exp
+ * @param exp the expression we want to count the colors
+ * @return the number of elements in the color set or 0
+ */
+static void clearColors(Tree exp)
+{
+ set<int>* cset = getColorProperty(exp);
+ if (cset != 0) {
+ cset->clear();
+ }
+}
+
+