1 package org.apache.lucene.facet.search;
3 import java.io.IOException;
4 import java.util.ArrayList;
6 import org.apache.lucene.facet.search.params.FacetRequest;
7 import org.apache.lucene.facet.search.results.FacetResult;
8 import org.apache.lucene.facet.search.results.FacetResultNode;
9 import org.apache.lucene.facet.search.results.MutableFacetResultNode;
10 import org.apache.lucene.facet.search.results.IntermediateFacetResult;
11 import org.apache.lucene.facet.taxonomy.TaxonomyReader;
12 import org.apache.lucene.facet.taxonomy.TaxonomyReader.ChildrenArrays;
13 import org.apache.lucene.facet.util.ResultSortUtils;
16 * Licensed to the Apache Software Foundation (ASF) under one or more
17 * contributor license agreements. See the NOTICE file distributed with
18 * this work for additional information regarding copyright ownership.
19 * The ASF licenses this file to You under the Apache License, Version 2.0
20 * (the "License"); you may not use this file except in compliance with
21 * the License. You may obtain a copy of the License at
23 * http://www.apache.org/licenses/LICENSE-2.0
25 * Unless required by applicable law or agreed to in writing, software
26 * distributed under the License is distributed on an "AS IS" BASIS,
27 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
28 * See the License for the specific language governing permissions and
29 * limitations under the License.
33 * Generate Top-K results for a particular FacetRequest.
35 * K is global (among all results) and is defined by {@link FacetRequest#getNumResults()}.
37 * Note: Values of 0 (Zero) are ignored by this results handler.
39 * @lucene.experimental
41 public class TopKFacetResultsHandler extends FacetResultsHandler {
44 * Construct top-K results handler.
45 * @param taxonomyReader taxonomy reader
46 * @param facetRequest facet request being served
48 public TopKFacetResultsHandler(TaxonomyReader taxonomyReader,
49 FacetRequest facetRequest) {
50 super(taxonomyReader, facetRequest);
53 // fetch top K for specific partition.
55 public IntermediateFacetResult fetchPartitionResult(FacetArrays facetArrays, int offset)
57 TopKFacetResult res = null;
58 int ordinal = taxonomyReader.getOrdinal(facetRequest.getCategoryPath());
59 if (ordinal != TaxonomyReader.INVALID_ORDINAL) {
61 if (isSelfPartition(ordinal, facetArrays, offset)) {
62 int partitionSize = facetArrays.getArraysLength();
63 value = facetRequest.getValueOf(facetArrays, ordinal % partitionSize);
66 // TODO (Facet): should initial value of "residue" depend on aggregator if not sum?
67 MutableFacetResultNode parentResultNode =
68 new MutableFacetResultNode(ordinal, value);
70 Heap<FacetResultNode> heap = ResultSortUtils.createSuitableHeap(facetRequest);
71 int totalFacets = heapDescendants(ordinal, heap, parentResultNode, facetArrays, offset);
72 res = new TopKFacetResult(facetRequest, parentResultNode, totalFacets);
78 // merge given top K results into current
80 public IntermediateFacetResult mergeResults(IntermediateFacetResult... tmpResults) throws IOException {
82 int ordinal = taxonomyReader.getOrdinal(facetRequest.getCategoryPath());
83 MutableFacetResultNode resNode = new MutableFacetResultNode(ordinal, 0);
86 Heap<FacetResultNode> heap = null;
88 // merge other results in queue
89 for (IntermediateFacetResult tmpFres : tmpResults) {
90 // cast should succeed
91 TopKFacetResult fres = (TopKFacetResult) tmpFres;
92 totalFacets += fres.getNumValidDescendants();
93 // set the value for the result node representing the facet request
94 resNode.increaseValue(fres.getFacetResultNode().getValue());
95 Heap<FacetResultNode> tmpHeap = fres.getHeap();
100 // bring sub results from heap of tmp res into result heap
101 for (int i = tmpHeap.size(); i > 0; i--) {
103 FacetResultNode a = heap.insertWithOverflow(tmpHeap.pop());
105 resNode.increaseResidue(a.getResidue());
110 TopKFacetResult res = new TopKFacetResult(facetRequest, resNode, totalFacets);
116 * Finds the top K descendants of ordinal, which are at most facetRequest.getDepth()
117 * deeper than facetRequest.getCategoryPath (whose ordinal is input parameter ordinal).
118 * Candidates are restricted to current "counting list" and current "partition",
119 * they join the overall priority queue pq of size K.
120 * @return total number of descendants considered here by pq, excluding ordinal itself.
122 private int heapDescendants(int ordinal, Heap<FacetResultNode> pq,
123 MutableFacetResultNode parentResultNode, FacetArrays facetArrays, int offset) {
124 int partitionSize = facetArrays.getArraysLength();
125 int endOffset = offset + partitionSize;
126 ChildrenArrays childrenArray = taxonomyReader.getChildrenArrays();
127 int[] youngestChild = childrenArray.getYoungestChildArray();
128 int[] olderSibling = childrenArray.getOlderSiblingArray();
129 FacetResultNode reusable = null;
131 int depth = facetRequest.getDepth();
132 int[] ordinalStack = new int[2+Math.min(Short.MAX_VALUE, depth)];
133 int childrenCounter = 0;
135 int tosOrdinal; // top of stack element
137 int yc = youngestChild[ordinal];
138 while (yc >= endOffset) {
139 yc = olderSibling[yc];
141 // make use of the fact that TaxonomyReader.INVALID_ORDINAL == -1, < endOffset
142 // and it, too, can stop the loop.
143 ordinalStack[++localDepth] = yc;
146 * stack holds input parameter ordinal in position 0.
147 * Other elements are < endoffset.
148 * Only top of stack can be TaxonomyReader.INVALID_ORDINAL, and this if and only if
149 * the element below it exhausted all its children: has them all processed.
151 * stack elements are processed (counted and accumulated) only if they
152 * belong to current partition (between offset and endoffset) and first time
153 * they are on top of stack
155 * loop as long as stack is not empty of elements other than input ordinal, or for a little while -- it sibling
157 while (localDepth > 0) {
158 tosOrdinal = ordinalStack[localDepth];
159 if (tosOrdinal == TaxonomyReader.INVALID_ORDINAL) {
160 // element below tos has all its children, and itself, all processed
161 // need to proceed to its sibling
163 // change element now on top of stack to its sibling.
164 ordinalStack[localDepth] = olderSibling[ordinalStack[localDepth]];
167 // top of stack is not invalid, this is the first time we see it on top of stack.
168 // collect it, if belongs to current partition, and then push its kids on itself, if applicable
169 if (tosOrdinal >= offset) { // tosOrdinal resides in current partition
170 int relativeOrdinal = tosOrdinal % partitionSize;
171 double value = facetRequest.getValueOf(facetArrays, relativeOrdinal);
172 if (value != 0 && !Double.isNaN(value)) {
173 // Count current ordinal -- the TOS
174 if (reusable == null) {
175 reusable = new MutableFacetResultNode(tosOrdinal, value);
177 // it is safe to cast since reusable was created here.
178 ((MutableFacetResultNode)reusable).reset(tosOrdinal, value);
181 reusable = pq.insertWithOverflow(reusable);
182 if (reusable != null) {
183 // TODO (Facet): is other logic (not add) needed, per aggregator?
184 parentResultNode.increaseResidue(reusable.getValue());
188 if (localDepth < depth) {
189 // push kid of current tos
190 yc = youngestChild[tosOrdinal];
191 while (yc >= endOffset) {
192 yc = olderSibling[yc];
194 ordinalStack[++localDepth] = yc;
195 } else { // localDepth == depth; current tos exhausted its possible children, mark this by pushing INVALID_ORDINAL
196 ordinalStack[++localDepth] = TaxonomyReader.INVALID_ORDINAL;
198 } // endof while stack is not empty
200 return childrenCounter; // we're done
204 public FacetResult renderFacetResult(IntermediateFacetResult tmpResult) {
205 TopKFacetResult res = (TopKFacetResult) tmpResult; // cast is safe by contract of this class
207 Heap<FacetResultNode> heap = res.getHeap();
208 MutableFacetResultNode resNode = (MutableFacetResultNode)res.getFacetResultNode(); // cast safe too
209 for (int i = heap.size(); i > 0; i--) {
210 resNode.insertSubResult(heap.pop());
217 public FacetResult rearrangeFacetResult(FacetResult facetResult) {
218 TopKFacetResult res = (TopKFacetResult) facetResult; // cast is safe by contract of this class
219 Heap<FacetResultNode> heap = res.getHeap();
220 heap.clear(); // just to be safe
221 MutableFacetResultNode topFrn = (MutableFacetResultNode) res.getFacetResultNode(); // safe cast
222 for (FacetResultNode frn : topFrn.getSubResults()) {
225 int size = heap.size();
226 ArrayList<FacetResultNode> subResults = new ArrayList<FacetResultNode>(size);
227 for (int i = heap.size(); i > 0; i--) {
228 subResults.add(0,heap.pop());
230 topFrn.setSubResults(subResults);
235 // label top K sub results
236 public void labelResult(FacetResult facetResult) throws IOException {
237 if (facetResult != null) { // any result to label?
238 FacetResultNode facetResultNode = facetResult.getFacetResultNode();
239 if (facetResultNode != null) { // any result to label?
240 facetResultNode.getLabel(taxonomyReader);
241 int num2label = facetRequest.getNumLabel();
242 for (FacetResultNode frn : facetResultNode.getSubResults()) {
243 if (--num2label < 0) {
246 frn.getLabel(taxonomyReader);
252 ////////////////////////////////////////////////////////////////////////////////////
253 ////////////////////////////////////////////////////////////////////////////////////
256 * Private Mutable implementation of result of faceted search.
258 private static class TopKFacetResult extends FacetResult implements IntermediateFacetResult {
260 // TODO (Facet): is it worth to override PriorityQueue.getSentinelObject()
261 // for any of our PQs?
262 private Heap<FacetResultNode> heap;
265 * Create a Facet Result.
266 * @param facetRequest Request for which this result was obtained.
267 * @param facetResultNode top result node for this facet result.
268 * @param totalFacets - number of children of the targetFacet, up till the requested depth.
270 TopKFacetResult(FacetRequest facetRequest, MutableFacetResultNode facetResultNode, int totalFacets) {
271 super(facetRequest, facetResultNode, totalFacets);
277 public Heap<FacetResultNode> getHeap() {
282 * Set the heap for this result.
283 * @param heap heap top be set.
285 public void setHeap(Heap<FacetResultNode> heap) {
291 //////////////////////////////////////////////////////