lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From paulir...@apache.org
Subject [37/53] [abbrv] Port much of Facet.Search and some others
Date Thu, 07 Nov 2013 13:53:52 GMT
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;
+        }
+    }
+}


Mime
View raw message