Skip to content

Instantly share code, notes, and snippets.

@juanplopes
Created June 8, 2012 19:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save juanplopes/2897783 to your computer and use it in GitHub Desktop.
Save juanplopes/2897783 to your computer and use it in GitHub Desktop.
Prefix navigation
package net.intelie.lognit.engine.trie;
import com.google.common.base.Objects;
import java.util.BitSet;
import static net.intelie.lognit.engine.trie.CaseInsensitiveComparator.commonPrefix;
public class PrefixNavigation implements Navigation {
private static final long serialVersionUID = 1L;
private final String term;
public PrefixNavigation(String term) {
this.term = term.toLowerCase();
}
@Override
public BitSet accept(TrieNode trie) {
if (trie == null) return new BitSet();
BitSet bits = new BitSet(trie.maxRef());
navigate(bits, trie, 0);
return bits;
}
private void navigate(BitSet set, TrieNode node, int start) {
if (node == null) return;
String key = node.key();
int step = commonPrefix(term, start, key, 0);
int target = start + step;
if (target < term.length())
navigate(set, node.child(term.charAt(target)), target);
else if (target == term.length())
recursiveSet(node, set);
}
private void recursiveSet(TrieNode node, BitSet set) {
node.set(set);
for (TrieNode child : node.children())
recursiveSet(child, set);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof PrefixNavigation)) return false;
PrefixNavigation that = (PrefixNavigation) o;
return Objects.equal(this.term, that.term);
}
@Override
public int hashCode() {
return Objects.hashCode(term);
}
@Override
public String toString() {
return term + "*";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment