[mkgmap-splitter] 01/06: New upstream version 0.0.0+svn583
Bas Couwenberg
sebastic at debian.org
Sat Jul 1 12:18:30 UTC 2017
This is an automated email from the git hooks/post-receive script.
sebastic pushed a commit to branch master
in repository mkgmap-splitter.
commit 9721c6ea106049728afc6d8abf968450492757ca
Author: Bas Couwenberg <sebastic at xs4all.nl>
Date: Sat Jul 1 13:58:51 2017 +0200
New upstream version 0.0.0+svn583
---
.classpath | 9 +
.idea/ant.xml | 7 -
.idea/inspectionProfiles/Project_Default.xml | 25 +-
.idea/libraries/libs.xml | 10 -
.idea/libraries/mkgmap.xml | 11 -
.idea/misc.xml | 40 +-
.project | 18 +
build.xml | 86 +-
doc/splitter.1 | 4 +-
doc/splitter.1.xml | 4 +-
doc/splitter.txt | 4 +-
ivy.xml | 6 +-
resources/splitter-version.properties | 4 +-
splitter.iml | 69 +-
src/uk/me/parabola/splitter/Area.java | 8 +-
src/uk/me/parabola/splitter/AreaList.java | 34 +-
src/uk/me/parabola/splitter/Main.java | 15 +-
.../me/parabola/splitter/MultiTileProcessor.java | 8 +-
.../me/parabola/splitter/ProblemListProcessor.java | 2 +-
src/uk/me/parabola/splitter/ProblemLists.java | 7 +-
.../me/parabola/splitter/parser/O5mMapParser.java | 8 +-
src/uk/me/parabola/splitter/tools/BitReader.java | 147 ++++
src/uk/me/parabola/splitter/tools/BitWriter.java | 198 +++++
.../parabola/splitter/tools/Long2IntClosedMap.java | 52 +-
.../parabola/splitter/tools/SparseLong2IntMap.java | 927 +++++++++++++--------
.../parabola/splitter/writer/BinaryMapWriter.java | 12 +-
.../me/parabola/splitter/writer/O5mMapWriter.java | 81 +-
test/func/ArgsTest.java | 35 +
test/func/Base.java | 46 +
test/func/SolverAndProblemGeneratorTest.java | 102 +++
test/func/lib/Args.java | 78 ++
test/func/lib/Outputs.java | 85 ++
test/func/lib/TestUtils.java | 134 +++
test/func/package.html | 5 +
.../{TestAreaSet.java => AreaSetTest.java} | 26 +-
.../{TestConvert.java => ConvertTest.java} | 27 +-
.../{TestRounding.java => RoundingTest.java} | 45 +-
.../{TestCityFinder.java => CityFinderTest.java} | 29 +-
...Collections.java => CustomCollectionsTest.java} | 156 ++--
...TestSparseBitSet.java => SparseBitSetTest.java} | 25 +-
.../me/parabola/splitter/tools/TestBitReader.java | 181 ++++
41 files changed, 2058 insertions(+), 712 deletions(-)
diff --git a/.classpath b/.classpath
new file mode 100644
index 0000000..c22db17
--- /dev/null
+++ b/.classpath
@@ -0,0 +1,9 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+ <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
+ <classpathentry kind="src" path="src"/>
+ <classpathentry kind="src" path="test"/>
+ <classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
+ <classpathentry kind="con" path="org.apache.ivyde.eclipse.cpcontainer.IVYDE_CONTAINER/?project=mkgmap&ivyXmlPath=ivy.xml&confs=*"/>
+ <classpathentry kind="output" path="bin"/>
+</classpath>
diff --git a/.idea/ant.xml b/.idea/ant.xml
deleted file mode 100644
index 2581ca3..0000000
--- a/.idea/ant.xml
+++ /dev/null
@@ -1,7 +0,0 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<project version="4">
- <component name="AntConfiguration">
- <defaultAnt bundledAnt="true" />
- </component>
-</project>
-
diff --git a/.idea/inspectionProfiles/Project_Default.xml b/.idea/inspectionProfiles/Project_Default.xml
index 6591a36..66fc030 100644
--- a/.idea/inspectionProfiles/Project_Default.xml
+++ b/.idea/inspectionProfiles/Project_Default.xml
@@ -1,7 +1,6 @@
<component name="InspectionProjectProfileManager">
- <profile version="1.0" is_locked="false">
+ <profile version="1.0">
<option name="myName" value="Project Default" />
- <option name="myLocal" value="false" />
<inspection_tool class="AbstractMethodCallInConstructor" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="AbstractMethodOverridesAbstractMethod" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="AssignmentToCatchBlockParameter" enabled="true" level="WARNING" enabled_by_default="true" />
@@ -15,6 +14,9 @@
<inspection_tool class="AutoUnboxing" enabled="false" level="INFO" enabled_by_default="false" />
<inspection_tool class="BadExceptionThrown" enabled="true" level="WARNING" enabled_by_default="true">
<option name="exceptionsString" value="java.lang.Throwable,java.lang.Exception,java.lang.Error,java.lang.RuntimeException,java.lang.NullPointerException,java.lang.ClassCastException,java.lang.ArrayIndexOutOfBoundsException" />
+ <option name="exceptions">
+ <value />
+ </option>
</inspection_tool>
<inspection_tool class="CStyleArrayDeclaration" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="CatchGenericClass" enabled="true" level="WARNING" enabled_by_default="true" />
@@ -26,7 +28,14 @@
</inspection_tool>
<inspection_tool class="ComparisonOfShortAndChar" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="ConfusingOctalEscape" enabled="true" level="WARNING" enabled_by_default="true" />
- <inspection_tool class="EmptyClass" enabled="true" level="WARNING" enabled_by_default="true" />
+ <inspection_tool class="EmptyClass" enabled="true" level="WARNING" enabled_by_default="true">
+ <option name="ignorableAnnotations">
+ <value />
+ </option>
+ <option name="ignoreClassWithParameterization" value="false" />
+ <option name="ignoreThrowables" value="true" />
+ <option name="commentsAreContent" value="true" />
+ </inspection_tool>
<inspection_tool class="ErrorRethrown" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="FallthruInSwitchStatement" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="ForLoopReplaceableByWhile" enabled="true" level="WARNING" enabled_by_default="true">
@@ -73,6 +82,7 @@
</inspection_tool>
<inspection_tool class="NegatedIfElse" enabled="true" level="WARNING" enabled_by_default="true">
<option name="m_ignoreNegatedNullComparison" value="true" />
+ <option name="m_ignoreNegatedZeroComparison" value="false" />
</inspection_tool>
<inspection_tool class="ObsoleteCollection" enabled="true" level="WARNING" enabled_by_default="true">
<option name="ignoreRequiredObsoleteCollectionTypes" value="false" />
@@ -80,6 +90,9 @@
<inspection_tool class="OverridableMethodCallDuringObjectConstruction" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="PublicField" enabled="true" level="WARNING" enabled_by_default="true">
<option name="ignoreEnums" value="false" />
+ <option name="ignorableAnnotations">
+ <value />
+ </option>
</inspection_tool>
<inspection_tool class="RedundantFieldInitialization" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="RedundantImport" enabled="true" level="WARNING" enabled_by_default="true" />
@@ -90,9 +103,7 @@
<inspection_tool class="ResultOfObjectAllocationIgnored" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="SamePackageImport" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="SameReturnValue" enabled="false" level="WARNING" enabled_by_default="false" />
- <inspection_tool class="SizeReplaceableByIsEmpty" enabled="true" level="WARNING" enabled_by_default="true">
- <option name="ignoreNegations" value="false" />
- </inspection_tool>
+ <inspection_tool class="SizeReplaceableByIsEmpty" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="SpellCheckingInspection" enabled="true" level="TYPO" enabled_by_default="true">
<option name="processCode" value="false" />
<option name="processLiterals" value="false" />
@@ -102,9 +113,7 @@
<option name="m_ignoreWeakCollections" value="false" />
</inspection_tool>
<inspection_tool class="StringBufferField" enabled="true" level="WARNING" enabled_by_default="true" />
- <inspection_tool class="StringBufferReplaceableByString" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="StringEqualsEmptyString" enabled="true" level="WARNING" enabled_by_default="true" />
- <inspection_tool class="SubstringZero" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="SubtractionInCompareTo" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="SystemGC" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="TextLabelInSwitchStatement" enabled="true" level="WARNING" enabled_by_default="true" />
diff --git a/.idea/libraries/libs.xml b/.idea/libraries/libs.xml
deleted file mode 100644
index b030af1..0000000
--- a/.idea/libraries/libs.xml
+++ /dev/null
@@ -1,10 +0,0 @@
-<component name="libraryTable">
- <library name="libs">
- <CLASSES>
- <root url="file://$PROJECT_DIR$/lib" />
- </CLASSES>
- <JAVADOC />
- <SOURCES />
- <jarDirectory url="file://$PROJECT_DIR$/lib" recursive="false" />
- </library>
-</component>
\ No newline at end of file
diff --git a/.idea/libraries/mkgmap.xml b/.idea/libraries/mkgmap.xml
deleted file mode 100644
index 781a3f1..0000000
--- a/.idea/libraries/mkgmap.xml
+++ /dev/null
@@ -1,11 +0,0 @@
-<component name="libraryTable">
- <library name="mkgmap">
- <CLASSES>
- <root url="file://$PROJECT_DIR$/../mkgmap/build/classes" />
- </CLASSES>
- <JAVADOC />
- <SOURCES>
- <root url="file://$PROJECT_DIR$/../mkgmap/src" />
- </SOURCES>
- </library>
-</component>
\ No newline at end of file
diff --git a/.idea/misc.xml b/.idea/misc.xml
index 44bc717..dbcfb86 100644
--- a/.idea/misc.xml
+++ b/.idea/misc.xml
@@ -1,12 +1,16 @@
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
- <component name="DependencyValidationManager">
- <option name="SKIP_IMPORT_STATEMENTS" value="false" />
- </component>
- <component name="EntryPointsManager">
- <entry_points version="2.0" />
- </component>
<component name="IdProvider" IDEtalkID="4895EF755ED348E86177D69FBFDA6A74" />
+ <component name="IvyIDEA.ProjectSettings">
+ <option name="artifactTypeSettings">
+ <ArtifactTypeSettings>
+ <option name="classesTypes" value="jar, mar, sar, war, ear, ejb, bundle, test-jar" />
+ <option name="javadocTypes" value="javadoc, doc, docs, apidoc, apidocs, documentation, documents" />
+ <option name="sourcesTypes" value="source, src, sources, srcs" />
+ </ArtifactTypeSettings>
+ </option>
+ <option name="ivySettingsFile" value="$PROJECT_DIR$/ivysettings.xml" />
+ </component>
<component name="JavadocGenerationManager">
<option name="OUTPUT_DIRECTORY" />
<option name="OPTION_SCOPE" value="protected" />
@@ -33,7 +37,7 @@
<component name="ProjectResources">
<default-html-doctype>http://www.w3.org/1999/xhtml</default-html-doctype>
</component>
- <component name="ProjectRootManager" version="2" languageLevel="JDK_1_6" assert-keyword="true" jdk-15="true" project-jdk-name="1.6" project-jdk-type="JavaSDK">
+ <component name="ProjectRootManager" version="2" languageLevel="JDK_1_8" default="false" project-jdk-name="1.8" project-jdk-type="JavaSDK">
<output url="file://$PROJECT_DIR$/build" />
</component>
<component name="SvnBranchConfigurationManager">
@@ -42,25 +46,6 @@
<entry key="$PROJECT_DIR$">
<value>
<SvnBranchConfiguration>
- <option name="branchMap">
- <map>
- <entry key="https://svn.parabola.me.uk/svn/splitter/branches">
- <value>
- <list />
- </value>
- </entry>
- <entry key="https://svn.parabola.me.uk/svn/splitter/releases">
- <value>
- <list />
- </value>
- </entry>
- <entry key="https://svn.parabola.me.uk/svn/splitter/tags">
- <value>
- <list />
- </value>
- </entry>
- </map>
- </option>
<option name="branchUrls">
<list>
<option value="https://svn.parabola.me.uk/svn/splitter/branches" />
@@ -77,5 +62,4 @@
<option name="myVersion" value="124" />
<option name="mySupportsUserInfoFilter" value="true" />
</component>
-</project>
-
+</project>
\ No newline at end of file
diff --git a/.project b/.project
new file mode 100644
index 0000000..10bd49f
--- /dev/null
+++ b/.project
@@ -0,0 +1,18 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+ <name>splitter</name>
+ <comment></comment>
+ <projects>
+ </projects>
+ <buildSpec>
+ <buildCommand>
+ <name>org.eclipse.jdt.core.javabuilder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ </buildSpec>
+ <natures>
+ <nature>org.eclipse.jdt.core.javanature</nature>
+ <nature>org.apache.ivyde.eclipse.ivynature</nature>
+ </natures>
+</projectDescription>
diff --git a/build.xml b/build.xml
index 85a0118..66ac125 100644
--- a/build.xml
+++ b/build.xml
@@ -60,6 +60,14 @@
<property name="ivy.retrieve.pattern" value="${ivy.lib.dir}/[conf]/[artifact]-[revision].[ext]" />
<property name="ivy.distrib.dir" value="ivy-distrib" />
+ <!-- A place to keep a local copy of the test input data. The test files
+ are large and so are not kept in svn. If you don't set this then they
+ will be downloaded.
+
+ You can set it in the external.properties file too.
+ -->
+ <property name="test.input.cache" value="/opt/data/testinput"/>
+
<!-- Classpaths -->
<path id="classpath">
<pathelement location="${build.classes}"/>
@@ -226,16 +234,32 @@
</javadoc>
</target>
- <target name="run.tests" depends="compile.tests">
- <!-- Run the java unit tests -->
- <taskdef resource="testngtasks" classpathref="test.classpath"/>
- <testng classpathref="test.classpath" outputdir="${build.test-output}" haltonfailure="true">
- <classfileset dir="${build.test-classes}">
- <include name="**/*.class"/>
- </classfileset>
- </testng>
- </target>
-
+ <target name="run.tests" depends="compile.tests" description="Run the junit tests">
+ <mkdir dir="tmp/report"/>
+ <junit printsummary="yes" failureproperty="junit.failure" forkmode="once">
+
+ <classpath refid="test.classpath"/>
+ <formatter type="xml"/>
+
+ <assertions>
+ <enable/>
+ </assertions>
+
+ <batchtest fork="yes" todir="tmp/report">
+ <fileset dir="test">
+ <include name="**/*Test.java"/>
+
+ <!-- These are standalone tests, not unit tests. -->
+ <exclude name="func/**"/>
+ </fileset>
+ </batchtest>
+ </junit>
+ <junitreport todir="tmp">
+ <fileset dir="tmp/report"/>
+ <report todir="test-reports"/>
+ </junitreport>
+ <fail if="junit.failure" message="Test failed. See test-reports/index.html"/>
+ </target>
<target name="dist" depends="build, check-version, version-file" description="Make the distribution area">
@@ -309,5 +333,47 @@
</target>
<target name="rebuild" depends="clean, build"/>
+
+ <target name="obtain-test-input-files" description="download the input files for the functional tests">
+ <!-- Local cache, if it doesn't exist then it is not a problem the files
+ will be downloaded in the next step -->
+ <copy todir="test/resources/in/" failonerror="false">
+ <fileset dir="${test.input.cache}" includes="osm/*.osm.pbf" />
+ </copy>
+ <mkdir dir="test/resources/in/osm"/>
+ <get src="http://www.mkgmap.org.uk/testinput/osm/alaska-2016-12-27.osm.pbf"
+ dest="test/resources/in/osm/alaska-2016-12-27.osm.pbf" usetimestamp="true"
+ ignoreerrors="true"/>
+ <get src="http://www.mkgmap.org.uk/testinput/osm/hamburg-2016-12-26.osm.pbf"
+ dest="test/resources/in/osm/hamburg-2016-12-26.osm.pbf" usetimestamp="true"
+ ignoreerrors="true"/>
+ </target>
+
+ <target name="run.func-tests" depends="compile,compile.tests,obtain-test-input-files" description="Run the functional tests">
+ <mkdir dir="tmp/report"/>
+ <junit printsummary="yes" failureproperty="junit.failure" forkmode="once">
+
+ <classpath refid="test.classpath"/>
+ <formatter type="xml"/>
+
+ <assertions>
+ <enable/>
+ </assertions>
+
+ <batchtest fork="yes" todir="tmp/report">
+ <fileset dir="test">
+ <include name="func/**/*Test.java"/>
+
+ <!-- These are standalone tests, not unit tests. -->
+ <exclude name="main/**"/>
+ </fileset>
+ </batchtest>
+ </junit>
+ <junitreport todir="tmp">
+ <fileset dir="tmp/report"/>
+ <report todir="test-reports"/>
+ </junitreport>
+ <fail if="junit.failure" message="Test failed. See test-reports/index.html"/>
+ </target>
</project>
diff --git a/doc/splitter.1 b/doc/splitter.1
index e64d064..bb31e8c 100644
--- a/doc/splitter.1
+++ b/doc/splitter.1
@@ -166,7 +166,7 @@ Default: 63240001
\*(T<\fB\-\-max\-areas=\fR\*(T>\fIint\fR
The maximum number of areas that can be processed in a single pass
during the second stage of processing.
-This must be a number from 1 to 4096.
+This must be a number from 1 to 9999.
Higher numbers mean fewer passes over the source file and hence
quicker overall processing, but also require more memory.
If you find you are running out of memory but don't want to
@@ -180,7 +180,7 @@ out of memory before the \*(T<\fIareas.list\fR\*(T> file is
generated, you need to either increase your \*(T<\fB\-Xmx\fR\*(T>
value or reduce the size of the input file you're trying to split.
-Default: 512
+Default: 2048
.TP
\*(T<\fB\-\-max\-nodes=\fR\*(T>\fIint\fR
The maximum number of nodes that can be in any of the resultant
diff --git a/doc/splitter.1.xml b/doc/splitter.1.xml
index a093a47..03acf9c 100644
--- a/doc/splitter.1.xml
+++ b/doc/splitter.1.xml
@@ -237,7 +237,7 @@ JAVA_OPTS="<replaceable>-Xmx512m</replaceable>" <command>mkgmap-splitter</comman
<para>
The maximum number of areas that can be processed in a single pass
during the second stage of processing.
- This must be a number from 1 to 4096.
+ This must be a number from 1 to 9999.
Higher numbers mean fewer passes over the source file and hence
quicker overall processing, but also require more memory.
If you find you are running out of memory but don't want to
@@ -252,7 +252,7 @@ JAVA_OPTS="<replaceable>-Xmx512m</replaceable>" <command>mkgmap-splitter</comman
value or reduce the size of the input file you're trying to split.
</para>
<para>
- Default: 512
+ Default: 2048
</para>
</listitem>
</varlistentry>
diff --git a/doc/splitter.txt b/doc/splitter.txt
index bc62a73..139f0ea 100644
--- a/doc/splitter.txt
+++ b/doc/splitter.txt
@@ -114,9 +114,9 @@ Do not specify it with --overlap unless you have a good reason to do so.
: Set the filename for the split files. In the example the first file will be
called 63240001.osm.pbf and the next one will be 63240002.osm.pbf and so on.
-;--max-areas=512
+;--max-areas=2048
: The maximum number of areas that can be processed in a single pass during
-the second stage of processing. This must be a number from 1 to 4096. Higher
+the second stage of processing. This must be a number from 1 to 9999. Higher
numbers mean fewer passes over the source file and hence quicker overall
processing, but also require more memory. If you find you are running out of
memory but don't want to increase your --max-nodes value, try reducing this
diff --git a/ivy.xml b/ivy.xml
index d2484ec..24d5dbd 100644
--- a/ivy.xml
+++ b/ivy.xml
@@ -28,8 +28,8 @@
<dependency org="xpp3" name="xpp3" rev="1.1.4c"
conf="compile->default(*)"/>
- <dependency org="org.testng" name="testng" rev="6.8.8"
- conf="test->default(*),master(*)"/>
-
+ <dependency org="junit" name="junit" rev="4.11"
+ conf="test->runtime(*),master(*)" />
+
</dependencies>
</ivy-module>
diff --git a/resources/splitter-version.properties b/resources/splitter-version.properties
index 036a607..049358e 100644
--- a/resources/splitter-version.properties
+++ b/resources/splitter-version.properties
@@ -1,2 +1,2 @@
-svn.version: 548
-build.timestamp: 2016-12-29T10:11:46+0000
+svn.version: 583
+build.timestamp: 2017-04-01T15:52:04+0100
diff --git a/splitter.iml b/splitter.iml
index 022ec50..e3fbcc8 100644
--- a/splitter.iml
+++ b/splitter.iml
@@ -1,20 +1,49 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<module relativePaths="true" type="JAVA_MODULE" version="4">
- <component name="NewModuleRootManager" inherit-compiler-output="false">
- <output url="file://$MODULE_DIR$/build/classes" />
- <output-test url="file://$MODULE_DIR$/build/test-classes" />
- <exclude-output />
- <content url="file://$MODULE_DIR$">
- <sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
- <sourceFolder url="file://$MODULE_DIR$/test" isTestSource="true" />
- <excludeFolder url="file://$MODULE_DIR$/dist" />
- <excludeFolder url="file://$MODULE_DIR$/test-output" />
- </content>
- <orderEntry type="inheritedJdk" />
- <orderEntry type="sourceFolder" forTests="false" />
- <orderEntry type="library" exported="" name="XPP 3.0" level="application" />
- <orderEntry type="library" name="TestNG 5.9" level="application" />
- <orderEntry type="library" name="libs" level="project" />
- </component>
-</module>
-
+<?xml version="1.0" encoding="UTF-8"?>
+<module relativePaths="true" type="JAVA_MODULE" version="4">
+ <component name="FacetManager">
+ <facet type="IvyIDEA" name="IvyIDEA">
+ <configuration ivyFile="$MODULE_DIR$/ivy.xml" useProjectSettings="true" useCustomIvySettings="true" ivySettingsFile="" onlyResolveSelectedConfigs="false">
+ <propertiesSettings>
+ <propertiesFiles includeProjectLevelPropertiesFiles="true" />
+ </propertiesSettings>
+ </configuration>
+ </facet>
+ </component>
+ <component name="NewModuleRootManager" inherit-compiler-output="false">
+ <output url="file://$MODULE_DIR$/build/classes" />
+ <output-test url="file://$MODULE_DIR$/build/test-classes" />
+ <exclude-output />
+ <content url="file://$MODULE_DIR$">
+ <sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
+ <sourceFolder url="file://$MODULE_DIR$/test" isTestSource="true" />
+ <excludeFolder url="file://$MODULE_DIR$/dist" />
+ <excludeFolder url="file://$MODULE_DIR$/test-output" />
+ </content>
+ <orderEntry type="inheritedJdk" />
+ <orderEntry type="sourceFolder" forTests="false" />
+ <orderEntry type="module-library">
+ <library name="IvyIDEA">
+ <CLASSES>
+ <root url="jar://$USER_HOME$/.ivy2/cache/com.google.protobuf/protobuf-java/bundles/protobuf-java-2.5.0.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/crosby/osmpbf/jars/osmpbf-1.3.3.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/it.unimi.dsi/fastutil/jars/fastutil-6.5.15-mkg.1b.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/xpp3/xpp3/jars/xpp3-1.1.4c.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/junit/junit/jars/junit-4.11.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/org.hamcrest/hamcrest-core/jars/hamcrest-core-1.3.jar!/" />
+ </CLASSES>
+ <JAVADOC>
+ <root url="jar://$USER_HOME$/.ivy2/cache/com.google.protobuf/protobuf-java/javadocs/protobuf-java-2.5.0-javadoc.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/xpp3/xpp3/javadocs/xpp3-1.1.4c-javadoc.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/junit/junit/javadocs/junit-4.11-javadoc.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/org.hamcrest/hamcrest-core/javadocs/hamcrest-core-1.3-javadoc.jar!/" />
+ </JAVADOC>
+ <SOURCES>
+ <root url="jar://$USER_HOME$/.ivy2/cache/com.google.protobuf/protobuf-java/sources/protobuf-java-2.5.0-sources.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/xpp3/xpp3/sources/xpp3-1.1.4c-sources.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/junit/junit/sources/junit-4.11-sources.jar!/" />
+ <root url="jar://$USER_HOME$/.ivy2/cache/org.hamcrest/hamcrest-core/sources/hamcrest-core-1.3-sources.jar!/" />
+ </SOURCES>
+ </library>
+ </orderEntry>
+ </component>
+</module>
\ No newline at end of file
diff --git a/src/uk/me/parabola/splitter/Area.java b/src/uk/me/parabola/splitter/Area.java
index 43bced5..fe3567a 100644
--- a/src/uk/me/parabola/splitter/Area.java
+++ b/src/uk/me/parabola/splitter/Area.java
@@ -205,8 +205,14 @@ public class Area {
*/
public final boolean intersects(Area bbox) {
return minLat <= bbox.getMaxLat() && maxLat >= bbox.getMinLat() &&
- minLong <= bbox.getMaxLong() && maxLong >= bbox.getMinLong();
+ minLong <= bbox.getMaxLong() && maxLong >= bbox.getMinLong();
}
+
+ public final boolean overlaps(Area bbox) {
+ return minLat < bbox.getMaxLat() && maxLat > bbox.getMinLat() &&
+ minLong < bbox.getMaxLong() && maxLong > bbox.getMinLong();
+ }
+
public Area add(Area area) {
return new Area(
diff --git a/src/uk/me/parabola/splitter/AreaList.java b/src/uk/me/parabola/splitter/AreaList.java
index 1874d30..65ea8e5 100644
--- a/src/uk/me/parabola/splitter/AreaList.java
+++ b/src/uk/me/parabola/splitter/AreaList.java
@@ -106,8 +106,8 @@ public class AreaList {
private void readList(String filename) throws IOException {
areas.clear();
- Pattern pattern = Pattern.compile("([0-9]{8}):" +
- " ([\\p{XDigit}x-]+),([\\p{XDigit}x-]+)" +
+ Pattern pattern = Pattern.compile("([0-9]{8})[ ]*:" +
+ "[ ]*([\\p{XDigit}x-]+),([\\p{XDigit}x-]+)" +
" to ([\\p{XDigit}x-]+),([\\p{XDigit}x-]+)");
try (Reader r = new FileReader(filename);
@@ -118,19 +118,23 @@ public class AreaList {
if (line.isEmpty() || line.charAt(0) == '#')
continue;
- Matcher matcher = pattern.matcher(line);
- matcher.find();
- String mapid = matcher.group(1);
+ try {
+ Matcher matcher = pattern.matcher(line);
+ matcher.find();
+ String mapid = matcher.group(1);
- Area area = new Area(
- Integer.decode(matcher.group(2)),
- Integer.decode(matcher.group(3)),
- Integer.decode(matcher.group(4)),
- Integer.decode(matcher.group(5)));
- if (!area.verify())
- throw new IllegalArgumentException("Invalid area in file "+ filename+ ": " + line);
- area.setMapId(Integer.parseInt(mapid));
- areas.add(area);
+ Area area = new Area(
+ Integer.decode(matcher.group(2)),
+ Integer.decode(matcher.group(3)),
+ Integer.decode(matcher.group(4)),
+ Integer.decode(matcher.group(5)));
+ if (!area.verify())
+ throw new IllegalArgumentException("Invalid area in file "+ filename+ ": " + line);
+ area.setMapId(Integer.parseInt(mapid));
+ areas.add(area);
+ } catch (IllegalStateException e) {
+ throw new IllegalArgumentException("Cannot parse line " + line);
+ }
}
} catch (NumberFormatException e) {
throw new IllegalArgumentException("Bad number in areas list file");
@@ -207,7 +211,7 @@ public class AreaList {
if (point.y == nextPoint.y && point.y == lastPoint.y)
continue;
}
- pw.format(Locale.ROOT, " %e %e%n",Utils.toDegrees(point.x) ,Utils.toDegrees(point.y));
+ pw.format(Locale.ROOT, " %f %f%n",Utils.toDegrees(point.x) ,Utils.toDegrees(point.y));
}
pw.println("END");
diff --git a/src/uk/me/parabola/splitter/Main.java b/src/uk/me/parabola/splitter/Main.java
index 44a8976..52c4e5f 100644
--- a/src/uk/me/parabola/splitter/Main.java
+++ b/src/uk/me/parabola/splitter/Main.java
@@ -60,6 +60,19 @@ public class Main {
private SplitterParams mainOptions;
+ /**
+ * Used for unit tests
+ */
+ public static void mainNoSystemExit(String... args) {
+ Main m = new Main();
+ try {
+ m.start(args);
+ } catch (StopNoErrorException e) {
+ if (e.getMessage() != null)
+ System.out.println(e.getMessage());
+ }
+ }
+
public static void main(String[] args) {
Main m = new Main();
try {
@@ -420,7 +433,7 @@ public class Main {
System.out.println("Setting default overlap=2000 because keep-complete=false is in use.");
}
- if (mainOptions.getProblemReport() != null) {
+ if (params.getProblemReport() != null) {
System.out.println(
"Parameter --problem-report is ignored, because parameter --keep-complete=false is used");
}
diff --git a/src/uk/me/parabola/splitter/MultiTileProcessor.java b/src/uk/me/parabola/splitter/MultiTileProcessor.java
index 888a46c..c4bd783 100644
--- a/src/uk/me/parabola/splitter/MultiTileProcessor.java
+++ b/src/uk/me/parabola/splitter/MultiTileProcessor.java
@@ -552,12 +552,10 @@ class MultiTileProcessor extends AbstractMapProcessor {
continue;
}
AreaSet memWriters = areaDictionary.getSet(memWriterIdx);
- AreaSet test = new AreaSet(memWriters);
- test.subtract(relWriters);
- if (test.isEmpty() == false){
- relWriters.or(memWriters);
+ int oldSize = relWriters.cardinality();
+ relWriters.or(memWriters);
+ if (oldSize != relWriters.cardinality())
changed = true;
- }
}
}
}
diff --git a/src/uk/me/parabola/splitter/ProblemListProcessor.java b/src/uk/me/parabola/splitter/ProblemListProcessor.java
index 6209bbd..a83752c 100644
--- a/src/uk/me/parabola/splitter/ProblemListProcessor.java
+++ b/src/uk/me/parabola/splitter/ProblemListProcessor.java
@@ -177,7 +177,7 @@ class ProblemListProcessor extends AbstractMapProcessor {
maybeChanged = true;
}
}
- if (!isFirstPass && maybeChanged || isLastPass){
+ if (!isFirstPass && maybeChanged || (isLastPass & !isFirstPass)){
int wayAreaIdx = ways.get(way.getId());
if (wayAreaIdx != UNASSIGNED)
areaSet.or(areaDictionary.getSet(wayAreaIdx));
diff --git a/src/uk/me/parabola/splitter/ProblemLists.java b/src/uk/me/parabola/splitter/ProblemLists.java
index 7c2a413..011482c 100644
--- a/src/uk/me/parabola/splitter/ProblemLists.java
+++ b/src/uk/me/parabola/splitter/ProblemLists.java
@@ -59,9 +59,14 @@ public class ProblemLists {
Area a1 = realAreas.get(i);
for (int j = i + 1; j < realAreas.size(); j++) {
Area a2 = realAreas.get(j);
- if (a1.intersects(a2)) {
+ if (a1.overlaps(a2)) {
overlappingTiles.add(a1.getMapId());
overlappingTiles.add(a2.getMapId());
+ System.out.format("overlapping areas %08d and %08d : (%d,%d to %d,%d) and (%d,%d to %d,%d)\n",
+ a1.getMapId(), a2.getMapId(),
+ a1.getMinLat(), a1.getMinLong(), a1.getMaxLat(), a1.getMaxLong(),
+ a2.getMinLat(), a2.getMinLong(), a2.getMaxLat(), a2.getMaxLong());
+ a1.overlaps(a2);
}
}
}
diff --git a/src/uk/me/parabola/splitter/parser/O5mMapParser.java b/src/uk/me/parabola/splitter/parser/O5mMapParser.java
index ed8ded2..593d4d9 100644
--- a/src/uk/me/parabola/splitter/parser/O5mMapParser.java
+++ b/src/uk/me/parabola/splitter/parser/O5mMapParser.java
@@ -138,7 +138,8 @@ public class O5mMapParser {
filePos = skipArray[WAY_DATASET]; // jump to first way
}
}
- readFile();
+ if (filePos >= 0)
+ readFile();
}
/**
@@ -603,8 +604,9 @@ public class O5mMapParser {
fillBuffer();
int pos = (int) (filePos - bufStart);
- if (pos >= bufSize)
- throw new IOException("no data in file buffer");
+ if (pos < 0 || pos >= bufSize) {
+ throw new IOException("no data in file buffer, pos="+pos);
+ }
filePos++;
return fileBuffer.get(pos);
diff --git a/src/uk/me/parabola/splitter/tools/BitReader.java b/src/uk/me/parabola/splitter/tools/BitReader.java
new file mode 100644
index 0000000..bdc7fce
--- /dev/null
+++ b/src/uk/me/parabola/splitter/tools/BitReader.java
@@ -0,0 +1,147 @@
+/*
+ * Copyright (C) 2008 Steve Ratcliffe
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe
+ * Create date: 29-Aug-2008
+ */
+package uk.me.parabola.splitter.tools;
+
+/**
+ * Read an array as a bit stream.
+ *
+ * @author Steve Ratcliffe
+ * @author Gerd Petermann
+ */
+public class BitReader {
+ private final byte[] buf;
+ /** index of the first available byte in the buffer. */
+ private final int offset;
+ /** index of the current byte in the buffer. */
+ private int index; //
+ /** bit position within the current byte. */
+ private int bitPosition;
+
+ public BitReader(byte[] buf) {
+ this(buf, 0);
+ }
+
+ public BitReader(byte[] buf, int start) {
+ this.buf = buf;
+ this.offset = start;
+ reset();
+
+ }
+
+ /** reset the reader for a repeated read. */
+ public void reset() {
+ index = offset;
+ bitPosition = 0;
+ }
+
+ /** set the reader to the given bit position. */
+ public void position(int bitPos) {
+ index = offset + bitPos / 8;
+ bitPosition = bitPos & 0x07;
+ }
+
+ /** set the reader to the relative bit position. */
+ public void skip(int bits) {
+ position(getBitPosition() + bits);
+ }
+
+ /** get a single bit. */
+ public boolean get1() {
+ int off = bitPosition;
+ byte b = buf[index];
+
+ if (++bitPosition == 8) {
+ bitPosition = 0;
+ index++;
+ }
+ return ((b >> off) & 1) == 1;
+ }
+
+ /** get an unsigned int value using the given number of bits */
+ public int get(int n) {
+ if (n == 1) {
+ return get1() ? 1 : 0;
+ }
+ int nb = n + bitPosition;
+ int shift = 0;
+ long work = 0;
+ do {
+ work |= ((long)buf[index++] & 0xff) << shift;
+ shift += 8;
+ nb -= 8;
+ } while (nb > 0);
+
+ if (nb < 0)
+ index--;
+
+ int res = (int) (work >>> bitPosition);
+ bitPosition = nb < 0 ? nb + 8 : 0;
+ if (n < 32)
+ res &= ((1 << n) - 1);
+ return res;
+ }
+
+ /**
+ * Get a signed quantity.
+ *
+ * @param n The field width, including the sign bit.
+ * @return A signed number.
+ */
+ public int sget(int n) {
+ int res = get(n);
+ if (n < 32) {
+ int top = 1 << (n - 1);
+
+ if ((res & top) != 0) {
+ int mask = top - 1;
+ res = ~mask | res;
+ }
+ }
+ return res;
+ }
+
+ /**
+ * Get a signed n-bit value, treating 1 << (n-1) as a flag to read another signed n-bit value
+ * for extended range.
+ */
+ public int sget2(int n) {
+ assert n > 1;
+ int top = 1 << (n - 1);
+ int mask = top - 1;
+ int base = 0;
+
+ long res = get(n);
+ while (res == top) {
+ // Add to the base value, and read another
+ base += mask;
+ res = get(n);
+ }
+
+ // The final byte determines the sign of the result. Add or subtract the base as
+ // appropriate.
+ if ((res & top) == 0)
+ res += base;
+ else
+ res = (res | ~mask) - base; // Make negative and subtract the base
+
+ return (int) res;
+ }
+
+ public int getBitPosition() {
+ return (index - offset) * 8 + bitPosition;
+ }
+}
diff --git a/src/uk/me/parabola/splitter/tools/BitWriter.java b/src/uk/me/parabola/splitter/tools/BitWriter.java
new file mode 100644
index 0000000..534e0ed
--- /dev/null
+++ b/src/uk/me/parabola/splitter/tools/BitWriter.java
@@ -0,0 +1,198 @@
+/*
+ * Copyright (C) 2006 Steve Ratcliffe
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe
+ * Create date: 14-Dec-2006
+ */
+package uk.me.parabola.splitter.tools;
+
+import java.util.Arrays;
+
+/**
+ * A class to write the bitstream.
+ *
+ * @author Steve Ratcliffe
+ */
+public class BitWriter {
+ // Choose so that chunks will not fill it.
+
+ // The byte buffer and its current length (allocated length)
+ private byte[] buf; // The buffer
+ private int bufsize; // The allocated size
+
+ /** The number of bits already used in the current byte of the buffer. */
+ private int usedBits;
+ /** The index of the current byte of the buffer. */
+ private int index;
+ private static final int BUFSIZE_INC = 50;
+ private static final int INITIAL_BUF_SIZE = 20;
+
+ public BitWriter(int sizeInBytes) {
+ bufsize = sizeInBytes;
+ buf = new byte[bufsize];
+ }
+
+ public BitWriter() {
+ this(INITIAL_BUF_SIZE);
+ }
+
+ public void clear() {
+ Arrays.fill(buf, (byte) 0);
+ index = 0;
+ usedBits = 0;
+ }
+
+ /**
+ * Put exactly one bit into the buffer.
+ *
+ * @param b The bottom bit of the integer is set at the current bit position.
+ */
+ private void put1(int b) {
+ ensureSize(index + 1);
+
+ // Get the remaining bits into the byte.
+ int rem = usedBits;
+
+ // Or it in, we are assuming that the position is never turned back.
+ buf[index] |= (b & 0x1) << rem;
+ usedBits++;
+ if (usedBits == 8) {
+ index++;
+ usedBits = 0;
+ }
+ }
+
+ public void put1(boolean b) {
+ put1(b ? 1 : 0);
+ }
+
+ /**
+ * Put a number of bits into the buffer, growing it if necessary.
+ *
+ * @param bval The bits to add, the lowest <b>n</b> bits will be added to
+ * the buffer.
+ * @param nb The number of bits.
+ */
+ public void putn(int bval, int nb) {
+ assert nb >= 1 && nb <= 32;
+ int val = nb < 32 ? bval & ((1<<nb) - 1) : bval;
+ int n = nb;
+
+ ensureSize(index + (usedBits + n + 7) / 8);
+
+ int rem = usedBits;
+
+ // Get each affected byte and set bits into it until we are done.
+ while (n > 0) {
+ buf[index] |= ((val << rem) & 0xff);
+
+ // Account for change so far
+ int nput = 8 - rem;
+ if (nput > n)
+ nput = n;
+ usedBits += nput;
+ if (usedBits >= 8) {
+ index++;
+ usedBits = 0;
+ }
+ // Shift down in preparation for next byte.
+ val >>>= nput;
+ rem = 0;
+ n -= nput;
+ }
+ }
+
+ /**
+ * Write a signed value. Caller must make sure that absolute value fits into
+ * the given number of bits
+ */
+
+ public void sputn(final int bval, final int nb) {
+ assert nb > 1 && nb <= 32;
+ int top = 1 << (nb - 1);
+ if (bval < 0) {
+ assert -bval < top || top < 0;
+ int v = (top + bval) | top;
+ putn(v, nb);
+ } else {
+ assert bval < top || top < 0;
+ putn(bval, nb);
+ }
+ }
+
+ /**
+ * Write a signed value. If the value doesn't fit into nb bits, write one or more 1 << (nb-1)
+ * as a flag for extended range.
+ */
+
+ public void sputn2(final int bval, final int nb) {
+ assert nb > 1 && nb <= 32;
+ int top = 1 << (nb - 1);
+ int mask = top - 1;
+ int val = Math.abs(bval);
+
+ if (bval == Integer.MIN_VALUE) {
+ // catch special case : Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE
+ putn(top, nb);
+ val = Math.abs(val - mask);
+ }
+ assert val >= 0;
+ while (val > mask) {
+ putn(top, nb);
+ val -= mask;
+ }
+ if (bval < 0) {
+ putn((top - val) | top, nb);
+ } else {
+ putn(val, nb);
+ }
+ }
+
+ public byte[] getBytes() {
+ return buf;
+ }
+
+ public int getBitPosition() {
+ return index * 8 + usedBits;
+ }
+
+ /**
+ * Get the number of bytes actually used to hold the bit stream. This therefore can be and usually
+ * is less than the length of the buffer returned by {@link #getBytes()}.
+ * @return Number of bytes required to hold the output.
+ */
+ public int getLength() {
+ if (usedBits == 0)
+ return index;
+ return index + 1;
+ }
+
+ /**
+ * Set everything up so that the given size can be accommodated.
+ * The buffer is re-sized if necessary.
+ *
+ * @param newlen The new length of the bit buffer in bytes.
+ */
+ private void ensureSize(int newlen) {
+ if (newlen >= bufsize)
+ reallocBuffer();
+ }
+
+ /**
+ * Reallocate the byte buffer.
+ */
+ private void reallocBuffer() {
+ bufsize += BUFSIZE_INC;
+ buf = Arrays.copyOf(buf, bufsize);
+ }
+}
diff --git a/src/uk/me/parabola/splitter/tools/Long2IntClosedMap.java b/src/uk/me/parabola/splitter/tools/Long2IntClosedMap.java
index 58ed34d..f9120ab 100644
--- a/src/uk/me/parabola/splitter/tools/Long2IntClosedMap.java
+++ b/src/uk/me/parabola/splitter/tools/Long2IntClosedMap.java
@@ -61,7 +61,6 @@ public class Long2IntClosedMap implements Long2IntClosedMapFunction{
this.maxSize = maxSize;
index = new LongArrayList();
bounds = new IntArrayList();
- vals = new int[maxSize];
keys = new int[maxSize];
this.unassigned = unassigned;
}
@@ -85,7 +84,12 @@ public class Long2IntClosedMap implements Long2IntClosedMapFunction{
oldTopId = topId;
}
keys[size] = (int)(key & LOW_ID_MASK);
- vals[size] = val;
+ if (val != unassigned) {
+ if (vals == null)
+ allocVals();
+
+ vals[size] = val;
+ }
currentKey = key;
size++;
return size-1;
@@ -99,21 +103,24 @@ public class Long2IntClosedMap implements Long2IntClosedMapFunction{
BufferedOutputStream stream = new BufferedOutputStream(fos);
DataOutputStream dos = new DataOutputStream(stream)) {
long lastKey = Long.MIN_VALUE;
- for (int indexPos = 0; indexPos < index.size(); indexPos++){
- long topId = index.getLong(indexPos);
- int lowerBound = bounds.getInt(indexPos);
- int upperBound = size;
- if (indexPos+1 < index.size())
- upperBound = bounds.getInt(indexPos+1);
- long topVal = topId << TOP_ID_SHIFT;
- for (int i = lowerBound; i < upperBound; i++){
- long key = topVal | (keys[i] & LOW_ID_MASK);
- int val = vals[i];
- assert i == 0 || lastKey < key;
- lastKey = key;
- if (val != unassigned){
- dos.writeLong(key);
- dos.writeInt(val);
+ if (vals != null) {
+ for (int indexPos = 0; indexPos < index.size(); indexPos++){
+ long topId = index.getLong(indexPos);
+ int lowerBound = bounds.getInt(indexPos);
+ int upperBound = size;
+ if (indexPos+1 < index.size())
+ upperBound = bounds.getInt(indexPos+1);
+ long topVal = topId << TOP_ID_SHIFT;
+ for (int i = lowerBound; i < upperBound; i++){
+ long key = topVal | (keys[i] & LOW_ID_MASK);
+
+ int val = vals[i];
+ assert i == 0 || lastKey < key;
+ lastKey = key;
+ if (val != unassigned){
+ dos.writeLong(key);
+ dos.writeInt(val);
+ }
}
}
}
@@ -141,8 +148,10 @@ public class Long2IntClosedMap implements Long2IntClosedMapFunction{
@Override
public int getRandom(long key){
+ if (vals == null)
+ return unassigned;
int pos = getKeyPos(key);
- if (pos >= 0)
+ if (pos >= 0)
return vals[pos];
return unassigned;
}
@@ -228,6 +237,8 @@ public class Long2IntClosedMap implements Long2IntClosedMapFunction{
int pos = getKeyPos(key);
if (pos < 0)
throw new IllegalArgumentException("replace on unknown key requested");
+ if (vals == null)
+ allocVals();
int oldVal = vals[pos];
vals[pos] = val;
return oldVal;
@@ -237,6 +248,11 @@ public class Long2IntClosedMap implements Long2IntClosedMapFunction{
public void stats(String prefix) {
System.out.println(prefix + name + "WriterMap contains " + Utils.format(size) + " pairs.");
}
+
+ private void allocVals() {
+ vals = new int[maxSize];
+ Arrays.fill(vals, unassigned);
+ }
}
diff --git a/src/uk/me/parabola/splitter/tools/SparseLong2IntMap.java b/src/uk/me/parabola/splitter/tools/SparseLong2IntMap.java
index 4d6fd1e..7e6fec4 100644
--- a/src/uk/me/parabola/splitter/tools/SparseLong2IntMap.java
+++ b/src/uk/me/parabola/splitter/tools/SparseLong2IntMap.java
@@ -17,8 +17,10 @@ import java.nio.ByteBuffer;
import java.util.Arrays;
import it.unimi.dsi.fastutil.Hash;
+import it.unimi.dsi.fastutil.ints.Int2IntLinkedOpenHashMap;
import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntBidirectionalIterator;
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import uk.me.parabola.splitter.Utils;
@@ -29,11 +31,11 @@ import uk.me.parabola.splitter.Utils;
*
* Inspired by SparseInt2ShortMapInline.
*
- * A HashMap is used to address large vectors which address chunks. The HashMap
+ * A HashMap is used to address {@link ChunkMem} instances which address chunks. The HashMap
* is the only part that stores long values, and it will be very small as long
- * as long as input is normal OSM data and not something with random numbers.
+ * as input is normal OSM data and not something with random keys.
* A chunk stores up to CHUNK_SIZE values. A separately stored bit-mask is used
- * to separate used and unused entries in the chunk. Thus, the chunk length
+ * to separate used and unused entries in the chunk. Thus, the stored chunk length
* depends on the number of used entries, not on the highest used entry.
* Such a "masked encoded" entry may look like this
* v1,v1,v1,v1,v1,v1,v2,v2,v2,v2,v1,v1,v1,v1,v1,u,?,?,...}
@@ -43,11 +45,18 @@ import uk.me.parabola.splitter.Utils;
*
* After applying Run Length Encryption on this the chunk looks like this:
* {v1,6,v2,4,v1,5,?,?,?}
- *
+ * Further compression is achieved by using a dictionary if appropriate. The dictionary
+ * contains all distinct values. These are then addressed by the position in the dictionary.
+ * The above example will be reduced to this:
+ * {v1,v2,6,4,5}
+ * Note that there is no need to store the position when the dictionary contains
+ * two entries.
+ * If a dictionary contains only one entry we only store the dictionary and the bit mask.
+ *
* Fortunately, OSM data is distributed in a way that a lot of chunks contain
* just one distinct value.
*
- * Since we have OSM ids with 64 bits, we have to divide the key into 3 parts:
+ * Since we have OSM IDs with 64 bits, we have to divide the key into 3 parts:
* 37 bits for the value that is stored in the HashMap.
* 21 bits for the chunkId (this gives the required length of a large vector)
* 6 bits for the position in the chunk
@@ -60,22 +69,19 @@ import uk.me.parabola.splitter.Utils;
* y is the position of the store (0-1048575), we store a value incremented by 1 to ensure a non-zero value for used chunks
* z is the position of the chunk within the store. (0-15)
* The maximum values for these three values are chosen so that we can place them
- * together into one int (32 bits).
+ * together into the int value that is kept in the large vector.
*/
public final class SparseLong2IntMap {
- /** the part of the key that is not saved in the top HashMap. */
- private static final long CHUNK_ID_MASK = 0x7ffffffL;
- private static final long TOP_ID_MASK = ~CHUNK_ID_MASK; // the part of the key that is saved in the top HashMap
- private static final int TOP_ID_SHIFT = Long.numberOfTrailingZeros(TOP_ID_MASK);
-
- private static final int CHUNK_SIZE = 64; // 64 = 1<< 6 (last 6 bits of the key)
- /** Number of entries addressed by one topMap entry. */
- private static final int LARGE_VECTOR_SIZE = (int) (CHUNK_ID_MASK / CHUNK_SIZE + 1);
- private static final int CHUNK_STORE_BITS_FOR_Z = 5; // must fit into byte field
- private static final int CHUNK_STORE_BITS_FOR_Y = Integer.numberOfTrailingZeros(LARGE_VECTOR_SIZE) - CHUNK_STORE_BITS_FOR_Z + 1;
- private static final int CHUNK_STORE_BITS_FOR_X = 8; // values 1 .. 256 are stored as 0..255
+ private static final boolean SELF_TEST = false;
+ private static final int CHUNK_SIZE = 64;
+ private static final int CHUNK_SHIFT = Integer.numberOfTrailingZeros(CHUNK_SIZE);
+ private static final int MAX_BYTES_FOR_VAL = Integer.BYTES;
+ private static final int MAX_STORED_BYTES_FOR_CHUNK = CHUNK_SIZE * MAX_BYTES_FOR_VAL;
+ private static final int CHUNK_STORE_BITS_FOR_X = Integer.SIZE - Integer.numberOfLeadingZeros(MAX_STORED_BYTES_FOR_CHUNK - 1); // values 1 .. 256 are stored as 0..255
+ private static final int CHUNK_STORE_BITS_FOR_Z = 8; // must not be higher than 8
+ private static final int CHUNK_STORE_BITS_FOR_Y = Integer.SIZE - (CHUNK_STORE_BITS_FOR_X + CHUNK_STORE_BITS_FOR_Z);
private static final int CHUNK_STORE_ELEMS = 1 << CHUNK_STORE_BITS_FOR_Z;
private static final int CHUNK_STORE_X_MASK = (1 << CHUNK_STORE_BITS_FOR_X) - 1;
private static final int CHUNK_STORE_Y_MASK = (1 << CHUNK_STORE_BITS_FOR_Y) - 1;
@@ -83,6 +89,15 @@ public final class SparseLong2IntMap {
private static final int CHUNK_STORE_Y_SHIFT = CHUNK_STORE_BITS_FOR_X;
private static final int CHUNK_STORE_Z_SHIFT = CHUNK_STORE_BITS_FOR_X + CHUNK_STORE_BITS_FOR_Y;
+ private static final int BYTES_FOR_MASK = 8;
+
+ /** Number of entries addressed by one topMap entry. */
+ private static final int TOP_ID_SHIFT = 27; // must be below 32, smaller values give smaller LARGE_VECTOR_SIZEs and more entries in the top HashMap
+ /** the part of the key that is not saved in the top HashMap. */
+ private static final long CHUNK_ID_MASK = (1L << (TOP_ID_SHIFT)) - 1;
+
+ /** Number of entries addressed by one topMap entry. */
+ private static final int LARGE_VECTOR_SIZE = (int) (CHUNK_ID_MASK / CHUNK_SIZE + 1);
private static final int MAX_Y_VAL = LARGE_VECTOR_SIZE / CHUNK_STORE_ELEMS + 1;
/** The part of the key that contains the offset in the chunk. */
private static final long CHUNK_OFFSET_MASK = CHUNK_SIZE - 1;
@@ -98,64 +113,91 @@ public final class SparseLong2IntMap {
private long oldModCount;
private long currentChunkId;
+ private ChunkMem currentMem;
private final int [] currentChunk = new int[CHUNK_SIZE]; // stores the values in the real position
+ private final int [] testChunk = new int[CHUNK_SIZE]; // for internal test
private final int [] maskedChunk = new int[CHUNK_SIZE]; // a chunk after applying the "mask encoding"
private final int[] tmpChunk = new int[CHUNK_SIZE * 2]; // used for tests of compression methods
private static final int MAX_BYTES_FOR_RLE_CHUNK = CHUNK_SIZE * (Integer.BYTES + 1);
private final ByteBuffer bufEncoded = ByteBuffer.allocate(MAX_BYTES_FOR_RLE_CHUNK); // for the RLE-compressed chunk
- private static final int MAX_STORED_BYTES_FOR_CHUNK = CHUNK_SIZE * Integer.BYTES;
// bit masks for the flag byte
- private static final int FLAG_USED_BYTES_MASK = 0x03; // number of bytes - 1
- private static final int FLAG_COMP_METHOD_DELTA = 0x10; // rest of vals are delta encoded, bias is first val
- private static final int FLAG_COMP_METHOD_RLE = 0x80; // values are run length encoded
-
+ private static final int FLAG1_USED_BYTES_MASK = 0x03; // number of bytes - 1
+ private static final int FLAG1_RUNLEN_MASK = 0x1C; // number of bits for run length values
+ private static final int FLAG1_DICTIONARY = 0x20; // if set a dictionary follows the flag bytes
+ private static final int FLAG1_COMP_METHOD_BITS = 0x40; // rest of vals are "bit" encoded
+ private static final int FLAG1_COMP_METHOD_RLE = 0x80; // values are run length encoded
+
+ private static final int FLAG2_BITS_FOR_VALS = 0x1f;
+ private static final int FLAG2_ALL_POSITIVE = 0x20;
+ private static final int FLAG2_ALL_NEGATIVE = 0x40;
+ private static final int FLAG2_DICT_SIZE_IS_2 = 0x80;
+ private static final int FLAG_BITS_FOR_DICT_SIZE = Integer.SIZE - Integer.numberOfLeadingZeros(CHUNK_SIZE - 1);
+ /** a chunk that is stored with a length between 1 and 3 has no flag byte and is always a single value chunk. */
+ private static final int SINGLE_VAL_CHUNK_LEN_NO_FLAG = 3;
+
// for statistics
private final String dataDesc;
- private int storedLengthOfCurrentChunk;
- private int currentChunkIdInStore;
-
- private Long2ObjectOpenHashMap<Mem> topMap;
+ private Long2ObjectOpenHashMap<ChunkMem> topMap;
static final long MAX_MEM = Runtime.getRuntime().maxMemory() / 1024 / 1024;
static final int POINTER_SIZE = (MAX_MEM < 32768) ? 4 : 8; // presuming that compressedOOps is enabled
- private Integer bias1; // used for initial delta encoding
+ private Integer bias1; // used for initial delta encoding
+ private final BitWriter bitWriter = new BitWriter(1000);
+
+
+ /**
+ * A map that stores pairs of (OSM) IDs and int values identifying the
+ * areas in which the object with the ID occurs.
+ * @param dataDesc
+ */
+ public SparseLong2IntMap(String dataDesc) {
+ // sanity check to make sure that we can store enough chunks with the same length
+ // If this test fails it is not possible to store the same value for all ids
+ long reserve = ((1L << CHUNK_STORE_BITS_FOR_Y) - 1) * CHUNK_SIZE - LARGE_VECTOR_SIZE;
+ assert reserve > 0 : "Bad combination of constants";
+ this.dataDesc = dataDesc;
+ System.out.println(dataDesc + " Map: uses " + this.getClass().getSimpleName());
+ clear();
+ }
/**
* Helper class to manage memory for chunks.
* @author Gerd Petermann
*
*/
- static class Mem {
- final long topId;
- long estimatedBytes; // estimate value for the allocated bytes
- final int[] largeVector;
- byte[][][] chunkStore;
- long[][][] maskStore;
- final int[] freePosInStore;
+ static class ChunkMem {
+ private final long topId;
+ private long estimatedBytes; // estimate value for the allocated bytes
+ private int[] largeVector; // only used when sparseVector is growing too large
+ private Int2ObjectOpenHashMap<IntArrayList> reusableChunks;
+ private byte[][][] chunkStore;
+ private final int[] freePosInStore;
/** maps chunks that can be reused. */
- Int2ObjectOpenHashMap<IntArrayList> reusableChunks;
+ private int chunkCount;
+ private int lastFlag;
+ private long lastChunkId = INVALID_CHUNK_ID;
+ private boolean checkReuse;
- public Mem(long topID) {
+ public ChunkMem(long topID) {
this.topId = topID;
- largeVector = new int[LARGE_VECTOR_SIZE];
chunkStore = new byte[MAX_STORED_BYTES_FOR_CHUNK][][];
- maskStore = new long[MAX_STORED_BYTES_FOR_CHUNK][][];
freePosInStore = new int[MAX_STORED_BYTES_FOR_CHUNK];
- reusableChunks = new Int2ObjectOpenHashMap<>(0);
+ reusableChunks = new Int2ObjectOpenHashMap<>(0, Hash.VERY_FAST_LOAD_FACTOR);
+ largeVector = new int[LARGE_VECTOR_SIZE];
estimatedBytes = LARGE_VECTOR_SIZE * Integer.BYTES
- + (MAX_STORED_BYTES_FOR_CHUNK) * (2 * 8 + 1 * Integer.BYTES) + 4 * (24 + 16) + 190;
+ + (MAX_STORED_BYTES_FOR_CHUNK) * (8 + 1 * Integer.BYTES) + 3 * (24 + 16) + 190;
}
- public void grow(int x) {
+ private void grow(int x) {
int oldCapacity = chunkStore[x].length;
- int newCapacity = oldCapacity < 1024 ? oldCapacity * 2 : oldCapacity + (oldCapacity >> 1);
- if (newCapacity >= MAX_Y_VAL)
- newCapacity = MAX_Y_VAL;
- if (newCapacity <= oldCapacity)
- return;
+ int newCapacity = oldCapacity < 1024 ? oldCapacity * 2 : oldCapacity + (oldCapacity >> 1);
+ if (newCapacity >= MAX_Y_VAL)
+ newCapacity = MAX_Y_VAL;
+ if (newCapacity <= oldCapacity)
+ return;
resize(x, newCapacity);
}
@@ -163,63 +205,140 @@ public final class SparseLong2IntMap {
int oldCapacity = chunkStore[x].length;
if (newCapacity < oldCapacity)
assert chunkStore[x][newCapacity] == null;
- chunkStore[x] = Arrays.copyOf(chunkStore[x], newCapacity);
- maskStore[x] = Arrays.copyOf(maskStore[x], newCapacity);
- // bytes for pointers seem to depends on the capacity ?
- estimatedBytes += (newCapacity - oldCapacity) * (2 * 8); // pointer-pointer
+ chunkStore[x] = Arrays.copyOf(chunkStore[x], newCapacity);
+ estimatedBytes += (newCapacity - oldCapacity) * 8; // pointer-pointer
}
- public void startStore(int x) {
- chunkStore[x] = new byte[2][];
- maskStore[x] = new long[2][];
- estimatedBytes += 2 * (24 + 2 * (8)); // pointer-pointer
- }
- }
-
- /**
- * Helper class to store the various positions in the multi-tier data structure.
- * @author Gerd Petermann
- *
- */
- private static class MemPos{
- final int x,y,z;
- final Mem mem;
- final int largeVectorIndex;
+ private void putChunk(long chunkId, ByteBuffer bufEncoded) {
+ int len = bufEncoded.limit();
+ int x = len - (1 + BYTES_FOR_MASK);
+
+ if (chunkStore[x] == null) {
+ chunkStore[x] = new byte[2][];
+ estimatedBytes += 24 + 2 * 8; // pointer-pointer
+ }
+
+ IntArrayList reusableChunk = null;
+ int reuseFlag = 0;
+ int lastX = -1;
+ if (lastChunkId != (chunkId & OLD_CHUNK_ID_MASK)) {
+ chunkCount++;
+ } else {
+ lastX = lastFlag & CHUNK_STORE_X_MASK;
+ if (x == lastX) {
+ reuseFlag = lastFlag;
+ } else {
+ // this is a rewrite with a different length, add the previously used chunk to the reusable list
+ reusableChunk = reusableChunks.get(lastX);
+ if (reusableChunk == null) {
+ reusableChunk = new IntArrayList(8);
+ reusableChunks.put(lastX, reusableChunk);
+ estimatedBytes += 8 * Integer.BYTES + 24 + Integer.BYTES + POINTER_SIZE + 16; // for the IntArrayList instance
+ estimatedBytes += 20; // estimate for the hash map entry
+ }
+ reusableChunk.add(lastFlag);
+ checkReuse = true;
+ }
+ }
+ if (x != lastX && checkReuse) {
+ reusableChunk = reusableChunks.get(x);
+ if (reusableChunk != null && !reusableChunk.isEmpty()) {
+ reuseFlag = reusableChunk.removeInt(reusableChunk.size() - 1);
+ }
+ }
+ int y, z;
+ byte[] store;
+ if (reuseFlag != 0) {
+ y = (reuseFlag >> CHUNK_STORE_Y_SHIFT) & CHUNK_STORE_Y_MASK;
+ y--; // we store the y value incremented by 1
+ z = (reuseFlag >> CHUNK_STORE_Z_SHIFT) & CHUNK_STORE_Z_MASK;
+ store = chunkStore[x][y];
+ } else {
+ y = ++freePosInStore[x] / CHUNK_STORE_ELEMS;
+ if (y >= chunkStore[x].length)
+ grow(x);
+ if (chunkStore[x][y] == null) {
+ int numChunks = (len < 16) ? CHUNK_STORE_ELEMS : 8;
+ chunkStore[x][y] = new byte[numChunks * len + 1];
+ estimatedBytes += 24 + numChunks * len + 1;
+ int padding = 8 - (numChunks & 7);
+ if (padding < 8)
+ estimatedBytes += padding;
+ }
+ store = chunkStore[x][y];
+ z = (store[0]++) & CHUNK_STORE_Z_MASK;
+ if (len * (z + 1) + 1 > store.length) {
+ int newNum = Math.min(CHUNK_STORE_ELEMS, z + 8);
+ store = Arrays.copyOf(store, newNum * len + 1);
+ chunkStore[x][y] = store;
+ estimatedBytes += (newNum - z) * len;
+ }
+ }
+
+ ByteBuffer storeBuf = ByteBuffer.wrap(store, z * len + 1, len);
+ storeBuf.put(bufEncoded);
- MemPos(Mem mem, int largeVectorIndex, int x, int y, int z) {
- this.mem = mem;
- this.largeVectorIndex = largeVectorIndex;
- this.x = x;
- this.y = y;
- this.z = z;
+ // calculate the position in the large vector
+ y++; // we store the y value incremented by 1
+ assert x < 1 << CHUNK_STORE_BITS_FOR_X;
+ assert y < 1 << CHUNK_STORE_BITS_FOR_Y;
+ assert z < 1 << CHUNK_STORE_BITS_FOR_Z;
+ int flag = (z & CHUNK_STORE_Z_MASK) << CHUNK_STORE_Z_SHIFT
+ | (y & CHUNK_STORE_Y_MASK) << CHUNK_STORE_Y_SHIFT
+ | (x & CHUNK_STORE_X_MASK);
+
+ assert flag != 0;
+
+ int vectorPos = getVectorPos(chunkId);
+ largeVector[vectorPos] = flag;
+ }
+
+ /**
+ * Calculate the position in the large vector
+ * @param chunkId the (unshifted) key
+ * @return the position in the large vector
+ */
+ private static int getVectorPos (long chunkId) {
+ return (int) (chunkId & CHUNK_ID_MASK) >> CHUNK_SHIFT;
}
- public long getMask() {
- return mem.maskStore[x][y][z];
+ private int getFlag(long chunkId) {
+ int vectorPos = getVectorPos(chunkId);
+ return largeVector[vectorPos];
}
- public ByteBuffer getInBuf() {
- int chunkLen = x + 1;
- int startPos = z * chunkLen + 1;
- byte[] store = mem.chunkStore[x][y];
- return ByteBuffer.wrap(store, startPos, chunkLen);
+ /**
+ * @return number of used chunks
+ */
+ public int getChunkCount() {
+ return chunkCount;
+ }
+
+ /**
+ * Get a {@link }ByteBuffer} that contains the stored (encoded) chunk.
+ * @param key the key
+ * @param forUpdate
+ * @return the buffer or null if no chunk
+ */
+ public ByteBuffer getStoredChunk(long key, boolean forUpdate) {
+ int flag = getFlag(key);
+ if (flag == 0)
+ return null;
+ int x = flag & CHUNK_STORE_X_MASK;
+ int y = (flag >> CHUNK_STORE_Y_SHIFT) & CHUNK_STORE_Y_MASK;
+ y--; // we store the y value incremented by 1
+ int z = (flag >> CHUNK_STORE_Z_SHIFT) & CHUNK_STORE_Z_MASK;
+ int chunkLenWithMask = x + 1 + BYTES_FOR_MASK;
+ int startPos = z * chunkLenWithMask + 1;
+ if (forUpdate) {
+ lastChunkId = key & OLD_CHUNK_ID_MASK;
+ lastFlag = flag;
+ }
+ return ByteBuffer.wrap(chunkStore[x][y], startPos, chunkLenWithMask);
}
}
/**
- * A map that stores pairs of (OSM) IDs and int values identifying the
- * areas in which the object with the ID occurs.
- * @param dataDesc
- */
- public SparseLong2IntMap(String dataDesc) {
- long reserve = (1L << CHUNK_STORE_BITS_FOR_Y - 1) * CHUNK_SIZE - LARGE_VECTOR_SIZE;
- assert reserve > 0;
- this.dataDesc = dataDesc;
- System.out.println(dataDesc + " Map: uses " + this.getClass().getSimpleName());
- clear();
- }
-
- /**
* Count how many of the lowest X bits in mask are set.
*
* @return how many of the lowest X bits in mask are set.
@@ -275,91 +394,191 @@ public final class SparseLong2IntMap {
}
/**
- * Try to use Run Length Encoding (RLE) to compress the chunk stored in tmpWork. In most
+ * calculate the number of bits needed to store the value as a signed number.
+ * @param val the value to store
+ * @return the number of bits needed to store the value as a signed number
+ */
+ private static int bitsNeeded(int val) {
+ return Long.SIZE - Long.numberOfLeadingZeros(Math.abs(val)) + 1;
+ }
+
+ private ChunkMem getMem (long key) {
+ long topID = (key >> TOP_ID_SHIFT);
+ if (currentMem == null || currentMem.topId != topID) {
+ currentMem = topMap.get(topID);
+ }
+ return currentMem;
+ }
+
+ /**
+ * Try to use Run Length Encoding (RLE) to compress the "mask-encoded" chunk. In most
* cases this works very well because chunks often have only one or two distinct values.
- * The run length value is always between 1 and 64, which requires just one byte.
- * If the stored values don't fit into a single byte, also try delta encoding (for values 2 .. n).
+ * The values and run length fields are each written with a fixed number of bits.
*
* @param numVals number of elements in the chunk, content of {@code maskedChunk} after that is undefined.
* @param minVal smallest value in maskedChunk
* @param maxVal highest value in maskedChunk
*
*/
- private void chunkCompress(int numVals, long minVal, long maxVal) {
- assert minVal != maxVal;
- int start = maskedChunk[0];
- int bytesFor1st = calcNeededBytes(start, start);
- int bytesForRest = calcNeededBytes(minVal, maxVal);
- int flag = 0;
- int bias2 = 0;
- int prefixLen = 1;
-
- if (bytesForRest > 1) {
- // check if all values are in a small range which allows
- int test = testBias(minVal, maxVal, start);
- if (test < bytesForRest) {
- bytesForRest = test;
- flag |= FLAG_COMP_METHOD_DELTA;
- bias2 = start;
- }
- }
- int lenNoCompress = Math.min(MAX_STORED_BYTES_FOR_CHUNK, prefixLen + bytesFor1st + (numVals-1) * bytesForRest);
- int lenRLE = prefixLen;
-
- int numCounts = 0;
+ private void chunkCompress(int numVals, int minVal, int maxVal) {
+ int flag1 = FLAG1_COMP_METHOD_BITS;
int opos = 0;
+ int maxRunLen = 0;
+ int numCounts = 0;
+ Int2IntLinkedOpenHashMap dict = new Int2IntLinkedOpenHashMap(32, Hash.VERY_FAST_LOAD_FACTOR);
+ dict.defaultReturnValue(-1);
+
for (int i = 0; i < numVals; i++) {
int runLength = 1;
- while (i+1 < numVals && maskedChunk[i] == maskedChunk[i+1]) {
+ while (i + 1 < numVals && maskedChunk[i] == maskedChunk[i + 1]) {
runLength++;
i++;
}
numCounts++;
- tmpChunk[opos++] = maskedChunk[i];
+ int v = maskedChunk[i];
+ if (dict.get(v) == dict.defaultReturnValue())
+ dict.put(v, dict.size());
+ tmpChunk[opos++] = v;
tmpChunk[opos++] = runLength;
- lenRLE += (numCounts == 1 ? bytesFor1st : bytesForRest) + 1;
- if (lenRLE >= lenNoCompress)
- break;
- }
- flag |= (bytesForRest - 1) << 2 | (bytesFor1st - 1);
+ if (maxRunLen < runLength)
+ maxRunLen = runLength;
+ }
+ // the first value is used as a bias because it is likely that this will bring min/max values closer to 0
+ int bias2 = maskedChunk[0];
+ int bits = Math.max(bitsNeeded(minVal - bias2), bitsNeeded(maxVal - bias2));
+ int sign = getSign(minVal - bias2, maxVal - bias2);
+ // try to find out if compression will help
+ int bitsForRLE = bitsNeeded(maxRunLen-1) - 1; // we always have positive values and we store the len decremented by 1
+ int bitsForVal = bits - Math.abs(sign);
+ int bitsForPos = bitsNeeded(dict.size() - 1) - 1;
+ int bitsForDictFlag = dict.size() > 2 ? FLAG_BITS_FOR_DICT_SIZE : 0;
+ int bitsForDict = bitsForDictFlag + (dict.size() - 1) * bitsForVal;
+ int len1 = toBytes((numVals - 1) * bitsForVal);
+ int len2 = toBytes(bitsForRLE + (numCounts - 1) * (bitsForRLE + bitsForVal));
+ int len3 = toBytes(bitsForDict + (numVals - 1) * bitsForPos);
+ int len4 = toBytes(bitsForDict + bitsForRLE + (numCounts - 1) * (bitsForRLE + (dict.size() > 2 ? bitsForPos : 0)));
+ boolean useRLE = numCounts < 5 && maxRunLen > 1 && (Math.min(len2, len4) < Math.min(len1, len3));
+ boolean useDict = (useRLE) ? len2 > len4 : len1 > len3;
- boolean storeFlag = true;
- if (lenRLE < lenNoCompress) {
- flag |= FLAG_COMP_METHOD_RLE;
- } else {
- // check unlikely special case to make sure that encoded len is below 256
- // don't write flag if all values are stored with 4 bytes
- storeFlag = (lenNoCompress < MAX_STORED_BYTES_FOR_CHUNK);
- }
- if (storeFlag) {
- bufEncoded.put((byte) flag);
+// System.out.println(len1 + " " + len2 + " " + len3 + " " + len4 + " " + useDict + " " + useRLE + " " + dict.size() + " " + numCounts);
+// if (useRLE && numVals / 2 < numCounts) {
+// long dd = 4;
+// }
+ bitWriter.clear();
+ if (useDict) {
+ flag1 |= FLAG1_DICTIONARY;
+ if (dict.size() > 2)
+ bitWriter.putn(dict.size() - 1, FLAG_BITS_FOR_DICT_SIZE);
+ IntBidirectionalIterator iter = dict.keySet().iterator();
+ iter.next();
+ while (iter.hasNext()) {
+ storeVal(iter.nextInt() - bias2, bits, sign);
+ }
}
- int bytesToUse = bytesFor1st;
- int bias = 0;
- if (lenRLE < lenNoCompress) {
- int pos = 0;
+
+ if (useRLE) {
+ flag1 |= FLAG1_COMP_METHOD_RLE;
+ flag1 |= ((bitsForRLE << 2) & FLAG1_RUNLEN_MASK) ;
+ boolean writeIndex = useDict & (dict.size() > 2);
+ int pos = 1; // first val is written with different method
+
+ bitWriter.putn(tmpChunk[pos++] - 1, bitsForRLE);
while (pos < opos) {
- putVal(bufEncoded, tmpChunk[pos++] - bias, bytesToUse);
- bufEncoded.put((byte) tmpChunk[pos++]); // run length
- if (pos == 2) {
- bytesToUse = bytesForRest;
- bias = bias2;
+ int v = tmpChunk[pos++];
+ if (!useDict)
+ storeVal(v - bias2, bits, sign);
+ else {
+ if (writeIndex) {
+ int idx = dict.get(v);
+ bitWriter.putn(idx, bitsForPos);
+ }
}
+ bitWriter.putn(tmpChunk[pos++] - 1, bitsForRLE);
}
- assert lenRLE == bufEncoded.position();
} else {
- for (int i = 0; i < numVals; i++) {
- putVal(bufEncoded, maskedChunk[i] - bias, bytesToUse);
- if (i == 0) {
- bytesToUse = bytesForRest;
- bias = bias2;
+ for (int i = 1; i < numVals; i++) { // first val is written with different method
+ if (useDict) {
+ int v = maskedChunk[i];
+ bitWriter.putn(dict.get(v), bitsForPos);
+ } else {
+ storeVal(maskedChunk[i] - bias2, bits, sign);
}
}
- assert lenNoCompress == bufEncoded.position();
}
-
+ int bytesForBias = 0;
+ bytesForBias = bytesNeeded(bias2, bias2);
+ flag1 |= (bytesForBias - 1) & FLAG1_USED_BYTES_MASK;
+ int bwLen = bitWriter.getLength();
+ if (SELF_TEST) {
+ if (useRLE && useDict && len4 != bwLen)
+ assert false : "len4 " + bwLen + " <> " + len4;
+ if (!useRLE && useDict && len3 != bwLen)
+ assert false : "len3 " + bwLen + " <> " + len3;
+ if (useRLE && !useDict && len2 != bwLen)
+ assert false : "len2 " + bwLen + " <> " + len2;
+ if (!useRLE && !useDict && len1 != bwLen)
+ assert false : "len1 " + bwLen + " <> " + len1;
+ }
+ int len = 1 + 1 + bitWriter.getLength() + bytesForBias;
+ if (len < MAX_STORED_BYTES_FOR_CHUNK) {
+ bufEncoded.put((byte) flag1);
+ int flag2 = (bits - 1) & FLAG2_BITS_FOR_VALS; // number of bits for the delta encoded values
+ if (sign > 0)
+ flag2 |= FLAG2_ALL_POSITIVE;
+ else if (sign < 0)
+ flag2 |= FLAG2_ALL_NEGATIVE;
+ if (dict.size() == 2)
+ flag2 |= FLAG2_DICT_SIZE_IS_2;
+ bufEncoded.put((byte) flag2);
+ putVal(bufEncoded, bias2, bytesForBias);
+
+ bufEncoded.put(bitWriter.getBytes(), 0, bitWriter.getLength());
+ } else {
+ // no flag byte for worst case
+ for (int i = 0; i < numVals; i++){
+ putVal(bufEncoded, currentChunk[i], 4);
+ }
+ }
return;
}
+
+ /**
+ * calculate the number of bytes consumed by given a number of bits
+ * @param nBits the number of bits
+ * @return the number of bytes needed to store the bits
+ */
+ private static int toBytes(int nBits) {
+ return (nBits + 7) / 8;
+ }
+
+ private void storeVal(int val, int nb, int sign) {
+ if (sign == 0)
+ bitWriter.sputn(val, nb);
+ else if (sign == 1){
+ bitWriter.putn(val, nb-1);
+ } else
+ bitWriter.putn(-val, nb-1);
+ }
+
+ private static int readVal(BitReader br, int bits, int sign) {
+ if (sign == 0)
+ return br.sget(bits);
+ else if (sign > 0)
+ return br.get(bits-1);
+ return -br.get(bits-1);
+ }
+
+ private static int getSign(int v1, int v2) {
+ assert v1 != v2;
+ if (v1 < 0) {
+ return (v2 <= 0) ? -1 : 0;
+ } else if (v1 > 0) {
+ return v2 >= 0 ? 1: 0;
+ } else {
+ //v1 == 0
+ return v2 < 0 ? -1 : 1;
+ }
+ }
/**
* Try to compress the data in currentChunk and store the result in the chunkStore.
@@ -389,32 +608,37 @@ public final class SparseLong2IntMap {
elementMask <<= 1;
}
bufEncoded.clear();
+ bufEncoded.putLong(mask);
if (minVal == maxVal) {
// nice: single value chunk
- int bytesFor1st = calcNeededBytes(minVal, maxVal);
- if (bytesFor1st > 2) {
+ int bytesFor1st = bytesNeeded(minVal, maxVal);
+ if (bytesFor1st > SINGLE_VAL_CHUNK_LEN_NO_FLAG) {
bufEncoded.put((byte) (bytesFor1st - 1)); // flag byte
}
putVal(bufEncoded, maskedChunk[0], bytesFor1st);
} else {
chunkCompress(simpleLen, minVal, maxVal);
+ assert bufEncoded.position() > SINGLE_VAL_CHUNK_LEN_NO_FLAG;
}
bufEncoded.flip();
- putChunk(currentChunkId, bufEncoded, mask);
- }
-
- /**
- * Calculate the needed bytes for the range minVal..maxVal if bias is substructed.
- * @param minVal start of range (including)
- * @param maxVal end of range (including)
- * @param bias the bias value to test
- * @return the number of needed bytes
- */
- private static int testBias(long minVal, long maxVal, int bias) {
- long minVal2 = minVal - bias;
- long maxVal2 = maxVal - bias;
- int test = calcNeededBytes(minVal2, maxVal2);
- return test;
+ ChunkMem mem = getMem(currentChunkId);
+ if (mem == null) {
+ long topID = currentChunkId >> TOP_ID_SHIFT;
+ mem = new ChunkMem(topID);
+ topMap.put(topID, mem);
+ currentMem = mem;
+ }
+ mem.putChunk(currentChunkId, bufEncoded);
+ if (SELF_TEST) {
+ Arrays.fill(testChunk, unassigned);
+ decodeStoredChunk(currentChunkId, testChunk, -1);
+ for (int i = 0; i < CHUNK_SIZE; i++) {
+ if (testChunk[i] != currentChunk[i]) {
+ assert false : "current chunk id=" + currentChunkId + " key=" + (currentChunkId + i)
+ + " doesn't match " + testChunk[i] + "<>" + currentChunk[i];
+ }
+ }
+ }
}
/**
@@ -423,7 +647,7 @@ public final class SparseLong2IntMap {
* @param maxVal highest value
* @return number of needed bytes
*/
- static int calcNeededBytes (long minVal, long maxVal) {
+ static int bytesNeeded (long minVal, long maxVal) {
if (minVal >= Byte.MIN_VALUE && maxVal <= Byte.MAX_VALUE) {
return Byte.BYTES;
} else if (minVal >= Short.MIN_VALUE && maxVal <= Short.MAX_VALUE) {
@@ -481,134 +705,191 @@ public final class SparseLong2IntMap {
* @param mp the MemPos instance with information about the store
* @param targetChunk if not null, data will be decoded into this buffer
* @param chunkOffset gives the wanted element (targetChunk must be null)
- * @return
+ * @return the extracted value or unassigned
*/
- private int decodeStoredChunk (MemPos mp, int[] targetChunk, int chunkOffset) {
- int chunkLen = mp.x + 1;
- ByteBuffer inBuf = mp.getInBuf();
+ private int decodeStoredChunk (long key, int[] targetChunk, int chunkOffset) {
+ ChunkMem mem = getMem(key);
+ if (mem == null)
+ return unassigned;
+ ByteBuffer inBuf = mem.getStoredChunk(key, targetChunk == currentChunk);
+ if (inBuf == null)
+ return unassigned;
+ long chunkMask = inBuf.getLong();
+ if (targetChunk == null) {
+ long elementmask = 1L << chunkOffset;
+ if ((chunkMask & elementmask) == 0)
+ return unassigned; // not in chunk
+ // the map contains the key, decode it
+ }
+ int chunkLenNoMask = inBuf.remaining();
+
int flag = 0;
int bytesToUse = Integer.BYTES; // assume worst case
- if (chunkLen == MAX_STORED_BYTES_FOR_CHUNK) {
+ if (chunkLenNoMask == MAX_STORED_BYTES_FOR_CHUNK) {
// special case: no flag is written if we have the max. size
- } else if (chunkLen <= 2) {
- bytesToUse = chunkLen;
+ // all values are written with 4 bytes and without bias
+ if (targetChunk == null) {
+ inBuf.position(inBuf.position() + chunkOffset * bytesToUse);
+ return getVal(inBuf, bytesToUse);
+ }
+ for (int i = 0; i < CHUNK_SIZE; i++) {
+ targetChunk[i] = getVal(inBuf, bytesToUse);
+ }
+ return unassigned;
+ } else if (chunkLenNoMask <= SINGLE_VAL_CHUNK_LEN_NO_FLAG) {
+ bytesToUse = chunkLenNoMask;
} else {
flag = inBuf.get();
- bytesToUse = (flag & FLAG_USED_BYTES_MASK) + 1;
+ if ((flag & FLAG1_COMP_METHOD_BITS) != 0) {
+ inBuf.position(inBuf.position() - 1);
+ int val = decodeBits(chunkMask, targetChunk, chunkOffset, inBuf);
+ return val;
+ }
+ bytesToUse = (flag & FLAG1_USED_BYTES_MASK) + 1;
}
- int bias = bias1;
- int start = bias + getVal(inBuf, bytesToUse);
- boolean singleValueChunk = (chunkLen <= 2 || chunkLen == 1 + bytesToUse);
-
- if (targetChunk == null && singleValueChunk) {
+ int start = bias1 + getVal(inBuf, bytesToUse);
+ boolean isSingleValueChunk = (chunkLenNoMask <= SINGLE_VAL_CHUNK_LEN_NO_FLAG || chunkLenNoMask == 1 + bytesToUse);
+ assert isSingleValueChunk;
+ if (targetChunk == null) {
return start;
}
- long chunkMask = mp.getMask();
+ maskedChunk[0] = start;
+ updateTargetChunk(targetChunk, chunkMask, isSingleValueChunk);
+ return unassigned;
+ }
+
+
+ private void updateTargetChunk(int[] targetChunk, long chunkMask, boolean singleValueChunk) {
+ if (targetChunk == null)
+ return;
+ int j = 0;
+ int opos = 0;
+ while (chunkMask != 0) {
+ if ((chunkMask & 1L) != 0) {
+ targetChunk[opos] = maskedChunk[j];
+ if (!singleValueChunk)
+ j++;
+ }
+ opos++;
+ chunkMask >>>= 1;
+ }
+ }
+
+ /**
+ * Decode a stored chunk written with the {@link BitWriter}.
+ * @param mp
+ * @param targetChunk
+ * @param chunkOffset
+ * @param inBuf
+ * @return
+ */
+ private int decodeBits(long chunkMask, int[] targetChunk, int chunkOffset, ByteBuffer inBuf) {
+ int flag1 = inBuf.get();
+ assert (flag1 & FLAG1_COMP_METHOD_BITS) != 0;
int index = CHUNK_SIZE + 1;
if (targetChunk == null) {
// we only want to retrieve one value for the index
index = countUnder(chunkMask, chunkOffset);
- if (index == 0 )
- return start;
}
- int mPos = 0;
- maskedChunk[mPos++] = start;
- // rest of values might be encoded with different number of bytes
- if (chunkLen != MAX_STORED_BYTES_FOR_CHUNK) {
- bytesToUse = ((flag >> 2) & FLAG_USED_BYTES_MASK) + 1;
- if ((flag & FLAG_COMP_METHOD_DELTA) != 0) {
- bias = start;
+ boolean useDict = (flag1 & FLAG1_DICTIONARY) != 0;
+ int flag2 = inBuf.get();
+ int bits = (flag2 & FLAG2_BITS_FOR_VALS) + 1;
+ int sign = 0;
+ if ((flag2 & FLAG2_ALL_POSITIVE) != 0)
+ sign = 1;
+ else if ((flag2 & FLAG2_ALL_NEGATIVE) != 0)
+ sign = -1;
+ boolean dictSizeIs2 = (flag2 & FLAG2_DICT_SIZE_IS_2) != 0;
+
+ assert bits >= 1;
+ BitReader br;
+ int bias = bias1;
+ int val;
+ // read first value
+ int bytesFor1st = (flag1 & FLAG1_USED_BYTES_MASK) + 1;
+ val = getVal(inBuf, bytesFor1st) + bias;
+ bias = val;
+ br = new BitReader(inBuf.array(), inBuf.position());
+ if (index == 0)
+ return val;
+ int dictSize = dictSizeIs2 ? 2: 1;
+ if (useDict) {
+ if (!dictSizeIs2)
+ dictSize = br.get(FLAG_BITS_FOR_DICT_SIZE) + 1;
+ }
+ int[] dict = new int[dictSize];
+ if (useDict) {
+ dict[0] = val;
+ for (int i = 1; i < dictSize; i++) {
+ dict[i] = readVal(br, bits, sign) + bias;
}
}
- int val = start;
- if (targetChunk == null && (flag & FLAG_COMP_METHOD_RLE) == 0) {
- // use shortcut, we can calculate the position of the wanted value
- inBuf.position(inBuf.position() + (index-1) * bytesToUse);
- return val = bias + getVal(inBuf, bytesToUse);
- }
- // loop through the values
- while (inBuf.hasRemaining()) {
- if ((flag & FLAG_COMP_METHOD_RLE) != 0) {
- int runLength = inBuf.get();
- index -= runLength - 1;
- if (index <= 0)
- return val;
- while (--runLength > 0) {
- maskedChunk[mPos++] = val;
- }
- if (!inBuf.hasRemaining())
- break;
+ boolean useRLE = (flag1 & FLAG1_COMP_METHOD_RLE) != 0;
+ int bitsForPos = bitsNeeded(dictSize - 1) - 1;
+
+ if (targetChunk == null && !useRLE) {
+ // shortcut: we can calculate the position of the value in the bit stream
+ if (useDict) {
+ br.skip((index-1) * bitsForPos);
+ int dictPos = br.get(bitsForPos);
+ return dict[dictPos];
}
- val = bias + getVal(inBuf, bytesToUse);
- if (--index <= 0)
- return val;
- maskedChunk[mPos++] = val;
-
+ // unlikely
+ int bitsToUse = bits - Math.abs(sign);
+ br.skip((index-1) * bitsToUse);
+ return readVal(br, bits, sign) + bias;
}
- if (targetChunk != null) {
- int j = 0;
- int opos = 0;
- while (chunkMask != 0) {
- if ((chunkMask & 1) != 0) {
- targetChunk[opos] = maskedChunk[j];
- if (!singleValueChunk) {
- j++;
- }
- }
- opos++;
- chunkMask >>>= 1;
+ int runLength;
+ int bitsForRLE = useRLE ? (flag1 & FLAG1_RUNLEN_MASK) >> 2 : 0;
+ int mPos = 0;
+ int dictPos = 0;
+ int nVals = 0;
+ int n = Long.bitCount(chunkMask);
+ boolean readIndex = dictSize > 2 || !useRLE;
+ while (true) {
+ if (useRLE) {
+ runLength = br.get(bitsForRLE) + 1;
+ nVals += runLength;
+ } else
+ nVals++;
+ if (index < nVals)
+ return val;
+ if (targetChunk != null) {
+ do {
+ maskedChunk[mPos++] = val;
+ } while (mPos < nVals);
+ }
+ if (nVals >= n)
+ break;
+ if (useDict) {
+ dictPos = readIndex ? br.get(bitsForPos) : (dictPos == 0) ? 1 : 0;
+ ;
+ val = dict[dictPos];
+ } else {
+ val = readVal(br, bits, sign) + bias;
}
}
+ updateTargetChunk(targetChunk, chunkMask, false);
return unassigned;
}
/**
- * Use the various bit masks to extract the position of the chunk in the store.
- * @param key the key for which we want the chunk
- * @return the filled MemPos instance or null if the chunk is not in the store.
- */
- private MemPos getMemPos(long key) {
- long topID = (key >> TOP_ID_SHIFT);
- Mem mem = topMap.get(topID);
- if (mem == null)
- return null;
- int chunkid = (int) (key & CHUNK_ID_MASK) / CHUNK_SIZE;
-
- int idx = mem.largeVector[chunkid]; // performance bottleneck: produces many cache misses
- if (idx == 0)
- return null;
- int x = idx & CHUNK_STORE_X_MASK;
- int y = (idx >> CHUNK_STORE_Y_SHIFT) & CHUNK_STORE_Y_MASK;
- y--; // we store the y value incremented by 1
- assert y < LARGE_VECTOR_SIZE;
- int z = (idx >> CHUNK_STORE_Z_SHIFT) & CHUNK_STORE_Z_MASK;
- return new MemPos(mem, idx, x, y, z);
- }
-
- /**
* Check if we already have a chunk for the given key. If no,
* fill currentChunk with default value, else with the saved
* chunk.
* @param key the key for which we need the current chunk
*/
private void replaceCurrentChunk(long key) {
-
saveCurrentChunk();
Arrays.fill(currentChunk, unassigned);
oldModCount = modCount;
currentChunkId = key & OLD_CHUNK_ID_MASK;
- storedLengthOfCurrentChunk = 0;
- currentChunkIdInStore = 0;
- MemPos mp = getMemPos(key);
- if (mp == null)
- return;
-
- currentChunkIdInStore = mp.largeVectorIndex;
- storedLengthOfCurrentChunk = mp.x;
- decodeStoredChunk(mp, currentChunk, -1);
+
+ decodeStoredChunk(key, currentChunk, -1);
}
+
/**
* Returns the value to which the given key is mapped or the {@code unassigned} value.
* @param key the key
@@ -621,16 +902,7 @@ public final class SparseLong2IntMap {
if (currentChunkId == chunkId) {
return currentChunk[chunkoffset];
}
- MemPos mp = getMemPos(key);
- if (mp == null)
- return unassigned;
-
- long chunkMask = mp.getMask();
- long elementmask = 1L << chunkoffset;
- if ((chunkMask & elementmask) == 0)
- return unassigned; // not in chunk
- // the map contains the key, decode it
- return decodeStoredChunk(mp, null, chunkoffset);
+ return decodeStoredChunk(key, null, chunkoffset);
}
public void clear() {
@@ -638,9 +910,8 @@ public final class SparseLong2IntMap {
Arrays.fill(currentChunk, 0);
Arrays.fill(maskedChunk, 0);
- storedLengthOfCurrentChunk = 0;
- currentChunkIdInStore = 0;
currentChunkId = INVALID_CHUNK_ID;
+ currentMem = null;
bias1 = null;
size = 0;
// test();
@@ -658,118 +929,38 @@ public final class SparseLong2IntMap {
unassigned = arg0;
}
- private void putChunk(long key, ByteBuffer bb, long mask) {
- long topID = key >> TOP_ID_SHIFT;
- Mem mem = topMap.get(topID);
- if (mem == null) {
- mem = new Mem(topID);
- topMap.put(topID, mem);
- }
-
- int chunkid = (int) (key & CHUNK_ID_MASK) / CHUNK_SIZE;
- int len = bb.limit();
- int x = len - 1;
- if (storedLengthOfCurrentChunk > 0) {
- // this is a rewrite, add the previously used chunk to the reusable list
- IntArrayList reusableChunk = mem.reusableChunks.get(storedLengthOfCurrentChunk);
- if (reusableChunk == null) {
- reusableChunk = new IntArrayList(8);
- mem.reusableChunks.put(storedLengthOfCurrentChunk, reusableChunk);
- mem.estimatedBytes += 8 * Integer.BYTES + 24 + Integer.BYTES + POINTER_SIZE + 16; // for the IntArrayList instance
- mem.estimatedBytes += 20; // estimate for the hash map entry
- }
- reusableChunk.add(currentChunkIdInStore);
- }
- if (mem.chunkStore[x] == null) {
- mem.startStore(x);
- }
- IntArrayList reusableChunk = mem.reusableChunks.get(x);
- int y, z;
- byte[] store;
- if (reusableChunk != null && !reusableChunk.isEmpty()) {
- int reusedIdx = reusableChunk.removeInt(reusableChunk.size() - 1);
- y = (reusedIdx >> CHUNK_STORE_Y_SHIFT) & CHUNK_STORE_Y_MASK;
- y--; // we store the y value incremented by 1
- z = (reusedIdx >> CHUNK_STORE_Z_SHIFT) & CHUNK_STORE_Z_MASK;
- store = mem.chunkStore[x][y];
- } else {
- y = ++mem.freePosInStore[x] / CHUNK_STORE_ELEMS;
- if (y >= mem.chunkStore[x].length)
- mem.grow(x);
- if (mem.chunkStore[x][y] == null) {
- int numElems = len * CHUNK_STORE_ELEMS + 1;
- mem.chunkStore[x][y] = new byte[numElems];
- mem.estimatedBytes += 24 + (numElems) * Byte.BYTES;
- int padding = 8 - (numElems * Byte.BYTES % 8);
- if (padding < 8)
- mem.estimatedBytes += padding;
- mem.maskStore[x][y] = new long[CHUNK_STORE_ELEMS];
- mem.estimatedBytes += 24 + CHUNK_STORE_ELEMS * Long.BYTES;
- }
- store = mem.chunkStore[x][y];
- z = store[0]++;
- }
-
- mem.maskStore[x][y][z] = mask;
- ByteBuffer storeBuf = ByteBuffer.wrap(store, z * len + 1, len);
- storeBuf.put(bb);
-
- // calculate the position in the large vector
- y++; // we store the y value incremented by 1
- assert x < 1 << CHUNK_STORE_BITS_FOR_X;
- assert y < 1 << CHUNK_STORE_BITS_FOR_Y;
- assert z < 1 << CHUNK_STORE_BITS_FOR_Z;
- int idx = (z & CHUNK_STORE_Z_MASK) << CHUNK_STORE_Z_SHIFT
- | (y & CHUNK_STORE_Y_MASK) << CHUNK_STORE_Y_SHIFT
- | (x & CHUNK_STORE_X_MASK);
-
- assert idx != 0;
- mem.largeVector[chunkid] = idx;
- }
/**
* calculate and print performance values regarding memory.
*/
public void stats(int msgLevel) {
- long totalBytes = currentChunk.length * Integer.BYTES;
- long totalChunks = 1; // current chunk
-
if (size() == 0){
System.out.println(dataDesc + " Map is empty");
return;
}
- int[] all = new int[MAX_STORED_BYTES_FOR_CHUNK];
- int memCount = 1;
-
- for (Mem mem : topMap.values()) {
- for (int x = 0; x < mem.freePosInStore.length; x++) {
- if (mem.freePosInStore[x] == 0)
- continue;
- all[x] += mem.freePosInStore[x];
- if (msgLevel >= 1) {
- System.out.println("mem store no: " + memCount + " len: " + (x+1) + " " + mem.freePosInStore[x]);
- }
- memCount++;
- totalChunks += mem.freePosInStore[x];
- }
+ long totalBytes = currentChunk.length * Integer.BYTES;
+ long totalChunks = 1; // current chunk
+
+ for (ChunkMem mem : topMap.values()) {
+ totalChunks += mem.getChunkCount();
totalBytes += mem.estimatedBytes;
}
-// if (msgLevel >= 0) {
-// for (int x = 0; x < all.length; x++) {
-// if (all[x] != 0)
-// System.out.println("len: " + (x+1) + " " + all[x]);
-// }
-// }
- float bytesPerKey = (size()==0) ? 0: (float)(totalBytes*100 / size()) / 100;
+ float bytesPerKey = (float) (totalBytes * 100 / size()) / 100;
System.out.println(dataDesc + " Map: " + Utils.format(size()) + " stored long/int pairs require ca. " +
bytesPerKey + " bytes per pair. " +
- totalChunks + " chunks are used, the avg. number of values in one "+CHUNK_SIZE+"-chunk is " +
- ((totalChunks==0) ? 0 :(size() / totalChunks)) + ".");
- System.out.println(dataDesc + " Map details: bytes ~" + Utils.format(totalBytes/1024/1024) + " MB, including " +
- topMap.size() + " array(s) with " + LARGE_VECTOR_SIZE * Integer.BYTES/1024/1024 + " MB");
+ Utils.format(totalChunks) + " chunks are used, the avg. number of values in one " + CHUNK_SIZE + "-chunk is " +
+ (totalChunks == 0 ? 0 : (size() / totalChunks)) + ".");
+ if (msgLevel >= 0) {
+ String details = dataDesc + " Map details: ~" + bytesToMB(totalBytes) + ", including " + topMap.size()
+ + " array(s) with " + bytesToMB(LARGE_VECTOR_SIZE * Integer.BYTES);
+ System.out.println(details);
+ }
System.out.println();
}
+ private static String bytesToMB (long bytes) {
+ return ((bytes + (1 << 19)) >>> 20) + " MB";
+ }
/*
void test(){
diff --git a/src/uk/me/parabola/splitter/writer/BinaryMapWriter.java b/src/uk/me/parabola/splitter/writer/BinaryMapWriter.java
index 54725c5..ee78049 100644
--- a/src/uk/me/parabola/splitter/writer/BinaryMapWriter.java
+++ b/src/uk/me/parabola/splitter/writer/BinaryMapWriter.java
@@ -161,11 +161,13 @@ public class BinaryMapWriter extends AbstractOSMWriter {
// }
if (versionMethod != REMOVE_VERSION) {
int version = getWriteVersion(e);
- b.setVersion(version);
- b.setTimestamp(0);
- b.setChangeset(0);
- b.setUid(0);
- b.setUserSid(0);
+ if (version != 0) {
+ b.setVersion(version);
+ b.setTimestamp(0);
+ b.setChangeset(0);
+ b.setUid(0);
+ b.setUserSid(0);
+ }
}
return b;
}
diff --git a/src/uk/me/parabola/splitter/writer/O5mMapWriter.java b/src/uk/me/parabola/splitter/writer/O5mMapWriter.java
index bf048c6..41e946c 100644
--- a/src/uk/me/parabola/splitter/writer/O5mMapWriter.java
+++ b/src/uk/me/parabola/splitter/writer/O5mMapWriter.java
@@ -12,11 +12,8 @@
*/
package uk.me.parabola.splitter.writer;
-import it.unimi.dsi.fastutil.longs.LongArrayList;
-
import java.io.BufferedOutputStream;
import java.io.ByteArrayOutputStream;
-import java.io.DataOutputStream;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
@@ -27,13 +24,14 @@ import java.util.Iterator;
import java.util.Locale;
import java.util.Map;
+import it.unimi.dsi.fastutil.longs.LongArrayList;
import uk.me.parabola.splitter.Area;
import uk.me.parabola.splitter.Element;
import uk.me.parabola.splitter.Node;
import uk.me.parabola.splitter.Relation;
+import uk.me.parabola.splitter.Relation.Member;
import uk.me.parabola.splitter.Utils;
import uk.me.parabola.splitter.Way;
-import uk.me.parabola.splitter.Relation.Member;
/**
* Implements the needed methods to write the result in the o5m format.
@@ -62,7 +60,7 @@ public class O5mMapWriter extends AbstractOSMWriter{
private static final double FACTOR = 10000000;
- private DataOutputStream dos;
+ private OutputStream os;
private byte[][][] stw__tab; // string table
private byte[] s1Bytes;
@@ -74,10 +72,10 @@ public class O5mMapWriter extends AbstractOSMWriter{
private long lastRef[];
private int lastLon,lastLat;
- int lastWrittenDatasetType = 0;
+ private int lastWrittenDatasetType = 0;
// index of last entered element in string table
- short stw__tabi= 0;
+ private short stw__tabi= 0;
// has table; elements point to matching strings in stw__tab[];
// -1: no matching element;
@@ -93,37 +91,37 @@ public class O5mMapWriter extends AbstractOSMWriter{
private byte[] numberConversionBuf;
- final static Map<String, byte[]> wellKnownTagKeys = new HashMap<>();
- final static Map<String, byte[]> wellKnownTagVals = new HashMap<>();
- final static String[] tagKeys = { "1", "1outer", "1inner", "type", // relation specific
- // 50 most often used keys (taken from taginfo 2016-11-20)
- "building", "source",
- "highway", "addr:housenumber", "addr:street", "name",
- "addr:city", "addr:postcode", "natural", "source:date", "addr:country",
- "landuse", "surface", "created_by", "power",
- "tiger:cfcc", "waterway", "tiger:county",
- "start_date", "tiger:reviewed", "wall",
- "amenity", "oneway", "ref:bag", "ref",
- "attribution", "tiger:name_base", "building:levels",
- "maxspeed", "barrier", "tiger:name_type", "height",
- "service", "source:addr", "tiger:tlid", "tiger:source",
- "lanes", "access", "addr:place", "tiger:zip_left",
- "tiger:upload_uuid", "layer", "tracktype",
- "ele", "tiger:separated", "tiger:zip_right",
- "yh:WIDTH", "place", "foot"
- };
- final static String[] tagVals = { "yes", "no", "residential", "garage", "water", "tower",
- "footway", "Bing", "PGS", "private", "stream", "service",
- "house", "unclassified", "track", "traffic_signals","restaurant","entrance"
- };
-
+ private final static Map<String, byte[]> wellKnownTagKeys = new HashMap<>(60, 0.25f);
+ private final static Map<String, byte[]> wellKnownTagVals = new HashMap<>(20, 0.25f);
+
static {
try {
- for (String s : tagKeys) {
+ for (String s : Arrays.asList(
+ "1", "1outer", "1inner", "type", // relation specific
+ // 50 most often used keys (taken from taginfo 2016-11-20)
+ "building", "source",
+ "highway", "addr:housenumber", "addr:street", "name",
+ "addr:city", "addr:postcode", "natural", "source:date", "addr:country",
+ "landuse", "surface", "created_by", "power",
+ "tiger:cfcc", "waterway", "tiger:county",
+ "start_date", "tiger:reviewed", "wall",
+ "amenity", "oneway", "ref:bag", "ref",
+ "attribution", "tiger:name_base", "building:levels",
+ "maxspeed", "barrier", "tiger:name_type", "height",
+ "service", "source:addr", "tiger:tlid", "tiger:source",
+ "lanes", "access", "addr:place", "tiger:zip_left",
+ "tiger:upload_uuid", "layer", "tracktype",
+ "ele", "tiger:separated", "tiger:zip_right",
+ "yh:WIDTH", "place", "foot"
+ )) {
wellKnownTagKeys.put(s, s.getBytes("UTF-8"));
}
- for (String s : tagVals) {
+ for (String s : Arrays.asList(
+ "yes", "no", "residential", "garage", "water", "tower",
+ "footway", "Bing", "PGS", "private", "stream", "service",
+ "house", "unclassified", "track", "traffic_signals","restaurant","entrance"
+ )) {
wellKnownTagVals.put(s, s.getBytes("UTF-8"));
}
} catch (Exception e) {
@@ -138,7 +136,7 @@ public class O5mMapWriter extends AbstractOSMWriter{
}
private void reset() throws IOException{
- dos.write(RESET_FLAG);
+ os.write(RESET_FLAG);
resetVars();
}
@@ -170,9 +168,8 @@ public class O5mMapWriter extends AbstractOSMWriter{
String filename = String.format(Locale.ROOT, "%08d.o5m", mapId);
try {
- FileOutputStream fos = new FileOutputStream(new File(outputDir, filename));
- dos = new DataOutputStream(new BufferedOutputStream(fos));
- dos.write(RESET_FLAG);
+ os = new BufferedOutputStream(new FileOutputStream(new File(outputDir, filename)));
+ os.write(RESET_FLAG);
writeHeader();
writeBBox();
} catch (IOException e) {
@@ -199,16 +196,16 @@ public class O5mMapWriter extends AbstractOSMWriter{
}
private void writeDataset(int fileType, ByteArrayOutputStream stream) throws IOException {
- dos.write(fileType);
- writeUnsignedNum(stream.size(), dos);
- stream.writeTo(dos);
+ os.write(fileType);
+ writeUnsignedNum(stream.size(), os);
+ stream.writeTo(os);
lastWrittenDatasetType = fileType;
}
public void finishWrite() {
try {
- dos.write(EOD_FLAG);
- dos.close();
+ os.write(EOD_FLAG);
+ os.close();
stw__hashtab = null;
stw__tabprev = null;
stw__tabnext = null;
diff --git a/test/func/ArgsTest.java b/test/func/ArgsTest.java
new file mode 100644
index 0000000..b34f26d
--- /dev/null
+++ b/test/func/ArgsTest.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2016
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe, Gerd Petermann
+ * Create date: 2016-12-28
+ */
+package func;
+
+import org.junit.Test;
+
+import func.lib.Outputs;
+import func.lib.TestUtils;
+
+/**
+ * A basic check of various arguments that can be passed in.
+ *
+ * @author Gerd Petermann
+ */
+public class ArgsTest extends Base {
+ @Test
+ public void testHelp() {
+ Outputs outputs = TestUtils.run("--help");
+ outputs.checkNoError();
+ }
+}
diff --git a/test/func/Base.java b/test/func/Base.java
new file mode 100644
index 0000000..98ce597
--- /dev/null
+++ b/test/func/Base.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2008 Steve Ratcliffe
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe
+ * Create date: 11-Jan-2009
+ */
+package func;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+
+import org.junit.After;
+import org.junit.Before;
+
+import func.lib.Args;
+import func.lib.TestUtils;
+
+/**
+ * Base class for tests with some useful routines. It ensures that created
+ * files are deleted before the test starts.
+ *
+ * @author Steve Ratcliffe
+ */
+public class Base {
+ @Before
+ public void baseSetup() {
+ TestUtils.deleteOutputFiles();
+ }
+
+ @After
+ public void baseTeardown() {
+ TestUtils.closeFiles();
+ }
+}
diff --git a/test/func/SolverAndProblemGeneratorTest.java b/test/func/SolverAndProblemGeneratorTest.java
new file mode 100644
index 0000000..ab3d2be
--- /dev/null
+++ b/test/func/SolverAndProblemGeneratorTest.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C)
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Gerd Petermann
+ * Create date: 2017-01-10
+ */
+package func;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+
+import org.junit.Test;
+
+import func.lib.Args;
+import uk.me.parabola.splitter.Main;
+
+
+/**
+ * Compare file sizes with expected results. A very basic check that the size of
+ * the output files has not changed. This can be used to make sure that a change
+ * that is not expected to change the output does not do so.
+ *
+ * The sizes will have to be always changed when the output does change though.
+ *
+ *
+ * @author Gerd Petermann
+ */
+public class SolverAndProblemGeneratorTest extends Base {
+
+ /**
+ * @throws IOException
+ */
+ @Test
+ public void testHamburg() throws IOException {
+ runSplitter(Args.expectedHamburg, "--stop-after=gen-problem-list", Args.HAMBURG);
+ }
+
+ @Test
+ public void testAlaska() throws IOException {
+ runSplitter(Args.expectedAlaska,"--stop-after=gen-problem-list", Args.ALASKA);
+ }
+
+ @Test
+ public void testAlaskaOverlap() throws IOException {
+ runSplitter(Args.expectedAlaskaOverlap,"--stop-after=split","--keep-complete=false", Args.ALASKA);
+ }
+
+ @Test
+ /** verifies that --max-areas has no effect on the output */
+ public void testAlaskaMaxAreas7() throws IOException {
+ runSplitter(Args.expectedAlaska,"--stop-after=gen-problem-list","--max-areas=5", Args.ALASKA);
+ }
+
+
+ private static void runSplitter(Map<String, Integer> expected, String... optArgs) throws IOException {
+ List<String> argsList = new ArrayList<>(Arrays.asList(Args.MAIN_ARGS));
+ for (String arg : optArgs)
+ argsList.add(arg);
+
+ Main.mainNoSystemExit(argsList.toArray(new String[argsList.size()]));
+
+ for (Entry<String, Integer> entry : expected.entrySet()) {
+ String f = entry.getKey();
+ long expectedSize = entry.getValue();
+ assertTrue("no " + f + " generated", new File(f).exists());
+ List<String> lines = Files.readAllLines(Paths.get(f, ""));
+ long realSize = 0;
+ for (String l : lines) {
+ realSize += l.length();
+ }
+ assertEquals(f + " has wrong size", expectedSize, realSize);
+ }
+ }
+
+ @Test
+ public void testNoSuchFile() {
+ Main.mainNoSystemExit("no-such-file-xyz.osm");
+ assertFalse("no file generated", new File(Args.DEF_AREAS_LIST).exists());
+ }
+
+}
diff --git a/test/func/lib/Args.java b/test/func/lib/Args.java
new file mode 100644
index 0000000..ea78f10
--- /dev/null
+++ b/test/func/lib/Args.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2017
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Gerd Petermann
+ * Create date: 2017-01-10
+ */
+package func.lib;
+
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+/**
+ * Useful constants that are used for arguments etc. in the functional
+ * tests.
+ *
+ * @author Gerd Petermann
+ */
+public interface Args {
+ public static final String TEST_RESOURCE_OSM = "test/resources/in/osm/";
+
+ public static final String DEF_TEMPLATE = "template.args";
+ public static final String DEF_DENSITIES = "densities-out.txt";
+ public static final String DEF_AREAS_KML = "areas.kml";
+ public static final String DEF_AREAS_LIST = "areas.list";
+ public static final String DEF_AREAS_POLY = "areas.poly";
+ public static final String DEF_PROBLEM_LIST = "problem.list";
+
+ public static final String[] MAIN_ARGS = { "--status-freq=0",
+ "--write-kml=" + DEF_AREAS_KML,
+ "--problem-report=" + DEF_PROBLEM_LIST,
+ "--max-nodes=500000",
+ };
+
+ public static final String ALASKA = TEST_RESOURCE_OSM + "alaska-2016-12-27.osm.pbf";
+ public static final String HAMBURG = TEST_RESOURCE_OSM + "hamburg-2016-12-26.osm.pbf";
+
+ /** expected summed line sizes for ALASKA file */
+ public static final Map<String, Integer> expectedAlaska = new LinkedHashMap<String, Integer>() {
+ {
+ put(DEF_AREAS_KML, 5158);
+ put(DEF_AREAS_LIST, 1076);
+ put(DEF_AREAS_POLY, 371);
+ put(DEF_DENSITIES, 769055);
+ put(DEF_PROBLEM_LIST, 12157);
+ put(DEF_TEMPLATE, 930);
+ }
+ };
+
+ /** expected summed line sizes for ALASKA file */
+ public static final Map<String, Integer> expectedAlaskaOverlap = new LinkedHashMap<String, Integer>() {
+ {
+ putAll(expectedAlaska);
+ remove(DEF_PROBLEM_LIST);
+ }
+ };
+
+ /** expected summed line sizes for HAMBURG file */
+ public static final Map<String, Integer> expectedHamburg = new LinkedHashMap<String, Integer>() {
+ {
+ put(DEF_AREAS_KML, 3143);
+ put(DEF_AREAS_LIST, 616);
+ put(DEF_AREAS_POLY, 204);
+ put(DEF_DENSITIES, 2157);
+ put(DEF_PROBLEM_LIST, 51017);
+ put(DEF_TEMPLATE, 662);
+ }
+ };
+}
diff --git a/test/func/lib/Outputs.java b/test/func/lib/Outputs.java
new file mode 100644
index 0000000..13df24d
--- /dev/null
+++ b/test/func/lib/Outputs.java
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2008 Steve Ratcliffe
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe
+ * Create date: 11-Jan-2009
+ */
+package func.lib;
+
+import static org.junit.Assert.*;
+
+/**
+ * Standard output and error as produced during a run.
+ *
+ * @author Steve Ratcliffe
+ */
+public class Outputs {
+ private final String out;
+ private final String err;
+
+ public Outputs(String out, String err) {
+ this.out = out;
+ this.err = err;
+ }
+
+ protected String getOut() {
+ return out;
+ }
+
+ protected String getErr() {
+ return err;
+ }
+
+ /**
+ * Check that the standard error is empty.
+ */
+ public void checkNoError() {
+ assertEquals("no error output", "", getErr());
+ }
+
+ /**
+ * Check that the output contains the given strings. You can specify
+ * any number of strings.
+ * @param strings The list of strings to check.
+ */
+ public void checkOutput(String... strings) {
+ String out = getOut();
+ for (String s : strings) {
+ if (!out.contains(s)) {
+ // Test has failed. Construct an assertion that will print
+ // something that is useful to show the problem.
+ assertEquals("contains '" + s + "'",
+ "..." + s + "...",
+ out);
+ }
+ }
+ }
+
+ /**
+ * Check that the output contains the given strings. You can specify
+ * any number of strings.
+ * @param strings The list of strings to check.
+ */
+ public void checkError(String... strings) {
+ String err = getErr();
+ for (String s : strings) {
+ if (!err.contains(s)) {
+ // Test has failed. Construct an assertion that will print
+ // something that is useful to show the problem.
+ assertEquals("contains '" + s + "'",
+ "..." + s + "...",
+ err);
+ }
+ }
+ }
+}
diff --git a/test/func/lib/TestUtils.java b/test/func/lib/TestUtils.java
new file mode 100644
index 0000000..9633052
--- /dev/null
+++ b/test/func/lib/TestUtils.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2008 Steve Ratcliffe
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe
+ * Create date: 10-Jan-2009
+ */
+package func.lib;
+
+import static org.junit.Assert.assertTrue;
+
+import java.io.ByteArrayOutputStream;
+import java.io.Closeable;
+import java.io.File;
+import java.io.IOException;
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.List;
+
+import uk.me.parabola.splitter.Main;
+
+/**
+ * Useful routines to use during the functional tests.
+ *
+ * @author Steve Ratcliffe
+ * @author Gerd Petermann
+ */
+public class TestUtils {
+ private static final List<String> files = new ArrayList<>();
+ private static final Deque<Closeable> open = new ArrayDeque<>();
+
+ static {
+ files.add(Args.DEF_AREAS_KML);
+ files.add(Args.DEF_AREAS_LIST);
+ files.add(Args.DEF_AREAS_POLY);
+ files.add(Args.DEF_PROBLEM_LIST);
+ files.add(Args.DEF_DENSITIES);
+ files.add(Args.DEF_TEMPLATE);
+
+ Runnable r = new Runnable() {
+ public void run() {
+ deleteOutputFiles();
+ }
+ };
+ Thread t = new Thread(r);
+ Runtime.getRuntime().addShutdownHook(t);
+ }
+
+ /**
+ * Delete output files that were created by the tests.
+ * Used to clean up before/after a test.
+ */
+ public static void deleteOutputFiles() {
+ for (String fname : files) {
+ File f = new File(fname);
+
+ if (f.exists())
+ assertTrue("delete existing file: " + f.getName(), f.delete());
+ }
+ }
+
+ public static void closeFiles() {
+ while (!open.isEmpty()) {
+ try {
+ open.remove().close();
+ } catch (IOException e) {
+ e.printStackTrace();
+ }
+ }
+ }
+
+ public static void registerFile(String ... names) {
+ Collections.addAll(files, names);
+ }
+
+ public static void registerFile(Closeable... fileList) {
+ Collections.addAll(open, fileList);
+ }
+
+ /**
+ * Run with a single argument. The standard arguments are added first.
+ * @param arg The argument.
+ */
+ public static Outputs run(String arg) {
+ return run(new String[] {arg});
+ }
+
+ /**
+ * Run with the given args. Some standard arguments are added first.
+ *
+ * To run without the standard args, use runRaw().
+ * @param in The arguments to use.
+ */
+ public static Outputs run(String ... in) {
+ List<String> args = new ArrayList<>(Arrays.asList(in));
+
+ OutputStream outsink = new ByteArrayOutputStream();
+ PrintStream out = new PrintStream(outsink);
+
+ OutputStream errsink = new ByteArrayOutputStream();
+ PrintStream err = new PrintStream(errsink);
+
+ PrintStream origout = System.out;
+ PrintStream origerr = System.err;
+
+ try {
+ System.setOut(out);
+ System.setErr(err);
+ Main.mainNoSystemExit(args.toArray(new String[args.size()]));
+ } finally {
+ out.close();
+ err.close();
+ System.setOut(origout);
+ System.setErr(origerr);
+ }
+
+ return new Outputs(outsink.toString(), errsink.toString());
+ }
+
+}
diff --git a/test/func/package.html b/test/func/package.html
new file mode 100644
index 0000000..417bf37
--- /dev/null
+++ b/test/func/package.html
@@ -0,0 +1,5 @@
+<body>
+<h3>Functional tests</h3>
+<p>Functional tests that make complete runs of splitter and examine the
+resultant files in some way.</p>
+</body>
\ No newline at end of file
diff --git a/test/uk/me/parabola/splitter/TestAreaSet.java b/test/uk/me/parabola/splitter/AreaSetTest.java
similarity index 64%
rename from test/uk/me/parabola/splitter/TestAreaSet.java
rename to test/uk/me/parabola/splitter/AreaSetTest.java
index e7babf2..0123b3b 100644
--- a/test/uk/me/parabola/splitter/TestAreaSet.java
+++ b/test/uk/me/parabola/splitter/AreaSetTest.java
@@ -13,15 +13,14 @@
package uk.me.parabola.splitter;
-import org.testng.Assert;
-import org.testng.annotations.Test;
+import static org.junit.Assert.assertEquals;
-import uk.me.parabola.splitter.AreaSet;
+import org.junit.Test;
/**
* Unit tests for the sparse BitSet implementation
*/
-public class TestAreaSet {
+public class AreaSetTest {
private final int NUM = 10000;
private final int[] POS = { 1, 63, 64, 65, 4711, 78231};
@@ -34,17 +33,17 @@ public class TestAreaSet {
public void testAreaSetSequential() {
AreaSet set = new AreaSet();
for (int i = 1; i < NUM; i++) {
- Assert.assertEquals(set.get(i), false, "get(" + i + ")");
+ assertEquals("get(" + i + ")", false, set.get(i));
}
for (int i = 1; i < NUM; i++) {
set.set(i);
- Assert.assertEquals(set.get(i), true, "get(" + i + ")");
+ assertEquals("get(" + i + ")", true, set.get(i));
}
- Assert.assertEquals(set.cardinality(), NUM - 1, "cardinality() returns wrong value");
+ assertEquals("cardinality() returns wrong value", NUM - 1, set.cardinality());
for (int i = 1; i < NUM; i++) {
set.clear(i);
- Assert.assertEquals(set.get(i), false, "get(" + i + ")");
- Assert.assertEquals(set.cardinality(), NUM - i - 1, "cardinality() returns wrong value");
+ assertEquals("get(" + i + ")", false, set.get(i));
+ assertEquals("cardinality() returns wrong value", NUM - i - 1, set.cardinality());
}
}
@@ -54,13 +53,12 @@ public class TestAreaSet {
AreaSet set = new AreaSet();
for (int i : POS) {
set.set(i);
- Assert.assertEquals(set.get(i), true, "get(" + i + ")");
- Assert.assertEquals(set.cardinality(), 1, "cardinality() returns wrong value");
+ assertEquals("get(" + i + ")", true, set.get(i));
+ assertEquals("cardinality() returns wrong value", 1, set.cardinality());
set.clear(i);
- Assert.assertEquals(set.get(i), false, "get(" + i + ")");
- Assert.assertEquals(set.cardinality(), 0, "cardinality() returns wrong value");
+ assertEquals("get(" + i + ")", false, set.get(i));
+ assertEquals("cardinality() returns wrong value", 0, set.cardinality());
}
-
}
@Test
diff --git a/test/uk/me/parabola/splitter/TestConvert.java b/test/uk/me/parabola/splitter/ConvertTest.java
similarity index 84%
rename from test/uk/me/parabola/splitter/TestConvert.java
rename to test/uk/me/parabola/splitter/ConvertTest.java
index 0f223d2..fda5e7f 100644
--- a/test/uk/me/parabola/splitter/TestConvert.java
+++ b/test/uk/me/parabola/splitter/ConvertTest.java
@@ -1,8 +1,8 @@
-/*
- * Copyright (c) 2009, Chris Miller
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 3 as
+/*
+ * Copyright (c) 2009, Chris Miller
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 3 as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
@@ -13,13 +13,14 @@
package uk.me.parabola.splitter;
-import org.testng.Assert;
-import org.testng.annotations.Test;
+import static org.junit.Assert.assertEquals;
+
+import org.junit.Test;
/**
* Unit tests for the rounding up/down utility methods.
*/
-public class TestConvert {
+public class ConvertTest {
@Test
public void testParseDouble() {
parse("0");
@@ -52,7 +53,9 @@ public class TestConvert {
parse("120.1234567890123456789012345678");
}
- private void parse(String dbl) {
- Assert.assertEquals(Convert.parseDouble(dbl), Double.parseDouble(dbl), "Double parsing failed when parsing " + dbl);
- }
-}
+ private static void parse(String dbl) {
+ final double epsilon = 3.0e-10;
+ assertEquals("Double parsing failed when parsing " + dbl, Double.parseDouble(dbl), Convert.parseDouble(dbl),
+ epsilon);
+ }
+}
diff --git a/test/uk/me/parabola/splitter/TestRounding.java b/test/uk/me/parabola/splitter/RoundingTest.java
similarity index 70%
rename from test/uk/me/parabola/splitter/TestRounding.java
rename to test/uk/me/parabola/splitter/RoundingTest.java
index 9994cc6..63a76be 100644
--- a/test/uk/me/parabola/splitter/TestRounding.java
+++ b/test/uk/me/parabola/splitter/RoundingTest.java
@@ -1,8 +1,8 @@
-/*
- * Copyright (c) 2009, Chris Miller
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 3 as
+/*
+ * Copyright (c) 2009, Chris Miller
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 3 as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
@@ -13,13 +13,14 @@
package uk.me.parabola.splitter;
-import org.testng.Assert;
-import org.testng.annotations.Test;
+import static org.junit.Assert.assertEquals;
+
+import org.junit.Test;
/**
* Unit tests for the rounding up/down utility methods.
*/
-public class TestRounding {
+public class RoundingTest {
@Test
public void testPositiveRoundingDown() {
for (int i = 0; i < 50000; i += 19) {
@@ -77,18 +78,24 @@ public class TestRounding {
testRound(-5, 2, -4);
}
- private void testRoundDown(int value, int shift, int outcome) {
- Assert.assertEquals(RoundingUtils.roundDown(value, shift), outcome, "Before: " + Integer.toHexString(value) +
- ", After: " + Integer.toHexString(RoundingUtils.roundDown(value, shift)));
+ private static void testRoundDown(int value, int shift, int outcome) {
+ assertEquals(
+ "Before: " + Integer.toHexString(value) + ", After: "
+ + Integer.toHexString(RoundingUtils.roundDown(value, shift)),
+ outcome, RoundingUtils.roundDown(value, shift));
}
- private void testRoundUp(int value, int shift, int outcome) {
- Assert.assertEquals(RoundingUtils.roundUp(value, shift), outcome, "Before: " + Integer.toHexString(value) +
- ", After: " + Integer.toHexString(RoundingUtils.roundUp(value, shift)));
+ private static void testRoundUp(int value, int shift, int outcome) {
+ assertEquals(
+ "Before: " + Integer.toHexString(value) + ", After: "
+ + Integer.toHexString(RoundingUtils.roundUp(value, shift)),
+ outcome, RoundingUtils.roundUp(value, shift));
}
- private void testRound(int value, int shift, int outcome) {
- Assert.assertEquals(RoundingUtils.round(value, shift), outcome, "Before: " + Integer.toHexString(value) +
- ", After: " + Integer.toHexString(RoundingUtils.round(value, shift)));
- }
-}
+ private static void testRound(int value, int shift, int outcome) {
+ assertEquals(
+ "Before: " + Integer.toHexString(value) + ", After: "
+ + Integer.toHexString(RoundingUtils.round(value, shift)),
+ outcome, RoundingUtils.round(value, shift));
+ }
+}
diff --git a/test/uk/me/parabola/splitter/geo/TestCityFinder.java b/test/uk/me/parabola/splitter/geo/CityFinderTest.java
similarity index 78%
rename from test/uk/me/parabola/splitter/geo/TestCityFinder.java
rename to test/uk/me/parabola/splitter/geo/CityFinderTest.java
index 69d01f6..b72c0fc 100644
--- a/test/uk/me/parabola/splitter/geo/TestCityFinder.java
+++ b/test/uk/me/parabola/splitter/geo/CityFinderTest.java
@@ -1,8 +1,8 @@
-/*
- * Copyright (c) 2009, Chris Miller
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 3 as
+/*
+ * Copyright (c) 2009, Chris Miller
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 3 as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
@@ -16,34 +16,35 @@ package uk.me.parabola.splitter.geo;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
+import static org.junit.Assert.assertEquals;
+
+import org.junit.Test;
-import org.testng.Assert;
-import org.testng.annotations.Test;
/**
* Unit tests for the CityFinder interface
*
* @author Chris Miller
*/
-public class TestCityFinder {
+public class CityFinderTest {
@Test
public void testFinder() {
List<City> cities = getCities();
CityFinder cityFinder = new DefaultCityFinder(cities);
Collection<City> results = cityFinder.findCities(10,10,10,10);
- Assert.assertEquals(results.size(), 2);
+ assertEquals(2, results.size());
results = cityFinder.findCities(10, -10, 12, 0);
- Assert.assertEquals(results.size(), 1);
- Assert.assertEquals(results.iterator().next().getId(), 0);
+ assertEquals(1, results.size());
+ assertEquals(0, results.iterator().next().getId());
results = cityFinder.findCities(10, -10, 12, -4);
- Assert.assertEquals(results.size(), 0);
+ assertEquals(0, results.size());
}
- public List<City> getCities() {
- List<City> cities = new ArrayList<City>();
+ private static List<City> getCities() {
+ List<City> cities = new ArrayList<>();
cities.add(new City(2, "EF", "Efefef", 10, 10, 100000));
cities.add(new City(1, "CD", "Cdcdcd", 10, 10, 100000));
cities.add(new City(4, "IJ", "Ijijij", 12, 11, 100000));
diff --git a/test/uk/me/parabola/splitter/tools/TestCustomCollections.java b/test/uk/me/parabola/splitter/tools/CustomCollectionsTest.java
similarity index 66%
rename from test/uk/me/parabola/splitter/tools/TestCustomCollections.java
rename to test/uk/me/parabola/splitter/tools/CustomCollectionsTest.java
index 6827407..ca82b2e 100644
--- a/test/uk/me/parabola/splitter/tools/TestCustomCollections.java
+++ b/test/uk/me/parabola/splitter/tools/CustomCollectionsTest.java
@@ -13,6 +13,8 @@
package uk.me.parabola.splitter.tools;
+import static org.junit.Assert.assertEquals;
+
import java.io.IOException;
import java.nio.ByteBuffer;
import java.util.Arrays;
@@ -21,17 +23,11 @@ import java.util.List;
import java.util.Map;
import java.util.Random;
-import org.testng.Assert;
-import org.testng.annotations.Test;
-
-import uk.me.parabola.splitter.tools.Long2IntClosedMap;
-import uk.me.parabola.splitter.tools.Long2IntClosedMapFunction;
-import uk.me.parabola.splitter.tools.SparseLong2IntMap;
-
+import org.junit.Test;
/**
*
*/
-public class TestCustomCollections {
+public class CustomCollectionsTest {
//@Test(expectedExceptions = IllegalArgumentException.class)
//public void testInit() {
@@ -39,26 +35,26 @@ public class TestCustomCollections {
//}
@Test
- public static void testLong2IntMap() {
+ public void testLong2IntMap() {
testMap(new Long2IntClosedMap("test", 10000, -1));
}
private static void testMap(Long2IntClosedMapFunction map) {
int val;
for (int i = 1; i < 1000; i++) {
- int j = map.add((long)i*10, i);
- Assert.assertEquals(j, i-1);
- Assert.assertEquals(map.size(), i);
+ int j = map.add((long) i * 10, i);
+ assertEquals(i - 1, j);
+ assertEquals(i, map.size());
}
for (int i = 1; i < 1000; i++) {
- int pos = map.getKeyPos(i*10);
- Assert.assertEquals(i, pos+1);
+ int pos = map.getKeyPos(i * 10);
+ assertEquals(pos + 1, i);
}
for (int i = 1; i < 1000; i++) {
- val = map.getRandom(i*10);
- Assert.assertEquals(i, val);
+ val = map.getRandom(i * 10);
+ assertEquals(val, i);
}
try {
@@ -71,16 +67,16 @@ public class TestCustomCollections {
try{
val = map.getRandom(5);
} catch (IllegalArgumentException e){
- Assert.assertEquals(e.getMessage(), "random access on sequential-only map requested");
+ assertEquals("random access on sequential-only map requested", e.getMessage());
}
val = map.getSeq(5);
- Assert.assertEquals(val,-1);
+ assertEquals(-1, val);
val = map.getSeq(10);
- Assert.assertEquals(val,1);
+ assertEquals(1, val);
val = map.getSeq(19);
- Assert.assertEquals(val,-1);
+ assertEquals(-1, val);
val = map.getSeq(30);
- Assert.assertEquals(val,3);
+ assertEquals(3, val);
map.finish();
}
@@ -95,13 +91,13 @@ public class TestCustomCollections {
map.put(1, 0); // trigger saving of chunk
key = 128;
for (int val : vals) {
- Assert.assertEquals(map.get(idOffset + key++), val, "values " + vals.toString());
+ assertEquals("values " + vals.toString(), val, map.get(idOffset + key++));
}
map.clear();
}
@Test
- public static void testSparseLong2IntMap() {
+ public void testSparseLong2IntMap() {
ByteBuffer buf = ByteBuffer.allocate(4);
for (int i = 0; i < 32; i++) {
int val = 1 << i;
@@ -114,7 +110,7 @@ public class TestCustomCollections {
buf.clear();
SparseLong2IntMap.putVal(buf, val, bytesToUse);
buf.flip();
- Assert.assertEquals(val, SparseLong2IntMap.getVal(buf, bytesToUse));
+ assertEquals(SparseLong2IntMap.getVal(buf, bytesToUse), val);
}
}
val = ~val;
@@ -127,9 +123,10 @@ public class TestCustomCollections {
testMap(-1L << 35);
}
+ private static int UNASSIGNED = Integer.MIN_VALUE;
private static void testMap(long idOffset) {
SparseLong2IntMap map = new SparseLong2IntMap("test");
- map.defaultReturnValue(Integer.MIN_VALUE);
+ map.defaultReturnValue(UNASSIGNED);
// special patterns
testVals(map, idOffset, Arrays.asList(1,2,1,1,1,2,1,1,2,1,1,2));
@@ -155,79 +152,77 @@ public class TestCustomCollections {
for (int i = 1; i < 1000; i++) {
int j = map.put(idOffset + i, i);
- Assert.assertEquals(j, Integer.MIN_VALUE);
- Assert.assertEquals(map.size(), i);
+ assertEquals(UNASSIGNED, j);
+ assertEquals(i, map.size());
}
for (int i = 1; i < 1000; i++) {
boolean b = map.containsKey(idOffset + i);
- Assert.assertEquals(b, true);
+ assertEquals(true, b);
}
for (int i = 1; i < 1000; i++) {
- Assert.assertEquals(map.get(idOffset + i), i);
+ assertEquals(i, map.get(idOffset + i));
}
// random read access
for (int i = 1; i < 1000; i++) {
int key = (int) Math.max(1, (Math.random() * 1000));
- Assert.assertEquals(map.get(idOffset + key), key);
+ assertEquals(key, map.get(idOffset + key));
}
for (int i = 1000; i < 2000; i++) {
- Assert.assertEquals(map.get(idOffset + i), Integer.MIN_VALUE);
+ assertEquals(UNASSIGNED, map.get(idOffset + i));
}
for (int i = 1000; i < 2000; i++) {
boolean b = map.containsKey(idOffset + i);
- Assert.assertEquals(b, false);
+ assertEquals(false, b);
}
for (int i = 1000; i < 1200; i++) {
int j = map.put(idOffset + i, 333);
- Assert.assertEquals(j, Integer.MIN_VALUE);
- Assert.assertEquals(map.size(), i);
+ assertEquals(UNASSIGNED, j);
+ assertEquals(i, map.size());
}
// random read access 2
- Assert.assertEquals(map.get(idOffset + 1010), 333);
+ assertEquals(333, map.get(idOffset + 1010));
for (int i = 1; i < 1000; i++) {
int key = 1000 + (int) (Math.random() * 200);
-
- Assert.assertEquals(map.get(idOffset + key), 333);
+ assertEquals(333, map.get(idOffset + key));
}
-
for (int i = -2000; i < -1000; i++) {
- Assert.assertEquals(map.get(idOffset + i), Integer.MIN_VALUE);
+ assertEquals(UNASSIGNED, map.get(idOffset + i));
}
for (int i = -2000; i < -1000; i++) {
boolean b = map.containsKey(idOffset + i);
- Assert.assertEquals(b, false);
+ assertEquals(false, b);
}
long mapSize = map.size();
// seq. update existing records
for (int i = 1; i < 1000; i++) {
int j = map.put(idOffset + i, i+333);
- Assert.assertEquals(j, i);
- Assert.assertEquals(map.size(), mapSize);
+ assertEquals(i, j);
+ assertEquals(mapSize, map.size());
}
// random read access 3, update existing entries
for (int i = 1; i < 1000; i++) {
int j = map.put(idOffset + i, i+555);
- Assert.assertEquals(true, j == i+333 | j == i+555);
- Assert.assertEquals(map.size(), mapSize);
+ assertEquals(true, j == i+333 | j == i+555);
+ assertEquals(mapSize, map.size());
}
- Assert.assertEquals(map.get(idOffset + 123456), Integer.MIN_VALUE);
+ assertEquals(UNASSIGNED, map.get(idOffset + 123456));
map.put(idOffset + 123456, 999);
- Assert.assertEquals(map.get(idOffset + 123456), 999);
+ assertEquals(999, map.get(idOffset + 123456));
map.put(idOffset + 123456, 888);
- Assert.assertEquals(map.get(idOffset + 123456), 888);
+ assertEquals(888, map.get(idOffset + 123456));
- Assert.assertEquals(map.get(idOffset - 123456), Integer.MIN_VALUE);
+ assertEquals(UNASSIGNED, map.get(idOffset - 123456));
map.put(idOffset - 123456, 999);
- Assert.assertEquals(map.get(idOffset - 123456), 999);
+ assertEquals(999, map.get(idOffset - 123456));
map.put(idOffset - 123456, 888);
- Assert.assertEquals(map.get(idOffset - 123456), 888);
+ assertEquals(888, map.get(idOffset - 123456));
map.put(idOffset + 3008, 888);
map.put(idOffset + 3009, 888);
map.put(idOffset + 3010, 876);
@@ -249,33 +244,33 @@ public class TestCustomCollections {
// add a very different key
map.put(idOffset + 5000, 889);
map.put(idOffset + 5001, 222);
- Assert.assertEquals(map.get(idOffset + 3008), 889);
- Assert.assertEquals(map.get(idOffset + 3009), 888);
- Assert.assertEquals(map.get(idOffset + 3010), 876);
- Assert.assertEquals(map.get(idOffset + 3011), 876);
- Assert.assertEquals(map.get(idOffset + 3012), 678);
- Assert.assertEquals(map.get(idOffset + 3013), 678);
- Assert.assertEquals(map.get(idOffset + 3014), 678);
- Assert.assertEquals(map.get(idOffset + 4000), 889);
- Assert.assertEquals(map.get(idOffset + 4001), 888);
- Assert.assertEquals(map.get(idOffset + 4002), 876);
- Assert.assertEquals(map.get(idOffset + 4003), 876);
- Assert.assertEquals(map.get(idOffset + 5000), 889);
- Assert.assertEquals(map.get(idOffset + 5001), 222);
+ assertEquals(889, map.get(idOffset + 3008));
+ assertEquals(888, map.get(idOffset + 3009));
+ assertEquals(876, map.get(idOffset + 3010));
+ assertEquals(876, map.get(idOffset + 3011));
+ assertEquals(678, map.get(idOffset + 3012));
+ assertEquals(678, map.get(idOffset + 3013));
+ assertEquals(678, map.get(idOffset + 3014));
+ assertEquals(889, map.get(idOffset + 4000));
+ assertEquals(888, map.get(idOffset + 4001));
+ assertEquals(876, map.get(idOffset + 4002));
+ assertEquals(876, map.get(idOffset + 4003));
+ assertEquals(889, map.get(idOffset + 5000));
+ assertEquals(222, map.get(idOffset + 5001));
map.clear();
// special pattern 1
- Assert.assertEquals(map.put(idOffset + 1, 0), Integer.MIN_VALUE);
- Assert.assertEquals(map.put(idOffset + 65, -1), Integer.MIN_VALUE);
- Assert.assertEquals(map.get(idOffset + 999), Integer.MIN_VALUE);
- Assert.assertEquals(map.get(idOffset + 1), 0);
- Assert.assertEquals(map.get(idOffset + 65), -1);
+ assertEquals(UNASSIGNED, map.put(idOffset + 1, 0));
+ assertEquals(UNASSIGNED, map.put(idOffset + 65, -1));
+ assertEquals(UNASSIGNED, map.get(idOffset + 999));
+ assertEquals(0, map.get(idOffset + 1));
+ assertEquals(-1, map.get(idOffset + 65));
map.clear();
map.put(idOffset + 1, 22);
map.put(idOffset + 5, 22);
map.put(idOffset + 100, 44);
- Assert.assertEquals(map.put(idOffset + 5, 33), 22);
+ assertEquals(22, map.put(idOffset + 5, 33));
map.clear();
@@ -284,8 +279,9 @@ public class TestCustomCollections {
map.put(idOffset + i, i);
}
for (int i = 100_000; i < 110_000; i++) {
- Assert.assertEquals(map.get(idOffset + i), i);
+ assertEquals(i, map.get(idOffset + i));
}
+ map.clear();
Random random = new Random(101);
Map<Long,Integer> ref = new HashMap<>();
// special cases long chunks (all 64 values used and random
@@ -298,15 +294,15 @@ public class TestCustomCollections {
}
// map.stats(0);
ref.entrySet().forEach(e -> {
- long id = e.getKey();
+ long id = e.getKey();
int val = map.get(id);
- Assert.assertEquals(val, (int)e.getValue());
+ assertEquals("id=" + id, (int) e.getValue(), val);
});
ref.clear();
map.clear();
- for (int i = 0; i < 100_00; i++) {
+ for (int i = 0; i < 10_000; i++) {
long id = Math.round((1L << 29) * random.nextDouble());
int val = (-1 * (1 << 20) + (int) Math.round((1 << 20) * random.nextDouble()));
map.put(idOffset + id, val);
@@ -314,9 +310,19 @@ public class TestCustomCollections {
}
// map.stats(0);
ref.entrySet().forEach(e -> {
- long id = e.getKey();
+ long id = e.getKey();
int val = map.get(id);
- Assert.assertEquals(val, (int)e.getValue());
+ assertEquals("id=" + id, (int) e.getValue(), val);
});
+
+ // simulate split where all nodes fall into same tile
+ map.clear();
+ for (int i = 0; i < 1 << 27; i+=64) {
+ map.put(idOffset + i, 12);
+ }
+ assertEquals("id=" + idOffset+ 2048, 12, map.get(idOffset + 2048));
+ assertEquals("id=" + idOffset+ 2048*1024, 12, map.get(idOffset + 2048*1024));
+ assertEquals("id=" + idOffset+ 2048*1024 + 1, UNASSIGNED, map.get(idOffset + 2048*1024+1));
+ return;
}
}
diff --git a/test/uk/me/parabola/splitter/tools/TestSparseBitSet.java b/test/uk/me/parabola/splitter/tools/SparseBitSetTest.java
similarity index 59%
rename from test/uk/me/parabola/splitter/tools/TestSparseBitSet.java
rename to test/uk/me/parabola/splitter/tools/SparseBitSetTest.java
index 5c7a0e6..3f7a592 100644
--- a/test/uk/me/parabola/splitter/tools/TestSparseBitSet.java
+++ b/test/uk/me/parabola/splitter/tools/SparseBitSetTest.java
@@ -13,15 +13,14 @@
package uk.me.parabola.splitter.tools;
-import org.testng.Assert;
-import org.testng.annotations.Test;
-
+import static org.junit.Assert.assertEquals;
import uk.me.parabola.splitter.tools.SparseBitSet;
+import org.junit.Test;
/**
* Unit tests for the sparse BitSet implementation
*/
-public class TestSparseBitSet {
+public class SparseBitSetTest {
private final int NUM = 10000;
private final long[] POS = { 1, 63, 64, 65, 4711, 12345654321L };
@@ -29,17 +28,17 @@ public class TestSparseBitSet {
public void testSparseBitSetSequential() {
SparseBitSet sparseSet = new SparseBitSet();
for (long i = 1; i < NUM; i++) {
- Assert.assertEquals(sparseSet.get(i), false, "get(" + i + ")");
+ assertEquals("get(" + i + ")", false, sparseSet.get(i));
}
for (long i = 1; i < NUM; i++) {
sparseSet.set(i);
- Assert.assertEquals(sparseSet.get(i), true, "get(" + i + ")");
+ assertEquals("get(" + i + ")", true, sparseSet.get(i));
}
- Assert.assertEquals(sparseSet.cardinality(), NUM - 1, "cardinality() returns wrong value");
+ assertEquals("cardinality() returns wrong value", NUM - 1, sparseSet.cardinality());
for (long i = 1; i < NUM; i++) {
sparseSet.clear(i);
- Assert.assertEquals(sparseSet.get(i), false, "get(" + i + ")");
- Assert.assertEquals(sparseSet.cardinality(), NUM - i - 1, "cardinality() returns wrong value");
+ assertEquals("get(" + i + ")", false, sparseSet.get(i));
+ assertEquals("cardinality() returns wrong value", NUM - i - 1, sparseSet.cardinality());
}
}
@@ -49,11 +48,11 @@ public class TestSparseBitSet {
SparseBitSet sparseSet = new SparseBitSet();
for (long i : POS) {
sparseSet.set(i);
- Assert.assertEquals(sparseSet.get(i), true, "get(" + i + ")");
- Assert.assertEquals(sparseSet.cardinality(), 1, "cardinality() returns wrong value");
+ assertEquals("get(" + i + ")", true, sparseSet.get(i));
+ assertEquals("cardinality() returns wrong value", 1, sparseSet.cardinality());
sparseSet.clear(i);
- Assert.assertEquals(sparseSet.get(i), false, "get(" + i + ")");
- Assert.assertEquals(sparseSet.cardinality(), 0, "cardinality() returns wrong value");
+ assertEquals("get(" + i + ")", false, sparseSet.get(i));
+ assertEquals("cardinality() returns wrong value", 0, sparseSet.cardinality());
}
}
diff --git a/test/uk/me/parabola/splitter/tools/TestBitReader.java b/test/uk/me/parabola/splitter/tools/TestBitReader.java
new file mode 100644
index 0000000..96dd546
--- /dev/null
+++ b/test/uk/me/parabola/splitter/tools/TestBitReader.java
@@ -0,0 +1,181 @@
+/*
+ * Copyright (C) 2016
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ *
+ * Author: Steve Ratcliffe, Gerd Petermann
+ */
+package uk.me.parabola.splitter.tools;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+
+public class TestBitReader {
+
+ /**
+ * Very simple test that the bit reader is working.
+ * @author Steve Ratcliffe for mkgmap
+ * @author Gerd Petermann
+ */
+ @Test
+ public void testGetBits() {
+ // Add your code here
+ BitReader br = new BitReader(new byte[]{
+ (byte) 0xf1, 0x73, (byte) 0xc2, 0x5
+ });
+
+ assertTrue("first bit", br.get1());
+ assertEquals("five bits", 0x18, br.get(5));
+ assertEquals("four bits", 0xf, br.get(4));
+ assertEquals("sixteen bits", 0x709c, br.get(16));
+ }
+
+ @Test
+ public void testSpecialNegative() {
+ BitReader br = new BitReader(new byte[]{0x24, 0xb});
+
+ int s = br.sget2(3);
+ assertEquals(-12, s);
+ }
+ @Test
+ public void testSpecialNegative2() {
+ BitReader br = new BitReader(new byte[]{0x2c, 0x0});
+
+ int s = br.sget2(3);
+ assertEquals(-6, s);
+ }
+
+ @Test
+ public void testSpecialPositive() {
+ BitReader br = new BitReader(new byte[]{(byte) 0xa4, 0});
+
+ int s = br.sget2(3);
+ assertEquals(8, s);
+ }
+
+ @Test
+ public void testWriteReadSingleBit() {
+ BitWriter bw = new BitWriter();
+ final int testVal = 1231212311;
+ int n = 0;
+
+ int v = testVal;
+ while (v > 0) {
+ bw.put1(v % 2 != 0);
+ v >>= 1;
+ n++;
+ }
+ assertEquals(n, bw.getBitPosition());
+ BitReader br = new BitReader(bw.getBytes());
+ v = testVal;
+ while (n-- > 0) {
+ boolean b = br.get1();
+ assertEquals(v % 2 != 0, b);
+ v >>= 1;
+ }
+ }
+
+ @Test
+ public void testDynAlloc() {
+ BitWriter bw = new BitWriter(10);
+ int n = 0;
+ int bits = 9;
+ for (int i = 0; i < 100; i++) {
+ bw.putn(i, bits);
+ n += bits;
+ }
+ assertEquals(n, bw.getBitPosition());
+ for (int i = 0; i < 100; i++) {
+ bw.put1(i % 3 == 0);
+ n += 1;
+ }
+ assertEquals(n, bw.getBitPosition());
+ }
+
+ @Test
+ public void testWriteReadSigned() {
+ for (int n = 2; n <= 32; n++) {
+ testWriteReadSigned(n);
+ }
+ }
+
+ private static void testWriteReadSigned(int nbits) {
+ int[] TEST_VALS = { Integer.MIN_VALUE, Integer.MIN_VALUE + 1, -40, -1, 0, 1, 40, Integer.MAX_VALUE - 1, Integer.MAX_VALUE };
+ for (int i = 0; i < TEST_VALS.length; i++) {
+ BitWriter bw = new BitWriter();
+ int v = TEST_VALS[i];
+ if (nbits < 30 && (v < -1000 || v > 1000))
+ continue;
+ bw.sputn2(v,nbits);
+ boolean checkSimple = false;
+ if ((1l << (nbits-1)) > Math.abs((long) v) || nbits == 32) {
+ bw.sputn(v, nbits);
+ checkSimple = true;
+ }
+ BitReader br = new BitReader(bw.getBytes());
+
+ int s = br.sget2(nbits);
+ assertEquals("number of bits:" + nbits, v, s);
+ if (checkSimple) {
+ int s2 = br.sget(nbits);
+ assertEquals("number of bits:" + nbits, v, s2);
+
+ }
+ }
+ }
+
+ @Test
+ public void testWriteReadUnsigned() {
+ for (int n = 1; n <= 32; n++) {
+ testWriteReadUnsigned(n);
+ }
+ }
+
+ private static void testWriteReadUnsigned(int nbits) {
+ int[] TEST_VALS = { 0, 1, 40, Integer.MAX_VALUE - 1, Integer.MAX_VALUE };
+ for (int i = 0; i < TEST_VALS.length; i++) {
+ BitWriter bw = new BitWriter();
+ int v = TEST_VALS[i] & (1 << nbits) - 1;
+ bw.putn(v, nbits);
+ BitReader br = new BitReader(bw.getBytes());
+
+ int s = br.get(nbits);
+ assertEquals("number of bits:" + nbits, v, s);
+ }
+ }
+
+ @Test
+ public void positionedRead() {
+ BitReader br = new BitReader(new byte[] { (byte) 0xf1, 0x73, (byte) 0xc2, 0x5 });
+
+ br.position(10);
+ assertEquals("sixteen bits at pos 10", 0x709c, br.get(16));
+
+ }
+
+ @Test
+ public void positionedReadWithOffset() {
+ BitReader br = new BitReader(new byte[] {0, (byte) 0xf1, 0x73, (byte) 0xc2, 0x5}, 1);
+
+ int pos = 10;
+ br.position(pos);
+ assertEquals("sixteen bits at pos " + pos, 0x709c, br.get(16));
+ br.skip(-16);
+ assertEquals("sixteen bits at pos " + pos, 0x709c, br.get(16));
+ br.skip(-2);
+ br.skip(-15);
+ br.skip(1);
+ assertEquals("sixteen bits at pos " + pos, 0x709c, br.get(16));
+ }
+}
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/mkgmap-splitter.git
More information about the Pkg-grass-devel
mailing list