/*
 * Klasse ArrayTreePrint druckt aus einem Array einen Baum, so wie z.B. HeapSort ihn sieht.
 * Als Parameter benötig arrayTreePrint das Integer Array und optional die gewünschte, maximale
 * Darstellungstiefe. Ohne optionalen Parameter wird nur bis zu einer Tiefe von 7 gedruckt.
 * 
 * Die Ausgabe der Feldinhalte wird an das längste Element angepasst. Somit erhält man immer
 * einen sauberen Ausdruck und ordentliche Einrückungen.
 * 
 * Um die Orientierung zu erleichtern, sind die Söhne eines Vaters durch Striche verbunden.
 * 
 * 19.08.2008 Wolfgang Führer; wolfgang.fuehrer@web.de
 */
 
public class ArrayTreePrint
{
    private static int maxbreite;
 
    private static void printStringsL(int a, String s)          // drucke n * maxbreite leerzeichen
    {
        for(int i = 0; i<a;i++)
            for(int j = 0; j < maxbreite; j++)
                System.out.print(s);
    }
 
    private static void printFormatted(int o)                   // gebe o in maxbreite aus (führende leerzeichen)
    {
        String s = "";
        for(int i = 0; i < maxbreite; i++)                      // füge maxbreite leerzeichen vorne an
            s += " ";
        s += o;
        s = s.substring(s.length()-maxbreite+2, s.length());    // kürze auf maxbreite
        System.out.print("[" + s + "]");
    }
 
    public static void arrayTreePrint(int[] feld)
    {
        arrayTreePrint(feld,7);
    }
 
    public static void arrayTreePrint(int[] feld, int maxH)
    {
        int temp = 0;
        int hoehe = 0;
        maxbreite = 1;
        for(int a = 0; a < feld.length; a++)                    // finde längstes element im array
        {   
            temp = (""+feld[a]).length();                       // ermittle stringlänge
            if(temp > maxbreite)
                maxbreite = temp;
        }
        maxbreite = maxbreite + 2;                              // +2 für [ und ]
        int arraysize = feld.length;
        int baumHoehe = (int)Math.round(Math.floor((Math.log10(arraysize)/Math.log10(2))));
        System.out.print("Elementanzahl = "+ feld.length);
        System.out.print("; Max Elementbreite = "+ (maxbreite-2));
        System.out.print("; Baumhöhe = " + baumHoehe);
        System.out.println("; Druckhöhe = " + maxH);
        if(baumHoehe > maxH)                                    // maximal maxH höhe anzeigen
            hoehe = maxH;
        else
            hoehe = baumHoehe;
        for(int h = 0; h <= hoehe; h++)                         // bearbeite alle höhen seperat
        {   
            printStringsL(((int)Math.pow(2, (hoehe-h)))/2," "); // linken rand drucken
            if(h==hoehe)                                        // korrigiere letzte zeile
            {
                for(int i = 0; i < maxbreite/2; i++)
                    System.out.print(" ");
            }
            int levelsize = (int)Math.pow(2, h);                // anzahl elemente auf höhe
            for(int e = levelsize; e < levelsize*2; e++)        // bearbeite die elemente einer höhe
            {   
                if(e-1 < arraysize)                             // wenn noch elemente vorhanden
                {
                    printFormatted(feld[e-1]);                  // feldinhalt auf maxbreite ausgeben
                    int t = (int)Math.pow(2,(hoehe-h))-1;
                    if((e-levelsize)%2 == 1)                    // verbinde kinder eines vaters
                    {
                        if(e<levelsize*2-1)                     // nur innerhalb tree drucken
                            printStringsL(t," ");               // keine geschwister
                    }
                    else
                    {
                        if(h != 0)                              // root braucht keinen verbinder
                            printStringsL(t,"-");               // verbinde geschwister
                    }
                }
            }
            System.out.println("");                             // zeilenforschub für nächste höhe
        } 
        if(hoehe < baumHoehe)
            System.out.println(" ... ... ...");                 // hinweis baum wurde gekürzt 
    }
 
    public static void main(String[] args)
    {
        int feld[] = {56,22,79,27,93,30,6,49,6999,38,52,89,2,17,68,30,33,67,
                      99,33,22,3,23,17,68,30,3355,67};
        arrayTreePrint(feld, 3);
        System.out.println("");
        arrayTreePrint(feld);
 
        /*
         * Ausgabe:
         * 
         * Elementanzahl = 72; Max Elementbreite = 4; Baumhöhe = 4; Druckhöhe = 3
         *                         [  56]
         *             [  22]------------------[  79]
         *       [  27]------[  93]      [  30]------[   6]
         *    [  49][6999][  38][  52][  89][   2][  17][  68]
         *   ... ... ...
         *   
         * Elementanzahl = 72; Max Elementbreite = 4; Baumhöhe = 4; Druckhöhe = 4
         *                                                 [  56]
         *                         [  22]------------------------------------------[  79]
         *             [  27]------------------[  93]                  [  30]------------------[   6]
         *       [  49]------[6999]      [  38]------[  52]      [  89]------[   2]      [  17]------[  68]
         *    [  30][  33][  67][  99][  33][  22][   3][  23][  17][  68][  30][3355][  67]                                                                                                                                          
         *                                                                                            
         */
    }
 
}