X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fparanoidnumber.cpp;h=60802eb432a7acc0f17c530a42bf7b0461c17f0b;hp=2510f66388cfce8f5431009c9887a330522f2974;hb=64b7c42c71c35d520424cf4ca5ecaa99faef8b26;hpb=6472d20ee58d2ecc0aee8bc1a12a071b2afc8a27 diff --git a/src/paranoidnumber.cpp b/src/paranoidnumber.cpp index 2510f66..60802eb 100644 --- a/src/paranoidnumber.cpp +++ b/src/paranoidnumber.cpp @@ -3,16 +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(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; @@ -20,9 +50,8 @@ 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; @@ -38,262 +67,939 @@ ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next this->operator+=(b); } + if (negate) + Negate(); + + #ifdef PARANOID_COMPARE_EPSILON + double d = strtod(str.c_str(), NULL); + CompareForSanity(d, d); + #endif } -ParanoidNumber * ParanoidNumber::InsertAfter(float value, Optype op) -{ - return InsertAfter(new ParanoidNumber(value, op)); -} - -ParanoidNumber * ParanoidNumber::InsertAfter(ParanoidNumber * insert) +ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a) { - //Debug("Insert {%s} after {%f, %s}",insert->Str().c_str(), - // m_value, g_opstr[m_op]); - ParanoidNumber * n = m_next; - m_next = insert; + //assert(this != NULL); - ParanoidNumber * p = m_next; - while (p->m_next != NULL) - p = p->m_next; - p->m_next = n; + #ifdef PARANOID_SIZE_LIMIT + m_size = a.m_size; + #endif - return m_next; + 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) + { + 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 { - const ParanoidNumber * na = &a; - ParanoidNumber * nb = this; - ParanoidNumber * p = NULL; - while (na != NULL && nb != NULL) + + //assert(this != NULL); + string result(""); + stringstream s; + s << (double)m_value; + result += s.str(); + for (auto mul : m_next[MULTIPLY]) { - nb->m_value = na->m_value; - nb->m_op = na->m_op; - na = na->m_next; - p = nb; - nb = nb->m_next; - + 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(); } - while (na != NULL) // => nb == NULL + for (auto add : m_next[ADD]) { - InsertAfter(na->m_value, na->m_op); - na = na->m_next; + 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(); } + - if (nb != NULL) + return result; +} + +template <> +bool TrustingOp(float & a, const float & b, Optype op) +{ + + + feclearexcept(FE_ALL_EXCEPT); + switch (op) { - if (p != NULL) - p->m_next = NULL; - delete nb; + 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 *this; + return !fetestexcept(FE_ALL_EXCEPT); } -ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a) +template <> +bool TrustingOp(double & a, const double & b, Optype op) { - ParanoidNumber * insert = new ParanoidNumber(a, ADD); - if (m_next == NULL || m_next->m_op == ADD || m_next->m_op == SUBTRACT) + feclearexcept(FE_ALL_EXCEPT); + switch (op) { - InsertAfter(insert); - Simplify(); - return *this; + 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) +{ + - 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 + feclearexcept(FE_ALL_EXCEPT); + switch (op) { - //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); + 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; } - else + 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) { - InsertAfter(insert); + 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; } - Simplify(); + 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) { - ParanoidNumber * insert = new ParanoidNumber(a, SUBTRACT); - if (m_next == NULL || m_next->m_op == ADD || m_next->m_op == SUBTRACT) + #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) +{ + #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) +{ + #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) { - InsertAfter(insert); - Simplify(); - return *this; + 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; +} + +// 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 (m_next->m_op == MULTIPLY) // (a*b) - c == (a-[c/b]) * b - insert->operator/=(*m_next); + + 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(); + } + + //assert(SanityCheck()); + return b; + } + if (b->Floating() && b->m_value == 0) // a + 0 = a + return b; + + + + if ((NoFactors() && b->NoFactors()) + || (GetFactors() == b->GetFactors())) + { + if (ParanoidOp(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(); + //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 - insert->operator*=(*m_next); // (a/b) - c == (a-[c*b])/b + { + 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; + } - if (insert->m_next != NULL) // neither of the above simplified + for (auto prev : m_next[invop]) { - //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); - } + 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 { - InsertAfter(insert); + if (m_next[op].size() == 0) + { + *merge_point = this; + *merge_op = op; + } } - Simplify(); - return *this; + + //assert(SanityCheck()); + + 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) + #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) + { + 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; + //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; } - - InsertAfter(new ParanoidNumber(a, MULTIPLY)); - Simplify(); - return *this; -} - -ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a) -{ - ParanoidNumber * n = m_next; - while (n != NULL) + + if (NoTerms() && b->NoTerms()) { - if (n->m_op == ADD || n->m_op == SUBTRACT) + if (ParanoidOp(m_value, b->m_value, op)) { - n->operator/=(a); - 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; } + - InsertAfter(new ParanoidNumber(a, DIVIDE)); - Simplify(); - return *this; + 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]) + { + 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) + { + //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; } -double ParanoidNumber::ToDouble() const + + +/** + * 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) { - double value = (m_op == SUBTRACT) ? -m_value : m_value; - const ParanoidNumber * n = m_next; - while (n != NULL) + + 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) { - switch (n->m_op) + Optype f = Optype(i); + s << this; + for (auto n : m_next[f]) { - case ADD: - case SUBTRACT: - return value + n->ToDouble(); - break; - case MULTIPLY: - value *= n->m_value; - break; - case DIVIDE: - value /= n->m_value; - break; + s << OpChar(f) << n->PStr(); } - n = n->m_next; } - return value; + return s.str(); } -void ParanoidNumber::Simplify() +bool ParanoidNumber::Simplify(Optype op) { - ParanoidNumber * n = m_next; - ParanoidNumber * p = this; - while (n != NULL) - { + 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; - float a = p->m_value; - switch (n->m_op) + + vector hold[2]; + if (op == MULTIPLY || op == DIVIDE) + { + swap(m_next[ADD], hold[0]); + swap(m_next[SUBTRACT], hold[1]); + } + + for (vector::iterator n = next.begin(); n != next.end(); ++n) + { + if (*n == NULL) + continue; + for (vector::iterator m = n; m != next.end(); ++m) { - 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; + 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); + } } - // can't merge p and n - if (fetestexcept(FE_ALL_EXCEPT)) - { - while (n != NULL && n->m_op != ADD && n->m_op != SUBTRACT) - n = n->m_next; - if (n != NULL) - n->Simplify(); - return; + } + + + + 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 } - else + } + + 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()) + { + Error("I think I've seen this tree before..."); + return false; + } + + visited.insert((ParanoidNumber*)this); + + 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]) + { + if (!mul->SanityCheck(visited)) + return false; + } + + for (auto div : m_next[DIVIDE]) + { + if (!div->SanityCheck(visited)) + return false; + if (div->Digit() == 0) { - // merge n into p - p->m_value = a; - p->m_next = n->m_next; - n->m_next = NULL; - delete n; - n = p->m_next; + Error("Divide by zero"); + return false; } - //Debug(" -> {%s}", Str().c_str()); } + return true; } -string ParanoidNumber::Str() const +void ParanoidNumber::Negate() { - string result(""); - switch (m_op) + 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) { - case ADD: - result += " +"; - break; - case SUBTRACT: - result += " -"; - break; - case MULTIPLY: - result += " *"; - break; - case DIVIDE: - result += " /"; - break; + 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}); } - stringstream s(""); - s << m_value; - result += s.str(); - if (m_next != NULL) - result += m_next->Str(); return result; } +void ParanoidNumber::Arena::deallocate(void * p) +{ + m_spare = p; +} +#endif //PARANOID_USE_ARENA + }