Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement