@Test public void testSearchTree() { ConcurrentRadixTree<Integer> tree = new ConcurrentRadixTree<Integer>(getNodeFactory()); final Node root, n1, n2, n3, n4, n5, n6; n6 = getNodeFactory().createNode("A", 6, Collections.<Node>emptyList(), false); n5 = getNodeFactory().createNode("AN", 5, Arrays.asList(n6), false); n4 = getNodeFactory().createNode("DANA", 4, Collections.<Node>emptyList(), false); n3 = getNodeFactory().createNode("N", 3, Arrays.asList(n4, n5), false); n2 = getNodeFactory().createNode("A", 2, Arrays.asList(n3), false); n1 = getNodeFactory().createNode("B", 1, Arrays.asList(n2), false); root = getNodeFactory().createNode("", null, Arrays.asList(n1), true); tree.root = root; String expected = "○\n" + "└── ○ B (1)\n" + " └── ○ A (2)\n" + " └── ○ N (3)\n" + " ├── ○ AN (5)\n" + " │ └── ○ A (6)\n" + " └── ○ DANA (4)\n"; assertEquals(expected, PrettyPrinter.prettyPrint(tree)); assertEquals(2, n3.getOutgoingEdges().size()); assertTrue(n3.getOutgoingEdges().contains(n4)); assertTrue(n3.getOutgoingEdges().contains(n5)); assertEquals(tree.root, tree.searchTree("Z").nodeFound); assertNull(tree.searchTree("Z").parentNode); assertNull(tree.searchTree("Z").parentNodesParent); assertEquals(0, tree.searchTree("Z").charsMatched); assertEquals(n1, tree.searchTree("B").nodeFound); assertEquals(tree.root, tree.searchTree("B").parentNode); assertEquals(null, tree.searchTree("B").parentNodesParent); assertEquals(1, tree.searchTree("B").charsMatched); assertEquals(n3, tree.searchTree("BAN").nodeFound); assertEquals(n2, tree.searchTree("BAN").parentNode); assertEquals(n1, tree.searchTree("BAN").parentNodesParent); assertEquals(3, tree.searchTree("BAN").charsMatched); assertEquals(n5, tree.searchTree("BANAN").nodeFound); assertEquals(n3, tree.searchTree("BANAN").parentNode); assertEquals(n2, tree.searchTree("BANAN").parentNodesParent); assertEquals(5, tree.searchTree("BANAN").charsMatched); assertEquals(n5, tree.searchTree("BANA").nodeFound); assertEquals(n3, tree.searchTree("BANA").parentNode); assertEquals(n2, tree.searchTree("BANA").parentNodesParent); assertEquals(4, tree.searchTree("BANA").charsMatched); assertEquals(n6, tree.searchTree("BANANA").nodeFound); assertEquals(n5, tree.searchTree("BANANA").parentNode); assertEquals(n3, tree.searchTree("BANANA").parentNodesParent); assertEquals(6, tree.searchTree("BANANA").charsMatched); assertEquals(n6, tree.searchTree("BANANAS").nodeFound); assertEquals(n5, tree.searchTree("BANANAS").parentNode); assertEquals(n3, tree.searchTree("BANANAS").parentNodesParent); assertEquals(6, tree.searchTree("BANANAS").charsMatched); assertEquals(n2, tree.searchTree("BAR").nodeFound); assertEquals(n1, tree.searchTree("BAR").parentNode); assertEquals(tree.root, tree.searchTree("BAR").parentNodesParent); assertEquals(2, tree.searchTree("BAR").charsMatched); assertEquals(n3, tree.searchTree("BANS").nodeFound); assertEquals(n2, tree.searchTree("BANS").parentNode); assertEquals(n1, tree.searchTree("BANS").parentNodesParent); assertEquals(3, tree.searchTree("BANS").charsMatched); assertEquals(n4, tree.searchTree("BANDAIDS").nodeFound); assertEquals(n3, tree.searchTree("BANDAIDS").parentNode); assertEquals(n2, tree.searchTree("BANDAIDS").parentNodesParent); assertEquals(5, tree.searchTree("BANDAIDS").charsMatched); }
SearchResult searchTree(CharSequence key) { Node parentNodesParent = null; Node parentNode = null; Node currentNode = root; int charsMatched = 0, charsMatchedInNodeFound = 0; final int keyLength = key.length(); outer_loop: while (charsMatched < keyLength) { Node nextNode = currentNode.getOutgoingEdge(key.charAt(charsMatched)); if (nextNode == null) { break outer_loop; } parentNodesParent = parentNode; parentNode = currentNode; currentNode = nextNode; charsMatchedInNodeFound = 0; CharSequence currentNodeEdgeCharacters = currentNode.getIncomingEdge(); for (int i = 0, numEdgeChars = currentNodeEdgeCharacters.length(); i < numEdgeChars && charsMatched < keyLength; i++) { if (currentNodeEdgeCharacters.charAt(i) != key.charAt(charsMatched)) { break outer_loop; } charsMatched++; charsMatchedInNodeFound++; } } return new SearchResult(key, currentNode, charsMatched, charsMatchedInNodeFound, parentNode, parentNodesParent); }
ConcurrentRadixTree implements RadixTree<O>, PrettyPrintable, Serializable { SearchResult searchTree(CharSequence key) { Node parentNodesParent = null; Node parentNode = null; Node currentNode = root; int charsMatched = 0, charsMatchedInNodeFound = 0; final int keyLength = key.length(); outer_loop: while (charsMatched < keyLength) { Node nextNode = currentNode.getOutgoingEdge(key.charAt(charsMatched)); if (nextNode == null) { break outer_loop; } parentNodesParent = parentNode; parentNode = currentNode; currentNode = nextNode; charsMatchedInNodeFound = 0; CharSequence currentNodeEdgeCharacters = currentNode.getIncomingEdge(); for (int i = 0, numEdgeChars = currentNodeEdgeCharacters.length(); i < numEdgeChars && charsMatched < keyLength; i++) { if (currentNodeEdgeCharacters.charAt(i) != key.charAt(charsMatched)) { break outer_loop; } charsMatched++; charsMatchedInNodeFound++; } } return new SearchResult(key, currentNode, charsMatched, charsMatchedInNodeFound, parentNode, parentNodesParent); } }
ConcurrentRadixTree implements RadixTree<O>, PrettyPrintable, Serializable { SearchResult searchTree(CharSequence key) { Node parentNodesParent = null; Node parentNode = null; Node currentNode = root; int charsMatched = 0, charsMatchedInNodeFound = 0; final int keyLength = key.length(); outer_loop: while (charsMatched < keyLength) { Node nextNode = currentNode.getOutgoingEdge(key.charAt(charsMatched)); if (nextNode == null) { break outer_loop; } parentNodesParent = parentNode; parentNode = currentNode; currentNode = nextNode; charsMatchedInNodeFound = 0; CharSequence currentNodeEdgeCharacters = currentNode.getIncomingEdge(); for (int i = 0, numEdgeChars = currentNodeEdgeCharacters.length(); i < numEdgeChars && charsMatched < keyLength; i++) { if (currentNodeEdgeCharacters.charAt(i) != key.charAt(charsMatched)) { break outer_loop; } charsMatched++; charsMatchedInNodeFound++; } } return new SearchResult(key, currentNode, charsMatched, charsMatchedInNodeFound, parentNode, parentNodesParent); } ConcurrentRadixTree(NodeFactory nodeFactory); }
ConcurrentRadixTree implements RadixTree<O>, PrettyPrintable, Serializable { SearchResult searchTree(CharSequence key) { Node parentNodesParent = null; Node parentNode = null; Node currentNode = root; int charsMatched = 0, charsMatchedInNodeFound = 0; final int keyLength = key.length(); outer_loop: while (charsMatched < keyLength) { Node nextNode = currentNode.getOutgoingEdge(key.charAt(charsMatched)); if (nextNode == null) { break outer_loop; } parentNodesParent = parentNode; parentNode = currentNode; currentNode = nextNode; charsMatchedInNodeFound = 0; CharSequence currentNodeEdgeCharacters = currentNode.getIncomingEdge(); for (int i = 0, numEdgeChars = currentNodeEdgeCharacters.length(); i < numEdgeChars && charsMatched < keyLength; i++) { if (currentNodeEdgeCharacters.charAt(i) != key.charAt(charsMatched)) { break outer_loop; } charsMatched++; charsMatchedInNodeFound++; } } return new SearchResult(key, currentNode, charsMatched, charsMatchedInNodeFound, parentNode, parentNodesParent); } 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(); }
ConcurrentRadixTree implements RadixTree<O>, PrettyPrintable, Serializable { SearchResult searchTree(CharSequence key) { Node parentNodesParent = null; Node parentNode = null; Node currentNode = root; int charsMatched = 0, charsMatchedInNodeFound = 0; final int keyLength = key.length(); outer_loop: while (charsMatched < keyLength) { Node nextNode = currentNode.getOutgoingEdge(key.charAt(charsMatched)); if (nextNode == null) { break outer_loop; } parentNodesParent = parentNode; parentNode = currentNode; currentNode = nextNode; charsMatchedInNodeFound = 0; CharSequence currentNodeEdgeCharacters = currentNode.getIncomingEdge(); for (int i = 0, numEdgeChars = currentNodeEdgeCharacters.length(); i < numEdgeChars && charsMatched < keyLength; i++) { if (currentNodeEdgeCharacters.charAt(i) != key.charAt(charsMatched)) { break outer_loop; } charsMatched++; charsMatchedInNodeFound++; } } return new SearchResult(key, currentNode, charsMatched, charsMatchedInNodeFound, parentNode, parentNodesParent); } 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();  }