src/3rd_party/strnatcmp/src/strnatcmp.cpp

   1 /* -*- mode: c; c-file-style: "k&r" -*-
   2
   3 strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
   4 Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net>
   5
   6 This software is provided 'as-is', without any express or implied
   7 warranty.  In no event will the authors be held liable for any damages
   8 arising from the use of this software.
   9
  10 Permission is granted to anyone to use this software for any purpose,
  11 including commercial applications, and to alter it and redistribute it
  12 freely, subject to the following restrictions:
  13
  14 1. The origin of this software must not be misrepresented; you must not
  15 claim that you wrote the original software. If you use this software
  16 in a product, an acknowledgment in the product documentation would be
  17 appreciated but is not required.
  18 2. Altered source versions must be plainly marked as such, and must not be
  19 misrepresented as being the original software.
  20 3. This notice may not be removed or altered from any source distribution.
  21 */
  22
  23
  24 /* partial change history:
  25 *
  26 * 2004-10-10 mbp: Lift out character type dependencies into macros.
  27 *
  28 * Eric Sosman pointed out that ctype functions take a parameter whose
  29 * value must be that of an unsigned int, even on platforms that have
  30 * negative chars in their default char type.
  31 */
  32
  33 /*
  34 * 2013-08-23: Skip leading zero's for any run of digits, except
  35 *             when a decimal point was seen immediatley before.
  36 *             Patch by LoRd_MuldeR <mulder2@gmx.de>
  37 */
  38
  39 #include <ctype.h>
  40 #include <string.h>
  41 #include <assert.h>
  42 #include <stdio.h>
  43
  44 #include "../include/strnatcmp.h"
  45
  46 typedef MUtils::Internal::NaturalSort::nat_char nat_char;
  47
  48 /* These are defined as macros to make it easier to adapt this code to
  49 * different characters types or comparison functions. */
  50 static inline int nat_isdigit(nat_char a)
  51 {
  52         return iswdigit(a);
  53 }
  54
  55 static inline int nat_isspace(nat_char a)
  56 {
  57         return iswspace(a);
  58 }
  59
  60 static inline nat_char nat_isdecpoint(nat_char a)
  61 {
  62         return (a == L'.') || (a == L',');
  63 }
  64
  65 static inline nat_char nat_toupper(nat_char a)
  66 {
  67         return towupper(a);
  68 }
  69
  70 static int compare_right(nat_char const *a, nat_char const *b)
  71 {
  72         int bias = 0;
  73
  74         /* The longest run of digits wins.  That aside, the greatest
  75         value wins, but we can't know that it will until we've scanned
  76         both numbers to know that they have the same magnitude, so we
  77         remember it in BIAS. */
  78         for (;; a++, b++)
  79         {
  80                 if (!nat_isdigit(*a) && !nat_isdigit(*b))
  81                         return bias;
  82                 else if (!nat_isdigit(*a))
  83                         return -1;
  84                 else if (!nat_isdigit(*b))
  85                         return +1;
  86                 else if (*a < *b)
  87                 {
  88                         if (!bias)
  89                                 bias = -1;
  90                 }
  91                 else if (*a > *b)
  92                 {
  93                         if (!bias)
  94                                 bias = +1;
  95                 }
  96                 else if (!*a && !*b)
  97                         return bias;
  98         }
  99
 100         // return 0;
 101 }
 102
 103 static int compare_left(nat_char const *a, nat_char const *b)
 104 {
 105         /* Compare two left-aligned numbers: the first to have a
 106         different value wins. */
 107         for (;; a++, b++)
 108         {
 109                 if (!nat_isdigit(*a) && !nat_isdigit(*b))
 110                         return 0;
 111                 else if (!nat_isdigit(*a))
 112                         return -1;
 113                 else if (!nat_isdigit(*b))
 114                         return +1;
 115                 else if (*a < *b)
 116                         return -1;
 117                 else if (*a > *b)
 118                         return +1;
 119         }
 120
 121         // return 0;
 122 }
 123
 124 static int strnatcmp0(nat_char const *a, nat_char const *b, const bool fold_case)
 125 {
 126         int ai, bi;
 127         nat_char ca, cb;
 128         int result;
 129         bool fractional;
 130         int sa, sb;
 131
 132         assert(a && b);
 133         ai = bi = 0;
 134         fractional = false;
 135
 136         while (1)
 137         {
 138                 ca = a[ai]; cb = b[bi];
 139
 140                 /* skip over leading spaces or zeros */
 141                 while (nat_isspace(ca))
 142                         ca = a[++ai];
 143
 144                 while (nat_isspace(cb))
 145                         cb = b[++bi];
 146
 147                 /* process run of digits */
 148                 if (nat_isdigit(ca) && nat_isdigit(cb))
 149                 {
 150                         sa = sb = 0;
 151
 152                         if(!fractional)
 153                         {
 154                                 while (ca == L'0')
 155                                 {
 156                                         ca = a[++ai]; sa++;
 157                                 }
 158                                 while (cb == L'0')
 159                                 {
 160                                         cb = b[++bi]; sb++;
 161                                 }
 162                         }
 163
 164                         if (fractional)
 165                         {
 166                                 if ((result = compare_left(a+ai, b+bi)) != 0)
 167                                         return result;
 168                         }
 169                         else
 170                         {
 171                                 if ((result = compare_right(a+ai, b+bi)) != 0)
 172                                         return result;
 173                         }
 174
 175                         /* on tie, the string with the longer leading zero's sequence wins */
 176                         if(sa < sb)
 177                                 return -1;
 178                         else if(sa > sb)
 179                                 return +1;
 180                 }
 181
 182                 if (!ca && !cb)
 183                 {
 184                         /* The strings compare the same.  Perhaps the caller
 185                         will want to call strcmp to break the tie. */
 186                         return (fold_case) ? _wcsicmp(a, b) : wcscmp(a, b);
 187                 }
 188
 189                 if (fold_case)
 190                 {
 191                         ca = nat_toupper(ca);
 192                         cb = nat_toupper(cb);
 193                 }
 194
 195                 if (ca < cb)
 196                         return -1;
 197                 else if (ca > cb)
 198                         return +1;
 199
 200                 /* skipp leading zero's, unless previously seen char was a decimal point */
 201                 fractional = nat_isdecpoint(ca) && nat_isdecpoint(cb);
 202
 203                 ++ai; ++bi;
 204         }
 205 }
 206
 207 int MUtils::Internal::NaturalSort::strnatcmp(nat_char const *a, nat_char const *b)
 208 {
 209         return strnatcmp0(a, b, false);
 210 }
 211
 212 /* Compare, recognizing numeric string and ignoring case. */
 213 int MUtils::Internal::NaturalSort::strnatcasecmp(nat_char const *a, nat_char const *b)
 214 {
 215         return strnatcmp0(a, b, true);
 216 }