Package net.mtrop.doom.struct.trie

Class AbstractTrie<V,S>

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

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    protected static class 
    AbstractTrie.Node<V,S>
    A single node in the Trie.
    protected static class 
    AbstractTrie.Result<V,S>
    A result of a passive search on a trie.
    protected static class 
    AbstractTrie.TrieIterator<V,S>
    Iterator for this Trie.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected AbstractTrie.Node<V,S>
    root
    Root Node.

  • Constructor Summary

    Constructors
    Constructor
    Description
    AbstractTrie()
    Creates a new trie.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(V value)
    Adds a value to this structure, but only if it does not exist.
    void
    clear()
    Removes all objects from the trie.
    boolean
    contains(V object)
    Checks if an object (by equality) is present in the structure.
    protected boolean
    equalityMethod(V object1, V object2)
    Determines if the objects are equal.
    int
    getAfter(V value, List<V> out)
    Returns all values descending from the end of a search for a particular value.
    int
    getAfter(V value, List<V> out, int startOffset)
    Returns all values descending from the end of a search for a particular value.
    int
    getBefore(V value, List<V> out)
    Returns all values in the order that they are found on the way through the Trie searching for a particular value.
    int
    getBefore(V value, 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 value.
    protected abstract S[]
    getSegments(V value)
    Creates the segments necessary to find/store values.
    V
    getWithRemainder(V value, List<S> out)
    Returns the last-encountered value down a trie search, plus the remainder of the segments generated by the key from the last-matched segment.
    V
    getWithRemainder(V value, List<S> out, int startOffset)
    Returns the last-encountered value down a trie search, plus the remainder of the segments generated by the key from the last-matched segment.
    boolean
    isEmpty()
     
    AbstractTrie.TrieIterator<V,S>
    iterator()
     
    boolean
    remove(V object)
    Removes an object from this structure.
    protected AbstractTrie.Result<V,S>
    search(V value, boolean includeEncountered, boolean includeDescendants)
    Returns a search result generated from walking the edges of the trie looking for a particular value.
    int
    size()
     
    void
    toArray(V[] out)
    Puts the contents of this trie into an array.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Field Details

  • Constructor Details

    • AbstractTrie

      public AbstractTrie()
      Creates a new trie.

  • Method Details

    • getSegments

      protected abstract S[] getSegments(V value)
      Creates the segments necessary to find/store values. This should always create the same segments for the same value.
      Parameters:
      value - the value to generate significant segments for.
      Returns:
      the list of segments for the value.

    • getBefore

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

      The results are added to the end of the list.

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

    • getBefore

      public int getBefore(V value, 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 value. Result may include the value searched for.

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

      Parameters:
      value - the value 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.

    • getAfter

      public int getAfter(V value, List<V> out)
      Returns all values descending from the end of a search for a particular value. Result may include the value searched for.

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

      The results are added to the end of the list.

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

    • getAfter

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

      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:
      value - the value 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.

    • getWithRemainder

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

    • getWithRemainder

      public V getWithRemainder(V value, List<S> out, int startOffset)
      Returns the last-encountered value down a trie search, plus the remainder of the segments generated by the key from the last-matched segment.
      Parameters:
      value - the value 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.

    • add

      public void add(V value)
      Adds a value to this structure, but only if it does not exist. If the value is already in the set, this does nothing. Else, it is added.
      Parameters:
      value - the value to add.
      See Also:

    • contains

      public boolean contains(V object)
      Checks if an object (by equality) is present in the structure.
      Parameters:
      object - the object to use for checking presence.
      Returns:
      true if it is in the structure, false otherwise.
      See Also:

    • remove

      public boolean remove(V object)
      Removes an object from this structure.
      Parameters:
      object - the object to use for checking presence.
      Returns:
      true if it was removed from the structure, false otherwise.

    • equalityMethod

      protected boolean equalityMethod(V object1, V object2)
      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.
      Parameters:
      object1 - the first object.
      object2 - the second object.
      Returns:
      true if the keys are considered equal, false otherwise.

    • size

      public int size()
      Returns:
      the amount of elements that this trie holds.

    • isEmpty

      public boolean isEmpty()
      Returns:
      true if this trie is empty, false if not.

    • toArray

      public void toArray(V[] out)
      Puts the contents of this trie into an array. If the array is too small for the contents of this trie, this will throw an ArrayIndexOutOfBoundsException.
      Parameters:
      out - the output array.
      Throws:
      ArrayIndexOutOfBoundsException - if the array is too small to fit every element.

    • clear

      public void clear()
      Removes all objects from the trie.

    • iterator

      public AbstractTrie.TrieIterator<V,S> iterator()
      Specified by:
      iterator in interface Iterable<V>

    • search

      protected AbstractTrie.Result<V,S> search(V value, boolean includeEncountered, boolean includeDescendants)
      Returns a search result generated from walking the edges of the trie looking for a particular value.
      Parameters:
      value - the value to search for.
      includeEncountered - if true, includes encountered (on the way) during the search.
      includeDescendants - if true, includes descendants (remainder) after the search.
      Returns:
      a trie AbstractTrie.Result. The result contents describe matches, encounters, and remainder, plus hops.