xref: /haiku/src/build/libshared/NaturalCompare.cpp (revision 3ec770177938efc5a7fee54d03b45fa593a57988)

/*
 * Copyright 2009, Dana Burkart
 * Copyright 2009, Stephan Aßmus <superstippi@gmx.de>
 * Copyright 2010, Axel Dörfler, axeld@pinc-software.de
 * Copyright 2010, Rene Gollent (anevilyak@gmail.com)
 * Distributed under the terms of the MIT License.
 */


#include <NaturalCompare.h>

#include <ctype.h>
#include <string.h>
#include <strings.h>

#include <StorageDefs.h>
#include <SupportDefs.h>


namespace BPrivate {


// #pragma mark - Natural sorting


struct natural_chunk {
	enum chunk_type {
		NUMBER,
		ASCII,
		END
	};
	chunk_type	type;
	char		buffer[B_FILE_NAME_LENGTH];
	int32		length;
};


inline int32
FetchNaturalChunk(natural_chunk& chunk, const char* source)
{
	if (chunk.type == natural_chunk::ASCII) {
		// string chunk
		int32 pos = 0;
		while (!isdigit(source[pos]) && !isspace(source[pos])
			&& source[pos] != '\0') {
			pos++;
		}
		strlcpy(chunk.buffer, source, pos + 1);
		chunk.length = pos;
		return pos;
	}

	// Skip leading zeros and whitespace characters
	int32 skip = 0;
	while (source[0] == '0' || isspace(source[0])) {
		source++;
		skip++;
	}

	// Number chunk (stop at next white space)
	int32 pos = 0;
	while (isdigit(source[pos])) {
		pos++;
	}

	strlcpy(chunk.buffer, source, pos + 1);
	chunk.length = pos;

	// Skip trailing whitespace as well
	while (isspace(source[pos])) {
		source++;
		skip++;
	}

	return pos + skip;
}


//! Compares two strings naturally, as opposed to lexicographically
int
NaturalCompare(const char* stringA, const char* stringB)
{
	if (stringA == NULL)
		return stringB == NULL ? 0 : -1;
	if (stringB == NULL)
		return 1;

	natural_chunk a;
	natural_chunk b;

	uint32 indexA = 0;
	uint32 indexB = 0;

	while (true) {
		// Determine type of next chunks in each string based on first char
		if (stringA[indexA] == '\0')
			a.type = natural_chunk::END;
		else if (isdigit(stringA[indexA]) || isspace(stringA[indexA]))
			a.type = natural_chunk::NUMBER;
		else
			a.type = natural_chunk::ASCII;

		if (stringB[indexB] == '\0')
			b.type = natural_chunk::END;
		else if (isdigit(stringB[indexB]) || isspace(stringB[indexB]))
			b.type = natural_chunk::NUMBER;
		else
			b.type = natural_chunk::ASCII;

		// Check if we reached the end of either string
		if (a.type == natural_chunk::END)
			return b.type == natural_chunk::END ? 0 : -1;
		if (b.type == natural_chunk::END)
			return 1;

		if (a.type != b.type) {
			// Different chunk types, just compare the remaining strings
			return strcasecmp(&stringA[indexA], &stringB[indexB]);
		}

		// Fetch the next chunks
		indexA += FetchNaturalChunk(a, &stringA[indexA]);
		indexB += FetchNaturalChunk(b, &stringB[indexB]);

		// Compare the two chunks based on their type
		if (a.type == natural_chunk::ASCII) {
			// String chunks
			int result = strcasecmp(a.buffer, b.buffer);
			if (result != 0)
				return result;
		} else {
			// Number chunks - they are compared as strings to allow an
			// almost arbitrary number of digits.
			if (a.length > b.length)
				return 1;
			if (a.length < b.length)
				return -1;

			int result = strcmp(a.buffer, b.buffer);
			if (result != 0)
				return result;
		}

		// The chunks were equal, proceed with the next chunk
	}

	return 0;
}


} // namespace BPrivate