Mantener los objetos mutables ordenados en TreeSets en todo momento

Question

Me di cuenta de que un TreeSet no mantiene los objetos mutables en orden si los valores de los atributos del objeto se modifican más adelante. Por ejemplo,

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 salida es:

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

Luego de cambiar la edad a un estudiante en particular y, a continuación, imprimir el TreeSet, el conjunto ya no se parece en forma ordenada. ¿Por qué pasó esto? y cómo mantenerlo ordenado siempre?

Answer 1

¿Por qué sucede esto?

Dado que el conjunto no puede monitor de todos sus objetos de cambios ... ¿Cómo sería capaz de hacer eso ?!

El mismo problema se presenta para HashSets. No puede cambiar los valores que afectan a un código hash de objetos cuando HashSet contiene el objeto.

y cómo mantenerlo ordenado siempre?

Por lo general, quita el elemento del conjunto, modificarlo, y luego vuelva a insertarla. En otras palabras, cambiar

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

a

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

También se puede utilizar, por ejemplo, una lista, y llamar Collections.sort en la lista cada vez que se haya modificado un objeto.

Answer 2

Este es un problema genérico con Maps and Sets. Los valores se insertan utilizando hashCode/equals/compare en el momento de la inserción, y si los valores en los que se basan estos métodos cambian, entonces las estructuras pueden arruinarse.

Una forma sería eliminar el elemento del conjunto y volver a agregarlo después de que se haya cambiado el valor. Entonces sería correcto.

Answer 3

Puede hacer uso del observer pattern. Deje que su TreeSet implemente Observer y deje que su Student extienda Observable. El único cambio que necesita hacer es ocultar el campo age por encapsulación para que tenga más control interno sobre el cambio.

Aquí está un ejemplo patada de salida:

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

} 

e

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

Ahora hacen un new ObservableTreeSet en lugar 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(); 
    } 
}); 

Es feo a primera vista, pero terminas sin cambios en el código principal. Simplemente haga un s.setAge(24) y el TreeSet se "reordenará".

Answer 4

listas esmaltadas pueden ayudar: http://www.glazedlists.com/

lo uso para su EventList y no han intentado clasificar. Pero en su página principal que la lista de las principales características:

vivo Ordenación significa que su mesa se mantiene ordenadas como los cambios de datos.

Answer 5

En general, lo mejor es mantener manualmente ordenados Set/Map continua constante (véase la estrategia mencionada por @aioobe).

Sin embargo, a veces esto no es una opción. En estos casos podemos probar esto:

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

o con un mapa:

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

Pero esto no va a funcionar correctamente, porque incluso containsKey puede dar lugar a un resultado incorrecto.

Entonces, ¿qué podemos hacer con un mapa sucio? ¿Cómo podemos actualizar una sola clave sin tener que reconstruir todo el mapa? Aquí es una clase de utilidad para resolver este problema (se puede convertir fácilmente para manejar conjuntos):

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 su problema es el orden de iteración, y que no quieren utilizar la funcionalidad adicional de TreeSet (headSet() etc.), luego use HashSet con un iterador personalizado. Además, hay un problema importante con su ejemplo: dos estudiantes de la misma edad (a menudo sucede) crean conflictos.

Una posible solución:

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

    } 

}