X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fparanoidnumber.cpp;h=b45c71e069e7ca95b0d79d7b1c8987fc9403080f;hp=53729a324717a05ad2e9262c69f75925b6438175;hb=0f3a7a9d2c6cc19852fae8ed048dcd1089d33250;hpb=0fe42dc1237a03b6368e6fa430c1503ed669bee2

diff --git a/src/paranoidnumber.cpp b/src/paranoidnumber.cpp
index 53729a3..b45c71e 100644
--- a/src/paranoidnumber.cpp
+++ b/src/paranoidnumber.cpp
@@ -3,6 +3,7 @@
 #include <sstream>
 #include <fenv.h>
 #include "log.h"
+#include <cassert>
 #include <iostream>
 
 using namespace std;
@@ -10,8 +11,20 @@ namespace IPDF
 {
 int64_t ParanoidNumber::g_count = 0;
 
-ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next_term(NULL), m_next_factor(NULL)
+
+ParanoidNumber::~ParanoidNumber()
+{
+	g_count--;
+	for (int i = 0; i < NOP; ++i)
+	{
+		for (auto n : m_next[i])
+			delete n;
+	}
+}
+
+ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_cached_result(0)
 {
+	Construct();
 	int dp = 0;
 	int end = 0;
 	while (str[dp] != '\0' && str[dp] != '.')
@@ -21,16 +34,12 @@ ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next
 	}
 	while (str[end] != '\0')
 		++end;
-		
 	ParanoidNumber m(1);
 	for (int i = dp-1; i >= 0; --i)
 	{
 		ParanoidNumber b(str[i]-'0');
 		b*=m;
-		//Debug("m is %s", m.Str().c_str());
-		//Debug("Add %s", b.Str().c_str());
 		this->operator+=(b);
-		//Debug("Now at %s", Str().c_str());
 		m*=10;
 	}
 	ParanoidNumber n(1);
@@ -38,341 +47,73 @@ ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next
 	{
 		n/=10;
 		ParanoidNumber b(str[i]-'0');
-		//Debug("%s * %s", b.Str().c_str(), n.Str().c_str());
 		b*=n;
-		//Debug("b -> %s", b.Str().c_str());
-		//Debug("Add %s", b.Str().c_str());
 		this->operator+=(b);
-		//Debug("Now at %s", Str().c_str());
-
 	}
-	//Debug("Constructed {%s} from %s (%f)", Str().c_str(), str, ToDouble());	
 }
 
 ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
 {
-	//TODO: Optimise
-	delete m_next_term;
-	delete m_next_factor;
-	m_op = a.m_op;
-	if (a.m_next_term != NULL)
-	{
-		m_next_term = new ParanoidNumber(*(a.m_next_term));
-	}
-	if (a.m_next_factor != NULL)
+	m_value = a.m_value;
+	m_cached_result = a.m_cached_result;
+	for (int i = 0; i < NOP; ++i)
 	{
-		m_next_factor = new ParanoidNumber(*(a.m_next_factor));
-	}
-	return *this;
-}
-
-ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
-{
-	if (m_next_factor == NULL && a.Floating())
-	{
-		if (ParanoidOp<digit_t>(m_value, a.m_value, ADD))
+		for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j)
 		{
-			Simplify();
-			return *this;
-		}
-	}
-	ParanoidNumber * nt = m_next_term;
-	ParanoidNumber * nf = m_next_factor;
-	
-	ParanoidNumber ca(a);
-	if (m_next_factor != NULL)
-	{
-		if (m_next_factor->m_op == MULTIPLY)
-			ca /= (*m_next_factor);
-		else
-			ca *= (*m_next_factor);
-			
-		if (ca.Floating())
-		{
-			m_next_factor = NULL;
-			m_next_term = NULL;
-			operator+=(ca);
-			m_next_factor = nf;
-			m_next_term = nt;
-			Simplify();
-			return *this;
+			m_next[i][j]->operator=(*(a.m_next[i][j]));
 		}
 		
-	}
-	
-	m_next_term = new ParanoidNumber(a, ADD);
-	ParanoidNumber * t = m_next_term;
-	while (t->m_next_term != NULL)
-		t = t->m_next_term;
-	t->m_next_term = nt;
-	//Debug("Simplify {%s} after add", Str().c_str());
-	Simplify();
-	return *this;
-}
-
-ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
-{
-	// this = v + t + (a)
-	// -> v + (a) + t
-	if (m_next_factor == NULL && a.Floating())
-	{
-		if (ParanoidOp<digit_t>(m_value, a.m_value, ADD))
+		for (unsigned j = a.m_next[i].size(); j < m_next[i].size(); ++j)
 		{
-			Simplify();
-			return *this;
+			delete m_next[i][j];
 		}
-	}
-
-	ParanoidNumber * nt = m_next_term;
-	ParanoidNumber * nf = m_next_factor;
-	
-	ParanoidNumber ca(a, SUBTRACT);
-	if (m_next_factor != NULL)
-	{
-		if (m_next_factor->m_op == MULTIPLY)
-			ca /= (*m_next_factor);
-		else
-			ca *= (*m_next_factor);
-			
-		if (ca.Floating())
-		{
-			m_next_factor = NULL;
-			m_next_term = NULL;
-			operator-=(ca);
-			m_next_factor = nf;
-			m_next_term = nt;
-			Simplify();
-			return *this;
-		}
-		
-	}
-	
-	m_next_term = new ParanoidNumber(a,SUBTRACT);
-	ParanoidNumber * t = m_next_term;
-	while (t->m_next_term != NULL)
-	{
-		t->m_op = SUBTRACT;
-		t = t->m_next_term;
-	}
-	t->m_op = SUBTRACT;
-	//Debug("next term {%s}", m_next_term->Str().c_str());
-	t->m_next_term = nt;
-	//Debug("Simplify {%s} after sub", Str().c_str());
-	Simplify();
-	return *this;
-}
-
-ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
-{
-
-	//if (m_value == 0)
-	//		return *this;
-	//Debug("{%s} *= {%s}", Str().c_str(), a.Str().c_str());
-	// this = (vf + t) * (a)
-	if (a.Floating() && ParanoidOp<digit_t>(m_value, a.m_value, MULTIPLY))
-	{
-		if (m_next_term != NULL)
-			m_next_term->operator*=(a);
-		Simplify();
-		return *this;
-	}
-	
-	ParanoidNumber * t = this;
-	while (t->m_next_factor != NULL)
-		t = t->m_next_factor;
-	t->m_next_factor = new ParanoidNumber(a, MULTIPLY);
-
-	if (m_next_term != NULL)
-		m_next_term->operator*=(a);
-
-	//Debug("Simplify {%s}", Str().c_str());
-	Simplify();
-	//Debug("Simplified to {%s}", Str().c_str());
-	return *this;
-}
-
-
-ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
-{
-		
-
-		
-	if (a.Floating() && ParanoidOp<digit_t>(m_value, a.m_value, DIVIDE))
-	{
-		if (m_next_term != NULL)
-			m_next_term->operator/=(a);
-		Simplify();
-		return *this;
-	}
-	
-	//Debug("Called %s /= %s", Str().c_str(), a.Str().c_str());
-	// this = (vf + t) * (a)
-	ParanoidNumber * t = this;
-	while (t->m_next_factor != NULL)
-	{
-		t = t->m_next_factor;
-	}
-	t->m_next_factor = new ParanoidNumber(a, DIVIDE);
-
-	if (m_next_term != NULL)
-		m_next_term->operator/=(a);
-
-	Simplify();
+		m_next[i].resize(a.m_next[i].size());
+	}	
 	return *this;
 }
 
 
-
-void ParanoidNumber::SimplifyTerms()
-{ 
-
-	//Debug("Simplify {%s}", Str().c_str()); 
-	if (m_next_term == NULL)
-	{
-		//Debug("No terms!");
-		return;
-	}
-
-	for (ParanoidNumber * a = this; a != NULL; a = a->m_next_term)
-	{
-		ParanoidNumber * b = a->m_next_term;
-		if (a->m_next_factor != NULL && !a->m_next_factor->Floating())
-		{
-			continue;
-		}
-		
-		ParanoidNumber * bprev = a;
-		while (b != NULL)
-		{
-			//Debug("Simplify factors of %s", b->Str().c_str());
-			b->SimplifyFactors();
-			if (b->m_next_factor != NULL && !b->m_next_factor->Floating())
-			{
-				bprev = b;
-				b = b->m_next_term;
-				continue;
-			}
-			
-			bool simplify = false;
-			if (a->m_next_factor != NULL || b->m_next_factor != NULL)
-			{
-				digit_t aa(a->Head<digit_t>());
-				digit_t ab = (a->m_next_factor != NULL) ? a->m_next_factor->Head<digit_t>() : 1;
-				digit_t bc(b->Head<digit_t>());
-				digit_t bd = (b->m_next_factor != NULL) ? b->m_next_factor->Head<digit_t>() : 1;
-				Optype aop = (a->m_next_factor != NULL) ? a->m_next_factor->m_op : DIVIDE;
-				Optype cop = (b->m_next_factor != NULL) ? b->m_next_factor->m_op : DIVIDE;
-				simplify = CombineTerms<digit_t>(aa, aop, ab, bc, cop, bd);
-				if (simplify)
-				{
-					a->m_value = aa;
-					if (a->m_next_factor != NULL)
-						a->m_next_factor->m_value = ab;
-					else if (ab != 1)
-					{
-						a->m_next_factor = b->m_next_factor;
-						b->m_next_factor = NULL;
-						a->m_next_factor->m_value = ab;
-					}
-				}
-			}
-			else
-			{
-				simplify = ParanoidOp<digit_t>(a->m_value, b->Head<digit_t>(), ADD);
-			}
-			if (simplify)
-			{
-				bprev->m_next_term = b->m_next_term;
-				b->m_next_term = NULL;
-				delete b;
-				b = bprev;
-			}
-			
-			bprev = b;
-			b = b->m_next_term;
-		}
-	}
-}
-
-void ParanoidNumber::SimplifyFactors()
-{ 
-
-	//Debug("Simplify {%s}", Str().c_str()); 
-	if (m_next_factor == NULL)
-	{
-		//Debug("No factors!");
-		return;
-	}
-
-	for (ParanoidNumber * a = this; a != NULL; a = a->m_next_factor)
-	{
-		if ((a->m_op != ADD || a->m_op != SUBTRACT) && a->m_next_term != NULL)
-			continue;
-			
-		ParanoidNumber * bprev = a;
-		ParanoidNumber * b = a->m_next_factor;
-		while (b != NULL)
-		{
-			b->SimplifyTerms();
-			if (b->m_next_term != NULL)
-			{
-				bprev = b;
-				b = b->m_next_factor;
-				continue;
-			}
-		
-			Optype op = b->m_op;
-			if (a->m_op == DIVIDE)
-			{
-				op = (b->m_op == DIVIDE) ? MULTIPLY : DIVIDE;
-			}
-			
-			if (ParanoidOp<digit_t>(a->m_value, b->m_value, op))
-			{	
-
-				bprev->m_next_factor = b->m_next_factor;
-				b->m_next_factor = NULL;
-				delete b;
-				b = bprev;
-			}
-			bprev = b;
-			b = b->m_next_factor;
-		}
-	}
-}
-
-void ParanoidNumber::Simplify()
-{
-	SimplifyFactors();
-	SimplifyTerms();
-}
-
 string ParanoidNumber::Str() const
 {
 	string result("");
 	stringstream s;
 	s << (double)m_value;
-	
-	if (m_next_factor != NULL)
+	result += s.str();
+	for (auto mul : m_next[MULTIPLY])
 	{
-		result += s.str();
-		result += OpChar(m_next_factor->m_op);
-		if (m_next_factor->m_next_term != NULL)
-			result += "(" + m_next_factor->Str() + ")";
+		result += "*";
+		if (!mul->Floating())
+			result += "(" + mul->Str() + ")";
 		else
-			result += m_next_factor->Str();
+			result += mul->Str();
 	}
-	else
+	for (auto div : m_next[DIVIDE])
+	{
+		result += "/";
+		if (!div->Floating())
+			result += "(" + div->Str() + ")";
+		else
+			result += div->Str();
+	}	
+	
+	for (auto add : m_next[ADD])
 	{
-		result += s.str();
+		result += "+";
+		if (!add->Floating())
+			result += "(" + add->Str() + ")";
+		else
+			result += add->Str();
 	}
-		
-	if (m_next_term != NULL)
+	for (auto sub : m_next[SUBTRACT])
 	{
-		result += " ";
-		result += OpChar(m_next_term->m_op);
-		result += m_next_term->Str();
+		result += "-";
+		if (!sub->Floating())
+			result += "(" + sub->Str() + ")";
+		else
+			result += sub->Str();
 	}
+	
+
 	return result;
 }
 
@@ -394,6 +135,8 @@ bool TrustingOp<float>(float & a, const float & b, Optype op)
 		case DIVIDE:
 			a /= b;
 			break;
+		case NOP:
+			break;
 	}
 	return !fetestexcept(FE_ALL_EXCEPT);
 }
@@ -416,6 +159,8 @@ bool TrustingOp<double>(double & a, const double & b, Optype op)
 		case DIVIDE:
 			a /= b;
 			break;
+		case NOP:
+			break;
 	}
 	return !fetestexcept(FE_ALL_EXCEPT);
 }
@@ -443,9 +188,363 @@ bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
 			exact = (b != 0 && sa > b && sa % b == 0);
 			sa /= b;
 			break;
+		case NOP:
+			break;
 	}
 	a = (int8_t)(sa);
 	return exact;
 }
 
+
+ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
+{
+	delete Operation(new ParanoidNumber(a), ADD);
+	Simplify(ADD);
+	Simplify(SUBTRACT);
+	return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
+{
+	delete Operation(new ParanoidNumber(a), SUBTRACT);
+	//Simplify(SUBTRACT);
+	//Simplify(ADD);
+	return *this;
+}
+
+ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
+{
+	delete Operation(new ParanoidNumber(a), MULTIPLY);
+	return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
+{
+	delete Operation(new ParanoidNumber(a), DIVIDE);
+	return *this;
+}
+
+// a + b
+ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
+{
+	m_cached_result = nan("");
+	if (Floating() && m_value == 0) // 0 + b = b
+	{
+		m_value = b->m_value;
+		if (op == SUBTRACT)
+		{
+			m_value = -m_value;
+			swap(b->m_next[ADD], b->m_next[SUBTRACT]);
+		}
+		
+		for (int i = 0; i < NOP; ++i)
+		{
+			m_next[i] = b->m_next[i];
+			b->m_next[i].clear();
+		}
+		return b;
+	}
+	if (b->Floating() && b->m_value == 0) // a + 0 = a
+		return b;
+		
+
+	
+	if ((NoFactors() && b->NoFactors())
+		|| (GetFactors() == b->GetFactors()))
+	{
+		if (ParanoidOp<digit_t>(m_value, b->m_value, op))
+		{
+			Optype addop = (op == ADD) ? ADD : SUBTRACT;
+			for (auto add : b->m_next[ADD])
+			{
+				delete OperationTerm(add, addop);
+			}
+			Optype subop = (op == ADD) ? SUBTRACT : ADD;
+			for (auto sub : b->m_next[SUBTRACT])
+				delete OperationTerm(sub, subop);
+				
+			b->m_next[ADD].clear();
+			b->m_next[SUBTRACT].clear();
+			return b;
+		}
+	}
+
+	
+	
+	bool parent = (merge_point == NULL);
+	ParanoidNumber * merge = this;
+	Optype mop = op;
+	assert(mop != NOP); // silence compiler warning
+	if (parent)
+	{
+		merge_point = &merge;
+		merge_op = &mop;
+	}
+	else
+	{
+		merge = *merge_point;
+		mop = *merge_op;
+	}
+		
+	Optype invop = InverseOp(op); // inverse of p
+	Optype fwd = op;
+	Optype rev = invop;
+	if (op == SUBTRACT)
+	{
+		fwd = ADD;
+		rev = SUBTRACT;
+	}
+	
+	for (auto prev : m_next[invop])
+	{
+		if (prev->OperationTerm(b, rev, merge_point, merge_op) == b)
+			return b;
+		
+	}
+	for (auto next : m_next[op])
+	{
+		if (next->OperationTerm(b, fwd, merge_point, merge_op) == b)
+			return b;
+	}
+	
+
+	
+	
+	if (parent)
+	{
+		//merge->m_next[*merge_op].push_back(b);
+		m_next[op].push_back(b);
+	}
+	else
+	{
+		if (m_next[op].size() == 0)
+		{
+			*merge_point = this;
+			*merge_op = op;
+		}
+	}
+	return NULL;
+}
+
+ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
+{
+	m_cached_result = nan("");
+	if (Floating() && m_value == 0)
+	{
+		return b;
+	}
+	
+	if (Floating() && m_value == 1 && op == MULTIPLY)
+	{
+		m_value = b->m_value;
+		for (int i = 0; i < NOP; ++i)
+		{
+			for (auto n : m_next[i])
+				delete n;
+			m_next[i].clear();
+			swap(m_next[i], b->m_next[i]);
+		}
+		return b;
+	}
+	if (b->Floating() && b->m_value == 1)
+		return b;
+	
+
+		
+	if (NoTerms() && b->NoTerms())
+	{
+		if (ParanoidOp<digit_t>(m_value, b->m_value, op))
+		{
+			Optype mulop = (op == MULTIPLY) ? MULTIPLY : DIVIDE;
+			for (auto mul : b->m_next[MULTIPLY])
+			{
+				delete OperationFactor(mul, mulop);
+			}
+			Optype divop = (op == MULTIPLY) ? DIVIDE : MULTIPLY;
+			for (auto div : b->m_next[DIVIDE])
+				delete OperationFactor(div, divop);
+				
+			b->m_next[DIVIDE].clear();
+			b->m_next[MULTIPLY].clear();
+			
+			
+			
+			return b;		
+		}
+	}
+	
+		
+	bool parent = (merge_point == NULL);
+	ParanoidNumber * merge = this;
+	Optype mop = op;
+	if (parent)
+	{
+		merge_point = &merge;
+		merge_op = &mop;	
+	}
+	else
+	{
+		merge = *merge_point;
+		mop = *merge_op;
+	}
+		
+	Optype invop = InverseOp(op); // inverse of p
+	Optype fwd = op;
+	Optype rev = invop;
+	if (op == DIVIDE)
+	{
+		fwd = MULTIPLY;
+		rev = DIVIDE;
+	}
+
+	ParanoidNumber * cpy_b = NULL;
+	
+	if (m_next[ADD].size() > 0 || m_next[SUBTRACT].size() > 0)
+	{
+		cpy_b = new ParanoidNumber(*b);
+	}
+	
+	for (auto prev : m_next[invop])
+	{
+		if (prev->OperationFactor(b, rev, merge_point, merge_op) == b)
+		{
+			for (auto add : m_next[ADD])
+				delete add->OperationFactor(new ParanoidNumber(*cpy_b), op);
+			for (auto sub : m_next[SUBTRACT])
+				delete sub->OperationFactor(new ParanoidNumber(*cpy_b), op);
+				
+			delete cpy_b;
+			return b;
+		}
+	}
+	for (auto next : m_next[op])
+	{
+		if (next->OperationFactor(b, fwd, merge_point, merge_op) == b)
+		{
+			for (auto add : m_next[ADD])
+				delete add->OperationFactor(new ParanoidNumber(*cpy_b), op);
+			for (auto sub : m_next[SUBTRACT])
+				delete sub->OperationFactor(new ParanoidNumber(*cpy_b), op);
+			delete cpy_b;
+			return b;
+		}
+	}
+	
+	if (parent)
+	{
+		m_next[op].push_back(b);
+		for (auto add : m_next[ADD])
+			delete add->OperationFactor(new ParanoidNumber(*cpy_b), op);
+		for (auto sub : m_next[SUBTRACT])
+			delete sub->OperationFactor(new ParanoidNumber(*cpy_b), op);
+	}
+	return NULL;	
+}
+
+
+
+/**
+ * Performs the operation on a with argument b (a += b, a -= b, a *= b, a /= b)
+ * @returns b if b can safely be deleted
+ * @returns NULL if b has been merged with a
+ * append indicates that b should be merged
+ */
+ParanoidNumber * ParanoidNumber::Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
+{
+
+	if (b == NULL)
+		return NULL;
+
+	
+	if (op == SUBTRACT || op == ADD)
+		return OperationTerm(b, op, merge_point, merge_op);
+	if (op == MULTIPLY || op == DIVIDE)
+		return OperationFactor(b, op, merge_point, merge_op);
+	return b;
+}
+
+
+
+string ParanoidNumber::PStr() const
+{
+	stringstream s;
+	for (int i = 0; i < NOP; ++i)
+	{
+		Optype f = Optype(i);
+		s << this;
+		for (auto n : m_next[f])
+		{
+			s << OpChar(f) << n->PStr();
+		}
+	}
+	return s.str();
+}
+
+bool ParanoidNumber::Simplify(Optype op)
+{
+	vector<ParanoidNumber*> next(0);
+	swap(m_next[op], next);
+	for (auto n : next)
+	{
+		delete Operation(n, op);
+	}
+	return (next.size() > m_next[op].size());
+}
+
+bool ParanoidNumber::FullSimplify()
+{
+	bool result = false;
+	result |= Simplify(MULTIPLY);
+	result |= Simplify(DIVIDE);
+	result |= Simplify(ADD);
+	result |= Simplify(SUBTRACT);
+	return result;
+}
+
+
+ParanoidNumber::digit_t ParanoidNumber::Digit()
+{
+	if (!isnan(m_cached_result))
+		return m_cached_result;
+	m_cached_result = m_value;
+	for (auto mul : m_next[MULTIPLY])
+	{
+		m_cached_result *= mul->Digit();
+	}
+	for (auto div : m_next[DIVIDE])
+	{
+		m_cached_result /= div->Digit();
+	}
+	for (auto add : m_next[ADD])
+		m_cached_result += add->Digit();
+	for (auto sub : m_next[SUBTRACT])
+		m_cached_result -= sub->Digit();
+	return m_cached_result;
+		
+}
+
+ParanoidNumber::digit_t ParanoidNumber::GetFactors()
+{
+	digit_t value = 1;
+	for (auto mul : m_next[MULTIPLY])
+		value *= mul->Digit();
+	for (auto div : m_next[DIVIDE])
+		value /= div->Digit();
+	return value;
+}
+
+
+ParanoidNumber::digit_t ParanoidNumber::GetTerms()
+{
+	digit_t value = 0;
+	for (auto add : m_next[ADD])
+		value += add->Digit();
+	for (auto sub : m_next[SUBTRACT])
+		value -= sub->Digit();
+	return value;
+}
+
+
 }