package com.xsm.beustchallenge.slidingwindowmap;

import java.util.Date;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Solving for Beust Challenge: Sliding Window Map
 * http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/
 *
 * @author Sony Mathew
 */
public class SlidingWindowMap {

    private final Set<String> keys;
    private final int maxCount;
    private final long maxPeriodMs;

    private List<KeyTrack> keyTracks = new LinkedList<>();

    /**
     * author Sony Mathew
     */
    public SlidingWindowMap(Set<String> keys, int maxCount, long maxPeriodMs) {
        this.keys = keys;
        this.maxCount = maxCount;
        this.maxPeriodMs = maxPeriodMs;

        for(String key : this.keys) {
            keyTracks.add(new KeyTrack(key));
        }
    }

    /**
     * @return a key that has been used less than `maxCount` times during the
     *         past `maxPeriodMs` milliseconds or null if no such key exists.
     */
    public synchronized String getNextKey() {
        List<KeyTrack> keyTracksUsedUp = new LinkedList<>();
        try {
            Iterator<KeyTrack> keyTrackIter = keyTracks.iterator();
            while(keyTrackIter.hasNext()) {
                KeyTrack keyTrack = keyTrackIter.next();
                String key = keyTrack.useKey();
                if (key != null) {
                    return key;
                }else{
                    keyTrackIter.remove();
                    keyTracksUsedUp.add(keyTrack);
                }
            }
            return null; //no keys found, all used up.
        }finally{
            //put used-up keys back at the end.
            for(KeyTrack keyTrackUsedUp : keyTracksUsedUp) {
                keyTracks.add(keyTrackUsedUp);
            }
        }
    }

    /**
     * Tracks a key's use.
     *
     * @author Sony Mathew
     */
    class KeyTrack {
        final String key;
        final List<Date> useTimes = new LinkedList<>();

        KeyTrack(String key) {
            this.key = key;
        }

        /**
         * @return : key if it can be used, else null.
         * author Sony Mathew
         */
        String useKey() {
            Date now = new Date();

            //Remove all old use times.
            Iterator<Date> useTimeIter = useTimes.iterator();
            while (useTimeIter.hasNext()) {
                Date useTime = useTimeIter.next();
                long usePeriod = now.getTime()-useTime.getTime();
                if (usePeriod>maxPeriodMs) {
                    useTimeIter.remove(); //no longer countable, past max period.
                }else{
                    break; //list is in order of oldest to newest, so done.
                }
            }

            if (useTimes.size() < maxCount) {
                useTimes.add(now);
                return key;
            }

            return null;
        }
    }
}