Changeset 106 for trunk/EventBenchCore/src
- Timestamp:
- 07/05/11 15:18:56 (13 years ago)
- Location:
- trunk/EventBenchCore/src/de/ugoe/cs/eventbench
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/IReplayDecorator.java
r97 r106 3 3 import java.io.Serializable; 4 4 5 /** 6 * <p> 7 * This interface defines the structure of decorators used when writing replay 8 * files. 9 * </p> 10 * 11 * @author Steffen Herbold 12 * @version 1.0 13 */ 5 14 public interface IReplayDecorator extends Serializable { 6 15 16 /** 17 * <p> 18 * Header of the file. Called at the beginning of the writing. 19 * </p> 20 * 21 * @return file header 22 */ 7 23 String getHeader(); 8 24 25 /** 26 * <p> 27 * Footer of the file. Called at the end of the writing. 28 * </p> 29 * 30 * @return file footer 31 */ 9 32 String getFooter(); 10 33 34 /** 35 * <p> 36 * Session Header. Called before each session. 37 * </p> 38 * 39 * @param sessionId 40 * id of the session 41 * @return session header 42 */ 11 43 String getSessionHeader(int sessionId); 12 44 45 /** 46 * <p> 47 * Session Footer. Called after each session. 48 * </p> 49 * 50 * @param sessionId 51 * id of the session 52 * @return session footer 53 */ 13 54 String getSessionFooter(int sessionId); 14 55 } -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/coverage/CoverageCalculator.java
r102 r106 12 12 import de.ugoe.cs.eventbench.models.IStochasticProcess; 13 13 14 /** 15 * <p> 16 * This class calculates various types of sequence coverage. 17 * </p> 18 * 19 * @author Steffen Herbold 20 * @version 1.0 21 */ 14 22 public class CoverageCalculator { 15 23 24 /** 25 * <p> 26 * Stochastic process that is the foundation for probabilistic coverages and 27 * coverages with reference to all possible sequences. 28 * </p> 29 */ 16 30 private final IStochasticProcess process; 31 32 /** 33 * <p> 34 * Sequences for which the coverage is calculated. 35 * </p> 36 */ 17 37 private final Collection<List<? extends Event<?>>> sequences; 38 39 /** 40 * <p> 41 * Length of the subsequences in relation to which the covarage is 42 * calculated. 43 * </p> 44 */ 18 45 private final int length; 19 46 47 /** 48 * <p> 49 * All subsequences of {@link #length} of {@link #sequences}. 50 * </p> 51 */ 20 52 private Collection<List<? extends Event<?>>> containedSubSeqs = null; 53 54 /** 55 * <p> 56 * All subsequences of {@link #length} that can be generated by 57 * {@link #process}. 58 * </p> 59 */ 21 60 private Collection<List<? extends Event<?>>> allPossibleSubSeqs = null; 61 62 /** 63 * <p> 64 * The probabilities of al subsequences of {@link #length} according to 65 * {@link #process}. 66 * </p> 67 */ 22 68 private Map<List<? extends Event<?>>, Double> subSeqWeights = null; 23 24 25 public CoverageCalculator(IStochasticProcess process, Collection<List<? extends Event<?>>> sequences, int length) { 69 70 /** 71 * <p> 72 * Constructor. Creates a new CoverageCalculator for a given stochastic 73 * process and generated sequences. 74 * </p> 75 * 76 * @param process 77 * stochastic process used for coverage calculations; if it is 78 * zero, not all calculations are possible 79 * @param sequences 80 * sequences for which the coverage is calculated; must not be 81 * null. 82 * @param length 83 * length of the subsequences for which the coverage is analyzed; 84 * must be >0 85 */ 86 public CoverageCalculator(IStochasticProcess process, 87 Collection<List<? extends Event<?>>> sequences, int length) { 88 // TODO check parameters 26 89 this.process = process; 27 90 this.sequences = sequences; 28 91 this.length = length; 29 92 } 30 31 93 94 /** 95 * <p> 96 * Calculates the percentage of subsequences of length k that exist occur, 97 * including those that cannot be generated by {@link #process}. 98 * </p> 99 * 100 * @return coverage percentage 101 */ 32 102 public double getCoverageAllNoWeight() { 33 if ( containedSubSeqs==null) {103 if (containedSubSeqs == null) { 34 104 containedSubSeqs = containedSubSequences(sequences, length); 35 105 } 36 return((double) containedSubSeqs.size())/numSequences(process, length); 37 } 38 106 return ((double) containedSubSeqs.size()) 107 / numSequences(process, length); 108 } 109 110 /** 111 * <p> 112 * Calculates the percentage of subsequences of length k that occur and can 113 * generated by {@link #process}. 114 * </p> 115 * 116 * @return coverage percentage 117 */ 39 118 public double getCoveragePossibleNoWeight() { 40 if ( containedSubSeqs==null) {119 if (containedSubSeqs == null) { 41 120 containedSubSeqs = containedSubSequences(sequences, length); 42 121 } 43 if ( allPossibleSubSeqs==null) {122 if (allPossibleSubSeqs == null) { 44 123 allPossibleSubSeqs = process.generateSequences(length); 45 124 } 46 return((double) containedSubSeqs.size())/allPossibleSubSeqs.size(); 47 } 48 125 return ((double) containedSubSeqs.size()) / allPossibleSubSeqs.size(); 126 } 127 128 /** 129 * <p> 130 * Calculates the weight of the subsequences that occur with relation to 131 * {@link #process}, i.e., the mass of the subsequence probability covered 132 * by the subsequences. 133 * </p> 134 * 135 * @return coverage weight 136 */ 49 137 public double getCoveragePossibleWeight() { 50 if ( containedSubSeqs==null) {138 if (containedSubSeqs == null) { 51 139 containedSubSeqs = containedSubSequences(sequences, length); 52 140 } 53 if ( allPossibleSubSeqs==null) {141 if (allPossibleSubSeqs == null) { 54 142 allPossibleSubSeqs = process.generateSequences(length); 55 143 } 56 if ( subSeqWeights==null) {144 if (subSeqWeights == null) { 57 145 subSeqWeights = generateWeights(process, allPossibleSubSeqs); 58 146 } 59 147 double weight = 0.0; 60 for ( List<? extends Event<?>> subSeq : containedSubSeqs) {148 for (List<? extends Event<?>> subSeq : containedSubSeqs) { 61 149 weight += subSeqWeights.get(subSeq); 62 150 } 63 151 return weight; 64 152 } 65 66 private Map<List<? extends Event<?>>, Double> generateWeights(IStochasticProcess process, Collection<List<? extends Event<?>>> sequences) { 153 154 /** 155 * <p> 156 * Calculates the weights for all sequences passed to this function as 157 * defined by the stochastic process and stores them in a {@link Map}. 158 * </p> 159 * 160 * @param process 161 * process used for weight calculation 162 * @param sequences 163 * sequences for which the weights are calculated 164 * @return {@link Map} of weights 165 */ 166 private static Map<List<? extends Event<?>>, Double> generateWeights( 167 IStochasticProcess process, 168 Collection<List<? extends Event<?>>> sequences) { 67 169 Map<List<? extends Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<? extends Event<?>>, Double>(); 68 170 double sum = 0.0; 69 for ( List<? extends Event<?>> sequence : sequences) {171 for (List<? extends Event<?>> sequence : sequences) { 70 172 double prob = 1.0; 71 173 List<Event<?>> context = new LinkedList<Event<?>>(); 72 for ( Event<?> event : sequence) {174 for (Event<?> event : sequence) { 73 175 prob *= process.getProbability(context, event); 74 176 context.add(event); … … 77 179 sum += prob; 78 180 } 79 if( sum<1.0 ) { 80 for( Map.Entry<List<? extends Event<?>>, Double> entry : subSeqWeights.entrySet() ) { 81 entry.setValue(entry.getValue()/sum); 181 if (sum < 1.0) { 182 for (Map.Entry<List<? extends Event<?>>, Double> entry : subSeqWeights 183 .entrySet()) { 184 entry.setValue(entry.getValue() / sum); 82 185 } 83 186 } 84 187 return subSeqWeights; 85 188 } 86 87 private long numSequences(IStochasticProcess process, int length) { 189 190 /** 191 * <p> 192 * Calculates the number of all existing sequences of a given length, 193 * regardless whether they are possible or not. 194 * </p> 195 * 196 * @param process 197 * stochastic process whose symbols are the basis for this 198 * calculation 199 * @param length 200 * lenght of the sequences 201 * @return numStates^length 202 */ 203 private static long numSequences(IStochasticProcess process, int length) { 88 204 return (long) Math.pow(process.getNumStates(), length); 89 205 } 90 91 // O(numSeq*lenSeq) 92 private Set<List<? extends Event<?>>> containedSubSequences(Collection<List<? extends Event<?>>> sequences, int length) { 206 207 /** 208 * <p> 209 * Creates a {@link Set} of all subsequences of a given length that are 210 * contained in a sequence collection. 211 * </p> 212 * 213 * @param sequences 214 * sequences from which the subsequences are extracted 215 * @param length 216 * length of the subsequences 217 * @return {@link Set} of all subsequences 218 */ 219 private static Set<List<? extends Event<?>>> containedSubSequences( 220 Collection<List<? extends Event<?>>> sequences, int length) { 93 221 Set<List<? extends Event<?>>> containedSubSeqs = new LinkedHashSet<List<? extends Event<?>>>(); 94 222 List<Event<?>> subSeq = new LinkedList<Event<?>>(); 95 223 boolean minLengthReached = false; 96 for ( List<? extends Event<?>> sequence : sequences) {97 for ( Event<?> event : sequence) {224 for (List<? extends Event<?>> sequence : sequences) { 225 for (Event<?> event : sequence) { 98 226 subSeq.add(event); 99 if ( !minLengthReached) {100 if ( subSeq.size()==length) {101 minLengthReached =true;227 if (!minLengthReached) { 228 if (subSeq.size() == length) { 229 minLengthReached = true; 102 230 } 103 231 } else { 104 232 subSeq.remove(0); 105 233 } 106 if ( minLengthReached) {107 if ( !containedSubSeqs.contains(subSeq)) {234 if (minLengthReached) { 235 if (!containedSubSeqs.contains(subSeq)) { 108 236 containedSubSeqs.add(new LinkedList<Event<?>>(subSeq)); 109 237 } … … 113 241 return containedSubSeqs; 114 242 } 115 243 116 244 } -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/IncompleteMemory.java
r19 r106 4 4 import java.util.List; 5 5 6 /** 7 * <p> 8 * Implements a round-trip buffered memory of a specified length that can be 9 * used to remember the recent history. Every event that happend longer ago than 10 * the length of the memory is forgotten, hence the memory is incomplete. 11 * </p> 12 * 13 * @author Steffen Herbold 14 * @version 1.0 15 * 16 * @param <T> 17 * Type which is memorized. 18 */ 6 19 public class IncompleteMemory<T> implements IMemory<T> { 7 20 21 /** 22 * <p> 23 * Maximum length of the memory. 24 * </p> 25 */ 8 26 private int length; 9 27 28 /** 29 * <p> 30 * Internal storage of the history. 31 * </p> 32 */ 10 33 private List<T> history; 11 34 35 /** 36 * <p> 37 * Constructor. Creates a new IncompleteMemory. 38 * </p> 39 * 40 * @param length 41 * number of recent events that are remembered 42 */ 12 43 public IncompleteMemory(int length) { 13 44 this.length = length; 14 45 history = new LinkedList<T>(); 15 46 } 16 47 48 /* 49 * (non-Javadoc) 50 * 51 * @see de.ugoe.cs.eventbench.models.IMemory#add(java.lang.Object) 52 */ 17 53 @Override 18 54 public void add(T state) { 19 if ( history.size()==length) {55 if (history.size() == length) { 20 56 history.remove(0); 21 57 } … … 23 59 } 24 60 61 /* 62 * (non-Javadoc) 63 * 64 * @see de.ugoe.cs.eventbench.models.IMemory#getLast(int) 65 */ 25 66 @Override 26 67 public List<T> getLast(int num) { … … 28 69 } 29 70 71 /** 72 * <p> 73 * Returns the current length of the memory. This can be less than 74 * {@link #length}, if the overall history is less than {@link #length}. 75 * </p> 76 * 77 * @return length of the current memory 78 */ 30 79 public int getLength() { 31 80 return history.size(); -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java
r102 r106 6 6 import java.util.LinkedList; 7 7 import java.util.List; 8 import java.util.Set;9 8 10 9 import de.ugoe.cs.util.StringTools; 11 10 12 11 import edu.uci.ics.jung.graph.DelegateTree; 12 import edu.uci.ics.jung.graph.Graph; 13 13 import edu.uci.ics.jung.graph.Tree; 14 14 15 /** 16 * <p> 17 * This class implements a <it>trie</it>, i.e., a tree of sequences that the 18 * occurence of subsequences up to a predefined length. This length is the trie 19 * order. 20 * </p> 21 * 22 * @author Steffen Herbold 23 * 24 * @param <T> 25 * Type of the symbols that are stored in the trie. 26 * 27 * @see TrieNode 28 */ 15 29 public class Trie<T> implements IDotCompatible, Serializable { 16 17 /** 30 31 /** 32 * <p> 18 33 * Id for object serialization. 34 * </p> 19 35 */ 20 36 private static final long serialVersionUID = 1L; 21 37 22 private Set<T> knownSymbols; 23 38 /** 39 * <p> 40 * Collection of all symbols occuring in the trie. 41 * </p> 42 */ 43 private Collection<T> knownSymbols; 44 45 /** 46 * <p> 47 * Reference to the root of the trie. 48 * </p> 49 */ 24 50 private final TrieNode<T> rootNode; 25 51 52 /** 53 * <p> 54 * Contructor. Creates a new Trie. 55 * </p> 56 */ 26 57 public Trie() { 27 58 rootNode = new TrieNode<T>(); 28 59 knownSymbols = new LinkedHashSet<T>(); 29 60 } 30 31 public Set<T> getKnownSymbols() { 61 62 /** 63 * <p> 64 * Returns a collection of all symbols occuring in the trie. 65 * </p> 66 * 67 * @return symbols occuring in the trie 68 */ 69 public Collection<T> getKnownSymbols() { 32 70 return new LinkedHashSet<T>(knownSymbols); 33 71 } 34 35 // trains the current Trie using the given sequence and adds all subsequence of length trieOrder 72 73 /** 74 * <p> 75 * Trains the current trie using the given sequence and adds all subsequence 76 * of length {@code maxOrder}. 77 * </p> 78 * 79 * @param sequence 80 * sequence whose subsequences are added to the trie 81 * @param maxOrder 82 * maximum length of the subsequences added to the trie 83 */ 36 84 public void train(List<T> sequence, int maxOrder) { 37 85 IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder); 38 int i =0;39 for (T currentEvent : sequence) {86 int i = 0; 87 for (T currentEvent : sequence) { 40 88 latestActions.add(currentEvent); 41 89 knownSymbols.add(currentEvent); 42 90 i++; 43 if ( i>=maxOrder) {91 if (i >= maxOrder) { 44 92 add(latestActions.getLast(maxOrder)); 45 93 } 46 94 } 47 95 int sequenceLength = sequence.size(); 48 for( int j=maxOrder-1 ; j>0 ; j-- ) { 49 add(sequence.subList(sequenceLength-j, sequenceLength)); 50 } 51 } 52 53 54 // increases the counters for each symbol in the subsequence 55 public void add(List<T> subsequence) { 56 if( subsequence!=null && !subsequence.isEmpty() ) { 96 for (int j = maxOrder - 1; j > 0; j--) { 97 add(sequence.subList(sequenceLength - j, sequenceLength)); 98 } 99 } 100 101 /** 102 * <p> 103 * Adds a given subsequence to the trie and increases the counters 104 * accordingly. 105 * </p> 106 * 107 * @param subsequence 108 * subsequence whose counters are increased 109 * @see TrieNode#add(List) 110 */ 111 protected void add(List<T> subsequence) { 112 if (subsequence != null && !subsequence.isEmpty()) { 57 113 knownSymbols.addAll(subsequence); 58 subsequence = new LinkedList<T>(subsequence); 114 subsequence = new LinkedList<T>(subsequence); // defensive copy! 59 115 T firstSymbol = subsequence.get(0); 60 116 TrieNode<T> node = getChildCreate(firstSymbol); … … 63 119 } 64 120 65 protected TrieNode<T> getChildCreate(T symbol) { 121 /** 122 * <p> 123 * Returns the child of the root node associated with the given symbol or 124 * creates it if it does not exist yet. 125 * </p> 126 * 127 * @param symbol 128 * symbol whose node is required 129 * @return node associated with the symbol 130 * @see TrieNode#getChildCreate(Object) 131 */ 132 protected TrieNode<T> getChildCreate(T symbol) { 66 133 return rootNode.getChildCreate(symbol); 67 134 } 68 135 136 /** 137 * <p> 138 * Returns the child of the root node associated with the given symbol or 139 * null if it does not exist. 140 * </p> 141 * 142 * @param symbol 143 * symbol whose node is required 144 * @return node associated with the symbol; null if no such node exists 145 * @see TrieNode#getChild(Object) 146 */ 69 147 protected TrieNode<T> getChild(T symbol) { 70 148 return rootNode.getChild(symbol); 71 149 } 72 150 73 // get the count of "sequence" 151 /** 152 * <p> 153 * Returns the number of occurences of the given sequence. 154 * </p> 155 * 156 * @param sequence 157 * sequence whose number of occurences is required 158 * @return number of occurences of the sequence 159 */ 74 160 public int getCount(List<T> sequence) { 75 161 int count = 0; 76 162 TrieNode<T> node = find(sequence); 77 if ( node!=null) {163 if (node != null) { 78 164 count = node.getCount(); 79 165 } 80 166 return count; 81 167 } 82 83 // get the count of "sequence,follower" 168 169 /** 170 * <p> 171 * Returns the number of occurences of the given prefix and a symbol that 172 * follows it.<br> 173 * Convenience function to simplify usage of {@link #getCount(List)}. 174 * </p> 175 * 176 * @param sequence 177 * prefix of the sequence 178 * @param follower 179 * suffix of the sequence 180 * @return number of occurences of the sequence 181 * @see #getCount(List) 182 */ 84 183 public int getCount(List<T> sequence, T follower) { 85 184 List<T> tmpSequence = new LinkedList<T>(sequence); 86 185 tmpSequence.add(follower); 87 186 return getCount(tmpSequence); 88 89 } 90 187 188 } 189 190 /** 191 * <p> 192 * Searches the trie for a given sequence and returns the node associated 193 * with the sequence or null if no such node is found. 194 * </p> 195 * 196 * @param sequence 197 * sequence that is searched for 198 * @return node associated with the sequence 199 * @see TrieNode#find(List) 200 */ 91 201 public TrieNode<T> find(List<T> sequence) { 92 if ( sequence==null || sequence.isEmpty()) {202 if (sequence == null || sequence.isEmpty()) { 93 203 return rootNode; 94 204 } … … 96 206 TrieNode<T> result = null; 97 207 TrieNode<T> node = getChild(sequenceCopy.get(0)); 98 if ( node!=null) {208 if (node != null) { 99 209 sequenceCopy.remove(0); 100 210 result = node.find(sequenceCopy); … … 102 212 return result; 103 213 } 104 105 // returns all symbols that follow the defined sequence 214 215 /** 216 * <p> 217 * Returns a collection of all symbols that follow a given sequence in the 218 * trie. In case the sequence is not found or no symbols follow the sequence 219 * the result will be empty. 220 * </p> 221 * 222 * @param sequence 223 * sequence whose followers are returned 224 * @return symbols following the given sequence 225 * @see TrieNode#getFollowingSymbols() 226 */ 106 227 public Collection<T> getFollowingSymbols(List<T> sequence) { 107 228 Collection<T> result = new LinkedList<T>(); 108 229 TrieNode<T> node = find(sequence); 109 if ( node!=null) {230 if (node != null) { 110 231 result = node.getFollowingSymbols(); 111 232 } 112 233 return result; 113 234 } 114 115 // longest suffix of context, that is contained in the tree and whose children are leaves 116 // possibly already deprecated 235 236 /** 237 * <p> 238 * Returns the longest suffix of the given context that is contained in the 239 * tree and whose children are leaves. 240 * </p> 241 * 242 * @param context 243 * context whose suffix is searched for 244 * @return longest suffix of the context 245 */ 117 246 public List<T> getContextSuffix(List<T> context) { 118 247 List<T> contextSuffix = new LinkedList<T>(context); // defensive copy 119 248 boolean suffixFound = false; 120 121 while (!suffixFound) {122 if ( contextSuffix.isEmpty()) {249 250 while (!suffixFound) { 251 if (contextSuffix.isEmpty()) { 123 252 suffixFound = true; // suffix is the empty word 124 253 } else { 125 254 TrieNode<T> node = find(contextSuffix); 126 if ( node!=null) {127 if ( !node.getFollowingSymbols().isEmpty()) {255 if (node != null) { 256 if (!node.getFollowingSymbols().isEmpty()) { 128 257 suffixFound = true; 129 258 } 130 259 } 131 if ( !suffixFound) {260 if (!suffixFound) { 132 261 contextSuffix.remove(0); 133 262 } 134 263 } 135 264 } 136 265 137 266 return contextSuffix; 138 267 } 139 140 141 static public class Edge{} 142 268 269 /** 270 * <p> 271 * Helper class for graph visualization of a trie. 272 * </p> 273 * 274 * @author Steffen Herbold 275 * @version 1.0 276 */ 277 static public class Edge { 278 } 279 280 /** 281 * <p> 282 * Helper class for graph visualization of a trie. 283 * </p> 284 * 285 * @author Steffen Herbold 286 * @version 1.0 287 */ 143 288 static public class TrieVertex { 289 290 /** 291 * <p> 292 * Id of the vertex. 293 * </p> 294 */ 144 295 private String id; 296 297 /** 298 * <p> 299 * Contructor. Creates a new TrieVertex. 300 * </p> 301 * 302 * @param id 303 * id of the vertex 304 */ 145 305 protected TrieVertex(String id) { 146 306 this.id = id; 147 307 } 308 309 /** 310 * <p> 311 * Returns the id of the vertex. 312 * </p> 313 * 314 * @see java.lang.Object#toString() 315 */ 316 @Override 148 317 public String toString() { 149 318 return id; 150 319 } 151 320 } 152 321 322 /** 323 * <p> 324 * Returns a {@link Graph} representation of the trie. 325 * </p> 326 * 327 * @return {@link Graph} representation of the trie 328 */ 153 329 protected Tree<TrieVertex, Edge> getGraph() { 154 330 DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>(); … … 156 332 return graph; 157 333 } 158 334 335 /* 336 * (non-Javadoc) 337 * 338 * @see de.ugoe.cs.eventbench.models.IDotCompatible#getDotRepresentation() 339 */ 159 340 public String getDotRepresentation() { 160 341 StringBuilder stringBuilder = new StringBuilder(); … … 164 345 return stringBuilder.toString(); 165 346 } 166 347 348 /** 349 * <p> 350 * Returns the string representation of the root node. 351 * </p> 352 * 353 * @see TrieNode#toString() 354 * @see java.lang.Object#toString() 355 */ 167 356 @Override 168 357 public String toString() { 169 358 return rootNode.toString(); 170 359 } 171 360 361 /** 362 * <p> 363 * Returns the number of symbols contained in the trie. 364 * </p> 365 * 366 * @return 367 */ 172 368 public int getNumSymbols() { 173 369 return knownSymbols.size(); -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java
r102 r106 11 11 import de.ugoe.cs.util.StringTools; 12 12 import edu.uci.ics.jung.graph.DelegateTree; 13 14 13 import edu.uci.ics.jung.graph.Tree; 14 15 /** 16 * <p> 17 * This class implements a node of a trie. Each node is associated with a symbol 18 * and has a counter. The counter marks the number of occurences of the sequence 19 * defined by the path from the root of the trie to this node. 20 * </p> 21 * 22 * @author Steffen Herbold 23 * 24 * @param <T> 25 * Type of the symbols that are stored in the trie. 26 * @see Trie 27 */ 15 28 class TrieNode<T> implements Serializable { 16 17 /** 29 30 /** 31 * <p> 18 32 * Id for object serialization. 33 * </p> 19 34 */ 20 35 private static final long serialVersionUID = 1L; 21 36 37 /** 38 * <p> 39 * Counter for the number of occurences of the sequence. 40 * </p> 41 */ 22 42 private int count; 43 44 /** 45 * <p> 46 * Symbol associated with the node. 47 * </p> 48 */ 23 49 private final T symbol; 24 50 51 /** 52 * <p> 53 * Child nodes of this node. If the node is a leaf this collection is empty. 54 * </p> 55 */ 25 56 private Collection<TrieNode<T>> children; 26 57 58 /** 59 * <p> 60 * Constructor. Creates a new TrieNode without a symbol associated.<br> 61 * <b>This constructor should only be used to create the root node of the 62 * trie!</b> 63 * </p> 64 */ 27 65 TrieNode() { 28 66 this.symbol = null; … … 30 68 children = new LinkedList<TrieNode<T>>(); 31 69 } 32 70 71 /** 72 * <p> 73 * Constructor. Creates a new TrieNode. The symbol must not be null. 74 * </p> 75 * 76 * @param symbol 77 * symbol associated with the trie node 78 */ 33 79 public TrieNode(T symbol) { 34 if( symbol==null ) { 35 throw new InvalidParameterException("symbol must not be null. null is reserved for root node!"); 80 if (symbol == null) { 81 throw new InvalidParameterException( 82 "symbol must not be null. null is reserved for root node!"); 36 83 } 37 84 this.symbol = symbol; … … 40 87 } 41 88 89 /** 90 * <p> 91 * Adds a given subsequence to the trie and increases the counters 92 * accordingly. 93 * </p> 94 * 95 * @param subsequence 96 * subsequence whose counters are increased 97 * @see Trie#add(List) 98 */ 42 99 public void add(List<T> subsequence) { 43 if( !subsequence.isEmpty() ) { 44 if( !symbol.equals(subsequence.get(0)) ) { // should be guaranteed by the recursion/TrieRoot! 100 if (!subsequence.isEmpty()) { 101 if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by 102 // the 103 // recursion/TrieRoot! 45 104 throw new AssertionError("Invalid trie operation!"); 46 105 } 47 106 count++; 48 107 subsequence.remove(0); 49 if ( !subsequence.isEmpty()) {108 if (!subsequence.isEmpty()) { 50 109 T nextSymbol = subsequence.get(0); 51 110 getChildCreate(nextSymbol).add(subsequence); … … 53 112 } 54 113 } 55 114 115 /** 116 * <p> 117 * Returns the symbol associated with the node. 118 * </p> 119 * 120 * @return symbol associated with the node 121 */ 56 122 public T getSymbol() { 57 123 return symbol; 58 124 } 59 125 126 /** 127 * <p> 128 * Returns the number of occurences of the sequence represented by the node. 129 * </p> 130 * 131 * @return number of occurences of the sequence represented by the node 132 */ 60 133 public int getCount() { 61 134 return count; 62 135 } 63 64 protected TrieNode<T> getChildCreate(T symbol) { 136 137 /** 138 * <p> 139 * Returns the child of the node associated with the given symbol or creates 140 * it if it does not exist yet. 141 * </p> 142 * 143 * @param symbol 144 * symbol whose node is required 145 * @return node associated with the symbol 146 * @see Trie#getChildCreate(Object) 147 */ 148 protected TrieNode<T> getChildCreate(T symbol) { 65 149 TrieNode<T> node = getChild(symbol); 66 if ( node==null) {150 if (node == null) { 67 151 node = new TrieNode<T>(symbol); 68 152 children.add(node); … … 70 154 return node; 71 155 } 72 156 157 /** 158 * <p> 159 * Returns the child of the node associated with the given symbol or null if 160 * it does not exist. 161 * </p> 162 * 163 * @param symbol 164 * symbol whose node is required 165 * @return node associated with the symbol; null if no such node exists 166 * @see Trie#getChild(Object) 167 */ 73 168 protected TrieNode<T> getChild(T symbol) { 74 for ( TrieNode<T> child : children) {75 if ( child.getSymbol().equals(symbol)) {169 for (TrieNode<T> child : children) { 170 if (child.getSymbol().equals(symbol)) { 76 171 return child; 77 172 } … … 79 174 return null; 80 175 } 81 82 83 176 177 /** 178 * <p> 179 * Searches the sub-trie of this trie node for a given sequence and returns 180 * the node associated with the sequence or null if no such node is found. 181 * </p> 182 * 183 * @param sequence 184 * sequence that is searched for 185 * @return node associated with the sequence 186 * @see Trie#find(List) 187 */ 84 188 public TrieNode<T> find(List<T> subsequence) { 85 189 TrieNode<T> result = null; 86 if ( subsequence.isEmpty()) {190 if (subsequence.isEmpty()) { 87 191 result = this; 88 192 } else { 89 193 TrieNode<T> node = getChild(subsequence.get(0)); 90 if ( node!=null) {194 if (node != null) { 91 195 subsequence.remove(0); 92 196 result = node.find(subsequence); … … 95 199 return result; 96 200 } 97 98 // returns all symbols that follow this node 201 202 /** 203 * <p> 204 * Returns a collection of all symbols that follow a this node, i.e., the 205 * symbols associated with the children of this node. 206 * </p> 207 * 208 * @return symbols follow this node 209 * @see TrieNode#getFollowingSymbols() 210 */ 99 211 public Collection<T> getFollowingSymbols() { 100 212 Collection<T> followingSymbols = new LinkedList<T>(); 101 for ( TrieNode<T> child : children) {213 for (TrieNode<T> child : children) { 102 214 followingSymbols.add(child.getSymbol()); 103 215 } 104 216 return followingSymbols; 105 217 } 106 218 219 /** 220 * <p> 221 * The string representation of a node is {@code symbol.toString()#count} 222 * </p> 223 * 224 * @see java.lang.Object#toString() 225 */ 107 226 @Override 108 227 public String toString() { 109 String str = symbol.toString() +" #"+count;110 if ( !children.isEmpty()) {228 String str = symbol.toString() + " #" + count; 229 if (!children.isEmpty()) { 111 230 str += StringTools.ENDLINE + children.toString(); 112 231 } 113 return str; 114 } 115 116 public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) { 232 return str; 233 } 234 235 /** 236 * <p> 237 * Generates a {@link Tree} represenation of the trie. 238 * </p> 239 * 240 * @param parent 241 * parent vertex in the generated tree 242 * @param graph 243 * complete tree 244 */ 245 void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) { 117 246 TrieVertex currentVertex; 118 if ( symbol==null ){247 if (symbol == null) { 119 248 currentVertex = new TrieVertex("root"); 120 249 graph.addVertex(currentVertex); 121 250 } else { 122 currentVertex = new TrieVertex(getSymbol().toString()+"#"+getCount()); 123 graph.addChild( new Edge() , parent, currentVertex ); 124 } 125 for( TrieNode<T> node : children ) { 251 currentVertex = new TrieVertex(getSymbol().toString() + "#" 252 + getCount()); 253 graph.addChild(new Edge(), parent, currentVertex); 254 } 255 for (TrieNode<T> node : children) { 126 256 node.getGraph(currentVertex, graph); 127 } 128 } 129 257 } 258 } 259 260 /** 261 * <p> 262 * Appends the current node to the dot representation of the trie. 263 * </p> 264 * 265 * @param stringBuilder 266 * {@link StringBuilder} to which the dot representation is 267 * appended 268 */ 130 269 void appendDotRepresentation(StringBuilder stringBuilder) { 131 270 String thisSaneId; 132 if ( symbol==null) {271 if (symbol == null) { 133 272 thisSaneId = "root"; 134 273 } else { 135 thisSaneId = symbol.toString().replace("\"", "\\\"").replaceAll("[\r\n]","")+"#"+count; 136 } 137 stringBuilder.append(" " + hashCode() + " [label=\""+thisSaneId+"\"];" + StringTools.ENDLINE); 138 for( TrieNode<T> childNode : children ) { 139 stringBuilder.append(" "+hashCode()+" -> " + childNode.hashCode() + ";" + StringTools.ENDLINE); 140 } 141 for( TrieNode<T> childNode : children ) { 274 thisSaneId = symbol.toString().replace("\"", "\\\"") 275 .replaceAll("[\r\n]", "") 276 + "#" + count; 277 } 278 stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId 279 + "\"];" + StringTools.ENDLINE); 280 for (TrieNode<T> childNode : children) { 281 stringBuilder.append(" " + hashCode() + " -> " 282 + childNode.hashCode() + ";" + StringTools.ENDLINE); 283 } 284 for (TrieNode<T> childNode : children) { 142 285 childNode.appendDotRepresentation(stringBuilder); 143 286 }
Note: See TracChangeset
for help on using the changeset viewer.