Celestia

1
// This file is based on strnatcmp.c by Martin Pool
2
// Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net>
3
// Adaptations
4
// Copyright (C) 2020, the Celestia Development Team
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
#include "strnatcmp.h"
24

25
#include <cwctype>
26
#include <optional>
27

28
#include <celutil/utf8.h>
29

30

31
namespace
32
{
33

34
using MaybeChar = std::optional<std::int32_t>;
35

36

37
inline bool
38
isDigit(MaybeChar c)
39
{
40
    return c.has_value() &&
41
           c >= 0 && c <= WCHAR_MAX &&
42
           std::iswdigit(static_cast<std::wint_t>(*c));
43
}
44

45
inline bool isSpace(MaybeChar c)
46
{
47
    return c.has_value() &&
48
           c >= 0 && c<= WCHAR_MAX &&
49
           std::iswspace(*c);
50
}
51

52

53
class CharMapper
54
{
55
public:
56
    explicit CharMapper(std::string_view _sv) : sv(_sv) {}
57

58
    MaybeChar next()
59
    {
60
        auto svSize = static_cast<std::int32_t>(sv.size());
61
        if (offset >= svSize)
62
            return std::nullopt;
63

64
        std::int32_t ch;
65
        if (!UTF8Decode(sv, offset, ch))
66
        {
67
            offset = svSize;
68
            return std::nullopt;
69
        }
70

71
        return ch;
72
    }
73

74
private:
75
    std::string_view sv;
76
    std::int32_t offset{ 0 };
77
};
78

79

80
int
81
right(CharMapper& a, MaybeChar& ca, CharMapper& b, MaybeChar& cb)
82
{
83
    int bias = 0;
84

85
    // The longest run of digits wins.  That aside, the greatest value
86
    // wins, but we can't know that it will until we've scanned both
87
    // numbers to know that they have the same magnitude, so we remember
88
    // it in BIAS.
89
    for (;;)
90
    {
91
        if (!isDigit(ca))
92
            return isDigit(cb) ? -1 : bias;
93
        if (!isDigit(cb))
94
            return +1;
95

96
        if (bias == 0)
97
        {
98
            if (*ca < *cb)
99
                bias = -1;
100
            else if (*ca > *cb)
101
                bias = 1;
102
        }
103

104
        ca = a.next();
105
        cb = b.next();
106
    }
107
}
108

109

110
int
111
left(CharMapper& a, MaybeChar& ca, CharMapper& b, MaybeChar& cb)
112
{
113
    // Compare two left-aligned numbers: the first to have a
114
    // different value wins.
115
    for (;;)
116
    {
117
        if (!isDigit(ca))
118
           return isDigit(cb) ? -1 : 0;
119
        if (!isDigit(cb))
120
            return 1;
121
        if (*ca < *cb)
122
            return -1;
123
        if (*ca > *cb)
124
            return 1;
125

126
        ca = a.next();
127
        cb = b.next();
128
    }
129
}
130

131
int
132
strnatcmp0(CharMapper& a, CharMapper& b)
133
{
134
    // skip over leading space
135
    MaybeChar ca = a.next();
136
    while (isSpace(ca))
137
        ca = a.next();
138

139
    MaybeChar cb = b.next();
140
    while (isSpace(cb))
141
        cb = b.next();
142

143
    for (;;)
144
    {
145
        if (!ca.has_value())
146
            return cb.has_value() ? -1 : 0;
147
        if (!cb.has_value())
148
            return 1;
149

150
        // process run of digits
151
        if (std::iswdigit(*ca) && std::iswdigit(*cb))
152
        {
153
            int r = (*ca == L'0' || *cb == L'0')
154
                ? left(a, ca, b, cb)
155
                : right(a, ca, b, cb);
156
            if (r != 0)
157
                return r;
158
            continue;
159
        }
160

161
        if (*ca < *cb)
162
            return -1;
163

164
        if (*ca > *cb)
165
            return 1;
166

167
        ca = a.next();
168
        cb = b.next();
169
    }
170
}
171

172
} // end unnamed namespace
173

174

175
int
176
strnatcmp(std::string_view a, std::string_view b)
177
{
178
    CharMapper aMapper{a};
179
    CharMapper bMapper{b};
180
    return strnatcmp0(aMapper, bMapper);
181
}
182