Package org.apache.solr.handler.component

Class QueryElevationComponent.TrieSubsetMatcher<E extends Comparable<? super E>,M>

java.lang.Object

org.apache.solr.handler.component.QueryElevationComponent.TrieSubsetMatcher<E,M>

Type Parameters:

E - Subset element type.

M - Subset match value type.

Enclosing class:

QueryElevationComponent

protected static class QueryElevationComponent.TrieSubsetMatcher<E extends Comparable<? super E>,M>
extends Object

Matches a potentially large collection of subsets with a trie implementation.

Given a collection of subsets N, finds all the subsets that are contained (ignoring duplicate elements) by a provided set s. That is, finds all subsets n in N for which s.containsAll(n) (s contains all the elements of n, in any order).

Associates a match value of type <M> to each subset and provides it each time the subset matches (i.e. is contained by the provided set).

This matcher imposes the elements are Comparable. It does not keep the subset insertion order. Duplicate subsets stack their match values.

The time complexity of adding a subset is O(n.log(n)), where n is the size of the subset.

The worst case time complexity of the subset matching is O(2^s), however a more typical case time complexity is O(s^3) where s is the size of the set to partially match. Note it does not depend on N, the size of the collection of subsets, nor on n, the size of a subset.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	QueryElevationComponent.TrieSubsetMatcher.Builder<E extends Comparable<? super E>,M>

Method Summary

Modifier and Type	Method	Description
Iterator<M>	findSubsetsMatching(Collection<E> set)	Returns an iterator over all the subsets that are contained by the provided set.
int	getSubsetCount()	Gets the number of subsets in this matcher.

Methods inherited from class java.lang.Object

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

Method Detail

getSubsetCount

public int getSubsetCount()

Gets the number of subsets in this matcher.

findSubsetsMatching

public Iterator<M> findSubsetsMatching(Collection<E> set)

Returns an iterator over all the subsets that are contained by the provided set. The returned iterator does not support removal.

Parameters:

set - This set is copied to a new SortedSet with natural ordering.