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; + } + } +}
