using System;

using System.Text;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        // We have an array of size n and want to left shift by k

        // Ex: 12345 left shited by 2 is 34512

        // Ex: 12345 left shifted by 4 is 51234

        int k = 3;

        int[] arr = new int[5]{1, 2, 3, 4, 5};

        Console.WriteLine("Shift array by " + k);

        LeftShiftArray(arr, k);

        PlayWithResizableArray();

    }

    public class ListNode{

        public int i;

        public ListNode next;

        public ListNode(int x){

            i  = x;

        }

    }

    private static void LeftShiftArray(int[] arr, int k)

    {

        ListNode head = null;

        ListNode prev = null;

        // O(n)

        for(int i = 0; i < arr.Length; i++){

            ListNode node = new ListNode(arr[i]);

            if(head == null){

                head = node;

            }

            else{

                prev.next = node;

            }

            prev = node;

        }

        // Make circular linked list so we can keep shifting past the length of the array

        prev.next = head;

        // O(k)

        // Find the kth node even if it is bigger than length of array

        ListNode start = head;

        for(int i = 0; i < k; i++){

            start = start.next;

        }

        //O(n)

        // Starting at kth node, print all nodes

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < arr.Length; i ++){

            sb.Append(String.Format("{0} ",start.i));

            start = start.next;

        }

        Console.WriteLine(sb.ToString());

    }

    public static void PlayWithResizableArray(){

        ResizableArray arr = new ResizableArray();

        string formatted = "Capacity {0} CapacityInUse {1}";

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(1);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(2);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(3);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(4);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(5);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(6);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Add(7);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

        arr.Set(arr.Capacity() + 1, 8);

        Console.WriteLine(String.Format(formatted, arr.Capacity(), arr.CapacityInUse()));

    }

    public class ResizableArray{

        int[] arr = new int[1];

        int size = 0;

        public int Capacity(){

            return arr.Length;

        }

        public int CapacityInUse(){

            return size;    

        }

        public void Set(int index, int i){

            if(index > arr.Length -1 || index < 0){

                throw new Exception("Array out of bounds");

            }

            arr[index] = i;

        }

        public void Add(int i){

            EnsureExtraCapacity();

            arr[size] = i;

            size++;

        }

        public int Get(int index){

            if(index > arr.Length - 1 || index < 0){

                throw new Exception("out of bounds");

            }

            return arr[index];  

        }

        void EnsureExtraCapacity(){

            if(size == arr.Length){

                int[] newArray = new int[arr.Length * 2];

                for(int x = 0; x < size; x++){

                    newArray[x] = arr[x];

                }

                arr = newArray; 

            }   

        }

    }

}