CODEWITHSUNDEEP
c++c++11
Medical physicist
Medical physicist

Reputation: 2594

Convert sorted floating point numbers into alphabetically sorted strings

I need to convert C++ double precision numbers into strings in such a way that sorting the strings alphabetically will deliver the same order as sorting the numbers arithmetically.

I'm considering using a fixed size integer and decimal part. For instance:

1.5 < 11.0, as well as alphabetically 0001.5000 < 0011.0000

However, this method has several problems (such as range limitation). Is there any better method? Does converting doubles into bitsets meet the requirements?

Upvotes: 1

Views: 83

Answers (2)

nielsen
nielsen

Reputation: 7719

The following function converts "normal" doubles into a string in the form <sign><exponent><mantissa> where sign is either N (negative) or P (positive). The mantissa precision is set to 17 decimal digits and can easily be adjusted.

Special cases (including 0) are handled in the bottom of the function.

Update: Added reversing the order of negative numbers. Since negative numbers need to be sorted with the largest absolute value first, we have to construct the 9's complement of the exponent and mantissa. Furthermore, the negative exponents must come after the positive exponents for negative numbers. Hence, the lower case "n" is used for negative exponents for negative numbers since that comes after uppercase "P" by its ASCII value.

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <cctype>

std::string doubleToString(double x)
{
    if(std::isnormal(x))
    {
        int e;
        double m = std::frexp(x, &e);
        std::stringstream s;
        bool negative = (m < 0.0);
        s << (negative ? "N" : "P"); // "N" for negative; "P" for positive
        s << "E"; // Exponent
        if(e >= 0)
        {
            s << "P" << std::setfill('0') << std::setw(5) << e;
        }
        else
        {
            s << ((negative) ? "n" : "N") << std::setfill('0') << std::setw(5) << -e;
        }
        s << "M" << std::setprecision(17) << std::fixed << std::fabs(m); // Mantissa
        std::string result;
        if(negative)
        {   // Convert numbers to 9's complement
            std::string tmp = s.str();
            for(auto c = tmp.begin(); c != tmp.end(); c++)
            {
                if(isdigit(*c))
                {
                    result += ('9' - ((*c) - '0'));
                }
                else
                {
                    result += *c;
                }
            }
        }
        else
        {
            result = s.str();
        }
        return result;
    }
    else
    {
        switch(std::fpclassify(x))
        {
            case FP_NAN: return "xNaN";
            case FP_ZERO: return "O";  // "O" is placed between "N" (negative) and "P" (positive)
            case FP_INFINITE: return (x>0) ? "PInf":"N Inf"; // The space after "N" goes before any number
            case FP_SUBNORMAL: // Fall through
            default:
                return "xUnknown";
        }
    }
}

Example outputs:

1.500000:  PEP00001M0.75000000000000000                                                                                                   
0.500000:  PEP00000M0.50000000000000000                                                                                                   
-0.005000: NEn99992M9.35999999999999998                                                                                                  
-0.500000: NEP99999M9.49999999999999999                                                                                                  
0.005000:  PEN00007M0.64000000000000001                                                                                                   
0.000000:  O                                                                                                                              
3.141593:  PEP00002M0.78539816339744828                                                                                                   
inf:       PInf                                                                                                                                
-inf:      N Inf                                                                                                                              
nan:       xNaN

Upvotes: 1

MSalters
MSalters

Reputation: 179981

We know FP numbers have three parts: sign, exponent, mantissa.

The sign has to come first, because all negative numbers sort before +0.0

The exponent has to come next, because all positive numbers with exponent N sort before exponent N+1. Naturally, all possible values of the exponent need a string representation such that they're ordered correctly, but the exponent is an integer. Therefore, zero-prefixing works.

The mantissa has to come last. It's also an integer, so the same zero-prefixing works.

NaN is unordered, so it doesn't matter where it would end up. +INF and -INF look like they'd work if you assume IEEE754 (iec559) representations.

Upvotes: 0

Related Questions