Created
September 5, 2012 04:14
-
-
Save jxerome/3630300 to your computer and use it in GitHub Desktop.
Beust Challenge - Sliding window map
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.mainaud.slidingwindow; | |
import java.util.Set; | |
public class SlidingWindowMap { | |
private long periodMs; | |
private SlidingWindow[] keyWindow; | |
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) { | |
keyWindow = new SlidingWindow[keys.size()]; | |
int i = 0; | |
for (String key : keys) { | |
keyWindow[i++] = new SlidingWindow(key, maxCount); | |
} | |
} | |
public String getNextKey() { | |
String key = null; | |
// Change i initialization to change key usage distribution | |
for (int i = 0; key == null && i < keyWindow.length; ++i) { | |
key = keyWindow[i].getKey(periodMs); | |
} | |
return key; | |
} | |
/* | |
* Keep the last maxCount usage timestamp and test the oldest one. Use an array as a round buffer because it is easy an | |
* efficient. | |
*/ | |
private static class SlidingWindow { | |
private final String key; | |
private final long[] timestamp; | |
private int next; | |
SlidingWindow(String key, int maxCount) { | |
this.key = key; | |
this.timestamp = new long[maxCount]; | |
/* | |
* works when periodMs < currentTimestamp. if paranoid uncomment next line: | |
*/ | |
// java.util.Arrays.fill(timestamp, Long.MIN_VALUE); | |
} | |
synchronized String getKey(long periodMs) { | |
long now = System.currentTimeMillis(); | |
if (now > timestamp[next] + periodMs) { | |
timestamp[next] = now; | |
next = (next + 1) % timestamp.length; | |
return key; | |
} else { | |
return null; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Many thanks for this, it's really helpful. However, what does 'String key' represent (e.g. line 31)? I can't work it out from your code?