This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

SlidingWindow

By: a guest on Sep 2nd, 2012  |  syntax: Java  |  size: 4.05 KB  |  views: 426  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Iterator;
  4. import java.util.List;
  5. import java.util.Map;
  6. import java.util.Set;
  7.  
  8. public class SlidingWindowMap {
  9.  
  10.     private final Map<String, SlidingWindow> keyToSlidingWindow = new HashMap<String, SlidingWindow>();
  11.     private final int maxCount;
  12.     private final long periodMs;
  13.  
  14.     public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) {
  15.         if(maxCount<=0) {
  16.             throw new IllegalArgumentException("Max count must be strictly greater than zero.");
  17.         }
  18.         if(periodMs<=0) {
  19.             throw new IllegalArgumentException("PeriodMs must be strictly greater than zero.");
  20.         }
  21.         this.maxCount = maxCount;
  22.         this.periodMs = periodMs;
  23.         for (String key : keys) {
  24.             keyToSlidingWindow.put(key, new SlidingWindow());
  25.         }
  26.     }
  27.  
  28.     public void keyPressed(String key) {
  29.         final SlidingWindow slidingWindow = keyToSlidingWindow.get(key);
  30.        
  31.         if(slidingWindow==null) {
  32.             throw new IllegalArgumentException(String.format("Unsupported key - %s", key));            
  33.         }
  34.        
  35.         final long now = System.currentTimeMillis();
  36.        
  37.         synchronized (slidingWindow.timeStamp) {
  38.             if(slidingWindow.timeStamp==null) {
  39.                 slidingWindow.timeStamp = new ArrayList<Long>();
  40.             }
  41.             slidingWindow.timeStamp.add(now);
  42.             cleanUpWindow(slidingWindow.timeStamp, now);
  43.         }
  44.     }
  45.    
  46.     /**
  47.      * @return a key that has been used less than `maxCount` times during the
  48.      * past `periodMs` milliseconds or null if no such key exists.
  49.      */
  50.     public String getNextKey() {
  51.         String nextKey=null;
  52.         String key;
  53.         SlidingWindow window;
  54.         int minKeyPresses=0;
  55.         int keyPressesInsideWindow;
  56.         boolean firstEntry = true;
  57.        
  58.         for (Iterator<String> iterator = keyToSlidingWindow.keySet().iterator(); iterator.hasNext();) {
  59.             key = iterator.next();
  60.             window = keyToSlidingWindow.get(key);
  61.             if(window==null || window.timeStamp==null || window.timeStamp.isEmpty()) {
  62.                 continue;
  63.             }
  64.             keyPressesInsideWindow = keyPressesForWindow(window);
  65.             if(keyPressesInsideWindow<=maxCount) {
  66.                 if(firstEntry) {
  67.                     firstEntry=false;
  68.                     minKeyPresses = keyPressesInsideWindow;
  69.                     nextKey = key;
  70.                 } else if(keyPressesInsideWindow<minKeyPresses) {
  71.                     minKeyPresses = keyPressesInsideWindow;
  72.                     nextKey = key;
  73.                 }
  74.             }
  75.         }
  76.        
  77.         return nextKey;
  78.     }
  79.    
  80.     /**
  81.      * this cleanup of the sliding window for the current key is done here, but could be done by a
  82.      * background thread. The idea is to prevent the windows from growing 'too' large
  83.      */
  84.     private void cleanUpWindow(List<Long> timeStamps, long now ) {
  85.         final long beginningOfWindow = now - periodMs;
  86.         for (Iterator<Long> iterator = timeStamps.iterator(); iterator.hasNext();) {
  87.             if(iterator.next()<beginningOfWindow) {
  88.                 iterator.remove();
  89.             }
  90.         }        
  91.     }
  92.    
  93.     private int keyPressesForWindow(SlidingWindow window) {
  94.         final long now = System.currentTimeMillis();
  95.         final long beginningOfWindow = now - periodMs;
  96.         int keyPressesInsideWindow = 0;
  97.         // iterate from most recent to least recently used
  98.         synchronized (window.timeStamp) {
  99.             for (int i = window.timeStamp.size()-1; i >= 0; i--) {
  100.                 if(window.timeStamp.get(i)>=beginningOfWindow) {
  101.                     ++keyPressesInsideWindow;
  102.                 }
  103.                 if(keyPressesInsideWindow>maxCount) {
  104.                     break;
  105.                 }
  106.             }
  107.         }
  108.         return keyPressesInsideWindow;
  109.     }
  110.  
  111.     private static class SlidingWindow {
  112.         List<Long> timeStamp;
  113.     }
  114. }
clone this paste RAW Paste Data