[1] | 1 | package de.ugoe.cs.eventbench.ppm;
|
---|
| 2 |
|
---|
| 3 | import java.util.LinkedList;
|
---|
| 4 | import java.util.List;
|
---|
| 5 |
|
---|
| 6 | public class Trie<T> {
|
---|
| 7 |
|
---|
| 8 | private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>();
|
---|
| 9 |
|
---|
| 10 |
|
---|
| 11 | public void add(List<T> subsequence) {
|
---|
| 12 | if( !subsequence.isEmpty() ) {
|
---|
| 13 | subsequence = new LinkedList<T>(subsequence); // copy list!
|
---|
| 14 | T firstSymbol = subsequence.get(0);
|
---|
| 15 | getChildCreate(firstSymbol).add(subsequence);
|
---|
| 16 | }
|
---|
| 17 | }
|
---|
| 18 |
|
---|
| 19 | // FIXME clones of TrieNode.getChildCreate
|
---|
| 20 | protected TrieNode<T> getChildCreate(T symbol) {
|
---|
| 21 | TrieNode<T> node = getChild(symbol);
|
---|
| 22 | if( node==null ) {
|
---|
| 23 | node = new TrieNode<T>(symbol);
|
---|
| 24 | children.add(node);
|
---|
| 25 | }
|
---|
| 26 | return node;
|
---|
| 27 | }
|
---|
| 28 |
|
---|
| 29 | // FIXME clones of TrieNode.getChild
|
---|
| 30 | protected TrieNode<T> getChild(T symbol) {
|
---|
| 31 | for( TrieNode<T> child : children ) {
|
---|
| 32 | if( child.getSymbol().equals(symbol) ) {
|
---|
| 33 | return child;
|
---|
| 34 | }
|
---|
| 35 | }
|
---|
| 36 | return null;
|
---|
| 37 | }
|
---|
| 38 |
|
---|
| 39 | public int getCount(List<T> sequence) {
|
---|
| 40 | int count = 0;
|
---|
| 41 | TrieNode<T> node = find(sequence);
|
---|
| 42 | if( node!=null ) {
|
---|
| 43 | count = node.getCount();
|
---|
| 44 | }
|
---|
| 45 | return count;
|
---|
| 46 | }
|
---|
| 47 |
|
---|
| 48 | public int getCount(List<T> sequence, T follower) {
|
---|
| 49 | List<T> tmpSequence = new LinkedList<T>(sequence);
|
---|
| 50 | tmpSequence.add(follower);
|
---|
| 51 | return getCount(tmpSequence);
|
---|
| 52 |
|
---|
| 53 | }
|
---|
| 54 |
|
---|
| 55 | public TrieNode<T> find(List<T> sequence) {
|
---|
| 56 | TrieNode<T> result = null;
|
---|
| 57 | if( !sequence.isEmpty() ) {
|
---|
| 58 | TrieNode<T> node = getChild(sequence.get(0));
|
---|
| 59 | if( node!=null ) {
|
---|
| 60 | result = node.find(sequence);
|
---|
| 61 | }
|
---|
| 62 | }
|
---|
| 63 | return result;
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | public List<T> getFollowingSymbols(List<T> sequence) {
|
---|
| 67 | List<T> result = null;
|
---|
| 68 | TrieNode<T> node = find(sequence);
|
---|
| 69 | if( node!=null ) {
|
---|
| 70 | result = node.getFollowingSymbols();
|
---|
| 71 | }
|
---|
| 72 | return result;
|
---|
| 73 | }
|
---|
| 74 |
|
---|
| 75 | public List<T> getContextSuffix(List<T> context) {
|
---|
| 76 | List<T> contextSuffix = new LinkedList<T>(context);
|
---|
| 77 | boolean suffixFound = false;
|
---|
| 78 |
|
---|
| 79 | while(!suffixFound) {
|
---|
| 80 | if( contextSuffix.isEmpty() ) {
|
---|
| 81 | suffixFound = true; // suffix is the empty word
|
---|
| 82 | } else {
|
---|
| 83 | TrieNode<T> node = find(contextSuffix);
|
---|
| 84 | if( node!=null ) {
|
---|
| 85 | if( !node.getFollowingSymbols().isEmpty() ) {
|
---|
| 86 | suffixFound = true;
|
---|
| 87 | }
|
---|
| 88 | }
|
---|
| 89 | contextSuffix.remove(0);
|
---|
| 90 | }
|
---|
| 91 | }
|
---|
| 92 |
|
---|
| 93 | return contextSuffix;
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | @Override
|
---|
| 97 | public String toString() {
|
---|
| 98 | return children.toString();
|
---|
| 99 | }
|
---|
| 100 | }
|
---|