import java.util.*;

public class SlidingWindowMap
{
	public final static int 	s_MaxKeyCount = 500;

	public final static long 	s_NumMSIn10Min 
				= 10 /*min*/ * 60 /*sec/min*/ * 1000 /*ms/sec*/;

	public final static int		s_NumberOfRequestsIn10Min_OnePerSecond 
				= 10 /*min*/ * 60 /*sec/min*/ * 2;  // 2 per second or every 500 ms

	public final static long	s_TimeBetweenRequestsInMs = 500;
	
	// Input data members
	private Set<String> 		m_Keys;
	private Iterator<String> 	m_KeysIterator;
	private int 			m_MaxCount;
	private long			m_PeriodMs;
	private KeyStyle		m_KeyStyle;

	// Throttled data members
	private long			m_LastTime;
	
	// Non-throttled data members
	private int			m_CurrentCount;
	
	enum KeyStyle
	{
		NoThrotle,
		Throtle
	}

	public static void main(String[] args)
	throws Exception
	{
		KeyStyle ks = KeyStyle.Throtle;
		
		if(args.length == 1)
		{
			String keyStyle = args[0];
			if(keyStyle.equalsIgnoreCase("-throttled"))
			{
				ks = KeyStyle.Throtle;
			}
			else if(keyStyle.equalsIgnoreCase("-nonthrottled"))
			{
				ks = KeyStyle.NoThrotle;
			}
		}
		
		Set<String> keys = generateKeys();
		
		SlidingWindowMap m = null;
		m = new SlidingWindowMap(keys, 500, s_NumMSIn10Min, ks);
		
		long start = System.currentTimeMillis();
		
		boolean firstNullAchieved = false;
		// Rate is greater than 500 in 10 min. ==> 2 per second. Null's should occur			
		for(int i=0; i<s_NumberOfRequestsIn10Min_OnePerSecond; i++)
		{
			String key = m.getNextKey();
			System.out.println(key);
			
			if(key == null && firstNullAchieved == false)
			{
				long firstNull = System.currentTimeMillis();
				long whenFirstNullAchieved = firstNull - start;
				System.out.println("Time Of First Null = "+whenFirstNullAchieved);
				firstNullAchieved = true;
			}
			
			Thread.sleep(s_TimeBetweenRequestsInMs);
		}

		long stop = System.currentTimeMillis();

		long total = stop - start;

		System.out.println("Total Time = "+total);
	}
	
	private static Set<String> generateKeys()
	{
		Set<String> keys = new HashSet<String>();
		for(int i=0; i<s_MaxKeyCount; i++)
		{
			keys.add("Key"+i);
		}
		return keys;
	}

	public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs)
	{
		this.m_Keys 		= keys;
		this.m_KeysIterator = keys.iterator();
		this.m_MaxCount 	= maxCount;
		this.m_PeriodMs		= periodMs;
	}
	
	public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs, KeyStyle keyStyle)
	{
		this(keys, maxCount, periodMs);
		
		this.m_KeyStyle = keyStyle;
	}

	/**
	 * @return a key that has been used less than 'maxCount' times during the 
	 * past 'periodMs' milliseconds or null if no such key exists.
	 */
	public String getNextKey()
	{
		String key = null;
		if(this.m_KeyStyle == KeyStyle.NoThrotle)
		{
			key = getNonThrottledNextKey();
		}
		else if(this.m_KeyStyle == KeyStyle.Throtle)
		{
			key = getThrottledNextKey();
		}
		return key;
	}

	/**
	 * To allow some keys to be accessible through the entire 10 min period.  
         * Return a null for any additional requests over the rate of 0.8333 requests per second.  
         * Every 1.2 seconds a valid key can be provided.
	 */
	private String getThrottledNextKey()
	{
		String key = null;

		long currentTime = System.currentTimeMillis();
		if(currentTime - this.m_LastTime >= 1200)
		{
			if(this.m_KeysIterator.hasNext())
			{
				key = this.m_KeysIterator.next();
				this.m_LastTime = currentTime;
			}
		}

		return key;
	}

	/**
	 * First come first serve, all keys may be used up in the first few minutes, leaving a range of 
	 * time at the end of the period that no keys are returned to any requests.
	 */
	private String getNonThrottledNextKey()
	{
		String key = null;
		if(this.m_CurrentCount != this.m_MaxCount)
		{
			if(this.m_KeysIterator.hasNext())
			{
				key = this.m_KeysIterator.next();
			}
		}
		return key;
	}
}