поддержание сортировки TreeSet при изменении значения объекта

Question

У меня есть объект, который определяет «естественный порядок сортировки», используя Comparable <>. Они хранятся в TreeSets.

Кроме удаления и повторного добавления объекта, есть ли другой способ обновить сортировку, когда обновляются элементы, используемые для определения порядка сортировки?

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), чтобы обновить значение сортировки и саму сортировку. Это требует от вас реализации дополнительного update() метода в вашем объекте данных.

Answer 2

У меня была похожая проблема, я нашел эту ветку и ответ tucuxi (спасибо!), На основе которого я реализовал свой собственный UpdateableTreeSet. Моя версия предоставляет средства для

• перебрать такой набор,
• расписание (отложенное) обновление / удаление элементов из цикла
• без необходимости создания временной копии набора и, наконец,
• делать все обновления / удаления как массовую операцию после завершения цикла.

UpdateableTreeSet скрывает большую сложность от пользователя. В дополнение к отложенному массовому обновлению / удалению в классе по-прежнему доступны одноэлементное обновление / удаление, как показано tucuxi.

Обновление 2012-08-07: Класс доступен в небольшом репозитории GitHub , включая вводный README со схематическим примером кода, а также модульные тесты, показывающие, как (не) использовать его более подробно.

Answer 3

Если вам действительно нужно использовать Set, значит, вам не повезло, я думаю.

Я собираюсь добавить подстановочный знак, хотя - если ваша ситуация достаточно гибкая, чтобы работать с List вместо Set, то вы можете использовать Collections.sort() для повторной сортировки List по запросу, по требованию. Это должно быть производительным, если порядок List не нужно сильно менять.

Answer 4

Я искал эту проблему, когда пытался внедрить кинетическую панель прокрутки, аналогичную прокрутке колес Apple 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 может потребоваться некоторое время, чтобы быть связанным в задаче runLater платформы JavaFX, поэтому индекс включен в этот класс-оболочку.

Поскольку scrollOffset всегда меняется в зависимости от положения пользовательской прокрутки на колесе прокрутки, нам необходим способ обновления. Обычно порядок всегда одинаков, так как смещение относительно позиции индекса элемента. Индекс никогда не изменяется, но смещение может быть отрицательным или положительным в зависимости от относительного расстояния элементов от текущего свойства vValue или hValue ScrollPane.

Чтобы обновить по требованию, только когда это необходимо , просто следуйте указаниям вышеупомянутого ответа Tucuxi.

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

, где verticalOffsets - это TreeSet<ItemOffset>. Если вы делаете распечатку из устанавливайте каждый раз, когда вызывается этот фрагмент обновления, вы увидите, что он обновляется.

Answer 5

Это помогает узнать, будут ли ваши объекты меняться небольшими шагами или большими. Если каждое изменение очень мало, вы бы очень хорошо поместили свои данные в список, который вы сортируете. Для этого вам нужно

1. binarySearch, чтобы найти индекс элемента
2. изменить элемент
3. пока элемент больше своего правого соседа, поменяйте местами его правого соседа
4. или если этого не произошло: хотя элемент меньше, чем его левый сосед, поменяйте его местами с левым соседом.

Но вы должны убедиться, что никто не может изменить элемент, не пройдя через «вы», чтобы сделать это.

РЕДАКТИРОВАТЬ: Также! Glazed Lists имеет некоторую поддержку:

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

Answer 6

Только встроенным способом является удаление и повторное добавление.

Answer 7

Я не думаю, что есть готовый способ сделать это.

Вы можете использовать шаблон наблюдателя , который уведомляет древовидную структуру при каждом изменении значения внутри элемента, а затем удаляет и повторно вставляет его.

Таким образом, вы можете неявно сохранять отсортированный список, не заботясь о том, чтобы сделать это вручную. Конечно, этот подход должен будет расширить TreeSet, изменив поведение вставки (установив наблюдаемую / уведомляющую механику только что добавленного пункт)