using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GDD2200_DoublyLinkedList
{
    /// <summary>
    /// DoublyLinkedList
    /// </summary>
    public class DoublyLinkedList<U>
    {
        /// <summary>
        /// DoublyLinkedListNode
        /// Private class that is only known to the DoublyLinkedList class
        /// and cannot be accessed by any "outside" code
        /// </summary>

        private DoublyLinkedListNode<U> head;
        private DoublyLinkedListNode<U> tail;
        private int count;

        private class DoublyLinkedListNode<T>
        {

            #region Properties_DLLN
            /// <summary>
            /// Reference to the next node in the list
            /// </summary>

            public DoublyLinkedListNode Next { get; set; }

            /// <summary>
            /// Reference to the previous node in the list
            /// </summary>
            public DoublyLinkedListNode Prev { get; set; }

            /// <summary>
            /// Item stored in the node
            /// </summary>
            public int Item { get; set; }
            #endregion

            /// <summary>
            /// Node constructor
            /// </summary>
            /// <param name="item">item to store in the node</param>
            /// <param name="next">next node in the list</param>
            /// <param name="prev">previous node in the list</param>
            public DoublyLinkedListNode(T item, DoublyLinkedListNode<T> next = null, DoublyLinkedListNode<T> prev = null)
            {
                Item = item;
                Next = next;
                Prev = prev;
            }
        }

        #region Properties_DDL
        /// <summary>
        /// Reference to the "front" of the list
        /// </summary>
        private DoublyLinkedListNode Head { get; set; }

        /// <summary>
        /// Reference to the "end" of the list
        /// </summary>
        private DoublyLinkedListNode Tail { get; set; }

        /// <summary>
        /// Number of items in the list
        /// </summary>
        public int Count { get; private set; }
        #endregion

        /// <summary>
        /// Add the item to the front of the list
        /// </summary>
        /// <param name="item">item to add</param>
        public void AddFront(int item)
        {
            //Adding to Empty List in Front
            if (this.head == null)
            {
                this.head = new DoublyLinkedListNode<U>(item);
                this.tail = this.head;
            }
            //Adding Item to Current List Front
            else
            {
                head.Prev = new DoublyLinkedListNode<U>(item);
                head.Prev.Next = head;
                head = head.Prev;
            }
            count++;

            //Throws an exception if the list is at 0
            if (item <= 0)
                throw new ArgumentOutOfRangeException("Item(s) are at negative: " + item);
        }

        /// <summary>
        /// Add the item to the back of the list
        /// </summary>
        /// <param name="item">item to add</param>
        public void AddBack(int item)
        {
            tail.Next = new DoublyLinkedListNode(item);
            tail.Next.Prev = tail;
            tail = tail.Next;

            //Throws an exception if the list is at 0
            if (item <= 0)
                throw new ArgumentOutOfRangeException("Item(s) are at Zero or Negative: " + item);
        }

        /// <summary>
        /// Remove the item from the front of the list
        /// </summary>
        /// <returns>item removed</returns>
        public int RemoveFront()
        {
                //Remove First Node
                DoublyLinkedListNode<U> frontCurrent = head.Next;
                if (frontCurrent != null)
                {
                    frontCurrent.Prev = null;
                }
                head = head.Next;
                count--;

            // Throws an exception if the list is empty
            if (count <= 0)
                throw new ArgumentOutOfRangeException("Item(s) are at Zero or Negative:");
            return 0;
        }

        /// <summary>
        /// Remove item from the back of the list
        /// </summary>
        /// <returns>item removed</returns>
        public int RemoveBack()
        {
                //Remove Last Node
                DoublyLinkedListNode<U> backCurrent = tail.Prev;
                if (backCurrent != null)
                {
                    backCurrent.Next = null;
                }
                tail = tail.Prev;
                count--;

            // Throws an exception if the list is empty
            if (count <= 0)
                throw new ArgumentOutOfRangeException("Item(s) are at Zero or Negative:");

            return 0;
        }

        /// <summary>
        /// Remove the item provided from the list
        /// </summary>
        /// <param name="item">item to remove</param>
        /// <returns>true if found and removed, false otherwise</returns>
        public bool RemoveItem(int item)
        {
            //If First Node Removed
            if (head.Item == item)
            {
                // Check Remove Single Node
                if (head == tail)
                {
                    tail = null;
                }

                // Remove First and Decrement
                DoublyLinkedListNode<U> next = head.Next;
                if (next != null)
                {
                    next.Prev = null;
                }
                head = head.Next;
                count--;

                return true;
            }

            else
            {
                DoublyLinkedListNode<U> current = head;
                while (current != null)
                {
                    if (current.Item == item)
                    {
                        //Remove Current
                        DoublyLinkedListNode<U> next = current.Next;

                        if (next != null)
                        {
                            next.Prev = current.Prev;
                        }

                        current.Prev.Next = next;
                        count--;

                        //If Remove Last Node
                        if (current == tail)
                        {
                            tail = current.Prev;
                        }

                        //Null References
                        current.Prev = null;
                        current.Next = null;

                        return true;
                    }
                    // Run Along Remainder of List
                    current = current.Next;
                }
            }
            return false;
        }

        /// <summary>
        /// Search for the item in the list
        /// </summary>
        /// <param name="item">true if found, false if otherwise</param>
        /// <returns></returns>
        public bool Search(int item)
        {
            //IndexOf Search
            DoublyLinkedListNode<U> search = this.head;
            for (int i = 0; i < this.count; i++)
            {
                if (search.Item.Equals(item))
                {
                    return true;
                }
                search = search.Next;
            }
            return false;
        }

        /// <summary>
        /// Convert the list to a string
        /// </summary>
        /// <returns>The list as a string</returns>
        /// DO NOT EDIT THIS METHOD OR ALL OF YOUR TESTS WILL FAIL
        public override string ToString()
        {
            DoublyLinkedListNode<U> curr = Head;
            StringBuilder output = new StringBuilder("HEAD->");
            while (curr != null)
            {
                output.Append(curr.Item);
                output.Append("->");
                curr = curr.Next;
            }
            output.Append("NULL\n");

            output.Append("TAIL->");
            curr = Tail;
            while (curr != null)
            {
                output.Append(curr.Item);
                output.Append("->");
                curr = curr.Prev;
            }
            output.Append("NULL");

            return output.ToString();
        }
    }
}