Skip to content

Instantly share code, notes, and snippets.

@rnaufal
Created September 16, 2012 17:36
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save rnaufal/3733384 to your computer and use it in GitHub Desktop.
Cedric's Coding challenge: a sliding window map (http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/)
package com.beust.coding.challenge.slidingwindowmap;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/**
*
* @author rnaufal
*
*/
public class SlidingWindowMap {
private final Set<String> keys;
private final int maxCount;
private final long periodMs;
private final Map<String, SlidingWindow> slidingWindowByKey = new HashMap<String, SlidingWindow>();
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) {
this.keys = keys;
this.maxCount = maxCount;
this.periodMs = periodMs;
}
/**
* @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() {
for (String key : keys) {
SlidingWindow slidingWindow = slidingWindowByKey.get(key);
if (slidingWindow == null) {
slidingWindow = new SlidingWindow();
slidingWindowByKey.put(key, slidingWindow);
return key;
}
if (slidingWindow.isValidForUse(maxCount, periodMs)) {
slidingWindow.incrementUse(periodMs);
return key;
}
}
return null;
}
private class SlidingWindow {
private int countUses = 1;
private long period = System.currentTimeMillis();
public boolean isValidForUse(int maxCount, long period) {
return isCountValid(maxCount) && isPeriodValid(period);
}
public void incrementUse(long period) {
incrementCount();
incrementPeriod(period);
}
private boolean isCountValid(int maxCount) {
return countUses < maxCount;
}
private boolean isPeriodValid(long periodMs) {
return System.currentTimeMillis() - period <= periodMs;
}
private void incrementCount() {
this.countUses++;
}
private void incrementPeriod(long period) {
this.period = System.currentTimeMillis() + period;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment