writing a Comparator for a compound object for binary searching

Question

I have a class, and list of instances, that looks something like this (field names changed to protect the innocent/proprietary):

public class Bloat
{
    public long timeInMilliseconds;
    public long spaceInBytes;
    public long costInPennies;
}

public class BloatProducer
{
    final private List<Bloat> bloatList = new ArrayList<Bloat>();
    final private Random random = new Random();
    public void produceMoreBloat()
    {
       int n = bloatList.size();
       Bloat previousBloat = (n == 0) ? new Bloat() : bloatList.get(n-1);
       Bloat newBloat = new Bloat();
       newBloat.timeInMilliseconds = 
          previousBloat.timeInMilliseconds + random.nextInt(10) + 1;
       newBloat.spaceInBytes = 
          previousBloat.spaceInBytes + random.nextInt(10) + 1;
       newBloat.costInPennies = 
          previousBloat.costInPennies + random.nextInt(10) + 1;
       bloatList.add(newBloat);
    }
    /* other fields/methods */

    public boolean testMonotonicity()
    {
 Bloat previousBloat = null;
 for (Bloat thisBloat : bloatList)
            {
               if (previousBloat != null)
               {
                  if ((previousBloat.timeInMilliseconds 
                     >= thisBloat.timeInMilliseconds)
                   || (previousBloat.spaceInBytes 
                     >= thisBloat.spaceInBytes)
                   || (previousBloat.costInPennies
                     >= thisBloat.costInPennies))
                       return false;
               }
               previousBloat = thisBloat;
           }
           return true;
    }

BloatProducer bloatProducer;

The list bloatList is kept internally by BloatProducer and is maintained in such a way that it only appends new Bloat records, does not modify any of the old ones, and each of the fields is monotonically increasing, e.g. bloatProducer.testMonotonicity() would always return true.

I would like to use Collections.binarySearch(list,key,comparator) to search for the Bloat record by either the timeInMilliseconds, spaceInBytes, or costInPennies fields. (and if the number is between two records, I want to find the previous record)

What's the easiest way to write a series of 3 Comparator classes to get this to work? Do I have to use a key that is a Bloat object with dummy fields for the ones I'm not searching for?

Answer 1

If you want to leverage the binary search for all three properties, you have to create comparators for them and have additional Lists or TreeSets sorted by the comparators.

Answer 2

You will need to have 3 separate Comparators if you want to search by each of the 3 properties.

A cleaner option would be to have a generic Comparator which receives a parameter which tells it by which field to compare.

A basic generic comparator should look something like this:

public class BloatComparator implements Comparator<Bloat>
{
    CompareByEnum field;

    public BloatComparator(CompareByEnum field) {
     this.field = field;
    }

    @Override
    public int compare(Bloat arg0, Bloat arg1) {
     if (this.field == CompareByEnum.TIME){
      // compare by field time
     }
     else if (this.field == CompareByEnum.SPACE) {
      // compare by field space
     }
     else {
      // compare by field cost
     }
    }
}

Answer 3

You'll need to write a separate comparator for each field you want to compare on:

public class BloatTimeComparator implements Comparator<Bloat> {
    public int compare(Bloat bloat1, Bloat bloat2) {
        if (bloat1.timeInMilliseconds > bloat2.timeInMilliseconds) {
            return 1;
        } else if (bloat1.timeInMilliseconds < bloat2.timeInMilliseconds) {
            return -1;
        } else {
            return 0;
        }
    }
}

And so on for each property in Bloat you want to compare on (you'll need to create a comparator class for each). Then use the Collections helper method:

Collections.binarySearch(bloatList,  bloatObjectToFind, 
    new BloatTimeComparator());

From the Java documentation for the binarySearch method, the return value will be:

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Which is the index you specified that you wanted.

Answer 4

Here's a test-driven approach to writing the first comparator:

public class BloatTest extends TestCase{
    public class Bloat {
     public long timeInMilliseconds;
     public long spaceInBytes;
     public long costInPennies;

     public Bloat(long timeInMilliseconds, long spaceInBytes, long costInPennies) {
      this.timeInMilliseconds = timeInMilliseconds;
      this.spaceInBytes = spaceInBytes;
      this.costInPennies = costInPennies;
     }
    }

    public void testMillisecondComparator() throws Exception {
     Bloat a = new Bloat(5, 10, 10);
     Bloat b = new Bloat(3, 12, 12);
     Bloat c = new Bloat(5, 12, 12);

     Comparator<Bloat> comparator = new MillisecondComparator();
     assertTrue(comparator.compare(a, b) > 0);
     assertTrue(comparator.compare(b, a) < 0);
     assertEquals(0, comparator.compare(a, c));
    }

    private static class MillisecondComparator implements Comparator<Bloat> {
     public int compare(Bloat a, Bloat b) {
      Long aTime = a.timeInMilliseconds;
      return aTime.compareTo(b.timeInMilliseconds);
     }
    }


}

Answer 5

test program (MultiBinarySearch.java) to see if these ideas work properly (they appear to):

package com.example.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

class Bloat
{
    final public long timeInMilliseconds;
    final public long spaceInBytes;
    final public long costInPennies;
    static final private int N = 100; 
    public Bloat(long l1, long l2, long l3) {
     timeInMilliseconds = l1;
     spaceInBytes = l2;
     costInPennies = l3; 
    }
    public Bloat() { this(0,0,0); }
    public Bloat moreBloat(Random r)
    {
     return new Bloat(
       timeInMilliseconds + r.nextInt(N) + 1,
       spaceInBytes + r.nextInt(N) + 1,
       costInPennies + r.nextInt(N) + 1
     );
    }
    public String toString() {
     return "[bloat: time="+timeInMilliseconds
      +", space="+spaceInBytes
      +", cost="+costInPennies
      +"]";
    }

    static int compareLong(long l1, long l2)
    {
     if (l2 > l1)
      return -1;
     else if (l1 > l2)
      return 1;
     else
      return 0;
    }

    public static class TimeComparator implements Comparator<Bloat> {
        public int compare(Bloat bloat1, Bloat bloat2) {
            return compareLong(bloat1.timeInMilliseconds, bloat2.timeInMilliseconds);
        }
    }
    public static class SpaceComparator implements Comparator<Bloat> {
        public int compare(Bloat bloat1, Bloat bloat2) {
            return compareLong(bloat1.spaceInBytes, bloat2.spaceInBytes);
        }
    }
    public static class CostComparator implements Comparator<Bloat> {
        public int compare(Bloat bloat1, Bloat bloat2) {
            return compareLong(bloat1.costInPennies, bloat2.costInPennies);
        }
    }
    enum Type { 
     TIME(new TimeComparator()), 
     SPACE(new SpaceComparator()),
     COST(new CostComparator());

     public Comparator<Bloat> comparator;
     Type(Comparator<Bloat> c) { this.comparator = c; } 
    } 
}

class BloatProducer
{
    final private List<Bloat> bloatList = new ArrayList<Bloat>();
    final private Random random = new Random();
    public void produceMoreBloat()
    {
     int n = bloatList.size();
     Bloat newBloat = 
      (n == 0) ? new Bloat() : bloatList.get(n-1).moreBloat(random);
      bloatList.add(newBloat);
    }
    /* other fields/methods */

    public boolean testMonotonicity()
    {
     Bloat previousBloat = null;
     for (Bloat thisBloat : bloatList)
     {
      if (previousBloat != null)
      {
       if ((previousBloat.timeInMilliseconds 
         >= thisBloat.timeInMilliseconds)
        || (previousBloat.spaceInBytes 
         >= thisBloat.spaceInBytes)
        || (previousBloat.costInPennies
         >= thisBloat.costInPennies))
        return false;
      }
      previousBloat = thisBloat;
     }
     return true;
    }
    public int searchBy(Bloat.Type t, Bloat key)
    {
     return Collections.binarySearch(bloatList, key, t.comparator);
    }
    public void showSearch(Bloat.Type t, Bloat key)
    {
     System.out.println("Search by "+t+": "); 
     System.out.println(key);
     int i = searchBy(t,key);
     if (i >= 0)
     {
      System.out.println("matches");
      System.out.println(bloatList.get(i));
     }
     else
     {
      System.out.println("is between");
      i = -i-1;
      Bloat b1 = (i == 0) ? null : bloatList.get(i-1);
      System.out.println(b1);
      Bloat b2 = (i >= bloatList.size()) ? null : bloatList.get(i);
      System.out.println("and");
      System.out.println(b2);
     }
    }
}

public class MultiBinarySearch {
    private static int N = 1000;
    public static void main(String[] args)
    {
     BloatProducer bloatProducer = new BloatProducer();
     for (int i = 0; i < N; ++i)
     {
      bloatProducer.produceMoreBloat();
     }

     System.out.println("testMonotonicity() returns "+
       bloatProducer.testMonotonicity());
     Bloat key;
     key = new Bloat(10*N, 20*N, 30*N);
     bloatProducer.showSearch(Bloat.Type.COST, key);
     bloatProducer.showSearch(Bloat.Type.SPACE, key);
     bloatProducer.showSearch(Bloat.Type.TIME, key);
     key = new Bloat(-10000, 0, 1000*N);
     bloatProducer.showSearch(Bloat.Type.COST, key);
     bloatProducer.showSearch(Bloat.Type.SPACE, key);
     bloatProducer.showSearch(Bloat.Type.TIME, key);
    }
}