NumberWriter.h

/*--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants
Licensee a limited, non-exclusive, non-transferable, royalty-free license
(without the right to sublicense) to use the API solely for the purpose of
Licensee's internal development efforts to develop applications for which
the API was provided.
 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: Base
File: NumberWriter
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/String.h>
#include <NDEVR/BaseValues.h>
#include <NDEVR/NumberParser.h>
#include <cmath>
 
namespace NDEVR
{
    static constexpr fltp08 kPowersOfTen[23] =
    {
        1e0,  1e1,  1e2,  1e3,  1e4,  1e5,  1e6,  1e7,  1e8,  1e9,
        1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
        1e20, 1e21, 1e22
    };

    class NumberWriter
    {
    private:
        static inline fltp08 QuickPowTen(uint04 exp) noexcept
        {
            if (exp < 23)
                return kPowersOfTen[exp];
            else
                return cast<fltp08>(std::pow(10, exp));
        }
        class D2A
        {
            static constexpr fltp08 kLog2_10 = 0.30102999566398119521373889472449; 
            static constexpr uint04 maxBase2Precision = 53; 
            static constexpr uint08 two_pow_maxBase2PrecisionMinus1 = uint08(1) << (maxBase2Precision - 1); 

            static inline fltp08 quickPowTwo(uint04 exp)
            {
                if (0 < exp && exp < 64)
                    return cast<fltp08>(uint64_t(1) << exp);
                else
                    return cast<fltp08>(std::pow(2, exp));
            }
 
        public:
            D2A(const fltp08 avalue, bool fixedPrecision, uint04 minPrecision)
                : value(avalue)
                , e(0)
                , finished(false)
            {
                mantissa = n_frexp(value, &e);
 
                if (fixedPrecision)
                {
                    lowOk = highOk = true;
                }
                else
                {
                    bool round = (mantissa & 1) == 0;
                    lowOk = highOk = round;
                }
 
                mantissaPrec = maxBase2Precision;
                while (mantissaPrec != 0 && (((mantissa >> --mantissaPrec) & 1) == 0)) {}
                mantissaPrec++;
                if (e >= 0)
                {
                    if (mantissa != two_pow_maxBase2PrecisionMinus1)
                    {
                        const fltp08 be = quickPowTwo(e);
 
                        dr = cast<fltp08>(mantissa) * be * 2;
                        ds = 2;
                        dMPlus = be;
                        dMMinus = be;
                    }
                    else
                    {
                        fltp08 be = quickPowTwo(e);
                        fltp08 be1 = be * 2;
 
                        dr = cast<fltp08>(mantissa) * be1 * 2;
                        ds = 4;
                        dMPlus = be1;
                        dMMinus = be;
                    }
                }
                else if (mantissa != two_pow_maxBase2PrecisionMinus1)
                {
 
                    dr = cast<fltp08>(mantissa) * 2.0;
                    ds = quickPowTwo(1 - e); // pow(2,-e)*2;
                    dMPlus = 1;
                    dMMinus = 1;
                }
                else
                {
                    dr = cast<fltp08>(mantissa) * 4.0;
                    ds = quickPowTwo(2 - e); // pow(2, 1-e)*2;
                    dMPlus = 2;
                    dMMinus = 1;
                }
                if (fixedPrecision)
                {
                    const fltp08 fixedPrecisionPowTen = QuickPowTen(minPrecision);
                    ds *= fixedPrecisionPowTen;
                    dr *= fixedPrecisionPowTen;
                }
                base10Exp = scale();
            }

            uint08 n_frexp(double v, int* eptr) const
            {
                fltp08 fracMantissa = std::frexp(v, eptr);
                *eptr -= 53; // 52 mantissa bits + the hidden bit
                return (uint64_t)(fracMantissa * (double)(1LL << 53));
            }

            uint01 nextDigit()
            {
                if (finished)
                    return Constant<uint01>::Invalid;
 
                bool withinLowEndRoundRange;
                bool withinHighEndRoundRange;
                uint01 quotient;
 
                quotient = cast<uint01>(dr / ds);
                lib_assert(quotient < 10, "quotient cannot be > 9");
                double mod = fmod(dr, ds);
                dr = mod;
 
                // check if remaining ratio r/s is within the range of floats which would round to the value we have output
                //  so far when read in from a string.
                withinLowEndRoundRange = (lowOk ? (dr <= dMMinus) : (dr < dMMinus));
                withinHighEndRoundRange = (highOk ? (dr + dMPlus >= ds) : (dr + dMPlus > ds));
 
 
                if (!withinLowEndRoundRange)
                {
                    if (!withinHighEndRoundRange) // if not within either error range, set up to generate the next digit.
                    {
                        dr *= 10;
                        dMPlus *= 10;
                        dMMinus *= 10;
                    }
                    else
                    {
                        quotient++;
                        finished = true;
                    }
                }
                else if (!withinHighEndRoundRange)
                {
                    finished = true;
                }
                else
                {
                    if (dr * 2 < ds) // if (r*2 < s)  todo: faster to do lshift and compare?
                    {
                        finished = true;
                    }
                    else
                    {
                        quotient++;
                        finished = true;
                    }
                }
                return quotient;
            }

            sint04 expBase10() { return base10Exp; }
 
            fltp08 value;             ///< The original double value being converted.
            sint04 e;                 ///< The binary exponent from decomposition.
            uint08 mantissa;          ///< On input, value = mantissa*2^e;  Only last 53 bits are used.
            sint04 mantissaPrec;      ///< The number of bits of precision that are present in the mantissa.
            sint04 base10Exp;         ///< The (derived) base 10 exponent of value.
            bool finished;            ///< Set to true when we've output all relevant digits.
 
        private:
            bool lowOk;             ///< For IEEE unbiased rounding, this is true when mantissa is even.  When true, use >= in mMinus test instead of >
            bool highOk;            ///< Ditto, but for mPlus test.
 
            // If !bFastEstimateOk, use these.
 
        // If bFastEstimateOk, use these - same as above, but integer value stored in double.
            fltp08 dr;              ///< Scaled remainder value used during digit generation.
            fltp08 ds;              ///< Scaled divisor value used during digit generation.
            fltp08 dMPlus;          ///< Upper error bound for rounding during digit generation.
            fltp08 dMMinus;         ///< Lower error bound for rounding during digit generation.
 
            // Estimate base 10 exponent of number, scale r,s,mPlus,mMinus appropriately.
            // Returns result of fixup_ExponentEstimate(est).
            sint04 scale()
            {
                // estimate base10 exponent:
                sint04 base2Exponent = e + mantissaPrec - 1;
                sint04 exponentEstimate = (sint04)ceil((base2Exponent * kLog2_10) - 0.0000000001);
 
                fltp08 scale = QuickPowTen((exponentEstimate > 0) ? exponentEstimate : -exponentEstimate);
 
                if (exponentEstimate >= 0)
                {
                    ds *= scale;
                    return fixup_ExponentEstimate(exponentEstimate);
                }
                else
                {
                    dr *= scale;
                    dMPlus *= scale;
                    dMMinus *= scale;
                    return fixup_ExponentEstimate(exponentEstimate);
                }
            }
 
            // Used by scale to adjust for possible off-by-one error in the base 10 exponent estimate.
            // Returns exact base10 exponent of number.
            sint04 fixup_ExponentEstimate(sint04 exponentEstimate)
            {
                sint04 correctedEstimate;
                uint01 quotient = cast<uint01>((dr * 10) / ds);
                if ((highOk ? (dr + dMPlus) >= ds : dr + dMPlus > ds) || quotient >= 10)
                {
                    correctedEstimate = exponentEstimate + 1;
                }
                else
                {
                    dr *= 10;
                    dMPlus *= 10;
                    dMMinus *= 10;
                    correctedEstimate = exponentEstimate;
                }
                quotient = cast<uint01>(dr / ds);
                lib_assert(quotient < 10, "quotient cannot be > 9");
                return correctedEstimate;
            }
        };
    public:
        enum flt_to_string {
            DTOSTR_NORMAL,      ///< Default formatting, choosing the shortest accurate representation.
            DTOSTR_FIXED,       ///< Fixed-point notation with a specified number of decimal places.
            DTOSTR_PRECISION,   ///< Precision mode with a specified number of significant digits.
            DTOSTR_EXPONENTIAL  ///< Scientific/exponential notation (e.g. 1.23e+4).
        };

        template<class t_type>
        constexpr static void writeInt(String& string, t_type initial_value)
        {
            t_type value = initial_value;
            constexpr uint04 max_digits = MaxDigits<t_type>() + (ObjectInfo<t_type>::Unsigned ? 0 : 1U);
            char digits[max_digits];
            uint04 index = max_digits;
            if constexpr (!ObjectInfo<t_type>::Unsigned)
            {
                if (initial_value < cast<t_type>(0))
                    value = cast<t_type>(0) - value;
            }
            if (value == 0)
            {
                string.add('0');
                return;
            }
            while (index != 0)
            {
                t_type j = value;
                value = value / cast<t_type>(10);
                j -= (value * cast<t_type>(10));
                digits[--index] = (cast<char>(j) + '0');
                if (value == cast<t_type>(0))
                    break;
            }
            if constexpr ((!ObjectInfo<t_type>::Unsigned))
            {
                if(initial_value < cast<t_type>(0))
                    digits[--index] = '-';
            }
            string.addAll(&digits[index], max_digits - index);
        }

        template<class t_type>
        constexpr static void writeHex(String& string, t_type initial_value)
        {
            t_type value = initial_value;
            constexpr uint04 max_digits = MaxDigits<t_type>() + (ObjectInfo<t_type>::Unsigned ? 0 : 1U);
            char digits[max_digits];
            uint04 index = max_digits;
            if ((!ObjectInfo<t_type>::Unsigned) && initial_value < cast<t_type>(0))
            {
                value = cast<t_type>(0) - value;
            }
            if (value == 0)
            {
                string.add('0');
                return;
            }
            while (index != 0)
            {
                t_type j = value;
                value = value / cast<t_type>(16);
                j -= (value * cast<t_type>(16));
 
                if (j < 10)
                    digits[--index] = '0' + cast<char>(j);
                else
                {
                    switch (j)
                    {
                    case 10: digits[--index] = 'A'; break;
                    case 11: digits[--index] = 'B'; break;
                    case 12: digits[--index] = 'C'; break;
                    case 13: digits[--index] = 'D'; break;
                    case 14: digits[--index] = 'E'; break;
                    case 15: digits[--index] = 'F'; break;
                    }
                }
                if (value == cast<t_type>(0))
                    break;
            }
            string.addAll(&digits[index], max_digits - index);
        }

        static void writeFloat(String& string, fltp08 value, flt_to_string mode = DTOSTR_NORMAL, uint01 precision = 10)
        {
            if (value > Constant<fltp08>::Max)
            {
                string.addAll("-Infinity");
                return;
            }
            if (value < Constant<fltp08>::Min)
            {
                string.addAll("Infinity");
                return;
            }
            if (IsInvalid(value))
            {
                string.addAll("NaN");
                return;
            }
            if (mode == DTOSTR_NORMAL)
            {
                sint08 intValue = cast<sint08>(value);
                if ((value == (double)(intValue)) && ((uint32_t)intValue != 0x80000000))
                {
                    writeInt(string, intValue);
                    return;
                }
            }
            const bool negative = value < 0.0;
            const bool zero = value == 0.0;
            if (negative) {
                value = -value;
                string.add('-');
            }
            D2A d2a = D2A(value, mode != DTOSTR_NORMAL, precision);
            int32_t exp10 = d2a.expBase10() - 1;

            enum FormatType {
                kNormal,        ///< Standard decimal notation.
                kExponential,   ///< Scientific notation with exponent.
                kFraction,      ///< Fractional form (0.xxxx).
                kFixedFraction  ///< Fixed fractional form with specified decimal places.
            };
            FormatType format;
 
            switch (mode) {
            case DTOSTR_FIXED:
            {
                if (exp10 < 0) {
                    format = kFixedFraction;
                }
                else {
                    format = kNormal;
                    precision++;
                }
            }
            break;
            case DTOSTR_PRECISION:
            {
                if (exp10 < 0) {
                    format = kFraction;
                }
                else if (exp10 >= precision) {
                    format = kExponential;
                }
                else {
                    format = kNormal;
                }
            }
            break;
            case DTOSTR_EXPONENTIAL:
                format = kExponential;
                precision++;
                break;
            default:
                if (exp10 < 0 && exp10 > -7) {
                    // Number is of form 0.######
                    if (exp10 < -precision) {
                        exp10 = -precision - 1;
                    }
                    format = kFraction;
                }
                else if (std::abs(exp10) > 20) { // ECMA spec 9.8.1
                    format = kExponential;
                }
                else {
                    format = kNormal;
                }
            }
 
            // Digit generation.
            switch (format) {
            case kNormal:
            {
                int32_t digits = 0;
                int32_t digit;
                digit = d2a.nextDigit();
                if (digit > 0)
                    string.add((char)(digit + '0'));
                while (exp10 > 0)
                {
                    digit = (d2a.finished) ? 0 : d2a.nextDigit();
                    string.add((char)(digit + '0'));
                    exp10--;
                    digits++;
                }
                if (mode == DTOSTR_FIXED)
                {
                    digits = 0;
                }
                if (mode == DTOSTR_NORMAL)
                {
                    if (!d2a.finished)
                    {
                        string.add('.');
                        while (!d2a.finished)
                            string.add((char)(d2a.nextDigit() + '0'));
                    }
                }
                else if (digits < precision - 1)
                {
                    string.add('.');
                    for (; digits < precision - 1; digits++)
                    {
                        digit = d2a.finished ? 0 : d2a.nextDigit();
                        string.add((char)(digit + '0'));
                    }
                }
            }
            break;
            case kFixedFraction:
            {
                string.add('0'); // Sentinel
                string.add('.');
                // Write out leading zeroes
                int32_t digits = 0;
                if (exp10 > 0) {
                    while (++exp10 < 10 && digits < precision) {
                        string.add('0');
                        digits++;
                    }
                }
                else if (exp10 < 0) {
                    while ((++exp10 < 0) && (precision-- > 0))
                        string.add('0');
                }
                if (IsValid(precision))
                {
                    // Write out significand
                    for (; digits < precision; digits++) {
                        if (d2a.finished)
                        {
                            if (mode == DTOSTR_NORMAL)
                                break;
                            string.add('0');
                        }
                        else {
                            string.add((char)(d2a.nextDigit() + '0'));
                        }
                    }
                }
                exp10 = 0;
            }
            break;
            case kFraction:
            {
                string.add('0'); // Sentinel
                string.add('.');
 
                // Write out leading zeros
                if (!zero)
                {
                    for (int32_t i = exp10; i < -1; i++) {
                        string.add('0');
                    }
                }
 
                // Write out significand
                int32_t i = 0;
                while (!d2a.finished)
                {
                    string.add((char)(d2a.nextDigit() + '0'));
                    if (mode != DTOSTR_NORMAL && ++i >= precision)
                        break;
                }
                if (mode == DTOSTR_PRECISION)
                {
                    while (i++ < precision)
                        string.add((char)(d2a.finished ? '0' : d2a.nextDigit() + '0'));
                }
                exp10 = 0;
            }
            break;
            case kExponential:
            {
                int32_t digit;
                digit = d2a.finished ? 0 : d2a.nextDigit();
                string.add((char)(digit + '0'));
                if (((mode == DTOSTR_NORMAL) && !d2a.finished) ||
                    ((mode != DTOSTR_NORMAL) && precision > 1)) {
                    string.add('.');
                    for (int32_t i = 0; i < precision - 1; i++) {
                        if (d2a.finished)
                        {
                            if (mode == DTOSTR_NORMAL)
                                break;
                            string.add('0');
                        }
                        else {
                            string.add((char)(d2a.nextDigit() + '0'));
                        }
                    }
                }
            }
            break;
            }
            // Clean up zeroes, and place the exponent
            if (exp10)
            {
                if (!zero)
                {
                    // Remove trailing zeroes, as might appear in 10e+95
                    while (string.size() > 0 && string.last() == '0')
                    {
                        string.removeLast();
                        exp10++;
                    }
                }
 
                // Place the exponent
                string.add('e');
                if (exp10 > 0) {
                    string.add('+');
                }
                writeInt(string, exp10);
            }
        }
    };
}