#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

#ifndef bool
  #define bool int
  #define false 0
  #define true (!false)
#endif

#ifndef max
  #define max(x,y) ((x) > (y) ? (x) : (y))
#endif

#ifndef strlen
  #include <string.h>
#endif

#ifndef strlwr
char* strlwr(char* s){
  for (int i= strlen(s)-1; i >= 0; i--){
    s[i]= (char)tolower(s[i]);
  }
  return s;
}
#endif

#ifndef stricmp
int stricmp(const char* s1, const char* s2){
  int nChars= max(strlen(s1), strlen(s2));
  for (int i= 0; i < nChars; i++){
    if (tolower(s1[i]) < tolower(s2[i])){
      return -1;
    } else if (tolower(s1[i]) > tolower(s2[i])){
      return 1;
    }
  }
  return 0;
}
#endif

//-----------------------------------------------------------------------------

/**
 * Kopieert alleen de velden uit sBuf die zijn aangevinkt in abCutField
 * in sCut.
 */
void copyFields(char* sCut, char* sBuf, char cDelimiter, bool* abCutField){
  int iInField= 1;
  int iInOff= 0;
  int iOutOff= 0;
  bool bFieldTerminated= true;
  while(sBuf[iInOff]){
    if (sBuf[iInOff]==cDelimiter){
      iInField++;
      if (iOutOff > 0){
        bFieldTerminated= false;
      }
    } else if (abCutField[iInField]){
      if (!bFieldTerminated){
        sCut[iOutOff++]= cDelimiter;
        bFieldTerminated= true;
      }
      /* karakters uit dit veld over te nemen in sCut */
      sCut[iOutOff++]= sBuf[iInOff];
    }
    iInOff++;
  }
  sCut[iOutOff]= '\0';
}

//-----------------------------------------------------------------------------

class ArrayList{
  char*** aasN; // array van normale blokken met elk 1024 pointers naar char
  /* asX is een apart gesorteerde 'overlooplijst' die
   * alleen in de methode insert 1024 items kan bevatten
   * en daar dan wordt overgestort in aasN: */
  char**   asX;
  int nMaxBlocks;
  int nBSize;   // aantal items in een blok
  int nItems;	// (aantal normale blokken = nItems/nBSize)
  //---------------------------------------------------------------------------

  /**
   *  Zoekt naar de positie of de invoegpositie van de gegeven string;
   *  geeft false terug indien niet gevonden; iInsert is dan de invoegpositie
   *  die gelegen is in het extra blok (de positie ligt dus tussen 0 en 1023).
   */
  bool find(char* s, int* piInsert){
    bool bFound= find(s, aasN, nItems -(nItems%nBSize), piInsert);
    if (bFound){
      return true;
    }
    bFound= find(s, &asX, nItems%nBSize, piInsert);
    if (bFound){
      return true;
    }
    return false; // niet gevonden in Normale blokken of in het Extra blok
  }
  //---------------------------------------------------------------------------
  /**
   *  Zoekt naar de positie of de invoegpositie van de gegeven string
   *  in de gegeven array van blokken met totaal nNItems items;
   *  geeft false terug indien niet gevonden; iInsert is dan de invoegpositie.
   */
  bool find(char* sFind, char*** aas, int nNItems, int* piInsert);
  //---------------------------------------------------------------------------
  /**
   *  Voegt de gegeven string toe aan asX op de gegeven positie;
   *  stort asX over in aasN als asX door de laatste toevoeging vol raakt.
   *  Geeft false terug als het aantal buffers wordt overschreden.
   */
  bool insert(char* s, int iInsert);
  //---------------------------------------------------------------------------

  public:

  /**
   *  Maakt een nieuwe ArrayList met ruimte voor totaal 1000M aan items.
   */
  ArrayList(){
    nMaxBlocks= 102400;
    nBSize= 10240;
    aasN= new char**[nMaxBlocks]; // pointers naar nog te maken blokken
    asX= new char*[nBSize]; // apart gesorteerde lijst (nog leeg)
    nItems= 0;
  };
  //---------------------------------------------------------------------------
  /**
   *  Onderzoekt de lijst op het voorkomen van de gegeven string.
   *  Geeft true indien gevonden, anders false.
   */
  bool contains(char *s){
    return find(s, NULL);
  }
  //---------------------------------------------------------------------------
  /**
   *  Voegt de gegeven string indien nodig toe aan de lijst.
   *  Geeft true terug als de string (evt. na toevoegen) in de lijst zit.
   */
  bool add(char* s){
    int iInsert;
    if (find(s, &iInsert)){
      return true;
    }
    return insert(s, iInsert);
  }
  //---------------------------------------------------------------------------
  /**
   *  Spoelt de lijst naar stdout met de gegeven scheider tussen de items.
   */
  void spool(char *sSep);
  //---------------------------------------------------------------------------
};
//-----------------------------------------------------------------------------

bool ArrayList::find(char* sFind, char*** aas, int nNItems, int* piInsert){
  /* Deze methode gebruikt bisectie: deelt het te doorzoeken stuk
   * steeds in tweeen en beoordeelt steeds een zijde
   * van het nieuwe snijvlak. */
  int iL= 0;
  int iR= nNItems;
  int nSpan= iR -iL;
  bool bSearch= (nSpan > 0);
  int iN= iL +nSpan/2;
  bool bFound= false;
  while (bSearch){
    char* sN= aas[iN/nBSize][iN%nBSize];
    int nCmp= strcmp(sFind,sN);
    if (nCmp > 0){
      /* gezochte string zit in of net rechts naast het rechter stuk */
      iL= iN;
    } else if (nCmp < 0){
      /* gezochte string zit in of net links naast het linker stuk */
      iR= iN;
    } else{
      bFound= true;
      break;
    }
    if (nSpan==1){
      if (nCmp > 0){
        iN= iR;
      } else{
        iN= iL;
      }
      break; // niet gevonden; invoegpositie wel
    }
    nSpan= iR -iL;
    iN= iL +nSpan/2;
  } // einde zoeklus
  if (piInsert){
    *piInsert= iN;
  }
  return bFound;
}
//-----------------------------------------------------------------------------

bool ArrayList::insert(char* s, int iInsert){
  if (nItems >= nBSize*nMaxBlocks +nBSize -1){
    return false;
  }
  int nXItems= nItems%nBSize;
  char* sNewItem= new char[strlen(s)+1]; // string s gered van destructie
  strcpy(sNewItem,s);
  for (int i= nXItems-1; i >= iInsert; i--){
    asX[i+1]= asX[i];
  }
  asX[iInsert]= sNewItem;
  nItems++;
  if (!(nItems%nBSize)){
    /* asX is vol; overstort nodig. */
    /* Maak een nieuw blok voor aasN */
    aasN[nItems/nBSize -1]= new char*[nBSize];
    int iX= nBSize -1; // grootste en tevens laatste in asX
    int iN= nItems -nBSize -1; // grootste en tevens laatste in 'oude' *aasN
    for (int i= nItems-1; iX >= 0; i--){
      if (iN < 0 || strcmp(asX[iX],aasN[iN/nBSize][iN%nBSize]) > 0){
        /* die in asX is groter dan die in de oude aasN, die eerst dus */
        aasN[i/nBSize][i%nBSize]= asX[iX];
        iX--;
      } else{
        aasN[i/nBSize][i%nBSize]= aasN[iN/nBSize][iN%nBSize];
        iN--;
      }
    }
  }
  return true;
}
//-----------------------------------------------------------------------------


void ArrayList::spool(char *sSep){
  int nX= nItems%nBSize;
  int nN= nItems -nX;
  int iN= 0, iX= 0;
  while (iN < nN || iX < nX){
    char* sOut;
    if (iN == nN){
      sOut= asX[iX++];
    } else if (iX == nX){
      sOut= aasN[iN/nBSize][iN%nBSize];
      iN++;
    } else if (strcmp(asX[iX],aasN[iN/nBSize][iN%nBSize]) < 0){
      sOut= asX[iX++];
    } else{
      sOut= aasN[iN/nBSize][iN%nBSize];
      iN++;
    }
    printf("%s%s",sOut,sSep);
  }
}
//-----------------------------------------------------------------------------


/**
 *  Laatste mededeling aan de gebruiker; geeft 1 terug.
 */
int argsError(){
  fprintf(stderr,"\nProbeer 'select --help' voor meer info.\n");
  return 1;
}
//-----------------------------------------------------------------------------

/**
 *  Snijdt CR/LF af van de gegeven string
 */
void remlf(char* s){
  int iLen= strlen(s);
  while (iLen > 0 && (s[iLen-1]=='\n'||s[iLen-1]=='\r')){
    s[iLen-1]= '\0';
    iLen--;
  }
}
//-----------------------------------------------------------------------------

/**
 *  Aanroep: select x minus/union/intersect y.
 *  Geeft resultaatbestand in stdout.
 */
int main (int nArgs, char* asArg[]){
  bool bUseStdin= false;
  if (nArgs==2 && !strcmp(asArg[1],"--help")){
    printf("Gebruik: select [OPTIES] BESTAND1 OPERAND [[-b] list] BESTAND2"
      "\nZoek naar verschillen, overeenkomsten of de som van twee bestanden.\n"
      "In de resultaatlijst komt iedere regel maar een keer voor.\n");
    printf("\nOPTIES:\n"
      "  -a         vermeld alle regels, niet alleen unieke\n"
      "               (alleen met operand MINUS, niet met optie -s)\n"
      "  -i         maak geen onderscheid tussen hoofd- en kleine letters\n"
      "  -s         sorteer de resultaatlijst\n"
      "  -v         tel verwerkte regels\n"
      );

    printf("\nOPERAND:\n"
      "  UNION      geef een gesorteerde, unieke lijst met regels in 1 en 2\n"
      "  MINUS      geef regels in 1 die niet in 2 voorkomen\n"
      "  INTERSECT  geef regels die in 1 en in 2 voorkomen\n"
      "  CUTINT     geef regels in 1 waarvan het uitgeknipte deel in 2 voorkomt.\n");
    printf("\nMeldt storingen bij <koen.brinkman@cnn.controlec.nl>\n");
    return 0;
  } else if (nArgs < 3){
    fprintf(stderr,"Te weinig argumenten.\n");
    return argsError();
  }
  int nOptieArgs= 0;
  int nOpdArgs= 0; // opties (parameters) van de operand (m.n. CUTINT)
  bool bIgnoreCase= false;
  bool bSortOutput= false;
  bool bNotUnique= false;
  bool bVerbose= false;
  while (asArg[1+nOptieArgs][0]=='-' && strlen(asArg[1+nOptieArgs]) > 1){
    for (int i= 1; i < strlen(asArg[1+nOptieArgs]); i++){
      char cOptie= asArg[1+nOptieArgs][i];
      if (cOptie=='i'){
        bIgnoreCase= true;
      } else if (cOptie=='s'){
        bSortOutput= true;
      } else if (cOptie=='a'){
        bNotUnique= true;
      } else if (cOptie=='v'){
        bVerbose= true;
      } else{
        fprintf(stderr,"Onjuiste optie: '-%c'\n", cOptie);
        return argsError();
      }
    }
    nOptieArgs++;
  }
  bool bMINUS= false;
  bool bUNION= false;
  bool bINTERSECT= false;
  bool bCUTINT= false;
  bool bDELIMIT_FIELDS= false;
  bool bDELIMIT_BYTES= false;
  char cDelimiter= '\t';
  int iCutFrom;         // gebruikt bij bDELIMIT_BYTES
  int iCutTo;           // gebruikt bij bDELIMIT_BYTES
  bool abCutField[4096]; // gebruikt bij bDELIMIT_FIELDS
  for (int i= 0; i < 4096; i++){
    abCutField[i]= false;
  }

  if (!stricmp(asArg[nOptieArgs+2],"MINUS")){
    bMINUS= true;
  } else if (!stricmp(asArg[nOptieArgs+2],"UNION")){
    bUNION= true;
  } else if (!stricmp(asArg[nOptieArgs+2],"INTERSECT")){
    bINTERSECT= true;
  } else if (!stricmp(asArg[nOptieArgs+2],"CUTINT")){
    bCUTINT= true;
    if (!strcmp(asArg[nOptieArgs+3],"-b")){
      bDELIMIT_BYTES= true;
      nOpdArgs= 2;
    } else if (!strncmp(asArg[nOptieArgs+3],"-d",2)){
      bDELIMIT_FIELDS= true;
      cDelimiter= asArg[nOptieArgs+3][2];
      nOpdArgs= 3;
    } else if (!strcmp(asArg[nOptieArgs+3],"-f")){
      bDELIMIT_FIELDS= true;
      nOpdArgs= 2;
    } else if (asArg[nOptieArgs+3][0]=='-'){
      fprintf(stderr,"Verwacht: '-b' i.p.v. '%s'\n", asArg[nOptieArgs+3]);
      return argsError();
    } else{
      bDELIMIT_FIELDS= true;
      nOpdArgs= 1;
    }
    char* pszList= asArg[nOptieArgs +nOpdArgs +2];
    for (int i= 0; i <= strlen(pszList); i++){
      if (pszList[i]=='-'){
        pszList[i]= '\0';
        iCutFrom= atoi(pszList);
        iCutTo=   atoi(pszList+i+1);
        for (int j= iCutFrom; j <= iCutTo; j++){
          abCutField[j]= true;
        }
        break;
      } else if (pszList[i]==','){ //
        pszList[i]= '\0';
        iCutFrom= atoi(pszList);
        iCutTo=   atoi(pszList+i+1);
        abCutField[iCutFrom]= true;
        abCutField[iCutTo]=   true;
        break;
      } else if (pszList[i]=='\0'){
        iCutFrom= atoi(pszList);
        iCutTo=   iCutFrom;
        abCutField[iCutFrom]= true;
        abCutField[iCutTo]=   true;
        break;
      }
    }
  } else{
    fprintf(stderr,"Onjuiste operand: '%s'\n", asArg[nOptieArgs+2]);
    return argsError();
  }
  if (nArgs-nOptieArgs-nOpdArgs==3){
    bUseStdin= true;
  }
  char* psFile1= asArg[nOptieArgs+1];
  char* psFile2= bUseStdin ? (char*)"stdin" : asArg[nOptieArgs+nOpdArgs+3];
  /* Gebruik stdin voor 1e bestand als daar 'stdin' of '-' genoemd wordt */
  FILE* pF1= (!strcmp(psFile1,"stdin") || !strcmp(psFile1,"-"))
             ? stdin
             : fopen(psFile1,"rt");
  if (!pF1){
    perror(psFile1);
    return 1;
  }
  FILE* pF2= bUseStdin ? stdin : fopen(psFile2,"rt");
  if (!pF2){
    perror(psFile2);
    return 1;
  }

  ArrayList al2, al1;
  int BUFSIZE= 4096;
  char sBuf[4096];

  int nRead2= 0;
  while (fgets(sBuf,BUFSIZE,pF2)){
    nRead2++;
    if (bVerbose){
      fprintf(stderr,"\r%d",nRead2);
    }
    remlf(sBuf);
    if (bIgnoreCase){
      strlwr(sBuf);
    }
    if (!al2.contains(sBuf)){
      if (bUNION && !bSortOutput){
        printf("%s\n",sBuf);
      }
      al2.add(sBuf);
    }
  }
  if (bVerbose){
    fprintf(stderr,"\n");
  }  

  int nRead1= 0;
  while (fgets(sBuf,BUFSIZE,pF1)){
    nRead1++;
    if (bVerbose){
      fprintf(stderr,"\r%d",nRead1);
    }  
    remlf(sBuf);
    if (bIgnoreCase){
      strlwr(sBuf);
    }
    if (bMINUS){
      if (bNotUnique){
        if (!al2.contains(sBuf)){
          printf("%s\n",sBuf);
        }
      } else if ((!al2.contains(sBuf)) && (!al1.contains(sBuf))){
        al1.add(sBuf);
        if (!bSortOutput){
          printf("%s\n",sBuf);
        }
      }
    } else if (bUNION){
      if (!al2.contains(sBuf)){
        al2.add(sBuf);
        if (!bSortOutput){
          printf("%s\n",sBuf);
        }
      }
    } else if (bINTERSECT){
      if (al2.contains(sBuf) && !al1.contains(sBuf)){
        al1.add(sBuf);
        if (!bSortOutput){
          printf("%s\n",sBuf);
        }
      }
    } else if (bCUTINT){
      /* knip het te vergelijken stuk eruit */
      char sCut[4096];
      if (bDELIMIT_BYTES){
        strncpy(sCut, sBuf+iCutFrom-1, 1+iCutTo-iCutFrom);
        sCut[1+iCutTo-iCutFrom]= '\0';
      } else if (bDELIMIT_FIELDS){
        /* kopieer alle te knippen velden achter elkaar in sCut */
        copyFields(sCut, sBuf, cDelimiter, abCutField);
      }

      if (al2.contains(sCut) && !al1.contains(sBuf)){
        al1.add(sBuf);
        if (!bSortOutput){
          printf("%s\n",sBuf);
        }
      }
    }
  }
  if (bVerbose){
    fprintf(stderr,"\n");
  }  

  if (bSortOutput){
    if (bUNION){
      al2.spool("\n");
    } else if (bCUTINT || bINTERSECT || bMINUS){
      al1.spool("\n");
    }
  }

  if (pF2!=stdin){
    fclose(pF2);
  }
  if (pF1!=stdin){
    fclose(pF1);
  }
  return 0;
}
//-----------------------------------------------------------------------------