Home | History | Annotate | Download | only in tree 
      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