lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [3/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:43 GMT
Some code fixes to Spatial, merging in before re-porting from 4.8.0

Closes #20 and closes #12


Project: http://git-wip-us.apache.org/repos/asf/lucenenet/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucenenet/commit/dc71f60d
Tree: http://git-wip-us.apache.org/repos/asf/lucenenet/tree/dc71f60d
Diff: http://git-wip-us.apache.org/repos/asf/lucenenet/diff/dc71f60d

Branch: refs/heads/master
Commit: dc71f60de96d092e6de3a8a5743f5cb75427346c
Parents: 8223d54
Author: Itamar Syn-Hershko <itamar@code972.com>
Authored: Sun Mar 8 23:51:19 2015 +0200
Committer: Itamar Syn-Hershko <itamar@code972.com>
Committed: Sun Mar 8 23:51:19 2015 +0200

----------------------------------------------------------------------
 src/Lucene.Net.Spatial/BBox/AreaSimilarity.cs   |  12 +-
 src/Lucene.Net.Spatial/BBox/BBoxSimilarity.cs   |   2 +-
 .../BBox/BBoxSimilarityValueSource.cs           | 102 ++--
 src/Lucene.Net.Spatial/BBox/BBoxStrategy.cs     |  48 +-
 .../BBox/DistanceSimilarity.cs                  |   4 +-
 src/Lucene.Net.Spatial/DisjointSpatialFilter.cs | 144 +++++
 .../Prefix/AbstractPrefixTreeFilter.cs          | 134 +++++
 .../Prefix/AbstractVisitingPrefixTreeFilter.cs  | 531 +++++++++++++++++++
 .../Prefix/ContainsPrefixTreeFilter.cs          | 364 +++++++++++++
 .../Prefix/IntersectsPrefixTreeFilter.cs        | 125 +++++
 .../Prefix/PointPrefixTreeFieldCacheProvider.cs |  43 +-
 .../Prefix/PrefixTreeStrategy.cs                | 213 +++++---
 .../Prefix/RecursivePrefixTreeStrategy.cs       |  91 +++-
 .../Prefix/TermQueryPrefixTreeStrategy.cs       |  52 +-
 src/Lucene.Net.Spatial/Prefix/Tree/Cell.cs      | 329 ++++++++++++
 .../Prefix/Tree/GeohashPrefixTree.cs            | 167 +++---
 src/Lucene.Net.Spatial/Prefix/Tree/Node.cs      |   6 +-
 .../Prefix/Tree/QuadPrefixTree.cs               | 343 ++++++------
 .../Prefix/Tree/SpatialPrefixTree.cs            | 360 +++++++------
 .../Prefix/Tree/SpatialPrefixTreeFactory.cs     | 109 ++--
 .../Prefix/WithinPrefixTreeFilter.cs            | 297 +++++++++++
 src/Lucene.Net.Spatial/Queries/SpatialArgs.cs   |   4 +-
 .../Queries/SpatialArgsParser.cs                |   8 +-
 .../Queries/SpatialOperation.cs                 |   8 +-
 .../Queries/UnsupportedSpatialOperation.cs      |   5 +-
 src/Lucene.Net.Spatial/SpatialStrategy.cs       |  21 +-
 .../Util/CachingDoubleValueSource.cs            |  79 +--
 .../Util/CompatibilityExtensions.cs             | 161 +-----
 src/Lucene.Net.Spatial/Util/FunctionQuery.cs    |   2 +-
 .../Util/ReciprocalFloatFunction.cs             |   4 +-
 src/Lucene.Net.Spatial/Util/ShapeFieldCache.cs  |   2 +-
 .../Util/ShapeFieldCacheDistanceValueSource.cs  |  22 +-
 .../Util/ShapeFieldCacheProvider.cs             |  87 +--
 .../Util/ValueSourceFilter.cs                   |  15 +-
 .../Vector/DistanceValueSource.cs               |  99 ++--
 .../Vector/PointVectorStrategy.cs               |  52 +-
 36 files changed, 3083 insertions(+), 962 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/BBox/AreaSimilarity.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/BBox/AreaSimilarity.cs b/src/Lucene.Net.Spatial/BBox/AreaSimilarity.cs
index fde6e10..88c8aaa 100644
--- a/src/Lucene.Net.Spatial/BBox/AreaSimilarity.cs
+++ b/src/Lucene.Net.Spatial/BBox/AreaSimilarity.cs
@@ -1,4 +1,4 @@
-/*
+/*
  * 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.
@@ -49,9 +49,9 @@ namespace Lucene.Net.Spatial.BBox
     /// </summary>
     public class AreaSimilarity : BBoxSimilarity
     {
-       /*
-        * Properties associated with the query envelope
-        */
+        /*
+         * Properties associated with the query envelope
+         */
         private readonly Rectangle queryExtent;
         private readonly double queryArea;
 
@@ -188,7 +188,7 @@ namespace Lucene.Net.Spatial.BBox
                     //        sb.append("\n  queryFactor=").append(queryFactor).append(" targetFactor=").append(targetFactor);
                     //        sb.append(" (queryPower=").append(queryPower).append(" targetPower=").append(targetPower).append(")");
 
-                    exp.Value = (float) score;
+                    exp.Value = (float)score;
                     exp.Description = GetType().Name;
 
                     Explanation e = null;
@@ -226,6 +226,6 @@ namespace Lucene.Net.Spatial.BBox
         public override int GetHashCode()
         {
             return GetDelimiterQueryParameters().GetHashCode();
-        } 
+        }
     }
 }

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/BBox/BBoxSimilarity.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/BBox/BBoxSimilarity.cs b/src/Lucene.Net.Spatial/BBox/BBoxSimilarity.cs
index a18baa4..6636961 100644
--- a/src/Lucene.Net.Spatial/BBox/BBoxSimilarity.cs
+++ b/src/Lucene.Net.Spatial/BBox/BBoxSimilarity.cs
@@ -1,4 +1,4 @@
-/*
+/*
  * 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.

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/BBox/BBoxSimilarityValueSource.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/BBox/BBoxSimilarityValueSource.cs b/src/Lucene.Net.Spatial/BBox/BBoxSimilarityValueSource.cs
index 6939274..fee54ad 100644
--- a/src/Lucene.Net.Spatial/BBox/BBoxSimilarityValueSource.cs
+++ b/src/Lucene.Net.Spatial/BBox/BBoxSimilarityValueSource.cs
@@ -1,4 +1,4 @@
-/*
+/*
  * 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.
@@ -15,19 +15,19 @@
  * limitations under the License.
  */
 
+using System.Collections.Generic;
 using Lucene.Net.Index;
 using Lucene.Net.Search;
 using Lucene.Net.Search.Function;
-using Lucene.Net.Spatial.Util;
+using Lucene.Net.Util;
 using Spatial4n.Core.Shapes;
-using Spatial4n.Core.Shapes.Impl;
 
 namespace Lucene.Net.Spatial.BBox
 {
     public class BBoxSimilarityValueSource : ValueSource
     {
-        private readonly BBoxStrategy strategy;
         private readonly BBoxSimilarity similarity;
+        private readonly BBoxStrategy strategy;
 
         public BBoxSimilarityValueSource(BBoxStrategy strategy, BBoxSimilarity similarity)
         {
@@ -35,55 +35,79 @@ namespace Lucene.Net.Spatial.BBox
             this.similarity = similarity;
         }
 
-        private class BBoxSimilarityValueSourceDocValues : DocValues
+        public override string Description
+        {
+            get { return "BBoxSimilarityValueSource(" + similarity + ")"; }
+        }
+
+        public override FunctionValues GetValues(IDictionary<object, object> context, AtomicReaderContext readerContext)
+        {
+            return new BBoxSimilarityValueSourceFunctionValue(readerContext.AtomicReader, this);
+        }
+
+        public override bool Equals(object o)
+        {
+            var other = o as BBoxSimilarityValueSource;
+            if (other == null) return false;
+            return similarity.Equals(other.similarity);
+        }
+
+        public override int GetHashCode()
+        {
+            return typeof(BBoxSimilarityValueSource).GetHashCode() + similarity.GetHashCode();
+        }
+
+        #region Nested type: BBoxSimilarityValueSourceFunctionValue
+
+        private class BBoxSimilarityValueSourceFunctionValue : FunctionValues
         {
             private readonly BBoxSimilarityValueSource _enclosingInstance;
+            private readonly FieldCache.Doubles maxX, maxY;
+            private readonly FieldCache.Doubles minX, minY;
             private readonly Rectangle rect;
-            private readonly double[] minX;
-            private readonly double[] minY;
-            private readonly double[] maxX;
-            private readonly double[] maxY;
 
-            private readonly IBits validMinX, validMaxX;
+            private readonly IBits validMaxX;
+            private readonly IBits validMinX;
 
-            public BBoxSimilarityValueSourceDocValues(IndexReader reader, BBoxSimilarityValueSource enclosingInstance)
+            public BBoxSimilarityValueSourceFunctionValue(AtomicReader reader,
+                                                          BBoxSimilarityValueSource enclosingInstance)
             {
                 _enclosingInstance = enclosingInstance;
-                rect = _enclosingInstance.strategy.GetSpatialContext().MakeRectangle(0, 0, 0, 0); //reused
+                rect = _enclosingInstance.strategy.SpatialContext.MakeRectangle(0, 0, 0, 0); //reused
 
-                minX = FieldCache_Fields.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_minX/*, true*/);
-                minY = FieldCache_Fields.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_minY/*, true*/);
-                maxX = FieldCache_Fields.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_maxX/*, true*/);
-                maxY = FieldCache_Fields.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_maxY/*, true*/);
+                minX = FieldCache.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_minX, true);
+                minY = FieldCache.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_minY, true);
+                maxX = FieldCache.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_maxX, true);
+                maxY = FieldCache.DEFAULT.GetDoubles(reader, enclosingInstance.strategy.field_maxY, true);
 
-                validMinX = FieldCache_Fields.DEFAULT.GetDocsWithField(reader, enclosingInstance.strategy.field_minX);
-                validMaxX = FieldCache_Fields.DEFAULT.GetDocsWithField(reader, enclosingInstance.strategy.field_maxX);
+                validMinX = FieldCache.DEFAULT.GetDocsWithField(reader, enclosingInstance.strategy.field_minX);
+                validMaxX = FieldCache.DEFAULT.GetDocsWithField(reader, enclosingInstance.strategy.field_maxX);
             }
 
             public override float FloatVal(int doc)
             {
                 // make sure it has minX and area
-                if (validMinX.Get(doc) && validMaxX.Get(doc))
+                if (validMinX[doc] && validMaxX[doc])
                 {
                     rect.Reset(
-                        minX[doc], maxX[doc],
-                        minY[doc], maxY[doc]);
-                    return (float) _enclosingInstance.similarity.Score(rect, null);
+                        minX.Get(doc), maxX.Get(doc),
+                        minY.Get(doc), maxY.Get(doc));
+                    return (float)_enclosingInstance.similarity.Score(rect, null);
                 }
                 else
                 {
-                    return (float) _enclosingInstance.similarity.Score(null, null);
+                    return (float)_enclosingInstance.similarity.Score(null, null);
                 }
             }
 
             public override Explanation Explain(int doc)
             {
                 // make sure it has minX and area
-                if (validMinX.Get(doc) && validMaxX.Get(doc))
+                if (validMinX[doc] && validMaxX[doc])
                 {
                     rect.Reset(
-                        minX[doc], maxX[doc],
-                        minY[doc], maxY[doc]);
+                        minX.Get(doc), maxX.Get(doc),
+                        minY.Get(doc), maxY.Get(doc));
                     var exp = new Explanation();
                     _enclosingInstance.similarity.Score(rect, exp);
                     return exp;
@@ -93,30 +117,10 @@ namespace Lucene.Net.Spatial.BBox
 
             public override string ToString(int doc)
             {
-                return _enclosingInstance.Description() + "=" + FloatVal(doc);
+                return _enclosingInstance.Description + "=" + FloatVal(doc);
             }
         }
 
-        public override DocValues GetValues(IndexReader reader)
-        {
-            return new BBoxSimilarityValueSourceDocValues(reader, this);
-        }
-
-        public override string Description()
-        {
-            return "BBoxSimilarityValueSource(" + similarity + ")";
-        }
-
-        public override bool Equals(object o)
-        {
-            var other = o as BBoxSimilarityValueSource;
-            if (other == null) return false;
-            return similarity.Equals(other.similarity);
-        }
-
-        public override int GetHashCode()
-        {
-            return typeof(BBoxSimilarityValueSource).GetHashCode() + similarity.GetHashCode();
-        }
+        #endregion
     }
-}
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/BBox/BBoxStrategy.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/BBox/BBoxStrategy.cs b/src/Lucene.Net.Spatial/BBox/BBoxStrategy.cs
index f14af08..d2acf1a 100644
--- a/src/Lucene.Net.Spatial/BBox/BBoxStrategy.cs
+++ b/src/Lucene.Net.Spatial/BBox/BBoxStrategy.cs
@@ -1,4 +1,4 @@
-/*
+/*
  * 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.
@@ -36,9 +36,9 @@ namespace Lucene.Net.Spatial.BBox
         public static String SUFFIX_XDL = "__xdl";
 
         /*
-         * The Bounding Box gets stored as four fields for x/y min/max and a flag
-         * that says if the box crosses the dateline (xdl).
-         */
+		 * The Bounding Box gets stored as four fields for x/y min/max and a flag
+		 * that says if the box crosses the dateline (xdl).
+		 */
         public readonly String field_bbox;
         public readonly String field_minX;
         public readonly String field_minY;
@@ -72,7 +72,7 @@ namespace Lucene.Net.Spatial.BBox
         // Indexing
         //---------------------------------
 
-        public override AbstractField[] CreateIndexableFields(Shape shape)
+        public override Field[] CreateIndexableFields(Shape shape)
         {
             var rect = shape as Rectangle;
             if (rect != null)
@@ -80,29 +80,28 @@ namespace Lucene.Net.Spatial.BBox
             throw new InvalidOperationException("Can only index Rectangle, not " + shape);
         }
 
-        public AbstractField[] CreateIndexableFields(Rectangle bbox)
+        public Field[] CreateIndexableFields(Rectangle bbox)
         {
-            var fields = new AbstractField[5];
+            var fields = new Field[5];
             fields[0] = DoubleField(field_minX, bbox.GetMinX());
             fields[1] = DoubleField(field_maxX, bbox.GetMaxX());
             fields[2] = DoubleField(field_minY, bbox.GetMinY());
             fields[3] = DoubleField(field_maxY, bbox.GetMaxY());
-            fields[4] = new Field(field_xdl, bbox.GetCrossesDateLine() ? "T" : "F", Field.Store.NO,
-                                  Field.Index.NOT_ANALYZED_NO_NORMS) {OmitNorms = true, OmitTermFreqAndPositions = true};
+            fields[4] = new StringField(field_xdl, bbox.GetCrossesDateLine() ? "T" : "F", Field.Store.NO);
             return fields;
         }
 
-        private AbstractField DoubleField(string field, double value)
+        private Field DoubleField(string field, double value)
         {
-            var f = new NumericField(field, precisionStep, Field.Store.NO, true)
-                        {OmitNorms = true, OmitTermFreqAndPositions = true};
-            f.SetDoubleValue(value);
-            return f;
+            return new DoubleField(field, value, new FieldType(Documents.DoubleField.TYPE_NOT_STORED)
+                                                     {
+                                                         NumericPrecisionStep = precisionStep
+                                                     });
         }
 
         public override ValueSource MakeDistanceValueSource(Point queryPoint)
         {
-            return new BBoxSimilarityValueSource(this, new DistanceSimilarity(this.GetSpatialContext(), queryPoint));
+            return new BBoxSimilarityValueSource(this, new DistanceSimilarity(this.SpatialContext, queryPoint));
         }
 
         public ValueSource MakeBBoxAreaSimilarityValueSource(Rectangle queryBox)
@@ -315,14 +314,14 @@ namespace Lucene.Net.Spatial.BBox
             Query qMinY = NumericRangeQuery.NewDoubleRange(field_minY, precisionStep, bbox.GetMinY(), bbox.GetMinY(), true, true);
             Query qMaxX = NumericRangeQuery.NewDoubleRange(field_maxX, precisionStep, bbox.GetMaxX(), bbox.GetMaxX(), true, true);
             Query qMaxY = NumericRangeQuery.NewDoubleRange(field_maxY, precisionStep, bbox.GetMaxY(), bbox.GetMaxY(), true, true);
-            
+
             var bq = new BooleanQuery
-                         {
-                             {qMinX, Occur.MUST},
-                             {qMinY, Occur.MUST},
-                             {qMaxX, Occur.MUST},
-                             {qMaxY, Occur.MUST}
-                         };
+			         	{
+			         		{qMinX, Occur.MUST},
+			         		{qMinY, Occur.MUST},
+			         		{qMaxX, Occur.MUST},
+			         		{qMaxY, Occur.MUST}
+			         	};
             return bq;
         }
 
@@ -345,7 +344,7 @@ namespace Lucene.Net.Spatial.BBox
             Query qIsNonXDL = this.MakeXDL(false);
             Query qIsXDL = this.MakeXDL(true);
             Query qHasEnv = this.MakeQuery(new Query[] { qIsNonXDL, qIsXDL }, Occur.SHOULD);
-            var qNotDisjoint = new BooleanQuery {{qHasEnv, Occur.MUST}, {qDisjoint, Occur.MUST_NOT}};
+            var qNotDisjoint = new BooleanQuery { { qHasEnv, Occur.MUST }, { qDisjoint, Occur.MUST_NOT } };
 
             //Query qDisjoint = makeDisjoint();
             //BooleanQuery qNotDisjoint = new BooleanQuery();
@@ -477,8 +476,7 @@ namespace Lucene.Net.Spatial.BBox
          */
         public Query MakeXDL(bool crossedDateLine, Query query)
         {
-            var bq = new BooleanQuery
-                         {{this.MakeXDL(crossedDateLine), Occur.MUST}, {query, Occur.MUST}};
+            var bq = new BooleanQuery { { this.MakeXDL(crossedDateLine), Occur.MUST }, { query, Occur.MUST } };
             return bq;
         }
     }

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/BBox/DistanceSimilarity.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/BBox/DistanceSimilarity.cs b/src/Lucene.Net.Spatial/BBox/DistanceSimilarity.cs
index 9b7c88b..a9fe4b1 100644
--- a/src/Lucene.Net.Spatial/BBox/DistanceSimilarity.cs
+++ b/src/Lucene.Net.Spatial/BBox/DistanceSimilarity.cs
@@ -1,4 +1,4 @@
-/*
+/*
  * 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.
@@ -52,7 +52,7 @@ namespace Lucene.Net.Spatial.BBox
             }
             if (exp != null)
             {
-                exp.Value = (float) score;
+                exp.Value = (float)score;
                 exp.Description = GetType().Name;
                 exp.AddDetail(new Explanation(-1f, "" + queryPoint));
                 exp.AddDetail(new Explanation(-1f, "" + indexRect));

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/DisjointSpatialFilter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/DisjointSpatialFilter.cs b/src/Lucene.Net.Spatial/DisjointSpatialFilter.cs
new file mode 100644
index 0000000..ab6fa3f
--- /dev/null
+++ b/src/Lucene.Net.Spatial/DisjointSpatialFilter.cs
@@ -0,0 +1,144 @@
+/* 
+ * 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 Lucene.Net.Index;
+using Lucene.Net.Search;
+using Lucene.Net.Spatial.Queries;
+using Lucene.Net.Util;
+
+namespace Lucene.Net.Spatial
+{
+    /// <summary>
+    /// A Spatial Filter implementing
+    /// <see cref="SpatialOperation.IsDisjointTo">Org.Apache.Lucene.Spatial.Query.SpatialOperation.IsDisjointTo
+    /// 	</see>
+    /// in terms
+    /// of a
+    /// <see cref="SpatialStrategy">SpatialStrategy</see>
+    /// 's support for
+    /// <see cref="SpatialOperation.Intersects">Org.Apache.Lucene.Spatial.Query.SpatialOperation.Intersects
+    /// 	</see>
+    /// .
+    /// A document is considered disjoint if it has spatial data that does not
+    /// intersect with the query shape.  Another way of looking at this is that it's
+    /// a way to invert a query shape.
+    /// </summary>
+    /// <lucene.experimental></lucene.experimental>
+    public class DisjointSpatialFilter : Filter
+    {
+        private readonly string field;
+
+        private readonly Filter intersectsFilter;
+
+        /// <param name="strategy">Needed to compute intersects</param>
+        /// <param name="args">Used in spatial intersection</param>
+        /// <param name="field">
+        /// This field is used to determine which docs have spatial data via
+        /// <see cref="Org.Apache.Lucene.Search.FieldCache.GetDocsWithField(Org.Apache.Lucene.Index.AtomicReader, string)
+        /// 	">Org.Apache.Lucene.Search.FieldCache.GetDocsWithField(Org.Apache.Lucene.Index.AtomicReader, string)
+        /// 	</see>
+        /// .
+        /// Passing null will assume all docs have spatial data.
+        /// </param>
+        public DisjointSpatialFilter(SpatialStrategy strategy, SpatialArgs args, string field
+            )
+        {
+            //maybe null
+            this.field = field;
+            // TODO consider making SpatialArgs cloneable
+            SpatialOperation origOp = args.Operation;
+            //copy so we can restore
+            args.Operation = SpatialOperation.Intersects;
+            //temporarily set to intersects
+            intersectsFilter = strategy.MakeFilter(args);
+            args.Operation = origOp;
+        }
+
+        //restore so it looks like it was
+        public override bool Equals(object o)
+        {
+            if (this == o)
+            {
+                return true;
+            }
+            if (o == null || GetType() != o.GetType())
+            {
+                return false;
+            }
+            var that = (DisjointSpatialFilter)o;
+            if (field != null ? !field.Equals(that.field) : that.field != null)
+            {
+                return false;
+            }
+            if (!intersectsFilter.Equals(that.intersectsFilter))
+            {
+                return false;
+            }
+            return true;
+        }
+
+        public override int GetHashCode()
+        {
+            int result = field != null ? field.GetHashCode() : 0;
+            result = 31 * result + intersectsFilter.GetHashCode();
+            return result;
+        }
+
+        /// <exception cref="System.IO.IOException"></exception>
+        public override DocIdSet GetDocIdSet(AtomicReaderContext context, IBits acceptDocs
+            )
+        {
+            IBits docsWithField;
+            if (field == null)
+            {
+                docsWithField = null;
+            }
+            else
+            {
+                //all docs
+                //NOTE By using the FieldCache we re-use a cache
+                // which is nice but loading it in this way might be slower than say using an
+                // intersects filter against the world bounds. So do we add a method to the
+                // strategy, perhaps?  But the strategy can't cache it.
+                docsWithField = FieldCache.DEFAULT.GetDocsWithField((context.AtomicReader), field);
+                int maxDoc = context.AtomicReader.MaxDoc;
+                if (docsWithField.Length != maxDoc)
+                {
+                    throw new InvalidOperationException("Bits length should be maxDoc (" + maxDoc + ") but wasn't: "
+                                                        + docsWithField);
+                }
+                if (docsWithField is Bits.MatchNoBits)
+                {
+                    return null;
+                }
+                else
+                {
+                    //match nothing
+                    if (docsWithField is Bits.MatchAllBits)
+                    {
+                        docsWithField = null;
+                    }
+                }
+            }
+            //all docs
+            //not so much a chain but a way to conveniently invert the Filter
+            DocIdSet docIdSet = new ChainedFilter(new[] { intersectsFilter }, ChainedFilter.ANDNOT).GetDocIdSet(context,
+                                                                                                              acceptDocs);
+            return BitsFilteredDocIdSet.Wrap(docIdSet, docsWithField);
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/AbstractPrefixTreeFilter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/AbstractPrefixTreeFilter.cs b/src/Lucene.Net.Spatial/Prefix/AbstractPrefixTreeFilter.cs
new file mode 100644
index 0000000..efcf078
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/AbstractPrefixTreeFilter.cs
@@ -0,0 +1,134 @@
+/* 
+ * 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.Diagnostics;
+using Lucene.Net.Index;
+using Lucene.Net.Search;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Util;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+    /// <summary>Base class for Lucene Filters on SpatialPrefixTree fields.</summary>
+    /// <remarks>Base class for Lucene Filters on SpatialPrefixTree fields.</remarks>
+    /// <lucene.experimental></lucene.experimental>
+    public abstract class AbstractPrefixTreeFilter : Filter
+    {
+        protected internal readonly int detailLevel;
+        protected internal readonly string fieldName;
+
+        protected internal readonly SpatialPrefixTree grid;
+        protected internal readonly Shape queryShape;
+
+        public AbstractPrefixTreeFilter(Shape queryShape, string
+                                                              fieldName, SpatialPrefixTree grid, int detailLevel)
+        {
+            //not in equals/hashCode since it's implied for a specific field
+            this.queryShape = queryShape;
+            this.fieldName = fieldName;
+            this.grid = grid;
+            this.detailLevel = detailLevel;
+        }
+
+        public override bool Equals(object o)
+        {
+            if (this == o)
+            {
+                return true;
+            }
+            if (!GetType().Equals(o.GetType()))
+            {
+                return false;
+            }
+            var that = (AbstractPrefixTreeFilter)o;
+            if (detailLevel != that.detailLevel)
+            {
+                return false;
+            }
+            if (!fieldName.Equals(that.fieldName))
+            {
+                return false;
+            }
+            if (!queryShape.Equals(that.queryShape))
+            {
+                return false;
+            }
+            return true;
+        }
+
+        public override int GetHashCode()
+        {
+            int result = queryShape.GetHashCode();
+            result = 31 * result + fieldName.GetHashCode();
+            result = 31 * result + detailLevel;
+            return result;
+        }
+
+        #region Nested type: BaseTermsEnumTraverser
+
+        /// <summary>
+        /// Holds transient state and docid collecting utility methods as part of
+        /// traversing a
+        /// <see cref="TermsEnum">Lucene.Net.Index.TermsEnum</see>
+        /// .
+        /// </summary>
+        public abstract class BaseTermsEnumTraverser
+        {
+            private readonly AbstractPrefixTreeFilter _enclosing;
+            protected internal readonly AtomicReaderContext context;
+
+            protected internal readonly int maxDoc;
+            protected internal IBits acceptDocs;
+
+            protected internal DocsEnum docsEnum;
+            protected internal TermsEnum termsEnum;
+
+            /// <exception cref="System.IO.IOException"></exception>
+            public BaseTermsEnumTraverser(AbstractPrefixTreeFilter _enclosing, AtomicReaderContext
+                                                                                   context, IBits acceptDocs)
+            {
+                this._enclosing = _enclosing;
+                //remember to check for null in getDocIdSet
+                this.context = context;
+                AtomicReader reader = context.AtomicReader;
+                this.acceptDocs = acceptDocs;
+                maxDoc = reader.MaxDoc;
+                Terms terms = reader.Terms(this._enclosing.fieldName);
+                if (terms != null)
+                {
+                    termsEnum = terms.Iterator(null);
+                }
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal virtual void CollectDocs(FixedBitSet bitSet)
+            {
+                //WARN: keep this specialization in sync
+                Debug.Assert(termsEnum != null);
+                docsEnum = termsEnum.Docs(acceptDocs, docsEnum, DocsEnum.FLAG_NONE
+                    );
+                int docid;
+                while ((docid = docsEnum.NextDoc()) != DocIdSetIterator.NO_MORE_DOCS)
+                {
+                    bitSet.Set(docid);
+                }
+            }
+        }
+
+        #endregion
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/AbstractVisitingPrefixTreeFilter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/AbstractVisitingPrefixTreeFilter.cs b/src/Lucene.Net.Spatial/Prefix/AbstractVisitingPrefixTreeFilter.cs
new file mode 100644
index 0000000..f187216
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/AbstractVisitingPrefixTreeFilter.cs
@@ -0,0 +1,531 @@
+/* 
+ * 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;
+using System.Collections.Generic;
+using System.Diagnostics;
+using Lucene.Net.Index;
+using Lucene.Net.Search;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Spatial.Util;
+using Lucene.Net.Util;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+    /// <summary>
+    /// Traverses a
+    /// <see cref="Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree">Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree
+    /// 	</see>
+    /// indexed field, using the template &
+    /// visitor design patterns for subclasses to guide the traversal and collect
+    /// matching documents.
+    /// <p/>
+    /// Subclasses implement
+    /// <see cref="Lucene.Net.Search.Filter.GetDocIdSet(AtomicReaderContext, Bits)
+    /// 	">Lucene.Search.Filter.GetDocIdSet(AtomicReaderContext, Bits)
+    /// 	</see>
+    /// by instantiating a custom
+    /// <see cref="VisitorTemplate">VisitorTemplate</see>
+    /// subclass (i.e. an anonymous inner class) and implement the
+    /// required methods.
+    /// </summary>
+    /// <lucene.internal></lucene.internal>
+    public abstract class AbstractVisitingPrefixTreeFilter : AbstractPrefixTreeFilter
+    {
+        protected internal readonly int prefixGridScanLevel;
+
+        public AbstractVisitingPrefixTreeFilter(Shape queryShape
+                                                , string fieldName, SpatialPrefixTree grid, int detailLevel,
+                                                int prefixGridScanLevel
+            )
+            : base(queryShape, fieldName, grid, detailLevel)
+        {
+            //Historical note: this code resulted from a refactoring of RecursivePrefixTreeFilter,
+            // which in turn came out of SOLR-2155
+            //at least one less than grid.getMaxLevels()
+            this.prefixGridScanLevel = Math.Max(0, Math.Min(prefixGridScanLevel, grid.MaxLevels - 1));
+            Debug.Assert(detailLevel <= grid.MaxLevels);
+        }
+
+        public override bool Equals(object o)
+        {
+            if (!base.Equals(o))
+            {
+                return false;
+            }
+            //checks getClass == o.getClass & instanceof
+            var that = (AbstractVisitingPrefixTreeFilter)o;
+            if (prefixGridScanLevel != that.prefixGridScanLevel)
+            {
+                return false;
+            }
+            return true;
+        }
+
+        public override int GetHashCode()
+        {
+            int result = base.GetHashCode();
+            result = 31 * result + prefixGridScanLevel;
+            return result;
+        }
+
+        #region Nested type: VNode
+
+        /// <summary>
+        /// A Visitor Cell/Cell found via the query shape for
+        /// <see cref="VisitorTemplate">VisitorTemplate</see>
+        /// .
+        /// Sometimes these are reset(cell). It's like a LinkedList node but forms a
+        /// tree.
+        /// </summary>
+        /// <lucene.internal></lucene.internal>
+        public class VNode
+        {
+            internal readonly VNode parent;
+
+            internal Cell cell;
+            internal IEnumerator<VNode> children;
+
+            /// <summary>call reset(cell) after to set the cell.</summary>
+            /// <remarks>call reset(cell) after to set the cell.</remarks>
+            internal VNode(VNode parent)
+            {
+                //Note: The VNode tree adds more code to debug/maintain v.s. a flattened
+                // LinkedList that we used to have. There is more opportunity here for
+                // custom behavior (see preSiblings & postSiblings) but that's not
+                // leveraged yet. Maybe this is slightly more GC friendly.
+                //only null at the root
+                //null, then sometimes set, then null
+                //not null (except initially before reset())
+                // remember to call reset(cell) after
+                this.parent = parent;
+            }
+
+            internal virtual void Reset(Cell cell)
+            {
+                Debug.Assert(cell != null);
+                this.cell = cell;
+                Debug.Assert(children == null);
+            }
+        }
+
+        #endregion
+
+        #region Nested type: VisitorTemplate
+
+        /// <summary>
+        /// An abstract class designed to make it easy to implement predicates or
+        /// other operations on a
+        /// <see cref="Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree">Lucene.Net.Spatial.Prefix.Tree.SpatialPrefixTree
+        /// 	</see>
+        /// indexed field. An instance
+        /// of this class is not designed to be re-used across AtomicReaderContext
+        /// instances so simply create a new one for each call to, say a
+        /// <see cref="Lucene.Net.Search.Filter.GetDocIdSet(Lucene.Net.Index.AtomicReaderContext, Lucene.Net.Util.Bits)
+        /// 	">Lucene.Net.Search.Filter.GetDocIdSet(Lucene.Net.Index.AtomicReaderContext, Lucene.Net.Util.Bits)
+        /// 	</see>
+        /// .
+        /// The
+        /// <see cref="GetDocIdSet()">GetDocIdSet()</see>
+        /// method here starts the work. It first checks
+        /// that there are indexed terms; if not it quickly returns null. Then it calls
+        /// <see cref="Start()">Start()</see>
+        /// so a subclass can set up a return value, like an
+        /// <see cref="Lucene.Net.Util.OpenBitSet">Lucene.Net.Util.OpenBitSet</see>
+        /// . Then it starts the traversal
+        /// process, calling
+        /// <see cref="FindSubCellsToVisit(Lucene.Net.Spatial.Prefix.Tree.Cell)">FindSubCellsToVisit(Lucene.Net.Spatial.Prefix.Tree.Cell)
+        /// 	</see>
+        /// which by default finds the top cells that intersect
+        /// <code>queryShape</code>
+        /// . If
+        /// there isn't an indexed cell for a corresponding cell returned for this
+        /// method then it's short-circuited until it finds one, at which point
+        /// <see cref="Visit(Lucene.Net.Spatial.Prefix.Tree.Cell)">Visit(Lucene.Net.Spatial.Prefix.Tree.Cell)
+        /// 	</see>
+        /// is called. At
+        /// some depths, of the tree, the algorithm switches to a scanning mode that
+        /// finds calls
+        /// <see cref="VisitScanned(Lucene.Net.Spatial.Prefix.Tree.Cell)">VisitScanned(Lucene.Net.Spatial.Prefix.Tree.Cell)
+        /// 	</see>
+        /// for each leaf cell found.
+        /// </summary>
+        /// <lucene.internal></lucene.internal>
+        public abstract class VisitorTemplate : BaseTermsEnumTraverser
+        {
+            private readonly AbstractVisitingPrefixTreeFilter _enclosing;
+            private readonly BytesRef curVNodeTerm = new BytesRef();
+            protected internal readonly bool hasIndexedLeaves;
+
+            private VNode curVNode;
+
+            private Cell scanCell;
+
+            private BytesRef thisTerm;
+
+            /// <exception cref="System.IO.IOException"></exception>
+            public VisitorTemplate(AbstractVisitingPrefixTreeFilter _enclosing, AtomicReaderContext
+                                                                                    context, IBits acceptDocs,
+                                   bool hasIndexedLeaves)
+                : base(_enclosing, context, acceptDocs)
+            {
+                this._enclosing = _enclosing;
+                //if false then we can skip looking for them
+                //current pointer, derived from query shape
+                //curVNode.cell's term.
+                //the result of termsEnum.term()
+                this.hasIndexedLeaves = hasIndexedLeaves;
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            public virtual DocIdSet GetDocIdSet()
+            {
+                Debug.Assert(curVNode == null, "Called more than once?");
+                if (termsEnum == null)
+                {
+                    return null;
+                }
+                //advance
+                if ((thisTerm = termsEnum.Next()) == null)
+                {
+                    return null;
+                }
+                // all done
+                curVNode = new VNode(null);
+                curVNode.Reset(_enclosing.grid.WorldCell);
+                Start();
+                AddIntersectingChildren();
+                while (thisTerm != null)
+                {
+                    //terminates for other reasons too!
+                    //Advance curVNode pointer
+                    if (curVNode.children != null)
+                    {
+                        //-- HAVE CHILDREN: DESCEND
+                        Debug.Assert(curVNode.children.MoveNext());
+                        //if we put it there then it has something
+                        PreSiblings(curVNode);
+                        curVNode = curVNode.children.Current;
+                    }
+                    else
+                    {
+                        //-- NO CHILDREN: ADVANCE TO NEXT SIBLING
+                        VNode parentVNode = curVNode.parent;
+                        while (true)
+                        {
+                            if (parentVNode == null)
+                            {
+                                goto main_break;
+                            }
+                            // all done
+                            if (parentVNode.children.MoveNext())
+                            {
+                                //advance next sibling
+                                curVNode = parentVNode.children.Current;
+                                break;
+                            }
+                            else
+                            {
+                                //reached end of siblings; pop up
+                                PostSiblings(parentVNode);
+                                parentVNode.children = null;
+                                //GC
+                                parentVNode = parentVNode.parent;
+                            }
+                        }
+                    }
+                    //Seek to curVNode's cell (or skip if termsEnum has moved beyond)
+                    curVNodeTerm.bytes = curVNode.cell.GetTokenBytes().ToSByteArray();
+                    curVNodeTerm.length = curVNodeTerm.bytes.Length;
+                    int compare = termsEnum.Comparator.Compare(thisTerm, curVNodeTerm
+                        );
+                    if (compare > 0)
+                    {
+                        // leap frog (termsEnum is beyond where we would otherwise seek)
+                        Debug.Assert(
+                            !((AtomicReader)context.Reader).Terms(_enclosing.fieldName).Iterator(null).SeekExact(
+                                curVNodeTerm, false), "should be absent"
+                            );
+                    }
+                    else
+                    {
+                        if (compare < 0)
+                        {
+                            // Seek !
+                            TermsEnum.SeekStatus seekStatus = termsEnum.SeekCeil(curVNodeTerm, true
+                                );
+                            if (seekStatus == TermsEnum.SeekStatus.END)
+                            {
+                                break;
+                            }
+                            // all done
+                            thisTerm = termsEnum.Term;
+                            if (seekStatus == TermsEnum.SeekStatus.NOT_FOUND)
+                            {
+                                continue;
+                            }
+                        }
+                        // leap frog
+                        // Visit!
+                        bool descend = Visit(curVNode.cell);
+                        //advance
+                        if ((thisTerm = termsEnum.Next()) == null)
+                        {
+                            break;
+                        }
+                        // all done
+                        if (descend)
+                        {
+                            AddIntersectingChildren();
+                        }
+                    }
+                    ;
+                }
+            main_break:
+                ;
+                //main loop
+                return Finish();
+            }
+
+            /// <summary>
+            /// Called initially, and whenever
+            /// <see cref="Visit(Lucene.Net.Spatial.Prefix.Tree.Cell)">Visit(Lucene.Net.Spatial.Prefix.Tree.Cell)
+            /// 	</see>
+            /// returns true.
+            /// </summary>
+            /// <exception cref="System.IO.IOException"></exception>
+            private void AddIntersectingChildren()
+            {
+                Debug.Assert(thisTerm != null);
+                Cell cell = curVNode.cell;
+                if (cell.Level >= _enclosing.detailLevel)
+                {
+                    throw new InvalidOperationException("Spatial logic error");
+                }
+                //Check for adjacent leaf (happens for indexed non-point shapes)
+                if (hasIndexedLeaves && cell.Level != 0)
+                {
+                    //If the next indexed term just adds a leaf marker ('+') to cell,
+                    // then add all of those docs
+                    Debug.Assert(StringHelper.StartsWith(thisTerm, curVNodeTerm
+                                     ));
+                    scanCell = _enclosing.grid.GetCell(thisTerm.bytes.ToByteArray(), thisTerm.offset
+                                                       , thisTerm.length, scanCell);
+                    if (scanCell.Level == cell.Level && scanCell.IsLeaf())
+                    {
+                        VisitLeaf(scanCell);
+                        //advance
+                        if ((thisTerm = termsEnum.Next()) == null)
+                        {
+                            return;
+                        }
+                    }
+                }
+                // all done
+                //Decide whether to continue to divide & conquer, or whether it's time to
+                // scan through terms beneath this cell.
+                // Scanning is a performance optimization trade-off.
+                //TODO use termsEnum.docFreq() as heuristic
+                bool scan = cell.Level >= _enclosing.prefixGridScanLevel;
+                //simple heuristic
+                if (!scan)
+                {
+                    //Divide & conquer (ultimately termsEnum.seek())
+                    IEnumerator<Cell> subCellsIter = FindSubCellsToVisit(cell);
+                    if (!subCellsIter.MoveNext())
+                    {
+                        //not expected
+                        return;
+                    }
+                    curVNode.children = new VNodeCellIterator
+                        (this, subCellsIter, new VNode(curVNode));
+                }
+                else
+                {
+                    //Scan (loop of termsEnum.next())
+                    Scan(_enclosing.detailLevel);
+                }
+            }
+
+            /// <summary>
+            /// Called when doing a divide & conquer to find the next intersecting cells
+            /// of the query shape that are beneath
+            /// <code>cell</code>
+            /// .
+            /// <code>cell</code>
+            /// is
+            /// guaranteed to have an intersection and thus this must return some number
+            /// of nodes.
+            /// </summary>
+            protected internal virtual IEnumerator<Cell> FindSubCellsToVisit(Cell cell)
+            {
+                return cell.GetSubCells(_enclosing.queryShape).GetEnumerator();
+            }
+
+            /// <summary>
+            /// Scans (
+            /// <code>termsEnum.next()</code>
+            /// ) terms until a term is found that does
+            /// not start with curVNode's cell. If it finds a leaf cell or a cell at
+            /// level
+            /// <code>scanDetailLevel</code>
+            /// then it calls
+            /// <see cref="VisitScanned(Lucene.Net.Spatial.Prefix.Tree.Cell)">VisitScanned(Lucene.Net.Spatial.Prefix.Tree.Cell)
+            /// 	</see>
+            /// .
+            /// </summary>
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal virtual void Scan(int scanDetailLevel)
+            {
+                for (;
+                    thisTerm != null && StringHelper.StartsWith(thisTerm, curVNodeTerm
+                                            );
+                    thisTerm = termsEnum.Next())
+                {
+                    scanCell = _enclosing.grid.GetCell(thisTerm.bytes.ToByteArray(), thisTerm.offset
+                                                       , thisTerm.length, scanCell);
+                    int termLevel = scanCell.Level;
+                    if (termLevel > scanDetailLevel)
+                    {
+                        continue;
+                    }
+                    if (termLevel == scanDetailLevel || scanCell.IsLeaf())
+                    {
+                        VisitScanned(scanCell);
+                    }
+                }
+            }
+
+            /// <summary>Called first to setup things.</summary>
+            /// <remarks>Called first to setup things.</remarks>
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal abstract void Start();
+
+            /// <summary>Called last to return the result.</summary>
+            /// <remarks>Called last to return the result.</remarks>
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal abstract DocIdSet Finish();
+
+            /// <summary>
+            /// Visit an indexed cell returned from
+            /// <see cref="FindSubCellsToVisit(Lucene.Net.Spatial.Prefix.Tree.Cell)">FindSubCellsToVisit(Lucene.Net.Spatial.Prefix.Tree.Cell)
+            /// 	</see>
+            /// .
+            /// </summary>
+            /// <param name="cell">An intersecting cell.</param>
+            /// <returns>
+            /// true to descend to more levels. It is an error to return true
+            /// if cell.level == detailLevel
+            /// </returns>
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal abstract bool Visit(Cell cell);
+
+            /// <summary>Called after visit() returns true and an indexed leaf cell is found.</summary>
+            /// <remarks>
+            /// Called after visit() returns true and an indexed leaf cell is found. An
+            /// indexed leaf cell means associated documents generally won't be found at
+            /// further detail levels.
+            /// </remarks>
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal abstract void VisitLeaf(Cell cell);
+
+            /// <summary>The cell is either indexed as a leaf or is the last level of detail.</summary>
+            /// <remarks>
+            /// The cell is either indexed as a leaf or is the last level of detail. It
+            /// might not even intersect the query shape, so be sure to check for that.
+            /// </remarks>
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal abstract void VisitScanned(Cell cell);
+
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal virtual void PreSiblings(VNode vNode)
+            {
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal virtual void PostSiblings(VNode vNode)
+            {
+            }
+
+            #region Nested type: VNodeCellIterator
+
+            /// <summary>
+            /// Used for
+            /// <see cref="VNode.children">VNode.children</see>
+            /// .
+            /// </summary>
+            private class VNodeCellIterator : IEnumerator<VNode>
+            {
+                private readonly VisitorTemplate _enclosing;
+                internal readonly IEnumerator<Cell> cellIter;
+
+                private readonly VNode vNode;
+
+                internal VNodeCellIterator(VisitorTemplate _enclosing, IEnumerator<Cell> cellIter, VNode vNode)
+                {
+                    this._enclosing = _enclosing;
+                    //term loop
+                    this.cellIter = cellIter;
+                    this.vNode = vNode;
+                }
+
+                //it always removes
+
+                #region IEnumerator<VNode> Members
+
+                public void Dispose()
+                {
+                    cellIter.Dispose();
+                }
+
+                public bool MoveNext()
+                {
+                    return cellIter.MoveNext();
+                }
+
+                public void Reset()
+                {
+                    cellIter.Reset();
+                }
+
+                public VNode Current
+                {
+                    get
+                    {
+                        Debug.Assert(cellIter.Current != null);
+                        vNode.Reset(cellIter.Current);
+                        return vNode;
+                    }
+                }
+
+                object IEnumerator.Current
+                {
+                    get { return Current; }
+                }
+
+                #endregion
+            }
+
+            #endregion
+
+            //class VisitorTemplate
+        }
+
+        #endregion
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/ContainsPrefixTreeFilter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/ContainsPrefixTreeFilter.cs b/src/Lucene.Net.Spatial/Prefix/ContainsPrefixTreeFilter.cs
new file mode 100644
index 0000000..bd13b79
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/ContainsPrefixTreeFilter.cs
@@ -0,0 +1,364 @@
+/* 
+ * 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 Lucene.Net.Spatial.Queries;
+using Lucene.Net.Spatial.Util;
+using Spatial4n.Core.Shapes;
+using Lucene.Net.Index;
+using Lucene.Net.Search;
+using Lucene.Net.Spatial.Prefix;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Util;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+    /// <summary>
+    /// Finds docs where its indexed shape
+    /// <see cref="SpatialOperation.Contains">CONTAINS</see>
+    /// the query shape. For use on
+    /// <see cref="RecursivePrefixTreeStrategy">RecursivePrefixTreeStrategy</see>
+    /// .
+    /// </summary>
+    /// <lucene.experimental></lucene.experimental>
+    public class ContainsPrefixTreeFilter : AbstractPrefixTreeFilter
+    {
+        public ContainsPrefixTreeFilter(Shape queryShape, string
+             fieldName, SpatialPrefixTree grid, int detailLevel)
+            : base(queryShape, fieldName, grid, detailLevel)
+        {
+        }
+
+        /// <exception cref="System.IO.IOException"></exception>
+        public override DocIdSet GetDocIdSet(AtomicReaderContext context, IBits acceptDocs
+            )
+        {
+            return new ContainsVisitor(this, context, acceptDocs).Visit(grid.WorldCell, acceptDocs);
+        }
+
+        private class ContainsVisitor : BaseTermsEnumTraverser
+        {
+            /// <exception cref="System.IO.IOException"></exception>
+            public ContainsVisitor(ContainsPrefixTreeFilter _enclosing, AtomicReaderContext context
+                , IBits acceptDocs)
+                : base(_enclosing, context, acceptDocs)
+            {
+                this._enclosing = _enclosing;
+            }
+
+            internal BytesRef termBytes = new BytesRef();
+
+            internal Cell nextCell;
+
+            //see getLeafDocs
+            /// <summary>This is the primary algorithm; recursive.</summary>
+            /// <remarks>This is the primary algorithm; recursive.  Returns null if finds none.</remarks>
+            /// <exception cref="System.IO.IOException"></exception>
+            internal SmallDocSet Visit(Cell cell, IBits acceptContains
+                )
+            {
+                if (termsEnum == null)
+                {
+                    //signals all done
+                    return null;
+                }
+                //Leaf docs match all query shape
+                SmallDocSet leafDocs = GetLeafDocs(cell, acceptContains);
+                // Get the AND of all child results
+                SmallDocSet combinedSubResults = null;
+                ICollection<Cell> subCells = cell.GetSubCells(_enclosing.queryShape);
+                foreach (Cell subCell in subCells)
+                {
+                    if (!SeekExact(subCell))
+                    {
+                        combinedSubResults = null;
+                    }
+                    else
+                    {
+                        if (subCell.Level == _enclosing.detailLevel)
+                        {
+                            combinedSubResults = GetDocs(subCell, acceptContains);
+                        }
+                        else
+                        {
+                            if (subCell.GetShapeRel() == SpatialRelation.WITHIN)
+                            {
+                                combinedSubResults = GetLeafDocs(subCell, acceptContains);
+                            }
+                            else
+                            {
+                                combinedSubResults = Visit(subCell, acceptContains);
+                            }
+                        }
+                    }
+                    //recursion
+                    if (combinedSubResults == null)
+                    {
+                        break;
+                    }
+                    acceptContains = combinedSubResults;
+                }
+                //has the 'AND' effect on next iteration
+                // Result: OR the leaf docs with AND of all child results
+                if (combinedSubResults != null)
+                {
+                    if (leafDocs == null)
+                    {
+                        return combinedSubResults;
+                    }
+                    return leafDocs.Union(combinedSubResults);
+                }
+                return leafDocs;
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            private bool SeekExact(Cell cell)
+            {
+                System.Diagnostics.Debug.Assert(new BytesRef(cell.GetTokenBytes().ToSByteArray()).CompareTo(this
+                    .termBytes) > 0);
+                this.termBytes.bytes = cell.GetTokenBytes().ToSByteArray();
+                this.termBytes.length = this.termBytes.bytes.Length;
+                return this.termsEnum.SeekExact(this.termBytes, cell.Level <= 2);
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            private ContainsPrefixTreeFilter.SmallDocSet GetDocs(Cell cell, IBits acceptContains
+                )
+            {
+                System.Diagnostics.Debug.Assert(new BytesRef(cell.GetTokenBytes().ToSByteArray()).Equals(this.termBytes
+                    ));
+                return this.CollectDocs(acceptContains);
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            private ContainsPrefixTreeFilter.SmallDocSet GetLeafDocs(Cell leafCell, IBits acceptContains)
+            {
+                System.Diagnostics.Debug.Assert(new BytesRef(leafCell.GetTokenBytes().ToSByteArray()).Equals(this
+                    .termBytes));
+                BytesRef nextTerm = this.termsEnum.Next();
+                if (nextTerm == null)
+                {
+                    this.termsEnum = null;
+                    //signals all done
+                    return null;
+                }
+                this.nextCell = this._enclosing.grid.GetCell(nextTerm.bytes.ToByteArray(), nextTerm.offset, nextTerm
+                    .length, this.nextCell);
+                if (this.nextCell.Level == leafCell.Level && this.nextCell.IsLeaf())
+                {
+                    return this.CollectDocs(acceptContains);
+                }
+                else
+                {
+                    return null;
+                }
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            private ContainsPrefixTreeFilter.SmallDocSet CollectDocs(IBits acceptContains)
+            {
+                ContainsPrefixTreeFilter.SmallDocSet set = null;
+                this.docsEnum = this.termsEnum.Docs(acceptContains, this.docsEnum, DocsEnum.FLAG_NONE
+                    );
+                int docid;
+                while ((docid = this.docsEnum.NextDoc()) != DocIdSetIterator.NO_MORE_DOCS)
+                {
+                    if (set == null)
+                    {
+                        int size = this.termsEnum.DocFreq;
+                        if (size <= 0)
+                        {
+                            size = 16;
+                        }
+                        set = new ContainsPrefixTreeFilter.SmallDocSet(size);
+                    }
+                    set.Set(docid);
+                }
+                return set;
+            }
+
+            private readonly ContainsPrefixTreeFilter _enclosing;
+            //class ContainsVisitor
+        }
+
+        /// <summary>A hash based mutable set of docIds.</summary>
+        /// <remarks>
+        /// A hash based mutable set of docIds. If this were Solr code then we might
+        /// use a combination of HashDocSet and SortedIntDocSet instead.
+        /// </remarks>
+        private class SmallDocSet : DocIdSet, Lucene.Net.Util.IBits
+        {
+            private readonly SentinelIntSet intSet;
+
+            private int maxInt = 0;
+
+            public SmallDocSet(int size)
+            {
+                intSet = new SentinelIntSet(size, -1);
+            }
+
+            public virtual void Set(int index)
+            {
+                intSet.Put(index);
+                if (index > maxInt)
+                {
+                    maxInt = index;
+                }
+            }
+
+            /// <summary>Largest docid.</summary>
+            /// <remarks>Largest docid.</remarks>
+            public int Length
+            {
+                get
+                {
+                    return maxInt;
+                }
+            }
+
+            /// <summary>Number of docids.</summary>
+            /// <remarks>Number of docids.</remarks>
+            public virtual int Size()
+            {
+                return intSet.Size;
+            }
+
+            /// <summary>NOTE: modifies and returns either "this" or "other"</summary>
+            public virtual ContainsPrefixTreeFilter.SmallDocSet Union(ContainsPrefixTreeFilter.SmallDocSet
+                 other)
+            {
+                ContainsPrefixTreeFilter.SmallDocSet bigger;
+                ContainsPrefixTreeFilter.SmallDocSet smaller;
+                if (other.intSet.Size > this.intSet.Size)
+                {
+                    bigger = other;
+                    smaller = this;
+                }
+                else
+                {
+                    bigger = this;
+                    smaller = other;
+                }
+                //modify bigger
+                foreach (int v in smaller.intSet.keys)
+                {
+                    if (v == smaller.intSet.emptyVal)
+                    {
+                        continue;
+                    }
+                    bigger.Set(v);
+                }
+                return bigger;
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            public override Lucene.Net.Util.IBits Bits
+            {
+                get
+                {
+                    //if the # of docids is super small, return null since iteration is going
+                    // to be faster
+                    return Size() > 4 ? this : null;
+                }
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            public override DocIdSetIterator Iterator()
+            {
+                if (Size() == 0)
+                {
+                    return null;
+                }
+                //copy the unsorted values to a new array then sort them
+                int d = 0;
+                int[] docs = new int[intSet.Size];
+                foreach (int v in intSet.keys)
+                {
+                    if (v == intSet.emptyVal)
+                    {
+                        continue;
+                    }
+                    docs[d++] = v;
+                }
+                System.Diagnostics.Debug.Assert(d == intSet.Size);
+                int size = d;
+                //sort them
+                Array.Sort(docs, 0, size);
+                return new _DocIdSetIterator_225(size, docs);
+            }
+
+            private sealed class _DocIdSetIterator_225 : DocIdSetIterator
+            {
+                public _DocIdSetIterator_225(int size, int[] docs)
+                {
+                    this.size = size;
+                    this.docs = docs;
+                    this.idx = -1;
+                }
+
+                internal int idx;
+
+                public override int DocID
+                {
+                    get
+                    {
+                        if (this.idx >= 0 && this.idx < size)
+                        {
+                            return docs[this.idx];
+                        }
+                        else
+                        {
+                            return -1;
+                        }
+                    }
+                }
+
+                /// <exception cref="System.IO.IOException"></exception>
+                public override int NextDoc()
+                {
+                    if (++this.idx < size)
+                    {
+                        return docs[this.idx];
+                    }
+                    return DocIdSetIterator.NO_MORE_DOCS;
+                }
+
+                /// <exception cref="System.IO.IOException"></exception>
+                public override int Advance(int target)
+                {
+                    //for this small set this is likely faster vs. a binary search
+                    // into the sorted array
+                    return this.SlowAdvance(target);
+                }
+
+                public override long Cost
+                {
+                    get { return size; }
+                }
+
+                private readonly int size;
+
+                private readonly int[] docs;
+            }
+            //class SmallDocSet
+            public bool this[int index]
+            {
+                get { return intSet.Exists(index); }
+            }
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/IntersectsPrefixTreeFilter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/IntersectsPrefixTreeFilter.cs b/src/Lucene.Net.Spatial/Prefix/IntersectsPrefixTreeFilter.cs
new file mode 100644
index 0000000..7201167
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/IntersectsPrefixTreeFilter.cs
@@ -0,0 +1,125 @@
+/* 
+ * 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 Lucene.Net.Index;
+using Lucene.Net.Search;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Util;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+    /// <summary>
+    /// A Filter matching documents that have an
+    /// <see cref="SpatialRelation.Intersects">SpatialRelation.Intersects
+    /// 	</see>
+    /// (i.e. not DISTINCT) relationship with a provided query shape.
+    /// </summary>
+    /// <lucene.internal></lucene.internal>
+    public class IntersectsPrefixTreeFilter : AbstractVisitingPrefixTreeFilter
+    {
+        private readonly bool hasIndexedLeaves;
+
+        public IntersectsPrefixTreeFilter(Shape queryShape, string
+                                                                fieldName, SpatialPrefixTree grid, int detailLevel,
+                                          int prefixGridScanLevel, bool
+                                                                       hasIndexedLeaves)
+            : base(queryShape, fieldName, grid, detailLevel, prefixGridScanLevel)
+        {
+            this.hasIndexedLeaves = hasIndexedLeaves;
+        }
+
+        public override bool Equals(object o)
+        {
+            return base.Equals(o) && hasIndexedLeaves == ((IntersectsPrefixTreeFilter)o).hasIndexedLeaves;
+        }
+
+        /// <exception cref="System.IO.IOException"></exception>
+        public override DocIdSet GetDocIdSet(AtomicReaderContext context, IBits acceptDocs
+            )
+        {
+            return new _VisitorTemplate_55(this, context, acceptDocs, hasIndexedLeaves).GetDocIdSet
+                ();
+        }
+
+        #region Nested type: _VisitorTemplate_55
+
+        private sealed class _VisitorTemplate_55 : VisitorTemplate
+        {
+            private readonly IntersectsPrefixTreeFilter _enclosing;
+            private FixedBitSet results;
+
+            public _VisitorTemplate_55(IntersectsPrefixTreeFilter _enclosing, AtomicReaderContext
+                                                                                  baseArg1, IBits baseArg2,
+                                       bool baseArg3)
+                : base(_enclosing, baseArg1, baseArg2, baseArg3)
+            {
+                this._enclosing = _enclosing;
+            }
+
+            protected internal override void Start()
+            {
+                results = new FixedBitSet(maxDoc);
+            }
+
+            protected internal override DocIdSet Finish()
+            {
+                return results;
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal override bool Visit(Cell cell)
+            {
+                if (cell.GetShapeRel() == SpatialRelation.WITHIN || cell.Level == _enclosing
+                                                                                      .detailLevel)
+                {
+                    CollectDocs(results);
+                    return false;
+                }
+                return true;
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal override void VisitLeaf(Cell cell)
+            {
+                CollectDocs(results);
+            }
+
+            /// <exception cref="System.IO.IOException"></exception>
+            protected internal override void VisitScanned(Cell cell)
+            {
+                Shape cShape;
+                //if this cell represents a point, use the cell center vs the box
+                // TODO this behavior is debatable; might want to be configurable
+                // (points never have isLeaf())
+                if (cell.Level == _enclosing.grid.MaxLevels && !cell.IsLeaf())
+                {
+                    cShape = cell.GetCenter();
+                }
+                else
+                {
+                    cShape = cell.GetShape();
+                }
+                if (_enclosing.queryShape.Relate(cShape).Intersects())
+                {
+                    CollectDocs(results);
+                }
+            }
+        }
+
+        #endregion
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/dc71f60d/src/Lucene.Net.Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs b/src/Lucene.Net.Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs
index 5a7c554..acf6f96 100644
--- a/src/Lucene.Net.Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs
+++ b/src/Lucene.Net.Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs
@@ -1,51 +1,64 @@
-/*
+/* 
  * 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 Lucene.Net.Spatial.Prefix.Tree;
 using Lucene.Net.Spatial.Util;
+using Lucene.Net.Util;
 using Spatial4n.Core.Shapes;
 
 namespace Lucene.Net.Spatial.Prefix
 {
     /// <summary>
-    /// Implementation of {@link ShapeFieldCacheProvider} designed for {@link PrefixTreeStrategy}s.
-    /// 
+    /// Implementation of
+    /// <see cref="Lucene.Net.Spatial.Util.ShapeFieldCacheProvider{T}">Lucene.Net.Spatial.Util.ShapeFieldCacheProvider&lt;T&gt;
+    /// 	</see>
+    /// designed for
+    /// <see cref="PrefixTreeStrategy">PrefixTreeStrategy</see>
+    /// s.
     /// Note, due to the fragmented representation of Shapes in these Strategies, this implementation
-    /// can only retrieve the central {@link Point} of the original Shapes.
+    /// can only retrieve the central
+    /// <see cref="Point">Point</see>
+    /// of the original Shapes.
     /// </summary>
+    /// <lucene.internal></lucene.internal>
     public class PointPrefixTreeFieldCacheProvider : ShapeFieldCacheProvider<Point>
     {
-        readonly SpatialPrefixTree grid; //
+        internal readonly SpatialPrefixTree grid;
 
-        public PointPrefixTreeFieldCacheProvider(SpatialPrefixTree grid, String shapeField, int defaultSize)
+        public PointPrefixTreeFieldCacheProvider(SpatialPrefixTree grid, string shapeField
+            , int defaultSize)
             : base(shapeField, defaultSize)
         {
+            //
             this.grid = grid;
         }
 
-        //A kluge that this is a field
-        private Node scanCell = null;
+        private Cell scanCell = null;
 
-        protected override Point ReadShape(Term term)
+        //re-used in readShape to save GC
+        protected internal override Point ReadShape(BytesRef term)
         {
-            scanCell = grid.GetNode(term.Text, scanCell);
-            return scanCell.IsLeaf() ? scanCell.GetShape().GetCenter() : null;
+            scanCell = grid.GetCell(term.bytes.ToByteArray(), term.offset, term.length, scanCell);
+            if (scanCell.Level == grid.MaxLevels && !scanCell.IsLeaf())
+            {
+                return scanCell.GetCenter();
+            }
+            return null;
         }
     }
 }


Mime
View raw message