import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class SlidingWindowMap {
private final Map<String, SlidingWindow> keyToSlidingWindow = new HashMap<String, SlidingWindow>();
private final int maxCount;
private final long periodMs;
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) {
if(maxCount<=0) {
throw new IllegalArgumentException("Max count must be strictly greater than zero.");
}
if(periodMs<=0) {
throw new IllegalArgumentException("PeriodMs must be strictly greater than zero.");
}
this.maxCount = maxCount;
this.periodMs = periodMs;
for (String key : keys) {
keyToSlidingWindow.put(key, new SlidingWindow());
}
}
public void keyPressed(String key) {
final SlidingWindow slidingWindow = keyToSlidingWindow.get(key);
if(slidingWindow==null) {
throw new IllegalArgumentException(String.format("Unsupported key - %s", key));
}
final long now = System.currentTimeMillis();
synchronized (slidingWindow.timeStamp) {
if(slidingWindow.timeStamp==null) {
slidingWindow.timeStamp = new ArrayList<Long>();
}
slidingWindow.timeStamp.add(now);
cleanUpWindow(slidingWindow.timeStamp, now);
}
}
/**
* @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 nextKey=null;
String key;
SlidingWindow window;
int minKeyPresses=0;
int keyPressesInsideWindow;
boolean firstEntry = true;
for (Iterator<String> iterator = keyToSlidingWindow.keySet().iterator(); iterator.hasNext();) {
key = iterator.next();
window = keyToSlidingWindow.get(key);
if(window==null || window.timeStamp==null || window.timeStamp.isEmpty()) {
continue;
}
keyPressesInsideWindow = keyPressesForWindow(window);
if(keyPressesInsideWindow<=maxCount) {
if(firstEntry) {
firstEntry=false;
minKeyPresses = keyPressesInsideWindow;
nextKey = key;
} else if(keyPressesInsideWindow<minKeyPresses) {
minKeyPresses = keyPressesInsideWindow;
nextKey = key;
}
}
}
return nextKey;
}
/**
* this cleanup of the sliding window for the current key is done here, but could be done by a
* background thread. The idea is to prevent the windows from growing 'too' large
*/
private void cleanUpWindow(List<Long> timeStamps, long now ) {
final long beginningOfWindow = now - periodMs;
for (Iterator<Long> iterator = timeStamps.iterator(); iterator.hasNext();) {
if(iterator.next()<beginningOfWindow) {
iterator.remove();
}
}
}
private int keyPressesForWindow(SlidingWindow window) {
final long now = System.currentTimeMillis();
final long beginningOfWindow = now - periodMs;
int keyPressesInsideWindow = 0;
// iterate from most recent to least recently used
synchronized (window.timeStamp) {
for (int i = window.timeStamp.size()-1; i >= 0; i--) {
if(window.timeStamp.get(i)>=beginningOfWindow) {
++keyPressesInsideWindow;
}
if(keyPressesInsideWindow>maxCount) {
break;
}
}
}
return keyPressesInsideWindow;
}
private static class SlidingWindow {
List<Long> timeStamp;
}
}