View Javadoc

1   /*
2    * Copyright 2006 - 2012 Christina Bohk and Roland Ewald
3    *  
4    * Licensed under the Apache License, Version 2.0 (the "License"); 
5    * you may not use this file except in compliance with the License. 
6    * You may obtain a copy of the License at 
7    *  
8    *  http://www.apache.org/licenses/LICENSE-2.0
9    *  
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
13   * See the License for the specific language governing permissions and 
14   * limitations under the License. 
15   */
16  package p3j.simulation.assignments.exhaustive;
17  
18  import java.util.ArrayList;
19  import java.util.Collections;
20  import java.util.Comparator;
21  import java.util.HashMap;
22  import java.util.HashSet;
23  import java.util.List;
24  import java.util.Map;
25  
26  import p3j.pppm.parameters.ParameterAssignment;
27  import p3j.pppm.parameters.ParameterInstance;
28  import p3j.pppm.sets.Set;
29  import p3j.pppm.sets.SetType;
30  
31  /**
32   * 
33   * Manages all {@link Set} objects for a certain {@link SetType}. It is
34   * responsible to create new parameter assignments for all
35   * {@link ParameterInstance} objects hat are covered by the {@link SetType} of
36   * its {@link Set}. The assignments should have a *decreasing* probability, new
37   * assignments can be triggered by calling {@link SetManager#nextAssignment()},
38   * the current assignment can be retrieved with
39   * {@link SetManager#getCurrentMapping()}. Basically, the set manager conducts a
40   * breadth-first search, guided by the probabilities of the index tuples.
41   * 
42   * Created: August 22, 2008
43   * 
44   * @author Christina Bohk
45   * @author Roland Ewald
46   * 
47   */
48  public class SetManager {
49  
50  	/** The set to be managed. */
51  	private Set set;
52  
53  	/** List of all instances covered by the corresponding {@link SetType}. */
54  	private List<ParameterInstance> instances;
55  
56  	/** List of assumption lists (ordered by probability). */
57  	private List<List<ParameterAssignment>> assumptions = new ArrayList<List<ParameterAssignment>>();
58  
59  	/** The assignment enumerator. */
60  	private AssignmentEnumerator assignmentEnumerator;
61  
62  	/** Reference to the current assignment. */
63  	private Assignment currentAssignment;
64  
65  	/**
66  	 * Default constructor.
67  	 * 
68  	 * @param s
69  	 *          the set to be managed
70  	 * @param setType
71  	 *          the type of the set
72  	 */
73  	public SetManager(Set s, SetType setType) {
74  		set = s;
75  		instances = setType.getDefinedParameters();
76  		List<Integer> maxProbCombination = new ArrayList<Integer>();
77  		for (ParameterInstance instance : instances) {
78  			List<ParameterAssignment> assignments = new ArrayList<ParameterAssignment>(
79  			    set.getParameterAssignments(instance).getAssignments());
80  
81  			// Sort assignments in decreasing order
82  			Collections.sort(assignments, new Comparator<ParameterAssignment>() {
83  				@Override
84  				public int compare(ParameterAssignment a1, ParameterAssignment a2) {
85  					return Double.compare(a2.getProbability(), a1.getProbability());
86  				}
87  			});
88  
89  			assumptions.add(assignments);
90  			maxProbCombination.add(0);
91  		}
92  
93  		// Add first element to assignment queue
94  		assignmentEnumerator = new AssignmentEnumerator(new Assignment(
95  		    maxProbCombination, calcAssignmentProbability(maxProbCombination)));
96  		nextAssignment();
97  	}
98  
99  	/**
100 	 * Calculate probability that current set and the most probable assignment are
101 	 * chosen.
102 	 * 
103 	 * @return the probability of the set, multiplied with the probability of the
104 	 *         currently most probable assignment combination, -1 if there is no
105 	 *         assignment left
106 	 */
107 	protected double calcSetAssignmentProbability() {
108 		if (currentAssignment == null) {
109 			return -1;
110 		}
111 		return set.getProbability() * currentAssignment.getProbability();
112 	}
113 
114 	/**
115 	 * Calculate probability that given assignment is chosen.
116 	 * 
117 	 * @param assumptionIndices
118 	 *          list of indices of the selected assumptions
119 	 * @return the probability of choosing the given assignment combination
120 	 */
121 	private double calcAssignmentProbability(List<Integer> assumptionIndices) {
122 		double prob = 1;
123 		for (int i = 0; i < assumptionIndices.size(); i++) {
124 			Integer index = assumptionIndices.get(i);
125 			if (index >= assumptions.get(i).size()) {
126 				return 0;
127 			}
128 			prob *= assumptions.get(i).get(index).getProbability();
129 		}
130 		return prob;
131 	}
132 
133 	/**
134 	 * Increments a single index to goto the next-probable combination of sets.
135 	 * 
136 	 * @return true, if new assignment could be selected, otherwise false
137 	 */
138 	protected final boolean nextAssignment() {
139 
140 		if (assignmentEnumerator.isEmpty()) {
141 			return false;
142 		}
143 
144 		currentAssignment = assignmentEnumerator.removeMostProbable();
145 		java.util.Set<Assignment> childs = createChildAssignments(currentAssignment);
146 		assignmentEnumerator.add(childs);
147 		return true;
148 	}
149 
150 	/**
151 	 * Generates children of given assignment.
152 	 * 
153 	 * @param assignment
154 	 *          the assignment for which the children shall be generated
155 	 * @return set of all children assignments
156 	 */
157 	private java.util.Set<Assignment> createChildAssignments(Assignment assignment) {
158 		java.util.Set<Assignment> childs = new HashSet<Assignment>();
159 		final List<Integer> indices = assignment.getAssignmentIndices();
160 		for (int i = 0; i < instances.size(); i++) {
161 			int currentIndex = indices.get(i);
162 			if (currentIndex >= assumptions.get(i).size() - 1) {
163 				continue;
164 			}
165 			List<Integer> childIndices = new ArrayList<Integer>(indices);
166 			childIndices.set(i, currentIndex + 1);
167 			childs.add(new Assignment(childIndices,
168 			    calcAssignmentProbability(childIndices)));
169 		}
170 		return childs;
171 	}
172 
173 	/**
174 	 * Get probability of <i>next</i> assignment combination.
175 	 * 
176 	 * @return probability of next assignment combination
177 	 */
178 	protected double getNextAssignmentProb() {
179 		return assignmentEnumerator.getMostProbable().getProbability();
180 	}
181 
182 	/**
183 	 * Gets the current assignment probability.
184 	 * 
185 	 * @return the current assignment probability
186 	 */
187 	protected double getCurrentAssignmentProb() {
188 		return currentAssignment.getProbability();
189 	}
190 
191 	/**
192 	 * Creates mapping from all {@link ParameterInstance} objects covered by the
193 	 * {@link SetType} of the managed {@link Set} to the currently selected
194 	 * {@link ParameterAssignment} instances.
195 	 * 
196 	 * @return the mapping instance -> assignment
197 	 */
198 	protected Map<ParameterInstance, ParameterAssignment> getCurrentMapping() {
199 		Map<ParameterInstance, ParameterAssignment> mapping = new HashMap<ParameterInstance, ParameterAssignment>();
200 		List<Integer> assumptionIndices = currentAssignment.getAssignmentIndices();
201 		for (int i = 0; i < instances.size(); i++) {
202 			mapping.put(instances.get(i),
203 			    assumptions.get(i).get(assumptionIndices.get(i)));
204 		}
205 		return mapping;
206 	}
207 }