1 module natcmp; 2 3 nothrow @safe: 4 enum compareMode { Undefined, String, Integer }; ///Marks the chunk type 5 /** 6 * A chunk of text, representing either a string of numbers or a string of other characters. 7 * Do not use. 8 * Authors: Cameron "Herringway" Ross 9 */ 10 private struct naturalCompareChunk { 11 nothrow @safe pure: 12 public string str; 13 public compareMode mode = compareMode.Undefined; 14 /** 15 * Compares two chunks. 16 * Integers are assumed to come before non-integers. 17 * Returns: 0 on failure, [-1,1] on success 18 */ 19 public int opCmp(ref const naturalCompareChunk b) in { 20 import std.uni : isNumber; 21 assert(this.mode != compareMode.Undefined, "Undefined chunk type (A)"); 22 assert( b.mode != compareMode.Undefined, "Undefined chunk type (B)"); 23 foreach (character; str) { 24 if (this.mode == compareMode.Integer) 25 assert(character.isNumber(), "Non-numeric value found in number string"); 26 else 27 assert(!character.isNumber(), "Numeric value found in non-numeric string"); 28 } 29 } out(result) { 30 assert(result <= 1, "Result too large"); 31 assert(result >= -1, "Result too small"); 32 } body { 33 import std.algorithm : min, max; 34 import std.conv : to; 35 import std.uni : icmp; 36 try { 37 if ((this.mode == compareMode.Integer) && (b.mode == compareMode.String)) { 38 return -1; 39 } else if ((this.mode == compareMode.String) && (b.mode == compareMode.Integer)) { 40 return 1; 41 } else if (this.mode == compareMode.String) { 42 return min(1, max(-1, icmp(this.str, b.str))); 43 } else if (this.mode == compareMode.Integer) { 44 auto int1 = to!long(this.str); 45 auto int2 = to!long(b.str); 46 if (int1 == int2) 47 return min(1, max(-1, icmp(this.str, b.str))); 48 return cast(int)max(-1,min(1,int1-int2)); 49 } 50 } catch (Exception) { 51 return 0; 52 } 53 assert(false); 54 } 55 } 56 unittest { 57 naturalCompareChunk chunkA; 58 naturalCompareChunk chunkB; 59 chunkA = naturalCompareChunk("a", compareMode.String); 60 chunkB = naturalCompareChunk("a", compareMode.String); 61 assertEqual(chunkA.opCmp(chunkB), 0, "Equal chunks tested as inequal"); 62 chunkA = naturalCompareChunk("a", compareMode.String); 63 chunkB = naturalCompareChunk("b", compareMode.String); 64 assert(chunkA < chunkB, "a > b"); 65 chunkA = naturalCompareChunk("b", compareMode.String); 66 chunkB = naturalCompareChunk("a", compareMode.String); 67 assert(chunkA > chunkB, "b < a"); 68 chunkA = naturalCompareChunk("1", compareMode.Integer); 69 chunkB = naturalCompareChunk("a", compareMode.String); 70 assert(chunkA < chunkB, "1 > a"); 71 chunkA = naturalCompareChunk("a", compareMode.String); 72 chunkB = naturalCompareChunk("1", compareMode.Integer); 73 assert(chunkA > chunkB, "a < 1"); 74 chunkA = naturalCompareChunk("1", compareMode.Integer); 75 chunkB = naturalCompareChunk("2", compareMode.Integer); 76 assert(chunkA < chunkB, "1 > 2"); 77 chunkA = naturalCompareChunk("1", compareMode.Integer); 78 chunkB = naturalCompareChunk("3", compareMode.Integer); 79 assertEqual(chunkA.opCmp(chunkB), -1, "(1 > 3) > 1"); 80 chunkA = naturalCompareChunk("3", compareMode.Integer); 81 chunkB = naturalCompareChunk("1", compareMode.Integer); 82 assertEqual(chunkA.opCmp(chunkB), 1, "(3 > 1) < -1"); 83 chunkA = naturalCompareChunk("a", compareMode.String); 84 chunkB = naturalCompareChunk("c", compareMode.String); 85 assertEqual(chunkA.opCmp(chunkB), -1, "(a > c) > 1"); 86 chunkA = naturalCompareChunk("c", compareMode.String); 87 chunkB = naturalCompareChunk("a", compareMode.String); 88 assertEqual(chunkA.opCmp(chunkB), 1, "(c > a) > 1"); 89 chunkA = naturalCompareChunk( "1", compareMode.Integer); 90 chunkB = naturalCompareChunk("01", compareMode.Integer); 91 assertEqual(chunkA.opCmp(chunkB), 1, "(1 > 01) > 1"); 92 chunkA = naturalCompareChunk( "01", compareMode.Integer); 93 chunkB = naturalCompareChunk("001", compareMode.Integer); 94 assertEqual(chunkA.opCmp(chunkB), 1, "(01 > 001) > 1"); 95 } 96 /** 97 * Splits a string into component chunks. Each component is treated either as an integer or a string. 98 * Returns: A list of prepared string chunks 99 */ 100 private naturalCompareChunk[] buildChunkList(inout char[] str) pure in { 101 //Unsure if there are any constraints on input 102 } out(result) { 103 foreach (chunk; result) 104 assert(chunk.mode != compareMode.Undefined, "Undefined chunk type"); 105 } body { 106 import std.uni : isNumber; 107 naturalCompareChunk tempChunk; 108 naturalCompareChunk[] output; 109 foreach (character; str) { 110 if (character.isNumber()) { 111 if (tempChunk.mode == compareMode.Integer) 112 tempChunk.str ~= character; 113 if (tempChunk.mode == compareMode.Undefined) { 114 tempChunk.str = [character]; 115 tempChunk.mode = compareMode.Integer; 116 } 117 if (tempChunk.mode == compareMode.String) { 118 output ~= tempChunk; 119 tempChunk = naturalCompareChunk([character],compareMode.Integer); 120 } 121 } else { 122 if (tempChunk.mode == compareMode.String) 123 tempChunk.str ~= character; 124 if (tempChunk.mode == compareMode.Undefined) { 125 tempChunk.str = [character]; 126 tempChunk.mode = compareMode.String; 127 } 128 if (tempChunk.mode == compareMode.Integer) { 129 output ~= tempChunk; 130 tempChunk = naturalCompareChunk([character],compareMode.String); 131 } 132 } 133 } 134 output ~= tempChunk; 135 return output; 136 } 137 /** 138 * Compares two strings in a way that is natural to humans. 139 * Integers come before non-integers, and integers are compared as if they were numbers instead of strings of characters. 140 * Intended for usage in opCmp overloads. 141 * Examples: 142 * -------------------- 143 * struct someStruct { 144 * string someText; 145 * int opCmp(someStruct b) { 146 * return compareNatural(this.someText, b.someText); 147 * } 148 * } 149 * -------------------- 150 * Returns: -1 if a comes before b, 0 if a and b are equal, 1 if a comes after b 151 */ 152 int compareNatural(inout char[] a, inout char[] b) pure in { 153 154 } out(result) { 155 assert(result <= 1, "Result too large"); 156 assert(result >= -1, "Result too small"); 157 } body { 158 import std.algorithm : min; 159 naturalCompareChunk[] chunkA = buildChunkList(a); 160 naturalCompareChunk[] chunkB = buildChunkList(b); 161 int cmpVal; 162 foreach (index; 0..min(chunkA.length, chunkB.length)) { 163 cmpVal = chunkA[index].opCmp(chunkB[index]); 164 if (cmpVal != 0) 165 return cmpVal; 166 } 167 if (chunkA.length > chunkB.length) 168 return 1; 169 if (chunkA.length < chunkB.length) 170 return -1; 171 return 0; 172 } 173 unittest { 174 assertEqual(compareNatural("10", "1"), 1, "1 > 10"); 175 assertEqual(compareNatural("010", "1"), 1, "1 > 010"); 176 assertEqual(compareNatural("10", "01"), 1, "01 > 10"); 177 assertEqual(compareNatural("10_1", "1_1"), 1, "1_1 > 10_1"); 178 assertEqual(compareNatural("10_1", "10_2"), -1, "10_1 > 10_2"); 179 assertEqual(compareNatural("10_2", "10_1"), 1, "10_1 > 10_2"); 180 assertEqual(compareNatural("a", "a1"), -1, "a > a1"); 181 assertEqual(compareNatural("a1", "a"), 1, "a1 < a"); 182 assertEqual(compareNatural("1000", "something"), -1, "1000 > something"); 183 assertEqual(compareNatural("something", "1000"), 1, "something < 1000"); 184 assertEqual(compareNatural("十", "〇"), 1, "Japanese: 10 > 0"); 185 assertEqual(compareNatural("עֶ֫שֶׂר", "אֶ֫פֶס"), 1, "Biblical Hebrew: 10 > 0"); 186 } 187 188 /** 189 * Natural string comparison function for use with phobos's sorting algorithm 190 * Examples: 191 * -------------------- 192 * assert(sort!compareNaturalSort(array(["0", "10", "1"])) == ["0", "1", "10"]); 193 * assert(sort!compareNaturalSort(array(["a", "c", "b"])) == ["a", "b", "c"]); 194 * assert(sort!compareNaturalSort(array(["a1", "a"])) == ["a", "a1"]); 195 * -------------------- 196 * Returns: true if a < b 197 */ 198 bool compareNaturalSort(inout(char[]) a, inout(char[]) b) pure { 199 return compareNatural(b,a) > 0; 200 } 201 @system unittest { 202 import std.algorithm : sort; 203 import std.array : array; 204 assertEqual(compareNaturalSort("a", "b"), true); 205 assertEqual(array(sort!compareNaturalSort(["0", "10", "1"])), ["0", "1", "10"]); 206 assertEqual(array(sort!compareNaturalSort(["a", "c", "b"])), ["a", "b", "c"]); 207 assertEqual(array(sort!compareNaturalSort(["a1", "a"])), ["a", "a1"]); 208 } 209 /** 210 * Compares path strings naturally. Comparing paths naturally requires path separators to be treated specially. 211 * Intended for usage in opCmp overloads. 212 * Examples: 213 * -------------------- 214 * struct someStruct { 215 * string someText; 216 * int opCmp(someStruct b) { 217 * return comparePathsNatural(this.someText, b.someText); 218 * } 219 * } 220 * -------------------- 221 * Returns: -1 if a comes before b, 0 if a and b are equal, 1 if a comes after b 222 */ 223 int comparePathsNatural(inout(char[]) pathA, inout(char[]) pathB) pure in { 224 import std.path : isValidPath; 225 assert(pathA.isValidPath(), "First path is invalid"); 226 assert(pathB.isValidPath(), "Second path is invalid"); 227 } out(result) { 228 assert(result <= 1, "Result too large"); 229 assert(result >= -1, "Result too small"); 230 } body { 231 import std.algorithm : min; 232 import std.array : array; 233 import std.path : pathSplitter; 234 auto pathSplitA = array(pathSplitter(pathA)); 235 auto pathSplitB = array(pathSplitter(pathB)); 236 int outVal = 0; 237 foreach (index; 0..min(pathSplitA.length, pathSplitB.length)) { 238 outVal = compareNatural(pathSplitA[index], pathSplitB[index]); 239 if (outVal != 0) 240 break; 241 } 242 return outVal; 243 } 244 /** 245 * Path comparison function for use with phobos's sorting algorithm 246 * Examples: 247 * -------------------- 248 * assert(array(sort!comparePathsNaturalSort(["a/b/c", "a/b/e", "a/b/d"])) == ["a/b/c", "a/b/d", "a/b/e"]); 249 * assert(array(sort!comparePathsNaturalSort(["a1", "a"])) == ["a", "a1"]); 250 * assert(array(sort!comparePathsNaturalSort(["a1/b", "a/b"])) == ["a/b", "a1/b"]); 251 * -------------------- 252 * Returns: true if a < b 253 */ 254 bool comparePathsNaturalSort(inout(char[]) a, inout(char[]) b) pure { 255 return comparePathsNatural(b,a) > 0; 256 } 257 258 @system unittest { 259 import std.algorithm : sort; 260 import std.array : array; 261 assertEqual(comparePathsNaturalSort("a/b", "a1/b"), true); 262 assertEqual(array(sort!comparePathsNaturalSort(["a/b/c", "a/b/e", "a/b/d"])), ["a/b/c", "a/b/d", "a/b/e"]); 263 assertEqual(array(sort!comparePathsNaturalSort(["a1", "a"])), ["a", "a1"]); 264 assertEqual(array(sort!comparePathsNaturalSort(["a1/b", "a/b"])), ["a/b", "a1/b"]); 265 } 266 unittest { 267 assertEqual(comparePathsNatural("a/b/c", "a/b/d"), -1, "Final path component sorting failed"); 268 assertEqual(comparePathsNatural("a/b/c", "a/b/d"), -1, "Final path component sorting failed"); 269 assertEqual(comparePathsNatural("a/b/c", "a/b/c"), 0, "Identical path sorting failed"); 270 assertEqual(comparePathsNatural("a/b/c", "a/b/a"), 1, "Final path component sorting failed (2)"); 271 assertEqual(comparePathsNatural("a/b/c", "a/c/c"), -1, "Middle path component sorting failed"); 272 assertEqual(comparePathsNatural("a/c/c", "a/b/c"), 1, "Middle path component sorting failed (2)"); 273 assertEqual(comparePathsNatural("a/b/c", "b/b/c"), -1, "First path component sorting failed"); 274 assertEqual(comparePathsNatural("b/b/c", "a/b/c"), 1, "First path component sorting failed (2)"); 275 assertEqual(comparePathsNatural("a/b", "a1/b"), -1, "Appended chunk sorting failed"); 276 assertEqual(comparePathsNatural("a1/b", "a/b"), 1, "Appended chunk sorting failed (2)"); 277 } 278 private void assertEqual(T,U)(lazy T valA, lazy U valB, string message = "") pure { 279 import std.string : format; 280 try { 281 if (valA != valB) 282 assert(true, format("%s: %s != %s",message, valA, valB)); 283 } catch (Exception e) { 284 assert(true, e.msg); 285 } 286 }