public
Created

Improved solution for Cedric's sliding window key problem.

  • Download Gist
gistfile1.groovy
Groovy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
// http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/
 
import java.util.concurrent.PriorityBlockingQueue
 
public class SlidingWindowMap
{
def queue
def windowWidthMillis
 
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs)
{
queue = new PriorityBlockingQueue(keys.size() * maxCount, { a, b -> a[0].peek() <=> b[0].peek() } as Comparator)
 
def random = new Random()
 
// Seed the timestamps with random values that are earlier than the beginning of the window could be.
// Since System.currentTimeMillis() is a positive long we can use negative millions safely.
keys.each { key -> maxCount.times { queue.add([-random.nextInt(2**24), key]) } }
 
windowWidthMillis = 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()
{
// Get the key that was used first.
def keyrec = queue.poll()
 
if (keyrec) {
// Can we use it again?
if (keyrec[0] < System.currentTimeMillis() - windowWidthMillis) {
def key = keyrec[1]
 
queue.add ([System.currentTimeMillis(), key])
 
return key
}
 
// No. Just put it back.
queue.add(keyrec)
}
 
return null
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.