Java:拥有一个项目集合,其中每个项目都有一个字段"previousItem",订购集合的最有效方法是什么？

Question

我在未排序的集合中有一组分层项.这些项目中的每一项都有一个字段previousItem:

public class Item{
   public Item previousItem;
}

处理这些项目的最有效方法是什么,以便输出是一个集合,其中没有任何previousItem的Item是集合中的第一个Item,而每个后续项目的previousItem是集合中的前一个项目？

我的第一个想法是在Item类中实现Comparable接口:

public int compareTo(Item that) {
    final int BEFORE = -1;
    final int EQUAL = 0;
    final int AFTER = 1;

    if(this.previousItem==null){
        return BEFORE;
    }

    if(that.previousItem==null){
        return AFTER;
    }

    if(this.previousItem.equals(that){
        return AFTER;
    }else if(that.previousItem.equals(this){
        return BEFORE;
    }

    return EQUAL;
}

然后遍历项目并将它们添加到TreeSet:

SortedSet<Item> itemSortedSet = new TreeSet<Item>();
for (Item item : itemCollection) {
    itemSortedSet.add(item);
}

是否有更有效的方法(处理所需的时间更少/需要的迭代次数)来订购集合,使它们处于逻辑层次顺序？

Answer 1

你的比较器不起作用:它不提供传递性,即如果在A-> B-> C的情况下比较项目A和C,它将做错误的事情.

如果没有项目可以具有相同的先前项目,则您的Item对象基本上形成基本链接列表.如果您碰巧知道哪一个是最后一项,您可以从那里开始一个循环并解开整个结构:

Item last = ...;

while (last != null) {
    result.add(last)
    last = last.previousItem
}

如果您没有办法找出哪个项目是最后一项,那么您可以使用a IdentityHashMap将每个previousItem值映射到Item使用它的对象:

IdentityHashMap<Item,Item> m = new IdentityHashMap<Item,Item>(itemset.size());

for (Item i : itemset)
    m.put(i.previousItem, i);

Item i = m.get(null);

while (i != null) {
    result.add(i);

    i = m.get(i);
}

这将从没有上一个节点的项开始解开未分类的集合.

两种方法在项目数量上都具有大致线性的复杂性,但它们做出两个假设,在您的情况下可能无效:

• 每个项目只能是最多一个其他节点的前一项,即您的项目是列表而不是树.

• 那个项目只有一个"线程".

如果这些假设中的任何一个无效,您将需要一个更复杂的算法来对其进行排序.