SHOW:
|
|
- or go back to the newest paste.
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 | } |