/**
 * Returns the lowest index of the matching line in the frame,
 * or -1 if no line in the frame matched.
 */
static CFIndex MTFrameGetFirstLine(CTFrameRef frame, CFIndex charIndex, CTLineRef *found, CFRange *characterRange)
{
  const CFArrayRef lines = CTFrameGetLines(frame);
  CFIndex l = 0, u = CFArrayGetCount(lines);
  while (l < u) {
    const CFIndex m = l + ((u - l) / 2);
    const CTLineRef line = CFArrayGetValueAtIndex(lines, m);
    const CFRange range = CTLineGetStringRange(line);
    const CFIndex t = charIndex - range.location;

    if (t < 0) u = m;
    else if (t >= range.length) l = m + 1;
    else {
      if (found != NULL) *found = line;
      if (characterRange != NULL) *characterRange = range;
      return m;
    }
  }

  return -1;
}

/**
 * Returns a line origin for a frame.
 */
CGPoint MTFrameGetLineOriginAtIndex(CTFrameRef frame, CFIndex index) {
  CGPoint origin;
  CTFrameGetLineOrigins(frame, CFRangeMake(index, 1), &origin);
  return origin;
}

/**
 * Calculates the typographic bounds of a line.
 */
static CGSize MTLineGetTypographicSize(CTLineRef line) {
  CGFloat ascent, descent, leading;
  double w = CTLineGetTypographicBounds(line, &ascent, &descent, &leading);

  if (w > 0.0) {
    const double h = ascent + descent + leading;
    w -= CTLineGetTrailingWhitespaceWidth(line);

    return CGSizeMake(
      w > CGFLOAT_MAX ? CGFLOAT_MAX : (CGFloat) w,
      h > CGFLOAT_MAX ? CGFLOAT_MAX : (CGFloat) h
    );
  }
  return CGSizeZero;
}

static CGRect MTLineGetFirstRectForCharacterAtIndex(CTFrameRef frame, CTLineRef line, CFIndex lineIndex, CFIndex charIndex, Boolean verticalForms) {
  const CGRect box = MTFrameGetBoundingBox(frame);
  const CGPoint origin = MTFrameGetLineOriginAtIndex(frame, lineIndex);
  const CGFloat offset = CTLineGetOffsetForStringIndex(line, charIndex, NULL);
  const CGSize size = MTLineGetTypographicSize(line);

  if (CGSizeEqualToSize(size, CGSizeZero)) return CGRectNull;
  if (!verticalForms) {
    return CGRectMake(
      origin.x + CGRectGetMinX(box) + offset,
      origin.y - CGRectGetMinY(box),
      size.width - offset,
      size.height
    );
  } else {
    return CGRectMake(
      origin.x,
      origin.y - size.width + CGRectGetMinY(box),
      size.height,
      size.width - offset
    );
  }
}