/*
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;
         }
    }

/* Programik pokazuje jak dziala algorytm wyznaczania drzewa rozpinajacego grafu metoda
   przeszukiwania w glab. Dane wejsciowe przedstawione sa za pomoca list incydencji.
   Plik 'in.txt', ktory przechowuje dane wejsciowe wyglada nastepujaco (przyklad):
   ------------------- in.txt --------------------------
           4
           2 3 4
           1 3 4
           1 2 4
           1 2 3
   -----------------------------------------------------
           
    - w pierwszej linii podana jest liczba wierzcholkow grafu.
    -  W kolejnych n liniach umieszczone sa listy incydencji dla kazdego
       z n wierzchokow.
       
    Dane wyjsciowe sa wypisywane na ekranie i przedstawiaja opis krawedzi utworzonego
    drzewa rozpinajacego (tj. pary wierzcholkow).
    
    Literatura: W.Lipski "Kombinatoryka dla programistow"  */

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

struct wierzcholek
{
    int x;
    struct wierzcholek *nast;
};

typedef struct wierzcholek wierzcholek;


/* Tworzenie list incydencji dla kazdego z wierzcholkow */
void stworz_liste(wierzcholek **lista, int y)
{
    wierzcholek *e, *tmp;
    
    e = malloc(sizeof(wierzcholek));
    e->x = y;
    e->nast = NULL;
    
    if(*lista == NULL) *lista = e;
    else
    {
       tmp = *lista;
       while(tmp->nast)
           tmp = tmp->nast;
         
           tmp->nast = e;
    }
}


/* Znajdowanie drzewa rozpinajacego grafu spojnego metoda przeszukiwania w glab */
/*     v - Od ktorego wierzcholka zaczynamy,
       nowy - tablica logiczna z wierzcholkami. Bedzie przyjmowac wartosci 0 i 1,
       tab - tablica z listami incydencji.
*/
void wgd(int v, int *nowy, wierzcholek **tab)
{
     nowy[v] = 0;
     
     while(tab[v])
     {
         if( nowy[ tab[v]->x ])
         {
              printf("%d %d\n",v,tab[v]->x);
              wgd(tab[v]->x,nowy,tab);
         }              
                  
         tab[v] = tab[v]->nast;         
     }
}


/* Czyszczenie pamieci */
void wyczysc(wierzcholek **tab, int liczba_w)
{
     wierzcholek *e;
     int i;
     
     for(i=1;i<=liczba_w;i++)
         while(tab[i])
           {
               e = tab[i]->nast;
               free(tab[i]);
               tab[i] = e;
           }                  
}  


int main()
{
    FILE *fp_in;         /* Uchwyt pliku wejsciowego */
    wierzcholek **tab;   /* Tablica ze wskaznikami na listy incydencji */
    int liczba_w;        /* Liczba wierzcholkow w grafie */
    int i,y;             /* Zmienne pomocnicze */
    char znak;           /* Bedziemy sprawdzac, czy ten znak nie jest koncem wiersza w pliku */ 
    
    
    
    /* Czytamy informacje z pliku */
    fp_in = fopen("in.txt","r");
    if(!fp_in) exit(1);
    
    fscanf(fp_in, "%d", &liczba_w);    /* Pobranie liczby wierzcholkow */
    
    tab = malloc(liczba_w*sizeof(wierzcholek*));   /* Alokacja tablicy ze wskaznikami na listy incydencji */
    for(i=0;i<=liczba_w;i++) tab[i] = NULL;
    i = 1;
        
    while(fscanf(fp_in, "%d", &y) != EOF)
    {
        stworz_liste(&tab[i], y);
        
        znak = fgetc(fp_in);
        if(znak=='\n') i++;
        
    }
    fclose(fp_in);
    
    
    /* Deklaracje oraz wywolanie wlasciwej procedury */
    int *nowy = malloc(liczba_w*sizeof(int));
    for(i=0; i<=liczba_w; i++) nowy[i] = 1;
    
    wgd(1, nowy, tab);
    
    free(nowy);
    wyczysc(tab,liczba_w);
    free(tab);
    
    getchar(); 
    return 0;
}