← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/contrib/facet/src/java/org/apache/lucene/facet/search/TopKFacetResultsHandler.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
}