Baum nach Stack plus Objektkonvertierung

[muckelzwerg]

Hey Leute, ich hab ein kleines Schönheitsproblem und suche einen guten Tipp.

Ich habe einen Baum, der mehr oder weniger über die Java Treenodes implementiert ist.
"getChildren()" steht zur Verfügung, um die Nachfahren zu ermitteln.
Jetzt wandele ich diesen Baum in eine Folge von Stackanweisungen um, die dann später sequentiell ausgeführt werden (Zeichnen).
Die Stimme aus dem Off ruft sofort nach "Rekursion", die will ich aber nicht verwenden.

Also arbeite ich "wie man das halt so macht", mit einer Queue.
Grober Pseudocode

	public ArrayList createDecendentsList(Node root){
		ArrayList destination = new ArrayList();
		ArrayList queue = new ArrayList();

		queue.add(root);
		Enumeration children;

		while( false == queue.isEmpty(){
			Node node = queue.remove(0);

            // Problemstelle 1
			destination.add(node);
			
			// Problemstelle 2
            "destination.add(new Push());"

			children = node.children();
			queue.addAll(0, Collections.list(children));

            // Problemstelle 3
            "queue.add(new Pop());"
			
		}
		return destination;
	}

Grundsätzlich funktioniert die Tiefensuche natürlich. Es gibt allerdings zwei Problemchen.
Zum einen müssen die Objekte umgewandelt werden, weil die Listen unterschiedliche Typen benötigen.
Jedesmal wenn ein Objekt aus der Queue in das Zielfeld übertragen wird, findet eine Typumwandlung statt.
Soweit ok, allerdings muss ich ja auch die "Pop"-Elemente in die Liste übertragen. Das Push-Element kann ich direkt im passenden Typ hineinschieben. Das Pop-Element muss aber zuerst mal in die Queue, damit es später an der richtigen Stelle eingefügt wird.
Das gibt dann ein ziemlich ekliges Gebrösel mit unterschiedlichen Objekttypen in der Queue und blöden Fallunterscheidungen ob das Objekt konvertiert (normaler Knoten) wird und ob es Kinder besitzt (normaler Knoten) oder ob es einfach nur kopiert wird (Pop) ...

Kommt noch jemand mit? Wenn ja, habt ihr eine Idee, wie man das einigermaßen sauber zurechtbasteln kann?

 

[SlaterB]

die Queue nimmt genau Node-Elemente auf, um Nodes geht, die Children sind Nodes, alle happy?
keine Typumwandlung nötig,

was sollen Pop und Push sein, welchen Zweck haben die?
wo brauchst du warum Kopien und können diese Kopien nicht auch Nodes sein?

 

[muckelzwerg]

Die Push und Pop Elemente werden benötigt um später beim Zeichnen die Hierarchie zu bewahren.
Unter OpenGL würde das in glPushmatrix und glPopmatrx umgesetzt werden.
Stell Dir vor Du hast Wurzel "a" mit den Kindern "b c d" und unterhalb von "b" nochmal ein "e" und darunter nochmal "f g".
(sorry hab grad kein Bild)
Daraus würde ein Term der Form
" a [ b [ e [ f ] [ g ] ] ] [ c ] [ d ] "
werden.
Die "[" entsprechen dem Push und legen später bei der Ausführung eine Kopie des aktuellen Zustandes (Transformationsmatrix) auf den Stack.
Die "]" entsprechen dem Pop und entfernen die letzte Transformationsmatrix um den Zustand von vorher zu erreichen.
Ein einfacheres Beispiel: Wurzel "a" mit den Kindern "b c d" wird zu
a [ b ] [ c ] [ d ]
entspricht:
- zeichne a
- speichere den zustand
- zeichne b als direkten nachfahren
- lade den alten zustand
- speichere den zustand
- zeichne c als direkten nachfahren
...

Das entspricht im Wesentlichen der Turtle-Grafik.

Um die schließenden Klammern richtig zu platzieren müssen sie mit in die Queue aufgenommen und später kopiert werden.
Genaugenommen wird jeder Nachfahre geklammert, aber das ändert nicht viel am Code. (eine Schleife mehr)

Im Zielarray werden keine Nodes verarbeitet. Selbst wenn, müsste ich bei Push und Pop wieder basteln, weil das Zeichnungsoperatoren sind und keine echten Elemente des Baums.

 

[SlaterB]

falls in jedem Node eine Information abgelegt ist wie Tiefe von der Wurzel, dann spart das vielleicht diese Elemente

a hat Tiefe 1, das weiß man noch vom letzten Element, b hat Tiefe 2 -> dann gehört dazwischen wohl ein [,
c hat danach dieselbe Tiefe, dann müsste seit dem b ein ] und ein [ dazwischen gehören, usw.,
aber du willst ja keine Nodes speichern wie ich langsam genauer lese..

als weiteren Vorschlag überlege, Push und Pop als Nodes bzw. sonstige Objekte zu implementieren, als statische Konstanten:
if (actualNode == Node.PUSH) { .. }
das geht insbesondere auch wenn Node ein Interface ist, mal abgesehen davon dass die Konstanten dann in anderen Klassen definiert sein sollten,
auch wenn du letztlich keine Nodes sondern beliebige Objekte speicherst funktionieren die statischen Konstanten immer noch relativ komfortabel ohne Casts, aber dann wohl wirklich in einer einfachen ArrayList, Generics ist nicht so gut

du könnest auch null speichern, das wäre dann mit Generics kompatibel,
allein aus einer Zahl-Information, aus der Anzahl an null-Elementen zwischen zwei Einträgen ließe sich alle Information ableiten, oder?
1x null -> [
2x null -> ][
3x null -> ]][
usw.

 

[muckelzwerg]

Generics will ich gar nicht verwenden. Ich hab die Typen nicht hingeschrieben, weil sie ja noch nicht feststehen.

Wir würdest Du die Konstanten implementieren, da blick ich noch nicht ganz durch, was Du meinst.

Die null-Variante finde ich nicht sonderlich "attraktiv". Aber trotzdem danke.

 

[SlaterB]

public static Object PUSH = new Object();
add(PUSH);
if (x == PUSH)
usw.

wenn es eine bestimmte Klasse wie Node sein soll, dann einen Konstruktor mit Dummy-Werten befüllen,
falls abstrakt oder Interface notfalls anonyme Klasse, alle Methoden Dummy-mäßig befüllen,
es ist egal was mit dem Objekt ist, hauptsache es kann mit == verglichen werden, ist eindeutig bestimmt,

falls im Konstruktor alle erstellten Objekte automatisch persistiert oder sonstwie verwaltet werden ist natürlich genauer aufzupassen,
wenn Konstruktor-Parameter direkt verwendet werden müssen es vielleicht mehrere Stufen sein:
public static Node PUSH = new Node(dummy, new Tree(dummy));
usw.,
die Object-Klasse ist da noch ziemlich komfortabel