//SDIZO I1 213A LAB01
//Mateusz Rynkiewicz
//rm39424@zut.edu.pl
#define _CRTDBG_MAP_ALLOC
#include "stdafx.h"
#include <string>
#include <iostream>
#include <ctype.h>
#include <time.h>


struct Lista {
    int a; //kluczowa, wyjatkowa
    double b;
    char c;
    Lista* next;
    Lista* prev;
};

//Wstawia nowy element za podany
void AddAfter(Lista* start, Lista* nowa) {
    nowa->prev = start;
    nowa->next = start->next;
    start->next->prev = nowa;
    start->next = nowa;
}
//Wstawia nowy element przed podany
void AddBefore(Lista* start, Lista* nowa) {
    nowa->next = start;
    nowa->prev = start->prev;
    start->prev->next = nowa;
    start->prev = nowa;
}
//wstawienie elementu do listy
Lista* WstawElement(Lista* start, Lista* nowy) {
    //gdy zero elementów

    if (start->a == NULL) {
        start->a = nowy->a;
        start -> b = rand();
        start->c = 'T';
        start->next = start;
        start->prev = start;
        return start;
    }


    //gdy mniejszy element
    if (start->a > nowy->a) {
        AddBefore(start, nowy);
        return  nowy;
    }
    //gdy jeden element
    if (start->a == start->next->a) {
        AddAfter(start, nowy);
        return start;
    }
    //gdy wiekszy lub rowny element
    Lista* obecny = start;
    for (;;) {
        if (obecny->a == nowy->a) {
            std::cout << "Klucz jest juz zajety" << std::endl;
            return start;
        }

        if ((obecny->a < nowy->a) && ((obecny->next->a > nowy->a)||(obecny->next->a < obecny->a))) {
            AddAfter(obecny, nowy);
            return start;
        }
        obecny = obecny->next;

    }

}
//Element z 1. (a podane, b losowe, c='T'
Lista* ElementZad1(Lista* start, int klucz) {
    Lista* nowy = (Lista*)malloc(sizeof(Lista));//nowy element
    nowy->a = klucz;
    nowy->b = rand();
    nowy->c = 'T';
    start = WstawElement(start, nowy);
    return start;
}
//wstawienie x nowych elementow
Lista* WstawX(Lista* start,int x) {
    Lista* nowy = (Lista*)malloc(sizeof(Lista));
    nowy->a= (rand() % 24975)+ (rand() % 24975)+ (rand() % 24971) + 99;

    for (int i = 0; i < x; i++) {
        Lista* nowy = (Lista*)malloc(sizeof(Lista));
        nowy->a = (rand() % 24975) + (rand() % 24975) + (rand() % 24971) + 99;
        start = WstawElement(start, nowy);
    }
    return start;
}
//zwraca pozycje klucza, zwraca -1, gdy nie ma klucza
int SzukajKlucz(Lista* start, int klucz) {
    if (start->a == NULL)return -1;
    for (int i = 0;; i++) {
        if (start->a == klucz) {
            return i;
        }
        if (klucz<start->a || start->a>start->next->a)
            return -1;

            start = start->next;

    }
}
//wypisuje, pozycje klucza na liscie
void WypiszPozycje(Lista* start, int klucz) {
    int a = SzukajKlucz(start, klucz);
    if (a == -1) {
        std::cout<< "Element z kluczem " << klucz << " nie znajduje sie w liscie"<< std::endl;
    }
    else {
        std::cout << "Element z kluczem " << klucz << " znajduje sie na pozycji " << a << std::endl;
    }

}
// usuwa element o danym kluczu
Lista* UsunElement(Lista* start, int klucz) {
    int pozycja = SzukajKlucz(start, klucz);
    if (pozycja == -1)return start;
    Lista* obecny = start;
    for (int i = 0; i < pozycja; i++)obecny=obecny->next;
    obecny->next->prev = obecny->prev;
    obecny->prev->next = obecny->next;
    if (klucz == 0) {
        start = start->next;

    }
    free(obecny);
    return start;


}
//wypisuje kluczowe z listy od początku
void WypiszPierwsze(Lista* start,int x) {
    std::cout << "Wypisanie pierwszych: " << std::endl;
    if (start->a == NULL) {
        std::cout << "Lista jest pusta" << std::endl;
        return;
    }
    for (int i = 0; i < x; i++) {
        std::cout << "Kluczowa z elementu " << i << " = " << start->a << std::endl;
        if (start->a > start->next->a) {
            std::cout << "Wszystkie zmienne zostały wypisane " << std::endl;
                return;
        }
        start = start->next;
    }
    return;
}
//wypisuje kluczowe z listy od konca
void WypiszOstatnie(Lista* start, int x) {
    std::cout << "Wypisanie ostatnich: " << std::endl;
    if (start->a == NULL) {
        std::cout << "Lista jest pusta" << std::endl;
        return;
    }
    start = start->prev;
    for (int i = 0; i < x; i++) {
        std::cout << "Kluczowa z elementu " << i << "od konca = " << start->a << std::endl;
        if (start->a < start->prev->a) {
            std::cout << "Wszystkie zmienne zostały wypisane " << std::endl;
            return;
        }
        start = start->prev;
    }
    return;
}
//wypisuje liczbe elementow w liscie
void LiczbaElementow(Lista* start) {
    int liczbaEl = 1;
    if (start->a == NULL) {
        std::cout << "W liscie nie ma elementow" << std::endl;
        return;
    }
    for (;;) {
        if (start->a > start->next->a) {
            std::cout << "Liczba elementow wynosi :" << liczbaEl << std::endl;
            return;
        }
        liczbaEl++;
        start = start->next;
    }
}
//Usuwa wszystkie elementy
void FreeLista(Lista* start) {
    start->a = NULL;
    start = start->next;
    for (;;) {
        start = start->next;
        free(start->prev);
        if (start->next->a == NULL) {
            free(start);
            return;
        }

    }

}


int main()
{
//  srand(time(NULL));
    clock_t begin, end;  double time_spent;  begin = clock();

    int* plik = (int*)malloc(sizeof(int) * 6);
    FILE *fp;
    fopen_s(&fp, "inlab02.txt", "r");
    if (fp == NULL)
        return -1;
    fscanf_s(fp, "%d %d %d %d %d %d", &plik[0], &plik[1], &plik[2], &plik[3], &plik[4], &plik[5]);
    fclose(fp);

    Lista* start = (Lista*)malloc(sizeof(Lista));//element
    start->a = NULL;

    WypiszPozycje(start, plik[1]);
    start = WstawX(start, plik[0]);
    WypiszPierwsze(start, 20);
    start = ElementZad1(start, plik[2]);
    WypiszPierwsze(start, 20);
    start = ElementZad1(start, plik[3]);
    WypiszPierwsze(start, 20);
    start = ElementZad1(start, plik[4]);
    WypiszPierwsze(start, 20);
    start = ElementZad1(start, plik[5]);
    start = UsunElement(start, plik[3]);
    WypiszPierwsze(start, 20);
    start = UsunElement(start, plik[2]);
    WypiszPierwsze(start, 20);
    start = UsunElement(start, plik[5]);
    LiczbaElementow(start);
    WypiszPozycje(start, plik[5]);
    WypiszOstatnie(start, 11);
    FreeLista(start);
    WypiszOstatnie(start, 11);
    LiczbaElementow(start);

    free(start);

    end = clock();  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    std::cout << "Czas: " << time_spent << " sekund" << std::endl;
    system("pause");
    _CrtDumpMemoryLeaks();
    return 0;
}