Class HashTrie<T>

  • All Implemented Interfaces:
    java.util.Map<java.lang.CharSequence,​T>, Trie<T>

    public class HashTrie<T>
    extends java.lang.Object
    implements Trie<T>
    Trie implementation for CharSequence keys. This uses HashMaps for each level instead of the traditional array. This is done as with unicode, each level's array would be 64k entries. NOTE:
    • {@link Map.remove(Object)} is not supported.
    • If deletion support is added the max key length will need work or removal.
    • Null values are not supported.
    Author:
    Ed Schaller
    • Constructor Summary

      Constructors 
      Constructor Description
      HashTrie()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Clear all entries.
      boolean containsKey​(java.lang.Object key)
      boolean containsValue​(java.lang.Object value)
      java.util.Set<java.util.Map.Entry<java.lang.CharSequence,​T>> entrySet()
      boolean equals​(java.lang.Object other)
      T get​(java.lang.Object key)
      Get the value for a key.
      java.util.Map.Entry<java.lang.CharSequence,​T> getLongestMatch​(java.io.PushbackReader keyIn)
      Get the key value entry who's key is the longest prefix match.
      java.util.Map.Entry<java.lang.CharSequence,​T> getLongestMatch​(java.lang.CharSequence key)
      Get the key value entry who's key is the longest prefix match.
      int getMaxKeyLength()
      Get the maximum key length.
      int hashCode()
      boolean isEmpty()
      java.util.Set<java.lang.CharSequence> keySet()
      T put​(java.lang.CharSequence key, T value)
      Add mapping.
      void putAll​(java.util.Map<? extends java.lang.CharSequence,​? extends T> map)
      T remove​(java.lang.Object key)
      Remove a entry.
      int size()
      Get the number of entries.
      java.lang.String toString()
      java.util.Collection<T> values()
      • Methods inherited from class java.lang.Object

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

        compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
    • Constructor Detail

      • HashTrie

        public HashTrie()
    • Method Detail

      • getLongestMatch

        public java.util.Map.Entry<java.lang.CharSequence,​T> getLongestMatch​(java.lang.CharSequence key)
        Get the key value entry who's key is the longest prefix match.
        Specified by:
        getLongestMatch in interface Trie<T>
        Parameters:
        key - The key to lookup
        Returns:
        Entry with the longest matching key.
      • getLongestMatch

        public java.util.Map.Entry<java.lang.CharSequence,​T> getLongestMatch​(java.io.PushbackReader keyIn)
                                                                            throws java.io.IOException
        Get the key value entry who's key is the longest prefix match.
        Specified by:
        getLongestMatch in interface Trie<T>
        Parameters:
        keyIn - Pushback reader to read the key from. This should have a buffer at least as large as getMaxKeyLength() or an IOException may be thrown backing up.
        Returns:
        Entry with the longest matching key.
        Throws:
        java.io.IOException - if keyIn.read() or keyIn.unread() does.
      • getMaxKeyLength

        public int getMaxKeyLength()
        Get the maximum key length.
        Specified by:
        getMaxKeyLength in interface Trie<T>
        Returns:
        max key length.
      • clear

        public void clear()
        Clear all entries.
        Specified by:
        clear in interface java.util.Map<java.lang.CharSequence,​T>
      • containsKey

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

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<java.lang.CharSequence,​T>
      • put

        public T put​(java.lang.CharSequence key,
                     T value)
              throws java.lang.NullPointerException
        Add mapping.
        Specified by:
        put in interface java.util.Map<java.lang.CharSequence,​T>
        Parameters:
        key - The mapping's key.
        Throws:
        java.lang.NullPointerException
      • remove

        public T remove​(java.lang.Object key)
                 throws java.lang.UnsupportedOperationException
        Remove a entry.
        Specified by:
        remove in interface java.util.Map<java.lang.CharSequence,​T>
        Returns:
        previous value
        Throws:
        java.lang.UnsupportedOperationException - always.
      • putAll

        public void putAll​(java.util.Map<? extends java.lang.CharSequence,​? extends T> map)
        Specified by:
        putAll in interface java.util.Map<java.lang.CharSequence,​T>
      • keySet

        public java.util.Set<java.lang.CharSequence> keySet()
        Specified by:
        keySet in interface java.util.Map<java.lang.CharSequence,​T>
      • values

        public java.util.Collection<T> values()
        Specified by:
        values in interface java.util.Map<java.lang.CharSequence,​T>
      • entrySet

        public java.util.Set<java.util.Map.Entry<java.lang.CharSequence,​T>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<java.lang.CharSequence,​T>
      • get

        public T get​(java.lang.Object key)
        Get the value for a key.
        Specified by:
        get in interface java.util.Map<java.lang.CharSequence,​T>
        Parameters:
        key - The key to look up.
        Returns:
        The value for key or null if the key is not found.
      • size

        public int size()
        Get the number of entries.
        Specified by:
        size in interface java.util.Map<java.lang.CharSequence,​T>
        Returns:
        the number or entries.
      • equals

        public boolean equals​(java.lang.Object other)
        Specified by:
        equals in interface java.util.Map<java.lang.CharSequence,​T>
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Map<java.lang.CharSequence,​T>
        Overrides:
        hashCode in class java.lang.Object
      • toString

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

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<java.lang.CharSequence,​T>