Guest User

Beust Challenge: Sliding Window Map

a guest
Sep 4th, 2012
189
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.xsm.beustchallenge.slidingwindowmap;
  2.  
  3. import java.util.Date;
  4. import java.util.Iterator;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7. import java.util.Set;
  8.  
  9. /**
  10.  * Solving for Beust Challenge: Sliding Window Map
  11.  * http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/
  12.  *
  13.  * @author Sony Mathew
  14.  */
  15. public class SlidingWindowMap {
  16.    
  17.     private final Set<String> keys;
  18.     private final int maxCount;
  19.     private final long maxPeriodMs;
  20.    
  21.     private List<KeyTrack> keyTracks = new LinkedList<>();
  22.    
  23.     /**
  24.      * author Sony Mathew
  25.      */
  26.     public SlidingWindowMap(Set<String> keys, int maxCount, long maxPeriodMs) {
  27.         this.keys = keys;
  28.         this.maxCount = maxCount;
  29.         this.maxPeriodMs = maxPeriodMs;
  30.        
  31.         for(String key : this.keys) {
  32.             keyTracks.add(new KeyTrack(key));
  33.         }
  34.     }
  35.  
  36.     /**
  37.      * @return a key that has been used less than `maxCount` times during the
  38.      *         past `maxPeriodMs` milliseconds or null if no such key exists.
  39.      */
  40.     public synchronized String getNextKey() {
  41.         List<KeyTrack> keyTracksUsedUp = new LinkedList<>();
  42.         try {
  43.             Iterator<KeyTrack> keyTrackIter = keyTracks.iterator();
  44.             while(keyTrackIter.hasNext()) {
  45.                 KeyTrack keyTrack = keyTrackIter.next();
  46.                 String key = keyTrack.useKey();
  47.                 if (key != null) {                                         
  48.                     return key;
  49.                 }else{
  50.                     keyTrackIter.remove();
  51.                     keyTracksUsedUp.add(keyTrack);
  52.                 }
  53.             }
  54.             return null; //no keys found, all used up.
  55.         }finally{
  56.             //put used-up keys back at the end.
  57.             for(KeyTrack keyTrackUsedUp : keyTracksUsedUp) {
  58.                 keyTracks.add(keyTrackUsedUp);
  59.             }
  60.         }
  61.     }
  62.    
  63.     /**
  64.      * Tracks a key's use.
  65.      *
  66.      * @author Sony Mathew
  67.      */
  68.     class KeyTrack {
  69.         final String key;
  70.         final List<Date> useTimes = new LinkedList<>();
  71.        
  72.         KeyTrack(String key) {
  73.             this.key = key;
  74.         }
  75.        
  76.         /**
  77.          * @return : key if it can be used, else null.
  78.          * author Sony Mathew
  79.          */
  80.         String useKey() {
  81.             Date now = new Date();
  82.            
  83.             //Remove all old use times.
  84.             Iterator<Date> useTimeIter = useTimes.iterator();
  85.             while (useTimeIter.hasNext()) {
  86.                 Date useTime = useTimeIter.next();
  87.                 long usePeriod = now.getTime()-useTime.getTime();
  88.                 if (usePeriod>maxPeriodMs) {
  89.                     useTimeIter.remove(); //no longer countable, past max period.
  90.                 }
  91.             }
  92.            
  93.             if (useTimes.size() < maxCount) {
  94.                 useTimes.add(now);
  95.                 return key;            
  96.             }
  97.            
  98.             return null;
  99.         }
  100.     }  
  101. }
RAW Paste Data