1a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com/* 2a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comThe MIT License 3a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 4a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comCopyright (c) 2008 Tahseen Ur Rehman 5a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 6a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comPermission is hereby granted, free of charge, to any person obtaining a copy 7a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comof this software and associated documentation files (the "Software"), to deal 8a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comin the Software without restriction, including without limitation the rights 9a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comto use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comcopies of the Software, and to permit persons to whom the Software is 11a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comfurnished to do so, subject to the following conditions: 12a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 13a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comThe above copyright notice and this permission notice shall be included in 14a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comall copies or substantial portions of the Software. 15a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 16a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 22a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comTHE SOFTWARE. 23a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com*/ 24a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 25a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.compackage ds.tree; 26a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 27a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.ArrayList; 28a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 29a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com/** 30a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * This interface represent the operation of a radix tree. A radix tree, 31a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Patricia trie/tree, or crit bit tree is a specialized set data structure 32a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * based on the trie that is used to store a set of strings. In contrast with a 33a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * regular trie, the edges of a Patricia trie are labelled with sequences of 34a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * characters rather than with single characters. These can be strings of 35a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * characters, bit strings such as integers or IP addresses, or generally 36a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * arbitrary sequences of objects in lexicographical order. Sometimes the names 37a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * radix tree and crit bit tree are only applied to trees storing integers and 38a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Patricia trie is retained for more general inputs, but the structure works 39a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * the same way in all cases. 40a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 41a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @author Tahseen Ur Rehman 42a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * email: tahseen.ur.rehman {at.spam.me.not} gmail.com 43a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 44a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.compublic interface RadixTree<T> { 45a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 46a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Insert a new string key and its value to the tree. 47a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 48a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key 49a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The string key of the object 50a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param value 51a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * The value that need to be stored corresponding to the given 52a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * key. 53a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @throws DuplicateKeyException 54a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 55a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void insert(String key, T value); 56a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 57a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 58a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Delete a key and its associated value from the tree. 59a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key The key of the node that need to be deleted 60a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return 61a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 62a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean delete(String key); 63a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 64a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 65a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Find a value based on its corresponding key. 66a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 67a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key The key for which to search the tree. 68a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return The value corresponding to the key. null if iot can not find the key 69a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 70a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public T find(String key); 71a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 72a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 73a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Find an existing entry and replace it's value. If no existing entry, do nothing 74a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 75a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key The key for which to search the tree. 76a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param value The value to set for the entry 77a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return true if an entry was found for the given key, false if not found 78a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 79a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean replace(String key, final T value); 80a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 81a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 82a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Check if the tree contains any entry corresponding to the given key. 83a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 84a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param key The key that needto be searched in the tree. 85a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return retun true if the key is present in the tree otherwise false 86a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 87a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean contains(String key); 88a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 89a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 90a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Search for all the keys that start with given prefix. limiting the results based on the supplied limit. 91a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 92a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param prefix The prefix for which keys need to be search 93a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param recordLimit The limit for the results 94a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return The list of values those key start with the given prefix 95a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 96a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public ArrayList<T> searchPrefix(String prefix, int recordLimit); 97a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 98a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 99a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Return the size of the Radix tree 100a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return the size of the tree 101a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 102a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public long getSize(); 103a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 104a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 105a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Complete the a prefix to the point where ambiguity starts. 106a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 107a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Example: 108a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * If a tree contain "blah1", "blah2" 109a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * complete("b") -> return "blah" 110a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 111a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param prefix The prefix we want to complete 112a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @return The unambiguous completion of the string. 113a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 114a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public String complete(String prefix); 115a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com} 116