Code review Leetcode 295 - median of stream - using SortedSet

Leetcode295_MedianOfStream_usingSortedSetCodeReview.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode295_medianOfStream
{
    /// <summary>
    /// Leetcode 295: 
    /// https://leetcode.com/problems/find-median-from-data-stream/#/description
    /// Using SortedSet to solve the problem, underneath is binary search tree. 
    /// A few challenges here:
    /// 1. Go over SortedSet in C#, understand API
    /// Comparer defintion:
    ///     Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])
    /// Max, Min, Count 3 APIs 
    /// 
    /// June 6, 2017 Will figure out how to get more familiar with C# SortedSet
    /// 
    /// June 29, 2017
    /// Read the book Item 31: Implement ordering relations with IComparable<T>
    /// and IComparer<T> 
    /// Book: Effective C# 50 Specific Ways to Improve Your C# Second Edition Scott Meyers
    /// 
    /// </summary>
    class MedianFinder
    {
        static void Main(string[] args)
        {
            //RunTestcase();
            RunTestcase2();
        }

        public static void RunTestcase()
        {
            var medianFinder = new MedianFinder();
            medianFinder.AddNumber(1);
            medianFinder.AddNumber(5);
            medianFinder.AddNumber(3);
            medianFinder.AddNumber(4);
            medianFinder.AddNumber(2);

            var median = medianFinder.FindMedian();
            Debug.Assert(median == 3);
        }

        public static void RunTestcase2()
        {
            var medianFinder = new MedianFinder();
            medianFinder.AddNumber(1);
            medianFinder.AddNumber(5);
            medianFinder.AddNumber(3);
            medianFinder.AddNumber(4);
            medianFinder.AddNumber(2);
            medianFinder.AddNumber(6);

            var median = medianFinder.FindMedian();
            Debug.Assert(Math.Abs(median - 3.5) < 0.001);
        }

        private int counter = 0;

        /// <summary>
        /// code review on June 29, 2017 - need to look into SortedSet<IComparer>
        /// 
        /// </summary>
        private SortedSet<int[]> treeLowerHalf = new SortedSet<int[]>(
            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

        private SortedSet<int[]> treeUpperHalf = new SortedSet<int[]>(
            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

        /// <summary>
        /// code review on June 29, 2017
        /// Keep two tree same size if there are even numbers. If there are odd numbers, 
        /// then first tree called treeLowerHalf will have numbers/2 + 1 numbers. 
        /// 
        /// Need to go over SortedSet API: Add, Remove, 
        /// Property Max[2] and Min[2]
        /// https://msdn.microsoft.com/en-us/library/dd411719(v=vs.110).aspx
        /// </summary>
        /// <param name="number"></param>
        public void AddNumber(int number)
        {
            var item = new int[] { number, counter++ };  // what is the second number for? 

            int  countLower = treeLowerHalf.Count; 
            bool isSameSize = countLower == treeUpperHalf.Count;
            bool lowerTreeEmpty = countLower == 0;

            int  maxValueLowerTree = lowerTreeEmpty ? int.MinValue : treeLowerHalf.Max[0];
            bool lessThanMaxValueLowerTree = number <= maxValueLowerTree; 

            if (isSameSize)
            {
                if (treeLowerHalf.Count == 0 || lessThanMaxValueLowerTree)
                {
                    treeLowerHalf.Add(item);
                }
                else
                {
                    treeUpperHalf.Add(item);

                    // move the minimum number from treeUpperHalf to treeLowerHalf. 
                    treeLowerHalf.Add(treeUpperHalf.Min);
                    treeUpperHalf.Remove(treeUpperHalf.Min);
                }
            }
            else if (lessThanMaxValueLowerTree)
            {
                treeLowerHalf.Add(item);

                // move the maximum number from treeLowerHalf to treeUpperHalf
                treeUpperHalf.Add(treeLowerHalf.Max);
                treeLowerHalf.Remove(treeLowerHalf.Max);
            }
            else
            {
                treeUpperHalf.Add(item);
            }
        }

        /// <summary>
        /// Code review on June 29, 2017
        /// Return the median of current data stream
        /// </summary>
        /// <returns></returns>
        public double FindMedian()
        {
            if (treeLowerHalf.Count == 0)
            {
                return 0;
            }

            if (treeLowerHalf.Count == treeUpperHalf.Count)
            {
                return (treeLowerHalf.Max[0] + treeUpperHalf.Min[0]) / 2d;
            }
            else
            {
                return treeLowerHalf.Max[0];
            }
        }
    }
}