using System;

/*
 * STUDENTS: Your answers (your code) goes into this file!!!!
 *
  * NOTE: In addition to your answers, this file also contains a 'main' method,
 *      in case you want to run a normal console application.
 *
 * If you want to / have to put something into 'Main' for these PCEs, then put that
 * into the Program.Main method that is located below,
 * then select this project as startup object
 * (Right-click on the project, then select 'Set As Startup Object'), then run it
 * just like any other normal, console app: use the menu item Debug->Start Debugging, or
 * Debug->Start Without Debugging
 *
 */

namespace PCE_StarterProject
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello, world!");
        }
    }

    class DuplicateValueException : Exception
    { public DuplicateValueException(string msg) : base(msg) { } }

    public class BST
    {
        private BSTNode m_top;

        private class BSTNode
        {
            private int m_data;
            private BSTNode m_left;
            private BSTNode m_right;

            public int Data
            {
                get { return m_data; }
                set { m_data = value; }
            }
            public BSTNode Left
            {
                get { return m_left; }
                set { m_left = value; }
            }
            public BSTNode Right
            {
                get { return m_right; }
                set { m_right = value; }
            }

            public BSTNode(int data)
            {
                m_data = data;
            }
        }

        public void AddValue(int v)
        {
            if (m_top == null)
            {
                m_top = new BSTNode(v);
            }
            else
            {
                BSTNode cur = m_top;
                while (true)
                {
                    if (v < cur.Data)
                    {
                        if (cur.Left == null)
                        {
                            cur.Left = new BSTNode(v);
                            return;
                        }
                        else
                            cur = cur.Left;
                    }
                    else if (v > cur.Data)
                    {
                        if (cur.Right == null)
                        {
                            cur.Right = new BSTNode(v);
                            return;
                        }
                        else
                            cur = cur.Right;
                    }
                    else
                        throw new DuplicateValueException("Value " + v + " is already in the tree!");
                }
            }
        }

        public void Print()
        {
            Console.WriteLine("=== Printing the tree ===");
            if (m_top == null)
                Console.WriteLine("Empty tree!");
            else
                PrintInternal(m_top);
        }
        private void PrintInternal(BSTNode cur)
        {
            if (cur.Left != null)
                PrintInternal(cur.Left);

            Console.WriteLine(cur.Data);

            if (cur.Right != null)
                PrintInternal(cur.Right);
        }

        public bool Find(int target)
        {
            return FindNode(target) != null;
        }

        private BSTNode FindNode(int target)
        {
            BSTNode cur = m_top;
            while (cur != null)
            {
                if (cur.Data == target)
                    return cur;
                else if (target < cur.Data)
                    cur = cur.Left;
                else if (target > cur.Data)
                    cur = cur.Right;
            }

            return null;
        }


        public void Remove(int target)
        {
            // if the tree is empty:
            if (m_top == null)
                return;
            //else
            //    throw new DuplicateValueException("Value " + target + " is already in the tree!");

            if (m_top.Data == target)
            {
                RemoveRootNode(target);
            }
            else
            {
                RemoveNonrootNode(target);
            }
        }

        private void RemoveNonrootNode(int target)
        {
            BSTNode cur = m_top;
            BSTNode parent = null;

            //First, find the target node that we need to remove
            // we'll have the 'parent' reference trail the cur pointer down the tree
            // so when we stop, cur is the node to remove, and parent is one above it.
            while (true)
            {
                if (cur.Data == target)
                {
                    break;
                }
                else if (cur.Data > target)
                {
                    parent = cur;
                    cur = cur.Left;
                }
                else
                {
                    parent = cur;
                    cur = cur.Right;
                }
            }

            // Next, we figure out which of the cases we're in

            // Case 1: The target node has no children
            if (cur.Left == null && cur.Right == null)
            {
                cur = parent;
                cur.Left = null;
                cur.Right = null;

                return;
            }
            // Case 2: The target node has 1 child
            // (You may want to split out the left vs. right child thing)
            else if (cur.Left == null || cur.Right == null)
            {
                BSTNode temp = (cur.Left == null) ? cur.Right : cur.Left;
                if (parent.Left == cur)
                    parent.Left = temp;
                else
                    parent.Right = temp;
            }

            // Case 3: The target node has 1 child
            else
            {
                int temp = TestFindAndRemoveNextSmallest(cur.Data);
                parent.Data = temp;
            }
        }

        private void RemoveRootNode(int target)
        {
            // If we're here, it's because we're removing the top-most node (the 'root' node)

            // Case 1: Root has no children
            if (m_top.Left == null && m_top.Right == null)
            {
                m_top = null;            // Therefore, the tree is now empty
                return;
            }
            // Case 2: Root has 1 child
            else if (m_top.Left == null)
            {
                // 1 (right) child, OR zero children (right may also be null)
                m_top = m_top.Right; // Right is null or another node - either way is correct
                return;
            }
            else if (m_top.Right == null)
            {
                // If we're here, Left is not null, so there MUST be one (Left) Child
                m_top = m_top.Left;
                return;
            }
            // Case 3: Root has two children - this is where it gets interesting :)
            else
            {
                // 2 children - find (and remove) next smaller value
                // use that data to overwrite the current data.
                BSTNode removee = FindAndRemoveNextSmallerValue(target, m_top);
                m_top.Data = removee.Data;
                return;
            }
        }

        /// <summary>
        /// This method takes 1 step to the left, then walks as far to the right
        /// as possible.  Once that right-most node is found, it's removed & returned.
        /// Note that the node MAY be immediately to the left of the <B>startHere</B>
        /// parameter, if startHere.Left.Right == null
        /// </summary>
        /// <param name="smallerThanThis"></param>
        /// <param name="startHere"></param>
        /// <returns></returns>
        private BSTNode FindAndRemoveNextSmallerValue(int smallerThanThis, BSTNode startHere)
        {
            BSTNode parent = startHere;
            BSTNode child = startHere.Left;

            return null;
        }

        // Given the value of a node, find (and remove) the predessor node in the tree
        // returns the value of the predecessor node, or Int32.MinValue if no such value was found
        public int TestFindAndRemoveNextSmallest(int sourceNode)
        {
            BSTNode startAt = this.FindNode(sourceNode);
            // sourceNode should == startAt.Data, unless startAt is null)
            BSTNode removed = FindAndRemoveNextSmallerValue(sourceNode, startAt);
            if (removed != null)
                return removed.Data;
            else
                return Int32.MinValue;
        }
    }


    public class SearchingAndSorting
    {
        // Answer O(nlogn)
        // Answer O(1) space
        public int Partition(int[] arr, int low, int high)
        {
            int pivot = arr[low];

            // index of the smaller element
            int i = (low - 1);
            for (int j = low; j < high; j++)
            {
                if (arr[j] <= pivot)
                {
                    i++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

            int temp1 = arr[i + 1];

            arr[i + 1] = arr[low];

            arr[low] = temp1;

            return i + 1;
        }


        public void QuickSort(int[] nums)
        {
            QuickSort(nums, 0, nums.Length - 1);

        }

        private void QuickSort(int[] nums, int iStart, int iEnd)
        {
            if (iStart < iEnd)
            {
                int pi = partition(nums, iStart, iEnd);
                QuickSort(nums, iStart, pi - 1);
                QuickSort(nums, pi - 1, iEnd);
            }
        }

            //finding the parttion index
        private void swap(int a, int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        private int partition(int[] arr, int low, int high)
        {
            int pivot = arr[high]; // pivot
            int i = (low - 1); // Index of smaller element

        for (int j = low; j <= high - 1; j++)
        {
            // If current element is smaller than the pivot
            if (arr[j] < pivot)
            {
                i++; // increment index of smaller element
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[high]);
        return (i + 1);
        }
    }
}