1/*
2The MIT License
3
4Copyright (c) 2008 Tahseen Ur Rehman
5
6Permission is hereby granted, free of charge, to any person obtaining a copy
7of this software and associated documentation files (the "Software"), to deal
8in the Software without restriction, including without limitation the rights
9to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10copies of the Software, and to permit persons to whom the Software is
11furnished to do so, subject to the following conditions:
12
13The above copyright notice and this permission notice shall be included in
14all copies or substantial portions of the Software.
15
16THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22THE SOFTWARE.
23*/
24
25package ds.tree;
26
27import 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 */
44public 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