SlidingWindow

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;
    }
}