Request for binary search using functions

[Peter Levart]

On 12/11/2012 08:25 PM, Julian Hyde wrote:
> On Dec 9, 2012, at 8:48 PM, Cleber Muramoto <cleber at nightcoders.com.br> wrote:
>
>> Hello, every once in a while I come across the problem of having to use an
>> incompatible key to perform a binary search, e.g.:
>>
>> int binarySearch(SimpleDateFormat[] array,String pattern){
>> ...
>> String midVal = array[i].toPattern();
>> ...
>> }
>>
>> (array is sorted using (l,r)->l.toPattern().compareTo(r.toPattern()) )
> I think an AbstractList does the trick. It maps values to strings, and only incurs one allocation per search. You need to make it implement RandomAccess so that binarySearch uses an efficient algorithm.
>
> final SimpleDateFormat[] array;
> final String seek;
> class AbstractRandomAccessList<E> extends AbstractList<E> implements RandomAccess {};
>
> return Collections.binarySearch(
>    new AbstractRandomAccessList<String>() {
>      public int size() {
>        return array.length;
>      }
>      public String get(int index) {
>        return array[index].toPattern();
>      },
>      seek);
>
> There's also a variant Collections.binarySearch(Object[], int, int) if you wish to search on ranges.
>
> Aside: AbstractList is so useful; it's a shame it is a DAM and not a SAM, and therefore not eligible for lambdafication. Does anyone have any bright ideas how the above could be expressed in lambdas?
>
> Julian
>
Like that?

public class Arrays {
...
     public static <F, T>List<T> asMappedImmutableList(final F[] array, 
final Function<F, T> mapper) {
         return new AbstractList<T>() {
             @Override
             public T get(int index) {
                 return mapper.apply(array[index]);
             }

             @Override
             public int size() {
                 return array.length;
             }
         };
     }
...
}

Peter