// Copyright Keith D Gregory
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package net.sf.kdgcommons.collections;

import java.util.Random;

import junit.framework.TestCase;


/**
 *  This is a combined test for {@link InplaceSort} and {@link BinarySearch},
 *  which builds an index over a large number of values. It is meant not only
 *  as a test, but also as an example of how these two classes work together.
 */
public class TestSearchingASortedIndex
extends TestCase
{
    public void testBuildAndSearchAnIndex() throws Exception
    {
        final int size = 10000;
        final Integer[] data = new Integer[size];
        final int[] index = new int[size];

        // note: I saw a test failure in the binary search, but was unable to
        //       reproduce in several dozen runs; if it happens again, the seed
        //       will be logged and a regression written
        long seed = System.currentTimeMillis();
        Random rnd = new Random(seed);
        for (int ii = 0 ; ii < size ; ii++)
        {
            data[ii] = new Integer(rnd.nextInt());
            index[ii] = ii;
        }

        InplaceSort.IntComparator sortComparator = new InplaceSort.IntComparator()
        {
            // note: this is passed values from the index array, which must be used
            //       to index the actual data array
            public int compare(int i1, int i2)
            {
                Integer v1 = data[i1];
                Integer v2 = data[i2];
                return v1.compareTo(v2);
            }
        };
        InplaceSort.sort(index, sortComparator);

        // verify that the index is sorted
        for (int ii = 1 ; ii < size ; ii++)
        {
            Integer v1 = data[index[ii - 1]];
            Integer v2 = data[index[ii]];
            assertTrue("index is not a sorted view: data[index[" + (ii-1) + "]] = " + v1 + ", data[index[" + ii + "] = " + v2,
                       v1.compareTo(v2) <= 0);
        }


        BinarySearch.IndexedComparator<Integer> searchComparator = new BinarySearch.IndexedComparator<Integer>()
        {
            // note: again, idx is an index into the data array
            public int compare(Integer value, int idx)
            {
                return value.compareTo(data[idx]);
            }
        };

        // we'll assert that we can find everything ... note that the returned
        // search value is an index into the *index* array, not the data array
        for (int ii = 0 ; ii < size ; ii++)
        {
            int ret = BinarySearch.search(index, data[index[ii]], searchComparator);
            assertEquals("BinarySearch failed; seed was " + seed, ii, ret);
        }
    }
}

@@ -1196,205 +1196,353 @@
 te: 
-I saw a test failure in the binary search, but was unable to%0A        //       reproduce in several dozen runs; if it happens again, the seed%0A        //       will be logged and a regression written
+seed is preserved because the original version of this test would%0A        //       occasionally fail; it turned out to be a bad test design, but to%0A        //       find it I needed to track the %22random%22 value that caused a failure%0A        //       ... and there's no reason to eliminate that tracking now that the%0A        //       test is fixed
 %0A   
@@ -2623,17 +2623,16 @@
      %7D%0A%0A
-%0A
         
@@ -2771,24 +2771,36 @@
 te: 
-again, idx is an
+the acessor will provide the
  ind
@@ -2807,28 +2807,30 @@
 ex into the 
-data
+actual
  array%0A     
@@ -2987,11 +2987,8 @@
 / we
-'ll
  ass
@@ -3015,120 +3015,119 @@
  eve
-r
 ything
- ... note that the returned%0A        // search value is an index into the *index* array, not the data arra
+; because we might randomly get two%0A        // copies of the same value, the assertions are a little wonk
 y%0A  
@@ -3279,71 +3279,889 @@
     
-assertEquals(%22B
+if (ret == ii)%0A                continue;   // success for this index%0A%0A            if (ret %3E ii)%0A            %7B%0A                fail(%22binary search returned index that was above expected:%22%0A                     + %22 was: %22 + ret + %22, expected: %22 + ii + %22, seed = %22 + seed);%0A            %7D%0A%0A            if (!data%5Bindex%5Bret%5D%5D.equals(data%5Bindex%5Bii%5D%5D))%0A            %7B%0A                fail(%22b
 inary
-S
+ s
 earch 
-failed; seed was %22 + seed, ii, ret);
+returned index for different value:%22%0A                     + %22 was: %22 + ret + %22 (%22 + data%5Bindex%5Bret%5D%5D + %22)%22%0A                     + %22, expected: %22 + ii + %22 (%22 + data%5Bindex%5Bii%5D%5D + %22)%22%0A                     + %22, seed = %22 + seed);%0A            %7D%0A%0A            if ((ret %3E 0) && (data%5Bindex%5Bret-1%5D%5D.equals(data%5Bindex%5Bret%5D%5D)))%0A            %7B%0A                fail(%22binary search returned index that was not lowest for value:%22%0A                     + %22 was: %22 + ret + %22, seed = %22 + seed);%0A            %7D
 %0A   

fix a buggy unit test