首页 文章

在TreeSet中查找相等的元素

提问于
浏览 次
0

我正在发展一些元素的历史观点 . 每个元素都有一个开始和结束日期 . 期间可能不重叠，因此每个开始日期必须等于或晚于其前任的结束日期 . 如果结束日期为空，则元素从其开始日期开始有效，直到结束日期已知 .

出于测试目的，我创建了这个类：

public class Entry implements Comparable<Entry>
{
    Integer start;
    Integer end;

    public Entry(Integer s, Integer e)
    {
        start = s;
        end = e;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (obj instanceof Entry)
        {
            return compareTo((Entry) obj) == 0;
        }
        return false;
    }

    @Override
    public int compareTo(Entry o)
    {
        if (o.end != null // other ends before or when this starts
                && (o.end.equals(start) || o.end < start ))
        {
            return 1;
        }
        if (end != null // other starts after or when this ends
                && (o.start.equals(end) || o.start > end ))
        {
            return -1;
        }
        return 0;
    }
}

我使用TreeSet对元素进行排序 . 现在我遇到的问题是我无法获得当前活动或首先出现的元素 .

查看JavaDoc的ceiling方法应该可以解决问题：

返回此set中大于或等于给定元素的最小元素，如果没有这样的元素，则返回null .

但这不起作用 .

在测试用例中，我使用一堆条目创建一个TreeSet：

TreeSet<Entry> ts = new TreeSet<Entry>();
ts.add(new Entry(1, 3));
ts.add(new Entry(3, 5));
ts.add(new Entry(5, 7));
ts.add(new Entry(7, 9));
ts.add(new Entry(9, 11));
ts.add(new Entry(11, 13));
ts.add(new Entry(13, 15));

然后我使用以下代码获取天花板：

ts.ceiling(new Entry(5, null));

我期望的结果是带有开始5和结束7的条目（'相等'条目） . 但结果是带有开始7和结束9的入口（更大的入口） . 两个结果都有资格等于或大于给定元素 . 但是由于JavaDoc提到它返回的元素最少，我期待5-7 Entry .

java treeset

1 回答

  • 2

    您正在定义什么是最小元素（通过定义 compareTo ） .

    而你自己也在说：

    “两项结果都是平等的”

    因此，当API引用最小元素时，它引用与有序集中的参数之后或等于（ceil）的元素 . 现在打印您订购的套装：

    [（1,3），（3,5），（5,7），（7,9），（9,11），（11,13），（13,15）]

    因此，天花板首先查找等于 5, null 的元素（意味着 compareTo 返回0），如果它找到一个返回该元素 . 你有两个相同的元素（所以不需要在那之后寻找一个） .

    这就是上限方法文档所引用的内容，即集合中的顺序（而不是通过设置某种新的比较） .

    public E ceiling（E e）返回此集合中的最小元素大于或等于给定元素

    见TreeSet#ceiling(E e) API

    所以它找到 5, 7 或 7,9 （它们都等于 5, null ）并返回它首先找到的那个，根据实现它是 7,9 .

    TreeSet实际上是幕后的树结构（doh），并且该树中哪个节点击中两个相等的节点取决于实现的细节和可能的插入顺序 .

    您的compareTo / equals不符合正常/推荐的规则（对于试图使用它们的树来说肯定是不好的） . 如果A和B相等且C和B相等，则A和C应相等，而compareTo函数则不然 .

    回复于

相关问题