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.

  • Method Details

    • 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.