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
20namespace BPrivate {
21
22
23// #pragma mark - Natural sorting
24
25
26struct 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
38inline int32
39FetchNaturalChunk(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
80int
81NaturalCompare(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