précédent | suivant | table des matières

TreeMap

Le conteneur TreeMap permet de stocker des couples (clé, valeur), dans une structure d’arbre binaire équilibré rouge-noir. Cette classe garantit que la collection Map sera triée selon un ordre croissant, conformément à l'ordre naturel des clés ou à l'aide d'un comparateur fourni au moment de la création de l'objet TreeMap.

public class TreeMap<K,V>extends AbstractMap<K,V>
                         implements SortedMap<K,V>, Cloneable, java.io.Serializable {
   private transient Comparator<? super K> comparator = null;
   private transient Entry<K,V> root = null;

1 Les constructeurs :

public TreeMap() {
}

public TreeMap(Comparator<?  super K> c) {
   this.comparator = c;
}

public TreeMap(Map<? extends K, ? extends V> m) {
   putAll(m);
}

Pour construire un TreeMap à partir d'un autre TreeMap, on peut s'y prendre comme précédemment, mais ceci va occasionner des restructurations de l'arbre au fur et à mesure des ajouts : la méthode buildFromSorted est faite pour éviter toutes ces restructurations :

public TreeMap(SortedMap<K, ? extends V> m) {
   comparator = m.comparator();
   try{
      buildFromSorted(m.size(), m.entrySet().iterator(),null, null);
   } catch (java.io.IOException cannotHappen) {
   } catch (ClassNotFoundException cannotHappen) {
   }
}

2 Les méthodes :

Les interrogations :

int size()

Retourne le nombre de couples (clé, valeur) contenus dans ce TreeMap.

 
Comparator<? super K> comparator()
 Retourne le Comparator utilisé par le TreeMap, ou null si le TreeMap n'utilise pas de Comparator. 
boolean containsKey(Object cle)
 Retourne true si le TreeMap contient la clé cle. 
boolean containsValue(Object valeur)
 Retourne true si le TreeMap contient la valeur valeur. 
V get(Object cle)
 Retourne la valeur associée à la clé cle. 
K firstKey()
 Retourne la première clé du TreeSet(la plus petite). Lève une exception NoSuchElementException si le TreeMap est vide. 
K lastKey()
 Retourne la dernière clé du TreeSet(la plus grande). Lève une exception NoSuchElementException si le TreeMap est vide.

Les modifications :

void clear()
 Supprime tous les couples (clés, valeur) du TreeMap. 
V put (K cle, V valeur)
 Range un nouveau couple (clé, valeur) dans le TreeMap,  et retourne :
  • l'ancienne valeur si la clé était déjà présente.
  • null si la clé n'était pas présente.
 
void putAll( Map<? extends K, ? extends V> map)
 Ajoute tous les élément de map au TreeMap. 
V  remove(Object cle)
 Enlève le couple (clé, valeur) associée  à cle, et retourne :
  • la valeur si le couple existe dans le TreeMap.
  • null si le couple n'existe pas dans le TreeMap.

Les vues sur un TreeMap :

Set <Map.Entry<K ,V >>entrySet()
 Retourne l'ensemble des couples (clé, valeur) sous forme de Set. Permet  d'obtenir un iterateur sur le TreeMap. Un modification du TreeMap entraîne une modification du Set et vice versa.   Les opérations add et addAll ne sont pas autorisées pour  le Set. 
Set<K> keySet()
 Retourne une vue Set du TreeMap. Un modification du TreeMap entraîne une modification du Set et vice versa.   Les opérations add et addAll ne sont pas autorisées pour  le Set. 
Collection<V> values()
 Retourne une vue Collection  de ce TreeMap. Une modification du TreeMap entraîne une modification de la Collection, et vice versa.  Les opérations add et addAll ne sont pas autorisées pour  la Collection.

Les sous TreeMap :

SortedMap<K,V>headMap(K  jusqua)
 Retourne un TreeMap contenant tous les couples (clé, valeur) jusqu'à la clé jusqua exclue. 
SortedMap<K,V> subMap(K cleDepuis, K cleJusqua)
 Retourne un TreeMap contenant tous les couples (clé, valeur) depuis la clé cleDepuis incluse, jusqu'à la clé cleJusqua exclue. 
SortedMap<K,V> tailMap(K cleDepuis)
 Retourne un TreeMap contenant tous les couples (clé, valeur) depuis la clé cleDepuis incluse.

Pour créer une vue Collectionsur le TreeMap, on crée une classe locale, dérivée de AbstractCollection, qui définit iterator, size, contains, remove, et clear. La Collection n'est pas fabriquée, elle est représentée dans le TreeMap,et ce qui est retourné est simplement une vue.

public Collection<V> values() {
   if (values == null) {
      values = new AbstractCollection<V>() {
         public Iterator<V> iterator() {
            return new ValueIterator();
         }
         public int size() {
            return TreeMap.this.size();
         }

         public boolean contains(Object o) {
            for (Entry<K,V> e = firstEntry(); e != null; e = successor(e))
               if (valEquals(e.getValue(), o)) return true;
            return false;
         }
         public boolean remove(Object o) {
            for (Entry<K,V> e = firstEntry(); e != null; e = successor(e)) {
               if (valEquals(e.getValue(), o)) {
                  deleteEntry(e);
                  return true;
               }
            }
            return false;
         }

         public void clear() {
            TreeMap.this.clear();
         }
      };
   }
   return values;
}

haut de la page