Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Copyright (c) 2011, Datacard Group, Minnetonka, MN. Do NOT copy or include without permission!
- */
- 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.
- }
- }
- if (useTimes.size() < maxCount) {
- useTimes.add(now);
- return key;
- }
- return null;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement