Utrzymywanie zmieniających się obiektów posortowanych w drzewkach przez cały czas

Question

Zauważyłem, że obiekt TreeSet nie zachowuje uporządkowanych obiektów w porządku posortowanym, jeśli wartości atrybutów obiektu zostaną później zmienione. Na przykład,

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 + "]"; 
    } 
} 

Wyjście jest:

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

Po zmienić wiek konkretnego ucznia, a następnie wydrukować TreeSet, zestaw nie wydaje się już posortowanych. Dlaczego to się dzieje? i jak go zawsze sortować?

Answer 1

Dlaczego tak się dzieje?

Ponieważ zestaw nie może monitorze wszystkich jej obiektów do zmian ... Jak to będzie w stanie to zrobić ?!

Ten sam problem występuje dla HashSets. Nie można zmienić wartości wpływających na kod mieszania obiektów, gdy obiekt ten posiada obiekt HashSet.

i jak go zawsze sortować?

Zazwyczaj usuwa się element z zestawu, modyfikuje go, a następnie ponownie wstawia. Innymi słowy, zmień

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

do

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

Można również użyć na przykład listy, i nazywają Collections.sort na liście za każdym razem masz zmodyfikowany obiekt.

Answer 2

Jest to ogólny problem z mapami i zestawami. Wartości wstawiane są za pomocą hashCode/equals/compare w momencie wstawienia, a jeśli wartości, na których oparte są te metody, zmieniają się, struktury mogą się zepsuć.

Jednym ze sposobów jest usunięcie elementu z zestawu i ponowne dodanie go po zmianie wartości. Wtedy byłoby to poprawne.

Answer 3

Możesz skorzystać z observer pattern. Pozwól swojemu operatorowi TreeSet wdrożyć Observer i pozwól, aby Twój Observer rozszerzył się. Jedyną zmianą, którą musisz wprowadzić, jest ukrycie pola age dzięki enkapsulacji, dzięki czemu masz większą kontrolę wewnętrzną nad zmianą.

Oto przykład kickoff:

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); 
    } 

} 

i

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 + "]"; 
    } 
} 

teraz zrobić new ObservableTreeSet zamiast 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(); 
    } 
}); 

Jest brzydki od pierwszego wejrzenia, ale kończy się bez zmian w głównym kodzie. Po prostu wykonaj polecenie "zmień kolejność" na s.setAge(24) i TreeSet.

Answer 4

szkliwione Listy mogą pomóc: http://www.glazedlists.com/

Używam go do swojej listy zdarzeń i nie próbował sortowania. Ale na ich stronie głównej listy one główne cechy:

żywo Sortowanie oznacza tabela pozostaje klasyfikowane jako swoich zmian danych.

Answer 5

Generalnie najlepiej jest trzymać swoje ręcznie sortowane Set/Map ciągły spójne (patrz strategię wspomniany przez @aioobe).

Czasami jednak nie jest to opcja. W takich przypadkach możemy spróbować to:

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

lub z mapą:

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

Ale to nie będzie działać poprawnie, ponieważ może doprowadzić nawet containsKey z nieprawidłowym wynikiem.

Co możemy zrobić z brudną mapą? Jak odświeżyć pojedynczy klucz, bez konieczności odbudowywania całej mapy? Oto klasy narzędzie do rozwiązania tego problemu (można łatwo przekształcić do obsługi zestawów):

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; 
     } 

    } 

} 

Answer 6

Jeśli problem jest kolejność iteracji, a nie chcesz korzystać z dodatkowych funkcjonalności TreeSet (headSet() itp.), a następnie użyj HashSet z niestandardowym iteratorem. Ponadto istnieje duży problem z twoim przykładem: dwóch studentów w tym samym wieku (często zdarza się) popełnia konflikt.

Możliwym rozwiązaniem:

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(); 
     } 

    } 

}