SlidingWindowMap.java

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