Garder les objets mutables triés dans TreeSets en tout temps

Question

Il m'est apparu qu'un TreeSet ne conserve pas les objets mutables dans l'ordre de tri si les valeurs d'attribut d'objet sont modifiées plus tard. Par exemple,

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

La sortie est:

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

Après avoir changé de l'âge d'un élève en particulier, puis imprimez le TreeSet, le jeu ne semble plus dans l'ordre. Pourquoi cela arrive-t-il? et comment le garder trié toujours?

Answer 1

Pourquoi cela se produit-il?

Parce que le jeu ne peut pas moniteur tous ses objets pour les changements ... Comment serait-il capable de le faire ?! Le problème se pose également pour HashSets. Vous ne pouvez pas modifier les valeurs affectant un code de hachage d'objet lorsqu'un HashSet contient l'objet.

et comment le garder trié toujours?

Vous supprimez généralement l'élément de l'ensemble, la modifier, puis réinsérez. En d'autres termes, le changement

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

Vous pouvez également utiliser par exemple une liste, et appelez Collections.sort sur la liste chaque fois que vous avez modifié un objet.

Answer 2

Ceci est un problème générique avec Maps et Sets. Les valeurs sont insérées en utilisant le hashCode/equals/compare au moment de l'insertion, et si les valeurs sur lesquelles ces méthodes sont basées changent, alors les structures peuvent bousiller. L'une des manières serait de retirer l'article de l'ensemble et de l'ajouter de nouveau après que la valeur ait été changée. Alors ce serait correct.

Answer 3

Vous pouvez utiliser le observer pattern. Laissez votre TreeSet mettre en œuvre Observer et laissez votre Student étendre Observable. Le seul changement que vous devez faire est de cacher le champ age par encapsulation afin que vous ayez plus de contrôle interne sur le changement.

Voici un exemple de coup d'envoi:

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

} 

et

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

Maintenant, faites un new ObservableTreeSet au lieu de 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(); 
    } 
}); 

Il est moche à première vue, mais vous vous retrouvez avec aucun changement dans le code principal. Il suffit de faire un s.setAge(24) et le TreeSet se "réorganisera" lui-même.

Answer 4

listes vitrés peuvent aider: http://www.glazedlists.com/

Je l'utilise pour son EventList et n'ont pas essayé de tri. Mais sur leur page d'accueil, ils présentent les caractéristiques principales:

en direct Tri signifie que votre tableau reste triée que vos modifications de données.

Answer 5

En général, il est préférable de garder manuellement triés Set/Map en continu constante (voir la stratégie mentionnée par @aioobe).

Cependant, parfois ce n'est pas une option. Dans ces cas, nous pouvons essayer:

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

ou avec une carte:

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

Mais cela ne fonctionne pas correctement, parce que même containsKey peut entraîner un résultat incorrect. Alors, que pouvons-nous faire avec une carte sale? Comment pouvons-nous actualiser une seule clé sans avoir à reconstruire toute la carte? Voici une classe utilitaire pour résoudre ce problème (peut être facilement converti pour gérer des ensembles):

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

Si votre problème est l'ordre d'itération, et vous ne voulez pas utiliser la fonctionnalité supplémentaire de TreeSet (headSet() etc.), puis utilisez HashSet avec l'itérateur personnalisé. De plus, il y a un problème majeur avec votre exemple: deux étudiants du même âge (cela arrive souvent) font des conflits.

Une solution possible:

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

    } 

}