using System;
namespace InsertSort
{
    class Insert_Sort
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Int16.MaxValue);
            Console.WriteLine(Int32.MaxValue);
            Console.WriteLine(Int64.MaxValue);
             Console.WriteLine((-50011/100000)%10);
            Console.WriteLine((-0)>(0));
            int seed = (int)DateTime.Now.Ticks & 0x0000FFFF;
            // Pirmas etapas
            Test_Array_List(seed);
            Console.ReadLine();
        }

        public static void InsertSort(DataArray items)
        {
            Int16 currentdata;
            int index;
            for (int i = 1; i<items.Length; i++)
            {
                currentdata = items[i];
                index = i;

                while (index>0 && items[index-1]>currentdata)
                {
                    items.Set(index, items[index - 1]);
                    index--;
                }
                items.Set(index, currentdata);
            }
        }
        public static void InsertSort(DataList items)
        {
            Int16 currentdata =items.Head();
            for (int i = 1; i <items.Length; i++)
            {
                currentdata = items.Next();

                while (currentdata<items.PreviousWithout())
                {
                    items.Swap(currentdata,items.PreviousWithout());
                    currentdata=items.Previous();
                    i--;
               }
            }
        }

        public static void RadixSort(DataArray items)
        {
            int MaxValueDigits = (int)Math.Floor(Math.Log10(getMaxValue(items)) + 1);
            for (int i = 0; i < MaxValueDigits; i++)
            {
                Int16 currentdata;
                int index;
                for (int j = 1; j < items.Length; j++)
                {
                    currentdata = items[j];
                    index = j;

                    while (GetDigit(currentdata, i) < GetDigit(items[index-1], i))
                    {
                        items.Set(index, items[index - 1]);
                        index--;
                        if (index == 0) break;
                    }
                    items.Set(index, currentdata);
                }
            }
        }

        public static void RadixSort(DataList items)
        {
            int MaxValueDigits = (int)Math.Floor(Math.Log10(getMaxValue(items)) + 1);
            for (int i = 0; i < MaxValueDigits; i++)
            {
                Int16 curr = items.Head();
                for(int j = 1; j < items.Length; j++)
                {
                    curr = items.Next();
                    while (GetDigit(curr, i) < GetDigit(items.PreviousWithout(), i))
                    {
                        items.Swap(curr, items.PreviousWithout());
                        curr = items.Previous();
                        j--;
                        if (j == 0) break;
                    }
                }
            }
        }
        public static int GetDigit(int number, int DigitNumber)
        {
            for (int i = 0; i < DigitNumber; i++)
            {
                number = number / 10;
            }

            return number % 10;
        }
        public static Int16 getMaxValue(DataArray items)
        {
            Int16 max = items[0];
            Int16 min = items[0];
            for (int i = 1; i < items.Length; i++)
            {
                Int16 curr = items[i];
                if (max < curr)
                {
                    max = curr;
                }
                if(min > curr)
                {
                    min = curr;
                }
            }
            if (min < 0) min *= (-1);
            if (max < 0) max *= (-1);
            return max > min ? (Int16)max : (Int16)min;
        }
        public static Int16 getMaxValue(DataList items)
        {
            Int16 curr = items.Head();
            Int16 max = curr;
            Int16 min = curr;
            for(int i=1; i < items.Length; i++)
            {
                curr = items.Next();
                if (max < curr)
                {
                    max = curr;
                }
                if (min > curr)
                {
                    min = curr;
                }
            }
            if (min < 0) min *= (-1);
            if (max < 0) max *= (-1);
            return max > min ? (Int16)max : (Int16)min;
        }
        public static void Test_Array_List(int seed)
        {
            int n = 5;

            MyDataArray myInsertSortArray = new MyDataArray(n, seed);
            Console.WriteLine("\n Insert Sort ARRAY \n");
            myInsertSortArray.Print(n);
            InsertSort(myInsertSortArray);
            myInsertSortArray.Print(n);

            MyDataList myInsertSortList = new MyDataList(n, seed);
            Console.WriteLine("\n Insert Sort LIST \n");
            myInsertSortList.Print(n);
            InsertSort(myInsertSortList);
            myInsertSortList.Print(n);

            MyDataArray myRadixSortArray = new MyDataArray(n, seed);
            Console.WriteLine("\n Radix Sort ARRAY \n");
            myRadixSortArray.Print(n);
            RadixSort(myRadixSortArray);
            myRadixSortArray.Print(n);

            MyDataList myRadixSortList = new MyDataList(n, seed);
            Console.WriteLine("\n Radix Sort LIST \n");
            myRadixSortList.Print(n);
            RadixSort(myRadixSortList);
            myRadixSortList.Print(n);
        }
    }
    abstract class DataArray
    {
        protected int length;
        public int Length { get { return length; } }
        public abstract Int16 this[int index] { get; }
        public abstract void Swap(int j, Int16 a, Int16 b);
        public abstract void Set(int i, Int16 value);
        public void Print(int n)
        {
            for (int i = 0; i < n; i++)
                Console.Write(" {0:d} ", this[i]);
            Console.WriteLine();
        }
    }
    abstract class DataList
    {
        protected int length;
        public int Length { get { return length; } }
        public abstract Int16 Head();
        public abstract Int16 Next();
        public abstract Int16 Previous();
        public abstract Int16 PreviousWithout();
        public abstract void Swap(Int16 a, Int16 b);
        public void Print(int n)
        {
            Console.Write(" {0:d} ", Head());
            for (int i = 1; i < n; i++)
                Console.Write(" {0:d} ", Next());
            Console.WriteLine();
        }
    }
}



//****************************************
using System;
using System.IO;
namespace InsertSort
{
    class MyDataArray : DataArray
    {
        Int16[] data;
        public MyDataArray(int n, int seed)
        {
            data = new Int16[n];
            length = n;
            Random rand = new Random(seed);
            for(int i = 0; i < length; i++)
            {

                data[i] =  (Int16)rand.Next(short.MinValue, short.MaxValue);
            }
        }
        public override Int16 this[int index]
        {
            get { return data[index]; }

        }
        public override void Swap(int j, Int16 a, Int16 b)
        {
            data[j - 1] = a;
            data[j] = b;
        }

        public override void Set(int i, Int16 value)
        {
            data[i] = value;
        }
    }
}


//****************************
using System;
using System.IO;
namespace InsertSort
{
    class MyDataList : DataList
    {
        class MyLinkedListNode
        {
            public MyLinkedListNode nextNode { get; set; }
            public MyLinkedListNode prevNode { get; set; }//
            public Int16 data { get; set; }
            public MyLinkedListNode(Int16 data)
            {
                this.data = data;
            }
        }
        MyLinkedListNode headNode;
        MyLinkedListNode prevNode;
        MyLinkedListNode currentNode;
        public MyDataList(int n, int seed)
        {
            length = n;
            Random rand = new Random(seed);
            headNode = new MyLinkedListNode((Int16)rand.Next(short.MinValue, short.MaxValue));
            currentNode = headNode;
            for (int i = 1; i < length; i++)
            {
                prevNode = currentNode;
                currentNode.nextNode = new MyLinkedListNode((Int16)rand.Next(short.MinValue, short.MaxValue));
                currentNode = currentNode.nextNode;
                currentNode.prevNode = prevNode;//
            }
            currentNode.nextNode = null;
        }
        public override Int16 Head()
        {
            currentNode = headNode;
            prevNode = null;
            return currentNode.data;
        }
        public override Int16 Next()
        {
            prevNode = currentNode;
            currentNode = currentNode.nextNode;
            return currentNode.data;
        }

        public override Int16 Previous()
        {
            prevNode = currentNode;
            currentNode = currentNode.prevNode;
            return currentNode.data;
        }

        public override Int16 PreviousWithout()
        {
            if (currentNode != headNode)
            {
                return currentNode.prevNode.data;
            } else
            {
                return Int16.MinValue;
            }
        }

        public override void Swap(Int16 a, Int16 b)//current/prev
        {
             currentNode.prevNode.data = a;
             currentNode.data = b;
        }
    }
}