RunExtensions.cs 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4. using System.Linq;
  5. using System.Linq.Expressions;
  6. using System.Text;
  7. using System.Xml.Schema;
  8. namespace Topten.RichTextKit.Utils
  9. {
  10. /// <summary>
  11. /// Interface to a run object with a start offset and a length
  12. /// </summary>
  13. public interface IRun
  14. {
  15. /// <summary>
  16. /// Offset of the start of this run
  17. /// </summary>
  18. int Offset { get; }
  19. /// <summary>
  20. /// Length of this run
  21. /// </summary>
  22. int Length { get; }
  23. }
  24. /// <summary>
  25. /// Represents a sub-run in a list of runs
  26. /// </summary>
  27. [DebuggerDisplay("[{Index}] [{Offset} + {Length} = {Offset + Length}] {Partial}")]
  28. public struct SubRun
  29. {
  30. /// <summary>
  31. /// Constructs a new sub-run
  32. /// </summary>
  33. /// <param name="index">The run index</param>
  34. /// <param name="offset">The sub-run offset</param>
  35. /// <param name="length">The sub-run length</param>
  36. /// <param name="partial">True if the sub-run is partial run</param>
  37. public SubRun(int index, int offset, int length, bool partial)
  38. {
  39. Index = index;
  40. Offset = offset;
  41. Length = length;
  42. Partial = partial;
  43. }
  44. /// <summary>
  45. /// The index of the run in the list of runs
  46. /// </summary>
  47. public int Index;
  48. /// <summary>
  49. /// Offset of this sub-run in the containing run
  50. /// </summary>
  51. public int Offset;
  52. /// <summary>
  53. /// Length of this sub-run in the containing run
  54. /// </summary>
  55. public int Length;
  56. /// <summary>
  57. /// Indicates if this sub-run is partial sub-run
  58. /// </summary>
  59. public bool Partial;
  60. }
  61. /// <summary>
  62. /// Helpers for iterating over a set of consecutive runs
  63. /// </summary>
  64. public static class RunExtensions
  65. {
  66. /// <summary>
  67. /// Given a list of consecutive runs, a start index and a length
  68. /// provides a list of sub-runs in the list of runs.
  69. /// </summary>
  70. /// <typeparam name="T">The list element type</typeparam>
  71. /// <param name="list">The list of runs</param>
  72. /// <param name="offset">The offset of the run</param>
  73. /// <param name="length">The length of the run</param>
  74. /// <returns>An enumerable collection of SubRuns</returns>
  75. public static IEnumerable<SubRun> GetInterectingRuns<T>(this IReadOnlyList<T> list, int offset, int length) where T : IRun
  76. {
  77. // Check list is consistent
  78. list.CheckValid();
  79. // Calculate end position
  80. int to = offset + length;
  81. // Find the start run
  82. int startRunIndex = list.BinarySearch(offset, (r, a) =>
  83. {
  84. if (r.Offset > a)
  85. return 1;
  86. if (r.Offset + r.Length <= a)
  87. return -1;
  88. return 0;
  89. });
  90. Debug.Assert(startRunIndex >= 0);
  91. Debug.Assert(startRunIndex < list.Count);
  92. // Iterate over all runs
  93. for (int i = startRunIndex; i < list.Count; i++)
  94. {
  95. // Get the run
  96. var r = list[i];
  97. // Quit if past requested run
  98. if (r.Offset >= to)
  99. break;
  100. // Yield sub-run
  101. var sr = new SubRun();
  102. sr.Index = i;
  103. sr.Offset = i == startRunIndex ? offset - r.Offset : 0;
  104. sr.Length = Math.Min(r.Offset + r.Length, to) - r.Offset - sr.Offset;
  105. sr.Partial = r.Length != sr.Length;
  106. yield return sr;
  107. }
  108. }
  109. /// <summary>
  110. /// Given a list of consecutive runs, a start index and a length
  111. /// provides a list of sub-runs in the list of runs (in reverse order)
  112. /// </summary>
  113. /// <typeparam name="T">The list element type</typeparam>
  114. /// <param name="list">The list of runs</param>
  115. /// <param name="offset">The offset of the run</param>
  116. /// <param name="length">The length of the run</param>
  117. /// <returns>An enumerable collection of SubRuns</returns>
  118. public static IEnumerable<SubRun> GetIntersectingRunsReverse<T>(this IReadOnlyList<T> list, int offset, int length) where T : IRun
  119. {
  120. // Check list is consistent
  121. list.CheckValid();
  122. // Calculate end position
  123. int to = offset + length;
  124. // Find the start run
  125. int endRunIndex = list.BinarySearch(to, (r, a) =>
  126. {
  127. if (r.Offset >= a)
  128. return 1;
  129. if (r.Offset + r.Length < a)
  130. return -1;
  131. return 0;
  132. });
  133. Debug.Assert(endRunIndex >= 0);
  134. Debug.Assert(endRunIndex < list.Count);
  135. // Iterate over all runs
  136. for (int i = endRunIndex; i >= 0; i--)
  137. {
  138. // Get the run
  139. var r = list[i];
  140. // Quit if past requested run
  141. if (r.Offset + r.Length <= offset)
  142. break;
  143. // Yield sub-run
  144. var sr = new SubRun();
  145. sr.Index = i;
  146. sr.Offset = r.Offset > offset ? 0 : offset - r.Offset;
  147. sr.Length = Math.Min(r.Offset + r.Length, to) - r.Offset - sr.Offset;
  148. sr.Partial = r.Length != sr.Length;
  149. yield return sr;
  150. }
  151. }
  152. /// <summary>
  153. /// Get the total length of a list of consecutive runs
  154. /// </summary>
  155. /// <typeparam name="T">The element type</typeparam>
  156. /// <param name="list">The list of runs</param>
  157. /// <returns>The total length</returns>
  158. public static int TotalLength<T>(this IReadOnlyList<T> list) where T : IRun
  159. {
  160. // Empty list?
  161. if (list.Count == 0)
  162. return 0;
  163. // Get length from last element
  164. var last = list[list.Count - 1];
  165. return last.Offset + last.Length;
  166. }
  167. /// <summary>
  168. /// Check that a list of runs is valid
  169. /// </summary>
  170. /// <typeparam name="T">The element type</typeparam>
  171. /// <param name="list">The list to be checked</param>
  172. [Conditional("DEBUG")]
  173. public static void CheckValid<T>(this IReadOnlyList<T> list) where T : IRun
  174. {
  175. CheckValid(list, list.TotalLength());
  176. }
  177. /// <summary>
  178. /// Check that a list of runs is valid
  179. /// </summary>
  180. /// <typeparam name="T">The element type</typeparam>
  181. /// <param name="list">The list to be checked</param>
  182. /// <param name="totalLength">The expected total length of the list of runs</param>
  183. [Conditional("DEBUG")]
  184. public static void CheckValid<T>(this IReadOnlyList<T> list, int totalLength) where T : IRun
  185. {
  186. if (list.Count > 0)
  187. {
  188. // Must start at zero
  189. Debug.Assert(list[0].Offset == 0);
  190. // Must cover entire code point buffer
  191. Debug.Assert(list[list.Count - 1].Offset + list[list.Count - 1].Length == totalLength);
  192. var prev = list[0];
  193. for (int i = 1; i < list.Count; i++)
  194. {
  195. // All runs must have a length
  196. Debug.Assert(list[i].Length > 0);
  197. // All runs must be consecutive and joined end to end
  198. Debug.Assert(list[i].Offset == prev.Offset + prev.Length);
  199. prev = list[i];
  200. }
  201. }
  202. else
  203. {
  204. // If no style runs then mustn't have any code points either
  205. Debug.Assert(totalLength == 0);
  206. }
  207. }
  208. }
  209. }