Changeset 106


Ignore:
Timestamp:
07/05/11 15:18:56 (13 years ago)
Author:
sherbold
Message:
  • code documentation
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  
    33import java.io.Serializable; 
    44 
     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 */ 
    514public 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         */ 
    723        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         */ 
    932        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         */ 
    1143        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         */ 
    1354        String getSessionFooter(int sessionId); 
    1455} 

  • trunk/EventBenchCore/src/de/ugoe/cs/eventbench/coverage/CoverageCalculator.java

    r102 r106  
    1212import de.ugoe.cs.eventbench.models.IStochasticProcess; 
    1313 
     14/** 
     15 * <p> 
     16 * This class calculates various types of sequence coverage. 
     17 * </p> 
     18 *  
     19 * @author Steffen Herbold 
     20 * @version 1.0 
     21 */ 
    1422public 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         */ 
    1630        private final IStochasticProcess process; 
     31 
     32        /** 
     33         * <p> 
     34         * Sequences for which the coverage is calculated. 
     35         * </p> 
     36         */ 
    1737        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         */ 
    1845        private final int length; 
    19          
     46 
     47        /** 
     48         * <p> 
     49         * All subsequences of {@link #length} of {@link #sequences}. 
     50         * </p> 
     51         */ 
    2052        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         */ 
    2160        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         */ 
    2268        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 
    2689                this.process = process; 
    2790                this.sequences = sequences; 
    2891                this.length = length; 
    2992        } 
    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         */ 
    32102        public double getCoverageAllNoWeight() { 
    33                 if( containedSubSeqs==null ) { 
     103                if (containedSubSeqs == null) { 
    34104                        containedSubSeqs = containedSubSequences(sequences, length); 
    35105                } 
    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         */ 
    39118        public double getCoveragePossibleNoWeight() { 
    40                 if( containedSubSeqs==null ) { 
     119                if (containedSubSeqs == null) { 
    41120                        containedSubSeqs = containedSubSequences(sequences, length); 
    42121                } 
    43                 if( allPossibleSubSeqs==null ) { 
     122                if (allPossibleSubSeqs == null) { 
    44123                        allPossibleSubSeqs = process.generateSequences(length); 
    45124                } 
    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         */ 
    49137        public double getCoveragePossibleWeight() { 
    50                 if( containedSubSeqs==null ) { 
     138                if (containedSubSeqs == null) { 
    51139                        containedSubSeqs = containedSubSequences(sequences, length); 
    52140                } 
    53                 if( allPossibleSubSeqs==null ) { 
     141                if (allPossibleSubSeqs == null) { 
    54142                        allPossibleSubSeqs = process.generateSequences(length); 
    55143                } 
    56                 if( subSeqWeights==null ) { 
     144                if (subSeqWeights == null) { 
    57145                        subSeqWeights = generateWeights(process, allPossibleSubSeqs); 
    58146                } 
    59147                double weight = 0.0; 
    60                 for( List<? extends Event<?>> subSeq : containedSubSeqs ) { 
     148                for (List<? extends Event<?>> subSeq : containedSubSeqs) { 
    61149                        weight += subSeqWeights.get(subSeq); 
    62150                } 
    63151                return weight; 
    64152        } 
    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) { 
    67169                Map<List<? extends Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<? extends Event<?>>, Double>(); 
    68170                double sum = 0.0; 
    69                 for( List<? extends Event<?>> sequence : sequences ) { 
     171                for (List<? extends Event<?>> sequence : sequences) { 
    70172                        double prob = 1.0; 
    71173                        List<Event<?>> context = new LinkedList<Event<?>>(); 
    72                         for( Event<?> event : sequence ) { 
     174                        for (Event<?> event : sequence) { 
    73175                                prob *= process.getProbability(context, event); 
    74176                                context.add(event); 
    … …  
    77179                        sum += prob; 
    78180                } 
    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); 
    82185                        } 
    83186                } 
    84187                return subSeqWeights; 
    85188        } 
    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) { 
    88204                return (long) Math.pow(process.getNumStates(), length); 
    89205        } 
    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) { 
    93221                Set<List<? extends Event<?>>> containedSubSeqs = new LinkedHashSet<List<? extends Event<?>>>(); 
    94222                List<Event<?>> subSeq = new LinkedList<Event<?>>(); 
    95223                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) { 
    98226                                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; 
    102230                                        } 
    103231                                } else { 
    104232                                        subSeq.remove(0); 
    105233                                } 
    106                                 if( minLengthReached ) { 
    107                                         if( !containedSubSeqs.contains(subSeq) ) { 
     234                                if (minLengthReached) { 
     235                                        if (!containedSubSeqs.contains(subSeq)) { 
    108236                                                containedSubSeqs.add(new LinkedList<Event<?>>(subSeq)); 
    109237                                        } 
    … …  
    113241                return containedSubSeqs; 
    114242        } 
    115          
     243 
    116244} 

  • trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/IncompleteMemory.java

    r19 r106  
    44import java.util.List; 
    55 
     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 */ 
    619public class IncompleteMemory<T> implements IMemory<T> { 
    720 
     21        /** 
     22         * <p> 
     23         * Maximum length of the memory. 
     24         * </p> 
     25         */ 
    826        private int length; 
    9          
     27 
     28        /** 
     29         * <p> 
     30         * Internal storage of the history. 
     31         * </p> 
     32         */ 
    1033        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         */ 
    1243        public IncompleteMemory(int length) { 
    1344                this.length = length; 
    1445                history = new LinkedList<T>(); 
    1546        } 
    16          
     47 
     48        /* 
     49         * (non-Javadoc) 
     50         *  
     51         * @see de.ugoe.cs.eventbench.models.IMemory#add(java.lang.Object) 
     52         */ 
    1753        @Override 
    1854        public void add(T state) { 
    19                 if( history.size()==length ) { 
     55                if (history.size() == length) { 
    2056                        history.remove(0); 
    2157                } 
    … …  
    2359        } 
    2460 
     61        /* 
     62         * (non-Javadoc) 
     63         *  
     64         * @see de.ugoe.cs.eventbench.models.IMemory#getLast(int) 
     65         */ 
    2566        @Override 
    2667        public List<T> getLast(int num) { 
    … …  
    2869        } 
    2970 
     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         */ 
    3079        public int getLength() { 
    3180                return history.size(); 

  • trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java

    r102 r106  
    66import java.util.LinkedList; 
    77import java.util.List; 
    8 import java.util.Set; 
    98 
    109import de.ugoe.cs.util.StringTools; 
    1110 
    1211import edu.uci.ics.jung.graph.DelegateTree; 
     12import edu.uci.ics.jung.graph.Graph; 
    1313import edu.uci.ics.jung.graph.Tree; 
    1414 
     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 */ 
    1529public class Trie<T> implements IDotCompatible, Serializable { 
    16          
    17         /** 
     30 
     31        /** 
     32         * <p> 
    1833         * Id for object serialization. 
     34         * </p> 
    1935         */ 
    2036        private static final long serialVersionUID = 1L; 
    2137 
    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         */ 
    2450        private final TrieNode<T> rootNode; 
    25          
     51 
     52        /** 
     53         * <p> 
     54         * Contructor. Creates a new Trie. 
     55         * </p> 
     56         */ 
    2657        public Trie() { 
    2758                rootNode = new TrieNode<T>(); 
    2859                knownSymbols = new LinkedHashSet<T>(); 
    2960        } 
    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() { 
    3270                return new LinkedHashSet<T>(knownSymbols); 
    3371        } 
    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         */ 
    3684        public void train(List<T> sequence, int maxOrder) { 
    3785                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) { 
    4088                        latestActions.add(currentEvent); 
    4189                        knownSymbols.add(currentEvent); 
    4290                        i++; 
    43                         if( i>=maxOrder ) { 
     91                        if (i >= maxOrder) { 
    4492                                add(latestActions.getLast(maxOrder)); 
    4593                        } 
    4694                } 
    4795                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()) { 
    57113                        knownSymbols.addAll(subsequence); 
    58                         subsequence = new LinkedList<T>(subsequence);  // defensive copy! 
     114                        subsequence = new LinkedList<T>(subsequence); // defensive copy! 
    59115                        T firstSymbol = subsequence.get(0); 
    60116                        TrieNode<T> node = getChildCreate(firstSymbol); 
    … …  
    63119        } 
    64120 
    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) { 
    66133                return rootNode.getChildCreate(symbol); 
    67134        } 
    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         */ 
    69147        protected TrieNode<T> getChild(T symbol) { 
    70148                return rootNode.getChild(symbol); 
    71149        } 
    72150 
    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         */ 
    74160        public int getCount(List<T> sequence) { 
    75161                int count = 0; 
    76162                TrieNode<T> node = find(sequence); 
    77                 if( node!=null ) { 
     163                if (node != null) { 
    78164                        count = node.getCount(); 
    79165                } 
    80166                return count; 
    81167        } 
    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         */ 
    84183        public int getCount(List<T> sequence, T follower) { 
    85184                List<T> tmpSequence = new LinkedList<T>(sequence); 
    86185                tmpSequence.add(follower); 
    87186                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         */ 
    91201        public TrieNode<T> find(List<T> sequence) { 
    92                 if( sequence==null || sequence.isEmpty() ) { 
     202                if (sequence == null || sequence.isEmpty()) { 
    93203                        return rootNode; 
    94204                } 
    … …  
    96206                TrieNode<T> result = null; 
    97207                TrieNode<T> node = getChild(sequenceCopy.get(0)); 
    98                 if( node!=null ) { 
     208                if (node != null) { 
    99209                        sequenceCopy.remove(0); 
    100210                        result = node.find(sequenceCopy); 
    … …  
    102212                return result; 
    103213        } 
    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         */ 
    106227        public Collection<T> getFollowingSymbols(List<T> sequence) { 
    107228                Collection<T> result = new LinkedList<T>(); 
    108229                TrieNode<T> node = find(sequence); 
    109                 if( node!=null ) { 
     230                if (node != null) { 
    110231                        result = node.getFollowingSymbols(); 
    111232                } 
    112233                return result; 
    113234        } 
    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         */ 
    117246        public List<T> getContextSuffix(List<T> context) { 
    118247                List<T> contextSuffix = new LinkedList<T>(context); // defensive copy 
    119248                boolean suffixFound = false; 
    120                  
    121                 while(!suffixFound) { 
    122                         if( contextSuffix.isEmpty() ) { 
     249 
     250                while (!suffixFound) { 
     251                        if (contextSuffix.isEmpty()) { 
    123252                                suffixFound = true; // suffix is the empty word 
    124253                        } else { 
    125254                                TrieNode<T> node = find(contextSuffix); 
    126                                 if( node!=null ) { 
    127                                         if( !node.getFollowingSymbols().isEmpty() ) { 
     255                                if (node != null) { 
     256                                        if (!node.getFollowingSymbols().isEmpty()) { 
    128257                                                suffixFound = true; 
    129258                                        } 
    130259                                } 
    131                                 if( !suffixFound ) { 
     260                                if (!suffixFound) { 
    132261                                        contextSuffix.remove(0); 
    133262                                } 
    134263                        } 
    135264                } 
    136                  
     265 
    137266                return contextSuffix; 
    138267        } 
    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         */ 
    143288        static public class TrieVertex { 
     289 
     290                /** 
     291                 * <p> 
     292                 * Id of the vertex. 
     293                 * </p> 
     294                 */ 
    144295                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                 */ 
    145305                protected TrieVertex(String id) { 
    146306                        this.id = id; 
    147307                } 
     308 
     309                /** 
     310                 * <p> 
     311                 * Returns the id of the vertex. 
     312                 * </p> 
     313                 *  
     314                 * @see java.lang.Object#toString() 
     315                 */ 
     316                @Override 
    148317                public String toString() { 
    149318                        return id; 
    150319                } 
    151320        } 
    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         */ 
    153329        protected Tree<TrieVertex, Edge> getGraph() { 
    154330                DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>(); 
    … …  
    156332                return graph; 
    157333        } 
    158          
     334 
     335        /* 
     336         * (non-Javadoc) 
     337         *  
     338         * @see de.ugoe.cs.eventbench.models.IDotCompatible#getDotRepresentation() 
     339         */ 
    159340        public String getDotRepresentation() { 
    160341                StringBuilder stringBuilder = new StringBuilder(); 
    … …  
    164345                return stringBuilder.toString(); 
    165346        } 
    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         */ 
    167356        @Override 
    168357        public String toString() { 
    169358                return rootNode.toString(); 
    170359        } 
    171          
     360 
     361        /** 
     362         * <p> 
     363         * Returns the number of symbols contained in the trie. 
     364         * </p> 
     365         *  
     366         * @return 
     367         */ 
    172368        public int getNumSymbols() { 
    173369                return knownSymbols.size(); 

  • trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java

    r102 r106  
    1111import de.ugoe.cs.util.StringTools; 
    1212import edu.uci.ics.jung.graph.DelegateTree; 
    13  
    14  
     13import 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 */ 
    1528class TrieNode<T> implements Serializable { 
    16          
    17         /** 
     29 
     30        /** 
     31         * <p> 
    1832         * Id for object serialization. 
     33         * </p> 
    1934         */ 
    2035        private static final long serialVersionUID = 1L; 
    21          
     36 
     37        /** 
     38         * <p> 
     39         * Counter for the number of occurences of the sequence. 
     40         * </p> 
     41         */ 
    2242        private int count; 
     43 
     44        /** 
     45         * <p> 
     46         * Symbol associated with the node. 
     47         * </p> 
     48         */ 
    2349        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         */ 
    2556        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         */ 
    2765        TrieNode() { 
    2866                this.symbol = null; 
    … …  
    3068                children = new LinkedList<TrieNode<T>>(); 
    3169        } 
    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         */ 
    3379        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!"); 
    3683                } 
    3784                this.symbol = symbol; 
    … …  
    4087        } 
    4188 
     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         */ 
    4299        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! 
    45104                                throw new AssertionError("Invalid trie operation!"); 
    46105                        } 
    47106                        count++; 
    48107                        subsequence.remove(0); 
    49                         if( !subsequence.isEmpty() ) { 
     108                        if (!subsequence.isEmpty()) { 
    50109                                T nextSymbol = subsequence.get(0); 
    51110                                getChildCreate(nextSymbol).add(subsequence); 
    … …  
    53112                } 
    54113        } 
    55          
     114 
     115        /** 
     116         * <p> 
     117         * Returns the symbol associated with the node. 
     118         * </p> 
     119         *  
     120         * @return symbol associated with the node 
     121         */ 
    56122        public T getSymbol() { 
    57123                return symbol; 
    58124        } 
    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         */ 
    60133        public int getCount() { 
    61134                return count; 
    62135        } 
    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) { 
    65149                TrieNode<T> node = getChild(symbol); 
    66                 if( node==null ) { 
     150                if (node == null) { 
    67151                        node = new TrieNode<T>(symbol); 
    68152                        children.add(node); 
    … …  
    70154                return node; 
    71155        } 
    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         */ 
    73168        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)) { 
    76171                                return child; 
    77172                        } 
    … …  
    79174                return null; 
    80175        } 
    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         */ 
    84188        public TrieNode<T> find(List<T> subsequence) { 
    85189                TrieNode<T> result = null; 
    86                 if( subsequence.isEmpty() ) { 
     190                if (subsequence.isEmpty()) { 
    87191                        result = this; 
    88192                } else { 
    89193                        TrieNode<T> node = getChild(subsequence.get(0)); 
    90                         if( node!=null ) { 
     194                        if (node != null) { 
    91195                                subsequence.remove(0); 
    92196                                result = node.find(subsequence); 
    … …  
    95199                return result; 
    96200        } 
    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         */ 
    99211        public Collection<T> getFollowingSymbols() { 
    100212                Collection<T> followingSymbols = new LinkedList<T>(); 
    101                 for( TrieNode<T> child : children ) { 
     213                for (TrieNode<T> child : children) { 
    102214                        followingSymbols.add(child.getSymbol()); 
    103215                } 
    104216                return followingSymbols; 
    105217        } 
    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         */ 
    107226        @Override 
    108227        public String toString() { 
    109                 String str = symbol.toString()+" #"+count; 
    110                 if( !children.isEmpty() ) { 
     228                String str = symbol.toString() + " #" + count; 
     229                if (!children.isEmpty()) { 
    111230                        str += StringTools.ENDLINE + children.toString(); 
    112231                } 
    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) { 
    117246                TrieVertex currentVertex; 
    118                 if( symbol==null ){ 
     247                if (symbol == null) { 
    119248                        currentVertex = new TrieVertex("root"); 
    120249                        graph.addVertex(currentVertex); 
    121250                } 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) { 
    126256                        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         */ 
    130269        void appendDotRepresentation(StringBuilder stringBuilder) { 
    131270                String thisSaneId; 
    132                 if( symbol==null ) { 
     271                if (symbol == null) { 
    133272                        thisSaneId = "root"; 
    134273                } 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) { 
    142285                        childNode.appendDotRepresentation(stringBuilder); 
    143286                } 
Note: See TracChangeset for help on using the changeset viewer.