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.
}else{
break; //list is in order of oldest to newest, so done.
}
}
if (useTimes.size() < maxCount) {
useTimes.add(now);
return key;
}
return null;
}
}
}