From 1eca50c3832a968ab4209e55673a600b0f13ec83 Mon Sep 17 00:00:00 2001
From: Tim Starling <tstarling@wikimedia.org>
Date: Thu, 11 Oct 2012 20:01:46 +1100
Subject: [PATCH] Fix various boundary cases in IcuCollation::findLowerBound()

Fix the following edge cases which were previously broken:

* Zero-length input array
* Target value before the start
* Target value past the end

They didn't really matter for my original application, but Liangent
wants to use this function for something else.

Change-Id: Ia5f5ed4ab3cb6c463177a4812fd3ce96c6d37b33
---
 includes/Collation.php | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

diff --git a/includes/Collation.php b/includes/Collation.php
index 8554c2b047..3cc7902855 100644
--- a/includes/Collation.php
+++ b/includes/Collation.php
@@ -335,8 +335,12 @@ class IcuCollation extends Collation {
 	 *     sorts before all items.
 	 */
 	function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
+		if ( $valueCount === 0 ) {
+			return false;
+		}
+
 		$min = 0;
-		$max = $valueCount - 1;
+		$max = $valueCount;
 		do {
 			$mid = $min + ( ( $max - $min ) >> 1 );
 			$item = call_user_func( $valueCallback, $mid );
@@ -351,12 +355,15 @@ class IcuCollation extends Collation {
 			}
 		} while ( $min < $max - 1 );
 
-		if ( $min == 0 && $max == 0 && $comparison > 0 ) {
-			// Before the first item
-			return false;
-		} else {
-			return $min;
+		if ( $min == 0 ) {
+			$item = call_user_func( $valueCallback, $min );
+			$comparison = call_user_func( $comparisonCallback, $target, $item );
+			if ( $comparison < 0 ) {
+				// Before the first item
+				return false;
+			}
 		}
+		return $min;
 	}
 
 	static function isCjk( $codepoint ) {
-- 
2.20.1