Package net.mtrop.doom.struct.trie

Class AbstractTrieMap<K,V,S>

java.lang.Object
net.mtrop.doom.struct.trie.AbstractTrie<Map.Entry<K,V>,S>
net.mtrop.doom.struct.trie.AbstractTrieMap<K,V,S>
Type Parameters:
K - the key type.
V - the value type that this holds.
S - the type of the split segments used for searching.
All Implemented Interfaces:
Iterable<Map.Entry<K,V>>
Direct Known Subclasses:
StringTrieMap
public abstract class AbstractTrieMap<K,V,S> extends AbstractTrie<Map.Entry<K,V>,S>
A trie is a data structure that maps an object to another object, using a path of objects derived from the key. This structure is not thread-safe - wrap calls with synchronized blocks if necessary.
Author:
Matthew Tropiano

  • Constructor Details

    • AbstractTrieMap

      public AbstractTrieMap()
      Creates a new trie map.

  • Method Details

    • getSegments

      protected final S[] getSegments(Map.Entry<K,V> pair)
      Description copied from class: AbstractTrie
      Creates the segments necessary to find/store values. This should always create the same segments for the same value.
      Specified by:
      getSegments in class AbstractTrie<Map.Entry<K,V>,S>
      Parameters:
      pair - the value to generate significant segments for.
      Returns:
      the list of segments for the value.

    • getSegmentsForKey

      protected abstract S[] getSegmentsForKey(K key)
      Creates the segments necessary to find/store values with keys. This should always create the same segments for the same key.
      Parameters:
      key - the key to generate significant segments for.
      Returns:
      the list of segments for the key.

    • put

      public void put(K key, V value)
      Associates a key to a value in this map. The policy of "put" is that if it an object already in the set, its value is replaced with the new value.
      Parameters:
      key - the map key.
      value - the corresponding value.
      See Also:

    • containsKey

      public boolean containsKey(K key)
      Checks if an object (by equality) is present in the structure.
      Parameters:
      key - the object to use for checking presence.
      Returns:
      true if it is in the map, false otherwise.

    • get

      public V get(K key)
      Returns a value for the key provided.
      Parameters:
      key - the key.
      Returns:
      the corresponding value, or null if there is no value associated with that key.

    • getBeforeKey

      public int getBeforeKey(K key, List<V> out)
      Returns all values in the order that they are found on the way through the Trie searching for a particular corresponding value. Result may include the value corresponding to the key.

      The results are set in the output list provided by the user - an offset before the end of the list replaces, not adds!

      Parameters:
      key - the key to search for.
      out - the output list.
      Returns:
      the amount of items returned into the list.

    • getBeforeKey

      public int getBeforeKey(K key, List<V> out, int startOffset)
      Returns all values in the order that they are found on the way through the Trie searching for a particular corresponding value. Result may include the value corresponding to the key.

      The results are set in the output list provided by the user - an offset before the end of the list replaces, not adds!

      Parameters:
      key - the key to search for.
      out - the output list.
      startOffset - the starting offset into the list to set values.
      Returns:
      the amount of items returned into the list.

    • getAfterKey

      public int getAfterKey(K key, List<V> out)
      Returns all values descending from the end of a search for a particular key. Result may include the value corresponding to the key.

      The values returned may not be returned in any consistent or stable order.

      The results are added to the end of the list.

      Parameters:
      key - the key to search for.
      out - the output list.
      Returns:
      the amount of items returned into the list.

    • getAfterKey

      public int getAfterKey(K key, List<V> out, int startOffset)
      Returns all values descending from the end of a search for a particular value. Result may include the value corresponding to the key.

      The values returned may not be returned in any consistent or stable order.

      The results are set in the output list provided by the user - an offset before the end of the list replaces, not adds!

      Parameters:
      key - the key to search for.
      out - the output list.
      startOffset - the starting offset into the list to set values.
      Returns:
      the amount of items returned into the list.

    • getWithRemainderByKey

      public V getWithRemainderByKey(K key, List<S> out)
      Returns the last-encountered value down a trie search. This is the remainder of the segments generated by the key from the last-matched segment.
      Parameters:
      key - the key to search for.
      out - the output list.
      Returns:
      the last-encountered value.

    • getWithRemainderByKey

      public V getWithRemainderByKey(K key, List<S> out, int startOffset)
      Returns the last-encountered value down a trie search. This is the remainder of the segments generated by the key from the last-matched segment.
      Parameters:
      key - the key to search for.
      out - the output list.
      startOffset - the starting offset into the list to set values.
      Returns:
      the last-encountered value, or null if none encountered.

    • getKeysBeforeKey

      public int getKeysBeforeKey(K key, List<K> out)
      Returns all keys in the order that they are found on the way through the Trie searching for a particular matching key. Result may include the provided key.

      The results are set in the output list provided by the user - an offset before the end of the list replaces, not adds!

      Parameters:
      key - the key to search for.
      out - the output list.
      Returns:
      the amount of items returned into the list.

    • getKeysBeforeKey

      public int getKeysBeforeKey(K key, List<K> out, int startOffset)
      Returns all keys in the order that they are found on the way through the Trie searching for a particular matching key. Result may include the the provided key.

      The results are set in the output list provided by the user - an offset before the end of the list replaces, not adds!

      Parameters:
      key - the key to search for.
      out - the output list.
      startOffset - the starting offset into the list to set keys.
      Returns:
      the amount of items returned into the list.

    • getKeysAfterKey

      public int getKeysAfterKey(K key, List<K> out)
      Returns all keys descending from the end of a search for a particular key. Result may include the provided key.

      The keys returned may not be returned in any consistent or stable order.

      The results are added to the end of the list.

      Parameters:
      key - the key to search for.
      out - the output list.
      Returns:
      the amount of items returned into the list.

    • getKeysAfterKey

      public int getKeysAfterKey(K key, List<K> out, int startOffset)
      Returns all keys descending from the end of a search for a particular key. Result may include the provided key.

      The keys returned may not be returned in any consistent or stable order.

      The results are set in the output list provided by the user - an offset before the end of the list replaces, not adds!

      Parameters:
      key - the key to search for.
      out - the output list.
      startOffset - the starting offset into the list to set keys.
      Returns:
      the amount of items returned into the list.

    • getKeyWithRemainderByKey

      public K getKeyWithRemainderByKey(K key, List<S> out)
      Returns the last-encountered key down a trie search, plus the remainder of the segments generated by the key from the last-matched segment.
      Parameters:
      key - the key to search for.
      out - the output list.
      Returns:
      the last-encountered value.

    • getKeyWithRemainderByKey

      public K getKeyWithRemainderByKey(K key, List<S> out, int startOffset)
      Returns the last-encountered key down a trie search, plus the remainder of the segments generated by the key from the last-matched segment.
      Parameters:
      key - the key to search for.
      out - the output list.
      startOffset - the starting offset into the list to set keys.
      Returns:
      the last-encountered value.

    • searchByKey

      protected AbstractTrie.Result<Map.Entry<K,V>,S> searchByKey(K key, boolean includeEncountered, boolean includeDescendants)
      Search using a key.
      Parameters:
      key - the key to search for.
      includeEncountered - if true, include all visited nodes in the result.
      includeDescendants - if true, include all descendants after the ending node in the result.
      Returns:
      the result of the search.

    • removeEntry

      public V removeEntry(K key)
      Removes a value from this map, corresponding to a key.
      Parameters:
      key - the key to use for checking presence.
      Returns:
      the corresponding value if it was removed from the map, null otherwise.

    • toArrayKeys

      public void toArrayKeys(K[] out)
      Copies the keys of this map into an array. The order of the contents are not guaranteed unless otherwise noted.
      Parameters:
      out - the target array to copy the key objects into.
      Throws:
      ArrayIndexOutOfBoundsException - if the target array is too small to contain the objects.
      See Also:

    • toArrayValues

      public void toArrayValues(V[] out)
      Copies the values of this map into an array. Values are not distinct - if more than one value is in this map, it is added as well. The order of the contents are not guaranteed unless otherwise noted.
      Parameters:
      out - the target array to copy the key objects into.
      Throws:
      ArrayIndexOutOfBoundsException - if the target array is too small to contain the objects.
      See Also:

    • equalityMethod

      protected final boolean equalityMethod(Map.Entry<K,V> object1, Map.Entry<K,V> object2)
      Description copied from class: AbstractTrie
      Determines if the objects are equal. This can be implemented differently in case a data structure has a different concept of what is considered equal.
      Overrides:
      equalityMethod in class AbstractTrie<Map.Entry<K,V>,S>
      Parameters:
      object1 - the first object.
      object2 - the second object.
      Returns:
      true if the keys are considered equal, false otherwise.

    • equalityMethodForKey

      protected boolean equalityMethodForKey(K key1, K key2)
      Determines if two keys are equal. This can be implemented differently in case a map has a different concept of what keys are considered equal.
      Parameters:
      key1 - the first key.
      key2 - the second key.
      Returns:
      true if the keys are considered equal, false otherwise.