Постоянное хранение изменяемых объектов в TreeSets - PullRequest
Новая
       2

Постоянное хранение изменяемых объектов в TreeSets

11 голосов
/ 07 ноября 2011

До меня дошло, что TreeSet не сохраняет изменяемые объекты в отсортированном порядке, если значения атрибутов объекта будут изменены позже. Например, 

public class Wrap { 
    static TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>(){
        @Override
        public int compare(Student o1, Student o2) {            
            return o1.age - o2.age;
        }       
    }); 
    public static void main(String []args){
        Student s = new Student(10);
        ts.add(s); 
        ts.add(new Student(50));
        ts.add(new Student(30));
        ts.add(new Student(15));
        System.out.println(ts);
        s.age = 24;      //Here I change the age of a student in the TreeSet
        System.out.println(ts);     
    }
}
class Student{
    int age;
    Student(int age){
        this.age = age;
    }   
    @Override
    public String toString() {
        return "Student [age=" + age + "]";
    }   
}

Вывод: 

[Student [age=10], Student [age=15], Student [age=30], Student [age=50]]
[Student [age=24], Student [age=15], Student [age=30], Student [age=50]]

После того, как я изменил возраст конкретного ученика, а затем распечатал TreeSet, набор, похоже, перестал сортироваться. Почему это происходит? и как сохранить его всегда отсортированным?

Ответы [ 6 ]

11 голосов
/ 07 ноября 2011

Почему это происходит?

Поскольку набор не может отслеживать все свои объекты на предмет изменений ... Как он мог бы это сделать?!

Та же проблема возникает для HashSets. Вы не можете изменять значения, влияющие на хеш-код объекта, когда HashSet содержит объект.

и как сохранить сортировку всегда?

Обычно вы удаляете элемент из набора, изменяете его, а затем снова вставляете. Другими словами, изменить 

s.age = 24;      //Here I change the age of a student in the TreeSet

до 

ts.remove(s);
s.age = 24;      //Here I change the age of a student in the TreeSet
ts.add(s);

Вы также можете использовать, например, список и вызывать Collections.sort в списке каждый раз, когда вы изменяете объект.

7 голосов
/ 07 ноября 2011

Вы можете использовать шаблон наблюдателя . Пусть ваш TreeSet реализует Observer, а ваш Student расширится Observable. Единственное изменение, которое вам нужно сделать, - это скрыть поле age путем инкапсуляции, чтобы иметь больше внутреннего контроля над изменением.

Вот начальный пример: 

public class ObservableTreeSet<O extends Observable> extends TreeSet<O> implements Observer {

    public ObservableTreeSet(Comparator<O> comparator) {
        super(comparator);
    }

    @Override
    public boolean add(O element) {
        element.addObserver(this);
        return super.add(element);
    }

    @Override
    @SuppressWarnings("unchecked")
    public void update(Observable element, Object arg) {
        remove(element);
        add((O) element);
    }

}

и 

public class Student extends Observable {

    private int age;

    Student(int age) {
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        if (this.age != age) {
            setChanged();
        }

        this.age = age;

        if (hasChanged()) {
            notifyObservers();
        }
    }

    @Override
    public String toString() {
        return "Student [age=" + age + "]";
    }
}

Теперь сделайте new ObservableTreeSet вместо new TreeSet. 

static TreeSet<Student> ts = new ObservableTreeSet<Student>(new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getAge() - o2.getAge();
    }
});

Это на первый взгляд безобразно, но в итоге вы не вносите никаких изменений в основной код. Просто сделайте s.setAge(24) и TreeSet сам "переупорядочит".

1 голос
/ 07 ноября 2011

Это общая проблема с картами и наборами. Значения вставляются с использованием hashCode / equals / compare в момент вставки, и если значения, на которых основаны эти методы, меняются, структуры могут испортиться.

Один из способов - удалить элемент из набора и повторно добавить его после изменения значения. Тогда это будет правильно.

0 голосов
/ 10 августа 2016

Если ваша проблема в порядке итерации, и вы не хотите использовать дополнительные функции TreeSet (headSet() и т. Д.), То используйте HashSet с пользовательским итератором. Кроме того, в вашем примере есть серьезная проблема: два ученика одного возраста (часто это бывает) вступают в конфликт.

Возможное решение: 

public class Main {

    public static void main(final String[] args) {
        MagicSet<Student> ts = new MagicSet<Student>(new Comparator<Student>() {

            @Override
            public int compare(Student student1, Student student2) {
                return student1.age - student2.age;
            }

        });

        Student s = new Student(10);

        ts.add(s); 
        ts.add(new Student(50));
        ts.add(new Student(30));
        ts.add(new Student(15));

        System.out.println(ts); // 10, 15, 30, 50
        s.age = 24;
        System.out.println(ts); // 15, 24, 30, 50
    }

    public static class Student {

        public int age;

        public Student(int age) {
            this.age = age;
        }

        @Override
        public String toString() {
            return "Student [age=" + age + "]";
        }

    }

    public static class MagicSet<T> extends HashSet<T> {

        private static final long serialVersionUID = -2736789057225925894L;

        private final Comparator<T> comparator;

        public MagicSet(Comparator<T> comparator) {
            this.comparator = comparator;
        }

        @Override
        public Iterator<T> iterator() {
            List<T> sortedList = new ArrayList<T>();
            Iterator<T> superIterator = super.iterator();
            while (superIterator.hasNext()) {
                sortedList.add(superIterator.next());
            }
            Collections.sort(sortedList, comparator);
            return sortedList.iterator();
        }

    }

}
0 голосов
/ 27 июля 2016

Как правило, лучше вручную сохранять отсортированные значения Set / Map непрерывно согласованными (см. Стратегию, упомянутую @aioobe).

Однако иногда это не вариант. В этих случаях мы можем попробовать это: 

if (treeSet.contains(item)) {
    treeSet.remove(item);
    treeSet.add(item);
}

или с картой: 

if (treeMap.containsKey(key)) {
    Value value = treeMap.get(key);
    treeMap.remove(key);
    treeMap.put(key, value);
}

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

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

public class MapUtil {

    /**
     * Rearranges a mutable key in a (potentially sorted) map
     * 
     * @param map
     * @param key
     */
    public static <K, V> void refreshItem(Map<K, V> map, K key) {
        SearchResult<K, V> result = MapUtil.searchMutableKey(map, key);
        if (result.found) {
            result.iterator.remove();
            map.put(key, result.value);
        }
    }

    /**
     * Searches a mutable key in a (potentially sorted) map
     * 
     * Warning: currently this method uses equals() to check equality.
     * The returned object contains three fields:
     * - `found`: true iff the key found
     * - `value`: the value under the key or null if `key` not found
     * - `iterator`: an iterator pointed to the key or null if `key` not found
     * 
     * @param map
     * @param key
     * @return
     */
    public static <K, V> SearchResult<K, V> searchMutableKey(Map<K, V> map, K key) {
        Iterator<Map.Entry<K, V>> entryIterator = map.entrySet().iterator();
        while (entryIterator.hasNext()) {
            Map.Entry<K, V> entry = entryIterator.next();
            if (key.equals(entry.getKey())) {
                return new SearchResult<K, V>(true, entry.getValue(), entryIterator);
            }
        }
        return new SearchResult<K, V>(false, null, null);
    }

    public static class SearchResult<K, V> {

        final public boolean found;

        final public V value;

        final public Iterator<Map.Entry<K, V>> iterator;

        public SearchResult(boolean found, V value, Iterator<Map.Entry<K, V>> iterator) {
            this.found = found;
            this.value = value;
            this.iterator = iterator;
        }

    }

}
0 голосов
/ 04 февраля 2015

Застекленные списки могут помочь: http://www.glazedlists.com/

Я использую его для EventList и не пробовал сортировать. Но на своей домашней странице они перечисляют основные функции:

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

...