KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gov > nasa > jpf > search > heuristic > BeamSearch


1 //
2 // Copyright (C) 2005 United States Government as represented by the
3 // Administrator of the National Aeronautics and Space Administration
4 // (NASA). All Rights Reserved.
5 //
6 // This software is distributed under the NASA Open Source Agreement
7 // (NOSA), version 1.3. The NOSA has been approved by the Open Source
8 // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
9 // directory tree for the complete NOSA document.
10 //
11 // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
12 // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
13 // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
14 // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
15 // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
16 // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
17 // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
18 //
19 package gov.nasa.jpf.search.heuristic;
20
21 import gov.nasa.jpf.Config;
22 import gov.nasa.jpf.VM;
23
24 import java.util.TreeSet JavaDoc;
25
26
27 /**
28  * A BeamSearch is a HeuristicSearch with a state queue that is reset at each
29  * search level (i.e. it doesn't hop between search levels whe fetching the
30  * next state from the queue)
31  */
32 public class BeamSearch extends HeuristicSearch {
33   private TreeSet JavaDoc parents;
34
35   public BeamSearch (Config config, VM vm) throws Config.Exception {
36     super(config, vm);
37   }
38
39   public void search () {
40     int maxDepth = getMaxSearchDepth();
41
42     int sid = getStateNumber();
43     h_state = new HeuristicState(sid, initHeuristicValue);
44     heuristic.processParent();
45
46     if (pathCoverage) {
47       h_state.saveCoverage();
48     }
49
50     done = false;
51
52     if (hasPropertyTermination()) {
53       return;
54     }
55
56     generateChildren(maxDepth);
57
58     while ((queue.size() != 0) && !done) {
59       expandChildren(maxDepth);
60     }
61   }
62
63   private void expandChildren (int maxDepth) {
64     // <2do> provide search listener hooks to monitor queue size and expanded states
65
66     parents = (TreeSet JavaDoc) (queue.clone());
67     queue = new TreeSet JavaDoc(parents.comparator()); // 2do - Hmm, is this correct?
68
69     while ((parents.size() != 0) && !done) {
70       expandState();
71       generateChildren(maxDepth);
72     }
73   }
74
75   private void expandState () {
76     int s = parents.size();
77     h_state = (HeuristicState) (parents.first());
78     parents.remove(h_state);
79     vm.restoreState(h_state.getVirtualState());
80     heuristic.processParent();
81   }
82 }
83
Popular Tags