当对象更改值时维护 TreeSet 排序

Question

我有一个使用 Comparable<> 定义“自然排序顺序”的对象。 这些存储在 TreeSet 中。

除了删除并重新添加对象之外，当用于定义排序顺序的成员更新时，是否还有其他方法来更新排序？

Answer 1

正如其他人所指出的，没有内置的方法。但是您始终可以使用您选择的构造函数对该 TreeSet 进行子类化，并添加所需的功能：

public class UpdateableTreeSet<T extends Updateable> extends TreeSet<T> {

    // definition of updateable
    interface Updateable{ void update(Object value); }

    // constructors here
    ...

    // 'update' method; returns false if removal fails or duplicate after update
    public boolean update(T e, Object value) {
       if (remove(e)) {
           e.update(value);
           return add(e);
       } else { 
           return false;
       }
    }
}

从那时起，您将必须调用 ((UpdateableTreeSet)mySet).update(anElement, aValue)< /code> 更新排序值和排序本身。这确实需要您在数据对象中实现额外的 update() 方法。

Answer 2

我遇到了类似的问题，找到了这个线程和 tucuxi 的答案（谢谢！），基于此我实现了自己的 UpdateableTreeSet。我的版本提供了

• 迭代这样一个集合的方法，
• 从循环内安排（延迟）元素更新/删除，
• 而无需创建该集合的临时副本，并最终
• 在循环结束后将所有更新/删除作为批量操作进行。

UpdateableTreeSet 向用户隐藏了很多复杂性。除了延迟的批量更新/删除之外，tucuxi 所示的单元素更新/删除在类中仍然可用。

更新 2012-08-07：该类可在一个小 GitHub 存储库 中找到，其中包括带有原理图示例的介绍性自述文件代码以及单元测试显示如何（不）更详细地使用它。

Answer 3

如果您确实需要使用Set，那么我想您就不走运了。

不过，我将添加一个通配符 - 如果您的情况足够灵活，可以使用 List 而不是 Set，那么您可以使用 Collections .sort() 根据需要对 List 重新排序。如果 List 顺序不需要做太多改变，这应该是高性能的。

Answer 4

唯一内置的方式就是删除并重新添加。

Answer 5

它有助于了解您的对象是否会发生小增量或大增量变化。如果每次更改都非常小，那么最好将数据放入保持排序的列表中。为此，您必须

1. 进行二进制搜索来查找元素的索引，
2. 修改该元素
3. 当该元素大于其右侧邻居时
4. ，将其与其右侧邻居交换，或者如果没有发生：当该元素小于其左侧邻居时邻居，将其与其左侧邻居交换。

但你必须确保没有人可以在不通过“你”的情况下更改该元素。

编辑：还有！ Glazed Lists对此有一些支持：

http ://publicobject.com/glazedlists/glazedlists-1.5.0/api/ca/odell/glazedlists/ObservableElementList.html

Answer 6

当我尝试实现类似于苹果 iPhone 滚轮滚动的动态滚动窗格时，我发现了这个问题。 TreeSet 中的项目是此类：

/**
 * Data object that contains a {@code DoubleExpression} bound to an item's
 * relative distance away from the current {@link ScrollPane#vvalueProperty()} or
 * {@link ScrollPane#hvalueProperty()}. Also contains the item index of the
 * scrollable content.
 */
private static final class ItemOffset implements Comparable<ItemOffset> {

    /**
     * Used for floor or ceiling searches into a navigable set. Used to find the
     * nearest {@code ItemOffset} to the current vValue or hValue of the scroll
     * pane using {@link NavigableSet#ceiling(Object)} or
     * {@link NavigableSet#floor(Object)}.
     */
    private static final ItemOffset ZERO = new ItemOffset(new SimpleDoubleProperty(0), -1);

    /**
     * The current offset of this item from the scroll vValue or hValue. This
     * offset is transformed into a real pixel length of the item distance from
     * the current scroll position.
     */
    private final DoubleExpression scrollOffset;

    /** The item index in the list of scrollable content. */
    private final int index;

    ItemOffset(DoubleExpression offset, int index) {
        this.scrollOffset = offset;
        this.index = index;
    }

    /** {@inheritDoc} */
    @Override
    public int compareTo(ItemOffset other) {
        double d1 = scrollOffset.get();
        double d2 = other.scrollOffset.get();

        if (d1 < d2) {
            return -1;
        }
        if (d1 > d2) {
            return 1;
        }

        // Double expression has yet to be bound
        // If we don't compare by index we will
        // have a lot of values ejected from the
        // navigable set since they will be equal.
        return Integer.compare(index, other.index);
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return index + "=" + String.format("%#.4f", scrollOffset.get());
    }
}

DoubleExpression 可能需要一些时间才能绑定到 JavaFX 平台的 runLater 任务中，这就是索引包含在此的原因包装类。

由于 scrollOffset 始终根据用户在滚轮上的滚动位置而变化，因此我们需要一种更新方法。通常顺序总是相同的，因为偏移量是相对于项目索引位置的。索引永远不会改变，但偏移量可能为负或正，具体取决于项目距 ScrollPane 的当前 vValue 或 hValue 属性的相对距离。

要仅在需要时按需更新，只需遵循 Tucuxi 上述答案的指导即可。

ItemOffset first = verticalOffsets.first();
verticalOffsets.remove(first);
verticalOffsets.add(first);

其中verticalOffsets是一个TreeSet。如果您打印出
每次调用此更新片段时设置，您都会看到它已更新。

Answer 7

我不认为有一种开箱即用的方法可以做到这一点。

您可以使用观察者模式，每当您更改元素内的值时通知树集，然后删除并重新插入它。

通过这种方式，您可以隐式地保持列表排序，而不必关心手动操作。当然，这种方法需要通过修改插入行为（设置观察/通知机制）来扩展 TreeSet 。刚刚添加的项目）