pv/strnatcmp.hpp

   1 /*
   2  * This file is part of the PulseView project.
   3  *
   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 // strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
  24 // This file has been modified for C++ compatibility.
  25 // Original at https://github.com/sourcefrog/natsort/blob/master/strnatcmp.c
  26
  27 #ifndef PULSEVIEW_PV_STRNATCMP_HPP
  28 #define PULSEVIEW_PV_STRNATCMP_HPP
  29
  30 #include <stddef.h>     /* size_t */
  31 #include <ctype.h>
  32 #include <string>
  33
  34 using std::string;
  35
  36 static int compare_right(char const *a, char const *b)
  37 {
  38         int bias = 0;
  39
  40         // The longest run of digits wins. That aside, the greatest
  41         // value wins, but we can't know that it will until we've scanned
  42         // both numbers to know that they have the same magnitude, so we
  43         // remember it in bias.
  44         for (;; a++, b++) {
  45                 if (!isdigit(*a) && !isdigit(*b))
  46                         return bias;
  47                 if (!isdigit(*a))
  48                         return -1;
  49                 if (!isdigit(*b))
  50                         return +1;
  51
  52                 if (*a < *b) {
  53                         if (!bias)
  54                                 bias = -1;
  55                 } else if (*a > *b) {
  56                         if (!bias)
  57                                 bias = +1;
  58                 } else if (!*a && !*b)
  59                         return bias;
  60         }
  61
  62         return 0;
  63 }
  64
  65 static int compare_left(char const *a, char const *b)
  66 {
  67         // Compare two left-aligned numbers: the first to have a
  68         // different value wins.
  69         for (;; a++, b++) {
  70                 if (!isdigit(*a)  &&  !isdigit(*b))
  71                         return 0;
  72                 if (!isdigit(*a))
  73                         return -1;
  74                 if (!isdigit(*b))
  75                         return +1;
  76                 if (*a < *b)
  77                         return -1;
  78                 if (*a > *b)
  79                         return +1;
  80         }
  81
  82         return 0;
  83 }
  84
  85 static int strnatcmp0(char const *a, char const *b, int fold_case)
  86 {
  87         int ai, bi, fractional, result;
  88         char ca, cb;
  89
  90         ai = bi = 0;
  91
  92         while (1) {
  93                 ca = a[ai];
  94                 cb = b[bi];
  95
  96                 // Skip over leading spaces or zeroes
  97                 while (isspace(ca))
  98                         ca = a[++ai];
  99
 100                 while (isspace(cb))
 101                         cb = b[++bi];
 102
 103                 // Process run of digits
 104                 if (isdigit(ca) && isdigit(cb)) {
 105                         fractional = (ca == '0' || cb == '0');
 106
 107                         if (fractional) {
 108                                 if ((result = compare_left(a + ai, b + bi)) != 0)
 109                                         return result;
 110                         } else {
 111                                 if ((result = compare_right(a + ai, b + bi)) != 0)
 112                                         return result;
 113                         }
 114                 }
 115
 116                 if (!ca && !cb) {
 117                         // The strings compare the same. Perhaps the caller
 118                         // will want to call strcmp to break the tie
 119                         return 0;
 120                 }
 121
 122                 if (fold_case) {
 123                         ca = toupper(ca);
 124                         cb = toupper(cb);
 125                 }
 126
 127                 if (ca < cb)
 128                         return -1;
 129
 130                 if (ca > cb)
 131                         return +1;
 132
 133                 ++ai;
 134                 ++bi;
 135         }
 136 }
 137
 138 // Compare, recognizing numeric strings and being case sensitive
 139 int strnatcmp(char const *a, char const *b)
 140 {
 141         return strnatcmp0(a, b, 0);
 142 }
 143
 144 int strnatcmp(const string a, const string b)
 145 {
 146         return strnatcmp0(a.c_str(), b.c_str(), 0);
 147 }
 148
 149 // Compare, recognizing numeric strings and ignoring case
 150 int strnatcasecmp(char const *a, char const *b)
 151 {
 152         return strnatcmp0(a, b, 1);
 153 }
 154
 155 int strnatcasecmp(const string a, const string b)
 156 {
 157         return strnatcmp0(a.c_str(), b.c_str(), 1);
 158 }
 159
 160 #endif // PULSEVIEW_PV_STRNATCMP_HPP