#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>
#include <fstream.h>

#include "e:\opt\common\timings.h"

int main(int argc, char *argv[])
{
    const int BUFCOUNT = 256;
    const int TOTAL_BUFFER = 16*1048576;
    const int INPUTLINESIZE = 1024;
    char InputLine[INPUTLINESIZE];
    char* BigBuffer = new char [TOTAL_BUFFER];
    char** Buffer = new char* [BUFCOUNT];
    int* BufferSize = new int[BUFCOUNT];
    int* BufferCharCount = new int[BUFCOUNT];
    int* Displacement = new int[BUFCOUNT];
    int* TotalDisplacement = new int[BUFCOUNT];
    char CurrentChar;
    char* InputFileName;
    char* OutputFileName;
    ifstream InputFile;
    ofstream OutputFile;
    int PassCount;
    int CurrentLength;
    int NewLength;
    int LineLength;
    char* OriginalInputFileName;
    char* OriginalOutputFileName;
    int TotalKeys = 0;
    int TotalData = 0;
    bool StatisticsDisplayed = false;
    int TotalWrites = 0;
    int i;
    double BufferRatio;
    int TotalBufferSize;

    if (argc < 4)
        {
        printf("Usage: zensort passcount infile outfile\n");
        exit(1);
        }
    else
        {
        PassCount = atoi(argv[1]);
        OriginalInputFileName = argv[2];
        OriginalOutputFileName = argv[3];
        }

char temp[100];
start_timing();

    for (int Pass = PassCount - 1; Pass >= 0; Pass --)
        {

        if ((PassCount - Pass) % 2 == 1)
            {
            InputFileName = OriginalInputFileName;
            OutputFileName = OriginalOutputFileName;
            }
        else
            {
            InputFileName = OriginalOutputFileName;
            OutputFileName = OriginalInputFileName;
            }

        InputFile.open(InputFileName,ios::in|ios::binary);
        OutputFile.open(OutputFileName,ios::out|ios::binary);

        for (i = 0; i < BUFCOUNT; i ++)
            {
            Displacement[i] = 0;
            TotalDisplacement[i] = 0;
            }

        while (true)
            {
            InputFile.getline(InputLine,INPUTLINESIZE);
            if (!InputFile)
                break;
            TotalKeys ++;
            LineLength = strlen(InputLine);
            if (Pass >= LineLength)
                CurrentChar = 0;
            else
                CurrentChar = InputLine[Pass];
            Displacement[CurrentChar] += LineLength + 1;
            }
        InputFile.close();

        for (i = 1; i < BUFCOUNT; i ++)
            TotalDisplacement[i] = TotalDisplacement[i-1] + Displacement[i-1];

        if (TotalData == 0)
           {
           for (i = 0; i < BUFCOUNT; i ++)
              TotalData += Displacement[i];
           BufferRatio = (double) TOTAL_BUFFER / TotalData;
           }

        TotalBufferSize = 0;
        for (i = 0; i < BUFCOUNT; i ++)
            {
            BufferSize[i] = (int) (BufferRatio*Displacement[i]);
            if (BufferSize[i] == 0)
              Buffer[i] = 0;
            else
              {
              Buffer[i] = BigBuffer + TotalBufferSize;
              TotalBufferSize += BufferSize[i];
              }
            BufferCharCount[i] = 0;
            }

    memset(BigBuffer,0,TOTAL_BUFFER);

if ((Pass == PassCount - 1) && StatisticsDisplayed == false)
  {
  printf("Total buffer space: %d\n",TOTAL_BUFFER);
  printf("Total keys: %d\n", TotalKeys);
  printf("Total data: %d\n", TotalData);
  StatisticsDisplayed = true;
  }

sprintf(temp,"Finished counting on pass %d",PassCount-Pass);
timing(temp);

        InputFile.open(InputFileName,ios::in|ios::binary);

        while (true)
            {
            InputFile.getline(InputLine,INPUTLINESIZE);
            if (!InputFile)
                break;
            LineLength = strlen(InputLine)+1;
            strcpy(InputLine+LineLength-1,"\n");
            if (Pass >= LineLength-1)
                CurrentChar = 0;
            else
                CurrentChar = InputLine[Pass];
            CurrentLength = BufferCharCount[CurrentChar];
            NewLength =  CurrentLength + LineLength;
            if (NewLength >= BufferSize[CurrentChar])
                {
                OutputFile.seekp(TotalDisplacement[CurrentChar]);
                TotalDisplacement[CurrentChar] += CurrentLength;
                OutputFile.write(Buffer[CurrentChar],CurrentLength);
                TotalWrites ++;
                memset(Buffer[CurrentChar],0,BufferSize[CurrentChar]);
                BufferCharCount[CurrentChar] = 0;
                }
            strcpy(Buffer[CurrentChar]+BufferCharCount[CurrentChar],InputLine);
            BufferCharCount[CurrentChar] += strlen(InputLine);
            }

        for (i = 0; i < BUFCOUNT; i ++)
            {
            if (Buffer[i])
                {
                CurrentLength = BufferCharCount[i];
                if (CurrentLength > 0)
                    {
                    OutputFile.seekp(TotalDisplacement[i]);
                    OutputFile.write(Buffer[i],CurrentLength);
                    TotalWrites ++;
                    }
                }
            }
        InputFile.close();
        OutputFile.close();


sprintf(temp,"Finished distributing on pass %d",PassCount-Pass);
timing(temp);
    }

    printf("Total writes: %d\n", TotalWrites);
    
    end_timing();

    return 0;
}