java - 为二进制搜索的复合对象编写比较器

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。

我想使用 Collections.binarySearch(list,key,comparator) 通过 timeInMilliseconds、spaceInBytes 或 costInPennies 字段搜索 Bloat 记录。 (如果数字在两条记录之间，我想找到上一条记录)

编写一系列 3 个比较器类以使其工作的最简单方法是什么？我是否必须使用一个 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());

来自Java documentation对于 binarySearch 方法，返回值将是:

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.

您指定的索引是您想要的。