X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=src%2Fparanoidnumber.cpp;h=b45c71e069e7ca95b0d79d7b1c8987fc9403080f;hb=6ce000e7212d9f5db6e5998c41df15bcad2022c8;hp=2510f66388cfce8f5431009c9887a330522f2974;hpb=6472d20ee58d2ecc0aee8bc1a12a071b2afc8a27;p=ipdf%2Fcode.git

diff --git a/src/paranoidnumber.cpp b/src/paranoidnumber.cpp
index 2510f66..b45c71e 100644
--- a/src/paranoidnumber.cpp
+++ b/src/paranoidnumber.cpp
@@ -3,14 +3,28 @@
 #include <sstream>
 #include <fenv.h>
 #include "log.h"
+#include <cassert>
+#include <iostream>
 
 using namespace std;
 namespace IPDF
 {
-	
+int64_t ParanoidNumber::g_count = 0;
+
+
+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_op(ADD), m_next(NULL)
+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] != '.')
@@ -20,7 +34,6 @@ 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)
 	{
@@ -37,263 +50,501 @@ ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next
 		b*=n;
 		this->operator+=(b);
 	}
-	
 }
 
-ParanoidNumber * ParanoidNumber::InsertAfter(float value, Optype op)
+ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
 {
-	return InsertAfter(new ParanoidNumber(value, op));
+	m_value = a.m_value;
+	m_cached_result = a.m_cached_result;
+	for (int i = 0; i < NOP; ++i)
+	{
+		for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j)
+		{
+			m_next[i][j]->operator=(*(a.m_next[i][j]));
+		}
+		
+		for (unsigned j = a.m_next[i].size(); j < m_next[i].size(); ++j)
+		{
+			delete m_next[i][j];
+		}
+		m_next[i].resize(a.m_next[i].size());
+	}	
+	return *this;
 }
-	
-ParanoidNumber * ParanoidNumber::InsertAfter(ParanoidNumber * insert)
+
+
+string ParanoidNumber::Str() const
 {
-	//Debug("Insert {%s} after {%f, %s}",insert->Str().c_str(),
-	//	m_value, g_opstr[m_op]);
-	ParanoidNumber * n = m_next;
-	m_next = insert;
+	string result("");
+	stringstream s;
+	s << (double)m_value;
+	result += s.str();
+	for (auto mul : m_next[MULTIPLY])
+	{
+		result += "*";
+		if (!mul->Floating())
+			result += "(" + mul->Str() + ")";
+		else
+			result += mul->Str();
+	}
+	for (auto div : m_next[DIVIDE])
+	{
+		result += "/";
+		if (!div->Floating())
+			result += "(" + div->Str() + ")";
+		else
+			result += div->Str();
+	}	
 	
-	ParanoidNumber * p = m_next;
-	while (p->m_next != NULL)
-		p = p->m_next;
-	p->m_next = n;
+	for (auto add : m_next[ADD])
+	{
+		result += "+";
+		if (!add->Floating())
+			result += "(" + add->Str() + ")";
+		else
+			result += add->Str();
+	}
+	for (auto sub : m_next[SUBTRACT])
+	{
+		result += "-";
+		if (!sub->Floating())
+			result += "(" + sub->Str() + ")";
+		else
+			result += sub->Str();
+	}
 	
-	return m_next;
+
+	return result;
 }
 
+template <>
+bool TrustingOp<float>(float & a, const float & b, Optype op)
+{
+	feclearexcept(FE_ALL_EXCEPT);
+	switch (op)
+	{
+		case ADD:
+			a += b;
+			break;
+		case SUBTRACT:
+			a -= b;
+			break;
+		case MULTIPLY:
+			a *= b;
+			break;
+		case DIVIDE:
+			a /= b;
+			break;
+		case NOP:
+			break;
+	}
+	return !fetestexcept(FE_ALL_EXCEPT);
+}
 
-ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
+template <>
+bool TrustingOp<double>(double & a, const double & b, Optype op)
 {
-	const ParanoidNumber * na = &a;
-	ParanoidNumber * nb = this;
-	ParanoidNumber * p = NULL;
-	while (na != NULL && nb != NULL)
-	{
-		nb->m_value = na->m_value;
-		nb->m_op = na->m_op;
-		na = na->m_next;
-		p = nb;
-		nb = nb->m_next;
-		
-	}	
-	
-	while (na != NULL) // => nb == NULL
+	feclearexcept(FE_ALL_EXCEPT);
+	switch (op)
 	{
-		InsertAfter(na->m_value, na->m_op);
-		na = na->m_next;
+		case ADD:
+			a += b;
+			break;
+		case SUBTRACT:
+			a -= b;
+			break;
+		case MULTIPLY:
+			a *= b;
+			break;
+		case DIVIDE:
+			a /= b;
+			break;
+		case NOP:
+			break;
 	}
+	return !fetestexcept(FE_ALL_EXCEPT);
+}
 
-	if (nb != NULL)
+template <>
+bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
+{
+	int16_t sa(a);
+	bool exact = true;
+	switch (op)
 	{
-		if (p != NULL)
-			p->m_next = NULL;
-		delete nb;
+		case ADD:
+			sa += b;
+			exact = (abs(sa) <= 127);
+			break;
+		case SUBTRACT:
+			sa -= b;
+			exact = (abs(sa) <= 127);
+			break;
+		case MULTIPLY:
+			sa *= b;
+			exact = (abs(sa) <= 127);
+			break;
+		case DIVIDE:
+			exact = (b != 0 && sa > b && sa % b == 0);
+			sa /= b;
+			break;
+		case NOP:
+			break;
 	}
-	return *this;
+	a = (int8_t)(sa);
+	return exact;
 }
 
+
 ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
 {
-	ParanoidNumber * insert = new ParanoidNumber(a, ADD);
-	if (m_next == NULL || m_next->m_op == ADD || m_next->m_op == SUBTRACT)
+	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
 	{
-		InsertAfter(insert);
-		Simplify();
-		return *this;
+		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;
+		}
+	}
+
 	
-	if (m_next->m_op == MULTIPLY) // (a*b) + c == (a+[c/b]) * b
-		insert->operator/=(*m_next);
-	else
-		insert->operator*=(*m_next); // (a/b) + c == (a+[c*b])/b
 	
-	if (insert->m_next != NULL) // neither of the above simplified
+	bool parent = (merge_point == NULL);
+	ParanoidNumber * merge = this;
+	Optype mop = op;
+	assert(mop != NOP); // silence compiler warning
+	if (parent)
 	{
-		//Debug("{%s} did not simplify, change back to {%s}", insert->Str().c_str(), a.Str().c_str());
-		insert->operator=(a); // Just add as is
-		insert->m_op = ADD;
-		ParanoidNumber * n = this;
-		while (n->m_next != NULL)
-			n = n->m_next;
-		n->InsertAfter(insert);
+		merge_point = &merge;
+		merge_op = &mop;
 	}
 	else
 	{
-		InsertAfter(insert);
+		merge = *merge_point;
+		mop = *merge_op;
 	}
-	Simplify();
-	return *this;
-}
-ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
-{
-	ParanoidNumber * insert = new ParanoidNumber(a, SUBTRACT);
-	if (m_next == NULL || m_next->m_op == ADD || m_next->m_op == SUBTRACT)
+		
+	Optype invop = InverseOp(op); // inverse of p
+	Optype fwd = op;
+	Optype rev = invop;
+	if (op == SUBTRACT)
 	{
-		InsertAfter(insert);
-		Simplify();
-		return *this;
+		fwd = ADD;
+		rev = SUBTRACT;
 	}
 	
-	if (m_next->m_op == MULTIPLY) // (a*b) - c == (a-[c/b]) * b
-		insert->operator/=(*m_next);
-	else
-		insert->operator*=(*m_next); // (a/b) - c == (a-[c*b])/b
-	
-	if (insert->m_next != NULL) // neither of the above simplified
-	{
-		//Debug("{%s} did not simplify, change back to {%s}", insert->Str().c_str(), a.Str().c_str());
-		insert->operator=(a); // Just add as is
-		insert->m_op = SUBTRACT;
-		ParanoidNumber * n = this;
-		while (n->m_next != NULL)
-			n = n->m_next;
-		n->InsertAfter(insert);
-	}	
-	else
+	for (auto prev : m_next[invop])
 	{
-		InsertAfter(insert);
+		if (prev->OperationTerm(b, rev, merge_point, merge_op) == b)
+			return b;
+		
 	}
-	Simplify();
-	return *this;
-}
+	for (auto next : m_next[op])
+	{
+		if (next->OperationTerm(b, fwd, merge_point, merge_op) == b)
+			return b;
+	}
+	
 
-ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
-{
-	ParanoidNumber * n = m_next;
-	while (n != NULL)
+	
+	
+	if (parent)
 	{
-		if (n->m_op == ADD || n->m_op == SUBTRACT)
+		//merge->m_next[*merge_op].push_back(b);
+		m_next[op].push_back(b);
+	}
+	else
+	{
+		if (m_next[op].size() == 0)
 		{
-			n->operator*=(a);
-			break;
+			*merge_point = this;
+			*merge_op = op;
 		}
-		n = n->m_next;
 	}
-		
-	InsertAfter(new ParanoidNumber(a, MULTIPLY));
-	Simplify();
-	return *this;
+	return NULL;
 }
 
-
-ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
+ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
 {
-	ParanoidNumber * n = m_next;
-	while (n != NULL)
+	m_cached_result = nan("");
+	if (Floating() && m_value == 0)
+	{
+		return b;
+	}
+	
+	if (Floating() && m_value == 1 && op == MULTIPLY)
 	{
-		if (n->m_op == ADD || n->m_op == SUBTRACT)
+		m_value = b->m_value;
+		for (int i = 0; i < NOP; ++i)
 		{
-			n->operator/=(a);
-			break;
+			for (auto n : m_next[i])
+				delete n;
+			m_next[i].clear();
+			swap(m_next[i], b->m_next[i]);
 		}
-		n = n->m_next;
+		return b;
 	}
-		
-	InsertAfter(new ParanoidNumber(a, DIVIDE));
-	Simplify();
-	return *this;
-}
+	if (b->Floating() && b->m_value == 1)
+		return b;
+	
 
-double ParanoidNumber::ToDouble() const
-{
-	double value = (m_op == SUBTRACT) ? -m_value : m_value;
-	const ParanoidNumber * n = m_next;
-	while (n != NULL)
+		
+	if (NoTerms() && b->NoTerms())
 	{
-		switch (n->m_op)
+		if (ParanoidOp<digit_t>(m_value, b->m_value, op))
 		{
-			case ADD:
-			case SUBTRACT:
-				return value + n->ToDouble();
-				break;
-			case MULTIPLY:
-				value *= n->m_value;
-				break;
-			case DIVIDE:
-				value /= n->m_value;
-				break;
+			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;		
 		}
-		n = n->m_next;
 	}
-	return value;
-}
-
-void ParanoidNumber::Simplify()
-{
-	ParanoidNumber * n = m_next;
-	ParanoidNumber * p = this;
 	
-	while (n != NULL)
+		
+	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;
+	}
 		
-		float a = p->m_value;
-		switch (n->m_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)
 		{
-			case ADD:
-				n->Simplify();
-				feclearexcept(FE_ALL_EXCEPT);
-				a += n->m_value;
-				break;
-			case SUBTRACT:
-				n->Simplify();
-				feclearexcept(FE_ALL_EXCEPT);
-				a -= n->m_value;
-				break;
-			case MULTIPLY:
-				feclearexcept(FE_ALL_EXCEPT);
-				a *= n->m_value;
-				break;
-			case DIVIDE:
-				feclearexcept(FE_ALL_EXCEPT);
-				a /= n->m_value;
-				break;
+			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;
 		}
-		// can't merge p and n
-		if (fetestexcept(FE_ALL_EXCEPT))
+	}
+	for (auto next : m_next[op])
+	{
+		if (next->OperationFactor(b, fwd, merge_point, merge_op) == b)
 		{
-			while (n != NULL && n->m_op != ADD && n->m_op != SUBTRACT)
-				n = n->m_next;
-			if (n != NULL)
-				n->Simplify();
-			return;
+			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;
 		}
-		else
+	}
+	
+	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])
 		{
-			//  merge n into p
-			p->m_value = a;
-			p->m_next = n->m_next;
-			n->m_next = NULL;
-			delete n;
-			n = p->m_next;		
+			s << OpChar(f) << n->PStr();
 		}
-		//Debug("  -> {%s}", Str().c_str());
 	}
+	return s.str();
 }
 
-string ParanoidNumber::Str() const
+bool ParanoidNumber::Simplify(Optype op)
 {
-	string result("");
-	switch (m_op)
+	vector<ParanoidNumber*> next(0);
+	swap(m_next[op], next);
+	for (auto n : next)
 	{
-		case ADD:
-			result += " +";
-			break;
-		case SUBTRACT:
-			result += " -";
-			break;
-		case MULTIPLY:
-			result += " *";
-			break;
-		case DIVIDE:
-			result += " /";
-			break;
+		delete Operation(n, op);
 	}
-	stringstream s("");
-	s << m_value;
-	result += s.str();
-	if (m_next != NULL)
-		result += m_next->Str();
+	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;
+}
+
+
 }