Bonjour,
 
Le problème est le suivant :
 
J'ai un tableau HTML "normalisé".
 
Normalisé pour moi, ça veux dire :
Il n'y a pas de cellule avec des rowspan ou colspan inutiles.
Pas de cellule non utilisée.
 
Je cherche un algo en JavaScript (DOM) le plus efficace possible qui me donne pour une cellule les Numéros de ligne et de colonne.
 
Pour le moment le seul algo que je vois :
 
J'initialise un Array à 2 dimensions avec toutes les case à false.
 
Ensuite je fais plusieurs boucle:
Boucle sur les lignes TR
Je cherche la première case de l'Array à false
Boucle sur les TD de la ligne TR
Si c'est la cellule que je cheche, sa position est celle de la case trouvée
Sinon
- je met à true les case occupées pas la cellule (rowspan et colspan).
- Je cherche dans la ligne de l'Array la case suivante à false.
Fin boucle TD
Fin boucle TR
 
Exemple :
 
Tableau HTML

 
Array Javascript

Dans cet exemple, je cherche la position de la case X (Premier TD du Troisième TR)
En Remplissant de 1 l'Array JS avec les cases occupées par les cellules A, B, C, D, E et F, je trouve bien la position de ma cellule : Ligne 3, colonne 5.
 
Je me demande donc si y'a pas plus simple

Bon, y'a plus simple...
 
En fait un simple Array de n colonnes suffit :
 
Tableau HTML

 
Array Javascript init

 
Pour chaque cellule, on cherche dans l'Array le premier plus petit nombre. Ca donne le Numéro de ligne de la cellule.
On augmente le nombre de rowspan, pour les colspan colonnes de la cellule.
 
Traitement de A, le tableau devient :

 
Traitement de B, le tableau devient :

 
Traitement de C, le tableau devient :

 
Traitement de D, le tableau devient :

 
Traitement de E, le tableau devient :

 
Traitement de F, le tableau devient :

 
Traitement de X :
Fini, la position de X est : Ligne 3 colonne 5.

La fonction en JS :

 
curTable est une variable globale qui est le TBODY du tableau HTML sur lequel on travaille.

Un petit up pour dire que je peux avoir facilement le numéro de ligne de la cellule.
 
J'ai cherché, mais je ne vois pas en quoi ça peut aider à simplifier l'algo.
 
Si vous avez des idées, n'hésitez pas hein

Ce que ça donne pour le moment :
http://www.surleau.org/edit/tab.html
 
Manque l'ajout de colonne.
Peut-être pour demain matin...
 
PS : Si le lien ne marche pas, y'a celui-là :
http://www.surleau.com/edit/tab.html
mais ce sera pas forcément la dernière version.
M'enfin vu qu'il semble que je sois le seul intéressé  
 
Normalement, ça marche sous IE et Moz.

il est fou
impressionant en tous cas.
 
juste une question naive: c'est quoi l'interet de faire ça coté client?

Pour un Content Management Systems par exemple.
 
http://www.bris.ac.uk/is/projects/cms/ttw/ttw.html#os

par exemple ....
 
en tout cas, comme moins moins ... c'est impressionnant !
mais c'est vraiment ce faire chier pour peu de choses non !?

Explique pourquoi ?
 
Pour moi, je le fait pour 2 raisons :
 
- Je n'ai rien trouvé de satisfaisant dans les éditeurs existants. Il sont soit IE soient Moz et s'il font les 2, c'est avec du code spécifique. D'autre part il n'ont jamais toutes les fonctions dont j'ai besoin, et souvent, il sont buggués.
 
- J'ai trouvé que c'était un très bon exercice pour apprendre le DOM JS. Ca me permet de me familiariser avec et de trouver des solutions qui ne soient jamais propres à IE ou Moz.
 
Le seul trus qui reste spécifique à un browser, c'est la gestion du clavier :
windows.event.key pour IE alors que Moz passe un objet event à la fonction qui gère les événements onKey...
Je cherche en ce moment le moyen de rendre ce fonctionnement spécifique des browsers le plus générique possible pour le code JS.

d'accord avec toi, c'est un super exercice !
mais je vois pas bien l'intérêt de ce genre de feature pour un cms par exemple .... ca va permettre aux utilisateurs de generer du html avec des couleurs hideuses ou une mise en page foireuse. Ca risque *fort* de pourrir la charte graphique adoptée lors du deploiement du cms.
 
disons que de manière général, je ne suis pas convaincu par l'outil.
 
(...mais je ne connais pas ton contexte d'utilisation    )

L'outils permet juste à l'utilisateur de générer un tableau HTML pour présenter des infos tabulaires.
Le style du tableau poura ensuite être choisi parmis une liste prédéfinie conforme à la charte.
 
Ce n'est pas un outils global de mise en page, juste un composant. Pour le moment ce n'est que la partie de l'éditeur qui permet définir le layout du tableau.
Taille, style, contenu seront définis ailleur
 
Par exemple, pour le moment, je bosse "officiellement" sur la version 2 de lutece, le CMS open source de paris.fr
Dans lutece, il n'y a pas pour le momemnt de possibilité pour un rédacteur de générer un tableau.
Ce genre de choses :  
http://www.paris.fr/fr/Sport/equip [...] tarifs.ASP doit être généré à la main ou avec un outil externe. Le respect de la charte incombe au rédacteur et au responsable de publication.
 
Par ailleur je travaille, "Officieusement" cette fois, depuis plusieurs années à un CMS dont la vocation est d'être "HYPER SIMPLE".
J'écris le composant tableau pour mon propre CMS. Si j'arrive à faire quelque-chose de robuste, je pourais proposer de l'intégrer à lutece V2

Salut,
 
Alors déjà, il y a quelquechose dans ton algo que je pense qu'on peut éviter, c'est la recherche de la plus petite valeur dans x :
- quand tu es dans une même ligne, au moment où tu marques les positions occupées par une cellule, tu peux déjà en profiter pour augmenter j de la valeur de colspan, ceci permettant de réduire le temps de recherche
- ensuite, tu n'es pas obligé de chercher un minimum ... car tu connais la valeur de ce minimum vu que c'est le numéro de ligne en cours. Il te suffit donc de chercher la première occurence de ce numéro.
Je suis d'accord, ça ne réduira pas de beaucoup de temps de calcul mais bon c'est ça de gagné
 
Et j'ai une autre manière de trouver la position de x, en exploitant le fait que tu puisses facilement avoir le numéro de ligne de la cellule. Ca me permet de trouver en 6 étapes au lieu de 7 la position ... mais c'est un mauvais exemple du fait que les C prennent pas mal de place en largeur.  
En fait je m'occupe uniquement de la partie du tableau située entre le début et la position éventuelle de X ce qui devrait être plus rapide que de balayer toute la largeur.
J'explique par l'exemple :
X se trouve à la ligne 3, je fais donc un tableau de 3 éléments que je remplis de 1 :

 
(je le dis tout de suite, au fur et à mesure je me suis rendu compte que j'utilisais pas mal le dernier algo que tu as proposé )
Ces 3 valeurs indique la prochaine colonne libre pour les 3 premières rangées (et non l'inverse pour ton algo).
Je démarre de la première ligne du tableau HTML :
- Première cellule : A (1, 1) (colspan, rowspan)
  je modifie donc ma liste en conséquence :

 
je regarde si il y a encore des valeurs à 1 (en fait je mets dans une variable la colonne en cours) : OUI en ligne 2 => je regarde donc la ligne 2 :
- Cellule E (1, 2) =>

je vois que la colonne 1 est remplie ... je passe à la colonne 2.
Pour cela je cherche la première occurence de 2 ... c'est à la ligne 1 : je lis donc l'élément suivant à cette ligne :
- Cellule B (2, 4) =>

(je me fous des rangées suivantes)
Il n'y a plus de 2 ... je passe à 3 ... plus de 3 ... je passe à 4 (ya sûrement moyen d'optimiser ça, entre autre en notant lors du remplissage d'une colonne la plus petite valeur entrée ... ce qui permettra de voir que dans notre c'est 4 et non 3)
Je cherche la première occurence de 4 ... c'est en 1 :
- Cellule C (5, 2) =>

 
Je recherche la première occurence de 4 (on peut commencer à chercher à partir de la ligne 3 vu qu'on connaît la hauteur de C) : c'est à la ligne 3 !
On lit la prochaine cellule à la ligne 3 :
- Cellule F (1, 1) =>

Plus de 4 ... on passe à 5 ... premier 5 à la ligne 3 :
- Cellule X (1, 1) =>
on a gagné ! on peut donc lire colonne 5 =)
 
Un autre exemple (parce que cet exemple m'a posé des problèmes au début) :
on a  

 
on commence avec

(X à la ligne 4)
 
Cellule A (1, 1)

 
Cellule E (1, 1)

 
Cellule F (2, 2)

 
Cellule B (1, 2)

 
Cellule D (1, 3)

 
Cellule X (1, 1)
Bingo -> colonne 3, ligne 4
 
(Le problème que j'avais rencontré, c'est que j'utilisais tout d'abord la liste pour avoir la prochaine ligne de libre (comme dans ton algo) et avec le F qui débordait vers la droite je me suis rendu compte qu'il fallait changer d'orientation ... en accord avec le fait que j'analyser colonne par colonne au lieu de ligne par ligne)
 
Le problème c'est que tu ne pourrais pas faire

vu qu'il faut gérer plusieurs lignes en même temps ... faudrait pouvoir stocker l'élément cell de chaque ligne dans un tableau de dimension égale à celle de la liste (donc 4) et ensuite faire

si c'est possible.

J'ai lu vite fait
Je ne suis pas sûr d'avoir saisi l'idée, mais je vais voir çà.
En tout cas, je te remercie de ta contribution, t'es le premier à t'intéresser au problème
 
Sinon, je confirme, il est possible de stocker les cellules dans un tableau.

 
 
Bah en fait tu prends ton algo et tu lui fais faire une rotation de 90°    

et moi ma question?
 
 
(perso pour faire ce genre de truc je prefererais une syntaxe wiki-like - oui oui y'en a qui supportent les tableaux - à moins qu'il y ait un réél besoin de tableaux complexes? auquel je ferais qd meme le truc coté serveur... je critique pas je cherche à comprendre )

 
elle n'etait pas intéressante....

 
Tu fais comment 'Coté serveur' ?
Tu demande au rédacteur combien de lignes et de colonnes c'est çà ? -> Beaucoup trop limité pour moi

Done !

 
C'est plus rapide, j'ai testé.
1.2 secondes contre plus de 2 pour calculer les positions d'un tableau de 20*20
 
En fait l'algo est plus efficace car (en gros) il ne parcours pas les cellules situées à droite de celle que je cherche (pour un tableau simple).
 
J'ai conservé l'ancien algo pour la petite histoire, et pour avoir une solution de rechange si le nouveau devenait fou dans un cas tordu
 
Merci, pour la piste, c'est exactement ce que je cherchais. Quand on réfléchi à ce problème, intuitivement on se rends compte que pour trouver la position d'une cellule, il faut regarder ce qui se passe dans le coin supérieur gauche du tableau. Mais pour moi, la réflexion était perturbé par le fait que pour limiter la recherche à la partie gauche il falait connaitre l'info recherché J'ai donc passé pas mal de temps avec un papier et un crayon, à chercher une itération qui s'approche de la cellule par le plus court chemin. Jusqu'à ce que je vois des cellules qui bougent, qui change de couleur, cligottent, bref jusqu'à ce que je me réveille avec une matrice imprimée sur la figure
 
A+, il me reste l'insertion des colonnes...

bah non, la meme chose que coté client ... mais ça serait moins complexe grace au préexistant

 
Bah si tu n'avais pas dit qu'on pouvait avoir le numéro de ligne facilement ... l'algo que j'ai proposé serait revenu au même que le tien vu qu'il aurait fallu balayer entièrement le tableau de haut en bas pour chaque colonne ...
 
 
J'ai 2 remarques sur le code ... je sais pas si ça améliorera la vitesse mais on peut essayer :
 
- ici :

tu vas modifier le tableau aCol sur le nombre de rangée de la cellule or si elle a un rowspan à 20 et que tu sais que la cellule que tu cherches est à la ligne 3 ... tu vas faire 17 assignations en trop. Tu pourrais peut-être faire  

A noter le < remplacer par <= ou sinon tu mets linePos-i+1
Par contre un truc que je ne sais pas, c'est si l'interpréteur va réévaluer min(aCell[i].rowSpan,linePos-i) à chaque itération ? Si c'est le cas, vaudrait mieux en stocker le résultat avant la boucle. Je sais pas si tout ça permettra d'accélérer le script mais bon javascript n'a pas l'air très rapide.
 
- Autre remarque, j'ai vu que tu as amélioré l'algorithme dans le sens où tu ne recherches pas à chaque fois la ligne avec la plus petite valeur (où comme je l'avais proposé, celle avec la valeur de la colonne en cours de traitement). C'est pas plus mal dans un sens, car ça évite justement cette recherche.
Mais en fait y a un cas où ça pourrait ralonger le traitement :
A A A A B B B B C C C C
A A A A B B B B C C C C
D F X
 
au départ : 1, 1, 1
cellule A => 5, 5, 1
cellule D => 5, 5, 2 (là tu reviens à la ligne 1 dans ta version)
cellule B => 9, 9, 2
cellule F => 9, 9, 3 (idem)
cellule C => 13, 13, 3
cellule X => BINGO
 
ce que je veux dire, c'est que tu vas faire les cellules B et C pour rien alors que dès que tu as 5, 5, 1 tu devrais te concentrer sur la ligne 3 et tu trouverais X 3 cellules plus loin. Evidemment cela nécéssite de trouver la ligne avec le plus petit numéro mais comme j'avais proposé, ya des manières pour optimiser cela, soit en connaissant le numéro de colonne en cours et en évitant ainsi les comparaisons fastidieuses et aussi dans certains cas de balayer toutes les lignes, soit en repérant le minimum quand tu modifies les valeurs dans aCol.
Enfin je sais pas trop si cela accélèrera le processus ... je pense qu'il faut tester pour voir ... surtout dans les cas courants (mon cas extrême n'est pas forcemment le plus courant).
 

1 - for( j=0; i + j <= linePos && j < rowSpan; j++ )
C'est ce que j'avais fais dans un premier temps. En fait cette optimisation avait sautée quand je corrigeais des bugs.
 
2- OK, j'y avais pensé, mais j'ai du mal à être certain que cette optimisation fonctionne dans tous les cas
En fait, y'a un contre exemple :
A B C D E F G H I  
J K L M N O P Q R
S S S S S S S S T
U V W X Y Z
Si je cherche Z, en choisissant le plus petit n° de colonne, je vais tester B, C, D, E et K, L, M, N pour rien.
J'ai donc modifié l'algo comme suit :
Si je ne suis pas sur la ligne 1, je reste sur la même ligne i tant que aCol[i] < aCol[i-1] (Edit) et que aCol[i].rowSpan <= aCol[i-1].rowSpan.
 
Ce qui donne :
A, J, S, U, V, W, X, Y et Z !
 

 
EDIT : Correction il ne faut pas rester sur la même ligne si la cellule suivante a un rowSpan plus grand !

Ouep je suis d'accord    
 

 
Heu j'ai pas bien compris pourquoi c'était grave si la prochaine cellule avait un rowSpan supérieure à celui de la prochaine cellule de la ligne au-dessus ?  
 
Et puis, ya un autre contre-exemple (inspiré du tien) mais pour ton code :

On va s'attarder sur la ligne J K L M ... alors que ce n'est pas nécéssaire. Peut-être faudrait-t-il plutôt appliquer cette règle quand on est à la ligne de Z et ensuite remonter si nécéssaire d'1 ligne en 1 ligne tout en continuant de l'appliquer puis en redescendant quand c'est possible.
 
Exemple :

 
ca ferait dans l'ordre :
A
S
J
U
V
W (car U prend 2 de large)
on peut pas faire le X, on passe à la ligne du dessus
on peut pas faire le T car la ligne dessus a une valeur inférieure ... on remonte encore
K
L
T (on est descendu là)
X
Y
on remonte
mais on peut pas faire le D donc on remonte encore  
M
N
D (on est descendu donc)
et enfin Z
 
Ainsi on économise encore des cellules ... si on continue le script va faire le 20x20 en 0.1 seconde    
 
De plus, il ne devrait plus être nécéssaire de faire le

 
... sauf que dans le cas d'un tableau avec des cellules prenant toutes uniquement 1 case, ça restera plus rapide.
 

Ok, j'ai vu ce PB aussi, je vais voir si je peux modifier le code sans qu'il devienne imcompréhenssible
 
Sinon, je viens de faire l'ajout de colonne.
http://www.surleau.org/edit/tab.html
ou
http://www.surleau.com/edit/tab.html

Correction d'un bug + légère optimisation

 
Edit 2 : Encore un bug corrigé
// Si rowSpan > 1 il faut compter cette cellule seulement si les positions sont les mêmes pour les lignes en dessous

énorme !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Merci

Voilà pour ceux que ça intéresse l'algorithme qu'on a finalement obtenu :
 

 
et une deuxième méthode surprenante proposée par Mara's dad :
 

 
Et enfin les performances (en sec) de chaque algo sur un tableau de 20x20 cases pour obtenir la position de chacune des cases (interêt minime ... juste pour faire des comparaisons):

Autre version de la deuxième méthode :

 
Les perfs sont les mêmes, j'ai juste fait le calcul en 1 seule ligne.
C'est pas évident au premier abord, mais en fait curTable.offsetLeft vaut 0 ! donc:
 

Est équivalent à :

Donc à :

Or, A / ( B / C ) = ( A * C ) / B !
( Pour ceux qu'auraient oublié, par exemple, diviser par un demi revient à multiplier par deux )
Donc :

 
L'appel systématique de la fonction getNbCols() ne coûte quasiment rien, c'est la division qui est catastophique avec IE.
 
Sous IE, une seule division est plus lente que le parcours de plusieurs nodes dans TBODY !

 
détrompes-toi    
 
J'ai fait quelques tests :
 
- ta fonction avec juste des valeurs fixes à la place de oCell.offsetLeft*getNbCols() et de curTable.offsetWidth : 0.03s
- je rajoute la ligne getNbCols() sans récupérer la valeur retournée (je fais toujours la division avec les valeurs fixes): 0.13s
- je rajoute la ligne oCell.offsetLeft; (en n'utilisant toujours pas la valeur retournée : 3.00s  
- je rajoute la ligne curTable.offsetWidth; : 3.00s
Le fait de mettre l'une , l'autre ou les 2 dernières lignes amènent au même temps d'exécution.
 
Donc apparement IE fait un savant calcul à chaque fois (peut-être le même algo que tu voulais   ) pour connaître la position d'un objet, ce qui lui prend beaucoup de temps. Moz se débrouille mieux apparement ... il garde peut-être les coordonnées des différents objets ?

T'as raison, c'est pas la division, mais l'accès aux propriétés offset* !
C'est plus logique comme çà.