#include <stdio.h>
#include <fstream.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
  int numberofchars;
  int sortarray [256][256];
  int sortarraycopy [256][256];
  int sortarray2 [256][256];
  int xvalues [256];        // used for smart sorting
  int yvalues [256];        // used for smart sorting
  float zvalues [256][256]; // used for smart sorting
  int charset [256*8];
  int solution [256];
  int bestsolution [256];
  int bin [256*8];
  int checkeduntil;
  int pointers [256];
  FILE *in;
  FILE *out;

  //input charsetdata

  int counter=0;
  int counter2=0;
  int counter3=0;
  int inputbyte=0;

  in = fopen ("CHARSET.PRG","rb");    // open charset
  fgetc(in);                          // load adress
  fgetc(in);

  while(feof(in)==0) {
      charset[counter]=fgetc(in);
      counter++;
  }

  numberofchars = counter/8;
  cout << numberofchars << " chars read." << endl;

  fclose(in);                          // close stream


  // calculate overlap for all char-pairs

  cout << "calculating overlap matrix";

  int char1,char2,overlap,maxoverlap;
  bool overlapping;

  for (char1=0;char1<numberofchars;char1++){
    for (char2=0;char2<numberofchars;char2++){

      // calculate overlap for char pair
      maxoverlap=0;
      for (overlap=7;overlap>0;overlap--){
        overlapping=true;
        for (counter=0;counter<overlap;counter++){
          if (charset[char1*8+(8-overlap+counter)]!=charset[char2*8+counter]) {
            overlapping=false;
          } // if
        } // for
        if (overlapping==true && overlap>maxoverlap) {maxoverlap=overlap;}
      } // for overlap
    sortarray[char1][char2]=maxoverlap;
    sortarraycopy[char1][char2]=maxoverlap;
    }//for char2
    if (char1 % 16==0) {cout << ".";}
  }//for char1
  cout << endl;

  //-----------------------------------------------------
  // determine which chars NOT to use for certain pairs -
  //-----------------------------------------------------

  // [AB] char pair -> x value == total amount of overlap for a certain A
  // char with _all_ other B chars
  // y-value == total amount of overlap for a certain B char with _all_ other
  // A chars
  // Z == x/y -> sort for lowest z-value

  // clear x-values & y-values

  for (counter=0;counter<numberofchars;counter++){
    xvalues[counter]=0;
    yvalues[counter]=0;
  }// for counter

  // calculate x- & y-values

  for (counter=0;counter<numberofchars;counter++){
    for (counter2=0;counter2<numberofchars;counter2++){
      xvalues[counter]+=(int)pow(sortarray[counter][counter2],2);
      yvalues[counter2]+=(int)pow(sortarray[counter][counter2],2);
    }//for counter2
  }// for counter

  // calculate z-values

  for (counter=0;counter<numberofchars;counter++){
    for (counter2=0;counter2<numberofchars;counter2++){
      zvalues[counter][counter2]=((float)xvalues[counter])/((float)yvalues[counter2]);
    }// for counter2
  }// for counter

  //-----------------
  // sort char-pairs-
  //-----------------

  cout << "Sorting overlap values." << endl;

  int occurances [8];
  int char3;
  int random;
  float maxzvalue;
  int maxcharzvalue;

  for (char1=0;char1<numberofchars;char1++){

    //-------------------------------------------------
    // count how many times a certain overlap occurs  -
    //-------------------------------------------------
    for (counter=0;counter<8;counter++) {occurances[counter]=0;}   // clear overlap occurances table
    for (char2=0;char2<numberofchars;char2++){
      occurances[sortarray[char1][char2]]++;
    } // for char2

    // starting with overlap=7, select a random char with that overlap and store it in sortarray2

    counter2=0;

    for (overlap=7;overlap>-1;overlap--){                          // all overlaps from 7 to 0
      for (counter=0;occurances[overlap]>0;occurances[overlap]--){             // fetch n chars
        maxzvalue=0;
        maxcharzvalue=0;
        for (counter3=0;counter3<numberofchars;counter3++){        // get the char with lowest z-value
          if (sortarraycopy[char1][counter3]==overlap) {
            if (zvalues[char1][counter3]>maxzvalue){
              maxzvalue=zvalues[char1][counter3];
              maxcharzvalue=counter3;
            } // if
          } // if
        } // for counter3
        sortarray2[char1][counter2]=maxcharzvalue;                         // store fetched char
        counter2++;
        sortarraycopy[char1][maxcharzvalue]=-1;
      } // for counter                                             // fetch another char
    } // for overlap                                               // next overlap
  } // for char1                                                   // all char-pairs

  // go through permutations...

  int savedbytes;
  int maxsavedbytes = 0;
  int usedchars [256];
  int usedchars2 [256];
  int runs = 0;
  int charsleft;
  int orderedchars[256];
  int solcount=0;
  int bytes,minbytes;

  cout << "Finding optimum solution..." << endl;

  while (1){
    for (counter=0;counter<numberofchars;counter++){
      //usedchars[counter]=counter;
      usedchars2[counter]=0;}  // clear used chars
    runs++;
    savedbytes=checkeduntil=0;
    minbytes=0;
    charsleft=numberofchars-1;
    bytes=0;

    // pick a random char to start with

    char1= (int) ( (double)rand()/(double)(RAND_MAX+1) * numberofchars);
    //char1=runs%numberofchars;

    for (counter=0;counter<8;counter++){bin[bytes+counter]=charset[char1*8+counter];}; // add char to bin
    pointers[char1]=0;
    bytes+=8;
    solution[0]=char1;
    solcount=1;

    // we used that char...

    usedchars2[char1]=1;
    //for (counter=char1;counter<charsleft;counter++){usedchars[counter]=usedchars[counter+1];} // for

    // pick another char, randomly weighted

    while (charsleft>0){

      // make sorted table of all chars that are left
      counter2=0;
      for (counter=0;counter<numberofchars;counter++){
        if (usedchars2[ (sortarray2[char1][counter]) ]==0){
          orderedchars[counter2]=sortarray2[char1][counter];
          counter2++;
        } // if
      } // for

      random = (int) ( (pow( ((double)rand()/(double)(RAND_MAX+1) ),100)) * (charsleft/4));
      char2 = orderedchars[random];
      solution[solcount]=char2;
      solcount++;
      pointers[char2]=bytes-sortarray[char1][char2];
      usedchars2[char2]=1;
      charsleft--;
      //for (counter=char2;counter<charsleft;counter++){usedchars[counter]=usedchars[counter+1];} // for
      for (counter=sortarray[char1][char2];counter<8;counter++){                //store extra bytes in bin
        bin[bytes+counter-(sortarray[char1][char2])]=charset[char2*8+counter];
      } // for
      bytes+=(8-sortarray[char1][char2]);     //extra bytes - overlapping bytes
      savedbytes+=(sortarray[char1][char2]);
      char1=char2;

      // check if we can fit one of the left chars in the bin

      for(counter=0;counter<numberofchars;counter++){       // check all left chars
        if (!usedchars2[counter]){
          for (counter2=checkeduntil;counter2<bytes-7;counter2++){   // check whole bin
            for (counter3=0;counter3<8;counter3++){       // check 8 bytes in char
              if (bin[counter2+counter3]!=charset[counter*8+counter3]){
                counter3=10;       // stop checking..
              } // if
            } //for counter3
            if (counter3<10){
              savedbytes+=8;                       // 8 bytes saved
              usedchars2[counter]=1;   // mark char as checked
              solution[solcount]=-counter;  //store in solution
              solcount++;
              charsleft--;                         // one char less
              pointers[counter]=counter2;
              counter2=bytes;                      // stop looking for this char
              //for (counter3=counter;counter3<charsleft;counter3++){usedchars[counter3]=usedchars[counter3+1];} // for
            } // if counter3
          } // for counter2
        } // if
      } // for counter
      checkeduntil=bytes-7;
    } // while

    if (savedbytes>maxsavedbytes) {
      maxsavedbytes=savedbytes;
      cout << "best solution after " << runs << " permutations, saving " << maxsavedbytes << " bytes" << endl;
      for (counter=0;counter<numberofchars;counter++){
        bestsolution[counter]=solution[counter];
      }

      //--------------------------------------------------------------------
      // check solution for correctness!

      savedbytes=0;
      for (counter=0;counter<numberofchars;counter++){usedchars[counter]=0;}
      for (counter=0;counter<numberofchars;counter++){
        if (usedchars[abs( bestsolution[counter] )]) {cout << "ERROR! CHARS DOUBLE! : " << bestsolution[counter] << endl;}
        usedchars[abs(bestsolution[counter])]=1;
        if (counter>0) {
          if (bestsolution[counter]<0) {savedbytes+=8;}
          else {savedbytes+=sortarray[char2][bestsolution[counter]];}
        } // if
        if (bestsolution[counter]>-1){char2=bestsolution[counter];}  // put last attached byte in char2
      } // for
      if (savedbytes!=maxsavedbytes){cout << "ERROR! #saved bytes not correct! : " << savedbytes << ", " << bytes << endl;}
      //---------------------------------------------------------------------
      // write solution
      out=fopen("solution.txt","w");
      fputs(";pointer table for clip chars\n\nclipcharslow\n",out);

      //-------------------------
      // output pointer table   -
      //-------------------------

      charsleft=numberofchars;
      counter=0;
      while (charsleft>0){
        if(counter%8==0){fputs("        .byte ",out);}
        fputs("<(clipcharsdata+",out);
        fprintf(out,"%i)",pointers[counter]);
        if (pointers[counter]<100){fputs(" ",out);}
        if (pointers[counter]<10){fputs(" ",out);}
        charsleft--;
        counter++;
        if(counter%8==0){
          fputs("\n",out);
        }//if
        else{
          if(charsleft>0) {fputs(",",out);}
          else {fputs("\n",out);}
        }// else
      } // while charsleft
      fputs("\n",out);

      //---------------------
      // output pointerhigh -
      //---------------------

      fputs("clipcharshigh\n",out);
      charsleft=numberofchars;
      counter=0;
      while (charsleft>0){
        if(counter%8==0){fputs("        .byte ",out);}
        fputs(">(clipcharsdata+",out);
        fprintf(out,"%i)",pointers[counter]);
        if (pointers[counter]<100){fputs(" ",out);}
        if (pointers[counter]<10){fputs(" ",out);}
        charsleft--;
        counter++;
        if(counter%8==0){
          fputs("\n",out);
        }//if
        else{
          if(charsleft>0) {fputs(",",out);}
          else {fputs("\n",out);}
        }// else
      } // while charsleft
      fputs("\nclipcharsdata\n",out);

      //----------------------
      // output charsetdata  -
      //----------------------

      counter=0;
      while(counter<bytes){
        if(counter%32==0){fputs("        .byte ",out);}
        fprintf(out,"%i",bin[counter]);
        if (bin[counter]<100){fputs(" ",out);}
        if (bin[counter]<10){fputs(" ",out);}
        counter++;
        if(counter%32==0){
          fputs("\n",out);
        }//if
        else{
          if(counter<bytes) {fputs(",",out);}
          else {fputs("\n",out);}
        }// else
      } // while
      fputs("\n",out);
      fclose(out);

      //---------------------------------------------------------------------
    } // if
  } // while

  // output best solution

  cout << "Best solution found :" << endl << bestsolution[0];
  for (counter=1;counter<numberofchars;counter++){cout << "," << bestsolution[counter];}
  cout << endl;

  return 0;
}
