/*
    Copyright (c) 2010, Luis Alvarez <lalvarez@dis.ulpgc.es>
	All rights reserved.
	
	This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/**
 * \page code_utilities.h \link utilities.h \endlink
 * \brief \ref code_utilities.cpp "See utilities.cpp"
 * \brief Code of  \ref code_utilities.h "utilities.h"
 * \includelineno utilities.h
 */

/**
 * \file utilities.h
 * \brief Basic image utilities procedures
 * \author Luis Alvarez \n \n
 * \brief \b Code: \n
 * - \ref code_utilities.cpp "utilities.cpp" \n
 * - \ref code_utilities.h "utilities.h"
*/
#ifndef UTILITIESAMI_H
#define UTILITIESAMI_H

#include <vector>
#include "image.h"
#include "point2d.h"

using namespace std;

namespace ami{

class utilities{

  public:

  std::vector < std::vector <int> > boundary_neighborhood_9n(const int width, const int height);
  std::vector < std::vector <int> > boundary_neighborhood_5n(const int width, const int height);
  std::vector <int>  boundary_neighborhood_1n(const int width, const int height);
  std::vector < std::vector <ami::point2d<int> > > construct_neighborhood(const int radius);

  template <class T>
  int scan_line_filling(ami::image<T> &img,const int x0,const int y0, const int channel, const T level1, const T level2);

  template <class T>
  T median (const std::vector <T> v,const int level);



};

}

/**
 * template <class T> T median (const std::vector <T> v)
 * \brief function to the vector median
 * \return the median value
 * \author Luis Alvarez
*/
template <class T>
T ami::utilities::median (
  const std::vector <T> v /** vector to compute the median */,
  const int level /** reference level. There are level "values" lower than the median in the vector */)
{
  if(v.size()==0) return( (T) 0);

  int i,ir,j,l,mid,n=v.size();
  int k=level;
	T a,paso;
	vector <T> y=v;

	l=0;
	ir=n-1;
	for (;;) {
		if (ir <= l+1) {
			if (ir == l+1 && y[ir] < y[l]) {
				paso=y[l]; y[l]=y[ir]; y[ir]=paso; //ami_swap(y[l],y[ir])
			}
            a=y[k];
			return a;
		} else {
			mid=(l+ir) >> 1;
			paso=y[mid]; y[mid]=y[l+1]; y[l+1]=paso; //ami_swap(y[mid],y[l+1])
			if (y[l] > y[ir]) {
				paso=y[l]; y[l]=y[ir]; y[ir]=paso; //ami_swap(y[l],y[ir])
			}
			if (y[l+1] > y[ir]) {
				paso=y[l+1]; y[l+1]=y[ir]; y[ir]=paso; //ami_swap(y[l+1],y[ir])
			}
			if (y[l] > y[l+1]) {
				paso=y[l]; y[l]=y[l+1]; y[l+1]=paso; //ami_swap(y[l],y[l+1])

			}
			i=l+1;
			j=ir;
			a=y[l+1];
			for (;;) {
				do i++; while (y[i] < a);
				do j--; while (y[j] > a);
				if (j < i) break;
				paso=y[i]; y[i]=y[j]; y[j]=paso; //ami_swap(y[i],y[j])
			}
			y[l+1]=y[j];
			y[j]=a;
			if (j >= k) ir=j-1;
			if (j <= k) l=i;
		}
	}

}

/**
 * \fn template <class T> int ami::utilities::scan_line_filling( ami::image<T> &img,
const int x0, const int y0,
const int channel,
const T level1, const T level2 )
 * \brief function to fill an image with a value
 * \return number of points filled with the level 2 value
 * \author Luis Alvarez
*/
template <class T>
int ami::utilities::scan_line_filling(
ami::image<T> &img /** INPUT/OUTPUT IMAGE */,
const int x0 /** x-COORDINATE OF FIRST POINT */,
const int y0 /** y-COORDINATE OF FIRST POINT */,
const int channel /** IMAGE CHANNEL TO BE FILLED */,
const T level1 /** IMAGE LEVEL 1 TO BE FILLED */,
const T level2 /** IMAGE LEVEL 2 ASSIGNED TO THE VALUES */)
{
  int width=img.width();
  int height=img.height();
  int image_size=width*height;
  int Coord_x=x0;
  int Coord_y=y0;
  int contador=0;
  T nivel1=level1;
  T nivel2=level2;
  int n2=channel*image_size;

  int m, x, y;
  int nVecinos=0;
  bool vecinoUp, vecinoDown;
  //vector <int> vecinos(image_size);
  int *vecinos = new int [width*height];//[height*4*2];
  vecinos[0] = Coord_x;
  vecinos[1] = Coord_y;
  nVecinos   = 2;

  while (nVecinos > 0){
    /*coger el siguiente vecino*/
    x = vecinos[nVecinos-2];
    y = vecinos[nVecinos-1];
    nVecinos-=2;

    /*indicar que se pueden incluir nuevos vecinos superiores e inferiores*/
    vecinoUp   = true;
    vecinoDown = true;

    /*retroceder hasta encontrar el primero*/
    m=y*width+x;
    while((x > -1) && m<image_size && (img[m+n2]==nivel1)){
      x--;
      m--/*=y*width+x*/;
    }
    x++;

    /*recorrer el scanline*/
    m=y*width+x;
    while((x < width) && m<image_size && (img[m+n2]==nivel1)){
      /*pintar la posicion actual*/
      img[m+n2]=nivel2;
      contador++;

      /*vigilar a los vecinos verticales*/
      /*vecino superior*/
      if(y<height-1){
        if (img[m+width+n2]==nivel1){
          if (vecinoUp){
            vecinos[nVecinos]   = x;
            vecinos[nVecinos+1] = y+1;
            vecinoUp  = false;
            nVecinos += 2;
          }
        }
        else{
          vecinoUp = true;
        }
      }
      /*vecino inferior*/
      if(y>0){
        if (img[m-width+n2]==nivel1){
          if (vecinoDown){
            vecinos[nVecinos]   = x;
            vecinos[nVecinos+1] = y-1;
            vecinoDown = false;
            nVecinos  += 2;
          }
        }
        else{
          vecinoDown = true;
        }
      }
      /*calcular la nueva posicion*/
      x++;
      m++/*=y*width+x*/;
    }
  }

  delete []vecinos;
  return(contador);
}




#endif
