#include <stdio.h>
#include <SDL.h>
#include <SDL_opengl.h>
#include <vector>
#include "Geometry.h"

#include <algorithm>
#include <numeric>
#include <vector>
#include <iterator>

using namespace std;

#define WIDTH 1280
#define HEIGHT 720
#define BPP 4
#define DEPTH 32

void DrawColoredQuad(const CRect & rect, float a, float r, float g, float b)
{
  glColor4f(r, g, b, a);
  glBegin(GL_QUADS);
    glVertex3f(rect.x1, rect.y1, 0.0f);	// Bottom Left Of The Texture and Quad
    glVertex3f(rect.x2, rect.y1, 0.0f);	// Bottom Right Of The Texture and Quad
    glVertex3f(rect.x2, rect.y2, 0.0f);	// Top Right Of The Texture and Quad
    glVertex3f(rect.x1, rect.y2, 0.0f);	// Top Left Of The Texture and Quad
  glEnd();
}

vector<CRect> markedRegions;
float costNewRegion = 1000.0f;
float costPerArea   = 0.01f;

float UnifyRegions(vector<CRect> &inputRegions, vector<CRect> &outputRegions)
{
  CRect unifiedRegion;

  for (unsigned int i = 0; i < inputRegions.size(); i++)
    unifiedRegion.Union(inputRegions[i]);

  outputRegions.push_back(unifiedRegion);

  return unifiedRegion.Area() * costPerArea + costNewRegion;
}

float CostReduction(vector<CRect> &inputRegions, vector<CRect> &outputRegions)
{
  float totalCost = 0.0f;

  for (unsigned int i = 0; i < inputRegions.size(); i++)
  {
    CRect possibleUnionRegion;
    int   possibleUnionNbr = -1;
    float possibleUnionCost = 100000.0f;

    CRect currentRegion = inputRegions[i];
    for (unsigned int j = 0; j < outputRegions.size(); j++)
    {
      CRect temporaryUnion = outputRegions[j];
      temporaryUnion.Union(currentRegion);
      float temporaryCost = costPerArea * (temporaryUnion.Area() - outputRegions[j].Area());
      if (temporaryCost < possibleUnionCost)
      {
        // TODO if the temporaryCost is 0 then we could skip checking the other regions since there exist no better solution
        possibleUnionRegion = temporaryUnion;
        possibleUnionNbr    = j;
        possibleUnionCost   = temporaryCost;
      }
    }

    float newRegionTotalCost = costPerArea * currentRegion.Area() + costNewRegion;

    if (possibleUnionNbr >= 0 && possibleUnionCost < newRegionTotalCost)
    {
      outputRegions[possibleUnionNbr] = possibleUnionRegion;
      totalCost += possibleUnionCost;
    }
    else
    {
      outputRegions.push_back(currentRegion);
      totalCost += newRegionTotalCost;
    }
  }

  return totalCost;
}

float UseAllRegions(vector<CRect> &inputRegions, vector<CRect> &outputRegions)
{
  outputRegions = inputRegions;

  float totalCost = 0.0f;

  for (unsigned int i = 0; i < inputRegions.size(); i++)
  {
    totalCost += inputRegions[i].Area() * costPerArea + costNewRegion;
  }

  return totalCost;
}

void Draw(int mode)
{ 
  for (unsigned int i = 0; i < markedRegions.size(); i++)
    DrawColoredQuad(markedRegions[i], 1.0f, 1.0f, 1.0f, 1.0f);

  vector<CRect> generatedDirtyRegions;
  vector<CRect> gdr[4];

  float cost[4];

  cost[0] = costNewRegion + ((float)(WIDTH * HEIGHT) * costPerArea);
  cost[1] = UnifyRegions(markedRegions, gdr[1]);
  cost[2] = UseAllRegions(markedRegions, gdr[2]);

  cost[3] = CostReduction(markedRegions, gdr[3]);
  vector<CRect> temp2;
  float superSmall = CostReduction(gdr[3], temp2);
  while (cost[3] > superSmall)
  {
    gdr[3] = temp2;
    printf("Even smaller %f against %f\n", cost[3], superSmall);
    cost[3] = superSmall;

    temp2.clear();
    superSmall = CostReduction(gdr[3], temp2);
  }

  mode = max(min(3, mode), 0);

  generatedDirtyRegions = gdr[mode];

  printf("Cost Everything: %i Unify: %i AllRegions: %i CostReduction: %i\n", (int)cost[0], (int)cost[1], (int)cost[2], (int)cost[3]);

  for (unsigned int i = 0; i < generatedDirtyRegions.size(); i++)
    DrawColoredQuad(generatedDirtyRegions[i], 0.2f, 1.0f, 0.0f, 0.0f);


  float currentCost = cost[3];
  float lowestCost = currentCost;
  vector<CRect> lowestRegions;

  for (unsigned int random = 0; random < 500; random++)
  {
    vector<CRect> temp;
    random_shuffle( markedRegions.begin(), markedRegions.end() );
    float newCost = CostReduction(markedRegions, temp);

    if (lowestCost > newCost)
    {
      lowestCost = newCost;
      lowestRegions = temp;
    }
  }
/*
  for (unsigned int i = 0; i < lowestRegions.size(); i++)
    DrawTexturedColoredQuad(lowestRegions[i], 0.2f, 0.0f, 0.0f, 1.0f, grid, false);
*/
  char name[100];
  sprintf(name, "Cost %i cheapest %i", (int)cost[mode], (int)lowestCost);
  SDL_WM_SetCaption(name, name);
}

bool initGL(unsigned int width, unsigned int height)
{
	glClearColor( 0.0f, 0.0f, 0.0f, 0.0f );
  glEnable(GL_BLEND);
  glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

  glViewport( 0, 0, (GLsizei)width, (GLsizei)height );
	glMatrixMode( GL_PROJECTION );
	glLoadIdentity();
  glOrtho(0.0, width, 0.0, height, -1.0f, 1.0f);
  glMatrixMode( GL_MODELVIEW );
  glLoadIdentity( );

  return true;
}

int main( int argc, char **argv )
{
  srand ( time(NULL) );
  SDL_Init( SDL_INIT_EVERYTHING );

  atexit(SDL_Quit);

  const int screenflags = SDL_OPENGL | SDL_GL_DOUBLEBUFFER | SDL_HWSURFACE;

  SDL_Surface *screen = SDL_SetVideoMode( WIDTH, HEIGHT, 32, screenflags );

  SDL_ShowCursor(0);

  if (!initGL(WIDTH, HEIGHT))
    return -1;

#ifdef RANDOMIZE
  for (unsigned int i = 0; i < 20; i++)
  {
    float x1 = rand() % 1180;
    float y1 = rand() % 620;
    float size = 10 + (rand() % 150);
    float x2 = x1 + size;
    float y2 = y1 + size;
  
    markedRegions.push_back(CRect(x1, y1, x2, y2));
  }
#else
  markedRegions.push_back(CRect(  0.0f,   0.0f, 100.0f, 100.0f));
  markedRegions.push_back(CRect(200.0f, 400.0f, 300.0f, 500.0f));
  markedRegions.push_back(CRect(300.0f, 400.0f, 400.0f, 500.0f));
#endif

  int mode = 3;
  SDL_Event event;
  bool needDraw = true;
  while (SDL_WaitEvent(&event))
  {
    if (needDraw)
    {
      glClearColor( 0.0f, 0.0f, 0.0f, 0.0f );
      glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT );

      // Reset transformation matrix
      glLoadIdentity();
      glTranslatef(0.0f, HEIGHT, 0.0f);
      glScalef(1.0f, -1.0f, 1.0f);

      Draw(mode);

      SDL_GL_SwapBuffers();
      needDraw = false;
    }

    switch (event.type) 
    {
      case SDL_QUIT:
        exit(0);
        break;
      case SDL_KEYDOWN:
        needDraw = true;
        switch(event.key.keysym.sym)
        {
          case SDLK_0:
            mode = 0;
            break;
          case SDLK_1:
            mode = 1;
            break;
          case SDLK_2:
            mode = 2;
            break;
          case SDLK_3:
            mode = 3;
            break;
          case SDLK_ESCAPE:
            exit(0);
            break;
          case SDLK_r:
            random_shuffle( markedRegions.begin(), markedRegions.end() );
            break;
          default:
            needDraw = false;
            break;
        }
        break;
      default:
        break;
    }
  }

  return 0;
}