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