ConcurrentRadixTree implements RadixTree<O>, PrettyPrintable, Serializable { @Override public Iterable<CharSequence> getClosestKeys(CharSequence candidate) { SearchResult searchResult = searchTree(candidate); Classification classification = searchResult.classification; switch (classification) { case EXACT_MATCH: { return getDescendantKeys(candidate, searchResult.nodeFound); } case KEY_ENDS_MID_EDGE: { CharSequence edgeSuffix = CharSequences.getSuffix(searchResult.nodeFound.getIncomingEdge(), searchResult.charsMatchedInNodeFound); candidate = CharSequences.concatenate(candidate, edgeSuffix); return getDescendantKeys(candidate, searchResult.nodeFound); } case INCOMPLETE_MATCH_TO_MIDDLE_OF_EDGE: { CharSequence keyOfParentNode = CharSequences.getPrefix(candidate, searchResult.charsMatched - searchResult.charsMatchedInNodeFound); CharSequence keyOfNodeFound = CharSequences.concatenate(keyOfParentNode, searchResult.nodeFound.getIncomingEdge()); return getDescendantKeys(keyOfNodeFound, searchResult.nodeFound); } case INCOMPLETE_MATCH_TO_END_OF_EDGE: { if (searchResult.charsMatched == 0) { break; } CharSequence keyOfNodeFound = CharSequences.getPrefix(candidate, searchResult.charsMatched); return getDescendantKeys(keyOfNodeFound, searchResult.nodeFound); } } return Collections.emptySet(); } ConcurrentRadixTree(NodeFactory nodeFactory); @Override O put(CharSequence key, O value); @Override O putIfAbsent(CharSequence key, O value); @Override O getValueForExactKey(CharSequence key); @Override Iterable<CharSequence> getKeysStartingWith(CharSequence prefix); @Override Iterable<O> getValuesForKeysStartingWith(CharSequence prefix); @Override Iterable<KeyValuePair<O>> getKeyValuePairsForKeysStartingWith(CharSequence prefix); @Override boolean remove(CharSequence key); @Override Iterable<CharSequence> getClosestKeys(CharSequence candidate); @Override Iterable<O> getValuesForClosestKeys(CharSequence candidate); @Override Iterable<KeyValuePair<O>> getKeyValuePairsForClosestKeys(CharSequence candidate); @Override int size(); @Override Node getNode();  }
@Test public void testGetClosestKeys() { ConcurrentRadixTree<Integer> tree = new ConcurrentRadixTree<Integer>(getNodeFactory()); tree.put("COD", 1); tree.put("CODFISH", 2); tree.put("COFFEE", 3); assertEquals("[COD, CODFISH, COFFEE]", Iterables.toString(tree.getClosestKeys("COW"))); assertEquals("[COD, CODFISH, COFFEE]", Iterables.toString(tree.getClosestKeys("CX"))); assertEquals("[COD, CODFISH]", Iterables.toString(tree.getClosestKeys("COD"))); assertEquals("[COFFEE]", Iterables.toString(tree.getClosestKeys("COF"))); assertEquals("[]", Iterables.toString(tree.getClosestKeys("DO"))); assertEquals("[CODFISH]", Iterables.toString(tree.getClosestKeys("CODFISHES"))); }