using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace CodingInterview
{
    [TestClass]
    public class SortStack
    {
        public static Stack<int> SortStack(Stack<int> stackToSort)
        {
            var buffer = new Stack<int>(stackToSort.Count);

            while (stackToSort.Count != 0)
            {
                for (int i = 0; i < stackToSort.Count; i++)
                {
                    var currentItem = stackToSort.Pop();
                    if (buffer.Count == 0 || currentItem >= buffer.Peek())
                    {
                        buffer.Push(currentItem);
                    }
                    else
                    {
                        while (buffer.Count > 0)
                        {
                            stackToSort.Push(buffer.Pop());
                        }

                        stackToSort.Push(currentItem);
                    }
                }
            }

            return buffer;
        }

        [TestMethod]
        public void SortStackTest()
        {
            var stack = new Stack<int>();
            var sequence = new[] {5, 12, 11, 3, 10, 20, 500, -9, 55, 1, -1, -1, 22, -1 };
            foreach (var i in sequence)
            {
                stack.Push(i);
            }

            var result = SortStack(stack);
            Assert.IsNotNull(result);

            Array.Sort(sequence);

            var reversed = sequence.Reverse();
            foreach (var i in reversed)
            {
                Assert.AreEqual(i, result.Pop());
            }
        }
    }
}