| 1 | package net.digitaltsunami.word.trie; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collection; |
| 5 | |
| 6 | /** |
| 7 | * Concrete implementation of {@link PatternSearchStrategy} using recursion to |
| 8 | * query the tree. |
| 9 | * <p> |
| 10 | * This strategy performs faster than the {@link PatternSearchQueueStrategy}, |
| 11 | * but may not be usable for tries with very deep entries. Normal terms or even |
| 12 | * phrases should not be an issue, but if this were to be used for character |
| 13 | * sequence matching, it is possible that a {@link StackOverflowError} could occur. |
| 14 | * |
| 15 | * @author dhagberg |
| 16 | * |
| 17 | */ |
| 18 | public class PatternSearchRecursiveStrategy implements PatternSearchStrategy { |
| 19 | |
| 20 | /* |
| 21 | * (non-Javadoc) |
| 22 | * |
| 23 | * @see |
| 24 | * net.digitaltsunami.word.trie.PatternSearchStrategy#findPattern(java.lang |
| 25 | * .String, net.digitaltsunami.word.trie.CharTrieNode, char) |
| 26 | */ |
| 27 | @Override |
| 28 | public Collection<String> findPattern(String pattern, CharTrieNode root, char wildcardChar) { |
| 29 | char[] lcPattern = pattern.toLowerCase().toCharArray(); |
| 30 | CharTrieNode currentNode = root; |
| 31 | Collection<String> matchingTerms = new ArrayList<String>(); |
| 32 | findPattern(matchingTerms, lcPattern, 0, currentNode, wildcardChar); |
| 33 | return matchingTerms; |
| 34 | } |
| 35 | |
| 36 | /** |
| 37 | * Recursive method to find all terms matching the pattern provided starting |
| 38 | * at the pattern position and node provided. Results will be stored in the |
| 39 | * provided list. |
| 40 | * |
| 41 | * @param list |
| 42 | * Location to store all matching results. |
| 43 | * @param pattern |
| 44 | * Mix of fixed and/or {@link #WILDCARD_CHAR} characters to |
| 45 | * match. |
| 46 | * @param pos |
| 47 | * current character position with pattern. |
| 48 | * @param node |
| 49 | * current node from which the children will be compared against |
| 50 | * the current character in the pattern. |
| 51 | * @param wildcardChar |
| 52 | * Character value used as wildcard in query. |
| 53 | */ |
| 54 | private void findPattern(Collection<String> list, char[] pattern, int pos, CharTrieNode node, |
| 55 | char wildcardChar) { |
| 56 | if (node == null) { |
| 57 | return; |
| 58 | } |
| 59 | if (pos == pattern.length) { |
| 60 | if (node.isTerminus()) { |
| 61 | list.add(((CharTrieTerminusNode) node).getTerm()); |
| 62 | } |
| 63 | return; |
| 64 | } |
| 65 | if (pattern[pos] == wildcardChar) { |
| 66 | for (CharTrieNode child : node) { |
| 67 | findPattern(list, pattern, pos + 1, child, wildcardChar); |
| 68 | } |
| 69 | } else { |
| 70 | findPattern(list, pattern, pos + 1, node.getChild(pattern[pos]), wildcardChar); |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | } |