1a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com/* 2a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comThe MIT License 3a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 4a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comCopyright (c) 2008 Tahseen Ur Rehman, Javid Jamae 5a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 6a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comhttp://code.google.com/p/radixtree/ 7a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 8a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comPermission is hereby granted, free of charge, to any person obtaining a copy 9a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comof this software and associated documentation files (the "Software"), to deal 10a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comin the Software without restriction, including without limitation the rights 11a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comto use, copy, modify, merge, publish, distribute, sublicense, and/or sell 12a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comcopies of the Software, and to permit persons to whom the Software is 13a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comfurnished to do so, subject to the following conditions: 14a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 15a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comThe above copyright notice and this permission notice shall be included in 16a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comall copies or substantial portions of the Software. 17a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 18a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 21a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 22a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 23a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 24a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comTHE SOFTWARE. 25a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com*/ 26a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 27a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.compackage ds.tree; 28a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 29a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.ArrayList; 30a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.Formattable; 31a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.Formatter; 32a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.Iterator; 33a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.LinkedList; 34a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.Queue; 35a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 36a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com/** 37a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Implementation for Radix tree {@link RadixTree} 38a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 39a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @author Tahseen Ur Rehman (tahseen.ur.rehman {at.spam.me.not} gmail.com) 40a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @author Javid Jamae 41a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @author Dennis Heidsiek 42a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 43a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.compublic class RadixTreeImpl<T> implements RadixTree<T>, Formattable { 44a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 45a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com protected RadixTreeNode<T> root; 46a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 47a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com protected long size; 48a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 49a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 50a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Create a Radix Tree with only the default node root. 51a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 52a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public RadixTreeImpl() { 53a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com root = new RadixTreeNode<T>(); 54a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com root.setKey(""); 55a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com size = 0; 56a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 57a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 58a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public T find(String key) { 59a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com Visitor<T,T> visitor = new VisitorImpl<T,T>() { 60a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 61a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void visit(String key, RadixTreeNode<T> parent, 62a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> node) { 63a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.isReal()) 64a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = node.getValue(); 65a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 66a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com }; 67a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 68a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visit(key, visitor); 69a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 70a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return visitor.getResult(); 71a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 72a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 73a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean replace(String key, final T value) { 74a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com Visitor<T,T> visitor = new VisitorImpl<T,T>() { 75a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void visit(String key, RadixTreeNode<T> parent, RadixTreeNode<T> node) { 76a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.isReal()) { 77a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setValue(value); 78a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = value; 79a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } else { 80a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = null; 81a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 82a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 83a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com }; 84a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 85a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visit(key, visitor); 86a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 87a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return visitor.getResult() != null; 88a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 89a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 90a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean delete(String key) { 91a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com Visitor<T, Boolean> visitor = new VisitorImpl<T, Boolean>(Boolean.FALSE) { 92a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void visit(String key, RadixTreeNode<T> parent, 93a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> node) { 94a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = node.isReal(); 95a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 96a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // if it is a real node 97a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (result) { 98a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // If there no children of the node we need to 99a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // delete it from the its parent children list 100a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.getChildern().size() == 0) { 101a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com Iterator<RadixTreeNode<T>> it = parent.getChildern() 102a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com .iterator(); 103a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com while (it.hasNext()) { 104a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (it.next().getKey().equals(node.getKey())) { 105a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com it.remove(); 106a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 107a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 108a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 109a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 110a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // if parent is not real node and has only one child 111a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // then they need to be merged. 112a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (parent.getChildern().size() == 1 113a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com && parent.isReal() == false) { 114a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com mergeNodes(parent, parent.getChildern().get(0)); 115a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 116a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } else if (node.getChildern().size() == 1) { 117a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // we need to merge the only child of this node with 118a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // itself 119a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com mergeNodes(node, node.getChildern().get(0)); 120a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } else { // we jus need to mark the node as non real. 121a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setReal(false); 122a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 123a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 124a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 125a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 126a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 127a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Merge a child into its parent node. Operation only valid if it is 128a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * only child of the parent node and parent node is not a real node. 129a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 130a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param parent 131a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The parent Node 132a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param child 133a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The child Node 134a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 135a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private void mergeNodes(RadixTreeNode<T> parent, 136a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> child) { 137a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com parent.setKey(parent.getKey() + child.getKey()); 138a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com parent.setReal(child.isReal()); 139a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com parent.setValue(child.getValue()); 140a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com parent.setChildern(child.getChildern()); 141a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 142a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 143a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com }; 144a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 145a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visit(key, visitor); 146a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 147a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if(visitor.getResult()) { 148a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com size--; 149a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 150a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return visitor.getResult().booleanValue(); 151a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 152a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 153a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /* 154a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * (non-Javadoc) 155a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @see ds.tree.RadixTree#insert(java.lang.String, java.lang.Object) 156a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 157a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void insert(String key, T value) throws DuplicateKeyException { 158a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com try { 159a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com insert(key, root, value); 160a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } catch (DuplicateKeyException e) { 161a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // re-throw the exception with 'key' in the message 162a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com throw new DuplicateKeyException("Duplicate key: '" + key + "'"); 163a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 164a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com size++; 165a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 166a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 167a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 168a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Recursively insert the key in the radix tree. 169a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 170a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key The key to be inserted 171a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param node The current node 172a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param value The value associated with the key 173a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @throws DuplicateKeyException If the key already exists in the database. 174a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 175a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private void insert(String key, RadixTreeNode<T> node, T value) 176a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com throws DuplicateKeyException { 177a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 178a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com int numberOfMatchingCharacters = node.getNumberOfMatchingCharacters(key); 179a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 180a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // we are either at the root node 181a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // or we need to go down the tree 182a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.getKey().equals("") == true || numberOfMatchingCharacters == 0 || (numberOfMatchingCharacters < key.length() && numberOfMatchingCharacters >= node.getKey().length())) { 183a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com boolean flag = false; 184a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com String newText = key.substring(numberOfMatchingCharacters, key.length()); 185a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (RadixTreeNode<T> child : node.getChildern()) { 186a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (child.getKey().startsWith(newText.charAt(0) + "")) { 187a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com flag = true; 188a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com insert(newText, child, value); 189a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 190a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 191a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 192a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 193a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // just add the node as the child of the current node 194a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (flag == false) { 195a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> n = new RadixTreeNode<T>(); 196a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setKey(newText); 197a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setReal(true); 198a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setValue(value); 199a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 200a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.getChildern().add(n); 201a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 202a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 203a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // there is a exact match just make the current node as data node 204a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com else if (numberOfMatchingCharacters == key.length() && numberOfMatchingCharacters == node.getKey().length()) { 205a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.isReal() == true) { 206a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com throw new DuplicateKeyException("Duplicate key"); 207a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 208a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 209a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setReal(true); 210a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setValue(value); 211a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 212a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // This node need to be split as the key to be inserted 213a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // is a prefix of the current node key 214a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com else if (numberOfMatchingCharacters > 0 && numberOfMatchingCharacters < node.getKey().length()) { 215a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> n1 = new RadixTreeNode<T>(); 216a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n1.setKey(node.getKey().substring(numberOfMatchingCharacters, node.getKey().length())); 217a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n1.setReal(node.isReal()); 218a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n1.setValue(node.getValue()); 219a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n1.setChildern(node.getChildern()); 220a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 221a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setKey(key.substring(0, numberOfMatchingCharacters)); 222a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setReal(false); 223a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setChildern(new ArrayList<RadixTreeNode<T>>()); 224a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.getChildern().add(n1); 225a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 226a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if(numberOfMatchingCharacters < key.length()) { 227a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> n2 = new RadixTreeNode<T>(); 228a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n2.setKey(key.substring(numberOfMatchingCharacters, key.length())); 229a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n2.setReal(true); 230a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n2.setValue(value); 231a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 232a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.getChildern().add(n2); 233a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } else { 234a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setValue(value); 235a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setReal(true); 236a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 237a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 238a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // this key need to be added as the child of the current node 239a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com else { 240a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> n = new RadixTreeNode<T>(); 241a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setKey(node.getKey().substring(numberOfMatchingCharacters, node.getKey().length())); 242a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setChildern(node.getChildern()); 243a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setReal(node.isReal()); 244a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com n.setValue(node.getValue()); 245a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 246a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setKey(key); 247a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setReal(true); 248a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.setValue(value); 249a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 250a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com node.getChildern().add(n); 251a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 252a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 253a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 254a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public ArrayList<T> searchPrefix(String key, int recordLimit) { 255a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com ArrayList<T> keys = new ArrayList<T>(); 256a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 257a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> node = searchPefix(key, root); 258a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 259a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node != null) { 260a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.isReal()) { 261a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com keys.add(node.getValue()); 262a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 263a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com getNodes(node, keys, recordLimit); 264a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 265a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 266a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return keys; 267a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 268a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 269a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private void getNodes(RadixTreeNode<T> parent, ArrayList<T> keys, int limit) { 270a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com Queue<RadixTreeNode<T>> queue = new LinkedList<RadixTreeNode<T>>(); 271a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 272a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com queue.addAll(parent.getChildern()); 273a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 274a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com while (!queue.isEmpty()) { 275a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> node = queue.remove(); 276a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.isReal() == true) { 277a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com keys.add(node.getValue()); 278a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 279a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 280a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (keys.size() == limit) { 281a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 282a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 283a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 284a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com queue.addAll(node.getChildern()); 285a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 286a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 287a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 288a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private RadixTreeNode<T> searchPefix(String key, RadixTreeNode<T> node) { 289a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> result = null; 290a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 291a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com int numberOfMatchingCharacters = node.getNumberOfMatchingCharacters(key); 292a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 293a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (numberOfMatchingCharacters == key.length() && numberOfMatchingCharacters <= node.getKey().length()) { 294a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = node; 295a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } else if (node.getKey().equals("") == true 296a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com || (numberOfMatchingCharacters < key.length() && numberOfMatchingCharacters >= node.getKey().length())) { 297a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com String newText = key.substring(numberOfMatchingCharacters, key.length()); 298a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (RadixTreeNode<T> child : node.getChildern()) { 299a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (child.getKey().startsWith(newText.charAt(0) + "")) { 300a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = searchPefix(newText, child); 301a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 302a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 303a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 304a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 305a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 306a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return result; 307a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 308a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 309a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean contains(String key) { 310a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com Visitor<T, Boolean> visitor = new VisitorImpl<T,Boolean>(Boolean.FALSE) { 311a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void visit(String key, RadixTreeNode<T> parent, 312a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> node) { 313a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com result = node.isReal(); 314a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 315a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com }; 316a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 317a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visit(key, visitor); 318a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 319a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return visitor.getResult().booleanValue(); 320a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 321a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 322a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 323a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * visit the node those key matches the given key 324a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key The key that need to be visited 325a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param visitor The visitor object 326a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 327a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public <R> void visit(String key, Visitor<T, R> visitor) { 328a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (root != null) { 329a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visit(key, visitor, null, root); 330a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 331a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 332a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 333a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 334a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * recursively visit the tree based on the supplied "key". calls the Visitor 335a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * for the node those key matches the given prefix 336a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 337a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param prefix 338a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The key o prefix to search in the tree 339a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param visitor 340a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The Visitor that will be called if a node with "key" as its 341a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * key is found 342a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param node 343a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The Node from where onward to search 344a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 345a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private <R> void visit(String prefix, Visitor<T, R> visitor, 346a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com RadixTreeNode<T> parent, RadixTreeNode<T> node) { 347a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 348a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com int numberOfMatchingCharacters = node.getNumberOfMatchingCharacters(prefix); 349a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 350a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // if the node key and prefix match, we found a match! 351a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (numberOfMatchingCharacters == prefix.length() && numberOfMatchingCharacters == node.getKey().length()) { 352a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visitor.visit(prefix, parent, node); 353a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } else if (node.getKey().equals("") == true // either we are at the 354a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // root 355a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com || (numberOfMatchingCharacters < prefix.length() && numberOfMatchingCharacters >= node.getKey().length())) { // OR we need to 356a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // traverse the childern 357a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com String newText = prefix.substring(numberOfMatchingCharacters, prefix.length()); 358a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (RadixTreeNode<T> child : node.getChildern()) { 359a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com // recursively search the child nodes 360a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (child.getKey().startsWith(newText.charAt(0) + "")) { 361a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com visit(newText, visitor, node, child); 362a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 363a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 364a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 365a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 366a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 367a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 368a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public long getSize() { 369a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return size; 370a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 371a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 372a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 373a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Display the Trie on console. 374a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 375a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * WARNING! Do not use this for a large Trie, it's for testing purpose only. 376a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @see formatTo 377a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 378a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com @Deprecated 379a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void display() { 380a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com formatNodeTo(new Formatter(System.out), 0, root); 381a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 382a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 383a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com @Deprecated 384a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private void display(int level, RadixTreeNode<T> node) { 385a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com formatNodeTo(new Formatter(System.out), level, node); 386a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 387a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 388a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 389a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * WARNING! Do not use this for a large Trie, it's for testing purpose only. 390a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 391a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private void formatNodeTo(Formatter f, int level, RadixTreeNode<T> node) { 392a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (int i = 0; i < level; i++) { 393a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com f.format(" "); 394a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 395a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com f.format("|"); 396a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (int i = 0; i < level; i++) { 397a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com f.format("-"); 398a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 399a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 400a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (node.isReal() == true) 401a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com f.format("%s[%s]*%n", node.getKey(), node.getValue()); 402a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com else 403a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com f.format("%s%n", node.getKey()); 404a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 405a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (RadixTreeNode<T> child : node.getChildern()) { 406a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com formatNodeTo(f, level + 1, child); 407a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 408a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 409a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 410a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 411a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Writes a textual representation of this tree to the given formatter. 412a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 413a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Currently, all options are simply ignored. 414a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 415a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * WARNING! Do not use this for a large Trie, it's for testing purpose only. 416a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 417a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void formatTo(Formatter formatter, int flags, int width, int precision) { 418a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com formatNodeTo(formatter, 0, root); 419a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 420a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 421a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 422a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Complete the a prefix to the point where ambiguity starts. 423a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 424a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Example: 425a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * If a tree contain "blah1", "blah2" 426a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * complete("b") -> return "blah" 427a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 428a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param prefix The prefix we want to complete 429a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return The unambiguous completion of the string. 430a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 431a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public String complete(String prefix) { 432a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return complete(prefix, root, ""); 433a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 434a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 435a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private String complete(String key, RadixTreeNode<T> node, String base) { 436a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com int i = 0; 437a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com int keylen = key.length(); 438a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com int nodelen = node.getKey().length(); 439a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 440a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com while (i < keylen && i < nodelen) { 441a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (key.charAt(i) != node.getKey().charAt(i)) { 442a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 443a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 444a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com i++; 445a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 446a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 447a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (i == keylen && i <= nodelen) { 448a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return base + node.getKey(); 449a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 450a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com else if (nodelen == 0 || (i < keylen && i >= nodelen)) { 451a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com String beginning = key.substring(0, i); 452a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com String ending = key.substring(i, keylen); 453a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com for (RadixTreeNode<T> child : node.getChildern()) { 454a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (child.getKey().startsWith(ending.charAt(0) + "")) { 455a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return complete(ending, child, base + beginning); 456a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 457a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 458a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 459a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 460a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return ""; 461a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 462a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com}