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

namespace LinkList
{
    /// <summary>
    /// 结点类
    /// 结点数据类型用double表示
    /// </summary>
    public class ListNode<T> //: IComparable<T>
    {
        public T data; //ElemType
        public ListNode(T value) : this() { this.data = value; }
        internal ListNode() { this.next  = null; }
        EqualityComparer<T> m_Comparer = EqualityComparer<T>.Default;
        public ListNode<T> next;
    }
    /// <summary>
    /// 链表类
    /// </summary>
    public class LinkList<T>//:IComparable<T>//:ICollection <T>,IEnumerator<T>,IList <T>
    {
        public  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<T>(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> where T : IComparable<T>
    {
       
        public override String ToString()
        {
            StringBuilder sb = new StringBuilder();
            return sb.ToString();
        }

        public IEnumerator<T> GetEnumerator()
        {
            ListNode<T> current = head;
            while (current != null)
            {
                yield return current.data;
                current = current.next;
            }
        }
        /// <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<T>(x);
            //xNode.data = x;
            if (pNode != null)
            {
                while (pNode.next != null)
                {
                    if (pNode.data.CompareTo(x) < 0 && pNode.next.data.CompareTo(x) > 0)
                    {
                        xNode.next = pNode.next;
                        pNode.next = xNode;
                        count++;
                        break;
                    }
                    else if (pNode.data.CompareTo(x) > 0)
                    {
                        xNode.next = pNode;
                        count++;
                        first = xNode;
                        head.next = first;
                        break;
                    }
                    pNode = pNode.next;

                }
                if (pNode.next == null)
                {
                    if (pNode.data.CompareTo(x) > 0)
                    {
                        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 T this[int index]
        {
            get { return this.GetNode(index).data; }
            set { this.GetNode(index).data = value; }
        }
       
    }
    class Program
    {
        static void Main(string[] args)
        {           
            //Declare and instantiate a new generic SortedList class.
            //Person is the type argument.
            SortLinkList<Person> list = new SortLinkList<Person>();
            //Create name and age values to initialize Person objects.
            string[] names = new string[]{"Franscoise", "Bill", "Li", "Sandra", "Gunnar", "Alok", "Hiroyuki", "Maria", "Alessandro", "Raul"};
            int[] ages = new int[]{45, 19, 28, 23, 18, 9, 108, 72, 30, 35};
            //Populate the list.
            for (int x = 0; x < 10; x++)
            {
                list.Add(new Person(names[x], ages[x]));
            }  
        }
    }
    public class Person : IComparable<Person>
    {

        string name;
        int age;
        public Person()
        {           
        }
        public Person(string s, int i)
        {
            name = s;
            age = i;
        }
        // This will cause list elements
        // to be sorted on age values.
        public int CompareTo(Person p)
        {
            return age - p.age;
        }
        public override string ToString()
        {
            return name + ":" + age;
        }
        // Must implement Equals.
        public bool Equals(Person p)
        {
            return (this.age == p.age);
        }

    }

}