import java.util.*;
/**
 * 
 * @author Mahsa Sadi
 * 
 * @since 2020 - 03 - 13 
 * 
 * License: Creative Commons
 * 
 * Copyright by Mahsa Sadi
 * 
 *
 */
public class MedianFinderV1 extends MedianFinder {
	
	
	/**
	 * Problem: 
	 * 
	 * Find Median from Data Stream
	 * 
	 * 
	 * 
	 * Description:
	 * 
	 * Median is the middle value in an ordered integer list. 
	 * 
	 * If the size of the list is even, there is no middle value. 
	 * 
	 * So the median is the mean of the two middle value.
	 * 
	 * 
	 * 
	 * Design a data structure that supports the following two operations:
	 * 
	 * void addNum(int num) - Add a integer number from the data stream to the data structure.
	 * 
	 * double findMedian() - Return the median of all elements so far.
	 * 
	 * 
	 * 
	 * 
	 * Solution:
	 * 
	 * 
	 * 1- Consider an array list for storing the elements of the data stream.
	 * 
	 * 2- Keep this array list always sorted upon adding a new element.
	 * 
	 * 3- Use binary search to find the location where a new element should be inserted. 
	 * 
	 * 
	 * 
	 * Note:  
	 * 
	 * This array list is a high-level data structure in Java,
	 * 
	 * with a performance between an array of items and a list of items.
	 * 
	 * 
	 * 
	 * Complexity:
	 * 
	 * 1- findMedian: O (1);
	 * 2- addNum: Log (dataStream.size()) + O (dataStream.size ()) = O (N + Log N) = O (N)
	 * 
	 * 
	 * 
	 */

	List <Integer> dataStream;
	
    
	
	public MedianFinderV1 ()
	{
		dataStream = new ArrayList <Integer> ();
	}
	
	
	
	@Override
	public double findMedian() {
		
		
		double median;
		
		if (dataStream.size() % 2 == 0)
		{
			median =  (double) ( dataStream.get(dataStream.size() / 2  ) + 
					    dataStream.get( (dataStream.size() / 2) - 1) ) 
			            / 2;
		}
		
		else 
			median = dataStream.get(dataStream.size() / 2);
		
		
		return median;
		
	}
	
	
	@Override
	public void addNum(int num) {
		
		if (dataStream.isEmpty())
			dataStream.add(num);
		  
		
		else 
		{
			int position = findLocationUsingBinarySearch (num, 0 , dataStream.size() - 1 );
			dataStream.add(position, num);
		}
		
	}
	
	
	
	
	public int findLocationUsingBinarySearch (int num, int start, int end)
	{
		int middle = (start + end ) / 2;
		int middleValue = dataStream.get(middle);
		
		
		
		if (num == middleValue) 
			return middle + 1;
		
		
		else if (start == end)
		{
		   if (num > dataStream.get(start))	
			 return end + 1;
		   else 
			 return start;
		}
		
		else if (num > middleValue)
		{
			
			if (middle != end )
			    return findLocationUsingBinarySearch (num, middle + 1, end);
			else 
				return findLocationUsingBinarySearch (num, middle, end);
		}
		
		
		else 
		{
			if (start != middle)
			   return findLocationUsingBinarySearch (num, start, middle - 1);
			else
			   return findLocationUsingBinarySearch (num, start, middle);
		}
		
		
	}

	
	
	public String toString ()
	{
		String data ="";
		
		for (Integer element : dataStream)
			data += element + "  ";
		
		return data;
			
	}

}