import java.awt.image.BufferedImage;
import javax.imageio.ImageIO;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
// Der folgende statische Import von Funktionen ist ganz schlechter Stil
// und wurde nur durchgeführt, um die betreffenden Zeilen zu kürzen. Damit
// ein Screenshot des Codes auch für Sehbeeinträchtigte Menschen lesbar bleibt.
import static java.util.Collections.max;
import static java.util.Collections.min;
import java.util.Comparator;
import java.awt.Color;



public class Median_Cut_LuL {

    public static void main(String[] args){

        /*
        * Hier müssen die gewünschten Änderungen vorgenommen werden, wenn:
        * 1. Anzahl der Farben geändert werden soll (Iterationen sind nicht gleich Anzahl Farben!)
        * 2. Ein anderes Bild bearbeitet werden soll
        * 3. Ein anderer Outputpfad-/name gewählt werden soll
        * 
        * Der Pfad zu den Bildern ist hier relativ zum Working Directory, welches immer der Ordner ist aus 
        * dem heraus die Anwendung gestartet wird. Hier könnten auch Absolute Pfade angegeben werden!
        */
        String RGB_ImageInputPath = "images/59723540_401.jpg";
        String RGB_ImageOutputPath = "images/result.png";
        int iterationSteps = 4;

        
        // BufferedImage ist eine durch Java bereitgestellte Klasse,
        // die den Zugriff auf verschiedene Bildformate, ihre Pixel und deren Farbwerte ermöglicht.
        // Hier werden die Datenstrukturen RGB und alteredRGB initialisiert.
        BufferedImage RGB;
        BufferedImage alteredRGB;

        // Das gewünschte Bild einlesen
        try {
	        RGB = ImageIO.read(new File(RGB_ImageInputPath));
	    } catch (IOException e) {
	    	System.err.println("Image not found. Check the ImagePath!");
            return;
	    }

        // Eine 1-dimensionale Liste der Bildpixel erzeugen.
        // Die Liste hält tatsächlich int[5] Werte für R,G,B,Width und Height jedes Pixels.
        ArrayList<int[]> flattenedImgArray = new ArrayList<int[]>();
        for(int i = 0; i < RGB.getHeight(); i++){
            for(int j = 0; j < RGB.getWidth(); j++){
                int[] list = {new Color(RGB.getRGB(j, i)).getRed(), new Color(RGB.getRGB(j, i)).getGreen(), new Color(RGB.getRGB(j, i)).getBlue(), j, i};
                flattenedImgArray.add(list);
            }
        }

        // Durch entkommentieren kann hier zwischen Rekursivem und Iterativem Code gewechselt werden
        // ArrayList<int[]> returnedFlattenedImgArray = MedianCutAlgorithm(flattenedImgArray,iterationSteps);
        ArrayList<int[]> returnedFlattenedImgArray = MedianCutAlgorithmAlternativ(flattenedImgArray, iterationSteps);


        // Diese For-Schleife nimmt jeden einzelnen Pixelwert des RückgabeArrays und speichert ihn an seiner korrekten Position wieder in das Bild.
        // Dafür müssen wir aus den 3 Integern für R,G und B einen einzelnen Integer machen für ARGB.
        // Das wird hier in dem hinteren Teil durch eine eigentlich sehr simplen Bit-Shift bewerkstelligt.
        // Wir speichern A,R,G und B in einem einzelnen 32-Bit Integer. (A = Transparenz erhält den Wert 255, sprich "Keine Transparenz")
        for(int[] pixelValues : returnedFlattenedImgArray){
            RGB.setRGB(pixelValues[3], pixelValues[4], (255 << 24) | pixelValues[0] << 16 | pixelValues[1] << 8 | pixelValues[2]);
        }

        // Das fertige Bild speichern
        alteredRGB = RGB;
        try {
            ImageIO.write(alteredRGB ,"png", new File(RGB_ImageOutputPath));
        } catch (IOException e){
            System.err.println("Image couldn´t be saved");
        }
    }



    // Rekursiver Codeblock
    public static ArrayList<int[]> MedianCutAlgorithm(ArrayList<int[]> inputListe, int iterationSteps){

        ArrayList<int[]> outputListe = inputListe;

        ArrayList<Integer> rK = new ArrayList<Integer>(inputListe.size());
        ArrayList<Integer> gK = new ArrayList<Integer>(inputListe.size());
        ArrayList<Integer> bK = new ArrayList<Integer>(inputListe.size());

        int sumOfRed = 0; int sumOfGreen = 0; int sumOFBlue = 0;

        for (int[] item : inputListe) {
            rK.add(item[0]);
            gK.add(item[1]);
            bK.add(item[2]);
        
            sumOfRed += item[0];
            sumOfGreen += item[1];
            sumOFBlue += item[2];
        }

        // Stoppbedingung und Output
        if(iterationSteps == 0){
            for (int[] item : outputListe) {
                item[0] = sumOfRed / inputListe.size();
                item[1] = sumOfGreen / inputListe.size();
                item[2] = sumOFBlue / inputListe.size();
            }

            return outputListe;
        }

        // Den selbst geschrieben Comparator erzeugen und die flattenedImgArray ArrayList
        // damit sortieren. Mit .set(1) wird die Liste nach ihrem zweiten Parameter sortiert.
        // Das wäre "Grün" im R,G,B,Width,Height
        customComparator customComp = new customComparator();

        if(max(rK) - min(rK) > max(gK) - min(gK)
        && max(rK) - min(rK) > max(bK) - min(bK))
                customComp.set(0);
        else if(max(gK) - min(gK) > max(rK) - min(rK)
             && max(gK) - min(gK) > max(bK) - min(bK))
                customComp.set(1);
        else if(max(bK) - min(bK) > max(gK) - min(gK)
             && max(bK) - min(bK) > max(rK) - min(rK))
                customComp.set(2);
            
        Collections.sort(inputListe, customComp);

        // Die Inputliste in der Mitte teilen
        ArrayList<int[]> tempArray1 = new ArrayList<int[]>(inputListe.subList
            (0, (int) inputListe.size()/2));
        ArrayList<int[]> tempArray2 = new ArrayList<int[]>(inputListe.subList
            ((int) inputListe.size()/2, inputListe.size()));

        // Rekursiver Funktionsaufruf
        outputListe = MedianCutAlgorithm(tempArray1, iterationSteps - 1);
        outputListe.addAll(MedianCutAlgorithm(tempArray2, iterationSteps - 1));

        return outputListe;
    }




    
    
    // Iterativer Codeblock
    public static ArrayList<int[]> MedianCutAlgorithmAlternativ(ArrayList<int[]> inputListe, int iterationSteps){
        ArrayList<ArrayList<int[]>> oldBuckets = new ArrayList<ArrayList<int[]>>(1);
        ArrayList<ArrayList<int[]>> newBuckets = new ArrayList<ArrayList<int[]>>(1);
        oldBuckets.add(inputListe);

        if (iterationSteps == 0){}  // Nichts tun!
        else{
            for(int step = 1; step <= iterationSteps; step++){
                for(int bucket = 0; bucket < Math.pow(2, step-1); bucket++){   
                    ArrayList<Integer> rK = new ArrayList<Integer>(oldBuckets.get(bucket).size()); // rK = roter Kanal
                    ArrayList<Integer> gK = new ArrayList<Integer>(oldBuckets.get(bucket).size()); // gK = grüner Kanal
                    ArrayList<Integer> bK = new ArrayList<Integer>(oldBuckets.get(bucket).size()); // bK = blauer Kanal
            
                    for (int[] item : oldBuckets.get(bucket)) {
                        rK.add(item[0]);
                        gK.add(item[1]);
                        bK.add(item[2]);
                    }
    
                    // Den selbst geschrieben Comparator erzeugen und die flattenedImgArray ArrayList
                    // damit sortieren. Mit .set(1) wird die Liste nach ihrem zweiten Parameter sortiert.
                    // Das wäre "Grün" im R,G,B,Width,Height
                    customComparator customComp = new customComparator();
            
                    if(max(rK) - min(rK) > max(gK) - min(gK) 
                    && max(rK) - min(rK) > max(bK) - min(bK))
                            customComp.set(0);
                    else if(max(gK) - min(gK) > max(rK) - min(rK)
                         && max(gK) - min(gK) > max(bK) - min(bK))
                            customComp.set(1);
                    else if(max(bK) - min(bK) > max(gK) - min(gK)
                         && max(bK) - min(bK) > max(rK) - min(rK))
                            customComp.set(2);
                        
                    Collections.sort(oldBuckets.get(bucket), customComp);
    
                    // Arrays in den korrekten Farben speichern
                    newBuckets.add(new ArrayList<>(oldBuckets.get(bucket).subList
                        (0, oldBuckets.get(bucket).size()/2)));
                    newBuckets.add(new ArrayList<>(oldBuckets.get(bucket).subList
                        (oldBuckets.get(bucket).size()/2, oldBuckets.get(bucket).size())));
                }
            oldBuckets = newBuckets;
            newBuckets = new ArrayList<ArrayList<int[]>>(1);
            }
        }

        for (ArrayList<int[]> finishedArrayList : oldBuckets) {
            int sumOfRed = 0; int sumOfGreen = 0; int sumOfBlue = 0;

            for (int[] item : finishedArrayList) {   
                sumOfRed += item[0];
                sumOfGreen += item[1];
                sumOfBlue += item[2];
            }
            for (int[] item : finishedArrayList) {
                item[0] = sumOfRed / finishedArrayList.size();
                item[1] = sumOfGreen / finishedArrayList.size();
                item[2] = sumOfBlue / finishedArrayList.size();
            }    
        }

        // Temporäre Arrays wieder zu einem einzelnen Rückgabearray zusammenführen.
        ArrayList<int[]> outputListe = new ArrayList<int[]>();
        for (ArrayList<int[]> tempList : oldBuckets) {
            outputListe.addAll(tempList);
        }
        return outputListe;
    }





    // Um die Int[5]´s vergleichen zu können, ist eine Funktion nötig, die diese Int[5]´s auch vergleichen kann.
    // Dazu braucht es einen "Comparator"
    static class customComparator implements Comparator<int[]>{
        int RGorB = 0;

        public void set(int whichRGBisHighest){
            if(whichRGBisHighest < 0 || 2 < whichRGBisHighest){
                System.out.println("Es können nur R,G oder B zum sortieren ausgewählt werden.");
                return;
            }

            RGorB = whichRGBisHighest;
        }

        public int compare(int[] firstIntArray, int[] secondIntArray){
            return Integer.compare(firstIntArray[RGorB], secondIntArray[RGorB]);
        }
    }
}
