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<Set<E>>

io.github.douira.glsl_transformer.ast.query.PermutermTrie<E>

All Implemented Interfaces:

InfixQueryable<E>, InvertedInfixQueryable<E>, PrefixQueryable<E>, SuffixQueryable<E>, Serializable, Map<String,Set<E>>, SortedMap<String,Set<E>>, Get<String,Set<E>>, IterableGet<String,Set<E>>, IterableMap<String,Set<E>>, IterableSortedMap<String,Set<E>>, OrderedMap<String,Set<E>>, Put<String,Set<E>>, Trie<String,Set<E>>

public class PermutermTrie<E>
extends DuplicatorTrie<Set<E>>
implements PrefixQueryable<E>, SuffixQueryable<E>, InfixQueryable<E>, InvertedInfixQueryable<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:

• Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class io.github.douira.glsl_transformer.ast.query.DuplicatorTrie

DuplicatorTrie.Holder<V>

Nested classes/interfaces inherited from class java.util.AbstractMap

AbstractMap.SimpleEntry<K extends Object,V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object,V extends Object>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

Field Summary

Fields

Modifier and Type	Field	Description
protected int	modCount	The number of times this Trie has been modified.

Fields inherited from class io.github.douira.glsl_transformer.ast.query.DuplicatorTrie

DEFAULT_MARKER, marker

Constructor Summary

Constructors

Constructor	Description
PermutermTrie()
PermutermTrie(char marker)
PermutermTrie(Map<? extends String,? extends Set<E>> m)
PermutermTrie(Map<? extends String,? extends Set<E>> m, char marker)

Method Summary

Modifier and Type	Method	Description
void	clear()
Comparator<? super String>	comparator()
Set<Map.Entry<String,Set<E>>>	entrySet()
String	firstKey()	Gets the first key currently in this map.
Stream<Set<E>>	infixQuery(String infix)	Returns a stream of all the elements that have a given infix (substring).
Stream<Set<E>>	invertedInfixQuery(String prefix, String suffix)	Returns a stream of all the elements that have a given prefix and suffix.
protected void	iterateKeyVariations(String key, Consumer<String> consumer)
Set<String>	keySet()
String	lastKey()	Gets the last key currently in this map.
OrderedMapIterator<String,Set<E>>	mapIterator()	Obtains an OrderedMapIterator over the map.
Stream<Set<E>>	prefixQuery(String prefix)	Returns a stream of all the elements that have a given prefix.
protected String	prepareKey(Object k)
Set<E>	selectValue(String key)	Returns the value whose key is closest in a bitwise XOR metric to the provided key.
int	size()
Stream<Set<E>>	suffixQuery(String suffix)	Returns a stream of all the elements that have a given suffix.
Collection<Set<E>>	values()

Methods inherited from class io.github.douira.glsl_transformer.ast.query.DuplicatorTrie

containsKey, distinctPrefixQuery, get, headMap, nextKey, prefixMap, prefixMapRaw, previousKey, put, remove, sanitizeKey, select, selectKey, subMap, tailMap

Methods inherited from class org.apache.commons.collections4.trie.AbstractBitwiseTrie

getKeyAnalyzer, toString

Methods inherited from class java.util.AbstractMap

clone, containsValue, equals, hashCode, isEmpty, putAll

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.apache.commons.collections4.Get

containsValue, isEmpty

Methods inherited from interface io.github.douira.glsl_transformer.ast.query.InfixQueryable

infixQueryFlat

Methods inherited from interface io.github.douira.glsl_transformer.ast.query.InvertedInfixQueryable

invertedInfixQueryFlat

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll

Methods inherited from interface io.github.douira.glsl_transformer.ast.query.PrefixQueryable

prefixQueryFlat

Methods inherited from interface org.apache.commons.collections4.Put

putAll

Methods inherited from interface io.github.douira.glsl_transformer.ast.query.SuffixQueryable

suffixQueryFlat

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 Set<E>> m)

PermutermTrie

public PermutermTrie(char marker)

PermutermTrie

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

Method Details

iterateKeyVariations

protected void iterateKeyVariations(String key,
 Consumer<String> consumer)

Specified by:

iterateKeyVariations in class DuplicatorTrie<Set<E>>

prepareKey

protected String prepareKey(Object k)

Overrides:

prepareKey in class DuplicatorTrie<Set<E>>

prefixQuery

public Stream<Set<E>> prefixQuery(String prefix)

Returns a stream of all the elements that have a given prefix.

Specified by:

prefixQuery in interface PrefixQueryable<E>

Parameters:

prefix - the prefix to search for

Returns:

the elements that have the prefix

suffixQuery

public Stream<Set<E>> suffixQuery(String suffix)

Returns a stream of all the elements that have a given suffix.

Specified by:

suffixQuery in interface SuffixQueryable<E>

Parameters:

suffix - the suffix to search for

Returns:

the elements that have the suffix

infixQuery

public Stream<Set<E>> infixQuery(String infix)

Returns a stream of all the elements that have a given infix (substring).

Specified by:

infixQuery in interface InfixQueryable<E>

Parameters:

infix - the infix to search for

Returns:

the elements that have the infix

invertedInfixQuery

public Stream<Set<E>> invertedInfixQuery(String prefix,
 String suffix)

Returns a stream of all the elements that have a given prefix and suffix.

Specified by:

invertedInfixQuery in interface InvertedInfixQueryable<E>

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:

• Map.clear()

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:

• Map.size()

selectValue

public Set<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,Set<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:

• Map.entrySet()

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:

• Map.keySet()

values

public Collection<Set<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:

• Map.values()

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,Set<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