Trouver la position de l'élément dans une Java TreeMap

Une fois que vous avez construit votre arbre de carte, copie de ses triés clés dans un tableau, et l'utilisation Tableaux.binarySearch pour rechercher l'index en O(logN). Si vous avez besoin de la valeur, faire une recherche sur la carte originale, trop.

Edit: c'est la façon dont vous la copie de clés dans un tableau

String[] mapKeys = new String[treeMap.size()];
int pos = 0;
for (String key : treeMap.keySet()) {
    mapKeys[pos++] = key;
}

OriginalL'auteur dasblinkenlight

Une solution alternative serait d'utiliser TreeMap's headMap méthode. Si le mot existe dans le TreeMap, puis le size() de sa tête la carte est égal à l'indice du mot dans le dictionnaire. Il est peut-être un peu de gaspillage par rapport à mes autres questions, par.

Ici est de savoir comment vous code en Java:

import java.util.*;

class Test {
    public static void main(String[] args) {
        TreeMap<String,String> tm = new TreeMap<String,String>();
        tm.put("quick", "one");
        tm.put("brown", "two");
        tm.put("fox", "three");
        tm.put("jumps", "four");
        tm.put("over", "five");
        tm.put("the", "six");
        tm.put("lazy", "seven");
        tm.put("dog", "eight");
        for (String s : new String[] {
            "quick", "brown", "fox", "jumps", "over",
            "the", "lazy", "dog", "before", "way_after"}
        ) {
            if (tm.containsKey(s)) {
                //Here is the operation you are looking for.
                //It does not work for items not in the dictionary.
                int pos = tm.headMap(s).size();
                System.out.println("Key '"+s+"' is at the position "+pos);
            } else {
                System.out.println("Key '"+s+"' is not found");
            }
        }
    }
}

Ici est la sortie produite par le programme:

Key 'quick' is at the position 6
Key 'brown' is at the position 0
Key 'fox' is at the position 2
Key 'jumps' is at the position 3
Key 'over' is at the position 5
Key 'the' is at the position 7
Key 'lazy' is at the position 4
Key 'dog' is at the position 1
Key 'before' is not found
Key 'way_after' is not found

OriginalL'auteur dasblinkenlight

J'ai eu le même problème. Alors j'ai pris le code source de java.util.TreeMap et écrit IndexedTreeMap. Il implémente mon propre IndexedNavigableMap:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

La mise en œuvre est basée sur la mise à jour du nœud de poids dans le rouge-noir arbre lorsqu'il est modifié. Le poids est le nombre de nœuds enfants en dessous d'un nœud donné, en plus de soi - même. Par exemple, lorsqu'un arbre est tourné vers la gauche:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight simplement les mises à jour des poids jusqu'à la racine:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

Et quand nous avons besoin de trouver l'élément à l'index ici est la mise en œuvre qui utilise des pondérations:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Également très pratique de trouver l'indice d'une clé:

    public int keyIndex(K key) {
if (key == null) {
throw new NullPointerException();
}
Entry<K, V> e = getEntry(key);
if (e == null) {
throw new NullPointerException();
}
if (e == root) {
return getWeight(e) - getWeight(e.right) - 1;//index to return
}
int index = 0;
int cmp;
if (e.left != null) {
index += getWeight(e.left);
}
Entry<K, V> p = e.parent;
//split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
while (p != null) {
cmp = cpr.compare(key, p.key);
if (cmp > 0) {
index += getWeight(p.left) + 1;
}
p = p.parent;
}
} else {
Comparable<? super K> k = (Comparable<? super K>) key;
while (p != null) {
if (k.compareTo(p.key) > 0) {
index += getWeight(p.left) + 1;
}
p = p.parent;
}
}
return index;
}

Je vais mettre en œuvre IndexedTreeSet bientôt, en attendant vous pouvez utiliser le jeu de clés de IndexedTreeMap.

Mise à jour: IndexedTreeSet est mis en œuvre maintenant.

Vous pouvez découvrir le résultat de ce travail à https://github.com/geniot/indexed-tree-map

OriginalL'auteur Vitaly Sazanovich

Avez-vous pensé à rendre les valeurs dans votre TreeMap contenir la position de votre dictionnaire? Je suis à l'aide d'un BitSet ici pour mon fichier de détails.

Cela ne fonctionne pas presque aussi bien que mon autre idée ci-dessous.

Map<String,Integer> dictionary = new TreeMap<String,Integer> ();
private void test () {
//Construct my dictionary.
buildDictionary();
//Make my file data.
String [] file1 = new String[] {
"1", "3", "5"
};
BitSet fileDetails = getFileDetails(file1, dictionary);
printFileDetails("File1", fileDetails);
}
private void printFileDetails(String fileName, BitSet details) {
System.out.println("File: "+fileName);
for ( int i = 0; i < details.length(); i++ ) {
System.out.print ( details.get(i) ? 1: -1 );
if ( i < details.length() - 1 ) {
System.out.print ( "," );
}
}
}
private BitSet getFileDetails(String [] file, Map<String, Integer> dictionary ) {
BitSet details = new BitSet();
for ( String word : file ) {
//The value in the dictionary is the index of the word in the dictionary.
details.set(dictionary.get(word));
}
return details;
}
String [] dictionaryWords = new String[] {
"1", "2", "3", "4", "5"
};
private void buildDictionary () {
for ( String word : dictionaryWords ) {
//Initially make the value 0. We will change that later.
dictionary.put(word, 0);
}
//Make the indexes.
int wordNum = 0;
for ( String word : dictionary.keySet() ) {
dictionary.put(word, wordNum++);
}
}

Ici la construction de l'détails du fichier consiste en une seule recherche dans le TreeMap pour chaque mot dans le fichier.

Si vous avez l'intention d'utiliser le value dans le dictionnaire TreeMap pour quelque chose d'autre, vous pouvez toujours composer avec un Integer.

Ajouté

De penser à elle, si le value domaine de la Map est réservé pour quelque chose, vous pouvez toujours utiliser les touches spéciales permettant de calculer leur propre position dans le Map et à agir comme des Strings à des fins de comparaison.

private void test () {
//Dictionary
Map<PosKey, String> dictionary = new TreeMap<PosKey, String> ();
//Fill it with words.
String[] dictWords = new String[] {
"0", "1", "2", "3", "4", "5"};
for ( String word : dictWords ) {
dictionary.put( new PosKey( dictionary, word ), word );
}
//File
String[] fileWords = new String[] {
"0", "2", "3", "5"};
int[] file = new int[dictionary.size()];
//Initially all -1.
for ( int i = 0; i < file.length; i++ ) {
file[i] = -1;
}
//Temp file words set.
Set fileSet = new HashSet( Arrays.asList( fileWords ) );
for ( PosKey key : dictionary.keySet() ) {
if ( fileSet.contains( key.getKey() ) ) {
file[key.getPosiion()] = 1;
}
}
//Print out.
System.out.println( Arrays.toString( file ) );
//Prints: [1, -1, 1, 1, -1, 1]
}
class PosKey
implements Comparable {
final String key;
//Initially -1
int position = -1;
//The map I am keying on.
Map<PosKey, ?> map;
public PosKey ( Map<PosKey, ?> map, String word ) {
this.key = word;
this.map = map;
}
public int getPosiion () {
if ( position == -1 ) {
//First access to the key.
int pos = 0;
//Calculate all positions in one loop.
for ( PosKey k : map.keySet() ) {
k.position = pos++;
}
}
return position;
}
public String getKey () {
return key;
}
public int compareTo ( Object it ) {
return key.compareTo( ( ( PosKey )it ).key );
}
public int hashCode () {
return key.hashCode();
}
}

NB: Suppose qu'une fois que getPosition() a été appelé, le dictionnaire n'est pas changé.

OriginalL'auteur OldCurmudgeon