lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [2/3] lucenenet git commit: Some code fixes to Spatial, merging in before re-porting from 4.8.0
Date Sun, 08 Mar 2015 21:51:42 GMT
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/PrefixTreeStrategy.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/PrefixTreeStrategy.cs b/src/Lucene.Net.Spatial/Prefix/PrefixTreeStrategy.cs
index e15f6cd..36c6177 100644
--- a/src/Lucene.Net.Spatial/Prefix/PrefixTreeStrategy.cs
+++ b/src/Lucene.Net.Spatial/Prefix/PrefixTreeStrategy.cs
@@ -1,20 +1,19 @@
-/*
+/* 
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 using System;
 #if !NET35
 using System.Collections.Concurrent;
@@ -25,98 +24,180 @@ using System.Collections.Generic;
 using Lucene.Net.Analysis;
 using Lucene.Net.Analysis.Tokenattributes;
 using Lucene.Net.Documents;
+using Lucene.Net.Index;
 using Lucene.Net.Search.Function;
 using Lucene.Net.Spatial.Prefix.Tree;
 using Lucene.Net.Spatial.Queries;
 using Lucene.Net.Spatial.Util;
+using Lucene.Net.Support;
 using Spatial4n.Core.Shapes;
 
 namespace Lucene.Net.Spatial.Prefix
 {
     /// <summary>
-    /// Abstract SpatialStrategy which provides common functionality for those 
-    /// Strategys which use {@link SpatialPrefixTree}s
+    /// An abstract SpatialStrategy based on
+    /// <see cref="Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree">Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree
+    /// 	</see>
+    /// . The two
+    /// subclasses are
+    /// <see cref="RecursivePrefixTreeStrategy">RecursivePrefixTreeStrategy</see>
+    /// and
+    /// <see cref="TermQueryPrefixTreeStrategy">TermQueryPrefixTreeStrategy</see>
+    /// .  This strategy is most effective as a fast
+    /// approximate spatial search filter.
+    /// <h4>Characteristics:</h4>
+    /// <ul>
+    /// <li>Can index any shape; however only
+    /// <see cref="RecursivePrefixTreeStrategy">RecursivePrefixTreeStrategy</see>
+    /// can effectively search non-point shapes.</li>
+    /// <li>Can index a variable number of shapes per field value. This strategy
+    /// can do it via multiple calls to
+    /// <see cref="CreateIndexableFields(Shape)">CreateIndexableFields(Shape)
+    /// 	</see>
+    /// for a document or by giving it some sort of Shape aggregate (e.g. JTS
+    /// WKT MultiPoint).  The shape's boundary is approximated to a grid precision.
+    /// </li>
+    /// <li>Can query with any shape.  The shape's boundary is approximated to a grid
+    /// precision.</li>
+    /// <li>Only
+    /// <see cref="Lucene.Net.Spatial.Query.SpatialOperation.Intersects">Lucene.Net.Spatial.Query.SpatialOperation.Intersects
+    /// 	</see>
+    /// is supported.  If only points are indexed then this is effectively equivalent
+    /// to IsWithin.</li>
+    /// <li>The strategy supports
+    /// <see cref="MakeDistanceValueSource(Point)">MakeDistanceValueSource(Point)
+    /// 	</see>
+    /// even for multi-valued data, so long as the indexed data is all points; the
+    /// behavior is undefined otherwise.  However, <em>it will likely be removed in
+    /// the future</em> in lieu of using another strategy with a more scalable
+    /// implementation.  Use of this call is the only
+    /// circumstance in which a cache is used.  The cache is simple but as such
+    /// it doesn't scale to large numbers of points nor is it real-time-search
+    /// friendly.</li>
+    /// </ul>
+    /// <h4>Implementation:</h4>
+    /// The
+    /// <see cref="Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree">Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree
+    /// 	</see>
+    /// does most of the work, for example returning
+    /// a list of terms representing grids of various sizes for a supplied shape.
+    /// An important
+    /// configuration item is
+    /// <see cref="SetDistErrPct(double)">SetDistErrPct(double)</see>
+    /// which balances
+    /// shape precision against scalability.  See those javadocs.
     /// </summary>
+    /// <lucene.internal></lucene.internal>
     public abstract class PrefixTreeStrategy : SpatialStrategy
     {
-        protected readonly SpatialPrefixTree grid;
+        protected internal readonly SpatialPrefixTree grid;
+
+        private readonly IDictionary<string, PointPrefixTreeFieldCacheProvider> provider =
+            new ConcurrentHashMap<string, PointPrefixTreeFieldCacheProvider>();
 
-        private readonly IDictionary<String, PointPrefixTreeFieldCacheProvider> provider =
-            new ConcurrentDictionary<string, PointPrefixTreeFieldCacheProvider>();
+        protected internal readonly bool simplifyIndexedCells;
 
-        protected int defaultFieldValuesArrayLen = 2;
-        protected double distErrPct = SpatialArgs.DEFAULT_DISTERRPCT; // [ 0 TO 0.5 ]
+        protected internal int defaultFieldValuesArrayLen = 2;
 
-        protected PrefixTreeStrategy(SpatialPrefixTree grid, String fieldName)
-            : base(grid.GetSpatialContext(), fieldName)
+        protected internal double distErrPct = SpatialArgs.DEFAULT_DISTERRPCT;
+
+        public PrefixTreeStrategy(SpatialPrefixTree grid, string fieldName, bool simplifyIndexedCells
+            )
+            : base(grid.SpatialContext, fieldName)
         {
+            // [ 0 TO 0.5 ]
             this.grid = grid;
+            this.simplifyIndexedCells = simplifyIndexedCells;
         }
 
-        /* Used in the in-memory ValueSource as a default ArrayList length for this field's array of values, per doc. */
-
-        public void SetDefaultFieldValuesArrayLen(int defaultFieldValuesArrayLen)
+        /// <summary>
+        /// A memory hint used by
+        /// <see cref="MakeDistanceValueSource(Point)">MakeDistanceValueSource(Point)
+        /// 	</see>
+        /// for how big the initial size of each Document's array should be. The
+        /// default is 2.  Set this to slightly more than the default expected number
+        /// of points per document.
+        /// </summary>
+        public virtual int DefaultFieldValuesArrayLen
         {
-            this.defaultFieldValuesArrayLen = defaultFieldValuesArrayLen;
+            set { defaultFieldValuesArrayLen = value; }
         }
 
         /// <summary>
-        /// The default measure of shape precision affecting indexed and query shapes.
-        /// Specific shapes at index and query time can use something different.
-        /// @see org.apache.lucene.spatial.query.SpatialArgs#getDistErrPct()
+        /// The default measure of shape precision affecting shapes at index and query
+        /// times.
         /// </summary>
-        public double DistErrPct { get; set; }
+        /// <remarks>
+        /// The default measure of shape precision affecting shapes at index and query
+        /// times. Points don't use this as they are always indexed at the configured
+        /// maximum precision (
+        /// <see cref="Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree.GetMaxLevels()
+        /// 	">Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree.GetMaxLevels()</see>
+        /// );
+        /// this applies to all other shapes. Specific shapes at index and query time
+        /// can use something different than this default value.  If you don't set a
+        /// default then the default is
+        /// <see cref="Lucene.Net.Spatial.Query.SpatialArgs.DefaultDisterrpct">Lucene.Net.Spatial.Query.SpatialArgs.DefaultDisterrpct
+        /// 	</see>
+        /// --
+        /// 2.5%.
+        /// </remarks>
+        /// <seealso cref="Lucene.Net.Spatial.Query.SpatialArgs.GetDistErrPct()">Lucene.Net.Spatial.Query.SpatialArgs.GetDistErrPct()
+        /// 	</seealso>
+        public virtual double DistErrPct
+        {
+            get { return distErrPct; }
+            set { distErrPct = value; }
+        }
 
-        public override AbstractField[] CreateIndexableFields(Shape shape)
+        public override Field[] CreateIndexableFields(Shape shape
+            )
         {
             double distErr = SpatialArgs.CalcDistanceFromErrPct(shape, distErrPct, ctx);
             return CreateIndexableFields(shape, distErr);
         }
 
-        public AbstractField[] CreateIndexableFields(Shape shape, double distErr)
+        public virtual Field[] CreateIndexableFields(Shape shape
+            , double distErr)
         {
             int detailLevel = grid.GetLevelForDistance(distErr);
-            var cells = grid.GetNodes(shape, detailLevel, true);//true=intermediates cells
-            //If shape isn't a point, add a full-resolution center-point so that
-            // PointPrefixTreeFieldCacheProvider has the center-points.
-            // TODO index each center of a multi-point? Yes/no?
-            if (!(shape is Point))
-            {
-                Point ctr = shape.GetCenter();
-                //TODO should be smarter; don't index 2 tokens for this in CellTokenStream. Harmless though.
-                cells.Add(grid.GetNodes(ctr, grid.GetMaxLevels(), false)[0]);
-            }
-
+            IList<Cell> cells = grid.GetCells(shape, detailLevel, true, simplifyIndexedCells);
+            //intermediates cells
             //TODO is CellTokenStream supposed to be re-used somehow? see Uwe's comments:
             //  http://code.google.com/p/lucene-spatial-playground/issues/detail?id=4
+            Field field = new Field(FieldName, new PrefixTreeStrategy.CellTokenStream(cells
+                .GetEnumerator()), FieldType);
+            return new Field[] { field };
+        }
+
+        public static readonly FieldType FieldType = new FieldType();
 
-            return new AbstractField[]
-                       {
-                           new Field(GetFieldName(), new CellTokenStream(cells.GetEnumerator()))
-                               {OmitNorms = true, OmitTermFreqAndPositions = true}
-                       };
+        static PrefixTreeStrategy()
+        {
+            FieldType.Indexed = true;
+            FieldType.Tokenized = true;
+            FieldType.OmitNorms = true;
+            FieldType.IndexOptions = FieldInfo.IndexOptions.DOCS_ONLY;
+            FieldType.Freeze();
         }
 
-        /// <summary>
-        /// Outputs the tokenString of a cell, and if its a leaf, outputs it again with the leaf byte.
-        /// </summary>
-        protected class CellTokenStream : TokenStream
+        /// <summary>Outputs the tokenString of a cell, and if its a leaf, outputs it again with the leaf byte.
+        /// 	</summary>
+        /// <remarks>Outputs the tokenString of a cell, and if its a leaf, outputs it again with the leaf byte.
+        /// 	</remarks>
+        internal sealed class CellTokenStream : TokenStream
         {
-            private ITermAttribute termAtt;
-            private readonly IEnumerator<Node> iter;
+            private readonly CharTermAttribute termAtt;
 
-            public CellTokenStream(IEnumerator<Node> tokens)
-            {
-                this.iter = tokens;
-                Init();
-            }
+            private IEnumerator<Cell> iter = null;
 
-            private void Init()
+            public CellTokenStream(IEnumerator<Cell> tokens)
             {
-                termAtt = AddAttribute<ITermAttribute>();
+                this.iter = tokens;
+                termAtt = AddAttribute<CharTermAttribute>();
             }
 
-            private string nextTokenStringNeedingLeaf;
+            internal string nextTokenStringNeedingLeaf;
 
             public override bool IncrementToken()
             {
@@ -124,38 +205,36 @@ namespace Lucene.Net.Spatial.Prefix
                 if (nextTokenStringNeedingLeaf != null)
                 {
                     termAtt.Append(nextTokenStringNeedingLeaf);
-                    termAtt.Append((char)Node.LEAF_BYTE);
+                    termAtt.Append((char)Cell.LEAF_BYTE);
                     nextTokenStringNeedingLeaf = null;
                     return true;
                 }
                 if (iter.MoveNext())
                 {
-                    Node cell = iter.Current;
-                    var token = cell.GetTokenString();
+                    Cell cell = iter.Current;
+                    string token = cell.TokenString;
                     termAtt.Append(token);
                     if (cell.IsLeaf())
+                    {
                         nextTokenStringNeedingLeaf = token;
+                    }
                     return true;
                 }
                 return false;
             }
-
-            protected override void Dispose(bool disposing)
-            {
-            }
         }
 
         public ShapeFieldCacheProvider<Point> GetCacheProvider()
         {
             PointPrefixTreeFieldCacheProvider p;
-            if (!provider.TryGetValue(GetFieldName(), out p) || p == null)
+            if (!provider.TryGetValue(FieldName, out p) || p == null)
             {
                 lock (this)
                 {//double checked locking idiom is okay since provider is threadsafe
-                    if (!provider.ContainsKey(GetFieldName()))
+                    if (!provider.ContainsKey(FieldName))
                     {
-                        p = new PointPrefixTreeFieldCacheProvider(grid, GetFieldName(), defaultFieldValuesArrayLen);
-                        provider[GetFieldName()] = p;
+                        p = new PointPrefixTreeFieldCacheProvider(grid, FieldName, defaultFieldValuesArrayLen);
+                        provider[FieldName] = p;
                     }
                 }
             }
@@ -168,9 +247,9 @@ namespace Lucene.Net.Spatial.Prefix
             return new ShapeFieldCacheDistanceValueSource(ctx, p, queryPoint);
         }
 
-        public SpatialPrefixTree GetGrid()
+        public virtual SpatialPrefixTree Grid
         {
-            return grid;
+            get { return grid; }
         }
     }
 }

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeStrategy.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeStrategy.cs b/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeStrategy.cs
index d6fa681..1e0ccd0 100644
--- a/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeStrategy.cs
+++ b/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeStrategy.cs
@@ -1,20 +1,19 @@
-/*
+/* 
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 using Lucene.Net.Search;
 using Lucene.Net.Spatial.Prefix.Tree;
 using Lucene.Net.Spatial.Queries;
@@ -23,40 +22,84 @@ using Spatial4n.Core.Shapes;
 namespace Lucene.Net.Spatial.Prefix
 {
     /// <summary>
-    /// Based on {@link RecursivePrefixTreeFilter}.
+    /// A
+    /// <see cref="PrefixTreeStrategy">PrefixTreeStrategy</see>
+    /// which uses
+    /// <see cref="AbstractVisitingPrefixTreeFilter">AbstractVisitingPrefixTreeFilter</see>
+    /// .
+    /// This strategy has support for searching non-point shapes (note: not tested).
+    /// Even a query shape with distErrPct=0 (fully precise to the grid) should have
+    /// good performance for typical data, unless there is a lot of indexed data
+    /// coincident with the shape's edge.
     /// </summary>
+    /// <lucene.experimental></lucene.experimental>
     public class RecursivePrefixTreeStrategy : PrefixTreeStrategy
     {
         private int prefixGridScanLevel;
 
         public RecursivePrefixTreeStrategy(SpatialPrefixTree grid, string fieldName)
-            : base(grid, fieldName)
+            : base(grid, fieldName, true)
         {
-            prefixGridScanLevel = grid.GetMaxLevels() - 4;//TODO this default constant is dependent on the prefix grid size
+            //simplify indexed cells
+            prefixGridScanLevel = grid.MaxLevels - 4;
         }
 
-        public void SetPrefixGridScanLevel(int prefixGridScanLevel)
+        //TODO this default constant is dependent on the prefix grid size
+        /// <summary>
+        /// Sets the grid level [1-maxLevels] at which indexed terms are scanned brute-force
+        /// instead of by grid decomposition.
+        /// </summary>
+        /// <remarks>
+        /// Sets the grid level [1-maxLevels] at which indexed terms are scanned brute-force
+        /// instead of by grid decomposition.  By default this is maxLevels - 4.  The
+        /// final level, maxLevels, is always scanned.
+        /// </remarks>
+        public virtual int PrefixGridScanLevel
         {
-            //TODO if negative then subtract from maxlevels
-            this.prefixGridScanLevel = prefixGridScanLevel;
+            set
+            {
+                //TODO if negative then subtract from maxlevels
+                prefixGridScanLevel = value;
+            }
         }
 
-        public override Filter MakeFilter(SpatialArgs args)
+        public override string ToString()
         {
-            var op = args.Operation;
-            if (op != SpatialOperation.Intersects)
-                throw new UnsupportedSpatialOperation(op);
-
-            Shape shape = args.Shape;
-
-            int detailLevel = grid.GetLevelForDistance(args.ResolveDistErr(ctx, distErrPct));
-
-            return new RecursivePrefixTreeFilter(GetFieldName(), grid, shape, prefixGridScanLevel, detailLevel);
+            return GetType().Name + "(prefixGridScanLevel:" + prefixGridScanLevel + ",SPG:(" + grid + "))";
         }
 
-        public override string ToString()
+        public override Filter MakeFilter(SpatialArgs args)
         {
-            return GetType().Name + "(prefixGridScanLevel:" + prefixGridScanLevel + ",SPG:(" + grid + "))";
+            SpatialOperation op = args.Operation;
+            if (op == SpatialOperation.IsDisjointTo)
+            {
+                return new DisjointSpatialFilter(this, args, FieldName);
+            }
+            Shape shape = args.Shape;
+            int detailLevel = grid.GetLevelForDistance(args.ResolveDistErr(ctx, distErrPct));
+            bool hasIndexedLeaves = true;
+            if (op == SpatialOperation.Intersects)
+            {
+                return new IntersectsPrefixTreeFilter(shape, FieldName, grid, detailLevel, prefixGridScanLevel
+                                                      , hasIndexedLeaves);
+            }
+            else
+            {
+                if (op == SpatialOperation.IsWithin)
+                {
+                    return new WithinPrefixTreeFilter(shape, FieldName, grid, detailLevel, prefixGridScanLevel
+                                                      , -1);
+                }
+                else
+                {
+                    //-1 flag is slower but ensures correct results
+                    if (op == SpatialOperation.Contains)
+                    {
+                        return new ContainsPrefixTreeFilter(shape, FieldName, grid, detailLevel);
+                    }
+                }
+            }
+            throw new UnsupportedSpatialOperation(op);
         }
     }
-}
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/TermQueryPrefixTreeStrategy.cs b/src/Lucene.Net.Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
index 84a074a..20cbf5f 100644
--- a/src/Lucene.Net.Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
+++ b/src/Lucene.Net.Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
@@ -1,56 +1,72 @@
-/*
+/* 
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
-using System;
-using Lucene.Net.Index;
+using System.Collections.Generic;
 using Lucene.Net.Search;
 using Lucene.Net.Spatial.Prefix.Tree;
 using Lucene.Net.Spatial.Queries;
-using Lucene.Net.Spatial.Util;
+using Lucene.Net.Util;
 using Spatial4n.Core.Shapes;
 
 namespace Lucene.Net.Spatial.Prefix
 {
     /// <summary>
-    /// A basic implementation using a large {@link TermsFilter} of all the nodes from
-    /// {@link SpatialPrefixTree#getNodes(com.spatial4j.core.shape.Shape, int, boolean)}.
+    /// A basic implementation of
+    /// <see cref="PrefixTreeStrategy">PrefixTreeStrategy</see>
+    /// using a large
+    /// <see cref="Lucene.Net.Queries.TermsFilter">Lucene.Net.Queries.TermsFilter
+    /// 	</see>
+    /// of all the cells from
+    /// <see cref="Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree.GetCells(Shape, int, bool, bool)
+    /// 	">Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree.GetCells(Shape, int, bool, bool)
+    /// 	</see>
+    /// . It only supports the search of indexed Point shapes.
+    /// <p/>
+    /// The precision of query shapes (distErrPct) is an important factor in using
+    /// this Strategy. If the precision is too precise then it will result in many
+    /// terms which will amount to a slower query.
     /// </summary>
+    /// <lucene.experimental></lucene.experimental>
     public class TermQueryPrefixTreeStrategy : PrefixTreeStrategy
     {
         public TermQueryPrefixTreeStrategy(SpatialPrefixTree grid, string fieldName)
-            : base(grid, fieldName)
+            : base(grid, fieldName, false)
         {
         }
 
+        //do not simplify indexed cells
         public override Filter MakeFilter(SpatialArgs args)
         {
             SpatialOperation op = args.Operation;
             if (op != SpatialOperation.Intersects)
+            {
                 throw new UnsupportedSpatialOperation(op);
-
+            }
             Shape shape = args.Shape;
             int detailLevel = grid.GetLevelForDistance(args.ResolveDistErr(ctx, distErrPct));
-            var cells = grid.GetNodes(shape, detailLevel, false);
-            var filter = new TermsFilter();
-            foreach (Node cell in cells)
+            IList<Cell> cells = grid.GetCells(shape, detailLevel, false, true);
+            //no parents
+            //simplify
+            var terms = new BytesRef[cells.Count];
+            int i = 0;
+            foreach (Cell cell in cells)
             {
-                filter.AddTerm(new Term(GetFieldName(), cell.GetTokenString()));
+                terms[i++] = new BytesRef(cell.TokenString);
             }
-            return filter;
+            return new TermsFilter(FieldName, terms);
         }
     }
-}
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/Tree/Cell.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/Tree/Cell.cs b/src/Lucene.Net.Spatial/Prefix/Tree/Cell.cs
new file mode 100644
index 0000000..f572f2c
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/Cell.cs
@@ -0,0 +1,329 @@
+/* 
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Runtime.CompilerServices;
+using System.Text;
+using Lucene.Net.Spatial.Util;
+using Lucene.Net.Util;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix.Tree
+{
+    /// <summary>Represents a grid cell.</summary>
+    /// <remarks>
+    /// Represents a grid cell. These are not necessarily thread-safe, although new
+    /// Cell("") (world cell) must be.
+    /// </remarks>
+    /// <lucene.experimental></lucene.experimental>
+    public abstract class Cell : IComparable<Cell>
+    {
+        public const byte LEAF_BYTE = (byte)('+');//NOTE: must sort before letters & numbers
+
+        /*
+        Holds a byte[] and/or String representation of the cell. Both are lazy constructed from the other.
+        Neither contains the trailing leaf byte.
+        */
+        private byte[] bytes;
+        private int b_off;
+        private int b_len;
+
+        /// <summary>Always false for points.</summary>
+        /// <remarks>
+        /// Always false for points. Otherwise, indicate no further sub-cells are going
+        /// to be provided because shapeRel is WITHIN or maxLevels or a detailLevel is
+        /// hit.
+        /// </remarks>
+        protected internal bool leaf;
+
+        /// <summary>
+        /// When set via getSubCells(filter), it is the relationship between this cell
+        /// and the given shape filter.
+        /// </summary>
+        /// <remarks>
+        /// When set via getSubCells(filter), it is the relationship between this cell
+        /// and the given shape filter.
+        /// </remarks>
+        protected internal SpatialRelation shapeRel = SpatialRelation.NULL_VALUE;//set in getSubCells(filter), and via setLeaf().
+
+        private string token;//this is the only part of equality
+
+        protected internal Cell(string token)
+        {
+            //NOTE: must sort before letters & numbers
+            //this is the only part of equality
+            this.token = token;
+            if (token.Length > 0 && token[token.Length - 1] == (char)LEAF_BYTE)
+            {
+                this.token = token.Substring(0, token.Length - 1);
+                SetLeaf();
+            }
+            if (Level == 0)
+            {
+                GetShape();//ensure any lazy instantiation completes to make this threadsafe
+            }
+        }
+
+        protected internal Cell(byte[] bytes, int off, int len)
+        {
+            //ensure any lazy instantiation completes to make this threadsafe
+            this.bytes = bytes;
+            b_off = off;
+            b_len = len;
+            B_fixLeaf();
+        }
+
+        #region IComparable<Cell> Members
+
+        public virtual int CompareTo(Cell o)
+        {
+            return string.CompareOrdinal(TokenString, o.TokenString);
+        }
+
+        #endregion
+
+        public virtual void Reset(byte[] bytes, int off, int len)
+        {
+            Debug.Assert(Level != 0);
+            token = null;
+            shapeRel = SpatialRelation.NULL_VALUE;
+            this.bytes = bytes;
+            b_off = off;
+            b_len = len;
+            B_fixLeaf();
+        }
+
+        public virtual void Reset(string token)
+        {
+            Debug.Assert(Level != 0);
+            this.token = token;
+            shapeRel = SpatialRelation.NULL_VALUE;
+
+            //converting string t0 byte[]
+            //bytes = Encoding.UTF8.GetBytes(token);
+            BytesRef utf8Result = new BytesRef(token.Length);
+            UnicodeUtil.UTF16toUTF8(token.ToCharArray(), 0, token.Length, utf8Result);
+            bytes = utf8Result.bytes.ToByteArray();
+
+            b_off = 0;
+            b_len = bytes.Length;
+            B_fixLeaf();
+        }
+
+        private void B_fixLeaf()
+        {
+            //note that non-point shapes always have the maxLevels cell set with setLeaf
+            if (bytes[b_off + b_len - 1] == LEAF_BYTE)
+            {
+                b_len--;
+                SetLeaf();
+            }
+            else
+            {
+                leaf = false;
+            }
+        }
+
+        public virtual SpatialRelation GetShapeRel()
+        {
+            return shapeRel;
+        }
+
+        /// <summary>For points, this is always false.</summary>
+        /// <remarks>
+        /// For points, this is always false.  Otherwise this is true if there are no
+        /// further cells with this prefix for the shape (always true at maxLevels).
+        /// </remarks>
+        public virtual bool IsLeaf()
+        {
+            return leaf;
+        }
+
+        /// <summary>Note: not supported at level 0.</summary>
+        /// <remarks>Note: not supported at level 0.</remarks>
+        public virtual void SetLeaf()
+        {
+            Debug.Assert(Level != 0);
+            leaf = true;
+        }
+
+        /*
+         * Note: doesn't contain a trailing leaf byte.
+         */
+        public virtual String TokenString
+        {
+            get
+            {
+                if (token == null)
+                    throw new InvalidOperationException("Somehow we got a null token");
+                return token;
+            }
+        }
+
+        /// <summary>Note: doesn't contain a trailing leaf byte.</summary>
+        /// <remarks>Note: doesn't contain a trailing leaf byte.</remarks>
+        public virtual byte[] GetTokenBytes()
+        {
+            if (bytes != null)
+            {
+                if (b_off != 0 || b_len != bytes.Length)
+                {
+                    throw new InvalidOperationException("Not supported if byte[] needs to be recreated.");
+                }
+            }
+            else
+            {
+                //converting string t0 byte[]
+                //bytes = Encoding.UTF8.GetBytes(token);
+                BytesRef utf8Result = new BytesRef(token.Length);
+                UnicodeUtil.UTF16toUTF8(token.ToCharArray(), 0, token.Length, utf8Result);
+                bytes = utf8Result.bytes.ToByteArray();
+                b_off = 0;
+                b_len = bytes.Length;
+            }
+            return bytes;
+        }
+
+        public virtual int Level
+        {
+            get
+            {
+                return token.Length;
+                //return token != null ? token.Length : b_len;
+            }
+        }
+
+        //TODO add getParent() and update some algorithms to use this?
+        //public Cell getParent();
+        /// <summary>
+        /// Like
+        /// <see cref="GetSubCells()">GetSubCells()</see>
+        /// but with the results filtered by a shape. If
+        /// that shape is a
+        /// <see cref="Point">Spatial4n.Core.Shapes.Point</see>
+        /// then it must call
+        /// <see cref="GetSubCell(Point)">GetSubCell(Spatial4n.Core.Shapes.Point)
+        /// 	</see>
+        /// . The returned cells
+        /// should have
+        /// <see cref="GetShapeRel()">GetShapeRel()</see>
+        /// set to their relation with
+        /// <code>shapeFilter</code>
+        /// . In addition,
+        /// <see cref="IsLeaf()">IsLeaf()</see>
+        /// must be true when that relation is WITHIN.
+        /// <p/>
+        /// Precondition: Never called when getLevel() == maxLevel.
+        /// </summary>
+        /// <param name="shapeFilter">an optional filter for the returned cells.</param>
+        /// <returns>A set of cells (no dups), sorted. Not Modifiable.</returns>
+        public virtual ICollection<Cell> GetSubCells(Shape shapeFilter)
+        {
+            //Note: Higher-performing subclasses might override to consider the shape filter to generate fewer cells.
+            if (shapeFilter is Point)
+            {
+                Cell subCell = GetSubCell((Point)shapeFilter);
+                subCell.shapeRel = SpatialRelation.CONTAINS;
+#if !NET35
+                return new ReadOnlyCollectionBuilder<Cell>(new[] { subCell }).ToReadOnlyCollection();
+#else
+                return new List<Cell>(new[] { subCell }).AsReadOnly();
+#endif
+            }
+
+            ICollection<Cell> cells = GetSubCells();
+            if (shapeFilter == null)
+            {
+                return cells;
+            }
+            //TODO change API to return a filtering iterator
+            IList<Cell> copy = new List<Cell>(cells.Count);
+            foreach (Cell cell in cells)
+            {
+                SpatialRelation rel = cell.GetShape().Relate(shapeFilter);
+                if (rel == SpatialRelation.DISJOINT)
+                {
+                    continue;
+                }
+                cell.shapeRel = rel;
+                if (rel == SpatialRelation.WITHIN)
+                {
+                    cell.SetLeaf();
+                }
+                copy.Add(cell);
+            }
+            return copy;
+        }
+
+        /// <summary>
+        /// Performant implementations are expected to implement this efficiently by
+        /// considering the current cell's boundary.
+        /// </summary>
+        /// <remarks>
+        /// Performant implementations are expected to implement this efficiently by
+        /// considering the current cell's boundary. Precondition: Never called when
+        /// getLevel() == maxLevel.
+        /// <p/>
+        /// Precondition: this.getShape().relate(p) != DISJOINT.
+        /// </remarks>
+        public abstract Cell GetSubCell(Point p);
+
+        //TODO Cell getSubCell(byte b)
+        /// <summary>Gets the cells at the next grid cell level that cover this cell.</summary>
+        /// <remarks>
+        /// Gets the cells at the next grid cell level that cover this cell.
+        /// Precondition: Never called when getLevel() == maxLevel.
+        /// </remarks>
+        /// <returns>A set of cells (no dups), sorted, modifiable, not empty, not null.</returns>
+        protected internal abstract ICollection<Cell> GetSubCells();
+
+        /// <summary>
+        /// <see cref="GetSubCells()">GetSubCells()</see>
+        /// .size() -- usually a constant. Should be &gt;=2
+        /// </summary>
+        public abstract int GetSubCellsSize();
+
+        public abstract Shape GetShape();
+
+        public virtual Point GetCenter()
+        {
+            return GetShape().GetCenter();
+        }
+
+        #region Equality overrides
+
+        public override bool Equals(object obj)
+        {
+            return !(obj == null || !(obj is Cell)) &&
+                   TokenString.Equals(((Cell)obj).TokenString);
+        }
+
+        public override int GetHashCode()
+        {
+            return TokenString.GetHashCode();
+        }
+
+        public override string ToString()
+        {
+            return TokenString + (IsLeaf() ? ((char)LEAF_BYTE).ToString() : string.Empty);
+        }
+
+        #endregion
+
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/Tree/GeohashPrefixTree.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/Tree/GeohashPrefixTree.cs b/src/Lucene.Net.Spatial/Prefix/Tree/GeohashPrefixTree.cs
index b05d7d2..3452948 100644
--- a/src/Lucene.Net.Spatial/Prefix/Tree/GeohashPrefixTree.cs
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/GeohashPrefixTree.cs
@@ -1,20 +1,19 @@
-/*
+/* 
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 using System;
 using System.Collections.Generic;
 using Spatial4n.Core.Context;
@@ -24,135 +23,167 @@ using Spatial4n.Core.Util;
 namespace Lucene.Net.Spatial.Prefix.Tree
 {
     /// <summary>
-    /// A SpatialPrefixGrid based on Geohashes.  Uses {@link GeohashUtils} to do all the geohash work.
+    /// A
+    /// <see cref="SpatialPrefixTree">SpatialPrefixTree</see>
+    /// based on
+    /// <a href="http://en.wikipedia.org/wiki/Geohash">Geohashes</a>.
+    /// Uses
+    /// <see cref="Spatial4n.Core.IO.GeohashUtils">Spatial4n.Core.IO.GeohashUtils
+    /// 	</see>
+    /// to do all the geohash work.
     /// </summary>
+    /// <lucene.experimental></lucene.experimental>
     public class GeohashPrefixTree : SpatialPrefixTree
     {
-        /// <summary>
-        /// Factory for creating {@link GeohashPrefixTree} instances with useful defaults
-        /// </summary>
-        public class Factory : SpatialPrefixTreeFactory
-        {
-            protected override int GetLevelForDistance(double degrees)
-            {
-                var grid = new GeohashPrefixTree(ctx, GeohashPrefixTree.GetMaxLevelsPossible());
-                return grid.GetLevelForDistance(degrees);
-            }
-
-            protected override SpatialPrefixTree NewSPT()
-            {
-                return new GeohashPrefixTree(ctx, maxLevels != null ? maxLevels.Value : GeohashPrefixTree.GetMaxLevelsPossible());
-            }
-        }
-
-
         public GeohashPrefixTree(SpatialContext ctx, int maxLevels)
             : base(ctx, maxLevels)
         {
             Rectangle bounds = ctx.GetWorldBounds();
             if (bounds.GetMinX() != -180)
-                throw new ArgumentException("Geohash only supports lat-lon world bounds. Got " + bounds);
-            int MAXP = GetMaxLevelsPossible();
-            if (maxLevels <= 0 || maxLevels > MAXP)
-                throw new ArgumentException("maxLen must be [1-" + MAXP + "] but got " + maxLevels);
-
+            {
+                throw new ArgumentException("Geohash only supports lat-lon world bounds. Got " +
+                                            bounds);
+            }
+            int Maxp = MaxLevelsPossible;
+            if (maxLevels <= 0 || maxLevels > Maxp)
+            {
+                throw new ArgumentException("maxLen must be [1-" + Maxp + "] but got " + maxLevels
+                    );
+            }
         }
 
-        /// <summary>
-        /// Any more than this and there's no point (double lat and lon are the same).
-        /// </summary>
-        /// <returns></returns>
-        public static int GetMaxLevelsPossible()
+        /// <summary>Any more than this and there's no point (double lat & lon are the same).
+        /// 	</summary>
+        /// <remarks>Any more than this and there's no point (double lat & lon are the same).
+        /// 	</remarks>
+        public static int MaxLevelsPossible
         {
-            return GeohashUtils.MAX_PRECISION;
+            get { return GeohashUtils.MAX_PRECISION; }
         }
 
         public override int GetLevelForDistance(double dist)
         {
             if (dist == 0)
-                return maxLevels;//short circuit
+            {
+                return maxLevels;
+            }
+            //short circuit
             int level = GeohashUtils.LookupHashLenForWidthHeight(dist, dist);
             return Math.Max(Math.Min(level, maxLevels), 1);
         }
 
-        protected override Node GetNode(Point p, int level)
+        protected internal override Cell GetCell(Point p, int level)
         {
-            return new GhCell(GeohashUtils.EncodeLatLon(p.GetY(), p.GetX(), level), this);//args are lat,lon (y,x)
+            return new GhCell(this, GeohashUtils.EncodeLatLon(p.GetY(), p.GetX
+                                                                            (), level));
         }
 
-        public override Node GetNode(string token)
+        //args are lat,lon (y,x)
+        public override Cell GetCell(string token)
         {
-            return new GhCell(token, this);
+            return new GhCell(this, token);
         }
 
-        public override Node GetNode(byte[] bytes, int offset, int len)
+        public override Cell GetCell(byte[] bytes, int offset, int len)
         {
-            throw new System.NotImplementedException();
+            return new GhCell(this, bytes, offset, len);
         }
 
-        public override IList<Node> GetNodes(Shape shape, int detailLevel, bool inclParents)
+        #region Nested type: Factory
+
+        /// <summary>
+        /// Factory for creating
+        /// <see cref="GeohashPrefixTree">GeohashPrefixTree</see>
+        /// instances with useful defaults
+        /// </summary>
+        public class Factory : SpatialPrefixTreeFactory
         {
-            var s = shape as Point;
-            return (s != null) ? base.GetNodesAltPoint(s, detailLevel, inclParents) : base.GetNodes(shape, detailLevel, inclParents);
+            protected internal override int GetLevelForDistance(double degrees)
+            {
+                var grid = new GeohashPrefixTree(ctx, MaxLevelsPossible);
+                return grid.GetLevelForDistance(degrees);
+            }
+
+            protected internal override SpatialPrefixTree NewSPT()
+            {
+                return new GeohashPrefixTree(ctx, maxLevels.HasValue ? maxLevels.Value : MaxLevelsPossible);
+            }
         }
 
-        public class GhCell : Node
+        #endregion
+
+        #region Nested type: GhCell
+
+        internal class GhCell : Cell
         {
-            public GhCell(String token, GeohashPrefixTree enclosingInstance)
-                : base(enclosingInstance, token)
+            private readonly GeohashPrefixTree _enclosing;
+            private Shape shape;
+
+            internal GhCell(GeohashPrefixTree _enclosing, string token)
+                : base(token)
             {
+                this._enclosing = _enclosing;
             }
 
-            public override void Reset(string newToken)
+            internal GhCell(GeohashPrefixTree _enclosing, byte[] bytes, int off, int len)
+                : base(bytes, off, len)
             {
-                base.Reset(newToken);
-                shape = null;
+                this._enclosing = _enclosing;
             }
 
-            public override IList<Node> GetSubCells()
+            public override void Reset(byte[] bytes, int off, int len)
             {
-                String[] hashes = GeohashUtils.GetSubGeohashes(GetGeohash());//sorted
-                var cells = new List<Node>(hashes.Length);
+                base.Reset(bytes, off, len);
+                shape = null;
+            }
 
-                var enclosingInstance = (GeohashPrefixTree)spatialPrefixTree;
-                foreach (String hash in hashes)
+            protected internal override ICollection<Cell> GetSubCells()
+            {
+                string[] hashes = GeohashUtils.GetSubGeohashes(Geohash);
+                //sorted
+                IList<Cell> cells = new List<Cell>(hashes.Length);
+                foreach (string hash in hashes)
                 {
-                    cells.Add(new GhCell(hash, enclosingInstance));
+                    cells.Add(new GhCell(_enclosing, hash));
                 }
                 return cells;
             }
 
             public override int GetSubCellsSize()
             {
-                return 32;//8x4
+                return 32;
             }
 
-            public override Node GetSubCell(Point p)
+            //8x4
+            public override Cell GetSubCell(Point p)
             {
-                return ((GeohashPrefixTree)spatialPrefixTree).GetNode(p, GetLevel() + 1); //not performant!
+                return _enclosing.GetCell(p, Level + 1);
             }
 
-            private Shape shape;//cache
-
+            //not performant!
+            //cache
             public override Shape GetShape()
             {
                 if (shape == null)
                 {
-                    shape = GeohashUtils.DecodeBoundary(GetGeohash(), ((GeohashPrefixTree)spatialPrefixTree).ctx);
+                    shape = GeohashUtils.DecodeBoundary(Geohash, _enclosing.ctx);
                 }
                 return shape;
             }
 
             public override Point GetCenter()
             {
-                return GeohashUtils.Decode(GetGeohash(), ((GeohashPrefixTree)spatialPrefixTree).ctx);
+                return GeohashUtils.Decode(Geohash, _enclosing.ctx);
             }
 
-            private String GetGeohash()
+            private string Geohash
             {
-                return GetTokenString();
+                get { return TokenString; }
             }
 
-        }//class GhCell
+            //class GhCell
+        }
+
+        #endregion
     }
-}
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/Tree/Node.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/Tree/Node.cs b/src/Lucene.Net.Spatial/Prefix/Tree/Node.cs
index ce403b0..bb05720 100644
--- a/src/Lucene.Net.Spatial/Prefix/Tree/Node.cs
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/Node.cs
@@ -143,7 +143,7 @@ namespace Lucene.Net.Spatial.Prefix.Tree
             if (point != null)
             {
 #if !NET35
-                return new ReadOnlyCollectionBuilder<Node>(new[] {GetSubCell(point)}).ToReadOnlyCollection();
+                return new ReadOnlyCollectionBuilder<Node>(new[] { GetSubCell(point) }).ToReadOnlyCollection();
 #else
                 return new List<Node>(new[]{GetSubCell(point)}).AsReadOnly();
 #endif
@@ -206,7 +206,7 @@ namespace Lucene.Net.Spatial.Prefix.Tree
 
         public override bool Equals(object obj)
         {
-            return !(obj == null || !(obj is Node)) && GetTokenString().Equals(((Node) obj).GetTokenString());
+            return !(obj == null || !(obj is Node)) && GetTokenString().Equals(((Node)obj).GetTokenString());
         }
 
         public override int GetHashCode()
@@ -216,7 +216,7 @@ namespace Lucene.Net.Spatial.Prefix.Tree
 
         public override string ToString()
         {
-            return GetTokenString() + (IsLeaf() ? new string(new[] {(char) LEAF_BYTE}) : string.Empty);
+            return GetTokenString() + (IsLeaf() ? new string(new[] { (char)LEAF_BYTE }) : string.Empty);
         }
     }
 }

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/Tree/QuadPrefixTree.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/Tree/QuadPrefixTree.cs b/src/Lucene.Net.Spatial/Prefix/Tree/QuadPrefixTree.cs
index 230fd4a..bde41b1 100644
--- a/src/Lucene.Net.Spatial/Prefix/Tree/QuadPrefixTree.cs
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/QuadPrefixTree.cs
@@ -1,23 +1,23 @@
-/*
+/* 
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 using System;
 using System.Collections.Generic;
 using System.Diagnostics;
+using System.IO;
 using System.Text;
 using Spatial4n.Core.Context;
 using Spatial4n.Core.Shapes;
@@ -25,76 +25,48 @@ using Spatial4n.Core.Shapes;
 namespace Lucene.Net.Spatial.Prefix.Tree
 {
     /// <summary>
-    /// Implementation of {@link SpatialPrefixTree} which uses a quad tree
-    /// (http://en.wikipedia.org/wiki/Quadtree)
+    /// A
+    /// <see cref="SpatialPrefixTree">SpatialPrefixTree</see>
+    /// which uses a
+    /// <a href="http://en.wikipedia.org/wiki/Quadtree">quad tree</a> in which an
+    /// indexed term will be generated for each cell, 'A', 'B', 'C', 'D'.
     /// </summary>
+    /// <lucene.experimental></lucene.experimental>
     public class QuadPrefixTree : SpatialPrefixTree
     {
-        /// <summary>
-        /// Factory for creating {@link QuadPrefixTree} instances with useful defaults
-        /// </summary>
-        public class Factory : SpatialPrefixTreeFactory
-        {
-            protected override int GetLevelForDistance(double degrees)
-            {
-                var grid = new QuadPrefixTree(ctx, MAX_LEVELS_POSSIBLE);
-                return grid.GetLevelForDistance(degrees);
-            }
-
-            protected override SpatialPrefixTree NewSPT()
-            {
-                return new QuadPrefixTree(ctx, maxLevels != null ? maxLevels.Value : MAX_LEVELS_POSSIBLE);
-            }
-        }
+        public const int MaxLevelsPossible = 50;
 
-        public static readonly int MAX_LEVELS_POSSIBLE = 50;//not really sure how big this should be
+        public const int DefaultMaxLevels = 12;
 
-        public static readonly int DEFAULT_MAX_LEVELS = 12;
-        private double xmin;
-        private double xmax;
-        private double ymin;
-        private double ymax;
-        private double xmid;
-        private double ymid;
+        public readonly double gridH;
+        private readonly double gridW;
 
-        private double gridW;
-        private double gridH;
+        internal readonly double[] levelH;
 
-        double[] levelW;
-        double[] levelH;
-        int[] levelS; // side
-        int[] levelN; // number
+        internal readonly int[] levelN;
+        internal readonly int[] levelS;
+        internal readonly double[] levelW;
+        private readonly double xmax;
+        private readonly double xmid;
+        private readonly double xmin;
+        private readonly double ymax;
+        private readonly double ymid;
+        private readonly double ymin;
 
         public QuadPrefixTree(SpatialContext ctx, Rectangle bounds, int maxLevels)
             : base(ctx, maxLevels)
         {
-            Init(ctx, bounds, maxLevels);
-        }
-
-        public QuadPrefixTree(SpatialContext ctx)
-            : base(ctx, DEFAULT_MAX_LEVELS)
-        {
-            Init(ctx, ctx.GetWorldBounds(), DEFAULT_MAX_LEVELS);
-        }
-
-        public QuadPrefixTree(SpatialContext ctx, int maxLevels)
-            : base(ctx, maxLevels)
-        {
-            Init(ctx, ctx.GetWorldBounds(), maxLevels);
-        }
-
-        protected void Init(SpatialContext ctx, Rectangle bounds, int maxLevels)
-        {
-            this.xmin = bounds.GetMinX();
-            this.xmax = bounds.GetMaxX();
-            this.ymin = bounds.GetMinY();
-            this.ymax = bounds.GetMaxY();
-
+            //not really sure how big this should be
+            // side
+            // number
+            xmin = bounds.GetMinX();
+            xmax = bounds.GetMaxX();
+            ymin = bounds.GetMinY();
+            ymax = bounds.GetMaxY();
             levelW = new double[maxLevels];
             levelH = new double[maxLevels];
             levelS = new int[maxLevels];
             levelN = new int[maxLevels];
-
             gridW = xmax - xmin;
             gridH = ymax - ymin;
             xmid = xmin + gridW / 2.0;
@@ -103,7 +75,6 @@ namespace Lucene.Net.Spatial.Prefix.Tree
             levelH[0] = gridH / 2.0;
             levelS[0] = 2;
             levelN[0] = 4;
-
             for (int i = 1; i < levelW.Length; i++)
             {
                 levelW[i] = levelW[i - 1] / 2.0;
@@ -111,13 +82,40 @@ namespace Lucene.Net.Spatial.Prefix.Tree
                 levelS[i] = levelS[i - 1] * 2;
                 levelN[i] = levelN[i - 1] * 4;
             }
+        }
+
+        public QuadPrefixTree(SpatialContext ctx)
+            : this(ctx, DefaultMaxLevels)
+        {
+        }
+
+        public QuadPrefixTree(SpatialContext ctx, int maxLevels)
+            : this(ctx, ctx.GetWorldBounds(), maxLevels)
+        {
+        }
 
+        public virtual void PrintInfo(TextWriter @out)
+        {
+            // Format the number to min 3 integer digits and exactly 5 fraction digits
+            const string FORMAT_STR = @"000.00000";
+            /*NumberFormat nf = NumberFormat.GetNumberInstance(CultureInfo.Root);
+			nf.SetMaximumFractionDigits(5);
+			nf.SetMinimumFractionDigits(5);
+			nf.SetMinimumIntegerDigits(3);*/
+            for (int i = 0; i < maxLevels; i++)
+            {
+                @out.WriteLine(i + "]\t" + levelW[i].ToString(FORMAT_STR) + "\t" + levelH[i].ToString(FORMAT_STR) + "\t" +
+                               levelS[i] + "\t" + (levelS[i] * levelS[i]));
+            }
         }
 
         public override int GetLevelForDistance(double dist)
         {
-            if (dist == 0)//short circuit
+            if (dist == 0)
+            {
+                //short circuit
                 return maxLevels;
+            }
             for (int i = 0; i < maxLevels - 1; i++)
             {
                 //note: level[i] is actually a lookup for level i+1
@@ -129,65 +127,49 @@ namespace Lucene.Net.Spatial.Prefix.Tree
             return maxLevels;
         }
 
-        protected override Node GetNode(Point p, int level)
+        protected internal override Cell GetCell(Point p, int level)
         {
-            var cells = new List<Node>(1);
+            IList<Cell> cells = new List<Cell>(1);
             Build(xmid, ymid, 0, cells, new StringBuilder(), ctx.MakePoint(p.GetX(), p.GetY()), level);
-            return cells[0];//note cells could be longer if p on edge
-        }
-
-        public override Node GetNode(string token)
-        {
-            return new QuadCell(token, this);
+            return cells[0];
         }
 
-        public override Node GetNode(byte[] bytes, int offset, int len)
+        //note cells could be longer if p on edge
+        public override Cell GetCell(string token)
         {
-            throw new System.NotImplementedException();
+            return new QuadCell(this, token);
         }
 
-        public override IList<Node> GetNodes(Shape shape, int detailLevel, bool inclParents)
+        public override Cell GetCell(byte[] bytes, int offset, int len)
         {
-            var point = shape as Point;
-            if (point != null)
-                return base.GetNodesAltPoint(point, detailLevel, inclParents);
-            else
-                return base.GetNodes(shape, detailLevel, inclParents);
+            return new QuadCell(this, bytes, offset, len);
         }
 
-        private void Build(double x, double y, int level, List<Node> matches, StringBuilder str, Shape shape, int maxLevel)
+        private void Build(double x, double y, int level, IList<Cell> matches, StringBuilder
+                                                                                   str, Shape shape, int maxLevel)
         {
             Debug.Assert(str.Length == level);
             double w = levelW[level] / 2;
             double h = levelH[level] / 2;
-
             // Z-Order
             // http://en.wikipedia.org/wiki/Z-order_%28curve%29
             CheckBattenberg('A', x - w, y + h, level, matches, str, shape, maxLevel);
             CheckBattenberg('B', x + w, y + h, level, matches, str, shape, maxLevel);
             CheckBattenberg('C', x - w, y - h, level, matches, str, shape, maxLevel);
             CheckBattenberg('D', x + w, y - h, level, matches, str, shape, maxLevel);
-
-            // possibly consider hilbert curve
-            // http://en.wikipedia.org/wiki/Hilbert_curve
-            // http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
-            // if we actually use the range property in the query, this could be useful
         }
 
-        private void CheckBattenberg(
-            char c,
-            double cx,
-            double cy,
-            int level,
-            List<Node> matches,
-            StringBuilder str,
-            Shape shape,
-            int maxLevel)
+        // possibly consider hilbert curve
+        // http://en.wikipedia.org/wiki/Hilbert_curve
+        // http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
+        // if we actually use the range property in the query, this could be useful
+        private void CheckBattenberg(char c, double cx, double cy, int level, IList<Cell>
+                                                                                  matches, StringBuilder str,
+                                     Shape shape, int maxLevel)
         {
             Debug.Assert(str.Length == level);
             double w = levelW[level] / 2;
             double h = levelH[level] / 2;
-
             int strlen = str.Length;
             Rectangle rectangle = ctx.MakeRectangle(cx - w, cx + w, cy - h, cy + h);
             SpatialRelation v = shape.Relate(rectangle);
@@ -195,60 +177,96 @@ namespace Lucene.Net.Spatial.Prefix.Tree
             {
                 str.Append(c);
                 //str.append(SpatialPrefixGrid.COVER);
-                matches.Add(new QuadCell(str.ToString(), v.Transpose(), this));
-            }
-            else if (SpatialRelation.DISJOINT == v)
-            {
-                // nothing
+                matches.Add(new QuadCell(this, str.ToString(), v.Transpose()));
             }
             else
-            { // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
-                str.Append(c);
-
-                int nextLevel = level + 1;
-                if (nextLevel >= maxLevel)
+            {
+                if (SpatialRelation.DISJOINT == v)
                 {
-                    //str.append(SpatialPrefixGrid.INTERSECTS);
-                    matches.Add(new QuadCell(str.ToString(), v.Transpose(), this));
                 }
                 else
                 {
-                    Build(cx, cy, nextLevel, matches, str, shape, maxLevel);
+                    // nothing
+                    // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
+                    str.Append(c);
+                    int nextLevel = level + 1;
+                    if (nextLevel >= maxLevel)
+                    {
+                        //str.append(SpatialPrefixGrid.INTERSECTS);
+                        matches.Add(new QuadCell(this, str.ToString(), v.Transpose()));
+                    }
+                    else
+                    {
+                        Build(cx, cy, nextLevel, matches, str, shape, maxLevel);
+                    }
                 }
             }
             str.Length = strlen;
         }
 
-        public class QuadCell : Node
+        #region Nested type: Factory
+
+        /// <summary>
+        /// Factory for creating
+        /// <see cref="QuadPrefixTree">QuadPrefixTree</see>
+        /// instances with useful defaults
+        /// </summary>
+        public class Factory : SpatialPrefixTreeFactory
+        {
+            protected internal override int GetLevelForDistance(double degrees)
+            {
+                var grid = new QuadPrefixTree(ctx, MaxLevelsPossible);
+                return grid.GetLevelForDistance(degrees);
+            }
+
+            protected internal override SpatialPrefixTree NewSPT()
+            {
+                return new QuadPrefixTree(ctx, maxLevels.HasValue ? maxLevels.Value : MaxLevelsPossible);
+            }
+        }
+
+        #endregion
+
+        #region Nested type: QuadCell
+
+        internal class QuadCell : Cell
         {
+            private readonly QuadPrefixTree _enclosing;
+            private Shape shape;
 
-            public QuadCell(String token, QuadPrefixTree enclosingInstance)
-                : base(enclosingInstance, token)
+            public QuadCell(QuadPrefixTree _enclosing, string token)
+                : base(token)
             {
+                this._enclosing = _enclosing;
             }
 
-            public QuadCell(String token, SpatialRelation shapeRel, QuadPrefixTree enclosingInstance)
-                : base(enclosingInstance, token)
+            public QuadCell(QuadPrefixTree _enclosing, string token, SpatialRelation shapeRel
+                )
+                : base(token)
             {
+                this._enclosing = _enclosing;
                 this.shapeRel = shapeRel;
             }
 
-            public override void Reset(string newToken)
+            internal QuadCell(QuadPrefixTree _enclosing, byte[] bytes, int off, int len)
+                : base(bytes, off, len)
             {
-                base.Reset(newToken);
+                this._enclosing = _enclosing;
+            }
+
+            public override void Reset(byte[] bytes, int off, int len)
+            {
+                base.Reset(bytes, off, len);
                 shape = null;
             }
 
-            public override IList<Node> GetSubCells()
+            protected internal override ICollection<Cell> GetSubCells()
             {
-                var tree = (QuadPrefixTree)spatialPrefixTree;
-                var cells = new List<Node>(4)
-                      {
-                          new QuadCell(GetTokenString() + "A", tree),
-                          new QuadCell(GetTokenString() + "B", tree),
-                          new QuadCell(GetTokenString() + "C", tree),
-                          new QuadCell(GetTokenString() + "D", tree)
-                      };
+                IList<Cell> cells = new List<Cell>(4);
+                cells.Add(new QuadCell(_enclosing, TokenString + "A"));
+                cells.Add(new QuadCell(_enclosing, TokenString + "B"));
+                cells.Add(new QuadCell(_enclosing, TokenString + "C"));
+                cells.Add(new QuadCell(_enclosing, TokenString + "D"));
                 return cells;
             }
 
@@ -257,67 +275,80 @@ namespace Lucene.Net.Spatial.Prefix.Tree
                 return 4;
             }
 
-            public override Node GetSubCell(Point p)
+            public override Cell GetSubCell(Point p)
             {
-                return ((QuadPrefixTree)spatialPrefixTree).GetNode(p, GetLevel() + 1); //not performant!
+                return _enclosing.GetCell(p, Level + 1);
             }
 
-            private Shape shape;//cache
-
+            //not performant!
+            //cache
             public override Shape GetShape()
             {
                 if (shape == null)
+                {
                     shape = MakeShape();
+                }
                 return shape;
             }
 
             private Rectangle MakeShape()
             {
-                String token = GetTokenString();
-                var tree = ((QuadPrefixTree)spatialPrefixTree);
-                double xmin = tree.xmin;
-                double ymin = tree.ymin;
-
+                string token = TokenString;
+                double xmin = _enclosing.xmin;
+                double ymin = _enclosing.ymin;
                 for (int i = 0; i < token.Length; i++)
                 {
                     char c = token[i];
                     if ('A' == c || 'a' == c)
                     {
-                        ymin += tree.levelH[i];
-                    }
-                    else if ('B' == c || 'b' == c)
-                    {
-                        xmin += tree.levelW[i];
-                        ymin += tree.levelH[i];
-                    }
-                    else if ('C' == c || 'c' == c)
-                    {
-                        // nothing really
-                    }
-                    else if ('D' == c || 'd' == c)
-                    {
-                        xmin += tree.levelW[i];
+                        ymin += _enclosing.levelH[i];
                     }
                     else
                     {
-                        throw new Exception("unexpected char: " + c);
+                        if ('B' == c || 'b' == c)
+                        {
+                            xmin += _enclosing.levelW[i];
+                            ymin += _enclosing.levelH[i];
+                        }
+                        else
+                        {
+                            if ('C' == c || 'c' == c)
+                            {
+                            }
+                            else
+                            {
+                                // nothing really
+                                if ('D' == c || 'd' == c)
+                                {
+                                    xmin += _enclosing.levelW[i];
+                                }
+                                else
+                                {
+                                    throw new Exception("unexpected char: " + c);
+                                }
+                            }
+                        }
                     }
                 }
                 int len = token.Length;
-                double width, height;
+                double width;
+                double height;
                 if (len > 0)
                 {
-                    width = tree.levelW[len - 1];
-                    height = tree.levelH[len - 1];
+                    width = _enclosing.levelW[len - 1];
+                    height = _enclosing.levelH[len - 1];
                 }
                 else
                 {
-                    width = tree.gridW;
-                    height = tree.gridH;
+                    width = _enclosing.gridW;
+                    height = _enclosing.gridH;
                 }
-                return spatialPrefixTree.ctx.MakeRectangle(xmin, xmin + width, ymin, ymin + height);
+                return _enclosing.ctx.MakeRectangle(xmin, xmin + width, ymin, ymin + height);
             }
-        }//QuadCell
 
+            //QuadCell
+        }
+
+        #endregion
     }
-}
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTree.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTree.cs b/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTree.cs
index 908fded..e13245e 100644
--- a/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTree.cs
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTree.cs
@@ -1,268 +1,319 @@
-/*
+/* 
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 using System;
 using System.Collections.Generic;
 using System.Collections.ObjectModel;
 using System.Diagnostics;
 using System.Linq;
 using System.Runtime.CompilerServices;
+using System.Text;
 using Spatial4n.Core.Context;
 using Spatial4n.Core.Shapes;
 
 namespace Lucene.Net.Spatial.Prefix.Tree
 {
     /// <summary>
-    /// A spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings at variable lengths corresponding to
-    /// variable precision.  Each string corresponds to a spatial region.
-    /// 
-    /// Implementations of this class should be thread-safe and immutable once initialized. 
+    /// A spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings
+    /// at variable lengths corresponding to variable precision.
     /// </summary>
+    /// <remarks>
+    /// A spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings
+    /// at variable lengths corresponding to variable precision.   Each string
+    /// corresponds to a rectangular spatial region.  This approach is
+    /// also referred to "Grids", "Tiles", and "Spatial Tiers".
+    /// <p/>
+    /// Implementations of this class should be thread-safe and immutable once
+    /// initialized.
+    /// </remarks>
+    /// <lucene.experimental></lucene.experimental>
     public abstract class SpatialPrefixTree
     {
-        protected readonly int maxLevels;
-        internal readonly SpatialContext ctx;// it's internal to allow Node to access it
+        protected internal readonly int maxLevels;
+
+        protected internal readonly SpatialContext ctx;
 
-        protected SpatialPrefixTree(SpatialContext ctx, int maxLevels)
+        public SpatialPrefixTree(SpatialContext ctx, int maxLevels)
         {
             Debug.Assert(maxLevels > 0);
             this.ctx = ctx;
             this.maxLevels = maxLevels;
         }
 
-        public SpatialContext GetSpatialContext()
+        public virtual SpatialContext SpatialContext
         {
-            return ctx;
+            get { return ctx; }
         }
 
-        public int GetMaxLevels()
+        public virtual int MaxLevels
         {
-            return maxLevels;
+            get { return maxLevels; }
         }
 
-        public override String ToString()
+        public override string ToString()
         {
             return GetType().Name + "(maxLevels:" + maxLevels + ",ctx:" + ctx + ")";
         }
 
         /// <summary>
         /// Returns the level of the largest grid in which its longest side is less
-        /// than or equal to the provided distance (in degrees). Consequently {@link
-        /// dist} acts as an error epsilon declaring the amount of detail needed in the
+        /// than or equal to the provided distance (in degrees).
+        /// </summary>
+        /// <remarks>
+        /// Returns the level of the largest grid in which its longest side is less
+        /// than or equal to the provided distance (in degrees). Consequently
+        /// <code>dist</code>
+        /// acts as an error epsilon declaring the amount of detail needed in the
         /// grid, such that you can get a grid with just the right amount of
         /// precision.
-        /// </summary>
-        /// <param name="dist">>= 0</param>
+        /// </remarks>
+        /// <param name="dist">&gt;= 0</param>
         /// <returns>level [1 to maxLevels]</returns>
         public abstract int GetLevelForDistance(double dist);
 
-        //TODO double getDistanceForLevel(int level)
-
-        //[NotSerialized]
-        private Node worldNode;//cached
-
-        /*
-         * Returns the level 0 cell which encompasses all spatial data. Equivalent to {@link #getNode(String)} with "".
-         * This cell is threadsafe, just like a spatial prefix grid is, although cells aren't
-         * generally threadsafe.
-         * TODO rename to getTopCell or is this fine?
-         */
-        public Node GetWorldNode()
+        /// <summary>
+        /// Given a cell having the specified level, returns the distance from opposite
+        /// corners.
+        /// </summary>
+        /// <remarks>
+        /// Given a cell having the specified level, returns the distance from opposite
+        /// corners. Since this might very depending on where the cell is, this method
+        /// may over-estimate.
+        /// </remarks>
+        /// <param name="level">[1 to maxLevels]</param>
+        /// <returns>&gt; 0</returns>
+        public virtual double GetDistanceForLevel(int level)
         {
-            if (worldNode == null)
+            if (level < 1 || level > MaxLevels)
             {
-                worldNode = GetNode("");
+                throw new ArgumentException("Level must be in 1 to maxLevels range");
             }
-            return worldNode;
+            //TODO cache for each level
+            Cell cell = GetCell(ctx.GetWorldBounds().GetCenter(), level);
+            Rectangle bbox = cell.GetShape().GetBoundingBox();
+            double width = bbox.GetWidth();
+            double height = bbox.GetHeight();
+            //Use standard cartesian hypotenuse. For geospatial, this answer is larger
+            // than the correct one but it's okay to over-estimate.
+            return Math.Sqrt(width * width + height * height);
         }
 
-        /*
-         * The cell for the specified token. The empty string should be equal to {@link #getWorldNode()}.
-         * Precondition: Never called when token length > maxLevel.
-         */
-        public abstract Node GetNode(String token);
+        [System.NonSerialized]
+        private Cell worldCell;
 
-        public abstract Node GetNode(byte[] bytes, int offset, int len);
+        //cached
+        /// <summary>Returns the level 0 cell which encompasses all spatial data.</summary>
+        /// <remarks>
+        /// Returns the level 0 cell which encompasses all spatial data. Equivalent to
+        /// <see cref="GetCell(string)">GetCell(string)</see>
+        /// with "".
+        /// This cell is threadsafe, just like a spatial prefix grid is, although cells aren't
+        /// generally threadsafe.
+        /// TODO rename to getTopCell or is this fine?
+        /// </remarks>
+        public virtual Cell WorldCell
+        {
+            get
+            {
+                if (worldCell == null)
+                {
+                    worldCell = GetCell(string.Empty);
+                }
+                return worldCell;
+            }
+        }
 
-        //public Node GetNode(byte[] bytes, int offset, int len, Node target)
-        //{
-        //    if (target == null)
-        //    {
-        //        return GetNode(bytes, offset, len);
-        //    }
+        /// <summary>The cell for the specified token.</summary>
+        /// <remarks>
+        /// The cell for the specified token. The empty string should be equal to
+        /// <see cref="WorldCell">WorldCell</see>
+        /// .
+        /// Precondition: Never called when token length &gt; maxLevel.
+        /// </remarks>
+        public abstract Cell GetCell(string token);
 
-        //    target.Reset(bytes, offset, len);
-        //    return target;
-        //}
+        public abstract Cell GetCell(byte[] bytes, int offset, int len);
 
-        public Node GetNode(string token, Node target)
+        public Cell GetCell(byte[] bytes, int offset, int len, Cell target)
         {
             if (target == null)
             {
-                return GetNode(token);
+                return GetCell(bytes, offset, len);
             }
-
-            target.Reset(token);
+            target.Reset(bytes, offset, len);
             return target;
         }
 
-        protected virtual Node GetNode(Point p, int level)
+        /// <summary>
+        /// Returns the cell containing point
+        /// <code>p</code>
+        /// at the specified
+        /// <code>level</code>
+        /// .
+        /// </summary>
+        protected internal virtual Cell GetCell(Point p, int level)
         {
-            return GetNodes(p, level, false).ElementAt(0);
+            return GetCells(p, level, false)[0];
         }
 
-        /*
-         * Gets the intersecting & including cells for the specified shape, without exceeding detail level.
-         * The result is a set of cells (no dups), sorted. Unmodifiable.
-         * <p/>
-         * This implementation checks if shape is a Point and if so uses an implementation that
-         * recursively calls {@link Node#getSubCell(com.spatial4j.core.shape.Point)}. Cell subclasses
-         * ideally implement that method with a quick implementation, otherwise, subclasses should
-         * override this method to invoke {@link #getNodesAltPoint(com.spatial4j.core.shape.Point, int, boolean)}.
-         * TODO consider another approach returning an iterator -- won't build up all cells in memory.
-         */
-        public virtual IList<Node> GetNodes(Shape shape, int detailLevel, bool inclParents)
+        /// <summary>
+        /// Gets the intersecting cells for the specified shape, without exceeding
+        /// detail level.
+        /// </summary>
+        /// <remarks>
+        /// Gets the intersecting cells for the specified shape, without exceeding
+        /// detail level. If a cell is within the query shape then it's marked as a
+        /// leaf and none of its children are added.
+        /// <p/>
+        /// This implementation checks if shape is a Point and if so returns
+        /// <see cref="GetCells(Point, int, bool)">GetCells(Point, int, bool)
+        /// 	</see>
+        /// .
+        /// </remarks>
+        /// <param name="shape">the shape; non-null</param>
+        /// <param name="detailLevel">the maximum detail level to get cells for</param>
+        /// <param name="inclParents">
+        /// if true then all parent cells of leaves are returned
+        /// too. The top world cell is never returned.
+        /// </param>
+        /// <param name="simplify">
+        /// for non-point shapes, this will simply/aggregate sets of
+        /// complete leaves in a cell to its parent, resulting in
+        /// ~20-25% fewer cells.
+        /// </param>
+        /// <returns>a set of cells (no dups), sorted, immutable, non-null</returns>
+        public virtual IList<Cell> GetCells(Shape shape, int detailLevel
+            , bool inclParents, bool simplify)
         {
+            //TODO consider an on-demand iterator -- it won't build up all cells in memory.
             if (detailLevel > maxLevels)
             {
-                throw new ArgumentException("detailLevel > maxLevels", "detailLevel");
+                throw new ArgumentException("detailLevel > maxLevels");
             }
-
-            List<Node> cells;
             if (shape is Point)
             {
-                //optimized point algorithm
-                int initialCapacity = inclParents ? 1 + detailLevel : 1;
-                cells = new List<Node>(initialCapacity);
-                RecursiveGetNodes(GetWorldNode(), (Point)shape, detailLevel, true, cells);
-                Debug.Assert(cells.Count == initialCapacity);
-            }
-            else
-            {
-                cells = new List<Node>(inclParents ? 1024 : 512);
-                RecursiveGetNodes(GetWorldNode(), shape, detailLevel, inclParents, cells);
-            }
-            if (inclParents)
-            {
-                Debug.Assert(cells[0].GetLevel() == 0);
-                cells.RemoveAt(0);//remove getWorldNode()
+                return GetCells((Point)shape, detailLevel, inclParents);
             }
+            IList<Cell> cells = new List<Cell>(inclParents ? 4096 : 2048);
+            RecursiveGetCells(WorldCell, shape, detailLevel, inclParents, simplify, cells
+                );
             return cells;
         }
 
-        private void RecursiveGetNodes(Node node, Shape shape, int detailLevel, bool inclParents, IList<Node> result)
+        /// <summary>Returns true if cell was added as a leaf.</summary>
+        /// <remarks>
+        /// Returns true if cell was added as a leaf. If it wasn't it recursively
+        /// descends.
+        /// </remarks>
+        private bool RecursiveGetCells(Cell cell, Shape shape, int
+             detailLevel, bool inclParents, bool simplify, IList<Cell> result)
         {
-            if (node.IsLeaf())
-            {//cell is within shape
-                result.Add(node);
-                return;
+            if (cell.Level == detailLevel)
+            {
+                cell.SetLeaf();
             }
-
-            var subCells = node.GetSubCells(shape);
-            if (node.GetLevel() == detailLevel - 1)
+            //FYI might already be a leaf
+            if (cell.IsLeaf())
+            {
+                result.Add(cell);
+                return true;
+            }
+            if (inclParents && cell.Level != 0)
             {
-                if (subCells.Count < node.GetSubCellsSize())
+                result.Add(cell);
+            }
+            ICollection<Cell> subCells = cell.GetSubCells(shape);
+            int leaves = 0;
+            foreach (Cell subCell in subCells)
+            {
+                if (RecursiveGetCells(subCell, shape, detailLevel, inclParents, simplify, result))
                 {
-                    if (inclParents)
-                        result.Add(node);
-                    foreach (var subCell in subCells)
-                    {
-                        subCell.SetLeaf();
-                        result.Add(subCell);
-                    }
-                }
-                else
-                {//a bottom level (i.e. detail level) optimization where all boxes intersect, so use parent cell.
-                    node.SetLeaf();
-                    result.Add(node);
+                    leaves++;
                 }
             }
-            else
+            //can we simplify?
+            if (simplify && leaves == cell.GetSubCellsSize() && cell.Level != 0)
             {
-                if (inclParents)
+                do
                 {
-                    result.Add(node);
+                    //Optimization: substitute the parent as a leaf instead of adding all
+                    // children as leaves
+                    //remove the leaves
+                    result.RemoveAt(result.Count - 1);
                 }
-                foreach (var subCell in subCells)
+                while (--leaves > 0);
+                //remove last
+                //add cell as the leaf
+                cell.SetLeaf();
+                if (!inclParents)
                 {
-                    RecursiveGetNodes(subCell, shape, detailLevel, inclParents, result);//tail call
+                    // otherwise it was already added up above
+                    result.Add(cell);
                 }
+                return true;
             }
+            return false;
         }
 
-        private void RecursiveGetNodes(Node node, Point point, int detailLevel, bool inclParents, IList<Node> result)
-        {
-            if (inclParents)
-            {
-                result.Add(node);
-            }
-            Node pCell = node.GetSubCell(point);
-            if (node.GetLevel() == detailLevel - 1)
-            {
-                pCell.SetLeaf();
-                result.Add(pCell);
-            }
-            else
-            {
-                RecursiveGetNodes(pCell, point, detailLevel, inclParents, result);//tail call
-            }
-        }
-
-        /*
-         * Subclasses might override {@link #getNodes(com.spatial4j.core.shape.Shape, int, boolean)}
-         * and check if the argument is a shape and if so, delegate
-         * to this implementation, which calls {@link #getNode(com.spatial4j.core.shape.Point, int)} and
-         * then calls {@link #getNode(String)} repeatedly if inclParents is true.
-         */
-        protected virtual IList<Node> GetNodesAltPoint(Point p, int detailLevel, bool inclParents)
+        /// <summary>
+        /// A Point-optimized implementation of
+        /// <see cref="GetCells(Shape, int, bool, bool)">GetCells(Shape, int, bool, bool)
+        /// 	</see>
+        /// . That
+        /// method in facts calls this for points.
+        /// <p/>
+        /// This implementation depends on
+        /// <see cref="GetCell(string)">GetCell(string)</see>
+        /// being fast, as its
+        /// called repeatedly when incPlarents is true.
+        /// </summary>
+        public virtual IList<Cell> GetCells(Point p, int detailLevel, bool inclParents)
         {
-            Node cell = GetNode(p, detailLevel);
+            Cell cell = GetCell(p, detailLevel);
             if (!inclParents)
             {
 #if !NET35
-                return new ReadOnlyCollectionBuilder<Node>(new[] { cell }).ToReadOnlyCollection();
+                return new ReadOnlyCollectionBuilder<Cell>(new[] { cell }).ToReadOnlyCollection();
 #else
-                return new List<Node>(new[] { cell }).AsReadOnly();
+                return new List<Cell>(new[] { cell }).AsReadOnly();
 #endif
             }
-
-            String endToken = cell.GetTokenString();
-            Debug.Assert(endToken.Length == detailLevel);
-            var cells = new List<Node>(detailLevel);
+            string endToken = cell.TokenString;
+            System.Diagnostics.Debug.Assert(endToken.Length == detailLevel);
+            IList<Cell> cells = new List<Cell>(detailLevel);
             for (int i = 1; i < detailLevel; i++)
             {
-                cells.Add(GetNode(endToken.Substring(0, i)));
+                cells.Add(GetCell(endToken.Substring(0, i)));
             }
             cells.Add(cell);
             return cells;
         }
 
-        /*
-         * Will add the trailing leaf byte for leaves. This isn't particularly efficient.
-         */
-        public static List<String> NodesToTokenStrings(Collection<Node> nodes)
+        /// <summary>Will add the trailing leaf byte for leaves.</summary>
+        /// <remarks>Will add the trailing leaf byte for leaves. This isn't particularly efficient.
+        /// 	</remarks>
+        public static IList<string> CellsToTokenStrings(ICollection<Cell> cells)
         {
-            var tokens = new List<String>((nodes.Count));
-            foreach (Node node in nodes)
+            IList<string> tokens = new List<string>((cells.Count));
+            foreach (Cell cell in cells)
             {
-                String token = node.GetTokenString();
-                if (node.IsLeaf())
+                string token = cell.TokenString;
+                if (cell.IsLeaf())
                 {
-                    tokens.Add(token + (char)Node.LEAF_BYTE);
+                    tokens.Add(token + (char)Cell.LEAF_BYTE);
                 }
                 else
                 {
@@ -271,6 +322,5 @@ namespace Lucene.Net.Spatial.Prefix.Tree
             }
             return tokens;
         }
-
     }
 }


Mime
View raw message