--- /dev/null
+package org.apache.lucene.facet.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.lucene.util.PriorityQueue;
+
+import org.apache.lucene.facet.search.params.FacetRequest;
+import org.apache.lucene.facet.search.params.FacetRequest.SortOrder;
+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.util.collections.IntIterator;
+import org.apache.lucene.util.collections.IntToObjectMap;
+
+/**
+ * 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.
+ */
+
+/**
+ * Generates {@link FacetResult} from the count arrays aggregated for a particular
+ * {@link FacetRequest}.
+ * The generated {@link FacetResult} is a subtree of the taxonomy tree.
+ * Its root node, {@link FacetResult#getFacetResultNode()},
+ * is the facet specified by {@link FacetRequest#getCategoryPath()},
+ * and the enumerated children, {@link FacetResultNode#getSubResults()}, of each node in that
+ * {@link FacetResult} are the top K ( = {@link FacetRequest#getNumResults()}) among its children
+ * in the taxonomy.
+ * Top in the sense {@link FacetRequest#getSortBy()},
+ * which can be by the values aggregated in the count arrays, or by ordinal numbers;
+ * also specified is the sort order, {@link FacetRequest#getSortOrder()},
+ * ascending or descending, of these values or ordinals before their top K are selected.
+ * The depth (number of levels excluding the root) of the
+ * {@link FacetResult} tree is specified by {@link FacetRequest#getDepth()}.
+ * <p>
+ * Because the number of selected children of each node is restricted,
+ * and not the overall number of nodes in the {@link FacetResult}, facets not selected
+ * into {@link FacetResult} might have better values, or ordinals, (typically,
+ * higher counts), than facets that are selected into the {@link FacetResult}.
+ * <p>
+ * The generated {@link FacetResult} also provides with
+ * {@link FacetResult#getNumValidDescendants()}, which returns the total number of facets
+ * that are descendants of the root node, no deeper than {@link FacetRequest#getDepth()}, and
+ * which have valid value. The rootnode itself is not counted here.
+ * Valid value is determined by the {@link FacetResultsHandler}.
+ * {@link TopKInEachNodeHandler} defines valid as != 0.
+ * <p>
+ * <b>NOTE:</b> this code relies on the assumption that {@link TaxonomyReader#INVALID_ORDINAL} == -1, a smaller
+ * value than any valid ordinal.
+ *
+ * @lucene.experimental
+ */
+public class TopKInEachNodeHandler extends FacetResultsHandler {
+
+ public TopKInEachNodeHandler(TaxonomyReader taxonomyReader,
+ FacetRequest facetRequest) {
+ super(taxonomyReader, facetRequest);
+ }
+
+ /**
+ * Recursively explore all facets that can be potentially included in the
+ * {@link FacetResult} to be generated, and that belong to the given
+ * partition, so that values can be examined and collected. For each such
+ * node, gather its top K ({@link FacetRequest#getNumResults()}) children
+ * among its children that are encountered in the given particular partition
+ * (aka current counting list).
+ *
+ * @return {@link IntermediateFacetResult} consisting of
+ * {@link IntToObjectMap} that maps potential
+ * {@link FacetResult} nodes to their top K children encountered in
+ * the current partition. Note that the mapped potential tree nodes
+ * need not belong to the given partition, only the top K children
+ * mapped to. The aim is to identify nodes that are certainly excluded
+ * from the {@link FacetResult} to be eventually (after going through
+ * all the partitions) returned by this handler, because they have K
+ * better siblings, already identified in this partition. For the
+ * identified excluded nodes, we only count number of their
+ * descendants in the subtree (to be included in
+ * {@link FacetResult#getNumValidDescendants()}), but not bother with
+ * selecting top K in these generations, which, by definition, are,
+ * too, excluded from the FacetResult tree.
+ * @param arrays the already filled in count array, potentially only covering
+ * one partition: the ordinals ranging from
+ * @param offset to <code>offset</code> + the length of the count arrays
+ * within <code>arrays</code> (exclusive)
+ * @throws IOException in case
+ * {@link TaxonomyReader#getOrdinal(org.apache.lucene.facet.taxonomy.CategoryPath)}
+ * does.
+ * @see FacetResultsHandler#fetchPartitionResult(FacetArrays, int)
+ */
+ @Override
+ public IntermediateFacetResult fetchPartitionResult(FacetArrays arrays, int offset) throws IOException {
+
+ // get the root of the result tree to be returned, and the depth of that result tree
+ // (depth means number of node levels excluding the root).
+ int rootNode = this.taxonomyReader.getOrdinal(this.facetRequest.getCategoryPath());
+ if (rootNode == TaxonomyReader.INVALID_ORDINAL) {
+ return null;
+ }
+
+ int K = Math.min(facetRequest.getNumResults(),taxonomyReader.getSize()); // number of best results in each node
+
+ // this will grow into the returned IntermediateFacetResult
+ IntToObjectMap<AACO> AACOsOfOnePartition = new IntToObjectMap<AACO>();
+
+ int partitionSize = arrays.getArraysLength(); // all partitions, except, possibly, the last,
+ // have the same length. Hence modulo is OK.
+
+ int depth = facetRequest.getDepth();
+
+ if (depth == 0) {
+ // Need to only have root node.
+ IntermediateFacetResultWithHash tempFRWH = new IntermediateFacetResultWithHash(
+ facetRequest, AACOsOfOnePartition);
+ if (isSelfPartition(rootNode, arrays, offset)) {
+ tempFRWH.isRootNodeIncluded = true;
+ tempFRWH.rootNodeValue = this.facetRequest.getValueOf(arrays, rootNode % partitionSize);
+ }
+ return tempFRWH;
+ }
+
+ if (depth > Short.MAX_VALUE - 3) {
+ depth = Short.MAX_VALUE -3;
+ }
+
+ int endOffset = offset + partitionSize; // one past the largest ordinal in the partition
+ ChildrenArrays childrenArray = taxonomyReader.getChildrenArrays();
+ int[] youngestChild = childrenArray.getYoungestChildArray();
+ int[] olderSibling = childrenArray.getOlderSiblingArray();
+ int totalNumOfDescendantsConsidered = 0; // total number of facets with value != 0,
+ // in the tree. These include those selected as top K in each node, and all the others that
+ // were not. Not including rootNode
+
+ // the following priority queue will be used again and again for each node recursed into
+ // to select its best K children among its children encountered in the given partition
+ PriorityQueue<AggregatedCategory> pq =
+ new AggregatedCategoryHeap(K, this.getSuitableACComparator());
+
+ // reusables will feed the priority queue in each use
+ AggregatedCategory [] reusables = new AggregatedCategory[2+K];
+ for (int i = 0; i < reusables.length; i++) {
+ reusables[i] = new AggregatedCategory(1,0);
+ }
+
+ /*
+ * The returned map is built by a recursive visit of potential tree nodes. Nodes
+ * determined to be excluded from the FacetResult are not recursively explored as others,
+ * they are only recursed in order to count the number of their descendants.
+ * Also, nodes that they and any of their descendants can not be mapped into facets encountered
+ * in this partition, are, too, explored no further. These are facets whose ordinal
+ * numbers are greater than the ordinals of the given partition. (recall that the Taxonomy
+ * maintains that a parent ordinal is smaller than any of its descendants' ordinals).
+ * So, when scanning over all children of a potential tree node n: (1) all children with ordinal number
+ * greater than those in the given partition are skipped over, (2) among the children of n residing
+ * in this partition, the best K children are selected (using pq) for usual further recursion
+ * and the rest (those rejected out from the pq) are only recursed for counting total number
+ * of descendants, and (3) all the children of ordinal numbers smaller than the given partition
+ * are further explored in the usual way, since these may lead to descendants residing in this partition.
+ *
+ * ordinalStack drives the recursive descent.
+ * Top of stack holds the current node which we recurse from.
+ * ordinalStack[0] holds the root of the facetRequest, and
+ * it is always maintained that parent(ordianlStack[i]) = ordinalStack[i-1].
+ * localDepth points to the current top of ordinalStack.
+ * Only top of ordinalStack can be TaxonomyReader.INVALID_ORDINAL, and this if and only if
+ * the element below it explored all its relevant children.
+ */
+ int[] ordinalStack = new int[depth+2]; // for 0 and for invalid on top
+ ordinalStack[0] = rootNode;
+ int localDepth = 0;
+
+ /*
+ * bestSignlingsStack[i] maintains the best K children of ordinalStack[i-1], namely,
+ * the best K siblings of ordinalStack[i], best K among those residing in the given partition.
+ * Note that the residents of ordinalStack need not belong
+ * to the current partition, only the residents of bestSignlingsStack.
+ * When exploring the children of ordianlStack[i-1] that reside in the current partition
+ * (after the top K of them have been determined and stored into bestSignlingsStack[i]),
+ * siblingExplored[i] points into bestSignlingsStack[i], to the child now explored, hence
+ * residing in ordinalStack[i], and firstToTheLeftOfPartition[i] holds the largest ordinal of
+ * a sibling smaller than the ordinals in the partition.
+ * When siblingExplored[i] == max int, the top K siblings of ordinalStack[i] among those siblings
+ * that reside in this partition have not been determined yet.
+ * if siblingExplored[i] < 0, the node in ordinalStack[i] is to the left of partition
+ * (i.e. of a smaller ordinal than the current partition)
+ * (step (3) above is executed for the children of ordianlStack[i-1])
+ */
+ int[][] bestSignlingsStack = new int[depth+2][];
+ int[] siblingExplored = new int[depth+2];
+ int[] firstToTheLeftOfPartition = new int [depth+2];
+
+ int tosOrdinal; // top of stack element, the ordinal at the top of stack
+
+ /*
+ * to start the loop, complete the datastructures for root node:
+ * push its youngest child to ordinalStack; make a note in siblingExplored[] that the children
+ * of rootNode, which reside in the current partition have not been read yet to select the top
+ * K of them. Also, make rootNode as if, related to its parent, rootNode belongs to the children
+ * of ordinal numbers smaller than those of the current partition (this will ease on end condition --
+ * we can continue to the older sibling of rootNode once the localDepth goes down, before we verify that
+ * it went that down)
+ */
+ ordinalStack[++localDepth] = youngestChild[rootNode];
+ siblingExplored[localDepth] = Integer.MAX_VALUE; // we have not verified position wrt current partition
+ siblingExplored[0] = -1; // as if rootNode resides to the left of current position
+
+ /*
+ * now the whole recursion: loop as long as stack is not empty of elements descendants of
+ * facetRequest's root.
+ */
+
+ while (localDepth > 0) {
+ tosOrdinal = ordinalStack[localDepth];
+ if (tosOrdinal == TaxonomyReader.INVALID_ORDINAL) {
+ // the brotherhood that has been occupying the top of stack is all exhausted.
+ // Hence, element below tos, namely, father of tos, has all its children,
+ // and itself, all explored.
+ localDepth--;
+ // replace this father, now on top of stack, by this father's sibling:
+ // this parent's ordinal can not be greater than current partition, as otherwise
+ // its child, now just removed, would not have been pushed on it.
+ // so the father is either inside the partition, or smaller ordinal
+ if (siblingExplored[localDepth] < 0 ) {
+ ordinalStack[localDepth] = olderSibling[ordinalStack[localDepth]];
+ continue;
+ }
+ // in this point, siblingExplored[localDepth] between 0 and number of bestSiblings
+ // it can not be max int
+ siblingExplored[localDepth]--;
+ if (siblingExplored[localDepth] == -1 ) {
+ //siblings residing in the partition have been all processed, we now move
+ // to those of ordinal numbers smaller than the partition
+ ordinalStack[localDepth] = firstToTheLeftOfPartition[localDepth];
+ } else {
+ // still explore siblings residing in the partition
+ // just move to the next one
+ ordinalStack[localDepth] = bestSignlingsStack[localDepth][siblingExplored[localDepth]];
+ }
+ continue;
+ } // endof tosOrdinal is invalid, and hence removed, and its parent was replaced by this
+ // parent's sibling
+
+ // now try to push a kid, but first look at tos whether it 'deserves' its kids explored:
+ // it is not to the right of current partition, and we know whether to only count or to
+ // select best K siblings.
+ if (siblingExplored[localDepth] == Integer.MAX_VALUE) {
+ //tosOrdinal was not examined yet for its position relative to current partition
+ // and the best K of current partition, among its siblings, have not been determined yet
+ while (tosOrdinal >= endOffset) {
+ tosOrdinal = olderSibling[tosOrdinal];
+ }
+ // now it is inside. Run it and all its siblings inside the partition through a heap
+ // and in doing so, count them, find best K, and sum into residue
+ double residue = 0f; // the sum of all the siblings from this partition that do not make
+ // it to top K
+ pq.clear();
+
+ //reusables are consumed as from a stack. The stack starts full and returns full.
+ int tosReuslables = reusables.length -1;
+
+ while (tosOrdinal >= offset) { // while tosOrdinal belongs to the given partition; here, too, we use the fact
+ // that TaxonomyReader.INVALID_ORDINAL == -1 < offset
+ double value = facetRequest.getValueOf(arrays, tosOrdinal % partitionSize);
+ if (value != 0) { // the value of yc is not 0, it is to be considered.
+ totalNumOfDescendantsConsidered++;
+
+ // consume one reusable, and push to the priority queue
+ AggregatedCategory ac = reusables[tosReuslables--];
+ ac.ordinal = tosOrdinal;
+ ac.value = value;
+ ac = pq.insertWithOverflow(ac);
+ if (null != ac) {
+ residue += ac.value;
+ // TODO (Facet): could it be that we need to do something
+ // else, not add, depending on the aggregator?
+
+ /* when a facet is excluded from top K, because already in this partition it has
+ * K better siblings, it is only recursed for count only.
+ */
+ // update totalNumOfDescendants by the now excluded node and all its descendants
+ totalNumOfDescendantsConsidered--; // reduce the 1 earned when the excluded node entered the heap
+ // and now return it and all its descendants. These will never make it to FacetResult
+ totalNumOfDescendantsConsidered += countOnly (ac.ordinal, youngestChild,
+ olderSibling, arrays, partitionSize, offset, endOffset, localDepth, depth);
+ reusables[++tosReuslables] = ac;
+ }
+ }
+ tosOrdinal = olderSibling[tosOrdinal];
+ }
+ // now pq has best K children of ordinals that belong to the given partition.
+ // Populate a new AACO with them.
+ // tosOrdinal is now first sibling smaller than partition, make a note of that
+ firstToTheLeftOfPartition[localDepth] = tosOrdinal;
+ int aaci = pq.size();
+ int[] ords = new int[aaci];
+ double [] vals = new double [aaci];
+ while (aaci > 0) {
+ AggregatedCategory ac = pq.pop();
+ ords[--aaci] = ac.ordinal;
+ vals[aaci] = ac.value;
+ reusables[++tosReuslables] = ac;
+ }
+ // if more than 0 ordinals, add this AACO to the map to be returned,
+ // and add ords to sibling stack, and make a note in siblingExplored that these are to
+ // be visited now
+ if (ords.length > 0) {
+ AACOsOfOnePartition.put(ordinalStack[localDepth-1], new AACO(ords,vals,residue));
+ bestSignlingsStack[localDepth] = ords;
+ siblingExplored[localDepth] = ords.length-1;
+ ordinalStack[localDepth] = ords[ords.length-1];
+ } else {
+ // no ordinals siblings of tosOrdinal in current partition, move to the left of it
+ // tosOrdinal is already there (to the left of partition).
+ // make a note of it in siblingExplored
+ ordinalStack[localDepth] = tosOrdinal;
+ siblingExplored[localDepth] = -1;
+ }
+ continue;
+ } // endof we did not check the position of a valid ordinal wrt partition
+
+ // now tosOrdinal is a valid ordinal, inside partition or to the left of it, we need
+ // to push its kids on top of it, if not too deep.
+ // Make a note that we did not check them yet
+ if (localDepth >= depth) {
+ // localDepth == depth; current tos exhausted its possible children, mark this by pushing INVALID_ORDINAL
+ ordinalStack[++localDepth] = TaxonomyReader.INVALID_ORDINAL;
+ continue;
+ }
+ ordinalStack[++localDepth] = youngestChild[tosOrdinal];
+ siblingExplored[localDepth] = Integer.MAX_VALUE;
+ } // endof loop while stack is not empty
+
+ // now generate a TempFacetResult from AACOsOfOnePartition, and consider self.
+ IntermediateFacetResultWithHash tempFRWH = new IntermediateFacetResultWithHash(
+ facetRequest, AACOsOfOnePartition);
+ if (isSelfPartition(rootNode, arrays, offset)) {
+ tempFRWH.isRootNodeIncluded = true;
+ tempFRWH.rootNodeValue = this.facetRequest.getValueOf(arrays, rootNode % partitionSize);
+ }
+ tempFRWH.totalNumOfFacetsConsidered = totalNumOfDescendantsConsidered;
+ return tempFRWH;
+
+ }
+
+ /**
+ * Recursively count <code>ordinal</code>, whose depth is <code>currentDepth</code>,
+ * and all its descendants down to <code>maxDepth</code> (including),
+ * descendants whose value in the count arrays, <code>arrays</code>, is != 0.
+ * The count arrays only includes the current partition, from <code>offset</code>, to (exclusive)
+ * <code>endOffset</code>.
+ * It is assumed that <code>ordinal</code> < <code>endOffset</code>,
+ * otherwise, not <code>ordinal</code>, and none of its descendants, reside in
+ * the current partition. <code>ordinal</code> < <code>offset</code> is allowed,
+ * as ordinal's descendants might be >= <code>offeset</code>.
+ *
+ * @param ordinal a facet ordinal.
+ * @param youngestChild mapping a given ordinal to its youngest child in the taxonomy (of largest ordinal number),
+ * or to -1 if has no children.
+ * @param olderSibling mapping a given ordinal to its older sibling, or to -1
+ * @param arrays values for the ordinals in the given partition
+ * @param offset the first (smallest) ordinal in the given partition
+ * @param partitionSize number of ordinals in the given partition
+ * @param endOffset one larger than the largest ordinal that belong to this partition
+ * @param currentDepth the depth or ordinal in the TaxonomyTree (relative to rootnode of the facetRequest)
+ * @param maxDepth maximal depth of descendants to be considered here (measured relative to rootnode of the
+ * facetRequest).
+ *
+ * @return the number of nodes, from ordinal down its descendants, of depth <= maxDepth,
+ * which reside in the current partition, and whose value != 0
+ */
+ private int countOnly(int ordinal, int[] youngestChild, int[] olderSibling,
+ FacetArrays arrays, int partitionSize, int offset,
+ int endOffset, int currentDepth, int maxDepth) {
+ int ret = 0;
+ if (offset <= ordinal) {
+ // ordinal belongs to the current partition
+ if (0 != facetRequest.getValueOf(arrays, ordinal % partitionSize)) {
+ ret++;
+ }
+ }
+ // now consider children of ordinal, if not too deep
+ if (currentDepth >= maxDepth) {
+ return ret;
+ }
+
+ int yc = youngestChild[ordinal];
+ while (yc >= endOffset) {
+ yc = olderSibling[yc];
+ }
+ while (yc > TaxonomyReader.INVALID_ORDINAL) { // assuming this is -1, smaller than any legal ordinal
+ ret += countOnly (yc, youngestChild, olderSibling, arrays,
+ partitionSize, offset, endOffset, currentDepth+1, maxDepth);
+ yc = olderSibling[yc];
+ }
+ return ret;
+ }
+
+ /**
+ * Merge several partitions' {@link IntermediateFacetResult}-s into one of the
+ * same format
+ *
+ * @see FacetResultsHandler#mergeResults(IntermediateFacetResult...)
+ */
+ @Override
+ public IntermediateFacetResult mergeResults(IntermediateFacetResult... tmpResults)
+ throws ClassCastException, IllegalArgumentException {
+
+ if (tmpResults.length == 0) {
+ return null;
+ }
+
+ int i=0;
+ // skip over null tmpResults
+ for (; (i < tmpResults.length)&&(tmpResults[i] == null); i++) {}
+ if (i == tmpResults.length) {
+ // all inputs are null
+ return null;
+ }
+
+ // i points to the first non-null input
+ int K = this.facetRequest.getNumResults(); // number of best result in each node
+ IntermediateFacetResultWithHash tmpToReturn = (IntermediateFacetResultWithHash)tmpResults[i++];
+
+ // now loop over the rest of tmpResults and merge each into tmpToReturn
+ for ( ; i < tmpResults.length; i++) {
+ IntermediateFacetResultWithHash tfr = (IntermediateFacetResultWithHash)tmpResults[i];
+ tmpToReturn.totalNumOfFacetsConsidered += tfr.totalNumOfFacetsConsidered;
+ if (tfr.isRootNodeIncluded) {
+ tmpToReturn.isRootNodeIncluded = true;
+ tmpToReturn.rootNodeValue = tfr.rootNodeValue;
+ }
+ // now merge the HashMap of tfr into this of tmpToReturn
+ IntToObjectMap<AACO> tmpToReturnMapToACCOs = tmpToReturn.mapToAACOs;
+ IntToObjectMap<AACO> tfrMapToACCOs = tfr.mapToAACOs;
+ IntIterator tfrIntIterator = tfrMapToACCOs.keyIterator();
+ //iterate over all ordinals in tfr that are maps to their children (and the residue over
+ // non included chilren)
+ while (tfrIntIterator.hasNext()) {
+ int tfrkey = tfrIntIterator.next();
+ AACO tmpToReturnAACO = null;
+ if (null == (tmpToReturnAACO = tmpToReturnMapToACCOs.get(tfrkey))) {
+ // if tmpToReturn does not have any kids of tfrkey, map all the kids
+ // from tfr to it as one package, along with their redisude
+ tmpToReturnMapToACCOs.put(tfrkey, tfrMapToACCOs.get(tfrkey));
+ } else {
+ // merge the best K children of tfrkey as appear in tmpToReturn and in tfr
+ AACO tfrAACO = tfrMapToACCOs.get(tfrkey);
+ int resLength = tfrAACO.ordinals.length + tmpToReturnAACO.ordinals.length;
+ if (K < resLength) {
+ resLength = K;
+ }
+ int[] resOrds = new int [resLength];
+ double[] resVals = new double [resLength];
+ double resResidue = tmpToReturnAACO.residue + tfrAACO.residue;
+ int indexIntoTmpToReturn = 0;
+ int indexIntoTFR = 0;
+ ACComparator merger = getSuitableACComparator(); // by facet Request
+ for (int indexIntoRes = 0; indexIntoRes < resLength; indexIntoRes++) {
+ if (indexIntoTmpToReturn >= tmpToReturnAACO.ordinals.length) {
+ //tmpToReturnAACO (former result to return) ran out of indices
+ // it is all merged into resOrds and resVal
+ resOrds[indexIntoRes] = tfrAACO.ordinals[indexIntoTFR];
+ resVals[indexIntoRes] = tfrAACO.values[indexIntoTFR];
+ indexIntoTFR++;
+ continue;
+ }
+ if (indexIntoTFR >= tfrAACO.ordinals.length) {
+ // tfr ran out of indices
+ resOrds[indexIntoRes] = tmpToReturnAACO.ordinals[indexIntoTmpToReturn];
+ resVals[indexIntoRes] = tmpToReturnAACO.values[indexIntoTmpToReturn];
+ indexIntoTmpToReturn++;
+ continue;
+ }
+ // select which goes now to res: next (ord, value) from tmpToReturn or from tfr:
+ if (merger.leftGoesNow( tmpToReturnAACO.ordinals[indexIntoTmpToReturn],
+ tmpToReturnAACO.values[indexIntoTmpToReturn],
+ tfrAACO.ordinals[indexIntoTFR],
+ tfrAACO.values[indexIntoTFR])) {
+ resOrds[indexIntoRes] = tmpToReturnAACO.ordinals[indexIntoTmpToReturn];
+ resVals[indexIntoRes] = tmpToReturnAACO.values[indexIntoTmpToReturn];
+ indexIntoTmpToReturn++;
+ } else {
+ resOrds[indexIntoRes] = tfrAACO.ordinals[indexIntoTFR];
+ resVals[indexIntoRes] = tfrAACO.values[indexIntoTFR];
+ indexIntoTFR++;
+ }
+ } // end of merge of best kids of tfrkey that appear in tmpToReturn and its kids that appear in tfr
+ // altogether yielding no more that best K kids for tfrkey, not to appear in the new shape of
+ // tmpToReturn
+
+ while (indexIntoTmpToReturn < tmpToReturnAACO.ordinals.length) {
+ resResidue += tmpToReturnAACO.values[indexIntoTmpToReturn++];
+ }
+ while (indexIntoTFR < tfrAACO.ordinals.length) {
+ resResidue += tfrAACO.values[indexIntoTFR++];
+ }
+ //update the list of best kids of tfrkey as appear in tmpToReturn
+ tmpToReturnMapToACCOs.put(tfrkey, new AACO(resOrds, resVals, resResidue));
+ } // endof need to merge both AACO -- children and residue for same ordinal
+
+ } // endof loop over all ordinals in tfr
+ } // endof loop over all temporary facet results to merge
+
+ return tmpToReturn;
+ }
+
+ private static class AggregatedCategoryHeap extends PriorityQueue<AggregatedCategory> {
+
+ private ACComparator merger;
+ public AggregatedCategoryHeap(int size, ACComparator merger) {
+ this.merger = merger;
+ initialize(size);
+ }
+
+ @Override
+ protected boolean lessThan(AggregatedCategory arg1, AggregatedCategory arg2) {
+ return merger.leftGoesNow(arg2.ordinal, arg2.value, arg1.ordinal, arg1.value);
+ }
+
+ }
+
+ private static class ResultNodeHeap extends PriorityQueue<FacetResultNode> {
+ private ACComparator merger;
+ public ResultNodeHeap(int size, ACComparator merger) {
+ this.merger = merger;
+ initialize(size);
+ }
+
+ @Override
+ protected boolean lessThan(FacetResultNode arg1, FacetResultNode arg2) {
+ return merger.leftGoesNow(arg2.getOrdinal(), arg2.getValue(), arg1.getOrdinal(), arg1.getValue());
+ }
+
+ }
+
+ /**
+ * @return the {@link ACComparator} that reflects the order,
+ * expressed in the {@link FacetRequest}, of
+ * facets in the {@link FacetResult}.
+ */
+
+ private ACComparator getSuitableACComparator() {
+ if (facetRequest.getSortOrder() == SortOrder.ASCENDING) {
+ switch (facetRequest.getSortBy()) {
+ case VALUE:
+ return new AscValueACComparator();
+ case ORDINAL:
+ return new AscOrdACComparator();
+ }
+ } else {
+ switch (facetRequest.getSortBy()) {
+ case VALUE:
+ return new DescValueACComparator();
+ case ORDINAL:
+ return new DescOrdACComparator();
+ }
+ }
+ return null;
+ }
+
+ /**
+ * A comparator of two Aggregated Categories according to the order
+ * (ascending / descending) and item (ordinal or value) specified in the
+ * FacetRequest for the FacetResult to be generated
+ */
+
+ private static abstract class ACComparator {
+ ACComparator() { }
+ protected abstract boolean leftGoesNow (int ord1, double val1, int ord2, double val2);
+ }
+
+ private static final class AscValueACComparator extends ACComparator {
+
+ AscValueACComparator() { }
+
+ @Override
+ protected boolean leftGoesNow (int ord1, double val1, int ord2, double val2) {
+ return (val1 < val2);
+ }
+ }
+
+ private static final class DescValueACComparator extends ACComparator {
+
+ DescValueACComparator() { }
+
+ @Override
+ protected boolean leftGoesNow (int ord1, double val1, int ord2, double val2) {
+ return (val1 > val2);
+ }
+ }
+
+ private static final class AscOrdACComparator extends ACComparator {
+
+ AscOrdACComparator() { }
+
+ @Override
+ protected boolean leftGoesNow (int ord1, double val1, int ord2, double val2) {
+ return (ord1 < ord2);
+ }
+ }
+
+ private static final class DescOrdACComparator extends ACComparator {
+
+ DescOrdACComparator() { }
+
+ @Override
+ protected boolean leftGoesNow (int ord1, double val1, int ord2, double val2) {
+ return (ord1 > ord2);
+ }
+ }
+
+ /**
+ * Intermediate result to hold counts from one or more partitions processed
+ * thus far. Its main field, constructor parameter <i>mapToAACOs</i>, is a map
+ * from ordinals to AACOs. The AACOs mapped to contain ordinals and values
+ * encountered in the count arrays of the partitions processed thus far. The
+ * ordinals mapped from are their parents, and they may be not contained in
+ * the partitions processed thus far. All nodes belong to the taxonomy subtree
+ * defined at the facet request, constructor parameter <i>facetReq</i>, by its
+ * root and depth.
+ */
+ public static class IntermediateFacetResultWithHash implements IntermediateFacetResult {
+ protected IntToObjectMap<AACO> mapToAACOs;
+ FacetRequest facetRequest;
+ boolean isRootNodeIncluded; // among the ordinals in the partitions
+ // processed thus far
+ double rootNodeValue; // the value of it, in case encountered.
+ int totalNumOfFacetsConsidered; // total number of facets
+ // which belong to facetRequest subtree and have value != 0,
+ // and have been encountered thus far in the partitions processed.
+ // root node of result tree is not included in this count.
+
+ public IntermediateFacetResultWithHash(FacetRequest facetReq,
+ IntToObjectMap<AACO> mapToAACOs) {
+ this.mapToAACOs = mapToAACOs;
+ this.facetRequest = facetReq;
+ this.isRootNodeIncluded = false;
+ this.rootNodeValue = 0.0;
+ this.totalNumOfFacetsConsidered = 0;
+ }
+
+ public FacetRequest getFacetRequest() {
+ return this.facetRequest;
+ }
+ } // endof FacetResultWithHash
+
+ /**
+ * Maintains info of one entry in the filled up count array:
+ * an ordinal number of a category and the value aggregated for it
+ * (typically, that value is the count for that ordinal).
+ */
+ private static final class AggregatedCategory {
+ int ordinal;
+ double value;
+ AggregatedCategory(int ord, double val) {
+ this.ordinal = ord;
+ this.value = val;
+ }
+ }
+
+ /**
+ * Maintains an array of {@link AggregatedCategory}. For space consideration, this is implemented as
+ * a pair of arrays, <i>ordinals</i> and <i>values</i>, rather than one array of pairs.
+ * Enumerated in <i>ordinals</i> are siblings,
+ * potential nodes of the {@link FacetResult} tree
+ * (i.e., the descendants of the root node, no deeper than the specified depth).
+ * No more than K ( = {@link FacetRequest#getNumResults()})
+ * siblings are enumerated, and
+ * <i>residue</i> holds the sum of values of the siblings rejected from the
+ * enumerated top K.
+ */
+ private static final class AACO {
+ int [] ordinals; // ordinals of the best K children, sorted from best to least
+ double [] values; // the respective values for these children
+ double residue; // sum of values of all other children, that did not get into top K
+ AACO (int[] ords, double[] vals, double r) {
+ this.ordinals = ords;
+ this.values = vals;
+ this.residue = r;
+ }
+ }
+
+ @Override
+ /**
+ * Recursively label the first facetRequest.getNumLabel() sub results
+ * of the root of a given {@link FacetResult}, or of an already labeled node in it.
+ * I.e., a node is labeled only if it is the root or all its ancestors are labeled.
+ */
+ public void labelResult(FacetResult facetResult) throws IOException {
+ if (facetResult == null) {
+ return; // any result to label?
+ }
+ FacetResultNode rootNode = facetResult.getFacetResultNode();
+ recursivelyLabel(rootNode, facetRequest.getNumLabel());
+ }
+
+ private void recursivelyLabel(FacetResultNode node, int numToLabel) throws IOException {
+ if (node == null) {
+ return;
+ }
+ node.getLabel(this.taxonomyReader); // attach a label -- category path -- to the node
+ if (null == node.getSubResults()) {
+ return; // if node has no children -- done
+ }
+
+ // otherwise, label the first numToLabel of these children, and recursively -- their children.
+ int numLabeled = 0;
+ for (FacetResultNode frn : node.getSubResults()) {
+ // go over the children of node from first to last, no more than numToLable of them
+ recursivelyLabel(frn, numToLabel);
+ if (++numLabeled >= numToLabel) {
+ return;
+ }
+ }
+ }
+
+ @Override
+ // verifies that the children of each node are sorted by the order
+ // specified by the facetRequest.
+ // the values in these nodes may have changed due to a re-count, for example
+ // following the accumulation by Sampling.
+ // so now we test and re-order if necessary.
+ public FacetResult rearrangeFacetResult(FacetResult facetResult) {
+ PriorityQueue<FacetResultNode> nodesHeap =
+ new ResultNodeHeap(this.facetRequest.getNumResults(), this.getSuitableACComparator());
+ MutableFacetResultNode topFrn = (MutableFacetResultNode) facetResult.getFacetResultNode(); // safe cast
+ rearrangeChilrenOfNode(topFrn, nodesHeap);
+ return facetResult;
+ }
+
+ private void rearrangeChilrenOfNode(FacetResultNode node,
+ PriorityQueue<FacetResultNode> nodesHeap) {
+ nodesHeap.clear(); // just to be safe
+ for (FacetResultNode frn : node.getSubResults()) {
+ nodesHeap.add(frn);
+ }
+ int size = nodesHeap.size();
+ ArrayList<FacetResultNode> subResults = new ArrayList<FacetResultNode>(size);
+ while (nodesHeap.size()>0) {
+ subResults.add(0,nodesHeap.pop());
+ }
+ ((MutableFacetResultNode)node).setSubResults(subResults);
+ for (FacetResultNode frn : node.getSubResults()) {
+ rearrangeChilrenOfNode(frn, nodesHeap);
+ }
+
+ }
+
+ @Override
+ public FacetResult renderFacetResult(IntermediateFacetResult tmpResult) throws IOException {
+ IntermediateFacetResultWithHash tmp = (IntermediateFacetResultWithHash) tmpResult;
+ int ordinal = this.taxonomyReader.getOrdinal(this.facetRequest.getCategoryPath());
+ if ((tmp == null) || (ordinal == TaxonomyReader.INVALID_ORDINAL)) {
+ return null;
+ }
+ double value = Double.NaN;
+ if (tmp.isRootNodeIncluded) {
+ value = tmp.rootNodeValue;
+ }
+ MutableFacetResultNode root = generateNode (ordinal, value, tmp.mapToAACOs);
+ return new FacetResult (tmp.facetRequest, root, tmp.totalNumOfFacetsConsidered);
+
+ }
+
+ private MutableFacetResultNode generateNode (int ordinal, double val, IntToObjectMap<AACO> mapToAACOs) {
+ MutableFacetResultNode node = new MutableFacetResultNode(ordinal, val);
+ AACO aaco = mapToAACOs.get(ordinal);
+ if (null == aaco) {
+ return node;
+ }
+ List<FacetResultNode> list = new ArrayList<FacetResultNode>();
+ for (int i = 0; i < aaco.ordinals.length; i++) {
+ list.add(generateNode(aaco.ordinals[i], aaco.values[i], mapToAACOs));
+ }
+ node.setSubResults(list);
+ node.setResidue(aaco.residue);
+ return node;
+ }
+
+}
fnp / pylucene.git / blobdiff