#include <string>
#include <queue> /*Hier wurde queue verwendet, weil die FIFO-Struktur bei der Ausgabe ganz nützlich ist*/

using namespace std;

class Objekt
{
	public:
	Objekt (string name) { this->name = name; this-> child1 = NULL; this->child2 = NULL; }
	void generateTree( queue<string> &str_q );

	private:
	Objekt* child1;
	Objekt* child2;
	string name;
};

/* Diese Implementierung setzt folgendes voraus (wurde auch oben schnell gezeigt):
 * queue und string wurden inkludiert
 * Die Klasse Objekt verfügt über die Attribute
 * - Objekt* child1
 * - Objekt* child2
 * - string name
 *
 * Ein weiteres Kriterium ist das Nullsetzen der beiden Pointer im Konstruktor,
 * und die Vorsorge, dass str_q NICHT leer ist, wenn sie übergeben wird.
 * Vor dem Auruf sollte einfach str_q.append("") erfolgen.
 * Sonst gibt es unvorhergesehene Konsequenzen wie Segfaults ;)*/

void Objekt::generateTree( queue<string> &str_q ){
    str_q.back().append( this->name );

    if( this->child1 != NULL ) //Jedes Kind ist ein weiterer Zweig
    {
        if( this->child2 == NULL )
            str_q.back().append("-"); //Normalen Strich, wenns nur ein Kind ist
        else
            str_q.back().append("+"); // Verzweigung, wenns zwei Kinder gibt

        this->child1->generateTree( str_q );
    }

    if( this->child2 != NULL )
    {
	string buffer;
        int p=str_q.back().find_last_of("+");
        int k=str_q.back().find_last_of("|");

        if(p<k)
            p=k;


        for( int i=0 ; i <= p; ++i )
        {
            if (i< p){
                if (str_q.back()[i] == '+' || str_q.back()[i] == '|')
                    buffer.append("|");
                else
                    buffer.append(" ");
            }else if (i==p){
                buffer.append("`");
            }
        }
        str_q.push( buffer );

        this->child2->generateTree( str_q );
    }
}