using System;
using System.Collections.Generic;
using System.Diagnostics;

//Przetestuj i porównaj czas wykonania metod dla różnych implementacji listy(skorzystaj ze Stopwatch).
//Przetestuj Dodaj, Podaj, CzyZawiera, Usuń, (jeśli jest dopisane - zadania 1, 2 - Dodaj na i tej pozycji,
//Dodaj na początku lub na końcu), PodajRozmiar.
//Jako plik testowy można wykorzystać pliki z laboratorium 5 (100000 elementów).
//    Sformułuj wnioski.

// rekurencyjne struktury danych - lista jednokierunkowa
// wersja obiektowa
public class Węzeł
{
    public int dane;// w węźle przechowujemy liczbę
    public Węzeł następny; // oraz referencję do następnego
}

class ListaDowiazaniowa
{
    Węzeł głowa = null;

    public bool CzyPusta()
    {
        return głowa == null;
    }

    // obliczamy rozmiar przechodząc przez wszystkie elementy listy
    // aż dojedziemy do nulla
    public int PodajRozmiar()
    {
        int licznik = 0;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny)
            licznik++;
        return licznik;
    }

    public void Dodaj(int liczba) //Do głowy
    {
        Węzeł tmp = new Węzeł(); // nowy węzeł
        tmp.dane = liczba;
        tmp.następny = głowa;  //dotychczasowa głowa staje się "następny"
        głowa = tmp;// dodany element staje się głową
    }

    public void Usuń() //Z głowy
    {
        if (głowa != null) // sprawdzamy, czy lista nie jest pusta
            głowa = głowa.następny;
    }

    public int Podaj(int i) //i-ty element
    {
        int licznik = 0;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny)
            if (licznik++ == i) return tmp.dane;
        throw new Exception("indeks poza zakresem!");
    }

    public int CzyZawiera(int n) //element o wartości n
    {
        int licznik = 0;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny, licznik++)
        {
            if (tmp.dane == n) return licznik;
        }
        return -1;
    }

    // DOPISANA METODA
    public void Wstaw(int i, int n)
    {
        if (i==0)
        {
            Dodaj(n);
            return;
        }
        int licznik = 0;
        Węzeł w = new Węzeł();
        w.dane = n;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny)
            if (licznik++ == i - 1)
            {
                w.następny = tmp.następny;
                tmp.następny = w;
                break;
            }
    }

    ////////////////////////////////////////////////////////////////////////

    // wyświetlanie
    public void Wyświetl()
    {
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny)
            Console.WriteLine(tmp.dane);
        Console.WriteLine();
    }
}

// STAŁA POJEMNOŚC
class ListaTablicowa
{
    int[] dane = new int[pojemność];
    int rozmiar = 0;
    const int pojemność = 500000; // stała

    public bool CzyPusta()
    {
        return rozmiar == 0;
    }

    public int PodajRozmiar()
    {
        return rozmiar;
    }

    public void Dodaj(int liczba) //na koniec
    {
        if (rozmiar == pojemność) throw new Exception("brak miejsca!");
        dane[rozmiar] = liczba;
        rozmiar++;
    }

    public void Usuń() //z końca
    {
        if (rozmiar > 0) rozmiar--;
    }

    public int Podaj(int i) //i-ty element
    {
        if (i >= 0 && i < rozmiar) return dane[i];
        throw new Exception("indeks poza zakresem!");
    }

    public int CzyZawiera(int n) //element o wartości n
    {
        for (int i = 0; i < rozmiar; i++)
        {
            if (dane[i] == n) return i;
        }
        return -1;
    }

    // NOWA METODA
    public void Wstaw(int i, int n)
    {
        for (int j = rozmiar; j > i; j--)
        {
            dane[j] = dane[j - 1];
        }
        dane[i] = n;
        rozmiar++;
    }

    //łączy dwie listy "dokleja" do pierwszej drugą
    public void Dołącz(ListaTablicowa LB)
    {
        if (rozmiar + LB.rozmiar > pojemność) throw new Exception("brak miejsca!");
        for (int i = 0; i < LB.rozmiar; i++)
            dane[i + rozmiar] = LB.dane[i];
        rozmiar += LB.rozmiar;
    }


    ////////////////////////////////////////////////////////////////////////

    // wyświetlanie
    public void Wyświetl()
    {
        for (int i = 0; i < rozmiar; i++)
            Console.WriteLine(dane[i]);
        Console.WriteLine();
    }
}
// Dynamicznie zmieniamy pojemność
class ListaTablicowa2
{
    int[] dane;
    int rozmiar = 0;
    //const int pojemność = 1000; // stała
    int pojemność = 1000; // startowa

    public ListaTablicowa2()
    {
        dane = new int[pojemność];
    }
    public bool CzyPusta()
    {
        return rozmiar == 0;
    }

    public int PodajRozmiar()
    {
        return rozmiar;
    }

    public void Dodaj(int liczba) //na koniec
    {
        //if (rozmiar == pojemność) throw new Exception("brak miejsca!");
        if (rozmiar == pojemność)
        {
            pojemność = 2 * pojemność;
            int[] tmp = new int[pojemność];
            for (int i = 0; i < rozmiar; i++)
                tmp[i] = dane[i];
            dane = tmp;
        }

        dane[rozmiar] = liczba;
        rozmiar++;
    }

    public void Usuń() //z końca
    {
        if (rozmiar > 0) rozmiar--;
    }

    public int Podaj(int i) //i-ty element
    {
        if (i >= 0 && i < rozmiar) return dane[i];
        throw new Exception("indeks poza zakresem!");
    }

    public int CzyZawiera(int n) //element o wartości n
    {
        for (int i = 0; i < rozmiar; i++)
        {
            if (dane[i] == n) return i;
        }
        return -1;
    }

    // NOWA METODA
    public void Wstaw(int i, int n)
    {
        if (rozmiar == pojemność)
        {
            pojemność = 2 * pojemność;
            int[] tmp = new int[pojemność];
            for (int j = 0; j < rozmiar; j++)
                tmp[j] = dane[j];
            dane = tmp;
        }
        for (int j = rozmiar; j > i; j--)
        {
            dane[j] = dane[j - 1];
        }
        dane[i] = n;
        rozmiar++;
    }

    //łączy dwie listy "dokleja" do pierwszej drugą
    public void Dołącz(ListaTablicowa2 LB)
    {
        if (rozmiar + LB.rozmiar > pojemność) throw new Exception("brak miejsca!");
        for (int i = 0; i < LB.rozmiar; i++)
            dane[i + rozmiar] = LB.dane[i];
        rozmiar += LB.rozmiar;
    }


    ////////////////////////////////////////////////////////////////////////

    // wyświetlanie
    public void Wyświetl()
    {
        for (int i = 0; i < rozmiar; i++)
            Console.WriteLine(dane[i]);
        Console.WriteLine();
    }
}

class Program
{
    static void Main(string[] args)
    {
        ListaDowiazaniowa ld0 = new ListaDowiazaniowa();
        ListaTablicowa lt0 = new ListaTablicowa();
        ListaTablicowa2 ltt0 = new ListaTablicowa2();

        for (int i = 0; i < 5; i++) ld0.Dodaj(i);
        for (int i = 0; i < 5; i++) lt0.Dodaj(i);
        for (int i = 0; i < 5; i++) ltt0.Dodaj(i);
        ld0.Wstaw(4, 99);
        lt0.Wstaw(4, 99);
        ltt0.Wstaw(4, 99);
        ld0.Wyświetl();
        lt0.Wyświetl();
        ltt0.Wyświetl();

        Console.WriteLine("TERAZ TESTY");
        Stopwatch sw = new Stopwatch();

        for (int m = 100000; m <= 400000; m += 100000)
        {
            Console.WriteLine(m + " elementów");

            ListaDowiazaniowa ld = new ListaDowiazaniowa();
            ListaTablicowa lt = new ListaTablicowa();
            ListaTablicowa2 ltt = new ListaTablicowa2();

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i++) ld.Dodaj(i);
            sw.Stop();
            Console.WriteLine("dowiazaniowa Dodaj {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i++) lt.Dodaj(i);
            sw.Stop();
            Console.WriteLine("tablicowa Dodaj {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i++) ltt.Dodaj(i);
            sw.Stop();
            Console.WriteLine("tablicowa2 Dodaj {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 100) ld.Podaj(i);
            sw.Stop();
            Console.WriteLine("dowiazaniowa Podaj {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 100) lt.Podaj(i);
            sw.Stop();
            Console.WriteLine("tablicowa Podaj {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 100) ltt.Podaj(i);
            sw.Stop();
            Console.WriteLine("tablicowa2 Podaj {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 10000) ld.CzyZawiera(i);
            sw.Stop();
            Console.WriteLine("dowiazaniowa CzyZawiera {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 10000) lt.CzyZawiera(i);
            sw.Stop();
            Console.WriteLine("tablicowa CzyZawiera {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 10000) ltt.CzyZawiera(i);
            sw.Stop();
            Console.WriteLine("tablicowa2 CzyZawiera {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 1000) ld.Wstaw(i, -10);
            sw.Stop();
            Console.WriteLine("dowiazaniowa Wstaw {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 1000) lt.Wstaw(i, -10);
            sw.Stop();
            Console.WriteLine("tablicowa Wstaw {0}", sw.ElapsedTicks);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < m; i += 1000) ltt.Wstaw(i, -10);
            sw.Stop();
            Console.WriteLine("tablicowa2 Wstaw {0}", sw.ElapsedTicks);
            Console.WriteLine(" ------------------------------ ");
        }

        Console.WriteLine(" KONIEC ");
        Console.ReadKey();
    }
}