[13] | 1 | package de.ugoe.cs.eventbench.models;
|
---|
[1] | 2 |
|
---|
| 3 | import java.security.InvalidParameterException;
|
---|
| 4 | import java.util.LinkedList;
|
---|
| 5 | import java.util.List;
|
---|
| 6 |
|
---|
[13] | 7 | import de.ugoe.cs.eventbench.models.Trie.Edge;
|
---|
| 8 | import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
|
---|
[1] | 9 | import de.ugoe.cs.util.StringTools;
|
---|
[5] | 10 | import edu.uci.ics.jung.graph.DelegateTree;
|
---|
[1] | 11 |
|
---|
| 12 |
|
---|
| 13 | class TrieNode<T> {
|
---|
| 14 |
|
---|
| 15 | private int count;
|
---|
| 16 | private final T symbol;
|
---|
| 17 |
|
---|
| 18 | private List<TrieNode<T>> children;
|
---|
| 19 |
|
---|
[6] | 20 | TrieNode() {
|
---|
| 21 | this.symbol = null;
|
---|
| 22 | count = 0;
|
---|
| 23 | children = new LinkedList<TrieNode<T>>();
|
---|
| 24 | }
|
---|
| 25 |
|
---|
[1] | 26 | public TrieNode(T symbol) {
|
---|
| 27 | if( symbol==null ) {
|
---|
[30] | 28 | throw new InvalidParameterException("symbol must not be null. null is reserved for root node!");
|
---|
[1] | 29 | }
|
---|
| 30 | this.symbol = symbol;
|
---|
| 31 | count = 0;
|
---|
| 32 | children = new LinkedList<TrieNode<T>>();
|
---|
| 33 | }
|
---|
| 34 |
|
---|
| 35 | public void add(List<T> subsequence) {
|
---|
| 36 | if( !subsequence.isEmpty() ) {
|
---|
| 37 | if( !symbol.equals(subsequence.get(0)) ) { // should be guaranteed by the recursion/TrieRoot!
|
---|
| 38 | throw new AssertionError("Invalid trie operation!");
|
---|
| 39 | }
|
---|
| 40 | count++;
|
---|
| 41 | subsequence.remove(0);
|
---|
| 42 | if( !subsequence.isEmpty() ) {
|
---|
| 43 | T nextSymbol = subsequence.get(0);
|
---|
| 44 | getChildCreate(nextSymbol).add(subsequence);
|
---|
| 45 | }
|
---|
| 46 | }
|
---|
| 47 | }
|
---|
| 48 |
|
---|
| 49 | public T getSymbol() {
|
---|
| 50 | return symbol;
|
---|
| 51 | }
|
---|
| 52 |
|
---|
| 53 | public int getCount() {
|
---|
| 54 | return count;
|
---|
| 55 | }
|
---|
| 56 |
|
---|
| 57 | protected TrieNode<T> getChildCreate(T symbol) {
|
---|
| 58 | TrieNode<T> node = getChild(symbol);
|
---|
| 59 | if( node==null ) {
|
---|
| 60 | node = new TrieNode<T>(symbol);
|
---|
| 61 | children.add(node);
|
---|
| 62 | }
|
---|
| 63 | return node;
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | protected TrieNode<T> getChild(T symbol) {
|
---|
| 67 | for( TrieNode<T> child : children ) {
|
---|
| 68 | if( child.getSymbol().equals(symbol) ) {
|
---|
| 69 | return child;
|
---|
| 70 | }
|
---|
| 71 | }
|
---|
| 72 | return null;
|
---|
| 73 | }
|
---|
| 74 |
|
---|
| 75 |
|
---|
| 76 |
|
---|
| 77 | public TrieNode<T> find(List<T> subsequence) {
|
---|
| 78 | TrieNode<T> result = null;
|
---|
| 79 | if( subsequence.isEmpty() ) {
|
---|
| 80 | result = this;
|
---|
| 81 | } else {
|
---|
| 82 | TrieNode<T> node = getChild(subsequence.get(0));
|
---|
| 83 | if( node!=null ) {
|
---|
| 84 | subsequence.remove(0);
|
---|
| 85 | result = node.find(subsequence);
|
---|
| 86 | }
|
---|
| 87 | }
|
---|
| 88 | return result;
|
---|
| 89 | }
|
---|
| 90 |
|
---|
[5] | 91 | // returns all symbols that follow this node
|
---|
[1] | 92 | public List<T> getFollowingSymbols() {
|
---|
| 93 | List<T> followingSymbols = new LinkedList<T>();
|
---|
| 94 | for( TrieNode<T> child : children ) {
|
---|
| 95 | followingSymbols.add(child.getSymbol());
|
---|
| 96 | }
|
---|
| 97 | return followingSymbols;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | @Override
|
---|
| 101 | public String toString() {
|
---|
| 102 | String str = symbol.toString()+" #"+count;
|
---|
| 103 | if( !children.isEmpty() ) {
|
---|
| 104 | str += StringTools.ENDLINE + children.toString();
|
---|
| 105 | }
|
---|
| 106 | return str;
|
---|
| 107 | }
|
---|
| 108 |
|
---|
[5] | 109 | public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
|
---|
[6] | 110 | TrieVertex currentVertex;
|
---|
| 111 | if( symbol==null ){
|
---|
| 112 | currentVertex = new TrieVertex("root");
|
---|
| 113 | graph.addVertex(currentVertex);
|
---|
| 114 | } else {
|
---|
| 115 | currentVertex = new TrieVertex(getSymbol().toString()+"#"+getCount());
|
---|
| 116 | graph.addChild( new Edge() , parent, currentVertex );
|
---|
| 117 | }
|
---|
[5] | 118 | for( TrieNode<T> node : children ) {
|
---|
[6] | 119 | node.getGraph(currentVertex, graph);
|
---|
[5] | 120 | }
|
---|
| 121 | }
|
---|
[30] | 122 |
|
---|
| 123 | void appendDotRepresentation(StringBuilder stringBuilder) {
|
---|
| 124 | String thisSaneId;
|
---|
| 125 | if( symbol==null ) {
|
---|
| 126 | thisSaneId = "root";
|
---|
| 127 | } else {
|
---|
| 128 | thisSaneId = symbol.toString().replace("\"", "\\\"").replaceAll("[\r\n]","")+"#"+count;
|
---|
| 129 | }
|
---|
| 130 | stringBuilder.append(" " + hashCode() + " [label=\""+thisSaneId+"\"];" + StringTools.ENDLINE);
|
---|
| 131 | for( TrieNode<T> childNode : children ) {
|
---|
| 132 | stringBuilder.append(" "+hashCode()+" -> " + childNode.hashCode() + ";" + StringTools.ENDLINE);
|
---|
| 133 | }
|
---|
| 134 | for( TrieNode<T> childNode : children ) {
|
---|
| 135 | childNode.appendDotRepresentation(stringBuilder);
|
---|
| 136 | }
|
---|
| 137 | }
|
---|
[1] | 138 | }
|
---|