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


У меня есть объект, который определяет "естественный порядок сортировки" с помощью Comparable. Они хранятся в наборах деревьев.

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

7 67

7 ответов:

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

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

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

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

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

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

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

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

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

но вы должны убедиться, что никто не может изменить элемент без "Вы", чтобы сделать это.

EDIT: также! Застекленные списки имеют некоторую поддержку только для этого:

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

Я искал эту проблему, когда пытался реализовать кинетическую панель прокрутки, похожую на прокрутки колес 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());
    }
}

The DoubleExpression может занять некоторое время, чтобы быть привязанным к задаче runLater платформы JavaFX, поэтому индекс включен в этот класс-оболочку.

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

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

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

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

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

Я не думаю, что есть способ сделать это из коробки.

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

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