Package io.github.douira.glsl_transformer.ast.query

Class PermutermTrie<E>

java.lang.Object
java.util.AbstractMap<K,V>
org.apache.commons.collections4.trie.AbstractBitwiseTrie<K,V>
org.apache.commons.collections4.trie.PatriciaTrie<E>
io.github.douira.glsl_transformer.ast.query.DuplicatorTrie<E>
io.github.douira.glsl_transformer.ast.query.PermutermTrie<E>
All Implemented Interfaces:
Serializable, Map<String,E>, SortedMap<String,E>, Get<String,E>, IterableGet<String,E>, IterableMap<String,E>, IterableSortedMap<String,E>, OrderedMap<String,E>, Put<String,E>, Trie<String,E>
public class PermutermTrie<E> extends DuplicatorTrie<E>
This permuterm trie supports prefix, suffix, infix and inverted infix (suffix + prefix) queries and works by inserting all rotations of the key into the underlying trie. The number of bits used to index an entry is quadratic in the size of the key.
See Also:

  • Field Details

    • modCount

      protected transient int modCount
      The number of times this Trie has been modified. It's used to detect concurrent modifications and fail-fast the Iterators.

  • Constructor Details

    • PermutermTrie

      public PermutermTrie()

    • PermutermTrie

      public PermutermTrie(Map<? extends String,? extends E> m)

    • PermutermTrie

      public PermutermTrie(char marker)

    • PermutermTrie

      public PermutermTrie(Map<? extends String,? extends E> m, char marker)

  • Method Details

    • iterateKeyVariations

      protected void iterateKeyVariations(String key, Consumer<String> consumer)
      Specified by:
      iterateKeyVariations in class DuplicatorTrie<E>

    • prepareKey

      protected String prepareKey(Object k)
      Overrides:
      prepareKey in class DuplicatorTrie<E>

    • prefixQuery

      public Stream<E> prefixQuery(String prefix)
      Returns a stream of all the elements that have a given prefix.
      Parameters:
      prefix - the prefix to search for
      Returns:
      the elements that have the prefix

    • suffixQuery

      public Stream<E> suffixQuery(String suffix)
      Returns a stream of all the elements that have a given suffix.
      Parameters:
      suffix - the suffix to search for
      Returns:
      the elements that have the suffix

    • infixQuery

      public Stream<E> infixQuery(String infix)
      Returns a stream of all the elements that have a given infix (substring).
      Parameters:
      infix - the infix to search for
      Returns:
      the elements that have the infix

    • suffixPrefixQuery

      public Stream<E> suffixPrefixQuery(String prefix, String suffix)
      Returns a stream of all the elements that have a given prefix and suffix.
      Parameters:
      prefix - the prefix to search require
      suffix - the suffix to search require
      Returns:
      the elements that have the prefix and suffix

    • clear

      public void clear()
      Specified by:
      clear in interface Map<K,V>
      Specified by:
      clear in interface Put<K,V>
      Overrides:
      clear in class AbstractMap<K,V>
      See Also:

    • size

      public int size()
      Specified by:
      size in interface Get<K,V>
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
      Returns:
      the number of key-value mappings in this map
      See Also:

    • selectValue

      public E selectValue(String key)
      Returns the value whose key is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:
      1. D = 1000100
      2. H = 1001000
      3. L = 1001100
      If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.
      Parameters:
      key - the key to use in the search
      Returns:
      the value whose key is closest in a bitwise XOR metric to the provided key

    • entrySet

      public Set<Map.Entry<String,E>> entrySet()
      Specified by:
      entrySet in interface Get<K,V>
      Specified by:
      entrySet in interface Map<K,V>
      Specified by:
      entrySet in interface SortedMap<K,V>
      Specified by:
      entrySet in class AbstractMap<K,V>
      Returns:
      a set view of the mappings contained in this map
      See Also:

    • keySet

      public Set<String> keySet()
      Specified by:
      keySet in interface Get<K,V>
      Specified by:
      keySet in interface Map<K,V>
      Specified by:
      keySet in interface SortedMap<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>
      Returns:
      a set view of the keys contained in this map
      See Also:

    • values

      public Collection<E> values()
      Specified by:
      values in interface Get<K,V>
      Specified by:
      values in interface Map<K,V>
      Specified by:
      values in interface SortedMap<K,V>
      Overrides:
      values in class AbstractMap<K,V>
      Returns:
      a collection view of the values contained in this map
      See Also:

    • comparator

      public Comparator<? super String> comparator()

    • firstKey

      public String firstKey()
      Description copied from interface: OrderedMap
      Gets the first key currently in this map.
      Returns:
      the first key currently in this map

    • lastKey

      public String lastKey()
      Description copied from interface: OrderedMap
      Gets the last key currently in this map.
      Returns:
      the last key currently in this map

    • mapIterator

      public OrderedMapIterator<String,E> mapIterator()
      Description copied from interface: OrderedMap
      Obtains an OrderedMapIterator over the map.

      A ordered map iterator is an efficient way of iterating over maps in both directions.

      Returns:
      a map iterator