| 1 | package net.digitaltsunami.word.trie; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collection; |
| 5 | import java.util.Collections; |
| 6 | import java.util.Iterator; |
| 7 | import java.util.LinkedList; |
| 8 | import java.util.Queue; |
| 9 | |
| 10 | /** |
| 11 | * Concrete implementation of {@link PatternSearchStrategy} using a queue to |
| 12 | * query the trie. |
| 13 | * <p> |
| 14 | * This strategy performs slower than the {@link PatternSearchQueueStrategy} and |
| 15 | * should be used only for very deep tries that may cause a |
| 16 | * {@link StackOverflowError} if using recursion. |
| 17 | * |
| 18 | * @author dhagberg |
| 19 | * |
| 20 | */ |
| 21 | public class PatternSearchQueueStrategy implements PatternSearchStrategy { |
| 22 | |
| 23 | private static final CharTrieNode SENTINEL = new CharTrieNodeSentinel('\0'); |
| 24 | |
| 25 | /* |
| 26 | * (non-Javadoc) |
| 27 | * |
| 28 | * @see |
| 29 | * net.digitaltsunami.word.trie.PatternSearchStrategy#findPattern(java.lang |
| 30 | * .String, net.digitaltsunami.word.trie.CharTrieNode, char) |
| 31 | */ |
| 32 | @Override |
| 33 | public Collection<String> findPattern(String pattern, CharTrieNode root, char wildcardChar) { |
| 34 | int patLen = pattern.length(); |
| 35 | if (patLen < 1) { |
| 36 | return Collections.emptyList(); |
| 37 | } |
| 38 | char[] lcPattern = pattern.toLowerCase().toCharArray(); |
| 39 | Collection<String> matchingTerms = new ArrayList<String>(); |
| 40 | |
| 41 | Queue<CharTrieNode> candidates = new LinkedList<CharTrieNode>(); |
| 42 | CharTrieNode currentNode = root; |
| 43 | candidates.add(root); |
| 44 | |
| 45 | // Sentinel is used to delimit level changes. |
| 46 | candidates.add(SENTINEL); |
| 47 | |
| 48 | int patPos = 0; |
| 49 | int lastPatPos = patLen - 1; |
| 50 | while (!candidates.isEmpty()) { |
| 51 | currentNode = candidates.poll(); |
| 52 | if (currentNode == SENTINEL) { |
| 53 | /* |
| 54 | * All nodes at the current level have been processed. Advance |
| 55 | * to next position and add a sentinel for the next level if not |
| 56 | * at the end. |
| 57 | */ |
| 58 | patPos++; |
| 59 | if (patPos < patLen) { |
| 60 | candidates.add(SENTINEL); |
| 61 | } |
| 62 | continue; |
| 63 | } |
| 64 | |
| 65 | if (patPos == lastPatPos) { |
| 66 | /* |
| 67 | * At the end of the pattern. Check all children of current node |
| 68 | * for match of pattern. If a match and the node indicates the |
| 69 | * last character in a term, add to list. |
| 70 | */ |
| 71 | if (lcPattern[patPos] == wildcardChar) { |
| 72 | for (CharTrieNode child : currentNode) { |
| 73 | if (child.isTerminus()) { |
| 74 | matchingTerms.add(((CharTrieTerminusNode) child).getTerm()); |
| 75 | } |
| 76 | } |
| 77 | } else { |
| 78 | CharTrieNode child = currentNode.getChild(lcPattern[patPos]); |
| 79 | if (child != null) { |
| 80 | if (child.isTerminus()) { |
| 81 | matchingTerms.add(((CharTrieTerminusNode) child).getTerm()); |
| 82 | } |
| 83 | } |
| 84 | } |
| 85 | } else { |
| 86 | /* |
| 87 | * Examine current nodes children and add all nodes matching the |
| 88 | * pattern to the candidates queue for subsequent processing. |
| 89 | */ |
| 90 | if (lcPattern[patPos] == wildcardChar) { |
| 91 | for (CharTrieNode child : currentNode) { |
| 92 | candidates.add(child); |
| 93 | } |
| 94 | } else { |
| 95 | CharTrieNode child = currentNode.getChild(lcPattern[patPos]); |
| 96 | if (child != null) { |
| 97 | candidates.add(child); |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | return matchingTerms; |
| 103 | } |
| 104 | |
| 105 | /** |
| 106 | * Empty implementation of {@link CharTrieNode} used to delimit levels |
| 107 | * within the trie while adding nodes to the queue. All methods return |
| 108 | * default value of null or false and should not be used. |
| 109 | * |
| 110 | * @author dhagberg |
| 111 | * |
| 112 | */ |
| 113 | private static class CharTrieNodeSentinel implements CharTrieNode { |
| 114 | |
| 115 | private char value; |
| 116 | |
| 117 | public CharTrieNodeSentinel(char value) { |
| 118 | this.value = value; |
| 119 | } |
| 120 | |
| 121 | @Override |
| 122 | public CharTrieNode getChild(char value) { |
| 123 | return null; |
| 124 | } |
| 125 | |
| 126 | @Override |
| 127 | public CharTrieNode addChild(char value) { |
| 128 | return null; |
| 129 | } |
| 130 | |
| 131 | @Override |
| 132 | public boolean isTerminus() { |
| 133 | return false; |
| 134 | } |
| 135 | |
| 136 | @Override |
| 137 | public boolean isRoot() { |
| 138 | return false; |
| 139 | } |
| 140 | |
| 141 | @Override |
| 142 | public char getValue() { |
| 143 | return value; |
| 144 | } |
| 145 | |
| 146 | @Override |
| 147 | public CharTrieNode getParent() { |
| 148 | return null; |
| 149 | } |
| 150 | |
| 151 | @Override |
| 152 | public Iterator<CharTrieNode> iterator() { |
| 153 | return null; |
| 154 | } |
| 155 | |
| 156 | } |
| 157 | |
| 158 | } |