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

Class PrefixSuffixTrie<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.PrefixSuffixTrie<E>

All Implemented Interfaces:

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 PrefixSuffixTrie<E>
extends DuplicatorTrie<Set<E>>
implements PrefixQueryable<E>, SuffixQueryable<E>

This prefix-suffix trie supports both prefix and suffix queries but no infix-related queries and works by inserting the key and its reverse into the underlying trie. This is more efficient than the permuterm trie since the number of bits used to index an entry is not quadratic in the size of the key but linear.

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
PrefixSuffixTrie()
PrefixSuffixTrie(char marker)
PrefixSuffixTrie(Map<? extends String,? extends Set<E>> m)
PrefixSuffixTrie(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.
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)
Set<E>	remove(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)
Collection<Set<E>>	values()

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

containsKey, distinctPrefixQuery, get, headMap, nextKey, prefixMap, prefixMapRaw, prepareKey, previousKey, put, 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 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

PrefixSuffixTrie

public PrefixSuffixTrie()

PrefixSuffixTrie

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

PrefixSuffixTrie

public PrefixSuffixTrie(char marker)

PrefixSuffixTrie

public PrefixSuffixTrie(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>>

remove

public Set<E> remove(Object k)

Specified by:

remove in interface Get<String,Set<E>>

Specified by:

remove in interface Map<String,Set<E>>

Overrides:

remove in class DuplicatorTrie<Set<E>>

Parameters:

k - key whose mapping is to be removed from the map

Returns:

the previous value associated with key, or null if there was no mapping for key.

See Also:

• Map.remove(Object)

prefixQuery

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

Specified by:

prefixQuery in interface PrefixQueryable<E>

suffixQuery

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

Specified by:

suffixQuery in interface SuffixQueryable<E>

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