Class RadixTreeImpl<T>

  • All Implemented Interfaces:
    java.util.Map<java.lang.String,​T>, MapRadixTree<T>, RadixTree<T>

    public class RadixTreeImpl<T>
    extends java.lang.Object
    implements MapRadixTree<T>
    Implementation for Radix tree RadixTree !!WARNING!! This class violates the general contract of Map in that the results of keySet(), values() and entrySet() are not backed by the map. Changes to the result sets are not reflected in this map!
    Author:
    Tahseen Ur Rehman (tahseen.ur.rehman {at.spam.me.not} gmail.com), Javid Jamae, Dennis Heidsiek, stm
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static interface  RadixTreeImpl.Visitor<T,​R>
      The visitor interface that is used by RadixTreeImpl for performing a task on a searched node.
      static class  RadixTreeImpl.VisitorImpl<T,​R>
      A simple standard implementation for a RadixTreeImpl.Visitor
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected magellan.library.utils.RadixTreeImpl.RadixTreeNode<T> root  
      protected long size  
    • Constructor Summary

      Constructors 
      Constructor Description
      RadixTreeImpl()
      Create a Radix Tree with only the default node root.
    • Method Summary

      All Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      void clear()  
      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 containsKey​(java.lang.Object key)  
      boolean containsValue​(java.lang.Object value)  
      boolean delete​(java.lang.String key)
      Delete a key and its associated value from the tree.
      void display()
      Deprecated.
      protected void display​(int level, magellan.library.utils.RadixTreeImpl.RadixTreeNode<T> node)
      Deprecated.
      java.util.Set<java.util.Map.Entry<java.lang.String,​T>> entrySet()
      !!
      T find​(java.lang.String key)
      Find a value based on its corresponding key.
      void formatTo​(java.util.Formatter formatter, int flags, int width, int precision)
      Writes a textual representation of this tree to the given formatter.
      T get​(java.lang.Object 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.
      boolean isEmpty()  
      java.util.Set<java.lang.String> keySet()
      !!
      T put​(java.lang.String key, T value)  
      void putAll​(java.util.Map<? extends java.lang.String,​? extends T> m)  
      T remove​(java.lang.Object key)  
      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.
      java.util.Map<java.lang.String,​T> searchPrefixMap​(java.lang.String key, int recordLimit)
      Returns a map containing all entries whose keys are have the specified key as a prefix.
      int size()  
      java.lang.String toString()  
      java.util.Collection<T> values()
      !!
      <R> void visit​(java.lang.String key, RadixTreeImpl.Visitor<T,​R> visitor)
      visit the node those key matches the given key
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll
    • Field Detail

      • root

        protected magellan.library.utils.RadixTreeImpl.RadixTreeNode<T> root
      • size

        protected long size
    • Constructor Detail

      • RadixTreeImpl

        public RadixTreeImpl()
        Create a Radix Tree with only the default node root.
    • Method Detail

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.size()
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.isEmpty()
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.containsKey(java.lang.Object)
      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.containsValue(java.lang.Object)
      • get

        public T get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.get(java.lang.Object)
      • put

        public T put​(java.lang.String key,
                     T value)
        Specified by:
        put in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.put(java.lang.Object, java.lang.Object)
      • remove

        public T remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.remove(java.lang.Object)
      • putAll

        public void putAll​(java.util.Map<? extends java.lang.String,​? extends T> m)
        Specified by:
        putAll in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.putAll(java.util.Map)
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.clear()
      • keySet

        public java.util.Set<java.lang.String> keySet()
        !!WARNING!! This violates the general contract of Map in that it isn't backed by the map. Changes to the result set are not reflected in this map!
        Specified by:
        keySet in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.keySet()
      • values

        public java.util.Collection<T> values()
        !!WARNING!! This violates the general contract of Map in that it isn't backed by the map. Changes to the result set are not reflected in this map!
        Specified by:
        values in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.values()
      • entrySet

        public java.util.Set<java.util.Map.Entry<java.lang.String,​T>> entrySet()
        !!WARNING!! This violates the general contract of Map in that it isn't backed by the map. Changes to the result set are not reflected in this map!
        Specified by:
        entrySet in interface java.util.Map<java.lang.String,​T>
        See Also:
        Map.entrySet()
      • searchPrefix

        public java.util.ArrayList<T> searchPrefix​(java.lang.String prefix,
                                                   int recordLimit)
        Description copied from interface: RadixTree
        Search for all the keys that start with given prefix. limiting the results based on the supplied limit.
        Specified by:
        searchPrefix in interface RadixTree<T>
        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
        See Also:
        RadixTree.searchPrefix(java.lang.String, int)
      • searchPrefixMap

        public java.util.Map<java.lang.String,​T> searchPrefixMap​(java.lang.String key,
                                                                       int recordLimit)
        Returns a map containing all entries whose keys are have the specified key as a prefix. The returned result is not backed by this maps. Changes made to it are independent of this map.
        Specified by:
        searchPrefixMap in interface MapRadixTree<T>
        Parameters:
        key -
        recordLimit -
      • find

        public T find​(java.lang.String key)
        Description copied from interface: RadixTree
        Find a value based on its corresponding key.
        Specified by:
        find in interface RadixTree<T>
        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
      • delete

        public boolean delete​(java.lang.String key)
        Description copied from interface: RadixTree
        Delete a key and its associated value from the tree.
        Specified by:
        delete in interface RadixTree<T>
        Parameters:
        key - The key of the node that need to be deleted
        Returns:
        true if the key was deleted, false otherwise.
      • insert

        public void insert​(java.lang.String key,
                           T value)
                    throws DuplicateKeyException
        Description copied from interface: RadixTree
        Insert a new string key and its value to the tree.
        Specified by:
        insert in interface RadixTree<T>
        Parameters:
        key - The string key of the object
        value - The value that need to be stored corresponding to the given key.
        Throws:
        DuplicateKeyException
      • contains

        public boolean contains​(java.lang.String key)
        Description copied from interface: RadixTree
        Check if the tree contains any entry corresponding to the given key.
        Specified by:
        contains in interface RadixTree<T>
        Parameters:
        key - The key that needto be searched in the tree.
        Returns:
        retun true if the key is present in the tree otherwise false
      • visit

        public <R> void visit​(java.lang.String key,
                              RadixTreeImpl.Visitor<T,​R> visitor)
        visit the node those key matches the given key
        Parameters:
        key - The key that need to be visited
        visitor - The visitor object
      • getSize

        public long getSize()
        Description copied from interface: RadixTree
        Return the size of the Radix tree
        Specified by:
        getSize in interface RadixTree<T>
        Returns:
        the size of the tree
      • display

        @Deprecated
        public void display()
        Deprecated.
        Display the Trie on console. WARNING! Do not use this for a large Trie, it's for testing purpose only.
      • display

        @Deprecated
        protected void display​(int level,
                               magellan.library.utils.RadixTreeImpl.RadixTreeNode<T> node)
        Deprecated.
      • formatTo

        public void formatTo​(java.util.Formatter formatter,
                             int flags,
                             int width,
                             int precision)
        Writes a textual representation of this tree to the given formatter. Currently, all options are simply ignored. WARNING! Do not use this for a large Trie, it's for testing purpose only.
      • complete

        public 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"
        Specified by:
        complete in interface RadixTree<T>
        Parameters:
        prefix - The prefix we want to complete
        Returns:
        The unambiguous completion of the string.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object