using Linked_List3102;

/*
 * Singly Linked List for CSC3102 Portfolio
 * Ltype
*/

/*
 * --REQUIRED METHODS--
 * LinkedList() (default constructor)
 * AddAt(Ltype item, int pos)
 * Ltype RemoveAt(int pos)
 * int Size()
 * 
 * --OPTIONAL METHODS--
 * AddHead(Ltype item)
 * Ltype RemoveHead()
 * AddTail(Ltype item)
 * Ltype RemoveTail()
 * override ToString() or printList()
 * 
 * --NEWLY REQUIRED METHODS--
 * Ltype Get(int pos)
 * Ltype Set(Ltype val, int pos) ***I don't have this one yet***
*/

namespace Linked_List3102
{
    public class Node<T>
    {
        public T? data;
        public Node()
        {
            data = default;
        }

        public Node(T value)
        {
            data = value;
        }
    }

    public class LinkedList<Ltype>
    {
        internal class ListNode<T> : Node<T>
        {
            public ListNode<T>? next;

            public ListNode(T value, ListNode<T>? next = null) : base(value)
            {
                this.data = value;
                this.next = next;
            }
        }

        private ListNode<Ltype>? head, tail;
        public int size;

        //default constuctor
        public LinkedList()
        {
            head = null;
            tail = null;
            size = 0;
        }

        /*
         * Inserts item at given position, if an element already exists there, it becomes the next element
         * @item - element we want stored
         * @pos - position we want the item stored at
        */
        public void AddAt(Ltype item, int pos) 
        {
            if(pos > size)
            {
                throw new IndexOutOfRangeException("Position you are trying to insert at is greater than the size");
            }
            if (pos == 0)
            {
                AddHead(item);
                return;
            }
            if (pos == size)
            {
                AddTail(item);
                return;
            }
            var prevNode = head;
            for (int i = 0; i < pos - 1; i++)
            {
                if (prevNode.next != null)
                {
                    prevNode = prevNode.next;
                }
            }
            var node = prevNode.next;
            var newNode = new ListNode<Ltype>(item, next: node);
            prevNode.next = newNode;
            size++;
        }


        /*
         * Removes element at specified position of the linked list, and returns that element
         * @pos - position of element being removed
        */

        public Ltype RemoveAt(int pos)
        {
            if (pos >= size)
            {
                throw new IndexOutOfRangeException("The position is greater than the size");
            }
            if (head == null)
            {
                throw new ArgumentException("The list is empty");
            }
            if (pos == 0)
            {
                return RemoveHead();
            }

            var prevNode = head;
            for (int i = 0; i < pos - 1; i++)
            {
                if (prevNode.next != null)
                {
                    prevNode = prevNode.next;
                } 
            }
            var node = prevNode.next;

            if(node.next != null)
            {
                prevNode.next = node.next;
            }
            else
            {
                tail = prevNode;
                prevNode.next = null;
            }
            size--;
            return node.data;                       
        }


        /*
         * Returns the size of the linked list
        */
        public int Size()
        {
            return size;
        }

       

        /*
         * Returns the item at the specified position
         * @pos - index of the value you are trying to retrieve
        */
        public Ltype Get(int pos)
        {
            if (size == 0)
            {
                throw new IndexOutOfRangeException("The list is empty");
            }
            else if(pos >= size || pos < 0)
            {
                throw new IndexOutOfRangeException("That position does not exist in the list");
            }
            else if (pos == 0)
            {
                return this.head.data;
            }
            else if (pos == size - 1)
            {
                return this.tail.data;
            }
            else
            {
                var travNode = this.head;
                for (int i = 0; i < pos; i++)
                {
                    travNode = travNode.next;
                }
                return travNode.data;
            }

        }

        /*
         * Sets the value of an item at specified position to a new value, and returns the old value.
         * Fails if index doesn't exist, or if index is negative
         */
        public Ltype Set(Ltype val, int pos)
        {
            if (size == 0)
            {
                throw new Exception("List is empty");
            }
            if(pos < 0)
            {
                throw new Exception("Position can't be negative");
            }
            if (pos >= size)
            {
                throw new Exception("Position is out of range");
            }
            else
            {
                var temp = this.head;
                for (int i = 0; i <= pos; i++)
                {
                    temp = temp.next;
                }
                Ltype ret = temp.data;
                temp.data = val;
                return ret;
            }
        }


        /*
        * Adds an item to the beginning of list, making it the new head
        * @item - the value you are adding
       */
        public void AddHead(Ltype item)
        {
            var newHead = new ListNode<Ltype>(item, next: head);
            size++;
            head = newHead; 
            if (tail == null) //only matters if list was empty, since now there is only 1 node it is both the head and tail
            {
                tail = newHead;
            }
        }

        /*
         * Adds an item to the end of the list, making it the new tail
         * @item - value you are adding 
        */
        public void AddTail(Ltype item)
        {
            var newTail = new ListNode<Ltype>(item);
            size++;
            if (tail != null)
            {
                tail.next = newTail;
                tail = newTail;
            }
            else
            {
                tail = newTail;
                head = newTail;
                newTail.next = null;
            }

        }

        /*
         * Removes the current head, head will then equal the next node, 
         * returns value of former head
        */
        public Ltype RemoveHead()
        {
            if (head == null)
            {
                throw new ArgumentException("List is empty");
            }
            if (head == tail) //checks if there is one item in the list
            {
                tail = null;
            }
            var node = head;
            head = node.next;
            size--;
            return node.data;
        }

        public void printList()
        {
            var node = this.head;
            Console.Write("[ ");
            for (int i = 0; i < size; i++)
            {
                if (node.data != null)
                {
                    Console.Write(node.data + " ");
                }
                node = node.next;
            }
            Console.WriteLine("]");
        }
    } 
}