#include <List.h>

//insere todos os pixels da imagem na lista
image_ref *insertImage(image_ref *list,float distLo,float distHi,char name[45])
{
   image_ref *novo;
   image_ref *aux;
   aux=list;
   novo=malloc(sizeof(image_ref));
   novo->distLo=distLo;
   novo->distHi=distHi;
   strcpy(novo->name,name);
   novo->prox=NULL;
   
   
   if (list==NULL)
   {
     list=novo;
   }
   else
   {
     while (aux->prox!=NULL)     
        aux=aux->prox;     
     aux->prox=novo;
   }
   return list;
}

int compara(image_ref *a, image_ref *b)
{
   //float va=(a->distLo+a->distHi)/2;
   //float vb=(b->distLo+b->distHi)/2;
   float va=a->distLo;
   float vb=b->distLo;
   if (va<vb)
     return -1;
   else if (va>vb)
     return 1;
   else return 0;
}

image_ref *insertSortImage(image_ref *list,float distLo,float distHi,char *name,int resolucao)
{
   image_ref *novo;
   image_ref *aux,*aux2;
   aux=list;
   aux2=NULL;
   novo=malloc(sizeof(image_ref));
   novo->distLo=distLo;
   novo->distHi=distHi;
   novo->resolucao=resolucao;
   strcpy(novo->name,name);
   novo->prox=NULL;
   
   if (list==NULL)
   {
     list=novo;
   }
   else
   {
     while ((aux!=NULL)&&(compara(novo,aux)>0))     
     {   
        aux2=aux;
        aux=aux->prox;
     }
     if (aux2==NULL)
     {   
        novo->prox=list;
        list=novo;
     }
     else if (aux==NULL)
        aux2->prox=novo;
     else
     {
        aux2->prox=novo;
        novo->prox=aux;
     }
   }
   return list;
}

image_ref *removeImage(image_ref *list,image_ref *img)
{
   image_ref *aux=list;
   image_ref *aux2=list;
      
   while ((aux!=NULL)&&(aux->name!=img->name))
   {
      aux2=aux;
      aux=aux->prox;
   }
   if (aux!=NULL)
   {
      if (aux==list)
         list=list->prox;
      else
         aux2->prox=img->prox;  
       free(img);
   }
   return list;
}

image_ref *editImage(image_ref *list,float distLo,float distHi,char name[45])
{
   image_ref *aux=list;
   while ((aux!=NULL)&&(aux->name!=name))     
      aux=aux->prox;     
   if (aux!=NULL)
   {
     aux->distLo=distLo;
     aux->distHi=distHi;
   }
   //free(aux);
   return list;
}

void free_Lista(image_ref *list)
{
   image_ref *aux;
   while (list!=NULL)
   {
      aux=list;
      list=list->prox;
      free(aux);
   }
}

image_ref *clone(image_ref *list)
{
	image_ref *n,*novo,*aux=NULL;
	aux=list;
	novo=malloc(sizeof(image_ref));
	novo->distLo=aux->distLo;
	novo->distHi=aux->distHi;
	strcpy(novo->name,aux->name);
	novo->prox=NULL;
	n=novo;
	aux=aux->prox;
	while (aux!=NULL)
	{
		n->prox=malloc(sizeof(image_ref));
		n=n->prox;
		n->distLo=aux->distLo;
		n->distHi=aux->distHi;
		strcpy(n->name,aux->name);
		n->prox=NULL;
		aux=aux->prox;
	}
	return novo;
}

//++++++++++++++++++++++++++++++++++++++Operações Lista Brilho+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=

image_brilho *insertSortBrilho(image_brilho *l,double brilho,int x,int y)
{
   image_brilho *novo;
   image_brilho *aux,*aux2;
   aux=l;
   aux2=NULL;
   novo=malloc(sizeof(image_brilho));
   novo->brilho=brilho;
   novo->x=x;
   novo->y=y;
   novo->prox=NULL;
   
   if (l==NULL)
   {
     l=novo;
   }
   else
   {
     while ((aux!=NULL)&&(novo->brilho>aux->brilho))     
     {   
        aux2=aux;
        aux=aux->prox;
     }
     if (aux2==NULL)
     {   
        novo->prox=l;
        l=novo;
     }
     else if (aux==NULL)
        aux2->prox=novo;
     else
     {
        aux2->prox=novo;
        novo->prox=aux;
     }
   }
   return l;
}

image_brilho *removeBrilho(image_brilho *l,image_brilho *bri)
{
   image_brilho *aux=l;
   image_brilho *aux2=l;
      
   while ((aux!=NULL)&&(aux->x!=bri->x)&&(aux->y!=bri->y))
   {
      aux2=aux;
      aux=aux->prox;
   }
   if (aux!=NULL)
   {
      if (aux==l)
         l=l->prox;
      else
         aux2->prox=bri->prox;  
       free(bri);
   }
   return l;
}

image_brilho *editBrilho(image_brilho *l,double brilho,int x,int y)
{
   image_brilho *aux=l;
   while ((aux!=NULL)&&(aux->x!=x)&&(aux->y!=y))     
      aux=aux->prox;     
   if (aux!=NULL)
   {
     aux->brilho=brilho;
   }
   return l;
}

void free_ListaBrilho(image_brilho *l)
{
   image_brilho *aux;
   while (l!=NULL)
   {
      aux=l;
      l=l->prox;
      free(aux);
   }
}

//+++++++++++++++QuickSort+++++++++++++

image_brilho *criaNo(double brilho,int x,int y)
{
   image_brilho *novo;
   novo=malloc(sizeof(image_brilho));
   novo->brilho=brilho;
   novo->x=x;
   novo->y=y;
   novo->prox=NULL;
   return novo;
}

//gera a partir de uma vetor com os brilhos uma lista ordenada eliminando os repetidos se requisitado
image_brilho *geralLista(image_brilho vet[],int fim[],int repetido)
{
   int i;
   image_brilho *l=NULL;
   image_brilho *aux=NULL;
   int insere,numPixels=0;
   l=criaNo(vet[0].brilho,vet[0].x,vet[0].y);
   float brilhoAnt=vet[0].brilho,brilho;
   aux=l;
   for (i=1;i<fim[0];i++)
   {
       insere=1;
       brilho=vet[i].brilho;
       if ((brilhoAnt==brilho)&&(repetido==0))
       {  insere=0;}

       if (insere==1)
       {
          numPixels++;
          brilhoAnt=vet[i].brilho;
          aux->prox=criaNo(vet[i].brilho,vet[i].x,vet[i].y);
          aux=aux->prox;
       }
   }
   fim[1]=numPixels;
   return l;
}

int compare(const void *a, const void *b);

int compare(const void *a, const void *b)
{
    image_brilho *ia = (image_brilho *)a;
    image_brilho *ib = (image_brilho *)b;
    if (ia->brilho < ib->brilho) return -1;
    if (ia->brilho == ib->brilho) return 0;
    return 1;
}

void quickSort(image_brilho vet[],int fim)
{
   qsort (vet,fim,sizeof(image_brilho),compare);
}

/*
void troca(image_brilho a,image_brilho b)
{
   image_brilho aux;
   aux=a;
   a=b;
   b=aux;
}


void quickSort(image_brilho vet[],int ini,int fim)
{
   image_brilho pivo=vet[ini];
   int i=ini+1,j=fim,k=fim;
   image_brilho t;

   while (i<j)
   {
      if (vet[i].brilho<pivo.brilho)
         i++;
      else if (vet[i].brilho>pivo.brilho)
      {
         j--; 
         k--;
         t=vet[i];
         vet[i]=vet[j];
         vet[j]=vet[k];
         vet[k]=t;
      }
      else
      {
         j--;
         troca(vet[i],vet[j]);
      }  
   }
   i--;
   troca(vet[ini],vet[i]);        
   if (i-ini>1)
      quickSort(vet,ini,i);
   if (fim-k>1)
      quickSort(vet,k,fim);                      
}

image_brilho *insereLista(image_brilho *l,image_brilho *t)
{
   if (l!=NULL)
      t->prox=l;   
   l=t;
   return l;
}

image_brilho *quickSort(image_brilho *l)
{
   image_brilho *pivo=l;
   image_brilho *aux=l->prox;
   image_brilho *aux2=NULL;
   int prim=0;
   image_brilho *me=NULL,*ma=NULL,*fim=NULL;
   //fprintf(stderr, "Pivo: %8.6f\n",aux->brilho);
   while (aux!=NULL)
   {
      aux2=aux->prox;
      if (aux->brilho<pivo->brilho)
      {
         me=insereLista(me,aux);
         //fprintf(stderr, "Menor: %8.6f\n",aux->brilho);
         if (prim==0)
         {
             fim=aux;
             prim=1;
         }
      }
      else{
         ma=insereLista(ma,aux);
         //fprintf(stderr, "Maior: %8.6f\n",aux->brilho);
      }
      aux=aux2;
   }//fprintf(stderr, "Menor: Quick\n");
   me=quickSort(me);//fprintf(stderr, "Maior: Quick\n");
   ma=quickSort(ma);
   fim->prox=pivo;
   pivo->prox=ma;
   return me;
}

image_brilho *insereBrilho(image_brilho *l,double brilho,int x,int y)
{
   image_brilho *novo;
   novo=malloc(sizeof(image_brilho));
   novo->brilho=brilho;
   novo->x=x;
   novo->y=y;
   novo->prox=NULL;
   l=insereLista(l,novo);
   //fprintf(stderr, "x: %d | y: %d | brilho: %8.6f\n",l->x,l->y,l->brilho);
   return l;
}

//new quicksort

//find previous image_brilho of curr image_brilho
image_brilho *FindPrev(image_brilho *list, image_brilho *curr)
{
  for(;list && list->prox; list=list->prox)
  {
    if(curr == list->prox)
    {
      break;
    }
  }

  if (list->prox != curr)
  {
    //not find any element, probably what we are 
    //searching for is the beginning image_brilho
    return curr;
  }

  return list;
}


image_brilho *SwapNodes(image_brilho *list, image_brilho *no1, image_brilho *no2)
{
  image_brilho *no1prev, *no2prev, *tmp;

  no1prev = FindPrev(list, no1);
  no2prev = FindPrev(list, no2);

  tmp = no2->prox;

  //check whether node to swapped is in 
  //beggining (i.e. header node)
  if (no1 != list)
  {
    no1prev->prox = no2;
  }
  else
  {
    //as we do not have special header node, 
    //if the first node and some 
    //other node, need to be swapped, 
    //then update the list (makes new min node as 
    //logical header)
    list = no2;
  }

  //are nodes to be swapped neibgoring nodes?
  if (no1->prox == no2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    no2->prox = no1;
    no1->prox = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes, 
    //they are apart
    //so, consider all scenarios
    no2->prox = no1->prox;

    no1->prox = tmp;
    no2prev->prox = no1;
  }

  return list;
}

image_brilho *GetNthNode(image_brilho *list, int n)
{
  int i=1;
  for(i=1;i<n;i++)
  {
    list = list->prox;
  }
  return list;
}

int NumNodes(image_brilho *list, image_brilho *end)
{
  int i;

  for(i=1;list && (list!=end);i++)
  {
    list = list->prox;
  }

  if (list != end)
  {
    return 0;
  }
  return i;
}

//total nodes in list
int countnodes(image_brilho *list)
{
  int i = 0;

  for (;list; list=list->prox)
  {
    i++;
  }

  return i;
}

image_brilho *SelectPivot(image_brilho *list, image_brilho *end)
{
  image_brilho *right, *noden;
  int n;

  n=NumNodes(list, end);

  noden = GetNthNode(list, (int)((float)n/2+0.5));
  //
  right = FindPrev(list, end);

  if (noden != right)
  {
    //swap the pivot and right most element in the list
    //later pivot will be restored.
    SwapNodes(list, noden, right->prox);
    return noden;
  }
  else
  {
    return noden->prox;
  }
}

image_brilho * quicksort(image_brilho *list, int list_start, int list_end) 
{
  image_brilho *pivot, *left=list, *right=list, *tmp;
  int i = list_start, j= list_end-1;

  if (list_start >= list_end)
  {
    return list;
  }

  right = GetNthNode(list, list_end);
  left = GetNthNode(list, list_start);

  //select pivot
  pivot = SelectPivot(left, right);

  right = FindPrev(left, pivot);

  for(;;)
  {
    //now starts partitioning the list
    for(;left->brilho < pivot->brilho; left=left->prox,i++);

    for(;right->brilho > pivot->brilho; right = FindPrev(list,right),j--);
    if (i < j)
    {
      list = SwapNodes(list, left, right);
      tmp = left;
      left = right;
      right = tmp;
    }
    else
      break;
  }

  //restore pivot
  list = SwapNodes(list, left, pivot); 

  //now sort on smaller linked lists
  list = quicksort(list, list_start, i-1);
  list = quicksort(list, i+1, list_end);

  return list;
}

//a wrapper for quicksort
image_brilho *QSort(image_brilho *list)
{
  int n;
  
  n=countnodes(list);

  return quicksort(list, 1, n);
}
*/