On 2/22/22 10:27 AM, Malcolm McLean wrote:
> Anyone got a string comparison function handy which compares strings intelligently by embedded numbers, so that foo2 compares earlier than foo11 ?

I know I have seen them. Basically as you scan the strings you need to
switch between mode. If you hit a digit in both strings you need to
collect the next set of chacters and convert them to number to compare,
and then switch back to letters after that,

The thing you need to decide is how do you want to handle things like:

a02b and a2b, are they the same? or which comes first?

Means you may need to keep track of how long the string was too.

Presumably you are only wanting to process the normal ASCII digits or
you get into all sorts of other complexities.

On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
> On 2/22/22 10:27 AM, Malcolm McLean wrote:
> > Anyone got a string comparison function handy which compares strings intelligently by embedded numbers, so that foo2 compares earlier than foo11 ?
> I know I have seen them. Basically as you scan the strings you need to
> switch between mode. If you hit a digit in both strings you need to
> collect the next set of chacters and convert them to number to compare,
> and then switch back to letters after that,
>
> The thing you need to decide is how do you want to handle things like:
>
>
> a02b and a2b, are they the same? or which comes first?
>
> Means you may need to keep track of how long the string was too.
>
> Presumably you are only wanting to process the normal ASCII digits or
> you get into all sorts of other complexities.
>
The customers are international so they might use non-ascii digits, but I don't think
we can cater for that.
Profile 1.01 should come after Profile 1.001. Since some people abuse decimal
points to indicate that 3.11 means "version three, minor version eleven", then you
can defend 3.2 coming either after or before 3.11. The system has no way of knowing
which convention is in use.

On Wed, 23 Feb 2022 07:21:54 -0800, Malcolm McLean wrote:

> On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
>> On 2/22/22 10:27 AM, Malcolm McLean wrote:
>> > Anyone got a string comparison function handy which compares strings
>> > intelligently by embedded numbers, so that foo2 compares earlier than
>> > foo11 ?
>> I know I have seen them. Basically as you scan the strings you need to
>> switch between mode. If you hit a digit in both strings you need to
>> collect the next set of chacters and convert them to number to compare,
>> and then switch back to letters after that,
>>
>> The thing you need to decide is how do you want to handle things like:
>>
>>
>> a02b and a2b, are they the same? or which comes first?
>>
>> Means you may need to keep track of how long the string was too.
>>
>> Presumably you are only wanting to process the normal ASCII digits or
>> you get into all sorts of other complexities.
>>
> The customers are international so they might use non-ascii digits, but
> I don't think we can cater for that.
> Profile 1.01 should come after Profile 1.001. Since some people abuse
> decimal points to indicate that 3.11 means "version three, minor version
> eleven", then you can defend 3.2 coming either after or before 3.11. The
> system has no way of knowing which convention is in use.

Given
Profile1
Profile2
where would you place
Profile01
? How about
Profile001
?

--
Lew Pitcher
"In Skills, We Trust"

On Wednesday, 23 February 2022 at 15:48:31 UTC, Lew Pitcher wrote:
> On Wed, 23 Feb 2022 07:21:54 -0800, Malcolm McLean wrote:
>
> > On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
> >> On 2/22/22 10:27 AM, Malcolm McLean wrote:
> >> > Anyone got a string comparison function handy which compares strings
> >> > intelligently by embedded numbers, so that foo2 compares earlier than
> >> > foo11 ?
> >> I know I have seen them. Basically as you scan the strings you need to
> >> switch between mode. If you hit a digit in both strings you need to
> >> collect the next set of chacters and convert them to number to compare,
> >> and then switch back to letters after that,
> >>
> >> The thing you need to decide is how do you want to handle things like:
> >>
> >>
> >> a02b and a2b, are they the same? or which comes first?
> >>
> >> Means you may need to keep track of how long the string was too.
> >>
> >> Presumably you are only wanting to process the normal ASCII digits or
> >> you get into all sorts of other complexities.
> >>
> > The customers are international so they might use non-ascii digits, but
> > I don't think we can cater for that.
> > Profile 1.01 should come after Profile 1.001. Since some people abuse
> > decimal points to indicate that 3.11 means "version three, minor version
> > eleven", then you can defend 3.2 coming either after or before 3.11. The
> > system has no way of knowing which convention is in use.
> Given
> Profile1
> Profile2
> where would you place
> Profile01
> ?
> How about
> Profile001

I'd say that leading zeroes place you before in the sorting order.
Thus
Profile001
Profile01
Profile1
Profile2

Profile0 would place before Profile001.

On 2022-02-23, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> On Wednesday, 23 February 2022 at 15:48:31 UTC, Lew Pitcher wrote:
>> On Wed, 23 Feb 2022 07:21:54 -0800, Malcolm McLean wrote:
>>
>> > On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
>> >> On 2/22/22 10:27 AM, Malcolm McLean wrote:
>> >> > Anyone got a string comparison function handy which compares strings
>> >> > intelligently by embedded numbers, so that foo2 compares earlier than
>> >> > foo11 ?
>> >> I know I have seen them. Basically as you scan the strings you need to
>> >> switch between mode. If you hit a digit in both strings you need to
>> >> collect the next set of chacters and convert them to number to compare,
>> >> and then switch back to letters after that,
>> >>
>> >> The thing you need to decide is how do you want to handle things like:
>> >>
>> >>
>> >> a02b and a2b, are they the same? or which comes first?
>> >>
>> >> Means you may need to keep track of how long the string was too.
>> >>
>> >> Presumably you are only wanting to process the normal ASCII digits or
>> >> you get into all sorts of other complexities.
>> >>
>> > The customers are international so they might use non-ascii digits, but
>> > I don't think we can cater for that.
>> > Profile 1.01 should come after Profile 1.001. Since some people abuse
>> > decimal points to indicate that 3.11 means "version three, minor version
>> > eleven", then you can defend 3.2 coming either after or before 3.11. The
>> > system has no way of knowing which convention is in use.
>> Given
>> Profile1
>> Profile2
>> where would you place
>> Profile01
>> ?
>> How about
>> Profile001
>
> I'd say that leading zeroes place you before in the sorting order.
> Thus
> Profile001
> Profile01
> Profile1
> Profile2
>
> Profile0 would place before Profile001.

I'd say that 001 compares equal to 1, and so Profile001 and Profile1 are
considered equivalent keys.

Either numbers are semantic, or else they are not. The users should
make up their mind and follow a numbering scheme accordingly.

Or else, if they want stable order under both lexicographic and
semantic, they should consistently use leading digits: 0001 0002 0003.

If these requirements are not suitable, that doesn't mean that
alternative requirements have to be shoehorned into the comparison
function, because comparison functions can be chained together, such
that if one comparison function reports equal, the next one is then
tried to resolve the tie. Sequences can be also be sorted by more than
one key, using a stable sort: sort it one way to put Profile001 ahead of
Profile01, and then use a stable sort over a comparison function with
embedded number semantics.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Richard Damon <Richard@Damon-Family.org> writes:

> On 2/22/22 10:27 AM, Malcolm McLean wrote:
>
>> Anyone got a string comparison function handy which compares strings
>> intelligently by embedded numbers, so that foo2 compares earlier than
>> foo11 ?
>
> I know I have seen them. Basically as you scan the strings you need to
> switch between mode. If you hit a digit in both strings you need to
> collect the next set of chacters and convert them to number to
> compare, and then switch back to letters after that,

Converting digit strings to a number is neither desirable nor
necessary. We would like to be able to handle digit strings
that have a value larger than any of the basic types can hold.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Wednesday, 23 February 2022 at 15:48:31 UTC, Lew Pitcher wrote:
>
>> On Wed, 23 Feb 2022 07:21:54 -0800, Malcolm McLean wrote:
>>
>>> On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
>>>
>>>> On 2/22/22 10:27 AM, Malcolm McLean wrote:
>>>>
>>>>> Anyone got a string comparison function handy which compares strings
>>>>> intelligently by embedded numbers, so that foo2 compares earlier than
>>>>> foo11 ?
>>>>
>>>> I know I have seen them. Basically as you scan the strings you need to
>>>> switch between mode. If you hit a digit in both strings you need to
>>>> collect the next set of chacters and convert them to number to compare,
>>>> and then switch back to letters after that,
>>>>
>>>> The thing you need to decide is how do you want to handle things like:
>>>>
>>>>
>>>> a02b and a2b, are they the same? or which comes first?
>>>>
>>>> Means you may need to keep track of how long the string was too.
>>>>
>>>> Presumably you are only wanting to process the normal ASCII digits or
>>>> you get into all sorts of other complexities.
>>>
>>> The customers are international so they might use non-ascii digits, but
>>> I don't think we can cater for that.
>>> Profile 1.01 should come after Profile 1.001. Since some people abuse
>>> decimal points to indicate that 3.11 means "version three, minor version
>>> eleven", then you can defend 3.2 coming either after or before 3.11. The
>>> system has no way of knowing which convention is in use.
>>
>> Given
>> Profile1
>> Profile2
>> where would you place
>> Profile01
>> ?
>> How about
>> Profile001
>
> I'd say that leading zeroes place you before in the sorting order.
> Thus
> Profile001
> Profile01
> Profile1
> Profile2
>
> Profile0 would place before Profile001.

The function foghorn_compare(), et al, as given below, does what
I think it is you want.

Both clang and gcc will optimize away the recursive calls. If
someone wants a version that is not facially recursive, I think
it shouldn't be too hard to synthesize one based on the function
definitions below (although I must confess I haven't tried to do
so).

(Note: I am taking an exception to my rule about not replying to
a posting from you. I hope you don't mind.)

#include <stddef.h>

typedef const char *String;

static int zero_compare( String, String );
static int nonzero_compare( String, String );
static int nonzero_prefer_p( String, String );
static int nonzero_prefer_q( String, String );

static size_t digits_length( String );
static String skip_digits( String );

static inline _Bool is_digit( unsigned );

int
foghorn_compare( String p, String q ){
return
*p == 0 && *q == 0 ? 0 :
*p == 0 ? -1 :
*q == 0 ? +1 :
is_digit(*p) && is_digit(*q) ? zero_compare( p, q ) :
is_digit(*p) ? -1 :
is_digit(*q) ? +1 :
*p+0u < *q+0u ? -1 :
*p+0u > *q+0u ? +1 :
foghorn_compare( p+1, q+1 );
}

int
zero_compare( String p, String q ){
return
*p == '0' && *q == '0' ? zero_compare( p+1, q+1 ) :
*p == '0' && is_digit( *q ) ? -1 :
*q == '0' && is_digit( *p ) ? +1 :
*q == '0' ? -1 :
*p == '0' ? +1 :
is_digit(*p) && is_digit(*q) ? nonzero_compare( p, q ) :
is_digit(*q) ? -1 :
is_digit(*p) ? +1 :
foghorn_compare( p, q );
}

int
nonzero_compare( String p, String q ){
_Bool p_not = ! is_digit( *p );
_Bool q_not = ! is_digit( *q );

return
p_not && q_not ? foghorn_compare( p, q ) :
p_not ? -1 :
q_not ? +1 :
*p < *q ? nonzero_prefer_p( p+1, q+1 ) :
*p > *q ? nonzero_prefer_q( p+1, q+1 ) :
nonzero_compare( p+1, q+1 );
}

int
nonzero_prefer_p( String p, String q ){
return digits_length( p ) <= digits_length( q ) ? -1 : +1;
}

int
nonzero_prefer_q( String p, String q ){
return digits_length( p ) >= digits_length( q ) ? +1 : -1;
}

size_t
digits_length( String s ){
return skip_digits( s ) - s;
}

String
skip_digits( String s ){
return is_digit( *s ) ? skip_digits( s+1 ) : s;
}

_Bool
is_digit( unsigned c ){
return c - '0' < 10;
}

On 2/23/22 10:21 AM, Malcolm McLean wrote:
> On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
>> On 2/22/22 10:27 AM, Malcolm McLean wrote:
>>> Anyone got a string comparison function handy which compares strings intelligently by embedded numbers, so that foo2 compares earlier than foo11 ?
>> I know I have seen them. Basically as you scan the strings you need to
>> switch between mode. If you hit a digit in both strings you need to
>> collect the next set of chacters and convert them to number to compare,
>> and then switch back to letters after that,
>>
>> The thing you need to decide is how do you want to handle things like:
>>
>>
>> a02b and a2b, are they the same? or which comes first?
>>
>> Means you may need to keep track of how long the string was too.
>>
>> Presumably you are only wanting to process the normal ASCII digits or
>> you get into all sorts of other complexities.
>>
> The customers are international so they might use non-ascii digits, but I don't think
> we can cater for that.
> Profile 1.01 should come after Profile 1.001. Since some people abuse decimal
> points to indicate that 3.11 means "version three, minor version eleven", then you
> can defend 3.2 coming either after or before 3.11. The system has no way of knowing
> which convention is in use.

Dealing with decimals says you need to treat things differently than
with just intergers.

1.51 is after 1.501 but 1 is equal to 1 and . is equal to . but 51 is
before 501, so yes, you are going to need to decide if '.' introduces a
decimal fraction or just a value separator.

IF . is a decimal point, the digits after can just be sorted lexically.
If it is a separator (like the version number case) then you get into a
new numeric sort.

On Wednesday, 23 February 2022 at 19:37:32 UTC, Tim Rentsch wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
> > On Wednesday, 23 February 2022 at 15:48:31 UTC, Lew Pitcher wrote:
> >
> >> On Wed, 23 Feb 2022 07:21:54 -0800, Malcolm McLean wrote:
> >>
> >>> On Wednesday, 23 February 2022 at 04:21:18 UTC, Richard Damon wrote:
> >>>
> >>>> On 2/22/22 10:27 AM, Malcolm McLean wrote:
> >>>>
> >>>>> Anyone got a string comparison function handy which compares strings
> >>>>> intelligently by embedded numbers, so that foo2 compares earlier than
> >>>>> foo11 ?
> >>>>
> >>>> I know I have seen them. Basically as you scan the strings you need to
> >>>> switch between mode. If you hit a digit in both strings you need to
> >>>> collect the next set of chacters and convert them to number to compare,
> >>>> and then switch back to letters after that,
> >>>>
> >>>> The thing you need to decide is how do you want to handle things like:
> >>>>
> >>>>
> >>>> a02b and a2b, are they the same? or which comes first?
> >>>>
> >>>> Means you may need to keep track of how long the string was too.
> >>>>
> >>>> Presumably you are only wanting to process the normal ASCII digits or
> >>>> you get into all sorts of other complexities.
> >>>
> >>> The customers are international so they might use non-ascii digits, but
> >>> I don't think we can cater for that.
> >>> Profile 1.01 should come after Profile 1.001. Since some people abuse
> >>> decimal points to indicate that 3.11 means "version three, minor version
> >>> eleven", then you can defend 3.2 coming either after or before 3.11. The
> >>> system has no way of knowing which convention is in use.
> >>
> >> Given
> >> Profile1
> >> Profile2
> >> where would you place
> >> Profile01
> >> ?
> >> How about
> >> Profile001
> >
> > I'd say that leading zeroes place you before in the sorting order.
> > Thus
> > Profile001
> > Profile01
> > Profile1
> > Profile2
> >
> > Profile0 would place before Profile001.
> The function foghorn_compare(), et al, as given below, does what
> I think it is you want.
>
Thanks to everyone who contributed, especially TIm.

Initially I used the code posted by Eric Sosman. But it turned out that it wasn't acceptable.
The problem was that the main program already has a Unicode comparison function
built in, which doesn't handle non-alnum glyphs in any simple way. It's also dependent on
the language the user chooses. We don't have access to the source.
So instead of comparing two UTF-8 character pointers in a C function, I had to move to
C++.

So this is what I did. Firstly, I wrote a function which scans a string for embedded numbers
at equal positions. If it finds a number pair that differ, it returns +1/-1. Otherwise it returns
zero. If the embedded number function returns zero, I call the main program comparison
function. The embedded numbers function is a static, it's got too quirky an interface to
expose it.
We also wanted a case-insensitive compare. So I called the main program toLower.
There's quite a lot of messing about converting between the main program Unicode format,
UTF-8, and back. This seems to be the way with Unicode. CompareUTF8StringCaseInsensitive
is a trivial wrapper I wrote to the main program compare, which works on ai::UnicodeStrings.

static inline int nat_isdigit(char a)
{ return isdigit((unsigned char)a);
}

static inline char nat_toupper(char a)
{ return toupper((unsigned char)a);
} static int compare_right(char const* a, char const* b)
{ int bias = 0;

/* The longest run of digits wins. That aside, the greatest
value wins, but we can't know that it will until we've scanned
both numbers to know that they have the same magnitude, so we
remember it in BIAS. */
for (;; a++, b++) {
if (!nat_isdigit(*a) && !nat_isdigit(*b))
return bias;
if (!nat_isdigit(*a))
return -1;
if (!nat_isdigit(*b))
return +1;
if (*a < *b) {
if (!bias)
bias = -1;
}
else if (*a > *b) {
if (!bias)
bias = +1;
}
else if (!*a && !*b)
return bias;
}

return 0;
}

static int compare_left(char const* a, char const* b)
{ /* Compare two left-aligned numbers: the first to have a
different value wins. */
for (;; a++, b++) {
if (!nat_isdigit(*a) && !nat_isdigit(*b))
return 0;
if (!nat_isdigit(*a))
return -1;
if (!nat_isdigit(*b))
return +1;
if (*a < *b)
return -1;
if (*a > *b)
return +1;
}

return 0;
}

static int numbercompare(const char* a, const char* b)
{ if (*a == 0 || *b == 0)
return 0;
if (nat_isdigit(*a) && nat_isdigit(*b))
{
int comp;

if (*a == '0' || *b == '0')
{
comp = compare_left(a, b);
}
else
{
comp = compare_right(a, b);
}
if (comp != 0)
return comp;
}
if (*a != *b)
return 0;
return numbercompare(a + 1, b + 1);
}

bool CompareProfileNames(std::string const& namea, std::string const& nameb)
{ ai::UnicodeString a = ai::UnicodeString::FromUTF8(namea);
ai::UnicodeString b = ai::UnicodeString::FromUTF8(nameb);
a.toUpper();
b.toUpper();
std::string autf8 = a.as_UTF8();
std::string butf8 = b.as_UTF8();

int numbercomp = numbercompare(autf8.c_str(), butf8.c_str());
if (numbercomp != 0)
return numbercomp < 0;
return CompareUTF8StringCaseInsensitive(namea, nameb);
}