/*

Unos brojeva u neopadajuce sortiranu listu.

*/


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


struct cvor {
                int podatak;                // sadrzaj cvora
                struct cvor *sledeci;       // i pointer na sledeceg clana
            };
typedef struct cvor CVOR;                   // jedan cvor liste CVOR
typedef CVOR* PCVOR;                        // pointer na listu CVOR


// Prikazuje sadrzaj cvorova liste glava
void prikazi_listu(char *tekst, PCVOR glava)
{
    printf("\n%s",tekst);

    if(glava == NULL)
        printf(" prazna. \n");
    else
        while(glava) {
            printf("%4d",glava->podatak);
            glava = glava->sledeci;
        }
    printf("\n");
}


void dodaj_broj_na_kraj(PCVOR *glava,int broj) {
    PCVOR novi;
    PCVOR tek;

    // moramo da pazimo da li je lista prazna ili ne.
    // Ako je glava = NULL onda je isto kao da ubacujemo na pocetak.
    novi = (PCVOR)malloc(sizeof(CVOR));
    novi -> podatak = broj;
    novi -> sledeci = NULL;

    if(*glava == NULL)  // onda je element jedini i prvi
        *glava = novi;
    else  {             // ako element nije prvi
        tek=*glava;
        while(tek->sledeci != NULL)
            tek=tek->sledeci;
        tek->sledeci=novi;
    }
}


// formira listu
void formiraj_neopadajucu_listu(PCVOR *glava)
{
    dodaj_broj_na_kraj(glava,2);
    dodaj_broj_na_kraj(glava,4);
    dodaj_broj_na_kraj(glava,6);
    dodaj_broj_na_kraj(glava,8);
    dodaj_broj_na_kraj(glava,10);
    dodaj_broj_na_kraj(glava,12);
    dodaj_broj_na_kraj(glava,14);
}


void napravi_novi_cvor(PCVOR *novi,int broj)
{
    *novi=(PCVOR)malloc(sizeof(CVOR));

    if(*novi == NULL){
        printf("\n Nije uspela rezervacija memorije za novi cvor. \n");
        exit(1);
    }

    (*novi)->podatak = broj;
    (*novi)->sledeci = NULL;
}


void dodaj_cvor_na_pocetak(PCVOR *glava,PCVOR novi)
{
    if(*glava != NULL)
        novi->sledeci=*glava;

    *glava=novi;
}


// Brise celu listu glava.
// Brisemo cvor po cvor tako sto ustvari stalno brisemo prvi cvor.
void obrisi_celu_listu(PCVOR *glava)
{
   PCVOR tek = *glava;
   while ( tek ){
      tek = tek->sledeci;
      free (*glava);
      *glava = tek;
   }
}


// dodaje broj u neopadajuce sortiranu listu
void dodaj_broj_u_neopadajuce_sortiranu_listu(PCVOR *glava,int KojiBroj)
{
    PCVOR prethodni=NULL,tek,novi;

    novi=(PCVOR)malloc(sizeof(CVOR));
    if(novi==NULL){
        printf("\n Greska pri rezervisanju memorije za cvor novi. \n");
    }
    novi->podatak=KojiBroj;
    novi->sledeci=NULL;

    if(*glava == NULL){ // ako je lista prazna
        *glava=novi;
    }
    else{               // ako lista nije prazna
        tek=*glava;

        while( tek->podatak <= KojiBroj && tek->sledeci != NULL){
            prethodni=tek;
            tek=tek->sledeci;
        }

        if(tek->podatak >= KojiBroj){   // ako je broj u listi veci ili jednak od KojiBroj
            if(prethodni == NULL){          // ako je to prvi element
                novi->sledeci=*glava;           // dodaj na pocetak
                *glava=novi;
            }else{                          // ako nije prvi element
                novi->sledeci=tek;              // dodaj levo od tek
                prethodni->sledeci=novi;
            }
        }else{                          // ako je broj u listi manji od KojiBroj
            tek->sledeci=novi;              // dodaj desno od tek
        }
    }
}


int main(void)
{
    PCVOR glava = NULL;     // deklarisemo listu (OBAVEZNO =NULL)

    formiraj_neopadajucu_listu(&glava);
    prikazi_listu(" Lista: ",glava);

    dodaj_broj_u_neopadajuce_sortiranu_listu(&glava,7);
    dodaj_broj_u_neopadajuce_sortiranu_listu(&glava,15);
    dodaj_broj_u_neopadajuce_sortiranu_listu(&glava,1);
    dodaj_broj_u_neopadajuce_sortiranu_listu(&glava,17);
    dodaj_broj_u_neopadajuce_sortiranu_listu(&glava,3);
    prikazi_listu(" Lista: ",glava);

    obrisi_celu_listu(&glava);
    prikazi_listu(" Lista: ",glava);

    return 0;
}