lucene-java-3.4.0/lucene/contrib/facet/src/java/org/apache/lucene/facet/search/TopKFacetResultsHandler.java

   1 package org.apache.lucene.facet.search;
   2
   3 import java.io.IOException;
   4 import java.util.ArrayList;
   5
   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;
  14
  15 /**
  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
  22  *
  23  *     http://www.apache.org/licenses/LICENSE-2.0
  24  *
  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.
  30  */
  31
  32 /**
  33  * Generate Top-K results for a particular FacetRequest.
  34  * <p>
  35  * K is global (among all results) and is defined by {@link FacetRequest#getNumResults()}.
  36  * <p>
  37  * Note: Values of 0 (Zero) are ignored by this results handler.
  38  *
  39  * @lucene.experimental
  40  */
  41 public class TopKFacetResultsHandler extends FacetResultsHandler {
  42
  43   /**
  44    * Construct top-K results handler.
  45    * @param taxonomyReader taxonomy reader
  46    * @param facetRequest facet request being served
  47    */
  48   public TopKFacetResultsHandler(TaxonomyReader taxonomyReader,
  49       FacetRequest facetRequest) {
  50     super(taxonomyReader, facetRequest);
  51   }
  52
  53   // fetch top K for specific partition.
  54   @Override
  55   public IntermediateFacetResult fetchPartitionResult(FacetArrays facetArrays, int offset)
  56   throws IOException {
  57     TopKFacetResult res = null;
  58     int ordinal = taxonomyReader.getOrdinal(facetRequest.getCategoryPath());
  59     if (ordinal != TaxonomyReader.INVALID_ORDINAL) {
  60       double value = 0;
  61       if (isSelfPartition(ordinal, facetArrays, offset)) {
  62         int partitionSize = facetArrays.getArraysLength();
  63         value = facetRequest.getValueOf(facetArrays, ordinal % partitionSize);
  64       }
  65
  66       // TODO (Facet): should initial value of "residue" depend on aggregator if not sum?
  67       MutableFacetResultNode parentResultNode =
  68         new MutableFacetResultNode(ordinal, value);
  69
  70       Heap<FacetResultNode> heap = ResultSortUtils.createSuitableHeap(facetRequest);
  71       int totalFacets = heapDescendants(ordinal, heap, parentResultNode, facetArrays, offset);
  72       res = new TopKFacetResult(facetRequest, parentResultNode, totalFacets);
  73       res.setHeap(heap);
  74     }
  75     return res;
  76   }
  77
  78   // merge given top K results into current
  79   @Override
  80   public IntermediateFacetResult mergeResults(IntermediateFacetResult... tmpResults) throws IOException {
  81
  82     int ordinal = taxonomyReader.getOrdinal(facetRequest.getCategoryPath());
  83     MutableFacetResultNode resNode = new MutableFacetResultNode(ordinal, 0);
  84
  85     int totalFacets = 0;
  86     Heap<FacetResultNode> heap = null;
  87
  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();
  96       if (heap == null) {
  97         heap = tmpHeap;
  98         continue;
  99       }
 100       // bring sub results from heap of tmp res into result heap
 101       for (int i = tmpHeap.size(); i > 0; i--) {
 102
 103         FacetResultNode a = heap.insertWithOverflow(tmpHeap.pop());
 104         if (a != null) {
 105           resNode.increaseResidue(a.getResidue());
 106         }
 107       }
 108     }
 109
 110     TopKFacetResult res = new TopKFacetResult(facetRequest, resNode, totalFacets);
 111     res.setHeap(heap);
 112     return res;
 113   }
 114
 115   /**
 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.
 121    */
 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;
 130     int localDepth = 0;
 131     int depth = facetRequest.getDepth();
 132     int[] ordinalStack = new int[2+Math.min(Short.MAX_VALUE, depth)];
 133     int childrenCounter = 0;
 134
 135     int tosOrdinal; // top of stack element
 136
 137     int yc = youngestChild[ordinal];
 138     while (yc >= endOffset) {
 139       yc = olderSibling[yc];
 140     }
 141     // make use of the fact that TaxonomyReader.INVALID_ORDINAL == -1, < endOffset
 142     // and it, too, can stop the loop.
 143     ordinalStack[++localDepth] = yc;
 144
 145     /*
 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.
 150      *
 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
 154      *
 155      * loop as long as stack is not empty of elements other than input ordinal, or for a little while -- it sibling
 156      */
 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
 162         localDepth--;
 163         // change element now on top of stack to its sibling.
 164         ordinalStack[localDepth] = olderSibling[ordinalStack[localDepth]];
 165         continue;
 166       }
 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);
 176           } else {
 177             // it is safe to cast since reusable was created here.
 178             ((MutableFacetResultNode)reusable).reset(tosOrdinal, value);
 179           }
 180           ++childrenCounter;
 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());
 185           }
 186         }
 187       }
 188       if (localDepth < depth) {
 189         // push kid of current tos
 190         yc = youngestChild[tosOrdinal];
 191         while (yc >= endOffset) {
 192           yc = olderSibling[yc];
 193         }
 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;
 197       }
 198     } // endof while stack is not empty
 199
 200     return childrenCounter; // we're done
 201   }
 202
 203   @Override
 204   public FacetResult renderFacetResult(IntermediateFacetResult tmpResult) {
 205     TopKFacetResult res = (TopKFacetResult) tmpResult; // cast is safe by contract of this class
 206     if (res != null) {
 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());
 211       }
 212     }
 213     return res;
 214   }
 215
 216   @Override
 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()) {
 223       heap.add(frn);
 224     }
 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());
 229     }
 230     topFrn.setSubResults(subResults);
 231     return res;
 232   }
 233
 234   @Override
 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) {
 244             break;
 245           }
 246           frn.getLabel(taxonomyReader);
 247         }
 248       }
 249     }
 250   }
 251
 252   ////////////////////////////////////////////////////////////////////////////////////
 253   ////////////////////////////////////////////////////////////////////////////////////
 254
 255   /**
 256    * Private Mutable implementation of result of faceted search.
 257    */
 258   private static class TopKFacetResult extends FacetResult implements IntermediateFacetResult {
 259
 260     // TODO (Facet): is it worth to override PriorityQueue.getSentinelObject()
 261     // for any of our PQs?
 262     private Heap<FacetResultNode> heap;
 263
 264     /**
 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.
 269      */
 270     TopKFacetResult(FacetRequest facetRequest, MutableFacetResultNode facetResultNode, int totalFacets) {
 271       super(facetRequest, facetResultNode, totalFacets);
 272     }
 273
 274     /**
 275      * @return the heap
 276      */
 277     public Heap<FacetResultNode> getHeap() {
 278       return heap;
 279     }
 280
 281     /**
 282      * Set the heap for this result.
 283      * @param heap heap top be set.
 284      */
 285     public void setHeap(Heap<FacetResultNode> heap) {
 286       this.heap = heap;
 287     }
 288
 289   }
 290
 291   //////////////////////////////////////////////////////
 292 }