using System;
using System.Collections.Generic;

namespace WaveLinkApp
{
    public class WaveLink
    {
        // Método Oleas
        public static void waveSort(LinkedList<int> lista)
        {
            for (int i = 1; i < lista.Count; i++)
            {
                // En índices pares: lista[i] >= lista[i-1]
                if (i % 2 == 0 && GetAt(lista, i) < GetAt(lista, i - 1))
                {
                    Swap(lista, i, i - 1);
                }
                // En índices impares: lista[i] <= lista[i-1]
                if (i % 2 != 0 && GetAt(lista, i) > GetAt(lista, i - 1))
                {
                    Swap(lista, i, i - 1);
                }
            }
        }

        // Método auxiliar para obtener elemento en índice
        private static int GetAt(LinkedList<int> lista, int index)
        {
            int i = 0;
            foreach (int val in lista)
            {
                if (i == index) return val;
                i++;
            }
            return -1; // nunca debería ocurrir
        }

        // Método auxiliar para intercambiar elementos
        private static void Swap(LinkedList<int> lista, int i, int j)
        {
            int valI = GetAt(lista, i);
            int valJ = GetAt(lista, j);

            // Reemplazar valores en las posiciones
            int k = 0;
            LinkedListNode<int> nodo = lista.First;
            while (nodo != null)
            {
                if (k == i) nodo.Value = valJ;
                if (k == j) nodo.Value = valI;
                nodo = nodo.Next;
                k++;
            }
        }

        // Imprimir lista
        public static void imprimirLista(LinkedList<int> lista)
        {
            foreach (int num in lista)
            {
                Console.Write(num + " ---> ");
            }
            Console.WriteLine("Final");
        }

        // Método para ingreso por teclado
        public void ingresoPorTeclado()
        {
            LinkedList<int> lista = new LinkedList<int>();

            Console.Write("Cuantos elementos quiere ingresar? : ");
            int cantidad = int.Parse(Console.ReadLine());

            for (int i = 0; i < cantidad; i++)
            {
                Console.Write("Ingrese elemento " + (i + 1) + " :  ");
                int elemento = int.Parse(Console.ReadLine());
                lista.AddLast(elemento);
            }

            Console.WriteLine("\nLista Ingresada:");
            imprimirLista(lista);

            waveSort(lista);

            Console.WriteLine("\nLista en forma de ONDITAS (Wave Sort):");
            imprimirLista(lista);
        }

        // Mains
        public static void Main(string[] args)
        {
            WaveLink obj = new WaveLink();
            obj.ingresoPorTeclado();
        }
    }
}