using System;
using System.Collections.Generic;
using System.Text;

namespace Chorice_List
{
    /// <summary>
    /// Iterating을 하면서 수정/삭제가 가능한 List가 필요해 만들어진 List입니다.
    /// Doubly Linked List로 구현되어 있으며
    /// foreach를 통한 Iteration 또한 가능합니다. 
    /// (단 foreach 중에는 Collction을 수정할 수 없습니다.)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class ChoriceList<T> : IList<T>
    {
      /* Nested Classes */
        /* List 내부에서 쓰이는 노드입니다. */
        class Node
        {
            public T Data;
            public Node Prev, Next;

            public Node()
            {
                Data = null;
                Prev = Next = null;
            }
            public Node(T Data)
            {
                Node();
                this.Data = Data;
            }
            public Node(Node Prev, T Data)
            {
                Node(Data);
                this.Prev = Prev;
                Prev.Next = this;
            }
            public Node(Node Prev, Node Next, T Data)
            {
                Node(Prev, Data);
                this.Next = Next;
                Next.Prev = this;
            }
            public T Remove()
            {
                if (this.Prev != null) this.Prev.Next = this.Next;
                if (this.Next != null) this.Next.Prev = this.Prev;
                return this.Data;
            }
        }

        /* Foreach를 위한 Enumerator입니다. */
        class Enumerator<T2> : IEnumerator<T2>
        {
            private Node current;       /* 현재 Enumerator가 가리키는 노드 */
            private Node dummy;         /* 가장 처음 노드의 앞 노드입니다. */

            public T2 Current
            {
                get
                {
                    if (current == null || current == dummy)
                    {
                        throw new InvalidOperationException();
                    }
                    return current.Data;
                }
            }

            /* MoveNext()와 Reset()은 List가 수정되면 Exception을 내야 한다. 
             * 하지만 어떻게 수정을 감지하는지 모른다.
             */

            /* 한칸 전진시킨다. current가 적당한 값이 아니면 false 리턴 */
            public bool MoveNext()
            {
                if (current!= null)
                    current = current.Next;
                if (current == null || current == dummy)
                    return false;
                return true;
            }
            /* 현재 Enumerator가 가리키는 것을 가장 처음으로 되돌린다. */
            public void Reset()
            {
                current = dummy;
            }
            /* 현재 Enumerator를 메모리 공간에서 삭제한다. */
            public void Dispose()
            {
                //뭘 넣어야 되는거지? -_-
            }

            /* 생성자들 */
            public Enumerator()
            {
                current = dummy = null;
            }
            public Enumerator(Node BeforeFirst)
            {
                Enumerator();
                dummy = BeforeFirst;
                current = dummy;
            }
            public Enumerator(Node BeforeFirst, Node Current)
            {
                Enumerator(BeforeFirst);
                current = Current;
            }
        }
        

      /* Properties */
        private Node dummy;         //List를 만들면 자동으로 만들어지는 더미노드
        private Node current;       //Enumerator를 통하지 않고 Iterating을 지원하기 위함.
        private int count;
        private bool isReadOnly;
        public int Count { get { return count; } }    
        public bool IsReadOnly { get { return isReadOnly; } }

      /* Methods */

        /// <summary>
        /// ChoriceList를 반복하는 열거자를 반환합니다.
        /// </summary>
        /// <returns></returns>
        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator<T>(dummy);
        }

        /* For Implementing IList */
        /* []을 이용한 Indexing. o(n) time complexity. n = index or the size of this list. */
        public T this[int index]
        {
            get
            {
                Node n = dummy;
                int i = 0;
                while (i <= index && (n = n.Next) != null)
                    i++;
                if (n != dummy && n != null)
                    return n;
                throw new ArgumentOutOfRangeException();
            }
            set
            {
                Node n = dummy;
                int i = 0;
                if (0 <= index && index < count)
                {
                    for (i; i <= index; i++)
                        n = n.Next;
                    n.Data = value;
                }
                else if (index == count)
                {
                    while (n.Next != null)
                        n = n.Next;
                    Node(n, value);
                    count++;
                }
                else
                {
                    throw new ArgumentOutOfRangeException();
                }
            }
        }

        /// <summary>
        /// 이 ChoriceList에서 해당 Item의 Index를 반환합니다. 
        /// 만약 해당 Item이 여러개 있다면 가장 앞에 있는 것의 Index를 반환합니다.
        /// 해당 Item이 List에 존재 하지 않으면 -1을 반환합니다.
        /// </summary>
        public int IndexOf(T Item) 
        {
            Node n = dummy;
            int i = 0;
            while ((n = n.Next) != null)
            {
                if (n.Data.Equals(Item))
                    return i;
                i++;
            }
            return -1;
        }
        /// <summary>
        /// 해당 Index에 Item을 추가합니다. Linear Search이며 
        /// Time Complexity는 o(n) 입니다.
        /// </summary>
        /// <param name="Index"></param>
        /// <param name="Item"></param>
        public void Insert(int Index, T Item)
        {
            if (isReadOnly) throw new NotSupportedException();

            Node n = dummy;
            int i = 0;
            if (0 <= index && index < count)
            {
                for (i; i < index; i++)
                    n = n.Next;
                Node(n, n.Next, Item);
                count++;
            }
            else if (index == count)
            {
                while (n.Next != null)
                    n = n.Next;
                Node(n, value);
                count++;
            }
            else
            {
                throw new ArgumentOutOfRangeException();
            }
        }
        /// <summary>
        /// 해당 Index의 Item을 삭제합니다.
        /// Time Complexity는 o(n) 입니다.
        /// </summary>
        /// <param name="Index"></param>
        public void RemoveAt(int Index)
        {
            if (isReadOnly) throw new NotSupportedException();

            Node n = dummy;
            int i = 0;
            if (0 <= index && index < count)
            {
                for (i; i <= index; i++)
                    n = n.Next;
                n.Remove();
                count--;
            }
            else
            {
                throw new ArgumentOutOfRangeException();
            }
        }

        /* For Implementing ICollection */
        /// <summary>
        /// 해당 Item을 이 ChoriceList에 더합니다. List의 가장 마지막 부분에 더하게 됩니다.
        /// </summary>
        public void Add(T Item)
        {
            if (isReadOnly) throw new NotSupportedException();
            Insert(count, Item);
        }
        /// <summary>
        /// 이 ChoriceList를 비웁니다.
        /// </summary>
        public void Clear()
        {
            if (isReadOnly) throw new NotSupportedException();
            dummy.Next = null;
            count = 0;
        }
        /// <summary>
        /// 이 ChoriceList에 해당 Item이 저장되어 있는지 확인합니다.
        /// Comparer가 아닌 Equals를 이용하여 구현합니다.
        /// </summary>
        /// <param name="Item"></param>
        /// <returns></returns>
        public bool Contains(T Item)
        {
            Node n = dummy;
            int i = 0;
            for (i; i <= count; i++)
            {
                n = n.Next;
                if (n.Data.Equals(Item))
                    return true;
            }
            return false;
        }
        /// <summary>
        /// 이 ChoriceList를 해당 Array의 해당 ArrayIndex로 복사합니다.
        /// </summary>
        /// <param name="Array"></param>
        /// <param name="ArrayIndex"></param>
        public void CopyTo(T[] Array, int ArrayIndex)
        {
            //Check Exceptions
            if (Array = null)
                throw new ArgumentNullException();
            if (ArrayIndex < 0)
                throw new ArgumentOutOfRangeException();
            if (Array.Rank != 1 || ArrayIndex >= Array.Length
                || count > Array.Length - ArrayIndex || !Array.GetType().IsAssignableFrom(T))
                throw new ArithmeticException();

            Node n = dummy;
            int i = ArrayIndex;
            while ((n = n.Next) != null)
                Array[i++] = n;
        }
        /// <summary>
        /// 이 ChoriceList에 들어있는 Item 중 가장 먼저 보이는 것을 삭제합니다.
        /// </summary>
        /// <param name="Item"></param>
        /// <returns></returns>
        public bool Remove(T Item)
        {
            if (isReadOnly) throw new NotSupportedException();

            Node n = dummy;
            int i = 0;
            while ((n = n.Next) != null)
            {
                if (n.Data.Equals(Item))
                {
                    n.Remove();
                    count--;
                    return true;
                }
            }
            return false;
        }

        /* .Net FrameWork의 기본 Generic List에 나오는 구현들 */

        /* 자체 Iteration을 위한 구현들 */

        /* 생성자들 */
        public ChoriceList()
        {
            dummy = new Node();
            count = 0;
            isReadOnly = false;
        }
        public ChoriceList(T Item)
        {
            ChoriceList();
            Node(dummy, Item);
            count++;
        }
    }
}