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

namespace LinkList
{
    /// <summary>
    /// 结点类
    /// 结点数据类型用double表示
    /// </summary>
    public class ListNode<T>
    {
        public T data; //ElemType
        public ListNode(T value) : this() { this.data = value; }
        internal ListNode() { this.next  = null; }

        public ListNode<T> next;
    }

    /// <summary>
    /// 链表类
    /// </summary>
    public class LinkList<T>
    {
        private  int count;
        private ListNode<T> hNode;
        public ListNode<T> head;
        public ListNode<T> first;   //第一个结点
        EqualityComparer<T> m_Comparer = EqualityComparer<T>.Default;
        public LinkList()
        {
             hNode = new ListNode<T>();
            //hNode.data = <T>count;
            hNode.next = null;
            head = hNode;
            first = null;
        }

        public bool IsEmpty()
        {
            return head .next  == null;
        }

        public int Length()
        {
            ListNode<T> current = first;
            int length = 0;
            while (current != null)
            {
                length++;
                current = current.next;
            }
            return length;
        }

        /// <summary>
        /// 返回第k个元素至x中
        /// </summary>
        /// <param name="k"></param>
        /// <param name="x"></param>
        /// <returns>如果不存在第k个元素则返回false,否则返回true</returns>
        public bool Find(int k, ref T x)
        {
            if (k < 1)
                return false;
            ListNode<T> current = first;
            int index = 1;
            while (index < k && current != null)
            {
                current = current.next;
                index++;
            }
            if (current != null)
            {
                x = current.data;
                return true;
            }
            return false;
        }

        /// <summary>
        /// 返回x所在的位置
        /// </summary>
        /// <param name="x"></param>
        /// <returns>如果x不在表中则返回0</returns>
        public int Search(T x)
        {
            ListNode<T> current = first;
            int index = 1;
            while (current != null && m_Comparer.Equals(x, current.data))
            {
                current = current.next;
                index++;
            }
            if (current != null)
                return index;
            return 0;
        }

        /// <summary>
        /// 删除第k个元素，并用x返回其值
        /// </summary>
        /// <param name="k"></param>
        /// <param name="x"></param>
        /// <returns></returns>
        public LinkList<T> Delete(int k, ref T x)
        {
            //如果不存在第k个元素则引发异常
            if (k < 1 || first == null)
                throw (new NullReferenceException());
            ListNode<T> pNode = first;  //pNode将最终指向第k个结点
            //将pNode移动至第k个元素，并从链表中删除该元素
            if (k == 1) //pNode已经指向第k个元素
            {
                x = first.data;
                first = first.next;  //删除之
            }
            else
            {
                //用qNode指向第k-1个元素
                ListNode<T> qNode = first;
                for (int index = 1; index < k - 1 && qNode != null; index++)
                    qNode = qNode.next;
                if (qNode == null || qNode.next == null)
                    throw (new NullReferenceException());//不存在第k个元素
                pNode = qNode.next; //pNode指向第k个元素
                qNode.next = pNode.next; //从链表中删除第k个元素
                x = pNode.data;
            }
            return this;
        }

        /// <summary>
        /// 在第k个元素之后插入x
        /// </summary>
        /// <param name="k"></param>
        /// <param name="x"></param>
        /// <returns></returns>
        public LinkList<T> Insert(int k, T x)
        {
            //如果不存在第k个元素,则引发异常NullReferenceException
            if (k < 0)
                throw (new IndexOutOfRangeException());
            ListNode<T> pNode = first;  //pNode将最终指向第k个结点
            for (int index = 1; index < k && pNode != null; index++)
                pNode = pNode.next;
            if (k > 0 && pNode == null)
                throw (new NullReferenceException());//不存在第k个元素
            ListNode<T> xNode = new ListNode(x);
            //xNode.data = x;
            if (k > 0)
            {
                //在pNode之后插入
                xNode.next = pNode.next;
                pNode.next = xNode;
            }
            else
            {
                //作为第一个元素插入
                xNode.next = first;
                first = xNode;
            }
            return this;
        }

        public void Clear()
        {
            first = null;
        }

        public void OutPut()
        {
            ListNode<T> current;
            for (current = first; current != null; current = current.next)
            {
                Console.Write("{0}", current.data.ToString());
            }

            Console.WriteLine();
        }
    }
    public class SortLinkList<T> : LinkList<T>
    {
        /// <summary>
        /// 返回x所在的位置
        /// </summary>
        /// <param name="x"></param>
        /// <returns>如果x不在表中则返回0</returns>
        public SortLinkList<T> Add(T x)
        {
            //int index = 1;
            ListNode<T> pNode = first;  //pNode将最终指向第k个结点
            ListNode<T> xNode = new ListNode(x);
            //xNode.data = x;
            if (pNode != null)
            {
                while (pNode.next != null)
                {
                    if (pNode.data < x && pNode.next.data > x)
                    {
                        xNode.next = pNode.next;
                        pNode.next = xNode;
                        count++;
                        break;
                    }
                    else if(pNode.data >x)
                    {
                        xNode.next = pNode;
                        count++;
                        first = xNode;
                        head .next = first;
                        break;
                    }
                    pNode = pNode.next;

                }
                if (pNode.next == null)
                {
                    if (pNode.data > x)
                    {                       
                        pNode.next = xNode;
                        count++;
                        T temp = xNode.data;
                        xNode.data = pNode.data;
                        pNode.data = temp;
                    }
                    else
                    {
                        pNode.next = xNode;
                        count++;
                    }
                }
            }
            else
            {
                //作为第一个元素插入
                count++;
                xNode.next = first;
                first = xNode;
                head.next = first;
            }
            return this;

        }
        private ListNode<T> GetNode(int index)
        {
            if (index < 0 || index >= this.count)
                throw new ArgumentOutOfRangeException("index", index, "Index value is out of range, please check!");

            ListNode<T> node = this.head.next;
            while (index-- > 0) node = node.next ;

            return node;
        }

        public object this[int index]
        {
            get { return this.GetNode(index).data; }
            set { this.GetNode(index).data  =(double) value; }
        }

        //public object this[int index]
        //{
        //    get
        //    {
        //        int ctr = 0;
        //        ListNode  node = first;
        //        while (node != null && ctr <= index)
        //        {
        //            if (ctr == index)
        //            {
        //                return node.data;
        //            }
        //            else
        //            {
        //                node = node.next;
        //            }
        //            ctr++;
        //        }
        //        return null;
        //    }
        //}

        class Program
        {
            static void Main(string[] args)
            {
                SortLinkList slltest = new SortLinkList();
                slltest.Add(3.0);
                slltest.Add(2.0);
                slltest.Add(1.0);
                slltest.Add(6.0);
                slltest.Add(5.0);
                slltest.Add(4.0);
                slltest.OutPut();
                double a1 = (double)slltest[0];
                double a2 = (double)slltest[5];
                double a3 = 9;
                slltest[5] = a3;
                slltest.OutPut();
            }
        }
    }
}