Binary search Java list with key extractor

user_3821009 0
Viewed 233

Say I have:

class Item {
   int id;
   int type;
}

I can do this:

List<Item> items;
Item itemToFind;
Comparator<Item> itemComparator;
Collections.binarySearch(items, itemToFind, itemComparator);

However, say that instead of the whole object, I'm only given a property of the object, say type for the above example. Assuming the list is sorted by that property, is there a standard method in Java or some established library to do something to this effect:

List<Item> items;
Function<Item, Integer> typeExtractor = Item::getType;
int typeToFind;
Comparator<Integer> typeComparator = Integer::compare;
binarySearch(items, typeExtractor, typeToFind, typeComparator);

without additional overhead (e.g. converting List<Item> to List<Integer> to call Collections.binarySearch on or similar)?

java
2 Answers

The comparator still would be Comparator<Item>. What you would change is the implementation of the comparator to evaluate upon the type instead of the id.

Comparator<Item> comparator = new Comparator<Item>(){
    public int compare(Item a, Item b) 
    { 
        return a.getType() - b.getType(); 
    } 
}

Item, would need to have the getter for type or the attribute made public. The same if using the id.

However, not sure how you suggest I would call Collections.binarySearch

The usage doesn't change (what changes is how the comparison is done inside the comparator object):

Item itemToFind = new Item();
itemToFind.setType(typeToFind);
Collections.binarySearch(items, itemToFind, comparator );

After some thought on the subject:

An alternative to use an Item as a needle is to base the Comparator on an Interface that Item and the needle implement.

An interface to return int values:

 public interface Intgettable{
     public int getInt();
 }

Item should have to implement this interface:

public class Item implements Intgettable{
     private int id;
     private int type;

     public void setId(int id){ 
         this.id = id;
     }
     public void setType(int type){ 
         this.type = type;
     }
     public int getId(){
         return id;
     }
     public int getType(){
         return type;
     }
     public int getInt(){
         return type;
     }
 }

The key to search will be an Intgettable which can be created:

1 - Using a class that extends Intgettable.

public static class MyItemKey implements Intgettable{
     private int value;

     public MyItemKey(int v){
         this.value = v;
     }

     @Override
     public int getInt(){
         return value;
     }
}

MyItemKey typeToFind = new MyItemKey(6);

2 - As an anonymous class inside the method.

Intgettable typeTofind = new Intgettable(){
        private int value = 6;
        public int getInt(){
            return value;
        }
};

3 - Or using the lambda version:

Intgettable typeTofind = ()->{return 6;};

The Comparator will be:

Comparator<Intgettable> comparator = new Comparator<Intgettable>(){
        public int compare(Intgettable a, Intgettable b){
            return a.getInt() - b.getInt();
        }
};

And finally use it in the binary search:

Collections.binarySearch(items, typeToFind, comparator );
user_22259600

Your problem is that in a Collection<T> the binary search implementation of java allows to search only for items of type T. In order to search for another type which is a part of T, you can do the following:

  1. Wrap the other type inside T, in your case this should look like this:
List<Item> items;
int typeToFind;

Item itemToFind = new Item(/* random value for id */ 0, typeToFind);
int index = binarySearch(items, itemToFind , (a, b) -> a.getType() - b.getType());

Some important notes to add here:

    - the comparison of items should depend only and only on `type`, otherwise you may end up with some nasty bugs;
    - the list of items should be sorted. The sorting should depend only and only on `type`(basically using the same comparator as before)
  1. Create a new list from the initial list:
List<Items> items;
int typeToFind

int index = binarySearch(items.stream.map(item -> item.getType()).collect(Collectors.toList()), itemToFind);

As far as I know, the standard library for Java does not provide binary search implementation with a comparator for key equality. If these options does not satisfy you, probably you should search for a library or implement your own search.

user_76611190
Related