1 files changed, 46 insertions, 37 deletions

diff --git a/csgterm.cc b/csgterm.cc
index 58c5177..359d3b5 100644
--- a/csgterm.cc
+++ b/csgterm.cc
@@ -22,10 +22,11 @@
 
 #include "openscad.h"
 
-CSGTerm::CSGTerm(PolySet *polyset, double m[16])
+CSGTerm::CSGTerm(PolySet *polyset, QString label, double m[16])
 {
 	this->type = PRIMITIVE;
 	this->polyset = polyset;
+	this->label = label;
 	this->left = NULL;
 	this->right = NULL;
 	for (int i=0; i<16; i++)
@@ -44,7 +45,7 @@ CSGTerm::CSGTerm(type_e type, CSGTerm *left, CSGTerm *right)
 	refcounter = 1;
 }
 
-CSGTerm *CSGTerm::normalize(bool &changed)
+CSGTerm *CSGTerm::normalize()
 {
 	// This function implements the CSG normalization
 	// Reference: Florian Kirsch, Juergen Doeller,
@@ -55,15 +56,31 @@ CSGTerm *CSGTerm::normalize(bool &changed)
 	if (type == PRIMITIVE)
 		return link();
 
-	CSGTerm *x, *y, *z;
+	CSGTerm *t1, *t2, *x, *y;
+
+	x = left->normalize();
+	y = right->normalize();
+
+	if (x != left || y != right) {
+		t1 = new CSGTerm(type, x, y);
+	} else {
+		t1 = link();
+		x->unlink();
+		y->unlink();
+	}
+
+	do {
+		t2 = t1->normalize_tail();
+		t1->unlink();
+		t1 = t2;
+	} while (t1 != t2);
 
-	x = left->normalize(changed);
-	left->unlink();
-	left = x;
+	return t1;
+}
 
-	x = right->normalize(changed);
-	right->unlink();
-	right = x;
+CSGTerm *CSGTerm::normalize_tail()
+{
+	CSGTerm *x, *y, *z;
 
 	// Part A: The 'x . (y . z)' expressions
 
@@ -72,40 +89,28 @@ CSGTerm *CSGTerm::normalize(bool &changed)
 	z = right->right;
 
 	// 1.  x - (y + z) -> (x - y) - z
-	if (type == DIFFERENCE && right->type == UNION) {
-		changed = true;
+	if (type == DIFFERENCE && right->type == UNION)
 		return new CSGTerm(DIFFERENCE, new CSGTerm(DIFFERENCE, x->link(), y->link()), z->link());
-	}
 
 	// 2.  x * (y + z) -> (x * y) + (x * z)
-	if (type == INTERSECTION && right->type == UNION) {
-		changed = true;
+	if (type == INTERSECTION && right->type == UNION)
 		return new CSGTerm(UNION, new CSGTerm(INTERSECTION, x->link(), y->link()), new CSGTerm(INTERSECTION, x->link(), z->link()));
-	}
 
 	// 3.  x - (y * z) -> (x - y) + (x - z)
-	if (type == DIFFERENCE && right->type == INTERSECTION) {
-		changed = true;
+	if (type == DIFFERENCE && right->type == INTERSECTION)
 		return new CSGTerm(UNION, new CSGTerm(DIFFERENCE, x->link(), y->link()), new CSGTerm(DIFFERENCE, x->link(), z->link()));
-	}
 
 	// 4.  x * (y * z) -> (x * y) * z
-	if (type == INTERSECTION && right->type == INTERSECTION) {
-		changed = true;
+	if (type == INTERSECTION && right->type == INTERSECTION)
 		return new CSGTerm(INTERSECTION, new CSGTerm(INTERSECTION, x->link(), y->link()), z->link());
-	}
 
 	// 5.  x - (y - z) -> (x - y) + (x * z)
-	if (type == DIFFERENCE && right->type == DIFFERENCE) {
-		changed = true;
+	if (type == DIFFERENCE && right->type == DIFFERENCE)
 		return new CSGTerm(UNION, new CSGTerm(DIFFERENCE, x->link(), y->link()), new CSGTerm(INTERSECTION, x->link(), z->link()));
-	}
 
 	// 6.  x * (y - z) -> (x * y) - z
-	if (type == INTERSECTION && right->type == DIFFERENCE) {
-		changed = true;
+	if (type == INTERSECTION && right->type == DIFFERENCE)
 		return new CSGTerm(DIFFERENCE, new CSGTerm(INTERSECTION, x->link(), y->link()), z->link());
-	}
 
 	// Part B: The '(x . y) . z' expressions
 
@@ -114,24 +119,18 @@ CSGTerm *CSGTerm::normalize(bool &changed)
 	z = right;
 
 	// 7. (x - y) * z  -> (x * z) - y
-	if (left->type == DIFFERENCE && type == INTERSECTION) {
-		changed = true;
+	if (left->type == DIFFERENCE && type == INTERSECTION)
 		return new CSGTerm(DIFFERENCE, new CSGTerm(INTERSECTION, x->link(), z->link()), y->link());
-	}
 
 	// 8. (x + y) - z  -> (x - z) + (y - z)
-	if (left->type == UNION && type == DIFFERENCE) {
-		changed = true;
+	if (left->type == UNION && type == DIFFERENCE)
 		return new CSGTerm(UNION, new CSGTerm(DIFFERENCE, x->link(), z->link()), new CSGTerm(DIFFERENCE, y->link(), z->link()));
-	}
 
 	// 9. (x + y) * z  -> (x * z) + (y * z)
-	if (left->type == UNION && type == INTERSECTION) {
-		changed = true;
+	if (left->type == UNION && type == INTERSECTION)
 		return new CSGTerm(UNION, new CSGTerm(INTERSECTION, x->link(), z->link()), new CSGTerm(INTERSECTION, y->link(), z->link()));
-	}
 
-	return this;
+	return link();
 }
 
 CSGTerm *CSGTerm::link()
@@ -153,3 +152,13 @@ void CSGTerm::unlink()
 	}
 }
 
+QString CSGTerm::dump()
+{
+	if (type == UNION)
+		return QString("(%1 + %2)").arg(left->dump(), right->dump());
+	if (type == INTERSECTION)
+		return QString("(%1 * %2)").arg(left->dump(), right->dump());
+	if (type == DIFFERENCE)
+		return QString("(%1 - %2)").arg(left->dump(), right->dump());
+	return label;
+}