Discussion :

[iubito]

Salut !
Je suis en train de chercher quelle structure conviendrait mieux à mon application.

Je veux avoir (en mémoire) pas de graphisme ( ) une structure (Tree? TreeMap? Node ?...) qui me permette d'avoir une arborescence simple, non triée.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Racine
+- 101 Dossier 1
+- 102 Dossier 2
|  +- 102/1 Sous-Dossier
|  +- 102/2 hop hop hop
+- 200 hop là !
...

avec à chaque fois un couple clé/texte, la clé étant un String que je défini moi même.

En gros, à chaque noeud un couple de String, et possibilité d'avoir des enfants.

Selon vous, quelle classe je devrais utiliser ? Parce qu'en regardant TreeMap et compagnie je vois que ça parle de tri et je n'en veux surtout pas !

Je n'ai pas beaucoup d'opérations à faire dessus, des ajouts d'enfants et de noeuds, et ensuite juste un parcours récursif.

[Debernad]

La structure des nodes est adapté à une arborescence ...
Il existe plusieurs interfaces ...
Par exemple, celle du xml : org.w3c.dom.Node
ou celle de swing : javax.swing.tree.TreeNode

Elles représentent uniquement des interfaces de structures de données ...
Pour Swing, il y a une implémentation qui javax.swing.tree.DefaultMutableTreeNode.

Qui te permettera de gérer une arborescence sans trop de difficulté incluant plusieurs méthodes trés utiles.

Cette classe est une structure de donnée et donc même si tu vois le mot swing dans le package , tu peux l'utiliser même si tu es sur un serveur Unix sans affichage graphique car il n'y a aucune dépendance graphique.

[c-top]

La classe suivante est destinée aux arbdres binaires et implémente directement la définition récursive de ces derniers.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
import java.util.*;
 
public class BinaryTree extends java.util.AbstractCollection
{ protected Object root;
  protected BinaryTree left, right, parent;
  protected int size;
 
  public BinaryTree()
  {
  }
 
  public BinaryTree(Object root)
  { this.root = root;
    size = 1;
  }
 
  public BinaryTree(Object root, BinaryTree left, BinaryTree right)
  { this(root);
    if (left != null)
    { this.left = left;
      left.parent = this;
      size += left.size();
    }
    if (right != null)
    { this.right = right;
      right.parent = this;
      size += right.size();
    }
  }
 
  public boolean equals(Object object)
  { if (!(object instanceof BinaryTree)) return false;
    BinaryTree tree = (BinaryTree)object;
    return ( tree.root.equals(root)
          && tree.left.equals(left)
          && tree.right.equals(right)
          && tree.parent.equals(parent)
          && tree.size == size);
  }
 
  public int hashCode()
  { return root.hashCode() + left.hashCode() + right.hashCode() + size;
  }
 
  public java.util.Iterator iterator()
  { return new java.util.Iterator()  // anonymous inner class
    { private boolean rootDone;
      private java.util.Iterator lit, rit;  // child iterators
      public boolean hasNext()
      { return !rootDone || lit != null && lit.hasNext()
                         || rit != null && rit.hasNext();
      }
      public Object next()
      { if (rootDone)
        { if (lit != null && lit.hasNext()) return lit.next();
          if (rit != null && rit.hasNext()) return rit.next();
          return null;
        }
        if (left != null) lit = left.iterator();
        if (right != null) rit = right.iterator();
        rootDone = true;
        return root;
      }
      public void remove()
      { throw new UnsupportedOperationException(); 
      }
    };
  }
  public int size()
  { return size;
  }
}

Pour tester

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
public class Test
{ static public void main(String[] args)
  { BinaryTree e = new BinaryTree("E");
    BinaryTree g = new BinaryTree("G");
    BinaryTree h = new BinaryTree("H");
    BinaryTree i = new BinaryTree("I");
    BinaryTree d = new BinaryTree("D",null,g);
    BinaryTree f = new BinaryTree("F",h,i);
    BinaryTree b = new BinaryTree("B",d,e);
    BinaryTree c = new BinaryTree("C",f,null);
    BinaryTree tree = new BinaryTree("A",b,c);
    System.out.println("tree = " + tree);
  }
}

[iubito]

Si je me plante pas, mon arbre n'est pas binaire !
Si mes souvenirs sont bons, un arbre binaire a un tronc, et 2 branches qui peuvent avoir chacune seulement 2 branches... l'une est appelée droite, et l'autre gauche.

Dans mon cas je peux avoir des branches multiples (0, 1, 2, ... n), exactement comme dans du XML (sauf que je ne traite pas un xml dans mon appli )

J'essayerai donc le Node de com.w3c ou l'autre... demain au boulot !

[iubito]

Je pense partir sur le org.w3c.dom.Node qui me semble plus pratique.
Mais comme c'est une interface, quelle implémentation utiliser ?
Parce que le compilo n'apprécie pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Node N = new Node();

[Debernad]

En effet, c'est une bonne idée comme cela, si tu souhaite stocker ton arborescence de facon persistante, tu n'aura plus qu'à l'écrire en fichier XML qui est un standard que tu peux facilement réutiliser avec d'autres applications.

Pour l'implémentation, tu peux utiliser les classes du package "javax.xml.parsers"

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
DocumentBuilder db = dbf.newDocumentBuilder();
Document root = db.newDocument();

la classe Document est une interface qui hérite de Node, donc c'est ton noeud racine qui posséde des méthodes createXXXX() pour créer différentes types de noeud.
A toi de voir quel type de noeud te convient le mieux.
Ensuite, lorsque tes noeuds sont créés, il te suffit de les imbriquer entre eux grâce au méthodes de Node.

[iubito]

euh... en partant de mon root, si je veux ajouter des noeuds, c'est root.appendChile(Node monNoeud)

donc à chaque fois que j'ajoute un nouveau noeud, c'est un db.newDocument() ?

Je n'ai aucune envie de sauvegarder mon bazar en XML, c'était juste pour montrer à c-top que je voulais pas du binaire

[Debernad]

Je te donne un exemple de comment je ferais, juste à titre indicatif ...
Cet exemple produit un fichier XML afin d'avoir un visuel du résultat et donc un visuel de ton arborescence ...
Mais dans ton code tu pourras supprimer la derniére partie qui fait appelle au transformer.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
import org.w3c.dom.*;
import javax.xml.transform.*;
import javax.xml.transform.stream.*;
import javax.xml.transform.dom.*;
import javax.xml.parsers.*;
import java.io.*;
 
public class Test
{
	public static void main(String[] args) throws Exception
	{
		DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance(); 
		DocumentBuilder db = dbf.newDocumentBuilder(); 
		Document document = db.newDocument();
 
		Node racine = document.createElement("Dossier");
		document.appendChild(racine);
		Node dossier1 = ajoutDossier(racine,"101", "dossier 1");
		ajoutDossier(dossier1,"101/1", "dossier 1/1");
		Node dossier2 = ajoutDossier(racine,"102", "dossier 1");
		ajoutDossier(dossier2,"102/1", "dossier 2/1");
 
		TransformerFactory tf = TransformerFactory.newInstance();
		Transformer t = tf.newTransformer();
		t.transform(new DOMSource(document),new StreamResult(new File("toto.xml")));
	}
 
	public static Node ajoutDossier(Node parent,String cle, String text)
	{
		Element element = parent.getOwnerDocument().createElement("Dossier");
		element.setAttribute("cle",cle);
		element.setAttribute("text",text);
		parent.appendChild(element);
		return element;
	}
}

ce qui donne comme résultat, test.xml :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
<?xml version="1.0" encoding="UTF-8"?>
<Racine>
	<Dossier cle="101" text="dossier 1">
		<Dossier cle="101/1" text="dossier 1/1"/>
	</Dossier>
	<Dossier cle="102" text="dossier 1">
		<Dossier cle="102/1" text="dossier 2/1"/>
	</Dossier>
</Racine>

[iubito]

Super je vais essayer de me débrouiller avec ça

[iubito]

...j'ai rien dit...

[iubito]

Parcours de l'arbre...

Salut !
Avec un transformateur, j'arrive bien à obtenir un fichier XML très propre, c'est le pied ! Je vois que mon arbre est OK.

Maintenant je voudrais parcourir mon arbre :

J'ai donc une fonction "affichage" récursive qui parcours mon arbre, et affiche un truc tout bête, des tabulations, suivies de CLE puis de TEXTE.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
System.out.println(affichage(doc.getFirstChild(), 0));
 
	private String affichage(Node N, int profondeur) {
		String ret = "";
		Node fils;
		NamedNodeMap nnm;
		if (N != null) {
			if (N.hasChildNodes()) {
				fils = N.getFirstChild();
				while (fils != null) {
					nnm = fils.getAttributes();
					ret += "\n";
					for (int i = 0; i <= profondeur; i++)
						ret += "\t";
					ret += nnm.getNamedItem("cle") + " " + nnm.getNamedItem("texte");
					ret += affichage(fils, profondeur + 1);
					fils = fils.getNextSibling();
				}
			}
		}
		return ret;
	}

Le parcours est OK mais le problème est pour l'affichage de la valeur de CLE et de TEXTE à chaque noeud.
J'obtiens un résultat du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
	cle="500" texte="Boîte de réception"
	cle="100" texte="Dossier Annuel 31/12/2004"
		cle="100" texte="Compta"
			cle="100" texte="Etats Comptables"
		cle="105" texte="Factures d'achats"
	...

Comment juste afficher 500 et Boîte de réception sans tout le tralala autour ?
je galère là-dessus, j'suis sûr que c'est tout con comparé à ce que je suis arrivé à faire, mais j'trouve pas

[Debernad]

Je propose cela pour résoudre ton probléme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
  private String affichage(Node N, int profondeur) { 
      String ret = ""; 
      Node fils; 
      if (N != null) { 
         if (N.hasChildNodes()) { 
            fils = N.getFirstChild(); 
            while (fils != null) { 
               ret += "\n"; 
               for (int i = 0; i <= profondeur; i++) 
                  ret += "\t"; 
               ret += ((Element)fils).getAttribute("cle") + " " + ((Element)fils).getAttribute("texte"); 
               ret += affichage(fils, profondeur + 1); 
               fils = fils.getNextSibling(); 
            } 
         } 
      } 
      return ret; 
   }

[iubito]

MERCI !