//Auteurs: Maxime Gagnon et Mathieu Auger
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Liste_CSharp
{
    class Noeud<T>
    {

        public T value { get; set; }
        public Noeud<T> succ { get; set; }


        public Noeud(T val)
        {
            value = val;
            succ = null;
        }

        public Noeud(Noeud<T> head)
        {
            value = head.value;
            while (head.succ != null)
            {
                head = head.succ;
                succ = head.succ;
            }
        }
    }

    class Liste<T>
    {
        private Noeud<T> head { get; set; }
        public Noeud<T> tail { get; set; }

        public int size { get; private set; }
        public Liste()
        {
            head = null;
            tail = null;
            size = 0;
        }

        ~Liste()
        {
            while (!isEmpty())
            {
                Extract();
            }
        }



        public bool isEmpty()
        {
            return head == null;
        }

        public void Add(T val)
        {

            if (isEmpty())
            {
                head = new Noeud<T>(val);
                tail = head;
            }
            else
            {
                Noeud<T> item = head;
                while(item.succ!=null)
                {
                    item = item.succ;
                }
                item.succ = new Noeud<T>(val);
                tail = item.succ;
            }

            ++size;
        }

        public Liste<T> Clone()
        {
            Liste<T> liste = new Liste<T>();
            Noeud<T> temp = head;

            while (temp != null)
            {
                liste.Add(temp.value);
                temp = temp.succ;
            }

            return liste;
        }

        public T Extract()
        {
            if(isEmpty())
            {
                throw new IndexOutOfRangeException();
            }
            Noeud<T> item = head;
            head = head.succ;
            T val = item.value;
            --size;

            return val;
        }

        public void Show(TextWriter stream)
        {
            Liste<T>copy = this.Clone();
            if(copy.size>0)
            {
                while (copy.head.succ != null)
                {
                    stream.WriteLine(copy.head.value);
                    copy.head = copy.head.succ;
                }
                stream.WriteLine(copy.head.value);
            }
        }

        public void Empty()
        {
            int nbBoucle = size;
            for(int i=0;i<nbBoucle;i++)
            {
                Extract();
            }
        }

        public bool SameAs(Liste<T> other)
        {
            Liste<T> main = this.Clone();
            Liste<T> otherListe = other.Clone();
            bool result = true;
            if(other.size==size)
            {
                while (otherListe.head.succ != null)
                {
                    if(!EqualityComparer<T>.Default.Equals(main.head.value, otherListe.head.value))
                    {
                        result = false;
                    }
                    otherListe.head = otherListe.head.succ;
                    main.head = main.head.succ;
                }
            }
            else
            {
                result = false;
            }
            return result;
        }
        public void Reverse()
        {
            Noeud<T> newHead = null;
            Noeud<T> newTail = null;

            while (head!=null)
            {
                Noeud<T> item = new Noeud<T>(head);
                if (newTail==null)
                {
                    newTail = item;
                }
                item.succ = newHead;
                newHead = item;
                item = head;
                head = head.succ;
            }
            tail = newTail;
            head = newHead;
        }
    }



    class Program
    {
        static void Main(string[] args)
        {
            int NB_ENTIERS = 25;
            Console.WriteLine("Creation Liste1");
            Liste<int> lst = new Liste<int>();

            //Ajouter des éléments à la liste
            for (int i = 0; i < NB_ENTIERS; i++)
                lst.Add(i + 1);

            //Dupliquer une liste
            Console.WriteLine("Dupliquer Liste1 sur Liste2");
            Liste<int> lstInv = lst.Clone();

            //Identiques?
            Console.WriteLine("Liste1 et Liste 2 sont identique: ");
            Console.WriteLine(lst.SameAs(lstInv));

            //Inverser les éléments d'une liste
            Console.WriteLine("Inverse Liste 2");
            lstInv.Reverse();

            //Connaître le nombre d'éléments dans la liste
            Console.WriteLine("Nb Elements Liste 2: ");
            int NB_ELEMENTS = lstInv.size;
            Console.WriteLine(NB_ELEMENTS);

            //Identiques?
            Console.WriteLine("Liste1 et Liste 2 sont identique: ");
            Console.WriteLine(lst.SameAs(lstInv));

            Console.WriteLine("Liste 1: ");
            lst.Show(Console.Out);

            Console.WriteLine("Liste 2: ");
            lstInv.Show(Console.Out);

            Console.WriteLine("Vider Liste2");
            lstInv.Empty();

            Console.WriteLine("Extraction des elements 1 par 1 de Liste1: ");

            for (int i = 0; i < NB_ELEMENTS; i++)
                Console.WriteLine("Extraction de "+lst.Extract() + " ");

            Console.WriteLine("Liste 1: ");
            lst.Show(Console.Out);

            Console.WriteLine("Liste 2: ");
            lstInv.Show(Console.Out);
        }
    }
}