BUG: check for monotonic bin arrays in digitize

The check for monotonic bin arrays of digitize doesn't properly handle
inputs with repeated entries at the beginning of the array:

```
>>> np.__version__
'1.8.0'
>>> np.digitize([1], [0, 0 , 2])
array([2], dtype=int64)
>>> np.digitize([1], [2, 2, 0])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: The bins must be monotonically increasing or decreasing
```

Modified `check_array_monotonic` in `_compiled_base.c` to skip over repeating
entries before deciding to check for increasing or decreasing monotonicity
and added relevant tests to `test_function_base.py`.

2 files changed, 29 insertions, 14 deletions

diff --git a/numpy/lib/src/_compiled_base.c b/numpy/lib/src/_compiled_base.c
index 328fc2d14..df4cf8191 100644
--- a/numpy/lib/src/_compiled_base.c
+++ b/numpy/lib/src/_compiled_base.c
@@ -66,32 +66,34 @@ decr_slot_right_(double x, double * bins, npy_intp lbins)
  * and 0 if the array is not monotonic.
  */
 static int
-check_array_monotonic(double * a, int lena)
+check_array_monotonic(const double *a, int lena)
 {
-    int i;
-
-    if (a [0] <= a [1]) {
-        /* possibly monotonic increasing */
-        for (i = 1; i < lena - 1; i ++) {
-            if (a [i] > a [i + 1]) {
+    /* This function is always called with lena>= 2 */
+    const double *a_next = a + 1;
+    /* Ignore repeating values at the beginning of the array */
+    while((--lena > 1) && (*a == *a_next)) {
+        a++;
+        a_next++;
+    }
+    if (*a < *a_next) { /* possibly monotonic increasing */
+        while(--lena) {
+            if (*(++a) > *(++a_next)) {
                 return 0;
             }
         }
         return 1;
-    }
-    else {
-        /* possibly monotonic decreasing */
-        for (i = 1; i < lena - 1; i ++) {
-            if (a [i] < a [i + 1]) {
+    } else if (*a > *a_next) { /* possibly monotonic decreasing */
+        while(--lena) {
+            if (*(++a) < *(++a_next)) {
                 return 0;
             }
         }
         return -1;
+    } else { /* all bins edges hold the same value */
+        return 1;
     }
 }
 
-
-
 /* find the index of the maximum element of an integer array */
 static npy_intp
 mxx (npy_intp *i , npy_intp len)
diff --git a/numpy/lib/tests/test_function_base.py b/numpy/lib/tests/test_function_base.py
index 494b512f7..0d2a66f53 100644
--- a/numpy/lib/tests/test_function_base.py
+++ b/numpy/lib/tests/test_function_base.py
@@ -760,6 +760,19 @@ class TestDigitize(TestCase):
         x = rand(10)
         bins = np.linspace(x.min(), x.max(), 10)
         assert_(np.all(digitize(x, bins, True) != 10))
+    
+    def test_monotonic(self):
+        x = [0]
+        bins = [0, 0, 1]
+        digitize(x, bins)
+        bins = [1, 1, 0]
+        digitize(x, bins)
+        bins = [1, 1, 1, 1]
+        digitize(x, bins)
+        bins = [0, 0, 1, 0]
+        assert_raises(ValueError, digitize, x, bins)
+        bins = [1, 1, 0, 1]
+        assert_raises(ValueError, digitize, x, bins)
 
 
 class TestUnwrap(TestCase):