Source code: infranet/UserCache.java
1 /* Copyright (c) 2003, Massachusetts Institute of Technology
2 * All rights reserved.
3 *
4 * Permission to use, copy, modify and distribute this software and its
5 * documentation for any purpose, without fee, and without written agreement is
6 * hereby granted, provided that the above copyright notice and the following
7 * paragraph appears in all copies of this software.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
10 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
11 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
12 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
13 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
14 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
15 * IN THE SOFTWARE.
16 *
17 * Author: Winston Wang
18 *
19 */
20
21 package infranet;
22
23 import java.util.*;
24
25 public class UserCache {
26 private static final int CACHE_SIZE = 300;
27
28 private LinkedList list;
29 private SortedMap map;
30
31 public UserCache() {
32 list = new LinkedList();
33 map = null;
34 }
35
36 public void add(String s) {
37 list.addFirst(s);
38 map = null;
39 }
40
41 public void addAll(Collection c) {
42 list.addAll(0, c);
43 map = null;
44 }
45
46 private SortedMap tempMap;
47
48 public double cdf(String s) {
49 if (map == null) makeMap();
50
51 tempMap = map.tailMap(s);
52 if (tempMap.isEmpty()) return 1;
53
54 return ((Double)tempMap.values().iterator().next()).doubleValue();
55 }
56
57 public String bound() {
58 if (tempMap.isEmpty()) return UniformCdf.HIGHEST_STRING;
59 return (String)tempMap.firstKey();
60 }
61
62 private void makeMap() {
63 SortedSet set = new TreeSet();
64 int total = 0;
65 for(Iterator i = list.iterator(); i.hasNext() && set.size() < CACHE_SIZE; ++total) {
66 set.add(i.next());
67 }
68 for(int i = total; i < list.size(); ++i) {
69 list.removeLast();
70 }
71
72 map = new TreeMap();
73 Iterator i = set.iterator();
74 for(int count = 0; i.hasNext(); ++count) {
75 map.put(i.next(), new Double(count / (double)total));
76 }
77 }
78 }