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