Source code: infranet/RangeDictionary.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 import java.io.*;
25
26 public class RangeDictionary implements Dictionary {
27
28 private static Vector urlTable;
29 private static Map pathMap;
30
31 private static boolean initialized = false;
32 private static final String END = "END";
33 private static final String ROOT = "ROOT";
34 private static final String POST = "POST";
35 private static final String BIND = "BIND";
36
37 private static final int SPLIT_NUM = 30;
38
39 public static void initCdf(String cdfFile, String symbolFile) throws FileNotFoundException, IOException {
40 Cdf.init(cdfFile, symbolFile);
41 }
42
43 public static void initUrl(Collection urls) {
44 if (!initialized) {
45 urlTable = new Vector(urls);
46 pathMap = new HashMap();
47
48 Iterator i = urlTable.iterator();
49 for(int c = 0; i.hasNext(); ++c) {
50 pathMap.put(i.next(), new Integer(c));
51 }
52 initialized = true;
53 }
54 }
55
56 private static class SplitPoint {
57 public String path, symbol;
58 public SplitPoint(String p, String s) {
59 path = p; symbol = s;
60 }
61 }
62
63 private Cdf cdf;
64 private String top, bottom, endPath, postPath, url;
65 private SplitPoint[] split;
66 private boolean isDone, isPost, pathMapSent;
67
68 public RangeDictionary() {
69 clear();
70 cdf = new Cdf();
71 pathMapSent = false;
72 }
73
74 public void clear() {
75 bottom = "";
76 top = UniformCdf.HIGHEST_STRING;
77 isDone = isPost = false;
78 url = "";
79 }
80
81 public void addGuesses(Collection c) {
82 cdf.addGuesses(c);
83 }
84
85 public boolean setUpstream(String path) {
86 if (path.equals(endPath)) {
87 return isDone = true;
88 }
89
90 if (path.equals(postPath)) {
91 url = bottom;
92 bottom = "";
93 top = UniformCdf.HIGHEST_STRING;
94 return isPost = true;
95 }
96
97 boolean success = false;
98 for(int i = 0; i < split.length; ++i) {
99 if (path.equals(split[i].path)) {
100 success = true;
101 bottom = split[i].symbol;
102 if (i != split.length - 1) {
103 top = split[i+1].symbol;
104 }
105 }
106 }
107 System.out.println(bottom + " - " + top);
108 return success;
109 }
110
111 public boolean isDone() {
112 return isDone;
113 }
114
115 public Object getMessage() {
116 if (isPost) {
117 return new Request(url, bottom);
118 }
119 return new Request(bottom);
120 }
121
122 public String getDownstream() {
123 StringBuffer total = new StringBuffer();
124
125 if (!pathMapSent) {
126 pathMapSent = true;
127 Iterator i = pathMap.entrySet().iterator();
128 while (i.hasNext()) {
129 Map.Entry e = (Map.Entry)i.next();
130 total.append(BIND+" "+e.getKey()+" "+e.getValue()+"\n");
131 }
132 }
133 Vector urls = new Vector(urlTable);
134
135 endPath = (String)Util.extractRandom(urls);
136 total.append(""+pathMap.get(endPath)+" "+END+"\n");
137 if (!isPost) {
138 postPath = (String)Util.extractRandom(urls);
139 total.append("" + pathMap.get(postPath) + " " + POST + "\n");
140 }
141 else {
142 postPath = null;
143 }
144
145 String[] symbols = isPost
146 ? cdf.uniformSplit(bottom, top, SPLIT_NUM)
147 : cdf.split(bottom, top, SPLIT_NUM);
148 Collection set = new Vector();
149 Object prev = null;
150 for(int i = 0; i < symbols.length; ++i) {
151 if (!symbols[i].equals(prev)) set.add(symbols[i]);
152 prev = symbols[i];
153 }
154 String root = maxSubString(set);
155 if (root.length() > 0) total.append("ROOT" + " " + root + "\n");
156 split = new SplitPoint[set.size()];
157 Iterator iter = set.iterator();
158 for(int i = 0; i < split.length; ++i) {
159 split[i] = new SplitPoint((String)Util.extractRandom(urls),
160 ((String)iter.next()));
161 total.append(pathMap.get(split[i].path));
162 total.append(' ');
163 total.append(split[i].symbol.substring(root.length()));
164 total.append('\n');
165 }
166 return total.toString();
167 }
168
169 private static String maxSubString(Collection c) {
170 Iterator i = c.iterator();
171 String cmp = (String)i.next();
172 int index = cmp.length();
173 while (i.hasNext()) {
174 String s = (String)i.next();
175 for (int j = 0; j < index; ++j) {
176 if (s.charAt(j) != cmp.charAt(j)) {
177 index = j;
178 break;
179 }
180 }
181 }
182 return cmp.substring(0, index);
183 }
184
185 public boolean timeToUpdate() {
186 return true;
187 }
188 }
189