Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 6th, 2012  |  syntax: Java  |  size: 2.48 KB  |  views: 56  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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.                                 }else{
  91.                                         break; //list is in order of oldest to newest, so done.
  92.                                 }
  93.                         }
  94.                        
  95.                         if (useTimes.size() < maxCount) {
  96.                                 useTimes.add(now);
  97.                                 return key;                            
  98.                         }
  99.                        
  100.                         return null;
  101.                 }
  102.         }      
  103. }