+++ /dev/null
-package org.apache.lucene.facet.search;
-
-import java.io.IOException;
-import java.util.ArrayList;
-
-import org.apache.lucene.facet.search.params.FacetRequest;
-import org.apache.lucene.facet.search.results.FacetResult;
-import org.apache.lucene.facet.search.results.FacetResultNode;
-import org.apache.lucene.facet.search.results.MutableFacetResultNode;
-import org.apache.lucene.facet.search.results.IntermediateFacetResult;
-import org.apache.lucene.facet.taxonomy.TaxonomyReader;
-import org.apache.lucene.facet.taxonomy.TaxonomyReader.ChildrenArrays;
-import org.apache.lucene.facet.util.ResultSortUtils;
-
-/**
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-/**
- * Generate Top-K results for a particular FacetRequest.
- * <p>
- * K is global (among all results) and is defined by {@link FacetRequest#getNumResults()}.
- * <p>
- * Note: Values of 0 (Zero) are ignored by this results handler.
- *
- * @lucene.experimental
- */
-public class TopKFacetResultsHandler extends FacetResultsHandler {
-
- /**
- * Construct top-K results handler.
- * @param taxonomyReader taxonomy reader
- * @param facetRequest facet request being served
- */
- public TopKFacetResultsHandler(TaxonomyReader taxonomyReader,
- FacetRequest facetRequest) {
- super(taxonomyReader, facetRequest);
- }
-
- // fetch top K for specific partition.
- @Override
- public IntermediateFacetResult fetchPartitionResult(FacetArrays facetArrays, int offset)
- throws IOException {
- TopKFacetResult res = null;
- int ordinal = taxonomyReader.getOrdinal(facetRequest.getCategoryPath());
- if (ordinal != TaxonomyReader.INVALID_ORDINAL) {
- double value = 0;
- if (isSelfPartition(ordinal, facetArrays, offset)) {
- int partitionSize = facetArrays.getArraysLength();
- value = facetRequest.getValueOf(facetArrays, ordinal % partitionSize);
- }
-
- // TODO (Facet): should initial value of "residue" depend on aggregator if not sum?
- MutableFacetResultNode parentResultNode =
- new MutableFacetResultNode(ordinal, value);
-
- Heap<FacetResultNode> heap = ResultSortUtils.createSuitableHeap(facetRequest);
- int totalFacets = heapDescendants(ordinal, heap, parentResultNode, facetArrays, offset);
- res = new TopKFacetResult(facetRequest, parentResultNode, totalFacets);
- res.setHeap(heap);
- }
- return res;
- }
-
- // merge given top K results into current
- @Override
- public IntermediateFacetResult mergeResults(IntermediateFacetResult... tmpResults) throws IOException {
-
- int ordinal = taxonomyReader.getOrdinal(facetRequest.getCategoryPath());
- MutableFacetResultNode resNode = new MutableFacetResultNode(ordinal, 0);
-
- int totalFacets = 0;
- Heap<FacetResultNode> heap = null;
-
- // merge other results in queue
- for (IntermediateFacetResult tmpFres : tmpResults) {
- // cast should succeed
- TopKFacetResult fres = (TopKFacetResult) tmpFres;
- totalFacets += fres.getNumValidDescendants();
- // set the value for the result node representing the facet request
- resNode.increaseValue(fres.getFacetResultNode().getValue());
- Heap<FacetResultNode> tmpHeap = fres.getHeap();
- if (heap == null) {
- heap = tmpHeap;
- continue;
- }
- // bring sub results from heap of tmp res into result heap
- for (int i = tmpHeap.size(); i > 0; i--) {
-
- FacetResultNode a = heap.insertWithOverflow(tmpHeap.pop());
- if (a != null) {
- resNode.increaseResidue(a.getResidue());
- }
- }
- }
-
- TopKFacetResult res = new TopKFacetResult(facetRequest, resNode, totalFacets);
- res.setHeap(heap);
- return res;
- }
-
- /**
- * Finds the top K descendants of ordinal, which are at most facetRequest.getDepth()
- * deeper than facetRequest.getCategoryPath (whose ordinal is input parameter ordinal).
- * Candidates are restricted to current "counting list" and current "partition",
- * they join the overall priority queue pq of size K.
- * @return total number of descendants considered here by pq, excluding ordinal itself.
- */
- private int heapDescendants(int ordinal, Heap<FacetResultNode> pq,
- MutableFacetResultNode parentResultNode, FacetArrays facetArrays, int offset) {
- int partitionSize = facetArrays.getArraysLength();
- int endOffset = offset + partitionSize;
- ChildrenArrays childrenArray = taxonomyReader.getChildrenArrays();
- int[] youngestChild = childrenArray.getYoungestChildArray();
- int[] olderSibling = childrenArray.getOlderSiblingArray();
- FacetResultNode reusable = null;
- int localDepth = 0;
- int depth = facetRequest.getDepth();
- int[] ordinalStack = new int[2+Math.min(Short.MAX_VALUE, depth)];
- int childrenCounter = 0;
-
- int tosOrdinal; // top of stack element
-
- int yc = youngestChild[ordinal];
- while (yc >= endOffset) {
- yc = olderSibling[yc];
- }
- // make use of the fact that TaxonomyReader.INVALID_ORDINAL == -1, < endOffset
- // and it, too, can stop the loop.
- ordinalStack[++localDepth] = yc;
-
- /*
- * stack holds input parameter ordinal in position 0.
- * Other elements are < endoffset.
- * Only top of stack can be TaxonomyReader.INVALID_ORDINAL, and this if and only if
- * the element below it exhausted all its children: has them all processed.
- *
- * stack elements are processed (counted and accumulated) only if they
- * belong to current partition (between offset and endoffset) and first time
- * they are on top of stack
- *
- * loop as long as stack is not empty of elements other than input ordinal, or for a little while -- it sibling
- */
- while (localDepth > 0) {
- tosOrdinal = ordinalStack[localDepth];
- if (tosOrdinal == TaxonomyReader.INVALID_ORDINAL) {
- // element below tos has all its children, and itself, all processed
- // need to proceed to its sibling
- localDepth--;
- // change element now on top of stack to its sibling.
- ordinalStack[localDepth] = olderSibling[ordinalStack[localDepth]];
- continue;
- }
- // top of stack is not invalid, this is the first time we see it on top of stack.
- // collect it, if belongs to current partition, and then push its kids on itself, if applicable
- if (tosOrdinal >= offset) { // tosOrdinal resides in current partition
- int relativeOrdinal = tosOrdinal % partitionSize;
- double value = facetRequest.getValueOf(facetArrays, relativeOrdinal);
- if (value != 0 && !Double.isNaN(value)) {
- // Count current ordinal -- the TOS
- if (reusable == null) {
- reusable = new MutableFacetResultNode(tosOrdinal, value);
- } else {
- // it is safe to cast since reusable was created here.
- ((MutableFacetResultNode)reusable).reset(tosOrdinal, value);
- }
- ++childrenCounter;
- reusable = pq.insertWithOverflow(reusable);
- if (reusable != null) {
- // TODO (Facet): is other logic (not add) needed, per aggregator?
- parentResultNode.increaseResidue(reusable.getValue());
- }
- }
- }
- if (localDepth < depth) {
- // push kid of current tos
- yc = youngestChild[tosOrdinal];
- while (yc >= endOffset) {
- yc = olderSibling[yc];
- }
- ordinalStack[++localDepth] = yc;
- } else { // localDepth == depth; current tos exhausted its possible children, mark this by pushing INVALID_ORDINAL
- ordinalStack[++localDepth] = TaxonomyReader.INVALID_ORDINAL;
- }
- } // endof while stack is not empty
-
- return childrenCounter; // we're done
- }
-
- @Override
- public FacetResult renderFacetResult(IntermediateFacetResult tmpResult) {
- TopKFacetResult res = (TopKFacetResult) tmpResult; // cast is safe by contract of this class
- if (res != null) {
- Heap<FacetResultNode> heap = res.getHeap();
- MutableFacetResultNode resNode = (MutableFacetResultNode)res.getFacetResultNode(); // cast safe too
- for (int i = heap.size(); i > 0; i--) {
- resNode.insertSubResult(heap.pop());
- }
- }
- return res;
- }
-
- @Override
- public FacetResult rearrangeFacetResult(FacetResult facetResult) {
- TopKFacetResult res = (TopKFacetResult) facetResult; // cast is safe by contract of this class
- Heap<FacetResultNode> heap = res.getHeap();
- heap.clear(); // just to be safe
- MutableFacetResultNode topFrn = (MutableFacetResultNode) res.getFacetResultNode(); // safe cast
- for (FacetResultNode frn : topFrn.getSubResults()) {
- heap.add(frn);
- }
- int size = heap.size();
- ArrayList<FacetResultNode> subResults = new ArrayList<FacetResultNode>(size);
- for (int i = heap.size(); i > 0; i--) {
- subResults.add(0,heap.pop());
- }
- topFrn.setSubResults(subResults);
- return res;
- }
-
- @Override
- // label top K sub results
- public void labelResult(FacetResult facetResult) throws IOException {
- if (facetResult != null) { // any result to label?
- FacetResultNode facetResultNode = facetResult.getFacetResultNode();
- if (facetResultNode != null) { // any result to label?
- facetResultNode.getLabel(taxonomyReader);
- int num2label = facetRequest.getNumLabel();
- for (FacetResultNode frn : facetResultNode.getSubResults()) {
- if (--num2label < 0) {
- break;
- }
- frn.getLabel(taxonomyReader);
- }
- }
- }
- }
-
- ////////////////////////////////////////////////////////////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////////
-
- /**
- * Private Mutable implementation of result of faceted search.
- */
- private static class TopKFacetResult extends FacetResult implements IntermediateFacetResult {
-
- // TODO (Facet): is it worth to override PriorityQueue.getSentinelObject()
- // for any of our PQs?
- private Heap<FacetResultNode> heap;
-
- /**
- * Create a Facet Result.
- * @param facetRequest Request for which this result was obtained.
- * @param facetResultNode top result node for this facet result.
- * @param totalFacets - number of children of the targetFacet, up till the requested depth.
- */
- TopKFacetResult(FacetRequest facetRequest, MutableFacetResultNode facetResultNode, int totalFacets) {
- super(facetRequest, facetResultNode, totalFacets);
- }
-
- /**
- * @return the heap
- */
- public Heap<FacetResultNode> getHeap() {
- return heap;
- }
-
- /**
- * Set the heap for this result.
- * @param heap heap top be set.
- */
- public void setHeap(Heap<FacetResultNode> heap) {
- this.heap = heap;
- }
-
- }
-
- //////////////////////////////////////////////////////
-}
fnp / pylucene.git / blobdiff