lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [5/6] lucenenet git commit: Moving the 3.0 spatial module to serve as a basis to Lucene.Net.Spatial
Date Mon, 09 Feb 2015 01:27:55 GMT
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeFilter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeFilter.cs b/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeFilter.cs
new file mode 100644
index 0000000..ce0d0d9
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeFilter.cs
@@ -0,0 +1,189 @@
+/*
+ * 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 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>
+    /// Performs a spatial intersection filter against a field indexed with {@link SpatialPrefixTree}, a Trie.
+    /// SPT yields terms (grids) at length 1 and at greater lengths corresponding to greater precisions.
+    /// This filter recursively traverses each grid length and uses methods on {@link Shape} to efficiently know
+    /// that all points at a prefix fit in the shape or not to either short-circuit unnecessary traversals or to efficiently
+    /// load all enclosed points.
+    /// </summary>
+    public class RecursivePrefixTreeFilter : Filter
+    {
+        /* TODOs for future:
+
+Can a polygon query shape be optimized / made-simpler at recursive depths (e.g. intersection of shape + cell box)
+
+RE "scan" threshold:
+// IF configured to do so, we could use term.freq() as an estimate on the number of places at this depth.  OR, perhaps
+//  make estimates based on the total known term count at this level?
+if (!scan) {
+  //Make some estimations on how many points there are at this level and how few there would need to be to set
+  // !scan to false.
+  long termsThreshold = (long) estimateNumberIndexedTerms(cell.length(),queryShape.getDocFreqExpenseThreshold(cell));
+  long thisOrd = termsEnum.ord();
+  scan = (termsEnum.seek(thisOrd+termsThreshold+1) == TermsEnum.SeekStatus.END
+          || !cell.contains(termsEnum.term()));
+  termsEnum.seek(thisOrd);//return to last position
+}
+
+*/
+
+        private readonly String fieldName;
+        private readonly SpatialPrefixTree grid;
+        private readonly Shape queryShape;
+        private readonly int prefixGridScanLevel;//at least one less than grid.getMaxLevels()
+        private readonly int detailLevel;
+
+        public RecursivePrefixTreeFilter(String fieldName, SpatialPrefixTree grid, Shape queryShape, int prefixGridScanLevel,
+                             int detailLevel)
+        {
+            this.fieldName = fieldName;
+            this.grid = grid;
+            this.queryShape = queryShape;
+            this.prefixGridScanLevel = Math.Max(1, Math.Min(prefixGridScanLevel, grid.GetMaxLevels() - 1));
+            this.detailLevel = detailLevel;
+            Debug.Assert(detailLevel <= grid.GetMaxLevels());
+        }
+
+        public override DocIdSet GetDocIdSet(Index.IndexReader reader /*, Bits acceptDocs*/)
+        {
+            var bits = new OpenBitSet(reader.MaxDoc);
+            var terms = new TermsEnumCompatibility(reader, fieldName);
+            var term = terms.Next();
+            if (term == null)
+                return null;
+            Node scanCell = null;
+
+            //cells is treated like a stack. LinkedList conveniently has bulk add to beginning. It's in sorted order so that we
+            //  always advance forward through the termsEnum index.
+            var cells = new LinkedList<Node>(
+                grid.GetWorldNode().GetSubCells(queryShape));
+
+            //This is a recursive algorithm that starts with one or more "big" cells, and then recursively dives down into the
+            // first such cell that intersects with the query shape.  It's a depth first traversal because we don't move onto
+            // the next big cell (breadth) until we're completely done considering all smaller cells beneath it. For a given
+            // cell, if it's *within* the query shape then we can conveniently short-circuit the depth traversal and
+            // grab all documents assigned to this cell/term.  For an intersection of the cell and query shape, we either
+            // recursively step down another grid level or we decide heuristically (via prefixGridScanLevel) that there aren't
+            // that many points, and so we scan through all terms within this cell (i.e. the term starts with the cell's term),
+            // seeing which ones are within the query shape.
+            while (cells.Count > 0)
+            {
+                Node cell = cells.First.Value; cells.RemoveFirst();
+                var cellTerm = cell.GetTokenString();
+                var seekStat = terms.Seek(cellTerm);
+                if (seekStat == TermsEnumCompatibility.SeekStatus.END)
+                    break;
+                if (seekStat == TermsEnumCompatibility.SeekStatus.NOT_FOUND)
+                    continue;
+                if (cell.GetLevel() == detailLevel || cell.IsLeaf())
+                {
+                    terms.Docs(bits);
+                }
+                else
+                {//any other intersection
+                    //If the next indexed term is the leaf marker, then add all of them
+                    var nextCellTerm = terms.Next();
+                    Debug.Assert(nextCellTerm.Text.StartsWith(cellTerm));
+                    scanCell = grid.GetNode(nextCellTerm.Text, scanCell);
+                    if (scanCell.IsLeaf())
+                    {
+                        terms.Docs(bits);
+                        term = terms.Next();//move pointer to avoid potential redundant addDocs() below
+                    }
+
+                    //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.
+                    bool scan = cell.GetLevel() >= prefixGridScanLevel;//simple heuristic
+
+                    if (!scan)
+                    {
+                        //Divide & conquer
+                        var lst = cell.GetSubCells(queryShape);
+                        for (var i = lst.Count - 1; i >= 0; i--) //add to beginning
+                        {
+                            cells.AddFirst(lst[i]);
+                        }
+                    }
+                    else
+                    {
+                        //Scan through all terms within this cell to see if they are within the queryShape. No seek()s.
+                        for (var t = terms.Term(); t != null && t.Text.StartsWith(cellTerm); t = terms.Next())
+                        {
+                            scanCell = grid.GetNode(t.Text, scanCell);
+                            int termLevel = scanCell.GetLevel();
+                            if (termLevel > detailLevel)
+                                continue;
+                            if (termLevel == detailLevel || scanCell.IsLeaf())
+                            {
+                                //TODO should put more thought into implications of box vs point
+                                Shape cShape = termLevel == grid.GetMaxLevels() ? scanCell.GetCenter() : scanCell.GetShape();
+                                if (queryShape.Relate(cShape) == SpatialRelation.DISJOINT)
+                                    continue;
+
+                                terms.Docs(bits);
+                            }
+                        }//term loop
+                    }
+                }
+            }//cell loop
+
+            return bits;
+        }
+
+        public override string ToString()
+        {
+            return "GeoFilter{fieldName='" + fieldName + '\'' + ", shape=" + queryShape + '}';
+        }
+
+        public override bool Equals(object o)
+        {
+            if (this == o) return true;
+            var that = o as RecursivePrefixTreeFilter;
+
+            if (that == null) return false;
+
+            if (!fieldName.Equals(that.fieldName)) return false;
+            //note that we don't need to look at grid since for the same field it should be the same
+            if (prefixGridScanLevel != that.prefixGridScanLevel) return false;
+            if (detailLevel != that.detailLevel) return false;
+            if (!queryShape.Equals(that.queryShape)) return false;
+
+            return true;
+        }
+
+        public override int GetHashCode()
+        {
+            int result = fieldName.GetHashCode();
+            result = 31 * result + queryShape.GetHashCode();
+            result = 31 * result + detailLevel;
+            return result;
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/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
new file mode 100644
index 0000000..d6fa681
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/RecursivePrefixTreeStrategy.cs
@@ -0,0 +1,62 @@
+/*
+ * 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.Search;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Spatial.Queries;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+    /// <summary>
+    /// Based on {@link RecursivePrefixTreeFilter}.
+    /// </summary>
+    public class RecursivePrefixTreeStrategy : PrefixTreeStrategy
+    {
+        private int prefixGridScanLevel;
+
+        public RecursivePrefixTreeStrategy(SpatialPrefixTree grid, string fieldName)
+            : base(grid, fieldName)
+        {
+            prefixGridScanLevel = grid.GetMaxLevels() - 4;//TODO this default constant is dependent on the prefix grid size
+        }
+
+        public void SetPrefixGridScanLevel(int prefixGridScanLevel)
+        {
+            //TODO if negative then subtract from maxlevels
+            this.prefixGridScanLevel = prefixGridScanLevel;
+        }
+
+        public override Filter MakeFilter(SpatialArgs args)
+        {
+            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);
+        }
+
+        public override string ToString()
+        {
+            return GetType().Name + "(prefixGridScanLevel:" + prefixGridScanLevel + ",SPG:(" + grid + "))";
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/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
new file mode 100644
index 0000000..84a074a
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
@@ -0,0 +1,56 @@
+/*
+ * 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.Prefix.Tree;
+using Lucene.Net.Spatial.Queries;
+using Lucene.Net.Spatial.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)}.
+    /// </summary>
+    public class TermQueryPrefixTreeStrategy : PrefixTreeStrategy
+    {
+        public TermQueryPrefixTreeStrategy(SpatialPrefixTree grid, string fieldName)
+            : base(grid, fieldName)
+        {
+        }
+
+        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)
+            {
+                filter.AddTerm(new Term(GetFieldName(), cell.GetTokenString()));
+            }
+            return filter;
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/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
new file mode 100644
index 0000000..b05d7d2
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/GeohashPrefixTree.cs
@@ -0,0 +1,158 @@
+/*
+ * 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 Spatial4n.Core.Context;
+using Spatial4n.Core.Shapes;
+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.
+    /// </summary>
+    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);
+
+        }
+
+        /// <summary>
+        /// Any more than this and there's no point (double lat and lon are the same).
+        /// </summary>
+        /// <returns></returns>
+        public static int GetMaxLevelsPossible()
+        {
+            return GeohashUtils.MAX_PRECISION;
+        }
+
+        public override int GetLevelForDistance(double dist)
+        {
+            if (dist == 0)
+                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)
+        {
+            return new GhCell(GeohashUtils.EncodeLatLon(p.GetY(), p.GetX(), level), this);//args are lat,lon (y,x)
+        }
+
+        public override Node GetNode(string token)
+        {
+            return new GhCell(token, this);
+        }
+
+        public override Node GetNode(byte[] bytes, int offset, int len)
+        {
+            throw new System.NotImplementedException();
+        }
+
+        public override IList<Node> GetNodes(Shape shape, int detailLevel, bool inclParents)
+        {
+            var s = shape as Point;
+            return (s != null) ? base.GetNodesAltPoint(s, detailLevel, inclParents) : base.GetNodes(shape, detailLevel, inclParents);
+        }
+
+        public class GhCell : Node
+        {
+            public GhCell(String token, GeohashPrefixTree enclosingInstance)
+                : base(enclosingInstance, token)
+            {
+            }
+
+            public override void Reset(string newToken)
+            {
+                base.Reset(newToken);
+                shape = null;
+            }
+
+            public override IList<Node> GetSubCells()
+            {
+                String[] hashes = GeohashUtils.GetSubGeohashes(GetGeohash());//sorted
+                var cells = new List<Node>(hashes.Length);
+
+                var enclosingInstance = (GeohashPrefixTree)spatialPrefixTree;
+                foreach (String hash in hashes)
+                {
+                    cells.Add(new GhCell(hash, enclosingInstance));
+                }
+                return cells;
+            }
+
+            public override int GetSubCellsSize()
+            {
+                return 32;//8x4
+            }
+
+            public override Node GetSubCell(Point p)
+            {
+                return ((GeohashPrefixTree)spatialPrefixTree).GetNode(p, GetLevel() + 1); //not performant!
+            }
+
+            private Shape shape;//cache
+
+            public override Shape GetShape()
+            {
+                if (shape == null)
+                {
+                    shape = GeohashUtils.DecodeBoundary(GetGeohash(), ((GeohashPrefixTree)spatialPrefixTree).ctx);
+                }
+                return shape;
+            }
+
+            public override Point GetCenter()
+            {
+                return GeohashUtils.Decode(GetGeohash(), ((GeohashPrefixTree)spatialPrefixTree).ctx);
+            }
+
+            private String GetGeohash()
+            {
+                return GetTokenString();
+            }
+
+        }//class GhCell
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/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
new file mode 100644
index 0000000..ce403b0
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/Node.cs
@@ -0,0 +1,222 @@
+/*
+ * 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.Collections.ObjectModel;
+using System.Diagnostics;
+using System.Runtime.CompilerServices;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix.Tree
+{
+    public abstract class Node : IComparable<Node>
+    {
+        public static 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;
+
+        private String token;//this is the only part of equality
+
+        protected SpatialRelation shapeRel;//set in getSubCells(filter), and via setLeaf().
+        protected readonly SpatialPrefixTree spatialPrefixTree;
+
+        protected Node(SpatialPrefixTree spatialPrefixTree, String token)
+        {
+            this.spatialPrefixTree = spatialPrefixTree;
+            this.token = token;
+            if (token.Length > 0 && token[token.Length - 1] == (char)LEAF_BYTE)
+            {
+                this.token = token.Substring(0, token.Length - 1);
+                SetLeaf();
+            }
+
+            if (GetLevel() == 0)
+                GetShape();//ensure any lazy instantiation completes to make this threadsafe
+        }
+
+        public virtual void Reset(string newToken)
+        {
+            Debug.Assert(GetLevel() != 0);
+            this.token = newToken;
+            shapeRel = SpatialRelation.NULL_VALUE;
+            b_fixLeaf();
+        }
+
+        private void b_fixLeaf()
+        {
+            if (GetLevel() == spatialPrefixTree.GetMaxLevels())
+            {
+                SetLeaf();
+            }
+        }
+
+        public SpatialRelation GetShapeRel()
+        {
+            return shapeRel;
+        }
+
+        public bool IsLeaf()
+        {
+            return shapeRel == SpatialRelation.WITHIN;
+        }
+
+        public void SetLeaf()
+        {
+            Debug.Assert(GetLevel() != 0);
+            shapeRel = SpatialRelation.WITHIN;
+        }
+
+        /*
+         * Note: doesn't contain a trailing leaf byte.
+         */
+        public String GetTokenString()
+        {
+            if (token == null)
+                throw new InvalidOperationException("Somehow we got a null token");
+            return token;
+        }
+
+        ///// <summary>
+        ///// Note: doesn't contain a trailing leaf byte.
+        ///// </summary>
+        ///// <returns></returns>
+        //public byte[] GetTokenBytes()
+        //{
+        //    if (bytes != null)
+        //    {
+        //        if (b_off != 0 || b_len != bytes.Length)
+        //        {
+        //            throw new IllegalStateException("Not supported if byte[] needs to be recreated.");
+        //        }
+        //    }
+        //    else
+        //    {
+        //        bytes = token.GetBytes(SpatialPrefixTree.UTF8);
+        //        b_off = 0;
+        //        b_len = bytes.Length;
+        //    }
+        //    return bytes;
+        //}
+
+        public int GetLevel()
+        {
+            return token.Length;
+            //return token != null ? token.Length : b_len;
+        }
+
+        //TODO add getParent() and update some algorithms to use this?
+        //public Cell getParent();
+
+        /*
+         * Like {@link #getSubCells()} but with the results filtered by a shape. If that shape is a {@link com.spatial4j.core.shape.Point} then it
+         * must call {@link #getSubCell(com.spatial4j.core.shape.Point)};
+         * Precondition: Never called when getLevel() == maxLevel.
+         *
+         * @param shapeFilter an optional filter for the returned cells.
+         * @return A set of cells (no dups), sorted. Not Modifiable.
+         */
+        public IList<Node> GetSubCells(Shape shapeFilter)
+        {
+            //Note: Higher-performing subclasses might override to consider the shape filter to generate fewer cells.
+            var point = shapeFilter as Point;
+            if (point != null)
+            {
+#if !NET35
+                return new ReadOnlyCollectionBuilder<Node>(new[] {GetSubCell(point)}).ToReadOnlyCollection();
+#else
+                return new List<Node>(new[]{GetSubCell(point)}).AsReadOnly();
+#endif
+
+            }
+
+            var cells = GetSubCells();
+            if (shapeFilter == null)
+            {
+                return cells;
+            }
+            var copy = new List<Node>(cells.Count);//copy since cells contractually isn't modifiable
+            foreach (var cell in cells)
+            {
+                SpatialRelation rel = cell.GetShape().Relate(shapeFilter);
+                if (rel == SpatialRelation.DISJOINT)
+                    continue;
+                cell.shapeRel = rel;
+                copy.Add(cell);
+            }
+            cells = copy;
+            return cells;
+        }
+
+        /*
+         * Performant implementations are expected to implement this efficiently by considering the current
+         * cell's boundary.
+         * Precondition: Never called when getLevel() == maxLevel.
+         * Precondition: this.getShape().relate(p) != DISJOINT.
+         */
+        public abstract Node GetSubCell(Point p);
+
+        //TODO Cell getSubCell(byte b)
+
+        /*
+         * Gets the cells at the next grid cell level that cover this cell.
+         * Precondition: Never called when getLevel() == maxLevel.
+         *
+         * @return A set of cells (no dups), sorted. Not Modifiable.
+         */
+        public abstract IList<Node> GetSubCells();
+
+        /*
+         * {@link #getSubCells()}.size() -- usually a constant. Should be >=2
+         */
+        public abstract int GetSubCellsSize();
+
+        public abstract Shape GetShape();
+
+        public virtual Point GetCenter()
+        {
+            return GetShape().GetCenter();
+        }
+
+
+        public int CompareTo(Node o)
+        {
+            return System.String.CompareOrdinal(GetTokenString(), o.GetTokenString());
+        }
+
+        public override bool Equals(object obj)
+        {
+            return !(obj == null || !(obj is Node)) && GetTokenString().Equals(((Node) obj).GetTokenString());
+        }
+
+        public override int GetHashCode()
+        {
+            return GetTokenString().GetHashCode();
+        }
+
+        public override string ToString()
+        {
+            return GetTokenString() + (IsLeaf() ? new string(new[] {(char) LEAF_BYTE}) : string.Empty);
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/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
new file mode 100644
index 0000000..230fd4a
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/QuadPrefixTree.cs
@@ -0,0 +1,323 @@
+/*
+ * 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.Text;
+using Spatial4n.Core.Context;
+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)
+    /// </summary>
+    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 static readonly int MAX_LEVELS_POSSIBLE = 50;//not really sure how big this should be
+
+        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;
+
+        private double gridW;
+        private double gridH;
+
+        double[] levelW;
+        double[] levelH;
+        int[] levelS; // side
+        int[] levelN; // number
+
+        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();
+
+            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;
+            ymid = ymin + gridH / 2.0;
+            levelW[0] = gridW / 2.0;
+            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;
+                levelH[i] = levelH[i - 1] / 2.0;
+                levelS[i] = levelS[i - 1] * 2;
+                levelN[i] = levelN[i - 1] * 4;
+            }
+
+        }
+
+        public override int GetLevelForDistance(double dist)
+        {
+            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
+                if (dist > levelW[i] && dist > levelH[i])
+                {
+                    return i + 1;
+                }
+            }
+            return maxLevels;
+        }
+
+        protected override Node GetNode(Point p, int level)
+        {
+            var cells = new List<Node>(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);
+        }
+
+        public override Node GetNode(byte[] bytes, int offset, int len)
+        {
+            throw new System.NotImplementedException();
+        }
+
+        public override IList<Node> GetNodes(Shape shape, int detailLevel, bool inclParents)
+        {
+            var point = shape as Point;
+            if (point != null)
+                return base.GetNodesAltPoint(point, detailLevel, inclParents);
+            else
+                return base.GetNodes(shape, detailLevel, inclParents);
+        }
+
+        private void Build(double x, double y, int level, List<Node> 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)
+        {
+            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);
+            if (SpatialRelation.CONTAINS == v)
+            {
+                str.Append(c);
+                //str.append(SpatialPrefixGrid.COVER);
+                matches.Add(new QuadCell(str.ToString(), v.Transpose(), this));
+            }
+            else if (SpatialRelation.DISJOINT == v)
+            {
+                // nothing
+            }
+            else
+            { // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
+                str.Append(c);
+
+                int nextLevel = level + 1;
+                if (nextLevel >= maxLevel)
+                {
+                    //str.append(SpatialPrefixGrid.INTERSECTS);
+                    matches.Add(new QuadCell(str.ToString(), v.Transpose(), this));
+                }
+                else
+                {
+                    Build(cx, cy, nextLevel, matches, str, shape, maxLevel);
+                }
+            }
+            str.Length = strlen;
+        }
+
+        public class QuadCell : Node
+        {
+
+            public QuadCell(String token, QuadPrefixTree enclosingInstance)
+                : base(enclosingInstance, token)
+            {
+            }
+
+            public QuadCell(String token, SpatialRelation shapeRel, QuadPrefixTree enclosingInstance)
+                : base(enclosingInstance, token)
+            {
+                this.shapeRel = shapeRel;
+            }
+
+            public override void Reset(string newToken)
+            {
+                base.Reset(newToken);
+                shape = null;
+            }
+
+            public override IList<Node> 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)
+                      };
+                return cells;
+            }
+
+            public override int GetSubCellsSize()
+            {
+                return 4;
+            }
+
+            public override Node GetSubCell(Point p)
+            {
+                return ((QuadPrefixTree)spatialPrefixTree).GetNode(p, GetLevel() + 1); //not performant!
+            }
+
+            private Shape shape;//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;
+
+                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];
+                    }
+                    else
+                    {
+                        throw new Exception("unexpected char: " + c);
+                    }
+                }
+                int len = token.Length;
+                double width, height;
+                if (len > 0)
+                {
+                    width = tree.levelW[len - 1];
+                    height = tree.levelH[len - 1];
+                }
+                else
+                {
+                    width = tree.gridW;
+                    height = tree.gridH;
+                }
+                return spatialPrefixTree.ctx.MakeRectangle(xmin, xmin + width, ymin, ymin + height);
+            }
+        }//QuadCell
+
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/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
new file mode 100644
index 0000000..908fded
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTree.cs
@@ -0,0 +1,276 @@
+/*
+ * 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.Collections.ObjectModel;
+using System.Diagnostics;
+using System.Linq;
+using System.Runtime.CompilerServices;
+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. 
+    /// </summary>
+    public abstract class SpatialPrefixTree
+    {
+        protected readonly int maxLevels;
+        internal readonly SpatialContext ctx;// it's internal to allow Node to access it
+
+        protected SpatialPrefixTree(SpatialContext ctx, int maxLevels)
+        {
+            Debug.Assert(maxLevels > 0);
+            this.ctx = ctx;
+            this.maxLevels = maxLevels;
+        }
+
+        public SpatialContext GetSpatialContext()
+        {
+            return ctx;
+        }
+
+        public int GetMaxLevels()
+        {
+            return maxLevels;
+        }
+
+        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
+        /// grid, such that you can get a grid with just the right amount of
+        /// precision.
+        /// </summary>
+        /// <param name="dist">>= 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()
+        {
+            if (worldNode == null)
+            {
+                worldNode = GetNode("");
+            }
+            return worldNode;
+        }
+
+        /*
+         * 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);
+
+        public abstract Node GetNode(byte[] bytes, int offset, int len);
+
+        //public Node GetNode(byte[] bytes, int offset, int len, Node target)
+        //{
+        //    if (target == null)
+        //    {
+        //        return GetNode(bytes, offset, len);
+        //    }
+
+        //    target.Reset(bytes, offset, len);
+        //    return target;
+        //}
+
+        public Node GetNode(string token, Node target)
+        {
+            if (target == null)
+            {
+                return GetNode(token);
+            }
+
+            target.Reset(token);
+            return target;
+        }
+
+        protected virtual Node GetNode(Point p, int level)
+        {
+            return GetNodes(p, level, false).ElementAt(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)
+        {
+            if (detailLevel > maxLevels)
+            {
+                throw new ArgumentException("detailLevel > maxLevels", "detailLevel");
+            }
+
+            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 cells;
+        }
+
+        private void RecursiveGetNodes(Node node, Shape shape, int detailLevel, bool inclParents, IList<Node> result)
+        {
+            if (node.IsLeaf())
+            {//cell is within shape
+                result.Add(node);
+                return;
+            }
+
+            var subCells = node.GetSubCells(shape);
+            if (node.GetLevel() == detailLevel - 1)
+            {
+                if (subCells.Count < node.GetSubCellsSize())
+                {
+                    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);
+                }
+            }
+            else
+            {
+                if (inclParents)
+                {
+                    result.Add(node);
+                }
+                foreach (var subCell in subCells)
+                {
+                    RecursiveGetNodes(subCell, shape, detailLevel, inclParents, result);//tail call
+                }
+            }
+        }
+
+        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)
+        {
+            Node cell = GetNode(p, detailLevel);
+            if (!inclParents)
+            {
+#if !NET35
+                return new ReadOnlyCollectionBuilder<Node>(new[] { cell }).ToReadOnlyCollection();
+#else
+                return new List<Node>(new[] { cell }).AsReadOnly();
+#endif
+            }
+
+            String endToken = cell.GetTokenString();
+            Debug.Assert(endToken.Length == detailLevel);
+            var cells = new List<Node>(detailLevel);
+            for (int i = 1; i < detailLevel; i++)
+            {
+                cells.Add(GetNode(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)
+        {
+            var tokens = new List<String>((nodes.Count));
+            foreach (Node node in nodes)
+            {
+                String token = node.GetTokenString();
+                if (node.IsLeaf())
+                {
+                    tokens.Add(token + (char)Node.LEAF_BYTE);
+                }
+                else
+                {
+                    tokens.Add(token);
+                }
+            }
+            return tokens;
+        }
+
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs b/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs
new file mode 100644
index 0000000..e4e73c6
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs
@@ -0,0 +1,102 @@
+/*
+ * 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 Spatial4n.Core.Context;
+using Spatial4n.Core.Distance;
+
+namespace Lucene.Net.Spatial.Prefix.Tree
+{
+    /// <summary>
+    /// Abstract Factory for creating {@link SpatialPrefixTree} instances with useful
+    /// defaults and passed on configurations defined in a Map.
+    /// </summary>
+    public abstract class SpatialPrefixTreeFactory
+    {
+        private const double DEFAULT_GEO_MAX_DETAIL_KM = 0.001; //1m
+        public static readonly String PREFIX_TREE = "prefixTree";
+        public static readonly String MAX_LEVELS = "maxLevels";
+        public static readonly String MAX_DIST_ERR = "maxDistErr";
+
+        protected Dictionary<String, String> args;
+        protected SpatialContext ctx;
+        protected int? maxLevels;
+
+        /// <summary>
+        /// The factory  is looked up via "prefixTree" in args, expecting "geohash" or "quad".
+        /// If its neither of these, then "geohash" is chosen for a geo context, otherwise "quad" is chosen.
+        /// </summary>
+        /// <param name="args"></param>
+        /// <param name="ctx"></param>
+        /// <returns></returns>
+        public static SpatialPrefixTree MakeSPT(Dictionary<String, String> args, SpatialContext ctx)
+        {
+            SpatialPrefixTreeFactory instance;
+            String cname;
+            if (!args.TryGetValue(PREFIX_TREE, out cname) || cname == null)
+                cname = ctx.IsGeo() ? "geohash" : "quad";
+            if ("geohash".Equals(cname, StringComparison.InvariantCultureIgnoreCase))
+                instance = new GeohashPrefixTree.Factory();
+            else if ("quad".Equals(cname, StringComparison.InvariantCultureIgnoreCase))
+                instance = new QuadPrefixTree.Factory();
+            else
+            {
+                Type t = Type.GetType(cname);
+                instance = (SpatialPrefixTreeFactory)Activator.CreateInstance(t);
+            }
+            instance.Init(args, ctx);
+            return instance.NewSPT();
+        }
+
+        protected void Init(Dictionary<String, String> args, SpatialContext ctx)
+        {
+            this.args = args;
+            this.ctx = ctx;
+            InitMaxLevels();
+        }
+
+        protected void InitMaxLevels()
+        {
+            String mlStr;
+            if (args.TryGetValue(MAX_LEVELS, out mlStr) && mlStr != null)
+            {
+                maxLevels = int.Parse(mlStr);
+                return;
+            }
+
+            double degrees;
+            if (!args.TryGetValue(MAX_DIST_ERR, out mlStr) || mlStr == null)
+            {
+                if (!ctx.IsGeo())
+                    return; //let default to max
+                degrees = DistanceUtils.Dist2Degrees(DEFAULT_GEO_MAX_DETAIL_KM, DistanceUtils.EARTH_MEAN_RADIUS_KM);
+            }
+            else
+            {
+                degrees = Double.Parse(mlStr);
+            }
+            maxLevels = GetLevelForDistance(degrees);
+        }
+
+        /* Calls {@link SpatialPrefixTree#getLevelForDistance(double)}. */
+        protected abstract int GetLevelForDistance(double degrees);
+
+        protected abstract SpatialPrefixTree NewSPT();
+
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Properties/AssemblyInfo.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Properties/AssemblyInfo.cs b/src/Lucene.Net.Spatial/Properties/AssemblyInfo.cs
new file mode 100644
index 0000000..a5b4d0a
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Properties/AssemblyInfo.cs
@@ -0,0 +1,63 @@
+/*
+ * 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.Reflection;
+using System.Runtime.InteropServices;
+using System.Security;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("Lucene.Net.Contrib.Spatial")]
+[assembly: AssemblyDescription("The Apache Software Foundation Lucene.Net a full-text search engine library")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("The Apache Software Foundation")]
+[assembly: AssemblyProduct("Lucene.Net.Contrib.Spatial")]
+[assembly: AssemblyCopyright("Copyright 2009 - 2012 The Apache Software Foundation")]
+[assembly: AssemblyTrademark("Copyright 2009 - 2012 The Apache Software Foundation")]
+[assembly: AssemblyDefaultAlias("Lucene.Net.Spatial")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("5c8e810f-4bf7-472f-9785-8d80a0de6ea8")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyInformationalVersionAttribute("3.0.3")]
+
+[assembly: AssemblyVersion("3.0.3")]
+[assembly: AssemblyFileVersion("3.0.3")]
+
+
+[assembly: AssemblyDelaySign(false)]
+[assembly: AssemblyKeyFile("")]
+[assembly: AssemblyKeyName("")]
+
+[assembly: AllowPartiallyTrustedCallers]

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Queries/SpatialArgs.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Queries/SpatialArgs.cs b/src/Lucene.Net.Spatial/Queries/SpatialArgs.cs
new file mode 100644
index 0000000..9af4c7f
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Queries/SpatialArgs.cs
@@ -0,0 +1,142 @@
+/*
+ * 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.Text;
+using Spatial4n.Core.Context;
+using Spatial4n.Core.Exceptions;
+using Spatial4n.Core.Shapes;
+
+namespace Spatial4n.Core.Exceptions
+{
+    [Serializable]
+    public class InvalidSpatialArgument : ArgumentException
+    {
+        public InvalidSpatialArgument(String reason)
+            : base(reason)
+        {
+        }
+    }
+}
+
+namespace Lucene.Net.Spatial.Queries
+{
+    public class SpatialArgs
+    {
+        public static readonly double DEFAULT_DISTERRPCT = 0.025d;
+
+        public SpatialOperation Operation { get; set; }
+
+        public SpatialArgs(SpatialOperation operation, Shape shape)
+        {
+            if (operation == null || shape == null)
+                throw new ArgumentException("operation and shape are required");
+            this.Operation = operation;
+            this.Shape = shape;
+        }
+
+        /// <summary>
+        /// Computes the distance given a shape and the {@code distErrPct}.  The
+        /// algorithm is the fraction of the distance from the center of the query
+        /// shape to its furthest bounding box corner.
+        /// </summary>
+        /// <param name="shape">Mandatory.</param>
+        /// <param name="distErrPct">0 to 0.5</param>
+        /// <param name="ctx">Mandatory</param>
+        /// <returns>A distance (in degrees).</returns>
+        public static double CalcDistanceFromErrPct(Shape shape, double distErrPct, SpatialContext ctx)
+        {
+            if (distErrPct < 0 || distErrPct > 0.5)
+            {
+                throw new ArgumentException("distErrPct " + distErrPct + " must be between [0 to 0.5]", "distErrPct");
+            }
+            if (distErrPct == 0 || shape is Point)
+            {
+                return 0;
+            }
+            Rectangle bbox = shape.GetBoundingBox();
+            //The diagonal distance should be the same computed from any opposite corner,
+            // and this is the longest distance that might be occurring within the shape.
+            double diagonalDist = ctx.GetDistCalc().Distance(
+                ctx.MakePoint(bbox.GetMinX(), bbox.GetMinY()), bbox.GetMaxX(), bbox.GetMaxY());
+            return diagonalDist*0.5*distErrPct;
+        }
+
+        /// <summary>
+        /// Gets the error distance that specifies how precise the query shape is. This
+        /// looks at {@link #getDistErr()}, {@link #getDistErrPct()}, and {@code
+        /// defaultDistErrPct}.
+        /// </summary>
+        /// <param name="ctx"></param>
+        /// <param name="defaultDistErrPct">0 to 0.5</param>
+        /// <returns>>= 0</returns>
+        public double ResolveDistErr(SpatialContext ctx, double defaultDistErrPct)
+        {
+            if (DistErr != null)
+                return DistErr.Value;
+            double? distErrPct = (this.distErrPct ?? defaultDistErrPct);
+            return CalcDistanceFromErrPct(Shape, distErrPct.Value, ctx);
+        }
+
+        /// <summary>
+        /// Check if the arguments make sense -- throw an exception if not
+        /// </summary>
+        public void Validate()
+        {
+            if (Operation.IsTargetNeedsArea() && !Shape.HasArea())
+            {
+                throw new ArgumentException(Operation + " only supports geometry with area");
+            }
+        }
+
+        public override String ToString()
+        {
+            return SpatialArgsParser.WriteSpatialArgs(this);
+        }
+
+        //------------------------------------------------
+        // Getters & Setters
+        //------------------------------------------------
+
+        public Shape Shape { get; set; }
+
+        /// <summary>
+        /// A measure of acceptable error of the shape as a fraction. This effectively
+        /// inflates the size of the shape but should not shrink it.
+        /// <p/>
+        /// The default is {@link #DEFAULT_DIST_PRECISION}
+        /// </summary>
+        /// <returns>0 to 0.5</returns>
+        public double? DistErrPct
+        {
+            get { return distErrPct; }
+            set
+            {
+                if (value != null)
+                    distErrPct = value.Value;
+            }
+        }
+        private double? distErrPct;
+
+        /// <summary>
+        /// The acceptable error of the shape.  This effectively inflates the
+        /// size of the shape but should not shrink it.
+        /// </summary>
+        /// <returns>>= 0</returns>
+        public double? DistErr { get; set; }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Queries/SpatialArgsParser.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Queries/SpatialArgsParser.cs b/src/Lucene.Net.Spatial/Queries/SpatialArgsParser.cs
new file mode 100644
index 0000000..6335780
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Queries/SpatialArgsParser.cs
@@ -0,0 +1,140 @@
+/*
+ * 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.Text;
+using Spatial4n.Core.Context;
+using Spatial4n.Core.Io;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Queries
+{
+    public class SpatialArgsParser
+    {
+        public const String DIST_ERR_PCT = "distErrPct";
+        public const String DIST_ERR = "distErr";
+
+        /// <summary>
+        /// Writes a close approximation to the parsed input format.
+        /// </summary>
+        /// <param name="args"></param>
+        /// <returns></returns>
+        public static String WriteSpatialArgs(SpatialArgs args)
+        {
+            var str = new StringBuilder();
+            str.Append(args.Operation.GetName());
+            str.Append('(');
+            str.Append(args.Shape);
+            if (args.DistErrPct != null)
+                str.Append(" distErrPct=").Append(String.Format("{0:0.00}%", args.DistErrPct*100d));
+            if (args.DistErr != null)
+                str.Append(" distErr=").Append(args.DistErr);
+            str.Append(')');
+            return str.ToString();
+        }
+
+        /// <summary>
+        /// Parses a string such as "Intersects(-10,20,-8,22) distErrPct=0.025".
+        /// </summary>
+        /// <param name="v"></param>
+        /// <param name="ctx"></param>
+        /// <returns></returns>
+        public SpatialArgs Parse(String v, SpatialContext ctx)
+        {
+            int idx = v.IndexOf('(');
+            int edx = v.LastIndexOf(')');
+
+            if (idx < 0 || idx > edx)
+            {
+                throw new ArgumentException("missing parens: " + v);
+            }
+
+            SpatialOperation op = SpatialOperation.Get(v.Substring(0, idx).Trim());
+
+            //Substring in .NET is (startPosn, length), But in Java it's (startPosn, endPosn)
+            //see http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/String.html#substring(int, int)
+            String body = v.Substring(idx + 1, edx - (idx + 1)).Trim();
+            if (body.Length < 1)
+            {
+                throw new ArgumentException("missing body : " + v);
+            }
+
+            var shape = ctx.ReadShape(body);
+            var args = new SpatialArgs(op, shape);
+
+            if (v.Length > (edx + 1))
+            {
+                body = v.Substring(edx + 1).Trim();
+                if (body.Length > 0)
+                {
+                    Dictionary<String, String> aa = ParseMap(body);
+                    args.DistErrPct = ReadDouble(aa["distErrPct"]); aa.Remove(DIST_ERR_PCT);
+                    args.DistErr = ReadDouble(aa["distErr"]); aa.Remove(DIST_ERR);
+                    if (aa.Count != 0)
+                    {
+                        throw new ArgumentException("unused parameters: " + aa);
+                    }
+                }
+            }
+            args.Validate();
+            return args;
+        }
+
+        protected static double? ReadDouble(String v)
+        {
+            double val;
+            return double.TryParse(v, out val) ? val : (double?)null;
+        }
+
+        protected static bool ReadBool(String v, bool defaultValue)
+        {
+            bool ret;
+            return bool.TryParse(v, out ret) ? ret : defaultValue;
+        }
+
+        /// <summary>
+        /// Parses "a=b c=d f" (whitespace separated) into name-value pairs. If there
+        /// is no '=' as in 'f' above then it's short for f=f.
+        /// </summary>
+        /// <param name="body"></param>
+        /// <returns></returns>
+        protected static Dictionary<String, String> ParseMap(String body)
+        {
+            var map = new Dictionary<String, String>();
+            int tokenPos = 0;
+            var st = body.Split(new[] {' ', '\n', '\t'}, StringSplitOptions.RemoveEmptyEntries);
+            while (tokenPos < st.Length)
+            {
+                String a = st[tokenPos++];
+                int idx = a.IndexOf('=');
+                if (idx > 0)
+                {
+                    String k = a.Substring(0, idx);
+                    String v = a.Substring(idx + 1);
+                    map[k] = v;
+                }
+                else
+                {
+                    map[a] = a;
+                }
+            }
+            return map;
+        }
+
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Queries/SpatialOperation.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Queries/SpatialOperation.cs b/src/Lucene.Net.Spatial/Queries/SpatialOperation.cs
new file mode 100644
index 0000000..af82b7d
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Queries/SpatialOperation.cs
@@ -0,0 +1,116 @@
+/* See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * Esri Inc. 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.Globalization;
+using System.Linq;
+using Spatial4n.Core.Exceptions;
+
+namespace Lucene.Net.Spatial.Queries
+{
+    public class SpatialOperation
+    {
+        // Private registry
+        private static readonly Dictionary<String, SpatialOperation> registry = new Dictionary<string, SpatialOperation>();
+        private static readonly IList<SpatialOperation> list = new List<SpatialOperation>();
+
+        // Geometry Operations
+
+        /// <summary>
+        /// Bounding box of the *indexed* shape.
+        /// </summary>
+        public static readonly SpatialOperation BBoxIntersects = new SpatialOperation("BBoxIntersects", true, false, false);
+        
+        /// <summary>
+        /// Bounding box of the *indexed* shape.
+        /// </summary>
+        public static readonly SpatialOperation BBoxWithin = new SpatialOperation("BBoxWithin", true, false, false);
+
+        public static readonly SpatialOperation Contains = new SpatialOperation("Contains", true, true, false);
+        public static readonly SpatialOperation Intersects = new SpatialOperation("Intersects", true, false, false);
+        public static readonly SpatialOperation IsEqualTo = new SpatialOperation("IsEqualTo", false, false, false);
+        public static readonly SpatialOperation IsDisjointTo = new SpatialOperation("IsDisjointTo", false, false, false);
+        public static readonly SpatialOperation IsWithin = new SpatialOperation("IsWithin", true, false, true);
+        public static readonly SpatialOperation Overlaps = new SpatialOperation("Overlaps", true, false, true);
+
+        // Member variables
+        private readonly bool scoreIsMeaningful;
+        private readonly bool sourceNeedsArea;
+        private readonly bool targetNeedsArea;
+        private readonly String name;
+
+        protected SpatialOperation(String name, bool scoreIsMeaningful, bool sourceNeedsArea, bool targetNeedsArea)
+        {
+            this.name = name;
+            this.scoreIsMeaningful = scoreIsMeaningful;
+            this.sourceNeedsArea = sourceNeedsArea;
+            this.targetNeedsArea = targetNeedsArea;
+            registry[name] = this;
+            registry[name.ToUpper(CultureInfo.CreateSpecificCulture("en-US"))] = this;
+            list.Add(this);
+        }
+
+        public static SpatialOperation Get(String v)
+        {
+            SpatialOperation op;
+            if (!registry.TryGetValue(v, out op) || op == null)
+            {
+                if (!registry.TryGetValue(v.ToUpper(CultureInfo.CreateSpecificCulture("en-US")), out op) || op == null)
+                    throw new ArgumentException("Unknown Operation: " + v, "v");
+            }
+            return op;
+        }
+
+        public static IList<SpatialOperation> Values()
+        {
+            return list;
+        }
+
+        public static bool Is(SpatialOperation op, params SpatialOperation[] tst)
+        {
+            return tst.Any(t => op == t);
+        }
+
+
+        // ================================================= Getters / Setters =============================================
+
+        public bool IsScoreIsMeaningful()
+        {
+            return scoreIsMeaningful;
+        }
+
+        public bool IsSourceNeedsArea()
+        {
+            return sourceNeedsArea;
+        }
+
+        public bool IsTargetNeedsArea()
+        {
+            return targetNeedsArea;
+        }
+
+        public String GetName()
+        {
+            return name;
+        }
+
+        public override String ToString()
+        {
+            return name;
+        }
+
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Queries/UnsupportedSpatialOperation.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Queries/UnsupportedSpatialOperation.cs b/src/Lucene.Net.Spatial/Queries/UnsupportedSpatialOperation.cs
new file mode 100644
index 0000000..ad93734
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Queries/UnsupportedSpatialOperation.cs
@@ -0,0 +1,29 @@
+/*
+ * 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;
+
+namespace Lucene.Net.Spatial.Queries
+{
+    [Serializable]
+    public class UnsupportedSpatialOperation : InvalidOperationException
+    {
+        public UnsupportedSpatialOperation(SpatialOperation op) : base(op.GetName())
+        {
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/SpatialStrategy.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/SpatialStrategy.cs b/src/Lucene.Net.Spatial/SpatialStrategy.cs
new file mode 100644
index 0000000..f47deca
--- /dev/null
+++ b/src/Lucene.Net.Spatial/SpatialStrategy.cs
@@ -0,0 +1,150 @@
+/*
+ * 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.Documents;
+using Lucene.Net.Search;
+using Lucene.Net.Search.Function;
+using Lucene.Net.Spatial.Queries;
+using Lucene.Net.Spatial.Util;
+using Spatial4n.Core.Context;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial
+{
+    /// <summary>
+    /// The SpatialStrategy encapsulates an approach to indexing and searching based on shapes.
+    /// <p/>
+    /// Note that a SpatialStrategy is not involved with the Lucene stored field values of shapes, which is
+    /// immaterial to indexing and search.
+    /// <p/>
+    /// Thread-safe.
+    /// </summary>
+    public abstract class SpatialStrategy
+    {
+        protected readonly SpatialContext ctx;
+        protected readonly string fieldName;
+
+        /// <summary>
+        /// Constructs the spatial strategy with its mandatory arguments.
+        /// </summary>
+        /// <param name="ctx"></param>
+        /// <param name="fieldName"> </param>
+        protected SpatialStrategy(SpatialContext ctx, string fieldName)
+        {
+            if (ctx == null)
+                throw new ArgumentException("ctx is required", "ctx");
+            this.ctx = ctx;
+            if (string.IsNullOrEmpty(fieldName))
+                throw new ArgumentException("fieldName is required", "fieldName");
+            this.fieldName = fieldName;
+        }
+
+        public SpatialContext GetSpatialContext()
+        {
+            return ctx;
+        }
+
+        /// <summary>
+        /// The name of the field or the prefix of them if there are multiple
+        /// fields needed internally.
+        /// </summary>
+        /// <returns></returns>
+        public String GetFieldName()
+        {
+            return fieldName;
+        }
+
+        /// <summary>
+        /// Returns the IndexableField(s) from the <c>shape</c> that are to be
+        /// added to the {@link org.apache.lucene.document.Document}.  These fields
+        /// are expected to be marked as indexed and not stored.
+        /// <p/>
+        /// Note: If you want to <i>store</i> the shape as a string for retrieval in search
+        /// results, you could add it like this:
+        /// <pre>document.add(new StoredField(fieldName,ctx.toString(shape)));</pre>
+        /// The particular string representation used doesn't matter to the Strategy since it
+        /// doesn't use it.
+        /// </summary>
+        /// <param name="shape"></param>
+        /// <returns>Not null nor will it have null elements.</returns>
+        public abstract AbstractField[] CreateIndexableFields(Shape shape);
+
+        public AbstractField CreateStoredField(Shape shape)
+        {
+            return new Field(GetFieldName(), ctx.ToString(shape), Field.Store.YES, Field.Index.NOT_ANALYZED_NO_NORMS, Field.TermVector.NO);
+        }
+
+        /// <summary>
+        /// Make a ValueSource returning the distance between the center of the
+        /// indexed shape and {@code queryPoint}.  If there are multiple indexed shapes
+        /// then the closest one is chosen.
+        /// </summary>
+        public abstract ValueSource MakeDistanceValueSource(Point queryPoint);
+
+        /// <summary>
+        /// Make a (ConstantScore) Query based principally on {@link org.apache.lucene.spatial.query.SpatialOperation}
+        /// and {@link Shape} from the supplied {@code args}.
+        /// The default implementation is
+        /// <pre>return new ConstantScoreQuery(makeFilter(args));</pre>
+        /// </summary>
+        /// <param name="args"></param>
+        /// <returns></returns>
+        public virtual ConstantScoreQuery MakeQuery(SpatialArgs args)
+        {
+            return new ConstantScoreQuery(MakeFilter(args));
+        }
+
+        /// <summary>
+        /// Make a Filter based principally on {@link org.apache.lucene.spatial.query.SpatialOperation}
+        /// and {@link Shape} from the supplied {@code args}.
+        /// <p />
+        /// If a subclasses implements
+        /// {@link #makeQuery(org.apache.lucene.spatial.query.SpatialArgs)}
+        /// then this method could be simply:
+        /// <pre>return new QueryWrapperFilter(makeQuery(args).getQuery());</pre>
+        /// </summary>
+        /// <param name="args"></param>
+        /// <returns></returns>
+        public abstract Filter MakeFilter(SpatialArgs args);
+
+        /// <summary>
+        /// Returns a ValueSource with values ranging from 1 to 0, depending inversely
+        /// on the distance from {@link #makeDistanceValueSource(com.spatial4j.core.shape.Point)}.
+        /// The formula is <c>c/(d + c)</c> where 'd' is the distance and 'c' is
+        /// one tenth the distance to the farthest edge from the center. Thus the
+        /// scores will be 1 for indexed points at the center of the query shape and as
+        /// low as ~0.1 at its furthest edges.
+        /// </summary>
+        /// <param name="queryShape"></param>
+        /// <returns></returns>
+        public ValueSource MakeRecipDistanceValueSource(Shape queryShape)
+        {
+            Rectangle bbox = queryShape.GetBoundingBox();
+            double diagonalDist = ctx.GetDistCalc().Distance(
+                ctx.MakePoint(bbox.GetMinX(), bbox.GetMinY()), bbox.GetMaxX(), bbox.GetMaxY());
+            double distToEdge = diagonalDist*0.5;
+            float c = (float) distToEdge*0.1f; //one tenth
+            return new ReciprocalFloatFunction(MakeDistanceValueSource(queryShape.GetCenter()), 1f, c, c);
+        }
+
+        public override string ToString()
+        {
+            return GetType().Name + " field:" + fieldName + " ctx=" + ctx;
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/c9f901b2/src/Lucene.Net.Spatial/Util/Bits.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Spatial/Util/Bits.cs b/src/Lucene.Net.Spatial/Util/Bits.cs
new file mode 100644
index 0000000..f0040ee
--- /dev/null
+++ b/src/Lucene.Net.Spatial/Util/Bits.cs
@@ -0,0 +1,92 @@
+/*
+ * 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.
+ */
+
+namespace Lucene.Net.Spatial.Util
+{
+    /// <summary>
+    /// Interface for Bitset-like structures.
+    /// </summary>
+    public interface IBits
+    {
+        bool Get(int index);
+        int Length();
+    }
+
+    /// <summary>
+    /// Empty implementation, basically just so we can provide EMPTY_ARRAY
+    /// </summary>
+    public abstract class Bits : IBits
+    {
+        public static readonly Bits[] EMPTY_ARRAY = new Bits[0];
+
+        public virtual bool Get(int index)
+        {
+            throw new System.NotImplementedException();
+        }
+
+        public virtual int Length()
+        {
+            throw new System.NotImplementedException();
+        }
+    }
+
+    /// <summary>
+    /// Bits impl of the specified length with all bits set.
+    /// </summary>
+    public class MatchAllBits : Bits
+    {
+        private readonly int len;
+
+        public MatchAllBits(int len)
+        {
+            this.len = len;
+        }
+
+        public override bool Get(int index)
+        {
+            return true;
+        }
+
+        public override int Length()
+        {
+            return len;
+        }
+    }
+
+    /// <summary>
+    /// Bits impl of the specified length with no bits set. 
+    /// </summary>
+    public class MatchNoBits : Bits
+    {
+        private readonly int len;
+
+        public MatchNoBits(int len)
+        {
+            this.len = len;
+        }
+
+        public override bool Get(int index)
+        {
+            return false;
+        }
+
+        public override int Length()
+        {
+            return len;
+        }
+    }
+}
\ No newline at end of file


Mime
View raw message