lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject svn commit: r1344182 [1/9] - in /incubator/lucene.net/trunk: ./ build/vs2010/test/ lib/Spatial4n/ src/contrib/Analyzers/ src/contrib/Analyzers/Filters/ src/contrib/Spatial/ src/contrib/Spatial/Prefix/ src/contrib/Spatial/Prefix/Tree/ src/contrib/Spatia...
Date Wed, 30 May 2012 10:17:21 GMT
Author: synhershko
Date: Wed May 30 10:17:16 2012
New Revision: 1344182

URL: http://svn.apache.org/viewvc?rev=1344182&view=rev
Log:
Merge branch 'trunk' of git@github.com:synhershko/lucene.net.git

Conflicts:
	.gitignore
	build/vs2010/test/Contrib.Spatial.Test.sln
	src/contrib/Analyzers/Contrib.Analyzers.csproj
	src/contrib/Spatial/Contrib.Spatial.csproj
	src/contrib/Spatial/Properties/AssemblyInfo.cs
	src/core/Lucene.Net.csproj
	test/contrib/Analyzers/Contrib.Analyzers.Test.csproj
	test/contrib/Spatial/Contrib.Spatial.Test.csproj
	test/core/Util/LuceneTestCase.cs
	test/core/Util/Paths.cs

Added:
    incubator/lucene.net/trunk/lib/Spatial4n/
    incubator/lucene.net/trunk/lib/Spatial4n/README.txt
    incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.dll
    incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.pdb
    incubator/lucene.net/trunk/src/contrib/Analyzers/Filters/
    incubator/lucene.net/trunk/src/contrib/Analyzers/Filters/ChainedFilter.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixCellsTokenizer.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixTreeStrategy.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeFilter.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeStrategy.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/GeohashPrefixTree.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/Node.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/QuadPrefixTree.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTree.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/SimpleSpatialFieldInfo.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/SpatialFieldInfo.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/SpatialStrategy.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/Bits.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/CachedDistanceValueSource.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/CachingDoubleValueSource.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/CompatibilityExtensions.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/FixedBitSet.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/FunctionQuery.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/NumericFieldInfo.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/OpenBitSetIterator.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/ShapeFieldCache.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/ShapeFieldCacheProvider.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/StringListTokenizer.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/TermsEnumCompatibility.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/TruncateFilter.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Util/ValueSourceFilter.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Vector/
    incubator/lucene.net/trunk/src/contrib/Spatial/Vector/DistanceValueSource.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Vector/TwoDoublesFieldInfo.cs
    incubator/lucene.net/trunk/src/contrib/Spatial/Vector/TwoDoublesStrategy.cs
    incubator/lucene.net/trunk/test-files/
    incubator/lucene.net/trunk/test-files/spatial/
    incubator/lucene.net/trunk/test-files/spatial/cities-IsWithin-BBox.txt
    incubator/lucene.net/trunk/test-files/spatial/data/
    incubator/lucene.net/trunk/test-files/spatial/data/countries-bbox.txt
    incubator/lucene.net/trunk/test-files/spatial/data/countries-poly.txt
    incubator/lucene.net/trunk/test-files/spatial/data/geonames-IE.txt
    incubator/lucene.net/trunk/test-files/spatial/data/states-bbox.txt
    incubator/lucene.net/trunk/test-files/spatial/data/states-poly.txt
    incubator/lucene.net/trunk/test-files/spatial/data/world-cities-points.txt
    incubator/lucene.net/trunk/test-files/spatial/states-Intersects-BBox.txt
    incubator/lucene.net/trunk/test-files/spatial/states-IsWithin-BBox.txt
    incubator/lucene.net/trunk/test/contrib/Analyzers/Filters/
    incubator/lucene.net/trunk/test/contrib/Analyzers/Filters/ChainedFilterTest.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Compatibility/
    incubator/lucene.net/trunk/test/contrib/Spatial/Compatibility/TestFixedBitSet.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/BaseRecursivePrefixTreeStrategyTestCase.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/TestRecursivePrefixTreeStrategy.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/TestSpatialPrefixField.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/TestTermQueryPrefixGridStrategy.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/Tree/
    incubator/lucene.net/trunk/test/contrib/Spatial/Prefix/Tree/SpatialPrefixTreeTest.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/SpatialMatchConcern.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/SpatialTestCase.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/SpatialTestQuery.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/StrategyTestCase.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/TestTestFramework.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Various.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Vector/
    incubator/lucene.net/trunk/test/contrib/Spatial/Vector/BaseTwoDoublesStrategyTestCase.cs
    incubator/lucene.net/trunk/test/contrib/Spatial/Vector/TwoDoublesStrategyTestCase.cs
Modified:
    incubator/lucene.net/trunk/.gitignore
    incubator/lucene.net/trunk/build/vs2010/test/Contrib.Spatial.Test.sln
    incubator/lucene.net/trunk/src/contrib/Analyzers/Contrib.Analyzers.csproj
    incubator/lucene.net/trunk/src/contrib/Spatial/Contrib.Spatial.csproj
    incubator/lucene.net/trunk/src/contrib/Spatial/Properties/AssemblyInfo.cs
    incubator/lucene.net/trunk/src/core/Lucene.Net.csproj
    incubator/lucene.net/trunk/test/contrib/Analyzers/Contrib.Analyzers.Test.csproj
    incubator/lucene.net/trunk/test/contrib/Spatial/Contrib.Spatial.Test.csproj
    incubator/lucene.net/trunk/test/core/Util/LuceneTestCase.cs
    incubator/lucene.net/trunk/test/core/Util/Paths.cs

Modified: incubator/lucene.net/trunk/.gitignore
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/.gitignore?rev=1344182&r1=1344181&r2=1344182&view=diff
==============================================================================
--- incubator/lucene.net/trunk/.gitignore (original)
+++ incubator/lucene.net/trunk/.gitignore Wed May 30 10:17:16 2012
@@ -13,4 +13,5 @@ obj
 test-results
 build/artifacts
 build/bin
-_ReSharper*
\ No newline at end of file
+_ReSharper*
+*.orig

Modified: incubator/lucene.net/trunk/build/vs2010/test/Contrib.Spatial.Test.sln
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/build/vs2010/test/Contrib.Spatial.Test.sln?rev=1344182&r1=1344181&r2=1344182&view=diff
==============================================================================
--- incubator/lucene.net/trunk/build/vs2010/test/Contrib.Spatial.Test.sln (original)
+++ incubator/lucene.net/trunk/build/vs2010/test/Contrib.Spatial.Test.sln Wed May 30 10:17:16 2012
@@ -1,26 +1,6 @@
 
 Microsoft Visual Studio Solution File, Format Version 11.00
-# Visual C# Express 2010
-#
-#
-# 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.
-#
-#
+# Visual Studio 2010
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Lucene.Net", "..\..\..\src\core\Lucene.Net.csproj", "{5D4AD9BE-1FFB-41AB-9943-25737971BF57}"
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Contrib.Spatial", "..\..\..\src\contrib\Spatial\Contrib.Spatial.csproj", "{35C347F4-24B2-4BE5-8117-A0E3001551CE}"
@@ -45,6 +25,10 @@ Global
 		{19FC2A6B-4DE9-403F-8CEF-10850F57B96E}.Debug|Any CPU.Build.0 = Debug|Any CPU
 		{19FC2A6B-4DE9-403F-8CEF-10850F57B96E}.Release|Any CPU.ActiveCfg = Release|Any CPU
 		{19FC2A6B-4DE9-403F-8CEF-10850F57B96E}.Release|Any CPU.Build.0 = Release|Any CPU
+		{777904AC-46EF-466C-9E13-2A52A6735987}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{777904AC-46EF-466C-9E13-2A52A6735987}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{777904AC-46EF-466C-9E13-2A52A6735987}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{777904AC-46EF-466C-9E13-2A52A6735987}.Release|Any CPU.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
 		HideSolutionNode = FALSE

Added: incubator/lucene.net/trunk/lib/Spatial4n/README.txt
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/lib/Spatial4n/README.txt?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/lib/Spatial4n/README.txt (added)
+++ incubator/lucene.net/trunk/lib/Spatial4n/README.txt Wed May 30 10:17:16 2012
@@ -0,0 +1,3 @@
+A .NET port of Spatial4j
+
+Project home is at https://github.com/synhershko/Spatial4n
\ No newline at end of file

Added: incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.dll
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.dll?rev=1344182&view=auto
==============================================================================
Files incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.dll (added) and incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.dll Wed May 30 10:17:16 2012 differ

Added: incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.pdb
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.pdb?rev=1344182&view=auto
==============================================================================
Files incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.pdb (added) and incubator/lucene.net/trunk/lib/Spatial4n/Spatial4n.Core.pdb Wed May 30 10:17:16 2012 differ

Modified: incubator/lucene.net/trunk/src/contrib/Analyzers/Contrib.Analyzers.csproj
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Analyzers/Contrib.Analyzers.csproj?rev=1344182&r1=1344181&r2=1344182&view=diff
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Analyzers/Contrib.Analyzers.csproj (original)
+++ incubator/lucene.net/trunk/src/contrib/Analyzers/Contrib.Analyzers.csproj Wed May 30 10:17:16 2012
@@ -185,4 +185,4 @@
   <Target Name="AfterBuild">
   </Target>
   -->
-</Project>
\ No newline at end of file
+</Project>

Added: incubator/lucene.net/trunk/src/contrib/Analyzers/Filters/ChainedFilter.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Analyzers/Filters/ChainedFilter.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Analyzers/Filters/ChainedFilter.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Analyzers/Filters/ChainedFilter.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,275 @@
+/**
+ * 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.Linq;
+using System.Text;
+
+using Lucene.Net.Search;
+using Lucene.Net.Index;
+using Lucene.Net.Util;
+
+namespace Lucene.Net.Analysis
+{
+
+    ///<summary>
+    ///* <p>
+    /// * Allows multiple {@link Filter}s to be chained.
+    /// * Logical operations such as <b>NOT</b> and <b>XOR</b>
+    /// * are applied between filters. One operation can be used
+    /// * for all filters, or a specific operation can be declared
+    /// * for each filter.
+    /// * </p>
+    /// * <p>
+    /// * Order in which filters are called depends on
+    /// * the position of the filter in the chain. It's probably
+    /// * more efficient to place the most restrictive filters
+    /// * /least computationally-intensive filters first.
+    /// * </p>
+    ///</summary>
+    public class ChainedFilter : Filter
+    {
+        public enum Logic
+        {
+            NONE = -1,
+            OR = 0,
+            AND = 1,
+            ANDNOT = 2,
+            XOR = 3
+        };
+
+        ///<summary>Logical operation when none is declared. Defaults to OR</summary>
+        public const Logic DEFAULT = Logic.OR;
+
+        /** The filter chain */
+        private Filter[] chain = null;
+
+        private Logic[] logicArray;
+
+        private Logic logic = Logic.NONE;
+
+        ///<summary>Ctor</summary><param name="chain">The chain of filters</param>
+        public ChainedFilter(Filter[] chain)
+        {
+            this.chain = chain;
+        }
+
+        ///<summary>ctor</summary>
+        ///<param name="chain">The chain of filters</param>
+        ///<param name="logicArray">Logical operations to apply between filters</param>
+        public ChainedFilter(Filter[] chain, Logic[] logicArray)
+        {
+            this.chain = chain;
+            this.logicArray = logicArray;
+        }
+
+        ///<summary>ctor</summary>
+        ///<param name="chain">The chain of filters</param>
+        ///<param name="logic">Logical operation to apply to ALL filters</param>
+        public ChainedFilter(Filter[] chain, Logic logic)
+        {
+            this.chain = chain;
+            this.logic = logic;
+        }
+
+        ///<see cref="Filter#getDocIdSet"/>
+        public override DocIdSet GetDocIdSet(IndexReader reader)
+        {
+            int[] index = new int[1]; // use array as reference to modifiable int; 
+            index[0] = 0;             // an object attribute would not be thread safe.
+            if (logic != Logic.NONE)
+                return GetDocIdSet(reader, logic, index);
+            else if (logicArray != null)
+                return GetDocIdSet(reader, logicArray, index);
+            else
+                return GetDocIdSet(reader, DEFAULT, index);
+        }
+
+        private DocIdSetIterator GetDISI(Filter filter, IndexReader reader)
+        {
+            DocIdSet docIdSet = filter.GetDocIdSet(reader);
+            if (docIdSet == null)
+            {
+                return DocIdSet.EMPTY_DOCIDSET.Iterator();
+            }
+            else
+            {
+                DocIdSetIterator iter = docIdSet.Iterator();
+                if (iter == null)
+                {
+                    return DocIdSet.EMPTY_DOCIDSET.Iterator();
+                }
+                else
+                {
+                    return iter;
+                }
+            }
+        }
+
+        private OpenBitSetDISI InitialResult(IndexReader reader, Logic logic, int[] index)
+        {
+            OpenBitSetDISI result;
+            /**
+             * First AND operation takes place against a completely false
+             * bitset and will always return zero results.
+             */
+            if (logic == Logic.AND)
+            {
+                result = new OpenBitSetDISI(GetDISI(chain[index[0]], reader), reader.MaxDoc());
+                ++index[0];
+            }
+            else if (logic == Logic.ANDNOT)
+            {
+                result = new OpenBitSetDISI(GetDISI(chain[index[0]], reader), reader.MaxDoc());
+                result.Flip(0, reader.MaxDoc()); // NOTE: may set bits for deleted docs.
+                ++index[0];
+            }
+            else
+            {
+                result = new OpenBitSetDISI(reader.MaxDoc());
+            }
+            return result;
+        }
+
+
+        ///<summary>
+        ///  * Provide a SortedVIntList when it is definitely
+        ///  * smaller than an OpenBitSet
+        ///  * @deprecated Either use CachingWrapperFilter, or
+        ///  * switch to a different DocIdSet implementation yourself.
+        ///  * This method will be removed in Lucene 4.0 
+        ///</summary>
+        protected DocIdSet FinalResult(OpenBitSetDISI result, int maxDocs)
+        {
+            return result;
+        }
+
+
+        /**
+         * Delegates to each filter in the chain.
+         * @param reader IndexReader
+         * @param logic Logical operation
+         * @return DocIdSet
+         */
+        private DocIdSet GetDocIdSet(IndexReader reader, Logic logic, int[] index)
+        {
+            OpenBitSetDISI result = InitialResult(reader, logic, index);
+            for (; index[0] < chain.Length; index[0]++)
+            {
+                DoChain(result, logic, chain[index[0]].GetDocIdSet(reader));
+            }
+            return FinalResult(result, reader.MaxDoc());
+        }
+
+        /**
+         * Delegates to each filter in the chain.
+         * @param reader IndexReader
+         * @param logic Logical operation
+         * @return DocIdSet
+         */
+        private DocIdSet GetDocIdSet(IndexReader reader, Logic[] logic, int[] index)
+        {
+            if (logic.Length != chain.Length)
+                throw new ArgumentException("Invalid number of elements in logic array");
+
+            OpenBitSetDISI result = InitialResult(reader, logic[0], index);
+            for (; index[0] < chain.Length; index[0]++)
+            {
+                DoChain(result, logic[index[0]], chain[index[0]].GetDocIdSet(reader));
+            }
+            return FinalResult(result, reader.MaxDoc());
+        }
+
+        public override String ToString()
+        {
+            StringBuilder sb = new StringBuilder();
+            sb.Append("ChainedFilter: [");
+            for (int i = 0; i < chain.Length; i++)
+            {
+                sb.Append(chain[i]);
+                sb.Append(' ');
+            }
+            sb.Append(']');
+            return sb.ToString();
+        }
+
+        private void DoChain(OpenBitSetDISI result, Logic logic, DocIdSet dis)
+        {
+
+            if (dis is OpenBitSet)
+            {
+                // optimized case for OpenBitSets
+                switch (logic)
+                {
+                    case Logic.OR:
+                        result.Or((OpenBitSet)dis);
+                        break;
+                    case Logic.AND:
+                        result.And((OpenBitSet)dis);
+                        break;
+                    case Logic.ANDNOT:
+                        result.AndNot((OpenBitSet)dis);
+                        break;
+                    case Logic.XOR:
+                        result.Xor((OpenBitSet)dis);
+                        break;
+                    default:
+                        DoChain(result, DEFAULT, dis);
+                        break;
+                }
+            }
+            else
+            {
+                DocIdSetIterator disi;
+                if (dis == null)
+                {
+                    disi = DocIdSet.EMPTY_DOCIDSET.Iterator();
+                }
+                else
+                {
+                    disi = dis.Iterator();
+                    if (disi == null)
+                    {
+                        disi = DocIdSet.EMPTY_DOCIDSET.Iterator();
+                    }
+                }
+
+                switch (logic)
+                {
+                    case Logic.OR:
+                        result.InPlaceOr(disi);
+                        break;
+                    case Logic.AND:
+                        result.InPlaceAnd(disi);
+                        break;
+                    case Logic.ANDNOT:
+                        result.InPlaceNot(disi);
+                        break;
+                    case Logic.XOR:
+                        result.InPlaceXor(disi);
+                        break;
+                    default:
+                        DoChain(result, DEFAULT, dis);
+                        break;
+                }
+            }
+        }
+
+    }
+
+}
\ No newline at end of file

Modified: incubator/lucene.net/trunk/src/contrib/Spatial/Contrib.Spatial.csproj
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Contrib.Spatial.csproj?rev=1344182&r1=1344181&r2=1344182&view=diff
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Contrib.Spatial.csproj (original)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Contrib.Spatial.csproj Wed May 30 10:17:16 2012
@@ -19,7 +19,6 @@
  under the License.
 
 -->
-
 <Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
   <PropertyGroup>
     <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
@@ -66,7 +65,7 @@
     <NoWarn>618</NoWarn>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
-    <DebugType>none</DebugType>
+    <DebugType>pdbonly</DebugType>
     <Optimize>true</Optimize>
     <OutputPath>..\..\..\build\bin\contrib\Spatial\Release\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
@@ -74,6 +73,7 @@
     <WarningLevel>4</WarningLevel>
     <DocumentationFile>..\..\..\build\bin\contrib\Spatial\Release\Lucene.Net.Contrib.Spatial.XML</DocumentationFile>
     <NoWarn>618</NoWarn>
+    <DebugSymbols>true</DebugSymbols>
   </PropertyGroup>
   <PropertyGroup>
     <SignAssembly>true</SignAssembly>
@@ -82,44 +82,46 @@
     <AssemblyOriginatorKeyFile>Lucene.Net.snk</AssemblyOriginatorKeyFile>
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="Spatial4n.Core, Version=1.0.0.0, Culture=neutral, PublicKeyToken=9f9456e1ca16d45e, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\lib\Spatial4n\Spatial4n.Core.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Data" />
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="GeoHash\GeoHashDistanceFilter.cs" />
-    <Compile Include="GeoHash\GeoHashUtils.cs" />
-    <Compile Include="Geometry\CartesianPoint.cs" />
-    <Compile Include="Geometry\DistanceUnits.cs" />
-    <Compile Include="Geometry\FixedLatLng.cs" />
-    <Compile Include="Geometry\FloatLatLng.cs" />
-    <Compile Include="Geometry\LatLng.cs" />
-    <Compile Include="Geometry\Shape\Ellipse.cs" />
-    <Compile Include="Geometry\Shape\IGeometry2D.cs" />
-    <Compile Include="Geometry\Shape\IntersectCase.cs" />
-    <Compile Include="Geometry\Shape\LineSegment.cs" />
-    <Compile Include="Geometry\Shape\LLRect.cs" />
-    <Compile Include="Geometry\Shape\Point2D.cs" />
-    <Compile Include="Geometry\Shape\Rectangle.cs" />
-    <Compile Include="Geometry\Shape\Vector2D.cs" />
+    <Compile Include="Prefix\PointPrefixTreeFieldCacheProvider.cs" />
+    <Compile Include="Prefix\PrefixCellsTokenizer.cs" />
+    <Compile Include="Prefix\PrefixTreeStrategy.cs" />
+    <Compile Include="Prefix\RecursivePrefixTreeFilter.cs" />
+    <Compile Include="Prefix\RecursivePrefixTreeStrategy.cs" />
+    <Compile Include="Prefix\TermQueryPrefixTreeStrategy.cs" />
+    <Compile Include="Prefix\Tree\GeohashPrefixTree.cs" />
+    <Compile Include="Prefix\Tree\Node.cs" />
+    <Compile Include="Prefix\Tree\QuadPrefixTree.cs" />
+    <Compile Include="Prefix\Tree\SpatialPrefixTree.cs" />
+    <Compile Include="Prefix\Tree\SpatialPrefixTreeFactory.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="Tier\CartesianPolyFilterBuilder.cs" />
-    <Compile Include="Tier\CartesianShapeFilter.cs" />
-    <Compile Include="Tier\DistanceFieldComparatorSource.cs" />
-    <Compile Include="Tier\DistanceFilter.cs" />
-    <Compile Include="Tier\DistanceHandler.cs" />
-    <Compile Include="Tier\DistanceQueryBuilder.cs" />
-    <Compile Include="Tier\DistanceUtils.cs" />
-    <Compile Include="Tier\LatLongDistanceFilter.cs" />
-    <Compile Include="Tier\Projectors\CartesianTierPlotter.cs" />
-    <Compile Include="Tier\Projectors\IProjector.cs" />
-    <Compile Include="Tier\Projectors\SinusoidalProjector.cs" />
-    <Compile Include="Tier\Shape.cs" />
-    <Compile Include="Utils\BitwiseHelper.cs" />
-    <Compile Include="Utils\MathHelper.cs" />
-  </ItemGroup>
-  <ItemGroup>
-    <Content Include="Overview.html" />
-    <Content Include="Tier\Package.html" />
+    <Compile Include="SimpleSpatialFieldInfo.cs" />
+    <Compile Include="SpatialFieldInfo.cs" />
+    <Compile Include="SpatialStrategy.cs" />
+    <Compile Include="Util\Bits.cs" />
+    <Compile Include="Util\CachedDistanceValueSource.cs" />
+    <Compile Include="Util\CachingDoubleValueSource.cs" />
+    <Compile Include="Util\CompatibilityExtensions.cs" />
+    <Compile Include="Util\FixedBitSet.cs" />
+    <Compile Include="Util\FunctionQuery.cs" />
+    <Compile Include="Util\NumericFieldInfo.cs" />
+    <Compile Include="Util\OpenBitSetIterator.cs" />
+    <Compile Include="Util\ShapeFieldCache.cs" />
+    <Compile Include="Util\ShapeFieldCacheProvider.cs" />
+    <Compile Include="Util\StringListTokenizer.cs" />
+    <Compile Include="Util\TermsEnumCompatibility.cs" />
+    <Compile Include="Util\TruncateFilter.cs" />
+    <Compile Include="Util\ValueSourceFilter.cs" />
+    <Compile Include="Vector\DistanceValueSource.cs" />
+    <Compile Include="Vector\TwoDoublesFieldInfo.cs" />
+    <Compile Include="Vector\TwoDoublesStrategy.cs" />
   </ItemGroup>
   <ItemGroup>
     <ProjectReference Include="..\..\core\Lucene.Net.csproj">
@@ -152,6 +154,7 @@
   <ItemGroup>
     <None Include="Lucene.Net.snk" />
   </ItemGroup>
+  <ItemGroup />
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
        Other similar extension points exist, see Microsoft.Common.targets.
@@ -160,4 +163,4 @@
   <Target Name="AfterBuild">
   </Target>
   -->
-</Project>
\ No newline at end of file
+</Project>

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PointPrefixTreeFieldCacheProvider.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,45 @@
+/*
+ * 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.Spatial.Prefix.Tree;
+using Lucene.Net.Spatial.Util;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+	public class PointPrefixTreeFieldCacheProvider : ShapeFieldCacheProvider<Point>
+	{
+		readonly SpatialPrefixTree grid; //
+
+		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;
+
+		protected override Point ReadShape(Term term)
+		{
+			scanCell = grid.GetNode(term.Text, scanCell);
+			return scanCell.IsLeaf() ? scanCell.GetShape().GetCenter() : null;
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixCellsTokenizer.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixCellsTokenizer.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixCellsTokenizer.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixCellsTokenizer.cs Wed May 30 10:17:16 2012
@@ -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.
+ */
+
+using Lucene.Net.Analysis;
+using Lucene.Net.Analysis.Tokenattributes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+	public class PrefixCellsTokenizer : Tokenizer
+	{
+		private readonly TermAttribute termAtt;
+
+		public PrefixCellsTokenizer()
+		{
+			termAtt = AddAttribute<TermAttribute>();
+		}
+
+		public override bool IncrementToken()
+		{
+			ClearAttributes();
+			int length = 0;
+			char[] buffer = termAtt.TermBuffer();
+			while (true)
+			{
+				char c = (char)input.Read();
+				if (c < 0) break;
+				if (c == 'a' || c == 'A')
+				{
+					buffer[length++] = 'A';
+					continue;
+				}
+				if (c == 'b' || c == 'B')
+				{
+					buffer[length++] = 'B';
+					continue;
+				}
+				if (c == 'c' || c == 'C')
+				{
+					buffer[length++] = 'C';
+					continue;
+				}
+				if (c == 'd' || c == 'D')
+				{
+					buffer[length++] = 'D';
+					continue;
+				}
+				if (c == '*')
+				{
+					buffer[length++] = '*';
+					continue;
+				}
+				if (c == '+')
+				{
+					buffer[length++] = '+';
+					continue;
+				}
+
+				if (length > 0)
+				{
+					// Skip any other character
+					break;
+				}
+			}
+
+			termAtt.SetTermLength(length);
+			return length > 0; // should only happen at the end
+		}
+
+		public override void End()
+		{
+		}
+
+		public override void Reset(System.IO.TextReader input)
+		{
+			base.Reset(input);
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixTreeStrategy.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixTreeStrategy.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixTreeStrategy.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/PrefixTreeStrategy.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,201 @@
+/*
+ * 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.Concurrent;
+using System.Collections.Generic;
+using Lucene.Net.Analysis;
+using Lucene.Net.Analysis.Tokenattributes;
+using Lucene.Net.Documents;
+using Lucene.Net.Search.Function;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Spatial.Util;
+using Spatial4n.Core.Distance;
+using Spatial4n.Core.Query;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+	public abstract class PrefixTreeStrategy : SpatialStrategy<SimpleSpatialFieldInfo>
+	{
+		protected readonly SpatialPrefixTree grid;
+		private readonly IDictionary<String, PointPrefixTreeFieldCacheProvider> provider = new ConcurrentDictionary<string, PointPrefixTreeFieldCacheProvider>();
+		protected int defaultFieldValuesArrayLen = 2;
+		protected double distErrPct = SpatialArgs.DEFAULT_DIST_PRECISION;
+
+		protected PrefixTreeStrategy(SpatialPrefixTree grid)
+			: base(grid.GetSpatialContext())
+		{
+			this.grid = grid;
+		}
+
+		/** Used in the in-memory ValueSource as a default ArrayList length for this field's array of values, per doc. */
+		public void SetDefaultFieldValuesArrayLen(int defaultFieldValuesArrayLen)
+		{
+			this.defaultFieldValuesArrayLen = defaultFieldValuesArrayLen;
+		}
+
+		/** See {@link SpatialPrefixTree#getMaxLevelForPrecision(com.spatial4j.core.shape.Shape, double)}. */
+		public void SetDistErrPct(double distErrPct)
+		{
+			this.distErrPct = distErrPct;
+		}
+
+		public override Field CreateField(SimpleSpatialFieldInfo fieldInfo, Shape shape, bool index, bool store)
+		{
+			int detailLevel = grid.GetMaxLevelForPrecision(shape, distErrPct);
+			var cells = grid.GetNodes(shape, detailLevel, true);//true=intermediates cells
+			//If shape isn't a point, add a full-resolution center-point so that
+			// PrefixFieldCacheProvider has the center-points.
+			// TODO index each center of a multi-point? Yes/no?
+			if (!(shape is Point))
+			{
+				Point ctr = shape.GetCenter();
+				//TODO should be smarter; don't index 2 tokens for this in CellTokenizer. Harmless though.
+				cells.Add(grid.GetNodes(ctr, grid.GetMaxLevels(), false)[0]);
+			}
+
+			var fname = fieldInfo.GetFieldName();
+			if (store)
+			{
+				//TODO figure out how to re-use original string instead of reconstituting it.
+				var wkt = grid.GetSpatialContext().ToString(shape);
+				if (index)
+				{
+					var f = new Field(fname, wkt, Field.Store.YES, Field.Index.ANALYZED); // TYPE_STORED is indexed, stored and tokenized
+					f.OmitNorms = true;
+					f.SetTokenStream(new CellTokenStream(cells.GetEnumerator()));
+					return f;
+				}
+				return new Field(fname, wkt, Field.Store.YES, Field.Index.NOT_ANALYZED_NO_NORMS); // StoredField is only stored
+			}
+
+			if (index)
+			{
+				// TYPE_UNSTORED is indexed and tokenized but not stored, and this is what this ctor returns
+				var f = new Field(fname, new CellTokenStream(cells.GetEnumerator()), Field.TermVector.NO);
+				f.OmitNorms = true;
+				return f;
+			}
+
+			throw new InvalidOperationException("Fields need to be indexed or store [" + fname + "]");
+		}
+
+		///* Indexed, tokenized, not stored. */
+		//public static final FieldType TYPE_UNSTORED = new FieldType();
+
+		///* Indexed, tokenized, stored. */
+		//public static final FieldType TYPE_STORED = new FieldType();
+
+		//static {
+		//  TYPE_UNSTORED.setIndexed(true);
+		//  TYPE_UNSTORED.setTokenized(true);
+		//  TYPE_UNSTORED.setOmitNorms(true);
+		//  TYPE_UNSTORED.freeze();
+
+		//  TYPE_STORED.setStored(true);
+		//  TYPE_STORED.setIndexed(true);
+		//  TYPE_STORED.setTokenized(true);
+		//  TYPE_STORED.setOmitNorms(true);
+		//  TYPE_STORED.freeze();
+		//}
+
+
+		/// <summary>
+		/// Outputs the tokenString of a cell, and if its a leaf, outputs it again with the leaf byte.
+		/// </summary>
+		protected class CellTokenStream : TokenStream
+		{
+			private ITermAttribute termAtt;
+			private readonly IEnumerator<Node> iter;
+
+			public CellTokenStream(IEnumerator<Node> tokens)
+			{
+				this.iter = tokens;
+				Init();
+			}
+
+			private void Init()
+			{
+				termAtt = AddAttribute<ITermAttribute>();
+			}
+
+			private string nextTokenStringNeedingLeaf;
+
+			public override bool IncrementToken()
+			{
+				ClearAttributes();
+				if (nextTokenStringNeedingLeaf != null)
+				{
+					termAtt.Append(nextTokenStringNeedingLeaf);
+					termAtt.Append((char)Node.LEAF_BYTE);
+					nextTokenStringNeedingLeaf = null;
+					return true;
+				}
+				if (iter.MoveNext())
+				{
+					Node cell = iter.Current;
+					var token = cell.GetTokenString();
+					termAtt.Append(token);
+					if (cell.IsLeaf())
+						nextTokenStringNeedingLeaf = token;
+					return true;
+				}
+				return false;
+			}
+
+			protected override void Dispose(bool disposing)
+			{
+			}
+		}
+
+		public override ValueSource MakeValueSource(SpatialArgs args, SimpleSpatialFieldInfo fieldInfo)
+		{
+			var calc = grid.GetSpatialContext().GetDistCalc();
+			return MakeValueSource(args, fieldInfo, calc);
+		}
+
+		public ShapeFieldCacheProvider<Point> GetCacheProvider(SimpleSpatialFieldInfo fieldInfo)
+		{
+			PointPrefixTreeFieldCacheProvider p;
+			if (!provider.TryGetValue(fieldInfo.GetFieldName(), out p) || p == null)
+			{
+				lock (this)
+				{//double checked locking idiom is okay since provider is threadsafe
+					if (!provider.ContainsKey(fieldInfo.GetFieldName()))
+					{
+						p = new PointPrefixTreeFieldCacheProvider(grid, fieldInfo.GetFieldName(), defaultFieldValuesArrayLen);
+						provider[fieldInfo.GetFieldName()] = p;
+					}
+				}
+			}
+			return p;
+		}
+
+		public ValueSource MakeValueSource(SpatialArgs args, SimpleSpatialFieldInfo fieldInfo, DistanceCalculator calc)
+		{
+			PointPrefixTreeFieldCacheProvider p = (PointPrefixTreeFieldCacheProvider)GetCacheProvider(fieldInfo);
+			Point point = args.GetShape().GetCenter();
+			return new CachedDistanceValueSource(point, calc, p);
+		}
+
+		public SpatialPrefixTree GetGrid()
+		{
+			return grid;
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeFilter.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeFilter.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeFilter.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeFilter.cs Wed May 30 10:17:16 2012
@@ -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, grid.GetSpatialContext()) == 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;
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeStrategy.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeStrategy.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeStrategy.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/RecursivePrefixTreeStrategy.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,69 @@
+/*
+ * 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.Search.Function;
+using Lucene.Net.Spatial.Prefix.Tree;
+using Lucene.Net.Spatial.Util;
+using Spatial4n.Core.Exceptions;
+using Spatial4n.Core.Query;
+using Spatial4n.Core.Shapes;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+	public class RecursivePrefixTreeStrategy : PrefixTreeStrategy
+	{
+		private int prefixGridScanLevel;//TODO how is this customized?
+
+		public RecursivePrefixTreeStrategy(SpatialPrefixTree grid)
+			: base(grid)
+		{
+			prefixGridScanLevel = grid.GetMaxLevels() - 4;//TODO this default constant is dependent on the prefix grid size
+		}
+
+		public void SetPrefixGridScanLevel(int prefixGridScanLevel)
+		{
+			this.prefixGridScanLevel = prefixGridScanLevel;
+		}
+
+		public override Query MakeQuery(SpatialArgs args, SimpleSpatialFieldInfo fieldInfo)
+		{
+			Filter f = MakeFilter(args, fieldInfo);
+
+			ValueSource vs = MakeValueSource(args, fieldInfo);
+			return new FilteredQuery(new FunctionQuery(vs), f);
+		}
+
+		public override Filter MakeFilter(SpatialArgs args, SimpleSpatialFieldInfo fieldInfo)
+		{
+			var op = args.Operation;
+			if (!SpatialOperation.Is(op, SpatialOperation.IsWithin, SpatialOperation.Intersects, SpatialOperation.BBoxWithin))
+				throw new UnsupportedSpatialOperation(op);
+
+			Shape qshape = args.GetShape();
+
+			int detailLevel = grid.GetMaxLevelForPrecision(qshape, args.GetDistPrecision());
+
+			return new RecursivePrefixTreeFilter(fieldInfo.GetFieldName(), grid, qshape, prefixGridScanLevel, detailLevel);
+		}
+
+		public override string ToString()
+		{
+			return GetType().Name + "(prefixGridScanLevel:" + prefixGridScanLevel + ",SPG:(" + grid + "))";
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/TermQueryPrefixTreeStrategy.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/TermQueryPrefixTreeStrategy.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/TermQueryPrefixTreeStrategy.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/TermQueryPrefixTreeStrategy.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,59 @@
+/*
+ * 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 Spatial4n.Core.Exceptions;
+using Spatial4n.Core.Query;
+
+namespace Lucene.Net.Spatial.Prefix
+{
+	public class TermQueryPrefixTreeStrategy : PrefixTreeStrategy
+	{
+		public TermQueryPrefixTreeStrategy(SpatialPrefixTree grid)
+			: base(grid)
+		{
+		}
+
+		public override Query MakeQuery(SpatialArgs args, SimpleSpatialFieldInfo fieldInfo)
+		{
+			if (args.Operation != SpatialOperation.Intersects &&
+				args.Operation != SpatialOperation.IsWithin &&
+				args.Operation != SpatialOperation.Overlaps)
+			{
+				// TODO -- can translate these other query types
+				throw new UnsupportedSpatialOperation(args.Operation);
+			}
+			var qshape = args.GetShape();
+			int detailLevel = grid.GetMaxLevelForPrecision(qshape, args.GetDistPrecision());
+			var cells = grid.GetNodes(qshape, detailLevel, false);
+
+			var booleanQuery = new BooleanQuery();
+			foreach (var cell in cells)
+			{
+				booleanQuery.Add(new TermQuery(new Term(fieldInfo.GetFieldName(), cell.GetTokenString())), Occur.SHOULD);
+			}
+			return booleanQuery;
+		}
+
+		public override Filter MakeFilter(SpatialArgs args, SimpleSpatialFieldInfo fieldInfo)
+		{
+			return new QueryWrapperFilter(MakeQuery(args, fieldInfo));
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/GeohashPrefixTree.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/GeohashPrefixTree.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/GeohashPrefixTree.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/GeohashPrefixTree.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,153 @@
+/*
+ * 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
+	{
+		public class Factory : SpatialPrefixTreeFactory
+		{
+			protected override int GetLevelForDistance(double degrees)
+			{
+				var grid = new GeohashPrefixTree(ctx, GeohashPrefixTree.GetMaxLevelsPossible());
+				return grid.GetLevelForDistance(degrees) + 1;//returns 1 greater
+			}
+
+			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 & lon are the same).
+		/// </summary>
+		/// <returns></returns>
+		public static int GetMaxLevelsPossible()
+		{
+			return GeohashUtils.MAX_PRECISION;
+		}
+
+		public override int GetLevelForDistance(double dist)
+		{
+			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
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/Node.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/Node.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/Node.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/Node.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,217 @@
+/*
+ * 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)
+			{
+				return new ReadOnlyCollectionBuilder<Node>(new[] {GetSubCell(point)}).ToReadOnlyCollection();
+			}
+
+			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)
+			{
+				var rel = cell.GetShape().Relate(shapeFilter, spatialPrefixTree.ctx);
+				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);
+		}
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/QuadPrefixTree.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/QuadPrefixTree.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/QuadPrefixTree.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/QuadPrefixTree.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,329 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+using System;
+using System.Collections.Generic;
+using System.Collections.ObjectModel;
+using System.Diagnostics;
+using System.Text;
+using Spatial4n.Core.Context;
+using Spatial4n.Core.Shapes;
+using Spatial4n.Core.Shapes.Impl;
+
+namespace Lucene.Net.Spatial.Prefix.Tree
+{
+	public class QuadPrefixTree : SpatialPrefixTree
+	{
+		public class Factory : SpatialPrefixTreeFactory
+		{
+
+			protected override int GetLevelForDistance(double degrees)
+			{
+				var grid = new QuadPrefixTree(ctx, MAX_LEVELS_POSSIBLE);
+				return grid.GetLevelForDistance(degrees) + 1; //returns 1 greater
+			}
+
+			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 void PrintInfo() {
+		//  NumberFormat nf = NumberFormat.getNumberInstance();
+		//  nf.setMaximumFractionDigits(5);
+		//  nf.setMinimumFractionDigits(5);
+		//  nf.setMinimumIntegerDigits(3);
+
+		//  for (int i = 0; i < maxLevels; i++) {
+		//    System.out.println(i + "]\t" + nf.format(levelW[i]) + "\t" + nf.format(levelH[i]) + "\t" +
+		//        levelS[i] + "\t" + (levelS[i] * levelS[i]));
+		//  }
+		//}
+
+		public override int GetLevelForDistance(double dist)
+		{
+			for (int i = 1; i < maxLevels; i++)
+			{
+				//note: level[i] is actually a lookup for level i+1
+				if (dist > levelW[i] || dist > levelH[i])
+				{
+					return i;
+				}
+			}
+			return maxLevels;
+		}
+
+		protected override Node GetNode(Point p, int level)
+		{
+			var cells = new List<Node>(1);
+			Build(xmid, ymid, 0, cells, new StringBuilder(), new PointImpl(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.MakeRect(cx - w, cx + w, cy - h, cy + h);
+			SpatialRelation v = shape.Relate(rectangle, ctx);
+			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 tree.ctx.MakeRect(xmin, xmin + width, ymin, ymin + height);
+			}
+		}//QuadCell
+
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTree.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTree.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTree.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTree.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,297 @@
+/*
+ * 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 + ")";
+		}
+
+		/**
+		 * See {@link com.spatial4j.core.query.SpatialArgs#getDistPrecision()}.
+		 * A grid level looked up via {@link #getLevelForDistance(double)} is returned.
+		 *
+		 * @param shape
+		 * @param precision 0-0.5
+		 * @return 1-maxLevels
+		 */
+		public int GetMaxLevelForPrecision(Shape shape, double precision)
+		{
+			if (precision < 0 || precision > 0.5)
+			{
+				throw new ArgumentException("Precision " + precision + " must be between [0-0.5]", "precision");
+			}
+			if (precision == 0 || shape is Point)
+			{
+				return maxLevels;
+			}
+			double bboxArea = shape.GetBoundingBox().GetArea();
+			if (bboxArea == 0)
+			{
+				return maxLevels;
+			}
+			double avgSideLenFromCenter = Math.Sqrt(bboxArea) / 2;
+			return GetLevelForDistance(avgSideLenFromCenter * precision);
+		}
+
+		/**
+		 * Returns the level of the smallest grid size with a side length that is greater or equal to the provided
+		 * distance.
+		 *
+		 * @param dist >= 0
+		 * @return level [1-maxLevels]
+		 */
+		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)
+			{
+				return new ReadOnlyCollectionBuilder<Node>(new[] { cell }).ToReadOnlyCollection();
+			}
+
+			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;
+		}
+
+	}
+}

Added: incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs?rev=1344182&view=auto
==============================================================================
--- incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs (added)
+++ incubator/lucene.net/trunk/src/contrib/Spatial/Prefix/Tree/SpatialPrefixTreeFactory.cs Wed May 30 10:17:16 2012
@@ -0,0 +1,97 @@
+/*
+ * 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
+{
+	public abstract class SpatialPrefixTreeFactory
+	{
+		private const double DEFAULT_GEO_MAX_DETAIL_KM = 0.001; //1m
+
+		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("prefixTree", 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("maxLevels", out mlStr) && mlStr != null)
+			{
+				maxLevels = int.Parse(mlStr);
+				return;
+			}
+
+			double degrees;
+			if (!args.TryGetValue("maxDetailDist", out mlStr) || mlStr == null)
+			{
+				if (!ctx.IsGeo())
+				{
+					return; //let default to max
+				}
+				degrees = DistanceUtils.Dist2Degrees(DEFAULT_GEO_MAX_DETAIL_KM, DistanceUnits.KILOMETERS.EarthRadius());
+			}
+			else
+			{
+				degrees = DistanceUtils.Dist2Degrees(double.Parse(mlStr), ctx.GetUnits().EarthRadius());
+			}
+			maxLevels = GetLevelForDistance(degrees) + 1; //returns 1 greater
+		}
+
+		/** Calls {@link SpatialPrefixTree#getLevelForDistance(double)}. */
+		protected abstract int GetLevelForDistance(double degrees);
+
+		protected abstract SpatialPrefixTree NewSPT();
+
+	}
+}



Mime
View raw message