#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

int rozm();
int *zlicz(string *tab,int n);
string *tworztab(int n);
string *odczyt(string *tab,int n);
void sortuj(string *tab,int Lewy,int Prawy);
int bisekcja(string *tab,string element,int Lewy,int Prawy,int n);
void zapisz(string *tab,int *tab2,int n);
void wypisz(string *tab,int n);
void wypisz(int *tab,int n);
void wypisz(int liczba);

int main(int argc, char *argv[])
{   int n=rozm();
    string arb;
    string *tablica=tworztab(2*n);
    sortuj(odczyt(tablica,n),0,n-1);
    do 
    {cout << "jakie warzywo dolozyc?\n";
    cin >> arb;
    wypisz(bisekcja(tablica,arb,0,2*n-1,2*n));
    wypisz(tablica,2*n-1);}
    while(arb!="exit");
    zapisz(tablica,zlicz(tablica,2*n),2*n);
    
    system("PAUSE");
    return EXIT_SUCCESS;
}
int rozm()
{  ifstream plik;
   char znak;
   int licznik=0;
   plik.open("wyrazy.txt");
    if(plik==NULL) cout << "brak pliku do otwarcia" << endl;
    while (plik.get(znak))
                                    {
                                        if(znak == '\n') licznik++ ;
                                        
                                        } 
   plik.close();
   return (licznik+1);
}
//---------------------
string *tworztab(int n)
{
       string *tab=new string[2*n];
       for(int i=0;i<2*n;i++)
       *(tab+i)="0";
       *(tab+2*n-1)="zzzzzzzzzzzzzzzzzzzzzzzz";
       return tab;
}
//---------------------
string *odczyt(string *tab,int n)
{
       ifstream plik;
       plik.open("wyrazy.txt");
       if(plik==NULL) cout << "brak pliku do otwarcia" << endl;
       for(int i=0;i<n;i++)
       plik >> *(tab+i);
       plik.close();
       
   return tab;
}
//---------------------

void sortuj(string *tab,int Lewy,int Prawy)                     //sortowanie szybkie
    {              
      int i = Lewy;
      int j = Prawy;
      string tmp;
      string x=*(tab+(Lewy+Prawy)/2);
        do
        {
          
          while (*(tab+i) < x) i++;
          while (*(tab+j) > x) j--;
          if (i <= j)
           {
           tmp=*(tab+i);
           *(tab+i)=*(tab+j);
           *(tab+j)=tmp;
           i++;
           j--;
           }
        }
        while(i <= j);
  if (Lewy < j) sortuj(tab,Lewy, j);
  if (Prawy > i) sortuj(tab,i, Prawy);
  
  
}
//----------------------
int *zlicz(string *tab,int n)
{   int *licznik=new int[n];
    for(int i=0;i<n;i++)
    *(licznik+i)=0;
    for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                    //if(i==j) continue;
                    if(*(tab+i)==*(tab+j)) (*(licznik+i))++;
                    }
    return licznik;
}
//----------------------
void zapisz(string *tab,int *tab2,int n)
{
     ofstream plik;
     plik.open("wyrazy2.txt");
     if(plik==NULL) cout << "brak pliku do zapisu" << endl;
     for(int i=1;i<n;i++)
     {       
             if(*(tab+i)==*(tab+i-1) || *(tab+i)=="0") continue;
             plik << *(tab+i) << "\tilosc:" << *(tab2+i) << endl;
             }
             plik.close();
}
//----------------------
void wypisz(string *tab,int n)
{
     for(int i=0;i<n;i++)
     {if(*(tab+i)=="0" || *(tab+i)=="zzzzzzzzzzzzzzzzzzzzzzzz") continue;cout << *(tab+i) << endl;}
}
void wypisz(int *tab,int n)
{
    for(int i=0;i<n;i++)
     cout << *(tab+i) << endl;
}        
void wypisz(int liczba)
{
     cout << liczba << endl;
}       
int bisekcja(string *tab,string element,int Lewy,int Prawy,int n)
{                  
                          
           string tmp;
      string x=*(tab+(Lewy+Prawy)/2);
      int iter=(Lewy+Prawy)/2;           
      int zakres=0;
      for(int i=0;i<n;i++) if(*(tab+i)!="0" && *(tab+i+1)=="0") zakres=i;
      if(element>*(tab+zakres)) *(tab+zakres)=element;
      if(element==x ) {
                                                                              for(int i=n-2;i>iter;i--){
                                                                                                      tmp=*(tab+i+1);
                                                                                                      *(tab+i+1)=*(tab+i);
                                                                                                      *(tab+i+2)=tmp;}
                                                                                                      *(tab+iter+1)=element;
                                                                                                      return iter;
                                                                                                   }                   
      if ((*(tab+(Lewy+Prawy)/2)>=element && *(tab+(Lewy+Prawy)/2-1)<=element) ) {
                                                                              for(int i=n-2;i>iter;i--){
                                                                                                      tmp=*(tab+i+1);
                                                                                                      *(tab+i+1)=*(tab+i);
                                                                                                      *(tab+i+2)=tmp;}
                                                                                                      *(tab+iter)=element;
                                                                                                      return iter;
                                                                                                   }
     
     if(element < x) { Prawy=(Lewy+Prawy)/2;bisekcja(tab,element,Lewy,Prawy,n); }
     if(element > x) { Lewy=(Lewy+Prawy)/2;bisekcja(tab,element,Lewy,Prawy,n);}
       
      
      
}