为复合对象编写比较器以进行二进制搜索

Question

我有一个类和实例列表,看起来像这样(更改字段名称以保护无辜/专有):

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;

该列表bloatList由内部保留BloatProducer并以这样的方式维护:它仅附加新Bloat记录,不修改任何旧记录,并且每个字段单调增加,例如bloatProducer.testMonotonicity()总是返回true.

我想用timeInMilliseconds,spaceInBytes或costInPennies字段Collections.binarySearch(list,key,comparator)来搜索Bloat记录.(如果数字在两个记录之间,我想找到以前的记录)

编写一系列3个Comparator类以使其工作的最简单方法是什么？我是否必须使用一个具有虚拟字段的Bloat对象的密钥用于我不搜索的密钥？

Answer 1

您需要为要比较的每个字段编写单独的比较器:

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;
        }
    }
}

对于Bloat您想要比较的每个属性等等(您需要为每个属性创建一个比较器类).然后使用Collections帮助器方法:

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

从binarySearch方法的Java文档中,返回值将是:

搜索关键字的索引,如果它包含在列表中; 否则,( - (插入点) - 1).插入点定义为键将插入列表的点:第一个元素的索引大于键,或者list.size(),如果列表中的所有元素都小于指定的键.请注意,当且仅当找到密钥时,这可以保证返回值> = 0.

您指定的索引是哪个.