You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by pa...@apache.org on 2013/11/07 14:53:52 UTC
[37/53] [abbrv] Port much of Facet.Search and some others
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/318dea52/src/contrib/Facet/Search/StandardFacetsAccumulator.cs
----------------------------------------------------------------------
diff --git a/src/contrib/Facet/Search/StandardFacetsAccumulator.cs b/src/contrib/Facet/Search/StandardFacetsAccumulator.cs
new file mode 100644
index 0000000..b979ac2
--- /dev/null
+++ b/src/contrib/Facet/Search/StandardFacetsAccumulator.cs
@@ -0,0 +1,308 @@
+using Lucene.Net.Facet.Complements;
+using Lucene.Net.Facet.Params;
+using Lucene.Net.Facet.Partitions;
+using Lucene.Net.Facet.Taxonomy;
+using Lucene.Net.Facet.Util;
+using Lucene.Net.Index;
+using Lucene.Net.Support;
+using Lucene.Net.Util;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.IO;
+using System.Linq;
+using System.Text;
+
+namespace Lucene.Net.Facet.Search
+{
+ public class StandardFacetsAccumulator : FacetsAccumulator
+ {
+ //private static readonly Logger logger = Logger.GetLogger(typeof(StandardFacetsAccumulator).GetName());
+ public static readonly double DEFAULT_COMPLEMENT_THRESHOLD = 0.6;
+ public static readonly double DISABLE_COMPLEMENT = double.PositiveInfinity;
+ public static readonly double FORCE_COMPLEMENT = 0;
+ protected int partitionSize;
+ protected int maxPartitions;
+ protected bool isUsingComplements;
+ private TotalFacetCounts totalFacetCounts;
+ private Object accumulateGuard;
+ private double complementThreshold;
+
+ public StandardFacetsAccumulator(FacetSearchParams searchParams, IndexReader indexReader, TaxonomyReader taxonomyReader)
+ : this(searchParams, indexReader, taxonomyReader, new FacetArrays(PartitionsUtils.PartitionSize(searchParams.indexingParams, taxonomyReader)))
+ {
+ }
+
+ public StandardFacetsAccumulator(FacetSearchParams searchParams, IndexReader indexReader, TaxonomyReader taxonomyReader, FacetArrays facetArrays)
+ : base(searchParams, indexReader, taxonomyReader, facetArrays)
+ {
+ isUsingComplements = false;
+ partitionSize = PartitionsUtils.PartitionSize(searchParams.indexingParams, taxonomyReader);
+ maxPartitions = (int)Math.Ceiling(this.taxonomyReader.Size / (double)partitionSize);
+ accumulateGuard = new Object();
+ }
+
+ public virtual List<FacetResult> Accumulate(IScoredDocIDs docids)
+ {
+ lock (accumulateGuard)
+ {
+ isUsingComplements = ShouldComplement(docids);
+ if (isUsingComplements)
+ {
+ try
+ {
+ totalFacetCounts = TotalFacetCountsCache.GetSingleton().GetTotalCounts(indexReader, taxonomyReader, searchParams.indexingParams);
+ if (totalFacetCounts != null)
+ {
+ docids = ScoredDocIdsUtils.GetComplementSet(docids, indexReader);
+ }
+ else
+ {
+ isUsingComplements = false;
+ }
+ }
+ catch (NotSupportedException e)
+ {
+ Debug.WriteLine("IndexReader used does not support completents: {0}", e);
+
+ isUsingComplements = false;
+ }
+ catch (IOException e)
+ {
+ Debug.WriteLine("Failed to load/calculate total counts (complement counting disabled): {0}", e);
+
+ isUsingComplements = false;
+ }
+ catch (Exception e)
+ {
+ throw new IOException("PANIC: Got unexpected exception while trying to get/calculate total counts", e);
+ }
+ }
+
+ docids = ActualDocsToAccumulate(docids);
+ HashMap<FacetRequest, IIntermediateFacetResult> fr2tmpRes = new HashMap<FacetRequest, IIntermediateFacetResult>();
+ try
+ {
+ for (int part = 0; part < maxPartitions; part++)
+ {
+ FillArraysForPartition(docids, facetArrays, part);
+ int offset = part * partitionSize;
+ HashSet<FacetRequest> handledRequests = new HashSet<FacetRequest>();
+ foreach (FacetRequest fr in searchParams.facetRequests)
+ {
+ if (handledRequests.Add(fr))
+ {
+ PartitionsFacetResultsHandler frHndlr = (PartitionsFacetResultsHandler)CreateFacetResultsHandler(fr);
+ IIntermediateFacetResult res4fr = frHndlr.FetchPartitionResult(offset);
+ IIntermediateFacetResult oldRes = fr2tmpRes[fr];
+ if (oldRes != null)
+ {
+ res4fr = frHndlr.MergeResults(oldRes, res4fr);
+ }
+
+ fr2tmpRes[fr] = res4fr;
+ }
+ }
+ }
+ }
+ finally
+ {
+ facetArrays.Free();
+ }
+
+ List<FacetResult> res = new List<FacetResult>();
+ foreach (FacetRequest fr in searchParams.facetRequests)
+ {
+ PartitionsFacetResultsHandler frHndlr = (PartitionsFacetResultsHandler)CreateFacetResultsHandler(fr);
+ IIntermediateFacetResult tmpResult = fr2tmpRes[fr];
+ if (tmpResult == null)
+ {
+ res.Add(EmptyResult(taxonomyReader.GetOrdinal(fr.categoryPath), fr));
+ continue;
+ }
+
+ FacetResult facetRes = frHndlr.RenderFacetResult(tmpResult);
+ frHndlr.LabelResult(facetRes);
+ res.Add(facetRes);
+ }
+
+ return res;
+ }
+ }
+
+ protected virtual bool MayComplement()
+ {
+ foreach (FacetRequest freq in searchParams.facetRequests)
+ {
+ if (!(freq is CountFacetRequest))
+ {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ protected override FacetResultsHandler CreateFacetResultsHandler(FacetRequest fr)
+ {
+ if (fr.ResultModeValue == FacetRequest.ResultMode.PER_NODE_IN_TREE)
+ {
+ return new TopKInEachNodeHandler(taxonomyReader, fr, facetArrays);
+ }
+ else
+ {
+ return new TopKFacetResultsHandler(taxonomyReader, fr, facetArrays);
+ }
+ }
+
+ protected virtual IScoredDocIDs ActualDocsToAccumulate(IScoredDocIDs docids)
+ {
+ return docids;
+ }
+
+ protected virtual bool ShouldComplement(IScoredDocIDs docids)
+ {
+ return MayComplement() && (docids.Size > indexReader.NumDocs * ComplementThreshold);
+ }
+
+ private void FillArraysForPartition(IScoredDocIDs docids, FacetArrays facetArrays, int partition)
+ {
+ if (isUsingComplements)
+ {
+ InitArraysByTotalCounts(facetArrays, partition, docids.Size);
+ }
+ else
+ {
+ facetArrays.Free();
+ }
+
+ HashMap<ICategoryListIterator, IAggregator> categoryLists = GetCategoryListMap(facetArrays, partition);
+ IntsRef ordinals = new IntsRef(32);
+ foreach (var entry in categoryLists)
+ {
+ IScoredDocIDsIterator iterator = docids.Iterator();
+ ICategoryListIterator categoryListIter = entry.Key;
+ IAggregator aggregator = entry.Value;
+ IEnumerator<AtomicReaderContext> contexts = indexReader.Leaves.GetEnumerator();
+ AtomicReaderContext current = null;
+ int maxDoc = -1;
+ while (iterator.Next())
+ {
+ int docID = iterator.DocID;
+ if (docID >= maxDoc)
+ {
+ bool iteratorDone = false;
+ do
+ {
+ if (!contexts.MoveNext())
+ {
+ throw new Exception(@"ScoredDocIDs contains documents outside this reader's segments !?");
+ }
+
+ current = contexts.Current;
+ maxDoc = current.docBase + current.Reader.MaxDoc;
+ if (docID < maxDoc)
+ {
+ bool validSegment = categoryListIter.SetNextReader(current);
+ validSegment &= aggregator.SetNextReader(current);
+ if (!validSegment)
+ {
+ while (docID < maxDoc && iterator.Next())
+ {
+ docID = iterator.DocID;
+ }
+
+ if (docID < maxDoc)
+ {
+ iteratorDone = true;
+ }
+ }
+ }
+ }
+ while (docID >= maxDoc);
+ if (iteratorDone)
+ {
+ break;
+ }
+ }
+
+ docID -= current.docBase;
+ categoryListIter.GetOrdinals(docID, ordinals);
+ if (ordinals.length == 0)
+ {
+ continue;
+ }
+
+ aggregator.Aggregate(docID, iterator.Score, ordinals);
+ }
+ }
+ }
+
+ private void InitArraysByTotalCounts(FacetArrays facetArrays, int partition, int nAccumulatedDocs)
+ {
+ int[] intArray = facetArrays.GetIntArray();
+ totalFacetCounts.FillTotalCountsForPartition(intArray, partition);
+ double totalCountsFactor = TotalCountsFactor;
+ if (totalCountsFactor < 1.0)
+ {
+ int delta = nAccumulatedDocs + 1;
+ for (int i = 0; i < intArray.Length; i++)
+ {
+ intArray[i] *= (int)totalCountsFactor;
+ intArray[i] += delta;
+ }
+ }
+ }
+
+ protected virtual double TotalCountsFactor
+ {
+ get
+ {
+ return 1;
+ }
+ }
+
+ protected virtual HashMap<ICategoryListIterator, IAggregator> GetCategoryListMap(FacetArrays facetArrays, int partition)
+ {
+ HashMap<ICategoryListIterator, IAggregator> categoryLists = new HashMap<ICategoryListIterator, IAggregator>();
+ FacetIndexingParams indexingParams = searchParams.indexingParams;
+ foreach (FacetRequest facetRequest in searchParams.facetRequests)
+ {
+ IAggregator categoryAggregator = facetRequest.CreateAggregator(isUsingComplements, facetArrays, taxonomyReader);
+ ICategoryListIterator cli = indexingParams.GetCategoryListParams(facetRequest.categoryPath).CreateCategoryListIterator(partition);
+ IAggregator old = categoryLists[cli] = categoryAggregator;
+ if (old != null && !old.Equals(categoryAggregator))
+ {
+ throw new Exception(@"Overriding existing category list with different aggregator");
+ }
+ }
+
+ return categoryLists;
+ }
+
+ public override List<FacetResult> Accumulate(List<FacetsCollector.MatchingDocs> matchingDocs)
+ {
+ return Accumulate(new MatchingDocsAsScoredDocIDs(matchingDocs));
+ }
+
+ public virtual double ComplementThreshold
+ {
+ get
+ {
+ return complementThreshold;
+ }
+ set
+ {
+ this.complementThreshold = value;
+ }
+ }
+
+ public virtual bool IsUsingComplements
+ {
+ get
+ {
+ return isUsingComplements;
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/318dea52/src/contrib/Facet/Search/TopKFacetResultsHandler.cs
----------------------------------------------------------------------
diff --git a/src/contrib/Facet/Search/TopKFacetResultsHandler.cs b/src/contrib/Facet/Search/TopKFacetResultsHandler.cs
new file mode 100644
index 0000000..7ff67fd
--- /dev/null
+++ b/src/contrib/Facet/Search/TopKFacetResultsHandler.cs
@@ -0,0 +1,227 @@
+using Lucene.Net.Facet.Partitions;
+using Lucene.Net.Facet.Taxonomy;
+using Lucene.Net.Facet.Util;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace Lucene.Net.Facet.Search
+{
+ public class TopKFacetResultsHandler : PartitionsFacetResultsHandler
+ {
+ public TopKFacetResultsHandler(TaxonomyReader taxonomyReader, FacetRequest facetRequest, FacetArrays facetArrays)
+ : base(taxonomyReader, facetRequest, facetArrays)
+ {
+ }
+
+ public override IIntermediateFacetResult FetchPartitionResult(int offset)
+ {
+ TopKFacetResult res = null;
+ int ordinal = taxonomyReader.GetOrdinal(facetRequest.categoryPath);
+ if (ordinal != TaxonomyReader.INVALID_ORDINAL)
+ {
+ double value = 0;
+ if (IsSelfPartition(ordinal, facetArrays, offset))
+ {
+ int partitionSize = facetArrays.arrayLength;
+ value = facetRequest.GetValueOf(facetArrays, ordinal % partitionSize);
+ }
+
+ FacetResultNode parentResultNode = new FacetResultNode(ordinal, value);
+ IHeap<FacetResultNode> heap = ResultSortUtils.CreateSuitableHeap(facetRequest);
+ int totalFacets = HeapDescendants(ordinal, heap, parentResultNode, offset);
+ res = new TopKFacetResult(facetRequest, parentResultNode, totalFacets);
+ res.SetHeap(heap);
+ }
+
+ return res;
+ }
+
+ public override IIntermediateFacetResult MergeResults(params IIntermediateFacetResult[] tmpResults)
+ {
+ int ordinal = taxonomyReader.GetOrdinal(facetRequest.categoryPath);
+ FacetResultNode resNode = new FacetResultNode(ordinal, 0);
+ int totalFacets = 0;
+ IHeap<FacetResultNode> heap = null;
+ foreach (IIntermediateFacetResult tmpFres in tmpResults)
+ {
+ TopKFacetResult fres = (TopKFacetResult)tmpFres;
+ totalFacets += fres.NumValidDescendants;
+ resNode.value += fres.FacetResultNode.value;
+ IHeap<FacetResultNode> tmpHeap = fres.GetHeap();
+ if (heap == null)
+ {
+ heap = tmpHeap;
+ continue;
+ }
+
+ for (int i = tmpHeap.Size; i > 0; i--)
+ {
+ heap.InsertWithOverflow(tmpHeap.Pop());
+ }
+ }
+
+ TopKFacetResult res = new TopKFacetResult(facetRequest, resNode, totalFacets);
+ res.SetHeap(heap);
+ return res;
+ }
+
+ private int HeapDescendants(int ordinal, IHeap<FacetResultNode> pq, FacetResultNode parentResultNode, int offset)
+ {
+ int partitionSize = facetArrays.arrayLength;
+ int endOffset = offset + partitionSize;
+ ParallelTaxonomyArrays childrenArray = taxonomyReader.ParallelTaxonomyArrays;
+ int[] children = childrenArray.Children;
+ int[] siblings = childrenArray.Siblings;
+ FacetResultNode reusable = null;
+ int localDepth = 0;
+ int depth = facetRequest.Depth;
+ int[] ordinalStack = new int[2 + Math.Min(short.MaxValue, depth)];
+ int childrenCounter = 0;
+ int tosOrdinal;
+ int yc = children[ordinal];
+ while (yc >= endOffset)
+ {
+ yc = siblings[yc];
+ }
+
+ ordinalStack[++localDepth] = yc;
+ while (localDepth > 0)
+ {
+ tosOrdinal = ordinalStack[localDepth];
+ if (tosOrdinal == TaxonomyReader.INVALID_ORDINAL)
+ {
+ localDepth--;
+ ordinalStack[localDepth] = siblings[ordinalStack[localDepth]];
+ continue;
+ }
+
+ if (tosOrdinal >= offset)
+ {
+ int relativeOrdinal = tosOrdinal % partitionSize;
+ double value = facetRequest.GetValueOf(facetArrays, relativeOrdinal);
+ if (value != 0 && !Double.IsNaN(value))
+ {
+ if (reusable == null)
+ {
+ reusable = new FacetResultNode(tosOrdinal, value);
+ }
+ else
+ {
+ reusable.ordinal = tosOrdinal;
+ reusable.value = value;
+ reusable.subResults.Clear();
+ reusable.label = null;
+ }
+
+ ++childrenCounter;
+ reusable = pq.InsertWithOverflow(reusable);
+ }
+ }
+
+ if (localDepth < depth)
+ {
+ yc = children[tosOrdinal];
+ while (yc >= endOffset)
+ {
+ yc = siblings[yc];
+ }
+
+ ordinalStack[++localDepth] = yc;
+ }
+ else
+ {
+ ordinalStack[++localDepth] = TaxonomyReader.INVALID_ORDINAL;
+ }
+ }
+
+ return childrenCounter;
+ }
+
+ public override FacetResult RenderFacetResult(IIntermediateFacetResult tmpResult)
+ {
+ TopKFacetResult res = (TopKFacetResult)tmpResult;
+ if (res != null)
+ {
+ IHeap<FacetResultNode> heap = res.GetHeap();
+ FacetResultNode resNode = res.FacetResultNode;
+ if (resNode.subResults == FacetResultNode.EMPTY_SUB_RESULTS)
+ {
+ resNode.subResults = new List<FacetResultNode>();
+ }
+
+ for (int i = heap.Size; i > 0; i--)
+ {
+ resNode.subResults.Insert(0, heap.Pop());
+ }
+ }
+
+ return res;
+ }
+
+ public override FacetResult RearrangeFacetResult(FacetResult facetResult)
+ {
+ TopKFacetResult res = (TopKFacetResult)facetResult;
+ IHeap<FacetResultNode> heap = res.GetHeap();
+ heap.Clear();
+ FacetResultNode topFrn = res.FacetResultNode;
+ foreach (FacetResultNode frn in topFrn.subResults)
+ {
+ heap.Add(frn);
+ }
+
+ int size = heap.Size;
+ List<FacetResultNode> subResults = new List<FacetResultNode>(size);
+ for (int i = heap.Size; i > 0; i--)
+ {
+ subResults.Insert(0, heap.Pop());
+ }
+
+ topFrn.subResults = subResults;
+ return res;
+ }
+
+ public override void LabelResult(FacetResult facetResult)
+ {
+ if (facetResult != null)
+ {
+ FacetResultNode facetResultNode = facetResult.FacetResultNode;
+ if (facetResultNode != null)
+ {
+ facetResultNode.label = taxonomyReader.GetPath(facetResultNode.ordinal);
+ int num2label = facetRequest.NumLabel;
+ foreach (FacetResultNode frn in facetResultNode.subResults)
+ {
+ if (--num2label < 0)
+ {
+ break;
+ }
+
+ frn.label = taxonomyReader.GetPath(frn.ordinal);
+ }
+ }
+ }
+ }
+
+ private class TopKFacetResult : FacetResult, IIntermediateFacetResult
+ {
+ private IHeap<FacetResultNode> heap;
+
+ internal TopKFacetResult(FacetRequest facetRequest, FacetResultNode facetResultNode, int totalFacets)
+ : base(facetRequest, facetResultNode, totalFacets)
+ {
+ }
+
+ public virtual IHeap<FacetResultNode> GetHeap()
+ {
+ return heap;
+ }
+
+ public virtual void SetHeap(IHeap<FacetResultNode> heap)
+ {
+ this.heap = heap;
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/318dea52/src/contrib/Facet/Search/TopKInEachNodeHandler.cs
----------------------------------------------------------------------
diff --git a/src/contrib/Facet/Search/TopKInEachNodeHandler.cs b/src/contrib/Facet/Search/TopKInEachNodeHandler.cs
new file mode 100644
index 0000000..d09d3a4
--- /dev/null
+++ b/src/contrib/Facet/Search/TopKInEachNodeHandler.cs
@@ -0,0 +1,520 @@
+using Lucene.Net.Facet.Collections;
+using Lucene.Net.Facet.Partitions;
+using Lucene.Net.Facet.Taxonomy;
+using Lucene.Net.Util;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace Lucene.Net.Facet.Search
+{
+ public class TopKInEachNodeHandler : PartitionsFacetResultsHandler
+ {
+ public TopKInEachNodeHandler(TaxonomyReader taxonomyReader, FacetRequest facetRequest, FacetArrays facetArrays)
+ : base(taxonomyReader, facetRequest, facetArrays)
+ {
+ }
+
+ public override IIntermediateFacetResult FetchPartitionResult(int offset)
+ {
+ int rootNode = this.taxonomyReader.GetOrdinal(facetRequest.categoryPath);
+ if (rootNode == TaxonomyReader.INVALID_ORDINAL)
+ {
+ return null;
+ }
+
+ int K = Math.Min(facetRequest.numResults, taxonomyReader.Size);
+ IntToObjectMap<AACO> AACOsOfOnePartition = new IntToObjectMap<AACO>();
+ int partitionSize = facetArrays.arrayLength;
+ int depth = facetRequest.Depth;
+ if (depth == 0)
+ {
+ IntermediateFacetResultWithHash tempFRWH = new IntermediateFacetResultWithHash(facetRequest, AACOsOfOnePartition);
+ if (IsSelfPartition(rootNode, facetArrays, offset))
+ {
+ tempFRWH.isRootNodeIncluded = true;
+ tempFRWH.rootNodeValue = this.facetRequest.GetValueOf(facetArrays, rootNode % partitionSize);
+ }
+
+ return tempFRWH;
+ }
+
+ if (depth > short.MaxValue - 3)
+ {
+ depth = short.MaxValue - 3;
+ }
+
+ int endOffset = offset + partitionSize;
+ ParallelTaxonomyArrays childrenArray = taxonomyReader.ParallelTaxonomyArrays;
+ int[] children = childrenArray.Children;
+ int[] siblings = childrenArray.Siblings;
+ int totalNumOfDescendantsConsidered = 0;
+ PriorityQueue<AggregatedCategory> pq = new AggregatedCategoryHeap(K, this.GetSuitableACComparator());
+ AggregatedCategory[] reusables = new AggregatedCategory[2 + K];
+ for (int i = 0; i < reusables.Length; i++)
+ {
+ reusables[i] = new AggregatedCategory(1, 0);
+ }
+
+ int[] ordinalStack = new int[depth + 2];
+ ordinalStack[0] = rootNode;
+ int localDepth = 0;
+ int[][] bestSignlingsStack = new int[depth + 2][];
+ int[] siblingExplored = new int[depth + 2];
+ int[] firstToTheLeftOfPartition = new int[depth + 2];
+ int tosOrdinal;
+ ordinalStack[++localDepth] = children[rootNode];
+ siblingExplored[localDepth] = int.MaxValue;
+ siblingExplored[0] = -1;
+ while (localDepth > 0)
+ {
+ tosOrdinal = ordinalStack[localDepth];
+ if (tosOrdinal == TaxonomyReader.INVALID_ORDINAL)
+ {
+ localDepth--;
+ if (siblingExplored[localDepth] < 0)
+ {
+ ordinalStack[localDepth] = siblings[ordinalStack[localDepth]];
+ continue;
+ }
+
+ siblingExplored[localDepth]--;
+ if (siblingExplored[localDepth] == -1)
+ {
+ ordinalStack[localDepth] = firstToTheLeftOfPartition[localDepth];
+ }
+ else
+ {
+ ordinalStack[localDepth] = bestSignlingsStack[localDepth][siblingExplored[localDepth]];
+ }
+
+ continue;
+ }
+
+ if (siblingExplored[localDepth] == int.MaxValue)
+ {
+ while (tosOrdinal >= endOffset)
+ {
+ tosOrdinal = siblings[tosOrdinal];
+ }
+
+ pq.Clear();
+ int tosReuslables = reusables.Length - 1;
+ while (tosOrdinal >= offset)
+ {
+ double value = facetRequest.GetValueOf(facetArrays, tosOrdinal % partitionSize);
+ if (value != 0)
+ {
+ totalNumOfDescendantsConsidered++;
+ AggregatedCategory ac = reusables[tosReuslables--];
+ ac.ordinal = tosOrdinal;
+ ac.value = value;
+ ac = pq.InsertWithOverflow(ac);
+ if (null != ac)
+ {
+ totalNumOfDescendantsConsidered--;
+ totalNumOfDescendantsConsidered += CountOnly(ac.ordinal, children, siblings, partitionSize, offset, endOffset, localDepth, depth);
+ reusables[++tosReuslables] = ac;
+ }
+ }
+
+ tosOrdinal = siblings[tosOrdinal];
+ }
+
+ 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 (ords.Length > 0)
+ {
+ AACOsOfOnePartition.Put(ordinalStack[localDepth - 1], new AACO(ords, vals));
+ bestSignlingsStack[localDepth] = ords;
+ siblingExplored[localDepth] = ords.Length - 1;
+ ordinalStack[localDepth] = ords[ords.Length - 1];
+ }
+ else
+ {
+ ordinalStack[localDepth] = tosOrdinal;
+ siblingExplored[localDepth] = -1;
+ }
+
+ continue;
+ }
+
+ if (localDepth >= depth)
+ {
+ ordinalStack[++localDepth] = TaxonomyReader.INVALID_ORDINAL;
+ continue;
+ }
+
+ ordinalStack[++localDepth] = children[tosOrdinal];
+ siblingExplored[localDepth] = int.MaxValue;
+ }
+
+ IntermediateFacetResultWithHash tempFRWH2 = new IntermediateFacetResultWithHash(facetRequest, AACOsOfOnePartition);
+ if (IsSelfPartition(rootNode, facetArrays, offset))
+ {
+ tempFRWH2.isRootNodeIncluded = true;
+ tempFRWH2.rootNodeValue = this.facetRequest.GetValueOf(facetArrays, rootNode % partitionSize);
+ }
+
+ tempFRWH2.totalNumOfFacetsConsidered = totalNumOfDescendantsConsidered;
+ return tempFRWH2;
+ }
+
+ private int CountOnly(int ordinal, int[] youngestChild, int[] olderSibling, int partitionSize, int offset, int endOffset, int currentDepth, int maxDepth)
+ {
+ int ret = 0;
+ if (offset <= ordinal)
+ {
+ if (0 != facetRequest.GetValueOf(facetArrays, ordinal % partitionSize))
+ {
+ ret++;
+ }
+ }
+
+ if (currentDepth >= maxDepth)
+ {
+ return ret;
+ }
+
+ int yc = youngestChild[ordinal];
+ while (yc >= endOffset)
+ {
+ yc = olderSibling[yc];
+ }
+
+ while (yc > TaxonomyReader.INVALID_ORDINAL)
+ {
+ ret += CountOnly(yc, youngestChild, olderSibling, partitionSize, offset, endOffset, currentDepth + 1, maxDepth);
+ yc = olderSibling[yc];
+ }
+
+ return ret;
+ }
+
+ public override IIntermediateFacetResult MergeResults(params IIntermediateFacetResult[] tmpResults)
+ {
+ if (tmpResults.Length == 0)
+ {
+ return null;
+ }
+
+ int i = 0;
+ for (; (i < tmpResults.Length) && (tmpResults[i] == null); i++)
+ {
+ }
+
+ if (i == tmpResults.Length)
+ {
+ return null;
+ }
+
+ int K = this.facetRequest.numResults;
+ IntermediateFacetResultWithHash tmpToReturn = (IntermediateFacetResultWithHash)tmpResults[i++];
+ for (; i < tmpResults.Length; i++)
+ {
+ IntermediateFacetResultWithHash tfr = (IntermediateFacetResultWithHash)tmpResults[i];
+ tmpToReturn.totalNumOfFacetsConsidered += tfr.totalNumOfFacetsConsidered;
+ if (tfr.isRootNodeIncluded)
+ {
+ tmpToReturn.isRootNodeIncluded = true;
+ tmpToReturn.rootNodeValue = tfr.rootNodeValue;
+ }
+
+ IntToObjectMap<AACO> tmpToReturnMapToACCOs = tmpToReturn.mapToAACOs;
+ IntToObjectMap<AACO> tfrMapToACCOs = tfr.mapToAACOs;
+ IIntIterator tfrIntIterator = tfrMapToACCOs.GetKeyIterator();
+ while (tfrIntIterator.HasNext())
+ {
+ int tfrkey = tfrIntIterator.Next();
+ AACO tmpToReturnAACO = null;
+ if (null == (tmpToReturnAACO = tmpToReturnMapToACCOs.Get(tfrkey)))
+ {
+ tmpToReturnMapToACCOs.Put(tfrkey, tfrMapToACCOs.Get(tfrkey));
+ }
+ else
+ {
+ 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];
+ int indexIntoTmpToReturn = 0;
+ int indexIntoTFR = 0;
+ ACComparator merger = GetSuitableACComparator();
+ for (int indexIntoRes = 0; indexIntoRes < resLength; indexIntoRes++)
+ {
+ if (indexIntoTmpToReturn >= tmpToReturnAACO.ordinals.Length)
+ {
+ resOrds[indexIntoRes] = tfrAACO.ordinals[indexIntoTFR];
+ resVals[indexIntoRes] = tfrAACO.values[indexIntoTFR];
+ indexIntoTFR++;
+ continue;
+ }
+
+ if (indexIntoTFR >= tfrAACO.ordinals.Length)
+ {
+ resOrds[indexIntoRes] = tmpToReturnAACO.ordinals[indexIntoTmpToReturn];
+ resVals[indexIntoRes] = tmpToReturnAACO.values[indexIntoTmpToReturn];
+ indexIntoTmpToReturn++;
+ continue;
+ }
+
+ 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++;
+ }
+ }
+
+ tmpToReturnMapToACCOs.Put(tfrkey, new AACO(resOrds, resVals));
+ }
+ }
+ }
+
+ return tmpToReturn;
+ }
+
+ private class AggregatedCategoryHeap : PriorityQueue<AggregatedCategory>
+ {
+ private ACComparator merger;
+ public AggregatedCategoryHeap(int size, ACComparator merger)
+ : base(size)
+ {
+ this.merger = merger;
+ }
+
+ public override bool LessThan(AggregatedCategory arg1, AggregatedCategory arg2)
+ {
+ return merger.LeftGoesNow(arg2.ordinal, arg2.value, arg1.ordinal, arg1.value);
+ }
+ }
+
+ private class ResultNodeHeap : PriorityQueue<FacetResultNode>
+ {
+ private ACComparator merger;
+ public ResultNodeHeap(int size, ACComparator merger)
+ : base(size)
+ {
+ this.merger = merger;
+ }
+
+ public override bool LessThan(FacetResultNode arg1, FacetResultNode arg2)
+ {
+ return merger.LeftGoesNow(arg2.ordinal, arg2.value, arg1.ordinal, arg1.value);
+ }
+ }
+
+ private ACComparator GetSuitableACComparator()
+ {
+ if (facetRequest.SortOrderValue == FacetRequest.SortOrder.ASCENDING)
+ {
+ return new AscValueACComparator();
+ }
+ else
+ {
+ return new DescValueACComparator();
+ }
+ }
+
+ private abstract class ACComparator
+ {
+ internal ACComparator()
+ {
+ }
+
+ protected internal abstract bool LeftGoesNow(int ord1, double val1, int ord2, double val2);
+ }
+
+ private sealed class AscValueACComparator : ACComparator
+ {
+ internal AscValueACComparator()
+ {
+ }
+
+ protected internal override bool LeftGoesNow(int ord1, double val1, int ord2, double val2)
+ {
+ return (val1 == val2) ? (ord1 < ord2) : (val1 < val2);
+ }
+ }
+
+ private sealed class DescValueACComparator : ACComparator
+ {
+ internal DescValueACComparator()
+ {
+ }
+
+ protected internal override bool LeftGoesNow(int ord1, double val1, int ord2, double val2)
+ {
+ return (val1 == val2) ? (ord1 > ord2) : (val1 > val2);
+ }
+ }
+
+ public class IntermediateFacetResultWithHash : IIntermediateFacetResult
+ {
+ protected internal IntToObjectMap<AACO> mapToAACOs;
+ internal FacetRequest facetRequest;
+ internal bool isRootNodeIncluded;
+ internal double rootNodeValue;
+ internal int totalNumOfFacetsConsidered;
+
+ 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 FacetRequest
+ {
+ get
+ {
+ return this.facetRequest;
+ }
+ }
+ }
+
+ private sealed class AggregatedCategory
+ {
+ internal int ordinal;
+ internal double value;
+ internal AggregatedCategory(int ord, double val)
+ {
+ this.ordinal = ord;
+ this.value = val;
+ }
+ }
+
+ public sealed class AACO
+ {
+ internal int[] ordinals;
+ internal double[] values;
+ internal AACO(int[] ords, double[] vals)
+ {
+ this.ordinals = ords;
+ this.values = vals;
+ }
+ }
+
+ public override void LabelResult(FacetResult facetResult)
+ {
+ if (facetResult == null)
+ {
+ return;
+ }
+
+ FacetResultNode rootNode = facetResult.FacetResultNode;
+ RecursivelyLabel(rootNode, facetRequest.NumLabel);
+ }
+
+ private void RecursivelyLabel(FacetResultNode node, int numToLabel)
+ {
+ if (node == null)
+ {
+ return;
+ }
+
+ node.label = taxonomyReader.GetPath(node.ordinal);
+ int numLabeled = 0;
+ foreach (FacetResultNode frn in node.subResults)
+ {
+ RecursivelyLabel(frn, numToLabel);
+ if (++numLabeled >= numToLabel)
+ {
+ return;
+ }
+ }
+ }
+
+ public override FacetResult RearrangeFacetResult(FacetResult facetResult)
+ {
+ PriorityQueue<FacetResultNode> nodesHeap = new ResultNodeHeap(this.facetRequest.numResults, this.GetSuitableACComparator());
+ FacetResultNode topFrn = facetResult.FacetResultNode;
+ RearrangeChilrenOfNode(topFrn, nodesHeap);
+ return facetResult;
+ }
+
+ private void RearrangeChilrenOfNode(FacetResultNode node, PriorityQueue<FacetResultNode> nodesHeap)
+ {
+ nodesHeap.Clear();
+ foreach (FacetResultNode frn in node.subResults)
+ {
+ nodesHeap.Add(frn);
+ }
+
+ int size = nodesHeap.Size;
+ List<FacetResultNode> subResults = new List<FacetResultNode>(size);
+ while (nodesHeap.Size > 0)
+ {
+ subResults.Insert(0, nodesHeap.Pop());
+ }
+
+ node.subResults = subResults;
+ foreach (FacetResultNode frn in node.subResults)
+ {
+ RearrangeChilrenOfNode(frn, nodesHeap);
+ }
+ }
+
+ public override FacetResult RenderFacetResult(IIntermediateFacetResult tmpResult)
+ {
+ IntermediateFacetResultWithHash tmp = (IntermediateFacetResultWithHash)tmpResult;
+ int ordinal = this.taxonomyReader.GetOrdinal(this.facetRequest.categoryPath);
+ if ((tmp == null) || (ordinal == TaxonomyReader.INVALID_ORDINAL))
+ {
+ return null;
+ }
+
+ double value = Double.NaN;
+ if (tmp.isRootNodeIncluded)
+ {
+ value = tmp.rootNodeValue;
+ }
+
+ FacetResultNode root = GenerateNode(ordinal, value, tmp.mapToAACOs);
+ return new FacetResult(tmp.facetRequest, root, tmp.totalNumOfFacetsConsidered);
+ }
+
+ private FacetResultNode GenerateNode(int ordinal, double val, IntToObjectMap<AACO> mapToAACOs)
+ {
+ FacetResultNode node = new FacetResultNode(ordinal, val);
+ AACO aaco = mapToAACOs.Get(ordinal);
+ if (null == aaco)
+ {
+ return node;
+ }
+
+ List<FacetResultNode> list = new List<FacetResultNode>();
+ for (int i = 0; i < aaco.ordinals.Length; i++)
+ {
+ list.Add(GenerateNode(aaco.ordinals[i], aaco.values[i], mapToAACOs));
+ }
+
+ node.subResults = list;
+ return node;
+ }
+ }
+}