Make line search logic in SourcePositions generally available.

Create an object Util for utility methods that are used in several places.

1 files changed, 35 insertions, 0 deletions

diff --git a/src/dotty/tools/dotc/util/Util.scala b/src/dotty/tools/dotc/util/Util.scala
new file mode 100644
index 000000000..e323d47db
--- /dev/null
+++ b/src/dotty/tools/dotc/util/Util.scala
@@ -0,0 +1,35 @@
+package dotty.tools.dotc.util
+import reflect.ClassTag
+
+object Util {
+  
+  /** The index `i` in `candidates.indices` such that `candidates(i) <= x` and
+   *  `candidates(i)` is closest to `x`, determined by binary search, or -1
+   *  if `x < candidates(0)`.
+   *  @param  hint   If between 0 and `candidates.length` use this
+   *                 as the first search point, otherwise use 
+   *                 `candidates.length/2`.
+   *  @pre   candidates is sorted
+   *  @pre   candidates(0) <= x
+   */
+  def bestFit(candidates: Array[Int], x: Int, hint: Int = -1): Int = {
+    def recur(lo: Int, hi: Int, mid: Int): Int =
+      if (x < candidates(mid)) 
+        recur(lo, mid - 1, (lo + mid - 1) / 2)
+      else if (mid + 1 < candidates.length && x >= candidates(mid + 1)) 
+        recur(mid + 1, hi, (mid + 1 + hi) / 2)
+      else mid
+    val initMid = 
+      if (0 <= hint && hint < candidates.length) hint
+      else candidates.length / 2
+    if (candidates.isEmpty || x < candidates(0)) -1
+    else recur(0, candidates.length, initMid)
+  }
+  
+  /** An array twice the size of given array, with existing elements copied over */
+  def dble[T: ClassTag](arr: Array[T]) = {
+    val arr1 = new Array[T](arr.length * 2)
+    Array.copy(arr, 0, arr1, 0, arr.length)
+    arr1
+  }
+}
\ No newline at end of file