1
2
3
4
5
6
7 package net.sf.bddbddb.order;
8
9 import java.util.Arrays;
10 import java.util.Collection;
11 import java.util.Iterator;
12 import java.util.LinkedHashMap;
13 import java.util.LinkedList;
14 import java.util.List;
15 import java.util.Map;
16
17 import net.sf.bddbddb.BDDInferenceRule;
18 import net.sf.bddbddb.FindBestDomainOrder;
19 import net.sf.bddbddb.InferenceRule;
20 import net.sf.bddbddb.Solver;
21
22 import org.jdom.Element;
23
24
25 /***
26 * A collection of trials on the same test. (The same BDD operation.)
27 *
28 * @author John Whaley
29 * @version $Id: EpisodeCollection.java 563 2005-05-24 05:24:11Z joewhaley $
30 */
31 public class EpisodeCollection {
32 /***
33 * Name of the test.
34 */
35 public String name;
36
37 /***
38 * Time of the test.
39 */
40
41
42 public static String RULE_CONST = "rule";
43 public static String SPACER = "_";
44 public static String UPDATE_CONST = "update";
45 public static String OP_CONST = "op";
46 /***
47 * Map from orders to their trial information.
48 */
49 public Map
50
51 List episodes;
52
53 /***
54 * Best trial so far.
55 */
56 TrialInfo best;
57
58 /***
59 * Trial info sorted by cost. Updated automatically when necessary.
60 */
61 transient TrialInfo[] sorted;
62
63 /***
64 * Construct a new collection of trials.
65 */
66 public EpisodeCollection(BDDInferenceRule rule, int opNum) {
67 name = RULE_CONST + rule.id + SPACER + UPDATE_CONST + rule.updateCount + SPACER + OP_CONST + opNum;
68 trials = new LinkedHashMap();
69 sorted = null;
70 episodes = new LinkedList();
71 }
72
73 EpisodeCollection(String n){
74 name = n;
75 trials = new LinkedHashMap();
76 sorted = null;
77 episodes = new LinkedList();
78 }
79
80
81
82
83
84
85 /***
86 * Add the information about a trial to this collection.
87 *
88 * @param i trial info
89 */
90 public void addTrial(TrialInfo i) {
91 if (FindBestDomainOrder.TRACE > 2) FindBestDomainOrder.out.println(this+": Adding trial "+i);
92 trials.put(i.order, i);
93 if (best == null || best.cost > i.cost) {
94 best = i;
95 }
96 sorted = null;
97 }
98
99 /***
100 * Add the information about a trial to this collection.
101 *
102 * @param o order
103 * @param p predicted value for this trial
104 * @param cost cost of operation
105 */
106 public void addTrial(Order o, TrialPrediction p, long cost, long timestamp) {
107 Episode ep = getCurrEpisode();
108 if(ep == null) ep = startNewEpisode(System.currentTimeMillis());
109
110 addTrial(new TrialInfo(o, p, cost, ep, timestamp));
111 }
112
113
114
115 /***
116 * Returns true if this collection contains a trial with the given order,
117 * false otherwise.
118 *
119 * @param o order
120 * @return true if this collection contains it, false otherwise
121 */
122 public boolean contains(Order o) {
123 return trials.containsKey(o);
124 }
125
126 /***
127 * Calculates the standard deviation of a collection of trials.
128 *
129 * @param trials collection of trials
130 * @return variance
131 */
132 public static double getStdDev(Collection trials) {
133 return Math.sqrt(getVariance(trials));
134 }
135
136 /***
137 * @return the standard deviation of the trials
138 */
139 public double getStdDev() {
140 return getStdDev(trials.values());
141 }
142
143 /***
144 * Calculates the variance of a collection of trials.
145 *
146 * @param trials collection of trials
147 * @return variance
148 */
149 public static double getVariance(Collection trials) {
150 double sum = 0.;
151 double sumOfSquares = 0.;
152 int n = 0;
153 for (Iterator i = trials.iterator(); i.hasNext(); ++n) {
154 TrialInfo t = (TrialInfo) i.next();
155 double c = (double) t.cost;
156 sum += c;
157 sumOfSquares += c * c;
158 }
159
160 double variance = (sumOfSquares * n - sum * sum) / (n * n);
161 return variance;
162 }
163
164 /***
165 * @return the variance of the trials
166 */
167 public double getVariance() {
168 return getVariance(trials.values());
169 }
170
171 /***
172 * @return the minimum cost trial
173 */
174 public TrialInfo getMinimum() {
175 return best;
176 }
177
178 /***
179 * @return the maximum cost trial
180 */
181 public TrialInfo getMaximum() {
182 TrialInfo best = null;
183 for (Iterator i = trials.values().iterator(); i.hasNext();) {
184 TrialInfo t = (TrialInfo) i.next();
185 if (best == null || t.cost > best.cost)
186 best = t;
187 }
188 return best;
189 }
190
191 /***
192 * @return the mean of the trials
193 */
194 public long getAverage() {
195 long total = 0;
196 int count = 0;
197 for (Iterator i = trials.values().iterator(); i.hasNext(); ++count) {
198 TrialInfo t = (TrialInfo) i.next();
199 total += t.cost;
200 }
201 if (count == 0) return 0L;
202 else return total / count;
203 }
204
205 /***
206 * @return the trials sorted by increasing cost
207 */
208 public TrialInfo[] getSorted() {
209 if (sorted == null) {
210 sorted = (TrialInfo[]) trials.values().toArray(new TrialInfo[trials.size()]);
211 Arrays.sort(sorted);
212 }
213 return sorted;
214 }
215
216 /***
217 * @return the collection of trials
218 */
219 public Collection getTrials() {
220 return trials.values();
221 }
222
223 /***
224 * @return the number of trials in this collection
225 */
226 public int getNumTrials() {
227 return trials.size();
228 }
229
230
231
232
233 public String toString() {
234 return name;
235
236 }
237
238 /***
239 * Returns this EpisodeCollection as an XML element.
240 *
241 * @return XML element
242 */
243 public Element toXMLElement() {
244 Element dis = new Element("episodeCollection");
245 dis.setAttribute("name", name);
246
247 for(Iterator it = episodes.iterator(); it.hasNext(); ){
248 Episode ep = (Episode) it.next();
249 dis.addContent(ep.toXMLElement());
250 }
251
252 return dis;
253 }
254
255 static InferenceRule parseRule(Solver solver, String s) {
256 int updateIndex = s.indexOf(UPDATE_CONST);
257
258 int ruleNum = -1;
259 if(updateIndex > -1)
260 ruleNum = Integer.parseInt(s.substring(RULE_CONST.length(),updateIndex - 1));
261 else
262 ruleNum = Integer.parseInt(s.substring(RULE_CONST.length()));
263
264 InferenceRule rule = solver.getRule(ruleNum);
265 return rule;
266 }
267
268 static int parseUpdateCount(String s){
269 int updateIndex = s.indexOf(UPDATE_CONST);
270 int opIndex = s.indexOf(OP_CONST);
271 if(opIndex > -1){
272 return Integer.parseInt(s.substring(updateIndex + UPDATE_CONST.length(), opIndex - 1));
273 }else if(updateIndex > -1){
274 return Integer.parseInt(s.substring(updateIndex + UPDATE_CONST.length()));
275 }
276 return -1;
277 }
278
279 static int parseOpNumber(String s){
280 int opIndex = s.indexOf(OP_CONST);
281 if(opIndex > -1)
282 return Integer.parseInt(s.substring(opIndex + OP_CONST.length()));
283 return -1;
284 }
285
286 public InferenceRule getRule(Solver solver) {
287 return parseRule(solver, name);
288 }
289
290 public int getUpdateCount(){ return parseUpdateCount(name); }
291
292 public int getOpNumber(){ return parseOpNumber(name); }
293
294 public static EpisodeCollection fromXMLElement(Element e, Solver solver) {
295 String name = e.getAttributeValue("name");
296 InferenceRule rule = parseRule(solver, name);
297 Map nameToVar = rule.getVarNameMap();
298
299
300
301
302
303
304
305 EpisodeCollection ec = new EpisodeCollection(name);
306
307
308
309 try{
310 long timestamp = Long.parseLong(e.getAttributeValue("timestamp"));
311 Episode ep = ec.startNewEpisode(timestamp);
312 for (Iterator i = e.getContent().iterator(); i.hasNext();) {
313 Object e2 = i.next();
314 if (e2 instanceof Element) {
315 TrialInfo ti = TrialInfo.fromXMLElement((Element) e2, nameToVar, ep);
316 ep.addTrial(ti);
317 }
318 }
319 }catch(IllegalArgumentException ex){
320 ec.episodes.clear();
321 for(Iterator it = e.getContent().iterator(); it.hasNext(); ){
322 Object elem2 = it.next();
323 if(elem2 instanceof Element)
324 episodeFromXMLElement((Element) elem2,nameToVar, ec);
325 }
326 }
327
328 return ec;
329 }
330 public Collection getOrders(){ return trials.keySet(); }
331 public Episode startNewEpisode(long timestamp){
332 Episode ep = new Episode(timestamp);
333 episodes.add(ep);
334 return ep;
335 }
336
337 public Episode getCurrEpisode(){
338 if(episodes.size() == 0) return null;
339 return (Episode) episodes.get(episodes.size() - 1);
340 }
341
342 public static Episode episodeFromXMLElement(Element elem1, Map nameToVar, EpisodeCollection tc){
343
344 long timestamp = Long.parseLong(elem1.getAttributeValue("timestamp"));
345 Episode ep = tc.startNewEpisode(timestamp);
346 for (Iterator i = elem1.getContent().iterator(); i.hasNext();) {
347 Object elem2 = i.next();
348 if (elem2 instanceof Element) {
349 TrialInfo ti = TrialInfo.fromXMLElement((Element) elem2, nameToVar, ep);
350 ep.addTrial(ti);
351 }
352 }
353 return ep;
354 }
355
356
357
358 public class Episode{
359 Map trials;
360 TrialInfo best;
361 long timestamp;
362 public Episode(long timestamp){
363 this.timestamp = timestamp;
364 trials = new LinkedHashMap();
365 }
366 public void addTrial(TrialInfo ti){
367 trials.put(ti.order, ti);
368 if (best == null || best.cost > ti.cost) {
369 best = ti;
370 }
371 EpisodeCollection.this.addTrial(ti);
372 }
373
374 public Element toXMLElement(){
375 Element e = new Element("episode");
376 e.setAttribute("timestamp", Long.toString(timestamp));
377 for (Iterator i = trials.values().iterator(); i.hasNext();) {
378 TrialInfo info = (TrialInfo) i.next();
379 e.addContent(info.toXMLElement());
380 }
381 return e;
382 }
383 public EpisodeCollection getEpisodeCollection(){ return EpisodeCollection.this; }
384 }
385 }