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

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

using namespace std;

float costNewRegion = 10.0f;
float costPerArea   = 0.0001f;

float InternalCostReduction(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;
}

bool MyDataSortPredicate(const CRect& d1, const CRect& d2)
{
  return d1.Area() > d2.Area();
}

float CostReduction(vector<CRect> &inputRegions, vector<CRect> &outputRegions, bool recursive = false)
{
//  sort(inputRegions.begin(), inputRegions.end(), MyDataSortPredicate);
  float cost = InternalCostReduction(inputRegions, outputRegions);

  if (recursive)
  {
    vector<CRect> temp;
    sort(outputRegions.begin(), outputRegions.end(), MyDataSortPredicate);
    float smallerCost = InternalCostReduction(outputRegions, temp);
    if (smallerCost < cost)
      return CostReduction(temp, outputRegions);
    else
    {
      outputRegions = temp;
      cost = smallerCost;
    }
  }

  return cost;
}

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;
}

int main( int argc, char **argv )
{
  srand ( time(NULL) );
  int sortedFail = 0, luckyFail = 0;
  int sortedSuccess = 0, luckySuccess = 0;

  float totalCostAlgorithm = 0.0f;
  float totalCostLowest = 0.0f;
  float totalCostUnion = 0.0f;

  for (unsigned int test = 0; test < 500; test++)
  {
    vector<CRect> markedRegions;

    for (unsigned int i = 0; i < 20; i++)
    {
      float x1 = rand() % 1180;
      float y1 = rand() % 620;
      float size = 10 + (rand() % 100);
      float x2 = x1 + size;
      float y2 = y1 + size;
    
      markedRegions.push_back(CRect(x1, y1, x2, y2));
    }

    vector<CRect> generatedDirtyRegions;
    float currentCost = (int)CostReduction(markedRegions, generatedDirtyRegions);
    float lowestCost = currentCost;

    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;
    }

    totalCostAlgorithm  += currentCost;
    totalCostLowest     += lowestCost;
    totalCostUnion      += UnifyRegions(markedRegions, generatedDirtyRegions);

    if ((int)currentCost != (int)lowestCost)
    {
      printf("currentCost %f lowest %f\n", currentCost, lowestCost);
      //printf("Test %i failed with sortedCost %i while lowest cost is %i\n", test, sortedCost, lowestCost);
      sortedFail++;
    }
    else
      sortedSuccess++;
  }

  int sortedTotal = sortedFail + sortedSuccess;
  printf("Failures %i / %i which means a failrate of %f\n", sortedFail, sortedTotal, (float)sortedFail / (float)sortedTotal);
  printf("Lowesttotal / algo total %f and lowesttotal / uniontotal %f\n", totalCostAlgorithm / totalCostLowest, totalCostUnion / totalCostLowest);
  return 0;
}