A generic Trie implementation in Java. TrieHard comes ready to create Tries of many types:
String, char[], byte[], int[], short[], long[], and java.nio.ByteBuffer
Trie<String, Boolean> t = Tries.forStrings();
// Include
t.put( "java.lang.", true );
t.put( "java.io.", true );
t.put( "java.util.concurrent.", true );
// Exclude
t.put( "java.util.", false );
t.put( "java.lang.Boolean", false );
assertTrue( t.get( "java.lang.Integer" ) );
assertTrue( t.get( "java.lang.Long" ) );
assertFalse( t.get( "java.lang.Boolean" ) );
assertTrue( t.get( "java.io.InputStream" ) );
assertFalse( t.get( "java.util.ArrayList" ) );
assertTrue( t.get( "java.util.concurrent.ConcurrentHashMap" ) );You can insert millions of keys/values into TrieHard in a second (average insert on all dictionary words is 300-400 nanoseconds) as well as retrieve millions of values in a second (average retrieval is 200-300 nanoseconds).
A typical Trie implementation has an element (i.e. character) per node (a non-compact structure). The Trie implementation in this library is a compact Trie which saves space and is just as efficient.
Given a Trie { "java.io." => 23 }...
- EXACT
Only an equivalent "java.io." will result in 23. - STARTS_WITH
Any superset or equivalent of "java.io." will result in 23. I.E. "java.io.InputStream" is a STARTS_WITH match to the Trie. - PARTIAL
Any subset, superset, or equivalent of "java.io." will result in 23. I.E. "java" is a PARTIAL match to the Trie.
- TrieHard-1.0.jar
- TrieHard-src-1.0.jar - includes source code
Trie<String, Integer> t = Tries.forInsensitiveStrings();
t.setDefaultMatch( TrieMatch.PARTIAL );
// Add all available values to the Trie
t.put( "world", 23 );
t.put( "worm", 45 );
t.put( "worry", 76 );
t.put( "why", -89 );
t.put( "women", 123 );
...
// Given user input, what are possible keys & values?
String userInput = "WO";
Set<Entry<String, Integer>> possible = t.nodes( userInput );
// possible = { world=>23, worm=>45, worry=>76, women=>123 }
...
// Use possible to display full keys and their values.Trie<byte[], String> mapper = Tries.forBytes();
mapper.setDefaultMatch( TrieMatch.EXACT );
...
mapper.put( socketAddress.getAddress(), "google.com" );
...
// Given an IP, get the host name
String host = mapper.get( socketAddress.getAddress() );Implement the following interface and pass it into the constructor of Trie.
public interface TrieSequencer<S>
{
public int matches(S sequenceA, int indexA, S sequenceB, int indexB, int count);
public int lengthOf(S sequence);
public int hashOf(S sequence, int index);
}
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent