Y a-t'il une classe pour ca ? (une sorte d'arbre)

Bonjour,

J'ai besoin d'utiliser une structure de donnee bien particuliere, je pense
qu'elle est assez connue, mais je ne sais pas si Java (jusqu'a 1.5) l'a ou
pas.

Explication : J'ai une liste d'objets representant des animations qui seront
jouee les une a la suite des autres.
J'ai la duree de chaque animation, donc je peux facilement connaitre a quel
temps t0 chacune commence et a quel temps t1 elle finit pour laisser la
suivante se jouer.

Probleme : Je dois implementer une fonction qui me renvoit l'objet animation
a partir d'un temps t donne. La methode debile et lente est de parcourrir
toute les animations a partir du debut de la liste pour trouver laquelle
sera jouee au temps t, mais c'est pas terrible de faire comme ca. La
meilleur solution serait d'utiliser un arbre equilibre que l'on puisse
mettre les animations avec le temps de debut de l'animation dans le noeud,
comme on est garanti de trouver l'anim en O(ln(n)).

Quelqu'un sait si la lib de Java a une telle structure de donnee ?

Si ya pas, je pense que je vais faire avec une dicotomie sur un tableau,
mais le O(ln(n)) n'est pas garanti si les tailles des anim sont vraiment
d'ordre de grandeur differente.

Merci,
Vincent

Si ya pas, je pense que je vais faire avec une dicotomie sur un tableau,
mais le O(ln(n)) n'est pas garanti si les tailles des anim sont vraiment
d'ordre de grandeur differente.

Là le O(ln(n)) est garanti !
Philippe

Si ya pas, je pense que je vais faire avec une dicotomie sur un
tableau,

mais le O(ln(n)) n'est pas garanti si les tailles des anim sont
vraiment

d'ordre de grandeur differente.

Là le O(ln(n)) est garanti !
Philippe

Je viens de realizer que je suis vraiment bete :
la dichotomie sur le tableau est forcement en O(ln(n)), ca ne depend pas
du

tout des durees des animations :p

J'ai jete un coup d'oeil sur le TreeMap, mais quand le temps t n'est pas
exactement le debut d'une anim, je n'ai pas moyen d'avoir l'anim en
question. t est une valeur quelconque.

Bref, j'utilise maintenant une dichotomie, et ya pas de pb.


Pour ceux qui veulent l'algo :

protected int getAnimationIndex(float timeInSeconds)
{
// we suppose indexMin < indexSup
int indexMin = 0;
int indexSup = sequence.length;

while (indexMin + 1 < indexSup)
{
int index = (indexMin + indexSup) / 2;

if (animationStartingTime[index] > timeInSeconds)
indexSup = index;
else if (animationStartingTime[index] <= timeInSeconds)
indexMin = index;
}

return indexMin;
}

Pourquoi n'utilises-tu pas une structure de données de type List
(ArrayList

ou LinkedList)
l'index de chaque objet dans la liste correspondant au rang dans la
séquence

de jeu
Tu parcours après avec un iterator et tu recupéres tes animations
séquentiellement selon l'ordre du play.Ces animations seront jouées ainsi
selon l'ordre que tu as défini dans la liste.
Je na sais si j'ai bien compris ton problème.