package com.xsm.beustchallenge.slidingwindowmap;

import java.util.Date;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Solving for Beust Challenge: Sliding Window Map
 * http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/
 * 
 * @author Sony Mathew
 */
public class SlidingWindowMap {
	
	private final Set<String> keys; 
	private final int maxCount;
	private final long maxPeriodMs;
	
	private List<KeyTrack> keyTracks = new LinkedList<>();
	
	/**
	 * author Sony Mathew
	 */
	public SlidingWindowMap(Set<String> keys, int maxCount, long maxPeriodMs) {
		this.keys = keys;
		this.maxCount = maxCount;
		this.maxPeriodMs = maxPeriodMs;
		
		for(String key : this.keys) {
			keyTracks.add(new KeyTrack(key));
		}
	}

	/**
	 * @return a key that has been used less than `maxCount` times during the
	 *         past `maxPeriodMs` milliseconds or null if no such key exists.
	 */
	public synchronized String getNextKey() {
		List<KeyTrack> keyTracksUsedUp = new LinkedList<>();
		try {
			Iterator<KeyTrack> keyTrackIter = keyTracks.iterator();	
			while(keyTrackIter.hasNext()) {
				KeyTrack keyTrack = keyTrackIter.next();
				String key = keyTrack.useKey();
				if (key != null) {											
					return key;
				}else{
					keyTrackIter.remove();
					keyTracksUsedUp.add(keyTrack);
				}
			}
			return null; //no keys found, all used up.
		}finally{
			//put used-up keys back at the end.
			for(KeyTrack keyTrackUsedUp : keyTracksUsedUp) {
				keyTracks.add(keyTrackUsedUp);
			}
		}
	}
	
	/**
	 * Tracks a key's use.
	 *
	 * @author Sony Mathew
	 */
	class KeyTrack {
		final String key;
		final List<Date> useTimes = new LinkedList<>(); 
		
		KeyTrack(String key) {
			this.key = key;
		}
		
		/**
		 * @return : key if it can be used, else null.
		 * author Sony Mathew
		 */
		String useKey() {
			Date now = new Date();
			
			//Remove all old use times.
			Iterator<Date> useTimeIter = useTimes.iterator();
			while (useTimeIter.hasNext()) {
				Date useTime = useTimeIter.next();
				long usePeriod = now.getTime()-useTime.getTime();
				if (usePeriod>maxPeriodMs) {
					useTimeIter.remove(); //no longer countable, past max period.
				}
			}
			
			if (useTimes.size() < maxCount) {
				useTimes.add(now);
				return key;				
			}
			
			return null;
		}
	}	
}