LexicographicStringComparer.cs 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
  1. /*
  2. Taken from https://gist.github.com/mstum/63a6e3e8cf54e8ae55b6aa28ca6f20c5
  3. Modified slightly to remove the need for unsafe and changed namespace to plugin namespace
  4. */
  5. using System;
  6. using System.Collections.Generic;
  7. namespace COM3D2.MeidoPhotoStudio.Plugin
  8. {
  9. /// <summary>
  10. /// A string comparer that behaves like StrCmpLogicalW
  11. /// https://msdn.microsoft.com/en-us/library/windows/desktop/bb759947
  12. ///
  13. /// This means:
  14. /// * case insensitive (ZA == za)
  15. /// * numbers are treated as numbers (z20 &gt; z3) and assumed positive
  16. /// (-100 comes AFTER 10 and 100, because the minus is seen
  17. /// as a char, not as part of the number)
  18. /// * leading zeroes come before anything else (z001 &lt; z01 &lt; z1)
  19. ///
  20. /// Note: Instead of instantiating this, you can also use
  21. /// <see cref="Comparison(string, string)"/>
  22. /// if you don't need an <see cref="IComparer{string}"/> but can
  23. /// use a <see cref="Comparison{string}"/> delegate instead.
  24. /// </summary>
  25. /// <remarks>
  26. /// NOTE: This behaves slightly different than StrCmpLogicalW because
  27. /// it handles large numbers.
  28. ///
  29. /// At some point, StrCmpLogicalW just gives up trying to parse
  30. /// something as a number (see the Test cases), while we keep going.
  31. /// Since we want to sort lexicographily as much as possible,
  32. /// that difference makes sense.
  33. /// </remarks>
  34. public class LexicographicStringComparer : IComparer<string>
  35. {
  36. /// <summary>
  37. /// A <see cref="Comparison{string}"/> delegate.
  38. /// </summary>
  39. public static int Comparison(string x, string y)
  40. {
  41. // 1 = x > y, -1 = y > x, 0 = x == y
  42. // Rules: Numbers < Letters. Space < everything
  43. if (x == y) return 0;
  44. if (string.IsNullOrEmpty(x) && !string.IsNullOrEmpty(y)) return -1;
  45. if (!string.IsNullOrEmpty(x) && string.IsNullOrEmpty(y)) return 1;
  46. if (string.IsNullOrEmpty(x) && string.IsNullOrEmpty(y)) return 0; // "" and null are the same for the purposes of this
  47. var yl = y.Length;
  48. for (int i = 0; i < x.Length; i++)
  49. {
  50. if (yl <= i) return 1;
  51. var cx = x[i];
  52. var cy = y[i];
  53. if (Char.IsWhiteSpace(cx) && !Char.IsWhiteSpace(cy)) return -1;
  54. if (!Char.IsWhiteSpace(cx) && Char.IsWhiteSpace(cy)) return 1;
  55. if (IsDigit(cx))
  56. {
  57. if (!IsDigit(cy))
  58. {
  59. return -1;
  60. }
  61. // Both are digits, but now we need to look at them as a whole, since
  62. // 10 > 2, but 10 > 002 > 02 > 2
  63. var numCmp = CompareNumbers(x, y, i, out int numChars);
  64. if (numCmp != 0) return numCmp;
  65. i += numChars; // We might have looked at more than one char, e.g., "10" is 2 chars
  66. }
  67. else if (IsDigit(cy))
  68. {
  69. return 1;
  70. }
  71. else
  72. {
  73. // Do this after the digit check
  74. // Case insensitive
  75. // Normalize to Uppercase:
  76. // https://docs.microsoft.com/en-US/visualstudio/code-quality/ca1308-normalize-strings-to-uppercase
  77. var cmp = Char.ToUpper(cx).CompareTo(Char.ToUpper(cy));
  78. if (cmp != 0) return cmp;
  79. }
  80. }
  81. // Strings are equal to that point, and y is at least as large as x
  82. if (y.Length > x.Length) return -1;
  83. return 0;
  84. }
  85. /// <summary>
  86. /// <see cref="IComparer{T}.Compare(T, T)"/>
  87. /// </summary>
  88. public int Compare(string x, string y)
  89. => Comparison(x, y);
  90. private static int CompareNumbers(string x, string y, int ix, out int numChars)
  91. {
  92. var xParsed = ParseNumber(x, ix);
  93. var yParsed = ParseNumber(y, ix);
  94. numChars = yParsed.NumCharsRead > xParsed.NumCharsRead
  95. ? xParsed.NumCharsRead
  96. : yParsed.NumCharsRead;
  97. return xParsed.CompareTo(yParsed);
  98. }
  99. private static ParsedNumber ParseNumber(string str, int offset)
  100. {
  101. var result = 0;
  102. var numChars = 0;
  103. var leadingZeroes = 0;
  104. var numOverflows = 0;
  105. bool countZeroes = true;
  106. for (int j = offset; j < str.Length; j++)
  107. {
  108. char c = str[j];
  109. if (IsDigit(c))
  110. {
  111. var cInt = (c - 48); // 48/0x30 is '0'
  112. checked
  113. {
  114. long tmp = (result * 10L) + cInt;
  115. if (tmp > int.MaxValue)
  116. {
  117. numOverflows++;
  118. tmp = tmp % int.MaxValue;
  119. }
  120. result = (int)tmp;
  121. numChars++;
  122. }
  123. if (cInt == 0 && countZeroes)
  124. {
  125. leadingZeroes++;
  126. }
  127. else
  128. {
  129. countZeroes = false;
  130. }
  131. }
  132. else
  133. {
  134. break;
  135. }
  136. }
  137. return new ParsedNumber(result, numOverflows, leadingZeroes, numChars);
  138. }
  139. private static bool IsDigit(char c) => (c >= '0' && c <= '9');
  140. /// <summary>
  141. /// Note that the ParsedNumber is not very useful as a number,
  142. /// but purely as a way to compare two numbers that are stored in a string.
  143. /// </summary>
  144. private struct ParsedNumber : IComparable<ParsedNumber>, IComparer<ParsedNumber>
  145. {
  146. /// <summary>
  147. /// The remainder, that is, the part of the number that
  148. /// didn't overflow int.MaxValue.
  149. /// </summary>
  150. public int Remainder;
  151. /// <summary>
  152. /// How often did the number overflow int.MaxValue during parsing?
  153. /// </summary>
  154. public int Overflows;
  155. /// <summary>
  156. /// How many leading zeroes were there in the string during parsing?
  157. /// "001" has a LeadingZeroesCount of 2.
  158. /// "100" has a LeadingZeroesCount of 0.
  159. /// "010" has a LeadingZeroesCount of 1.
  160. ///
  161. /// This is important, because 001 comes before 01 comes before 1.
  162. /// </summary>
  163. public int LeadingZeroesCount;
  164. /// <summary>
  165. /// How many characters were read from the input during parsing?
  166. /// </summary>
  167. public int NumCharsRead;
  168. public ParsedNumber(int remainder, int overflows, int leadingZeroes, int numChars)
  169. {
  170. Remainder = remainder;
  171. Overflows = overflows;
  172. LeadingZeroesCount = leadingZeroes;
  173. NumCharsRead = numChars;
  174. }
  175. public int Compare(ParsedNumber x, ParsedNumber y)
  176. {
  177. // Note: if numCharsX and Y aren't equal, this doesn't matter
  178. // as the return value will be either -1 or 1 anyway
  179. if (x.Overflows > y.Overflows) return 1;
  180. if (x.Overflows < y.Overflows) return -1;
  181. // 001 > 01 > 1
  182. if (x.Remainder == y.Remainder)
  183. {
  184. if (x.LeadingZeroesCount > y.LeadingZeroesCount) return -1;
  185. if (x.LeadingZeroesCount < y.LeadingZeroesCount) return 1;
  186. }
  187. if (x.Remainder > y.Remainder) return 1;
  188. if (x.Remainder < y.Remainder) return -1;
  189. return 0;
  190. }
  191. public int CompareTo(ParsedNumber other)
  192. => Compare(this, other);
  193. }
  194. }
  195. }