Tree Object structure

[PollerJava]

Hallo,

ich habe ein spezielles Problem, und zwar hab ich unteren Baum mit einem DOM- Parser eingelesen.
So weit so gut, Jetzt möchte (bzw muss) ich aus diesem Baum eine Objektstruktur erzeugen und zwar so in der Art

CustomerNode     (z.B.: Customer1)
  |-- GroupNodeList   
         |-- GroupNode (NAME,PATH)   NAME ist hier z.B.: Path11 PATH ist Customer1
                |-- NodeList
                |     |-- Node[0]     (wenn Path11 ein leaf hätte, dann wäre Node[1] das leaf, da Path11 kein leaf hat, muss man es terminieren)
                |-- GroupNodeList
                      |-- GroupNode
                             |-- NodeList
                                    |-- Node[0] (Path11 hat keine unter "node" mehr, daher terminieren)

          ...

d.h also, dass ich den Tree unten in so ein Objektgebilde abbilden muss und wenn es keine "Unterknoten" mehr gibt, dann muss dieser mit einem Array der länge [0] terminiert werden (z.B.: Node[0]).
Ich bin mir jetzt nicht sicher, wie ich das am Besten mache, ich kenne die Struktur des Trees nicht, muss diesen aber irgendwie durchlaufen um die Object- Struktur zu bekommen.
Wie würdet Ihr das machen, einfach von oben nach unten durchlaufen oder kennt jemand einen besseren Vorschlag?
Vielleicht hat jemand einen Tipp, wie man das am einfachsten hinbekommen könnte.
Vielen Dank,
lg

[XML]
<tree>
<customer name="Customer1">
<node name="Path11" />
<node name="Path12">
<leaf name="item11" />
</node>
<node name="Path13">
<node name="Path131">
<leaf name="item12" />
<leaf name="item13" />
</node>
</node>
</customer>
<customer name="Customer2">
<node name="Path21">
<leaf name="item21" />
<leaf name="item22" />
<leaf name="item23" />
</node>
<node name="Path22">
<node name="Path221">
<node name="Path2211">
<leaf name="item221" />
<node name="Path2111">
<node name="Path21111">
<node name="Path211111">
<leaf name="item222" />
<leaf name="item223" />
</node>
</node>
</node>
</node>
</node>
</node>
</customer>
</tree>
[/XML]

 

[maki]

Würde das entweder mit In Order Traversing oder Pre Order Traversing machen.

 

[SlaterB]

hast du einen DOM-Tree in Java vorliegen?
kannst du elementar damit umgehen, z.B. alle Knoten durchlaufen und diese ausgeben?

dann musst du ihn also verarbeiten, Schritt für Schritt in einen anderen Baum umwandeln,
hast du entsprechende Node-Klassen vorhanden oder sonst ein Model bereit, was du erstellen willst
(Standard-Nodes mit bestimmten Namen)?

die Hauptverarbeitung könnte rekursiv aussehen:

MyNode verarbeiteDomNode(DomNode x) {
// Rekursion: erstelle Liste neuer MyNodes aus DomNode-Children von x

// nun den MyNode zu x erstellen:
// - wenn keine Kinder, dann MyNode mit leeren Array oder was du da komisches erzählt hast
// - wenn alle Kinder komische Nodes mit leeren Array sind (im Volksmund 'Leaf'), dann MyNode NodeList
erstellen?
// - wenn irgendeines der Kinder NodeList ist, dann ist x ein GroupNodeList-MyNode
// usw.
}

alle deine Regeln einbauen, wie du da die Kette von
> GroupNodeList, GroupNode, GroupNodeList, GroupNode, NodeList, Node[0]
begründest habe ich noch nicht verstanden, aber vielleicht hängt das auch vom Inhalt des DomNodes x zusammen,
den habe ich im obigen Schema noch gar nicht berücksichtig, aus Path211111 kann man vielleicht irgendwas erkennen

für den Anfang solltest du nicht versuchen, nicht wirklich alles sofort einzubauen,
wäre schon gut wenn du allein zwischen Blättern und inneren Knoten unterscheiden könntest

 

[PollerJava]

Besten Dank für die schnellen Antworten.

>>hast du einen DOM-Tree in Java vorliegen?
>>kannst du elementar damit umgehen, z.B. alle Knoten durchlaufen und diese ausgeben?

Ja das funktioniert, in einer rekursiven Methode kann ich alle Nodes des DOM- BAUMS der Reihe nach ausgeben, so wie diese in
der XML- Datei stehen.

>> hast du entsprechende Node-Klassen vorhanden

ja, hab ich, dass sind eh die CustomerNode, GroupNodeList, GroupNode, NodeList, ...

>>begründest habe ich noch nicht verstanden, aber vielleicht hängt das auch vom Inhalt des DomNodes x zusammen,

Der fertige Tree wird mittels eines WebServices bereitgestellt und ein Client des WebService ließt dann unter anderem so aus:

public Set<Node> gatherItems(CustomerNode[] customers) {

		for (CustomerNode customer : customers) {

			gatherItems(customer.getGroupList());

			gatherItems(customer.getList());

		}

		return new HashSet<Node>(nodes.values());

	}



	private void gatherItems(GroupNode[] groups) {

		for (Node group : groups) {
                                // wenn ein leaf null wäre, würde man hier eine NPE bekommen
			gatherItems(group.getGroupList());
             // wenn aber Node[0] istm dann wird einfach die iteration beendet
			gatherItems(group.getList());

		}

	}



	private void gatherItems(Node[] nodes) {

		for (Node node : nodes)

			addNode(convert(node));

	}

Also es müssen alle nodes, die keine leaf haben, mit einem Node[0] leaf terminiert werden, da sonst am Client eine NPE auftritt

Mir ist noch nicht ganz klar wie ich den Tree durchlaufen soll -> so weit ichs versteh von oben nach unten, also In Order Traversiong, so wie von maki vorgeschlagen, oder?

 

[SlaterB]

es gibt nur drei Order, wenn du die Begriffe noch nie gehört hast kannst du sie jetzt nachschlagen,
ansonsten würde ich das nicht als eine wesentliche Info ansehen

du durchläufst den Baum, fängst bei der Wurzel an, und dann eben arbeiten

 

[maki]

ansonsten würde ich das nicht als eine wesentliche Info ansehen

Richtig, eher als Tipps für Suchbegriffe

 

[PollerJava]

Ok, das ist mir klar, also ich laufe den Tree von oben nach unten durch (also rekursiv den DOM- Baum durchgehen), mit dem Anhängen eines ChildNodes an den richtigen ParentNode, da hab ich noch meine Bedenken wie ich im Code wissen soll, dass z.B.: Path12 an den Customer1 Node gehängr gehört und nicht an Path11.

Wie würdest Du das machen, damit die Nodes an die richtigen ParentNodes gehängt werden.
Vielen Dank!!

 

[SlaterB]

das ist kein Problem, siehe meinen Pseudo-Code oben oder jede beliebigen rekursiven Durchlauf eines Baums,

da hat man einen Node als Parameter (x) und durchläuft dann unter anderen dessen Children,
die im Laufe der Methode x zugeordnet werden, nicht viel falsch zu machen

 

[PollerJava]

Also das heißt, du würdest der Methode convertDomNode den ersten Node übergeben (in meinem Fall <customer name="Customer1">) und diesen dann so durchlaufen, wie du beschrieben hast (also Rekursiv), also würde dann eh der ganze DOM- Baum der Reihe nach durchlaufen.

d.h dann auch, dass du gar nicht unterscheiden würdest zwischen CUSTOMER, NODE und LEAF, so wie ich das gemacht habe in der Methode createTree.
Versteh ich das richtig so?
lg

PS: mit der Methode createTree lese ich den DOM- Baum aus (rekursiv), ich hoff das passt so.

private void createTree(final Node node) {
        final short type = node.getNodeType();
        switch (type) {
            case Node.ELEMENT_NODE: {
                final String name = node.getNodeName();
                final NamedNodeMap attrs = node.getAttributes();                          
                final Node attribute =  attrs.item(0);
                final String nodeValue = attribute.getNodeValue();               
                if(name.equals(DOMParser.CUSTOMER)) {                                                  // CustomerNode(NAME)                  
                    }
                else if(name.equals(DOMParser.NODE)) {                                                                 
                    }
                else if(name.equals(DOMParser.LEAF)) {                                            
                    }
                System.out.println("NODE: " + name + "=" + nodeValue + "\t " + getPath(node));
                final NodeList children = node.getChildNodes();
                if (children != null) {
                    int length = children.getLength();
                    for (int i = 0; i < length; i++) {
                        createTree(children.item(i));   // rekursion
                        }
                    }
                break;
                }
            }
        }

    private Node convertDomNode(final Node node) {
        // Rekursion: erstelle Liste neuer Nodes aus DomNode-Children von x
        // nun den Node zu x erstellen:
        // - wenn keine Kinder, dann MyNode mit leeren Array oder was du da komisches erzählt hast
        // - wenn alle Kinder komische Nodes mit leeren Array sind (im Volksmund 'Leaf'), dann MyNode NodeList erstellen?
        // - wenn irgendeines der Kinder NodeList ist, dann ist x ein GroupNodeList-MyNode
        // usw.
        return null;
        }

 

[SlaterB]

convertDomNode() brauchst du kaum noch wenn du schon createTree() hast, eine Methode dürfte erstmal reichen

was in jedem Fall noch fehlt, und deine vorherige Frage betrifft, ist die Zusammenführung der neuen Elemente,
irgendwo muss stehen wer Kind von wem ist,
Zeile 20 bietet sich an, da werden neue Nodes für die Kinder erstellt, allerdings nur per Rekursion quasi in anderer Methode,
der neue Node könnte als Rückgabewert wieder ins Spiel kommen, den dann dem in Zeile 13-15 erstellten Hauptnode des aktuellen Methodendurchlaufs als Kind zuweisen

 

[PollerJava]

Das ist mir jetzt ein bisschen zu schnell, also die Methode createTree(Node node) wird das erste mal mit dem Root- Node aufgerufen, also bei mir der Node "Customer1". Aus diesem Node wird dann der Type bestimmt, und wenn es sich um ein ELEMENT_NODE handelt, dann wird der Name und die Attribute ausgegeben und es wird die Methode createTree mit dem ersten Child von "Customer1" aufgerufen und dann gehts rekursiv so weiter ...


den Satz "da werden neue Nodes für die Kinder erstellt" versteh ich nicht ganz -> so viel ich versteh werden, gibt es die Nodes ja schon, es werden nur die Kind-Nodes ausgegeben, also für "Customer1" werden "Path11", "Path12" und "Path13" ausgegeben oder lieg ich da falsch?

so viel versteh ich, Mir ist jetzt nicht klar, was ich genau in Zeile 20 und in Zeile 13-15 machen muss.
wäre es vielleicht möglich, dass du mir da pseudocode reinschreibst?
Vielen Dank.

 

[SlaterB]

Pseudo-Code steht schon in meiner ersten Antwort,
was die Methode grundsätzlich machen soll muss man natürlich vorher überlegen,
wie man an meinem Pseudo-Code + Text erkennnt gehe ich davon aus, dass du die Dom-Nodes in andere Nodes umwandeln willst,
du hast ja auch wie selbst geschrieben CustomerNode, GroupNodeList, GroupNode, NodeList usw.

bisher enthält deine Methode createTree() noch nichts davon, aber ist ja ok in einer frühen Version,
das musst du nun schon selbst programmieren:
zum übergebenen Parameter ein neues Node-Objekt (x) erstellen, für die Kinder auch (rekursiv) und die Kinder dem richtigen Parent zuordnen, eben gerade x

 

[PollerJava]

Also die Zuweisung zum richtigen Parent bereitet mir noch Kopfzerbrechen, bin ich da auf dem richtigen Weg, hast Du das so ungefähr gemeint?

    AbstractTreeNode parentNode = null;
    AbstractTreeNode childNode = null;
    private AbstractTreeNode createTree(final Node node) {
        final short type = node.getNodeType();
        switch (type) {
            case Node.ELEMENT_NODE:
                if(parentNode != null)
                    parentNode.setServiceList(childNode);
                parentNode = new ServiceGroupNode();
                final NodeList children = node.getChildNodes();
                if (children != null) {
                    for (int i = 0, n = children.getLength(); i < n; i++) {
                        if(children.item(i).ELEMENT_NODE == children.item(i).getNodeType()) {
                            childNode = createTree(children.item(i));
                            }
                        }
                    }
                break;            
            }
        return parentNode;
        }

 

[SlaterB]

sieht ja gut aus, du hast den parentNode in Zeile 9 und die childNode in Zeile 14,
jetzt nur noch z.B.
parantNode.addNewChild(childNode);
in Zeile 15

Zeile 1 und 2 solltest du entfernen, bei Rekursion sind solche Variablen außen sehr fehlerträchtig,
es geht alles innen,
Zeile 7 und 8 sind dann auch bedenklich, bevor der parentNode in Zeile 9 überhaupt erst erstellt wird

 

[PollerJava]

Fertig:

    private AbstractTreeNode createTree(final Node node) {
        AbstractTreeNode parentNode = null; 
        final short type = node.getNodeType();
        switch (type) {
            case Node.ELEMENT_NODE:
                parentNode = new ServiceGroupNode();
                final NodeList children = node.getChildNodes();
                if (children != null) {
                    for (int i = 0, n = children.getLength(); i < n; i++) {
                        if(children.item(i).ELEMENT_NODE == children.item(i).getNodeType()) {
                            final AbstractTreeNode childNode = createTree(children.item(i));
                            parentNode.addList(childNode);
                            }
                        }
                    }
                break;            
            }
        return parentNode;  
        }

 

[SlaterB]

wegen return musst du keine Variable extern deklarieren, vor dem switch reicht,
jede Methode gibt einen SubTree zurück, richtig, einen Parent der entweder ein Blatt ist oder eine Menge Unterknoten enthält,
ganz am Anfang wurde die Methode von jemand anders mit dem Root des DomTrees aufgerufen, und bei diesem ersten Aufruf kommt richtigerweise der Root des neuen Trees zurück,
alles passt zusammen

edit:
> parentNode.setServiceList(childNode);
klingt komisch, das wird ja evtl. für mehrere Children aufgerufen, werden die alle aufgenommen oder immer nur eine Variable serviceList überschrieben, wie bei set-Methoden üblich?

addChild() wäre deutlicher für mehrere verschiedene Children oder von mir aus addServiceList()

 

[PollerJava]

Aja, da werden die einzelnen rekursiven Methodenaufrufe am Stack abgelegt und dann in umgekehrter Reihenfolge abgearbeitet, da war der Denkfehler begraben,
Vielen Dank für Deine Mühe!!

 

[PollerJava]

edit:
> parentNode.setServiceList(childNode);
klingt komisch, das wird ja evtl. für mehrere Children aufgerufen, werden die alle aufgenommen oder immer nur eine Variable serviceList überschrieben, wie bei set-Methoden üblich?

addChild() wäre deutlicher für mehrere verschiedene Children oder von mir aus addServiceList()

Das muss ich mir noch genauer anschauen, ich muss ja auch mit "leafs" (Node[0]) terminieren und so,
setServiceList hab ich jetzt mal hingeschrieben zum Verständnis, kann aber leicht sein, dass es eh add... heißt -> das muss ich mir erst anschaun, die Klassen und die Methoden (mit denen ich den DOM- Baum in meinen Baum umwandeln muss) sind alle vorgegeben.

 

[PollerJava]

Hallo,

muss leider noch mal fragen, ich habs jetzt so programmiert, damit ich meinen Tree aus dem DOM bekomme aber leider fehlen manche Nodes in meinem Tree.
Hat vielleicht jemand einen Ahnung was da falsch ist.
Vielen Dank!
lg

private AbstractServiceTreeNode createTree(final Node node) {
        AbstractServiceTreeNode parentNode = null;
        switch (node.getNodeType()) {
            case Node.ELEMENT_NODE:

                // get information for DOM- Node
                final String name = node.getNodeName();
                final NamedNodeMap attrs = node.getAttributes();
                final Node attribute =  attrs.item(0);
                final String nodeValue = attribute.getNodeValue();                

                // create appropriate node
                if(name.equals(DOMParser.CUSTOMER))
                    parentNode = new CustomerNode();                                      
                else if(name.equals(DOMParser.NODE))
                    parentNode = new ServiceGroupNode();                  
                else if(name.equals(DOMParser.LEAF)) 
                    parentNode = new ServiceDetails();                   
                parentNode.setName(nodeValue);
                parentNode.setPath(getPath(node));

                // run through child- nodes of the DOM parent- node
                final NodeList children = node.getChildNodes();
                if (children != null) {
                    for (int i = 0, n = children.getLength(); i < n; i++) {
                        if(children.item(i).ELEMENT_NODE == children.item(i).getNodeType()) {
                            // run the method recursively
                            final Node childNode = children.item(i);
                            final String childNodeName = childNode.getAttributes().item(0).getNodeValue();
                            final AbstractServiceTreeNode child = createTree(childNode);
                            final Class<?> clazz = child.getClass();
                            // append the child to the right parent
                            if(parentNode instanceof CustomerNode) {            // an einem Customer kann nur ein ServiceGroupNode(Site) oder ein ServiceDetails(Device) hängen
                                if(child instanceof ServiceGroupNode) {         // parent = CustomerNode, child = ServiceGroupNode
                                    final ServiceGroupNodeList serviceGroupNodeList = new ServiceGroupNodeList();
                                    final ServiceGroupNode serviceGroupNode = (ServiceGroupNode)child;
                                    serviceGroupNodeList.addServiceGroupNode(serviceGroupNode);
                                    ((CustomerNode)parentNode).setServiceGroupList(serviceGroupNodeList);
                                    }
                                else if(child instanceof ServiceDetails) {      // parent = CustomerNode, child = ServiceDetails
                                    final ServiceNodeList serviceNodeList = new ServiceNodeList();
                                    final ServiceNode[] serviceNode = new ServiceNode[1];
                                    serviceNode[0] = (ServiceNode) child;
                                    serviceNodeList.setServiceNode(serviceNode);
                                    ((CustomerNode)parentNode).setServiceList(serviceNodeList);
                                    }
                                }
                            else if(parentNode instanceof ServiceGroupNode) {   // an einer ServiceGroupNode kann nur eine weitere ServiceGroupNode(Site) oder ein ServiceDetails(Device) hängen
                                if(child instanceof ServiceGroupNode) {         // parent = ServiceGroupNode, child = ServiceGroupNode
                                    final ServiceGroupNodeList serviceGroupNodeList = new ServiceGroupNodeList();
                                    final ServiceGroupNode serviceGroupNode = (ServiceGroupNode)child;
                                    serviceGroupNodeList.addServiceGroupNode(serviceGroupNode);
                                    ((ServiceGroupNode)parentNode).setServiceGroupList(serviceGroupNodeList);
                                    }
                                else if(child instanceof ServiceDetails) {      // parent = ServiceGroupNode, child = ServiceDetails
                                    final ServiceNodeList serviceNodeList = new ServiceNodeList();
                                    final ServiceNode[] serviceNode = new ServiceNode[1];
                                    serviceNode[0] = (ServiceNode) child;
                                    serviceNodeList.setServiceNode(serviceNode);
                                    ((ServiceGroupNode)parentNode).setServiceList(serviceNodeList);
                                    }
                                }
                            }
                        }
                    }
                break;            
            }
        return parentNode;
        }

 

[SlaterB]

ein einfacher Schritt wäre, bei jedem deiner ifs ohne finales else noch das else zu adden (5x in deinem Code!),
und diesen Fall dann zu dokumentieren
'bearbeite Node xy .., kann ihn nirgendwo zuordnen'

genauso geradezu simpel ist ein Log aller Aktionen,
'verarbaite Node ..., Anzahl Children = ..'
'mach daraus .. '
'verarbaite Child x von y von Parent z'
'mach daraus .. '

usw.
da du weißt wo etwas am Ende fehlt kannst du relativ gezielt genau diese Log-Stelle näher untersuchen

-----

inhaltlich kann ich ansonsten zu deinem Code nix sagen,
du hast diverse komplizierte Regeln, und ob nun ein Node mal nicht DOMParser.LEAF ist
oder ob es noch andere Parent/Child-Kombinationen als ServiceGroupNode + ServiceGroupNode gibt,
kann ich aus der Ferne nun wirklich nicht beurteilen

wenn es grundsätzlich klappt und nur Teile fehlen, dann deutet es wie gesagt auf Lücken in der Abdeckung durch die Regeln hin