Natural Sort?


#1

Has anybody implemented a natural order sort function for juce strings? I’ve thought about just using StrCmpLogicalW(), but I would like something that is portable.

Also, it would be nice if StringArray had a sort function that you could pass an ElementComparator into.


#2

This.

I recently ran into the case where for a set of strings, I knew that sorting by doing the comparison from right to left would be more efficient 90% of the time, and it would have been useful if a custom sort comparator could be set.

Obviously it’s easy enough to create an owned array of string, but string array is more descriptive.


#3
// FOR THE STRING CLASS

    /* This converts a char pointer to an int like stroul ... but only in 

     base 10 (boring!)  Assumes that we already have a digit. */

    

    unsigned long charPtrToIntInternal(CharPointerType & s) const {

        unsigned int digit; // careful. must be unsigned so negs roll around.

        long int result(0);

        while (s.isDigit()) {

            digit = (*s) - '0';

            result *= 10;

            result += digit;

            ++s;

        }

        return result;

    }


    /* This is a stripped back version of DOJ's code. Adjusted to be a bit more

     JUCE friendly. */

    

    int compareWithYogicKarma(const String & other) const noexcept

    {

        enum Mode {

            mString,

            mNumber

        } mode;

        

        CharPointerType s1 (text);

        CharPointerType s2 (other.text);

        

        while (*s1 && *s2) {

            if (mode == mString) {

                // mString.  Flips into number mode if it

                // spots a digit at the same point in both

                // strings.

                char s1c, s2c;

                while ((s1c = *s1) && (s2c = *s2)) {

                    const bool s1dig = s1.isDigit();

                    const bool s2dig = s2.isDigit();

                    if (s1dig && s2dig) {

                        mode = mNumber;

                        break;

                    }

                    if (s1dig) return -1;

                    if (s2dig) return 1;

                    const int diff = *s1 - *s2;

                    if (diff != 0) return diff;

                    s1++;

                    s2++;

                }

            } else {

                // mNumber.

                // Note that charPtrToIntInternal advances s1 or s2 past the number!

                unsigned long s1int = charPtrToIntInternal(s1);

                unsigned long s2int = charPtrToIntInternal(s2);

                const long int diff = s1int - s2int;

                if (diff != 0)

                    return diff;

                mode = mString;

                

            }

        }

        if (*s1) return -1;

        if (*s2) return 1;

        return 0;

    }

And some additions to StringArray: 


struct InternalStringArrayComparator_Natural

{

    static int compareElements (String& first, String& second)      { return first.compareWithYogicKarma(second); }

};


void StringArray::naturalSort() {

    InternalStringArrayComparator_Natural comp;

    strings.sort(comp);

}

The sort code is based on http://www.davekoelle.com/files/alphanum.hpp and probably warrants the inclusion of the copyright message from there. Though I've had to modify a few bits to make it more JUCE friendly.  

The following test passes.  It doesn't crash, but doesn't properly sort, if numbers in the string are bigger than a long int can hold. 

int main (int argc, char* argv[])

{

    

    const char* data[] = {

        "Test1",

        "Test2",

        "Test0",

        "Test 30",

        "Test 12",

        "Test 01",

        "Fred Flintstone",

        "Wilma 1",

        "Wilma 0",

        "Wilma 31892038291",

        "Wilma 100",

        ""

    };

    

    

    StringArray array(data);


    array.naturalSort();

    

    for (auto & s: array) {

        DBG(s);

    }


    return 0;

}

#4

Jules - I don't suppose there's much chance of something along these lines making it into JUCE?  If not I'll knock something together here.. 


#5

Doesn't the Array class have a sort function?


#6

Yeah, possibly.. I'll take a look if I get chance.


#7

Not for this type of sort I guess :)


#8

No hurry at all.


#9

Actually, I know I said no hurry at all, but can you bump this one up onto a fresher post-it note!

Let me know if there's no chance and I'll figure out how to squeeze it in for myself everywhere :)


#10

Added it weeks ago! String::compareNatural()


#11

Oh bloody hell.  I'm going to get some kind of stream of your commits set up! :) 


#12