X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fparanoidnumber.cpp;h=60802eb432a7acc0f17c530a42bf7b0461c17f0b;hp=2bb44da2b5fbbf0dab74ccb9c7b35d6233cfbf62;hb=64b7c42c71c35d520424cf4ca5ecaa99faef8b26;hpb=dfba002efc3b5f126ddb69e63b9a7dafdd9eacda diff --git a/src/paranoidnumber.cpp b/src/paranoidnumber.cpp index 2bb44da..60802eb 100644 --- a/src/paranoidnumber.cpp +++ b/src/paranoidnumber.cpp @@ -3,17 +3,46 @@ #include #include #include "log.h" +#include #include +// here be many copy paste bugs + using namespace std; namespace IPDF { - -ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next_term(NULL), m_next_factor(NULL) + +#ifdef PARANOID_USE_ARENA +ParanoidNumber::Arena ParanoidNumber::g_arena; +#endif //PARANOID_USE_ARENA + +ParanoidNumber::~ParanoidNumber() +{ + for (int i = 0; i < NOP; ++i) + { + for (auto n : m_next[i]) + delete n; + } +} + +ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_next() { + #ifdef PARANOID_SIZE_LIMIT + m_size = 1; + #endif + #ifdef PARANOID_CACHE_RESULTS + m_cache_valid = false; + #endif + int dp = 0; int end = 0; + bool negate = str[0] == '-'; + if (negate) + { + dp++; + end++; + } while (str[dp] != '\0' && str[dp] != '.') { ++dp; @@ -21,16 +50,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) + for (int i = dp-1; i >= negate; --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,297 +63,943 @@ 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()); + + if (negate) + Negate(); + + #ifdef PARANOID_COMPARE_EPSILON + double d = strtod(str.c_str(), NULL); + CompareForSanity(d, d); + #endif } 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) + //assert(this != NULL); + + #ifdef PARANOID_SIZE_LIMIT + m_size = a.m_size; + #endif + + m_value = a.m_value; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = a.m_cached_result; + m_cache_valid = a.m_cache_valid; + #endif + for (int i = 0; i < NOP; ++i) { - m_next_factor = new ParanoidNumber(*(a.m_next_factor)); + for (auto n : m_next[i]) + delete n; + m_next[i].clear(); + for (auto n : a.m_next[i]) + m_next[i].push_back(new ParanoidNumber(*n)); } + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(a.Digit(),a.Digit()); + #endif return *this; } -ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a) + +string ParanoidNumber::Str() const { - // this = v + t + (a) - // -> v + (a) + t - ParanoidNumber * nt = m_next_term; - ParanoidNumber * nf = m_next_factor; + //assert(this != NULL); + 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 ca(a); - if (m_next_factor != NULL) + for (auto add : m_next[ADD]) { - if (m_next_factor->m_op == MULTIPLY) - ca /= (*m_next_factor); + result += "+"; + if (!add->Floating()) + result += "(" + add->Str() + ")"; 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; - } - + result += add->Str(); + } + for (auto sub : m_next[SUBTRACT]) + { + result += "-"; + if (!sub->Floating()) + result += "(" + sub->Str() + ")"; + else + result += sub->Str(); } - 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; + + return result; } -ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a) +template <> +bool TrustingOp(float & a, const float & b, Optype op) { - // this = v + t + (a) - // -> v + (a) + t - - ParanoidNumber * nt = m_next_term; - ParanoidNumber * nf = m_next_factor; + - ParanoidNumber ca(a, SUBTRACT); - if (m_next_factor != NULL) + feclearexcept(FE_ALL_EXCEPT); + switch (op) { - if (m_next_factor->m_op == MULTIPLY) - ca /= (*m_next_factor); - else - ca *= (*m_next_factor); + case ADD: + a += b; + break; + case SUBTRACT: + a -= b; + break; + case MULTIPLY: + a *= b; + break; + case DIVIDE: + if (b == 0) + { + a = (a >= 0) ? INFINITY : -INFINITY; + return false; + } - if (ca.Floating()) - { - m_next_factor = NULL; - m_next_term = NULL; - operator-=(ca); - m_next_factor = nf; - m_next_term = nt; - Simplify(); - return *this; - } - + a /= b; + break; + case NOP: + break; } + return !fetestexcept(FE_ALL_EXCEPT); +} + +template <> +bool TrustingOp(double & a, const double & 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: + if (b == 0) + { + a = (a >= 0) ? INFINITY : -INFINITY; + return false; + } + a /= b; + break; + case NOP: + break; + } + return !fetestexcept(FE_ALL_EXCEPT); +} + + + +template <> +bool TrustingOp(long double & a, const long double & b, Optype op) +{ + - m_next_term = new ParanoidNumber(a,SUBTRACT); - ParanoidNumber * t = m_next_term; - while (t->m_next_term != NULL) + feclearexcept(FE_ALL_EXCEPT); + switch (op) { - t->m_op = SUBTRACT; - t = t->m_next_term; + case ADD: + a += b; + break; + case SUBTRACT: + a -= b; + break; + case MULTIPLY: + a *= b; + break; + case DIVIDE: + if (b == 0) + { + a = (a >= 0) ? INFINITY : -INFINITY; + return false; + } + + a /= b; + break; + case NOP: + break; } - 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 !fetestexcept(FE_ALL_EXCEPT); +} + + +template <> +bool TrustingOp(int8_t & a, const int8_t & b, Optype op) +{ + int16_t sa(a); + bool exact = true; + switch (op) + { + 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; + } + a = (int8_t)(sa); + return exact; +} + + +ParanoidNumber & ParanoidNumber::operator+=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare += a; + #endif + delete Operation(new ParanoidNumber(a), ADD); + Simplify(SUBTRACT); + Simplify(ADD); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator-=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare -= a; + #endif + delete Operation(new ParanoidNumber(a), SUBTRACT); + Simplify(ADD); + Simplify(SUBTRACT); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} + +ParanoidNumber & ParanoidNumber::operator*=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare *= a; + #endif + delete Operation(new ParanoidNumber(a), MULTIPLY); + Simplify(DIVIDE); + Simplify(MULTIPLY); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator/=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare /= a; + #endif + delete Operation(new ParanoidNumber(a), DIVIDE); + Simplify(MULTIPLY); + Simplify(DIVIDE); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare += a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), ADD); + Simplify(SUBTRACT); + Simplify(ADD); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare -= a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), SUBTRACT); + Simplify(ADD); + Simplify(SUBTRACT); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif return *this; } ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a) { - Debug("{%s} *= {%s}", Str().c_str(), a.Str().c_str()); - // this = (vf + t) * (a) - ParanoidNumber * nf = m_next_factor; - m_next_factor = new ParanoidNumber(a, MULTIPLY); - ParanoidNumber * t = m_next_factor; - while (t->m_next_factor != NULL) - t = t->m_next_factor; - t->m_next_factor = nf; - if (m_next_term != NULL) - m_next_term->operator*=(a); - //Debug("Simplify after mul"); - Debug("Simplify {%s}", Str().c_str()); - Simplify(); + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare *= a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), MULTIPLY); + Simplify(DIVIDE); + Simplify(MULTIPLY); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif return *this; } ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a) { - //Debug("Called %s /= %s", Str().c_str(), a.Str().c_str()); - // this = (vf + t) * (a) - ParanoidNumber * nf = m_next_factor; - m_next_factor = new ParanoidNumber(a, DIVIDE); - ParanoidNumber * t = m_next_factor; - while (t->m_next_factor != NULL) - t = t->m_next_factor; - t->m_next_factor = nf; - if (m_next_term != NULL) - m_next_term->operator/=(a); - Simplify(); + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare /= a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), DIVIDE); + Simplify(MULTIPLY); + Simplify(DIVIDE); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif return *this; } +ParanoidNumber & ParanoidNumber::operator=(const digit_t & a) +{ + + for (int i = 0; i < NOP; ++i) + { + for (auto n : m_next[i]) + delete n; + m_next[i].clear(); + } + m_value = a; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = a; + m_cache_valid = true; + #endif + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(a,a); + #endif + + return *this; +} -void ParanoidNumber::SimplifyTerms() -{ - //Debug("Simplify {%s}", Str().c_str()); - if (m_next_term == NULL) +// a + b +ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op) +{ + ////assert(b->SanityCheck()); + #ifdef PARANOID_CACHE_RESULTS + m_cache_valid = false; + #endif + #ifdef PARANOID_SIZE_LIMIT + if (m_size + b->m_size >= PARANOID_SIZE_LIMIT) + { + this->operator=(this->Digit()); + if (op == ADD) + m_value += b->Digit(); + else + m_value -= b->Digit(); + m_size = 1; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = m_value; + m_cache_valid = true; + #endif + return b; + } + //Debug("At size limit %d", m_size); + #endif + + + if (Floating() && m_value == 0) // 0 + b = b { - //Debug("No terms!"); - return; + 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(); + } + + //assert(SanityCheck()); + return b; } + if (b->Floating() && b->m_value == 0) // a + 0 = a + return b; + - for (ParanoidNumber * a = this; a != NULL; a = a->m_next_term) + + if ((NoFactors() && b->NoFactors()) + || (GetFactors() == b->GetFactors())) { - ParanoidNumber * bprev = a; - ParanoidNumber * b = a->m_next_term; - while (b != NULL) + if (ParanoidOp(m_value, b->m_value, op)) { - //Debug("Simplify factors of %s", b->Str().c_str()); - b->SimplifyFactors(); - if (b->m_next_factor != NULL) - { - bprev = b; - b = b->m_next_term; - continue; - } - float f = a->m_value; - feclearexcept(FE_ALL_EXCEPT); - switch (b->m_op) + Optype addop = (op == ADD) ? ADD : SUBTRACT; + for (auto add : b->m_next[ADD]) { - case ADD: - f += b->m_value; - break; - case SUBTRACT: - f -= b->m_value; - break; - default: - Fatal("Unexpected %c in term list...", OpChar(b->m_op)); - break; + delete (OperationTerm(add, addop)); } - if (!fetestexcept(FE_ALL_EXCEPT)) - { - a->m_value = f; - bprev->m_next_term = b->m_next_term; - b->m_next_term = NULL; - delete b; - b = bprev; - } - bprev = b; - b = b->m_next_term; + 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(); + //assert(SanityCheck()); + 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) + { + //assert(SanityCheck()); + return b; + } + + } + for (auto next : m_next[op]) + { + if (next->OperationTerm(b, fwd, merge_point, merge_op) == b) + { + //assert(SanityCheck()); + return b; + } + } + + + + + if (parent) + { + //merge->m_next[*merge_op].push_back(b); + m_next[op].push_back(b); + #ifdef PARANOID_SIZE_LIMIT + m_size += b->m_size; + #endif + } + else + { + if (m_next[op].size() == 0) + { + *merge_point = this; + *merge_op = op; } } + + //assert(SanityCheck()); + + return NULL; } -void ParanoidNumber::SimplifyFactors() -{ - //Debug("Simplify {%s}", Str().c_str()); - if (m_next_factor == NULL) +ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op) +{ + #ifdef PARANOID_CACHE_RESULTS + m_cache_valid = false; + #endif + #ifdef PARANOID_SIZE_LIMIT + if (m_size + b->m_size >= PARANOID_SIZE_LIMIT) + { + this->operator=(this->Digit()); + if (op == MULTIPLY) + m_value *= b->Digit(); + else + m_value /= b->Digit(); + m_size = 1; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = m_value; + m_cache_valid = true; + #endif + //Debug("Cut off %p", this); + return b; + + } + #endif + + if (Floating() && m_value == 0) { - //Debug("No factors!"); - return; + 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]); + } + //assert(SanityCheck()); + return b; + } + if (b->Floating() && b->m_value == 1) + return b; + if (b->Floating() && b->m_value == 0 && op == MULTIPLY) + { + operator=(*b); + return b; } - for (ParanoidNumber * a = this; a != NULL; a = a->m_next_factor) + + if (NoTerms() && b->NoTerms()) { - ParanoidNumber * bprev = a; - ParanoidNumber * b = a->m_next_factor; - while (b != NULL) + if (ParanoidOp(m_value, b->m_value, op)) { - b->SimplifyTerms(); - if (b->m_next_term != NULL) + Optype mulop = (op == MULTIPLY) ? MULTIPLY : DIVIDE; + for (auto mul : b->m_next[MULTIPLY]) { - bprev = b; - b = b->m_next_factor; - continue; + delete(OperationFactor(mul, mulop)); } - float f = a->m_value; - feclearexcept(FE_ALL_EXCEPT); - switch (b->m_op) + 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 = 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]) { - case MULTIPLY: - if (a->m_op != DIVIDE) - f *= b->m_value; - else - f /= b->m_value; - break; - case DIVIDE: - if (a->m_op != DIVIDE) - f /= b->m_value; - else - f *= b->m_value; - break; - default: - Fatal("Unexpected %c in factor list...",OpChar(b->m_op)); - break; + delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op)); } - if (!fetestexcept(FE_ALL_EXCEPT)) + for (auto sub : m_next[SUBTRACT]) { - - a->m_value = f; - bprev->m_next_factor = b->m_next_factor; - b->m_next_factor = NULL; - delete b; - b = bprev; + delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op)); } - //else - //Debug("Failed to simplify %f %c %f", a->m_value, OpChar(b->m_op), b->m_value); - bprev = b; - b = b->m_next_factor; + delete(cpy_b); + return b; } } + + if (parent) + { + //assert(b != NULL); + 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)); + + #ifdef PARANOID_SIZE_LIMIT + m_size += b->m_size; + #endif + } + //assert(SanityCheck()); + + + + return NULL; } -void ParanoidNumber::Simplify() + + +/** + * 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) { - SimplifyFactors(); - SimplifyTerms(); + + 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::Str() const + + +string ParanoidNumber::PStr() const { - string result(""); 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) +{ - s << m_value; + if (Floating()) + return false; + + //assert(SanityCheck()); + vector next; + next.clear(); + swap(m_next[op], next); + m_next[op].clear(); + //assert(m_next[op].size() == 0); + //assert(SanityCheck()); + Optype fwd = op; + if (op == DIVIDE) + fwd = MULTIPLY; + else if (op == SUBTRACT) + fwd = ADD; + + + vector hold[2]; + if (op == MULTIPLY || op == DIVIDE) + { + swap(m_next[ADD], hold[0]); + swap(m_next[SUBTRACT], hold[1]); + } - if (m_next_factor != NULL) + for (vector::iterator n = next.begin(); n != next.end(); ++n) { - result += OpChar(m_op); - result += "("; - result += s.str(); - result += m_next_factor->Str(); - result += ")"; + if (*n == NULL) + continue; + for (vector::iterator m = n; m != next.end(); ++m) + { + if ((*m) == (*n)) + continue; + if (*m == NULL) + continue; + + ParanoidNumber * parent = this; + Optype mop = op; + ParanoidNumber * result = (*n)->Operation(*m, fwd, &parent, &mop); + if (result != NULL) + { + #ifdef PARANOID_SIZE_LIMIT + m_size -= result->m_size; + #endif + *m = NULL; + delete(result); + } + } } - else + + + + for (auto n : next) + { + if (n != NULL) + { + #ifdef PARANOID_SIZE_LIMIT + if (Operation(n, op) == n) + { + m_size -= n->m_size; + delete n; + } + #else + delete(Operation(n, op)); + #endif + } + } + + if (op == MULTIPLY || op == DIVIDE) + { + swap(m_next[ADD], hold[0]); + swap(m_next[SUBTRACT], hold[1]); + } + + set s; + //if (!SanityCheck(s)) + //{ + // Error("Simplify broke Sanity"); + //} + 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() const +{ + + // Get around the absurd requirement that const correctness be observed. + #ifdef PARANOID_CACHE_RESULTS + if (m_cache_valid) // le sigh ambiguous function compiler warnings + return m_cached_result; + + digit_t & result = ((ParanoidNumber*)(this))->m_cached_result; + + #else + digit_t result; + #endif + result = m_value; + for (auto mul : m_next[MULTIPLY]) + { + result *= mul->Digit(); + } + for (auto div : m_next[DIVIDE]) + { + result /= div->Digit(); + } + for (auto add : m_next[ADD]) + result += add->Digit(); + for (auto sub : m_next[SUBTRACT]) + result -= sub->Digit(); + + #ifdef PARANOID_CACHE_RESULTS + ((ParanoidNumber*)(this))->m_cache_valid = true; + #endif + return result; + +} + +ParanoidNumber::digit_t ParanoidNumber::GetFactors() const +{ + 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() const +{ + digit_t value = 0; + for (auto add : m_next[ADD]) + value += add->Digit(); + for (auto sub : m_next[SUBTRACT]) + value -= sub->Digit(); + return value; +} + +bool ParanoidNumber::SanityCheck(set & visited) const +{ + if (this == NULL) + { + Error("NULL pointer in tree"); + return false; + } + + if (visited.find((ParanoidNumber*)this) != visited.end()) { - result += OpChar(m_op); - result += s.str(); + Error("I think I've seen this tree before..."); + return false; } + + visited.insert((ParanoidNumber*)this); - if (m_next_term != NULL) + for (auto add : m_next[ADD]) + { + if (!add->SanityCheck(visited)) + return false; + } + for (auto sub : m_next[SUBTRACT]) + { + if (!sub->SanityCheck(visited)) + return false; + } + for (auto mul : m_next[MULTIPLY]) { - result += " "; - result += m_next_term->Str(); + if (!mul->SanityCheck(visited)) + return false; + } + + for (auto div : m_next[DIVIDE]) + { + if (!div->SanityCheck(visited)) + return false; + if (div->Digit() == 0) + { + Error("Divide by zero"); + return false; + } + } + return true; +} + +void ParanoidNumber::Negate() +{ + swap(m_next[ADD], m_next[SUBTRACT]); + m_value = -m_value; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = -m_cached_result; + #endif +} + +#ifdef PARANOID_USE_ARENA + +void * ParanoidNumber::operator new(size_t s) +{ + return g_arena.allocate(s); +} + +void ParanoidNumber::operator delete(void * p) +{ + g_arena.deallocate(p); +} + +ParanoidNumber::Arena::Arena(int64_t block_size) : m_block_size(block_size), m_spare(NULL) +{ + m_blocks.push_back({malloc(block_size*sizeof(ParanoidNumber)),0}); +} + +ParanoidNumber::Arena::~Arena() +{ + for (auto block : m_blocks) + { + free(block.memory); + } + m_blocks.clear(); +} + +void * ParanoidNumber::Arena::allocate(size_t s) +{ + if (m_spare != NULL) + { + void * result = m_spare; + m_spare = NULL; + return result; + } + + Block & b = m_blocks.back(); + void * result = (ParanoidNumber*)(b.memory) + (b.used++); + if (b.used >= m_block_size) + { + m_block_size *= 2; + Debug("Add block of size %d", m_block_size); + m_blocks.push_back({malloc(m_block_size*sizeof(ParanoidNumber)), 0}); } return result; } +void ParanoidNumber::Arena::deallocate(void * p) +{ + m_spare = p; +} +#endif //PARANOID_USE_ARENA + }