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 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 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