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 /* These are defined as macros to make it easier to adapt this code to
  47 * different characters types or comparison functions. */
  48 static inline int nat_isdigit(MUtils::Internal::NaturalSort::nat_char a)
  49 {
  50         return iswdigit(a);
  51 }
  52
  53 static inline int nat_isspace(MUtils::Internal::NaturalSort::nat_char a)
  54 {
  55         return iswspace(a);
  56 }
  57
  58 static inline MUtils::Internal::NaturalSort::nat_char nat_isdecpoint(MUtils::Internal::NaturalSort::nat_char a)
  59 {
  60         return (a == L'.') || (a == L',');
  61 }
  62
  63 static inline MUtils::Internal::NaturalSort::nat_char nat_toupper(MUtils::Internal::NaturalSort::nat_char a)
  64 {
  65         return towupper(a);
  66 }
  67
  68 static int compare_right(MUtils::Internal::NaturalSort::nat_char const *a, MUtils::Internal::NaturalSort::nat_char const *b)
  69 {
  70         int bias = 0;
  71
  72         /* The longest run of digits wins.  That aside, the greatest
  73         value wins, but we can't know that it will until we've scanned
  74         both numbers to know that they have the same magnitude, so we
  75         remember it in BIAS. */
  76         for (;; a++, b++)
  77         {
  78                 if (!nat_isdigit(*a) && !nat_isdigit(*b))
  79                         return bias;
  80                 else if (!nat_isdigit(*a))
  81                         return -1;
  82                 else if (!nat_isdigit(*b))
  83                         return +1;
  84                 else if (*a < *b)
  85                 {
  86                         if (!bias)
  87                                 bias = -1;
  88                 }
  89                 else if (*a > *b)
  90                 {
  91                         if (!bias)
  92                                 bias = +1;
  93                 }
  94                 else if (!*a && !*b)
  95                         return bias;
  96         }
  97
  98         return 0;
  99 }
 100
 101 static int compare_left(MUtils::Internal::NaturalSort::nat_char const *a, MUtils::Internal::NaturalSort::nat_char const *b)
 102 {
 103         /* Compare two left-aligned numbers: the first to have a
 104         different value wins. */
 105         for (;; a++, b++)
 106         {
 107                 if (!nat_isdigit(*a) && !nat_isdigit(*b))
 108                         return 0;
 109                 else if (!nat_isdigit(*a))
 110                         return -1;
 111                 else if (!nat_isdigit(*b))
 112                         return +1;
 113                 else if (*a < *b)
 114                         return -1;
 115                 else if (*a > *b)
 116                         return +1;
 117         }
 118
 119         return 0;
 120 }
 121
 122 static int strnatcmp0(MUtils::Internal::NaturalSort::nat_char const *a, MUtils::Internal::NaturalSort::nat_char const *b, const bool fold_case)
 123 {
 124         int ai, bi;
 125         MUtils::Internal::NaturalSort::nat_char ca, cb;
 126         int result;
 127         bool fractional;
 128         int sa, sb;
 129
 130         assert(a && b);
 131         ai = bi = 0;
 132         fractional = false;
 133
 134         while (1)
 135         {
 136                 ca = a[ai]; cb = b[bi];
 137
 138                 /* skip over leading spaces or zeros */
 139                 while (nat_isspace(ca))
 140                         ca = a[++ai];
 141
 142                 while (nat_isspace(cb))
 143                         cb = b[++bi];
 144
 145                 /* process run of digits */
 146                 if (nat_isdigit(ca) && nat_isdigit(cb))
 147                 {
 148                         sa = sb = 0;
 149
 150                         if(!fractional)
 151                         {
 152                                 while (ca == L'0')
 153                                 {
 154                                         ca = a[++ai]; sa++;
 155                                 }
 156                                 while (cb == L'0')
 157                                 {
 158                                         cb = b[++bi]; sb++;
 159                                 }
 160                         }
 161
 162                         if (fractional)
 163                         {
 164                                 if ((result = compare_left(a+ai, b+bi)) != 0)
 165                                         return result;
 166                         }
 167                         else
 168                         {
 169                                 if ((result = compare_right(a+ai, b+bi)) != 0)
 170                                         return result;
 171                         }
 172
 173                         /* on tie, the string with the longer leading zero's sequence wins */
 174                         if(sa < sb)
 175                                 return -1;
 176                         else if(sa > sb)
 177                                 return +1;
 178                 }
 179
 180                 if (!ca && !cb)
 181                 {
 182                         /* The strings compare the same.  Perhaps the caller
 183                         will want to call strcmp to break the tie. */
 184                         return (fold_case) ? _wcsicmp(a, b) : wcscmp(a, b);
 185                 }
 186
 187                 if (fold_case)
 188                 {
 189                         ca = nat_toupper(ca);
 190                         cb = nat_toupper(cb);
 191                 }
 192
 193                 if (ca < cb)
 194                         return -1;
 195                 else if (ca > cb)
 196                         return +1;
 197
 198                 /* skipp leading zero's, unless previously seen char was a decimal point */
 199                 fractional = nat_isdecpoint(ca) && nat_isdecpoint(cb);
 200
 201                 ++ai; ++bi;
 202         }
 203 }
 204
 205 int MUtils::Internal::NaturalSort::strnatcmp(nat_char const *a, nat_char const *b)
 206 {
 207         return strnatcmp0(a, b, false);
 208 }
 209
 210 /* Compare, recognizing numeric string and ignoring case. */
 211 int MUtils::Internal::NaturalSort::strnatcasecmp(nat_char const *a, nat_char const *b)
 212 {
 213         return strnatcmp0(a, b, true);
 214 }