import java.io.*;
import java.util.*;
 
 
 
public class kmeans {


    /** Numero de clusters */
    private int k;

    /** Debug por consola */
    boolean debug=false;

    /** Paleta final, en las mismas posiciones que los clusters */
    int[] paleta;

    /** Array de clusters */
    private int[] clusters;


    /** Numero de iteraciones (log) */
    private int nIterations;

    /** Vector de pixeles */
    private int[] pixeles;

    /** Tamanyo del vector de pixeles **/
    private int tamanyo;

    /** Asignacion a cluster de los pixeles; sirve para sacar la imagen recompuesta **/
    private int[] asignacion;

    /**
    * Constructor kmeans: kmeans( k, img, tamanyo, debug)
    *   k = numero de clases a encontrar
    *   img = pixeles de la imagen en un int[]
    *   tamanyo = tamanyo de la imagen en pixeles, igual que tamanyo de img
    *   debug = bool, activa el debug
    */
    public kmeans(int k, int[] pixeles, int tamanyo, boolean debug) {
        int ii=0;
        this.debug = debug;
        this.k = k;
        this.nIterations = 0;
        this.tamanyo = tamanyo;
        this.clusters = new int[k];
        this.paleta = new int[k];
        this.asignacion = new int[this.tamanyo];
        this.pixeles = new int[tamanyo];
        /** Inicializamos los clusters con los primeros k pixeles no repetidos **/
        for( int i=0; i < tamanyo; i++) this.pixeles[i] = (pixeles[i] & 0x00FFFFFF);

        /** Cogemos los 1os k colores diferentes como iniciales de las clases **/
        int cluster=0;
        for( int i=0; i<this.tamanyo && cluster < this.k; i++) {
            boolean continuar=true;
            for( ii = 0; ii < cluster && continuar == true; ii++) if( this.pixeles[i] == this.clusters[ii]) continuar=false;
            if( continuar == true ) {
                this.clusters[cluster] = this.pixeles[i];
                if(debug) System.out.println("Cluster inicial " + cluster + ", pixel " + i + ": rojo=" + ( (this.clusters[cluster] & 0xFF0000) / 0x10000) +"; verde=" + ( (this.clusters[cluster] & 0x00FF00) / 0x100) + " azul=" + (this.clusters[cluster] & 0x0000FF) );
                cluster++;
                }
            }
       runkmeans();
       } // fin del kmeans()


    /**
     * Runs the k-means algorithm over the data set
     */
    private void runkmeans() {
        int[] clustersant=new int[this.k];
        int[] clusterstmpR = new int[this.k];
        int[] clusterstmpG = new int[this.k];
        int[] clusterstmpB = new int[this.k];
        int[] clusterstmpn = new int[this.k];
        int distanciamin,dtmp;
        int pixeli,clusteri,indexmin;
        boolean mismocluster;

        do {
            mismocluster = true;
            /**
            Para cada pixel encontramos su cluster
            **/
            for(pixeli=0; pixeli < this.tamanyo; pixeli++) {
                distanciamin=distancia(this.clusters[0],this.pixeles[pixeli]);
                indexmin=0;
                /**
                Para todos los clusters, calculamos la distáncia y escogemos
                la minima como cluster al que pertenece ese pixel
                **/
                for( clusteri=0; clusteri<this.k; clusteri++) {
                    dtmp=distancia(this.pixeles[pixeli],this.clusters[clusteri]);
                    if( dtmp < distanciamin ) {
                        distanciamin = dtmp;
                        indexmin = clusteri;
                        }
                    }
                this.asignacion[pixeli] = indexmin;
                } // fin de analisis de pixeles
            /**
            Ponemos a 0 el acumulador temporal...
            **/
            for(clusteri=0; clusteri<this.k; clusteri++){
                clusterstmpR[clusteri]=0;
                clusterstmpG[clusteri]=0;
                clusterstmpB[clusteri]=0;
                clusterstmpn[clusteri]=0;
                }
            /**
            Para los pixeles reagrupados, ahora encontramos el nuevo 'centro de
            gravedad', que sera la nueva ubicacion del cluster
            Para ello usamos unos acumuladores donde iremos sumando 
            **/
            for(pixeli=0; pixeli<this.tamanyo; pixeli++){
                clusterstmpR[this.asignacion[pixeli]] += (this.pixeles[pixeli] & 0x00FF0000) / 0x10000;
                clusterstmpG[this.asignacion[pixeli]] += (this.pixeles[pixeli] & 0x0000FF00) / 0x100;
                clusterstmpB[this.asignacion[pixeli]] += (this.pixeles[pixeli] & 0x000000FF);
                clusterstmpn[this.asignacion[pixeli]]++;
                }
            for(clusteri=0; clusteri<this.k; clusteri++){
                if( clusterstmpn[clusteri] > 0 ) {
                    clusterstmpR[clusteri]=clusterstmpR[clusteri]/clusterstmpn[clusteri];
                    clusterstmpG[clusteri]=clusterstmpG[clusteri]/clusterstmpn[clusteri];
                    clusterstmpB[clusteri]=clusterstmpB[clusteri]/clusterstmpn[clusteri];
                    clustersant[clusteri] = this.clusters[clusteri];
                    this.clusters[clusteri] = clusterstmpR[clusteri]*0x10000 + clusterstmpG[clusteri]*0x100 + clusterstmpB[clusteri];
                    if( clusters[clusteri] != clustersant[clusteri] ) mismocluster = false;
                    }
                  else System.out.println("/!\\ Cluster "+clusteri+" con 0 pixeles!");
                }

            if( debug ) {
                System.out.println("> Iteracion " + nIterations );
                for( int ii = 0; ii < this.k ; ii++)  System.out.println("   -cluster " + ii + ": rojo=" + ( (this.clusters[ii] & 0xFF0000) / 0x10000) +"; verde=" + ( (this.clusters[ii] & 0x00FF00) / 0x100) + " azul=" + (this.clusters[ii] & 0x0000FF) );
                }

            this.nIterations++;
            } while ( !mismocluster );
        if( debug ) System.out.println("-- usadas " + this.nIterations + " iteraciones--");
        } // end of runkmeans()

    /**
    * Para ahorrar tiempo de computo calculamos la distancia al cuadrado
    * Esto no afecta a las comparaciones, que es lo que nos interesa
    * Asi nos ahorramos hacer la raiz cuadrada
    */
    private int distancia(int puntoa, int puntob) {
        int resultR = ( (puntoa & 0x00FF0000) - (puntob & 0x00FF0000) ) / 0x10000;
        int resultG = ( (puntoa & 0x0000FF00) - (puntob & 0x0000FF00) ) / 0x100;
        int resultB = (puntoa & 0x000000FF) - (puntob & 0x000000FF);
        return (resultR*resultR + resultG*resultG + resultB*resultB);
        } // fin de distancia()

    /**
    * Retorna el valor de k, el numero de clusters
    */
    public int getK() {
        return this.k;
        } // end of getK()

    /**
    * Retorna los clusters en un array de int's
    */
    public int[] getClusters() {
        return this.clusters;
        } // end of getCluster()


    /**
    * Retorna la imagen transformada por kmeans a 'k' colores cualquiera.
    */
    public int[] getkImage() {
        int i=0;
        int[] ret=new int[this.tamanyo];
        for( i=0; i<this.tamanyo; i++) ret[i]= 0xFF000000 + this.clusters[this.asignacion[i]];
        return ret;
        }


    /**
    * Retorna la imagen transformada por kmeans a 'k' colores (max) de la paleta.
    */
    public void setPaleta(int[] paleta, int l) {
        int distanciamin,indexmin,dtmp,clusteri,paletai;
        /**
        * Para todos los clusters, calculamos la distáncia a la paleta dada
        * y escogemos la minima como color al que pertenece ese cluster
        */
        for( clusteri=0; clusteri<this.k; clusteri++) {
            distanciamin=distancia(this.clusters[clusteri],paleta[0]);
            indexmin=0;
            for( paletai=0; paletai < l; paletai++) {
                dtmp=distancia(paleta[paletai],this.clusters[clusteri]);
                if( dtmp < distanciamin ) {
                    distanciamin = dtmp;
                    indexmin = paletai;
                    }
                }
            this.paleta[clusteri] = paleta[indexmin];
            }
        }


    /**
    * Retorna la imagen transformada por kmeans a 'k' colores (max) de la paleta
    */
    public int[] getkImagep() {
        int[] ret=new int[this.tamanyo];
        for( int i=0; i<this.tamanyo; i++) ret[i]= 0xFF000000 | this.paleta[this.asignacion[i]];
        return ret;
        }

    /**
    * Retorna la paleta que usa la imagen transformada con el kmeans (k colores de los 11)
    */
    public int[] getPaleta() {
        return this.paleta;
        }



    } // final de la calse kmeans