/*
Algorytm wyznaczający przedział, do którego należy dana wartość. Wejściowymi danymi są:
- przedziały domknięte o krańcach całkowitych, wzajemnie rozłączne, uporządkowane rosnąco
pod względem początków przedziałów. Maksymalna liczba przedziałów wynosi 1000
(zaimplementowałem również losowe wyznaczanie przedziałów rozłącznych).
- wartość rzeczywista, której do przedziału chcemy stwierdzić.
Wynikiem algorytmu jest:
-plik wyjściowy zawierający wszystkie przedziały
- numer kolejny przedziału w przypadku gdy element należy do pewnego przedziału,
- (-1) gdy element nie należy do żadnego z przedziałów.
Przykład:
Przedziały: 10,14 16,22, 30, 60, 110,116, 130,140
Wartość rzeczywista: 30.3
wynik: 3

Przedziały: 1,14 16,22, 30, 60, 110,116, 130,140
Wartość rzeczywista: 117
wynik: -1

Jest to implementacja rekurencyjna oraz iteracyjna. Wstawiony został licznik
porównań między krańcami przedziałów a wartością szukaną.
*/




#include <iostream>

using namespace std;


struct przedzial
       {
        int dol,gora;
       }; 

int licznik1, licznik2;

int method1(const struct przedzial *tab, int n, double x);
int method2(const struct przedzial *tab, int first, int end, double x);



int main()
    {
     int opt,opt2;
     int n;
     int wyn;
     int zg,zd,zzg;
     double x;
     struct przedzial *tab;
     FILE *out;
     do
       {
        cout << "       1. Wprowadz dane do programu" << endl;
        cout << "       2. Znajdz odpowiedni przedzial dla podanej wartosci" << endl;
        cout << "       3. Testuj wykonanie algorytmow" << endl;
        cout << "       4. Koniec programu" << endl << endl << endl;
        cout << "       Wybierz opcje: ";
        cin >> opt;
        
        switch (opt)
               {
                case 1:
                           system ("cls");
                           cout << "      1. Samodzielne wprowadzenie wartosci" << endl;
                           cout << "      2. Losowe wartosci" << endl << endl << endl;
                           cout << "      Wybierz opcje: ";
                           cin >> opt2;
                           if (opt2==1)
                              {
                               system ("cls");
                               cout << "      Podaj liczbe przedzialow: ";
                               cin >> n;
                               tab=new struct przedzial[n];
                               for (int i=0; i<n; ++i)
                                   {
                                    cout << endl << endl << "      Dane dotyczace przedzialu " << i << "/" << n-1 << endl << endl;
                                    cout << "      Podaj zakres dolny przedzialu: ";
                                    cin >> tab[i].dol;
                                    cout << "      Podaj zakres gorny przedzialu: ";
                                    cin >> tab[i].gora;
                                   }
                               cout << endl << "      Podaj szukana wartosc: ";
                               cin >> x;
                               system ("PAUSE");
                              }
                           else
                               {
                                system ("cls");
                                out=fopen("out.txt", "w");
                                cout << "      Podaj liczbe przedzialow: ";
                                cin >> n;
                                zd=0;
                                zg=n*100;
                                tab=new struct przedzial[n];
                                srand(time(NULL));
                                
                                tab[0].dol = rand() % (5 - 0 + 1) + 0;
                                do
                                  tab[0].gora = rand() % (10 - 0 + 1) + 0;
                                while (tab[0].dol > tab[0].gora);
                                
                                
                                cout << "      Dane dotyczace przedzialu " << 0 << "/" << n-1 << endl << endl;
                                     fprintf (out, "      Dane dotyczace przedzialu 0/%d\n", n-1);
                                cout << "      Zakres dolny przedzialu: " << tab[0].dol;
                                     fprintf (out, "      Zakres dolny przedzialu: %d", tab[0].dol);
                                cout << "      Zakres gorny przedzialu: " << tab[0].gora;
                                     fprintf (out, "      Zakres gorny przedzialu: %d\n\n\n", tab[0].gora);
                                
                                for (int i=1; i<n; ++i)
                                   {
                                    cout << endl << endl << "      Dane dotyczace przedzialu " << i << "/" << n-1 << endl << endl;
                                         fprintf (out, "      Dane dotyczace przedzialu %d/%d\n", i, n-1);
                                    do
                                      tab[i].dol = rand() % (i*(zg/n) - (tab[i-1].gora+2) + 1) + tab[i-1].gora;
                                    while (tab[i].dol > i*(zg/n));
                                    cout << "      Zakres dolny przedzialu: " << tab[i].dol;
                                         fprintf (out, "      Zakres dolny przedzialu: %d", tab[i].dol);
                                    
                                    
                                    do
                                      tab[i].gora = rand() % (i*(zg/n) - tab[i].dol + 1) + tab[i].dol;
                                    while ((tab[i].gora > i*(zg/n)) && (tab[i].dol==tab[i].gora));
                                    cout << "      Zakres gorny przedzialu: " << tab[i].gora << endl;
                                         fprintf (out, "      Zakres gorny przedzialu: %d\n\n\n", tab[i].gora);
                                   }
                                cout << endl << endl << "      Podaj szukana wartosc: ";
                                cin >> x;
                                fclose(out);
                                system ("PAUSE");
                               }
                           break;
                           
                case 2:
                           system ("cls");
                           cout << "   ALGORYTM 1:\n";
                           cout << "   Numer przedzialu, w ktorym znajduje sie liczba " << x << " : " << method1(tab,n,x) << endl;
                           cout << "   ALGORYTM 2:\n";
                           cout << "   Numer przedzialu, w ktorym znajduje sie liczba " << x << " : " << method2(tab,0,n,x) << endl << endl << endl;
                           system ("PAUSE");
                           break;
                           
                case 3:
                           system ("cls");
                           cout << "ROZMIAR ZADANIA\t\tLICZNIK OPERACJI\t\tLICZNIK OPERACJI" << endl;
                           cout << "               \t\t   ALGORYTMU I  \t\t  ALGORYTMU II" << endl << endl << endl;
                           cout << "n= " << n << " x=" <<  x << "\t\tlicznik=" << licznik1 << "\t\t\tlicznik=" << licznik2 << "\n\n\n\n\n\n\n\n\n\n";
                           system ("PAUSE");
                           break;
                           
                case 4:
                           break;
                           
                default:
                           system ("cls");
                           cout << "      Blad programu" << endl << endl;
                           system ("PAUSE");
                           break;
               }
        system ("cls");
       }
     while (opt != 4);
     return 0;
    }

int method1(const struct przedzial *tab, int n, double x)
    {
     int first = -1;
     int end = n;
     int mid = 0;
     licznik1=0;    
   
     while (end > first + 1) 
           {
            mid = (first + end) / 2;
            licznik1++;
            if ((x >= tab[mid].dol) && (x <= tab[mid].gora))
               { 
                return mid;
               }
            else
                {
                if (tab[mid].gora < x)
                   {
                    first = mid;
                   }
                else
                     end = mid;
                }
           }      
     
     return -1;
    }
    
int method2(const struct przedzial *tab, int first, int end, double x)
    {
     int mid,wyn;
     if (end < first) return -1;
     if (first == end)
        {
         if ((x >= tab[first].dol) && (x <= tab[first].gora))
            return first;
         else
             return -1;
        }
     else
         {
          mid = (first + end) / 2;
          licznik2++;
          if (x > tab[mid].gora)
             wyn = method2(tab,mid+1,end,x);
          else
             wyn = method2(tab,first,mid,x);
                 
          return wyn;
         }
    }