lib/src/utils.dart

// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

library source_span.utils;

/// Returns the minimum of [obj1] and [obj2] according to
/// [Comparable.compareTo].
Comparable min(Comparable obj1, Comparable obj2) =>
    obj1.compareTo(obj2) > 0 ? obj2 : obj1;

/// Returns the maximum of [obj1] and [obj2] according to
/// [Comparable.compareTo].
Comparable max(Comparable obj1, Comparable obj2) =>
    obj1.compareTo(obj2) > 0 ? obj1 : obj2;

/// Find the first entry in a sorted [list] that matches a monotonic predicate.
///
/// Given a result `n`, that all items before `n` will not match, `n` matches,
/// and all items after `n` match too. The result is -1 when there are no
/// items, 0 when all items match, and list.length when none does.
int binarySearch(List list, bool matches(item)) {
  if (list.length == 0) return -1;
  if (matches(list.first)) return 0;
  if (!matches(list.last)) return list.length;

  int min = 0;
  int max = list.length - 1;
  while (min < max) {
    var half = min + ((max - min) ~/ 2);
    if (matches(list[half])) {
      max = half;
    } else {
      min = half + 1;
    }
  }
  return max;
}