1 /*
2 * Copyright 2009, Dana Burkart
3 * Copyright 2009, Stephan Aßmus <superstippi@gmx.de>
4 * Copyright 2010, Axel Dörfler, axeld@pinc-software.de
5 * Copyright 2010, Rene Gollent (anevilyak@gmail.com)
6 * Distributed under the terms of the MIT License.
7 */
8
9
10 #include <NaturalCompare.h>
11
12 #include <ctype.h>
13 #include <string.h>
14 #include <strings.h>
15
16 #include <StorageDefs.h>
17 #include <SupportDefs.h>
18
19
20 namespace BPrivate {
21
22
23 // #pragma mark - Natural sorting
24
25
26 struct natural_chunk {
27 enum chunk_type {
28 NUMBER,
29 ASCII,
30 END
31 };
32 chunk_type type;
33 char buffer[B_FILE_NAME_LENGTH];
34 int32 length;
35 };
36
37
38 inline int32
FetchNaturalChunk(natural_chunk & chunk,const char * source)39 FetchNaturalChunk(natural_chunk& chunk, const char* source)
40 {
41 if (chunk.type == natural_chunk::ASCII) {
42 // string chunk
43 int32 pos = 0;
44 while (!isdigit(source[pos]) && !isspace(source[pos])
45 && source[pos] != '\0') {
46 pos++;
47 }
48 strlcpy(chunk.buffer, source, pos + 1);
49 chunk.length = pos;
50 return pos;
51 }
52
53 // Skip leading zeros and whitespace characters
54 int32 skip = 0;
55 while (source[0] == '0' || isspace(source[0])) {
56 source++;
57 skip++;
58 }
59
60 // Number chunk (stop at next white space)
61 int32 pos = 0;
62 while (isdigit(source[pos])) {
63 pos++;
64 }
65
66 strlcpy(chunk.buffer, source, pos + 1);
67 chunk.length = pos;
68
69 // Skip trailing whitespace as well
70 while (isspace(source[pos])) {
71 source++;
72 skip++;
73 }
74
75 return pos + skip;
76 }
77
78
79 //! Compares two strings naturally, as opposed to lexicographically
80 int
NaturalCompare(const char * stringA,const char * stringB)81 NaturalCompare(const char* stringA, const char* stringB)
82 {
83 if (stringA == NULL)
84 return stringB == NULL ? 0 : -1;
85 if (stringB == NULL)
86 return 1;
87
88 natural_chunk a;
89 natural_chunk b;
90
91 uint32 indexA = 0;
92 uint32 indexB = 0;
93
94 while (true) {
95 // Determine type of next chunks in each string based on first char
96 if (stringA[indexA] == '\0')
97 a.type = natural_chunk::END;
98 else if (isdigit(stringA[indexA]) || isspace(stringA[indexA]))
99 a.type = natural_chunk::NUMBER;
100 else
101 a.type = natural_chunk::ASCII;
102
103 if (stringB[indexB] == '\0')
104 b.type = natural_chunk::END;
105 else if (isdigit(stringB[indexB]) || isspace(stringB[indexB]))
106 b.type = natural_chunk::NUMBER;
107 else
108 b.type = natural_chunk::ASCII;
109
110 // Check if we reached the end of either string
111 if (a.type == natural_chunk::END)
112 return b.type == natural_chunk::END ? 0 : -1;
113 if (b.type == natural_chunk::END)
114 return 1;
115
116 if (a.type != b.type) {
117 // Different chunk types, just compare the remaining strings
118 return strcasecmp(&stringA[indexA], &stringB[indexB]);
119 }
120
121 // Fetch the next chunks
122 indexA += FetchNaturalChunk(a, &stringA[indexA]);
123 indexB += FetchNaturalChunk(b, &stringB[indexB]);
124
125 // Compare the two chunks based on their type
126 if (a.type == natural_chunk::ASCII) {
127 // String chunks
128 int result = strcasecmp(a.buffer, b.buffer);
129 if (result != 0)
130 return result;
131 } else {
132 // Number chunks - they are compared as strings to allow an
133 // almost arbitrary number of digits.
134 if (a.length > b.length)
135 return 1;
136 if (a.length < b.length)
137 return -1;
138
139 int result = strcmp(a.buffer, b.buffer);
140 if (result != 0)
141 return result;
142 }
143
144 // The chunks were equal, proceed with the next chunk
145 }
146
147 return 0;
148 }
149
150
151 } // namespace BPrivate
152