Interface RadixTree<T>

  • All Known Subinterfaces:
    MapRadixTree<T>
    All Known Implementing Classes:
    RadixTreeImpl

    public interface RadixTree<T>
    This interface represent the operation of a radix tree. A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings. In contrast with a regular trie, the edges of a Patricia trie are labelled with sequences of characters rather than with single characters. These can be strings of characters, bit strings such as integers or IP addresses, or generally arbitrary sequences of objects in lexicographical order. Sometimes the names radix tree and crit bit tree are only applied to trees storing integers and Patricia trie is retained for more general inputs, but the structure works the same way in all cases.
    Author:
    Tahseen Ur Rehman email: tahseen.ur.rehman {at.spam.me.not} gmail.com
    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      java.lang.String complete​(java.lang.String prefix)
      Complete the a prefix to the point where ambiguity starts.
      boolean contains​(java.lang.String key)
      Check if the tree contains any entry corresponding to the given key.
      boolean delete​(java.lang.String key)
      Delete a key and its associated value from the tree.
      T find​(java.lang.String key)
      Find a value based on its corresponding key.
      long getSize()
      Return the size of the Radix tree
      void insert​(java.lang.String key, T value)
      Insert a new string key and its value to the tree.
      java.util.ArrayList<T> searchPrefix​(java.lang.String prefix, int recordLimit)
      Search for all the keys that start with given prefix. limiting the results based on the supplied limit.
    • Method Detail

      • insert

        void insert​(java.lang.String key,
                    T value)
             throws DuplicateKeyException
        Insert a new string key and its value to the tree.
        Parameters:
        key - The string key of the object
        value - The value that need to be stored corresponding to the given key.
        Throws:
        DuplicateKeyException
      • delete

        boolean delete​(java.lang.String key)
        Delete a key and its associated value from the tree.
        Parameters:
        key - The key of the node that need to be deleted
        Returns:
        true if the key was deleted, false otherwise.
      • find

        T find​(java.lang.String key)
        Find a value based on its corresponding key.
        Parameters:
        key - The key for which to search the tree.
        Returns:
        The value corresponding to the key. null if iot can not find the key
      • contains

        boolean contains​(java.lang.String key)
        Check if the tree contains any entry corresponding to the given key.
        Parameters:
        key - The key that needto be searched in the tree.
        Returns:
        retun true if the key is present in the tree otherwise false
      • searchPrefix

        java.util.ArrayList<T> searchPrefix​(java.lang.String prefix,
                                            int recordLimit)
        Search for all the keys that start with given prefix. limiting the results based on the supplied limit.
        Parameters:
        prefix - The prefix for which keys need to be search
        recordLimit - The limit for the results
        Returns:
        The list of values those key start with the given prefix
      • getSize

        long getSize()
        Return the size of the Radix tree
        Returns:
        the size of the tree
      • complete

        java.lang.String complete​(java.lang.String prefix)
        Complete the a prefix to the point where ambiguity starts. Example: If a tree contain "blah1", "blah2" complete("b") -> return "blah"
        Parameters:
        prefix - The prefix we want to complete
        Returns:
        The unambiguous completion of the string.