commit 5b1d3bdbce4fb4e233306ba191186d86d5c2a18e
Author: Friedel Schön <[email protected]>
Date: Fri, 1 Dec 2023 11:37:26 +0100
first commit
Diffstat:
51 files changed, 4303 insertions(+), 0 deletions(-)
diff --git a/gradle/wrapper/gradle-wrapper.jar b/gradle/wrapper/gradle-wrapper.jar
Binary files differ.
diff --git a/gradle/wrapper/gradle-wrapper.properties b/gradle/wrapper/gradle-wrapper.properties
@@ -0,0 +1,6 @@
+distributionBase=GRADLE_USER_HOME
+distributionPath=wrapper/dists
+distributionUrl=https\://services.gradle.org/distributions/gradle-7.6-bin.zip
+networkTimeout=10000
+zipStoreBase=GRADLE_USER_HOME
+zipStorePath=wrapper/dists
diff --git a/gradlew b/gradlew
@@ -0,0 +1,244 @@
+#!/bin/sh
+
+#
+# Copyright © 2015-2021 the original authors.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# https://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+##############################################################################
+#
+# Gradle start up script for POSIX generated by Gradle.
+#
+# Important for running:
+#
+# (1) You need a POSIX-compliant shell to run this script. If your /bin/sh is
+# noncompliant, but you have some other compliant shell such as ksh or
+# bash, then to run this script, type that shell name before the whole
+# command line, like:
+#
+# ksh Gradle
+#
+# Busybox and similar reduced shells will NOT work, because this script
+# requires all of these POSIX shell features:
+# * functions;
+# * expansions «$var», «${var}», «${var:-default}», «${var+SET}»,
+# «${var#prefix}», «${var%suffix}», and «$( cmd )»;
+# * compound commands having a testable exit status, especially «case»;
+# * various built-in commands including «command», «set», and «ulimit».
+#
+# Important for patching:
+#
+# (2) This script targets any POSIX shell, so it avoids extensions provided
+# by Bash, Ksh, etc; in particular arrays are avoided.
+#
+# The "traditional" practice of packing multiple parameters into a
+# space-separated string is a well documented source of bugs and security
+# problems, so this is (mostly) avoided, by progressively accumulating
+# options in "$@", and eventually passing that to Java.
+#
+# Where the inherited environment variables (DEFAULT_JVM_OPTS, JAVA_OPTS,
+# and GRADLE_OPTS) rely on word-splitting, this is performed explicitly;
+# see the in-line comments for details.
+#
+# There are tweaks for specific operating systems such as AIX, CygWin,
+# Darwin, MinGW, and NonStop.
+#
+# (3) This script is generated from the Groovy template
+# https://github.com/gradle/gradle/blob/HEAD/subprojects/plugins/src/main/resources/org/gradle/api/internal/plugins/unixStartScript.txt
+# within the Gradle project.
+#
+# You can find Gradle at https://github.com/gradle/gradle/.
+#
+##############################################################################
+
+# Attempt to set APP_HOME
+
+# Resolve links: $0 may be a link
+app_path=$0
+
+# Need this for daisy-chained symlinks.
+while
+ APP_HOME=${app_path%"${app_path##*/}"} # leaves a trailing /; empty if no leading path
+ [ -h "$app_path" ]
+do
+ ls=$( ls -ld "$app_path" )
+ link=${ls#*' -> '}
+ case $link in #(
+ /*) app_path=$link ;; #(
+ *) app_path=$APP_HOME$link ;;
+ esac
+done
+
+# This is normally unused
+# shellcheck disable=SC2034
+APP_BASE_NAME=${0##*/}
+APP_HOME=$( cd "${APP_HOME:-./}" && pwd -P ) || exit
+
+# Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script.
+DEFAULT_JVM_OPTS='"-Xmx64m" "-Xms64m"'
+
+# Use the maximum available, or set MAX_FD != -1 to use that value.
+MAX_FD=maximum
+
+warn () {
+ echo "$*"
+} >&2
+
+die () {
+ echo
+ echo "$*"
+ echo
+ exit 1
+} >&2
+
+# OS specific support (must be 'true' or 'false').
+cygwin=false
+msys=false
+darwin=false
+nonstop=false
+case "$( uname )" in #(
+ CYGWIN* ) cygwin=true ;; #(
+ Darwin* ) darwin=true ;; #(
+ MSYS* | MINGW* ) msys=true ;; #(
+ NONSTOP* ) nonstop=true ;;
+esac
+
+CLASSPATH=$APP_HOME/gradle/wrapper/gradle-wrapper.jar
+
+
+# Determine the Java command to use to start the JVM.
+if [ -n "$JAVA_HOME" ] ; then
+ if [ -x "$JAVA_HOME/jre/sh/java" ] ; then
+ # IBM's JDK on AIX uses strange locations for the executables
+ JAVACMD=$JAVA_HOME/jre/sh/java
+ else
+ JAVACMD=$JAVA_HOME/bin/java
+ fi
+ if [ ! -x "$JAVACMD" ] ; then
+ die "ERROR: JAVA_HOME is set to an invalid directory: $JAVA_HOME
+
+Please set the JAVA_HOME variable in your environment to match the
+location of your Java installation."
+ fi
+else
+ JAVACMD=java
+ which java >/dev/null 2>&1 || die "ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH.
+
+Please set the JAVA_HOME variable in your environment to match the
+location of your Java installation."
+fi
+
+# Increase the maximum file descriptors if we can.
+if ! "$cygwin" && ! "$darwin" && ! "$nonstop" ; then
+ case $MAX_FD in #(
+ max*)
+ # In POSIX sh, ulimit -H is undefined. That's why the result is checked to see if it worked.
+ # shellcheck disable=SC3045
+ MAX_FD=$( ulimit -H -n ) ||
+ warn "Could not query maximum file descriptor limit"
+ esac
+ case $MAX_FD in #(
+ '' | soft) :;; #(
+ *)
+ # In POSIX sh, ulimit -n is undefined. That's why the result is checked to see if it worked.
+ # shellcheck disable=SC3045
+ ulimit -n "$MAX_FD" ||
+ warn "Could not set maximum file descriptor limit to $MAX_FD"
+ esac
+fi
+
+# Collect all arguments for the java command, stacking in reverse order:
+# * args from the command line
+# * the main class name
+# * -classpath
+# * -D...appname settings
+# * --module-path (only if needed)
+# * DEFAULT_JVM_OPTS, JAVA_OPTS, and GRADLE_OPTS environment variables.
+
+# For Cygwin or MSYS, switch paths to Windows format before running java
+if "$cygwin" || "$msys" ; then
+ APP_HOME=$( cygpath --path --mixed "$APP_HOME" )
+ CLASSPATH=$( cygpath --path --mixed "$CLASSPATH" )
+
+ JAVACMD=$( cygpath --unix "$JAVACMD" )
+
+ # Now convert the arguments - kludge to limit ourselves to /bin/sh
+ for arg do
+ if
+ case $arg in #(
+ -*) false ;; # don't mess with options #(
+ /?*) t=${arg#/} t=/${t%%/*} # looks like a POSIX filepath
+ [ -e "$t" ] ;; #(
+ *) false ;;
+ esac
+ then
+ arg=$( cygpath --path --ignore --mixed "$arg" )
+ fi
+ # Roll the args list around exactly as many times as the number of
+ # args, so each arg winds up back in the position where it started, but
+ # possibly modified.
+ #
+ # NB: a `for` loop captures its iteration list before it begins, so
+ # changing the positional parameters here affects neither the number of
+ # iterations, nor the values presented in `arg`.
+ shift # remove old arg
+ set -- "$@" "$arg" # push replacement arg
+ done
+fi
+
+# Collect all arguments for the java command;
+# * $DEFAULT_JVM_OPTS, $JAVA_OPTS, and $GRADLE_OPTS can contain fragments of
+# shell script including quotes and variable substitutions, so put them in
+# double quotes to make sure that they get re-expanded; and
+# * put everything else in single quotes, so that it's not re-expanded.
+
+set -- \
+ "-Dorg.gradle.appname=$APP_BASE_NAME" \
+ -classpath "$CLASSPATH" \
+ org.gradle.wrapper.GradleWrapperMain \
+ "$@"
+
+# Stop when "xargs" is not available.
+if ! command -v xargs >/dev/null 2>&1
+then
+ die "xargs is not available"
+fi
+
+# Use "xargs" to parse quoted args.
+#
+# With -n1 it outputs one arg per line, with the quotes and backslashes removed.
+#
+# In Bash we could simply go:
+#
+# readarray ARGS < <( xargs -n1 <<<"$var" ) &&
+# set -- "${ARGS[@]}" "$@"
+#
+# but POSIX shell has neither arrays nor command substitution, so instead we
+# post-process each arg (as a line of input to sed) to backslash-escape any
+# character that might be a shell metacharacter, then use eval to reverse
+# that process (while maintaining the separation between arguments), and wrap
+# the whole thing up as a single "set" statement.
+#
+# This will of course break if any of these variables contains a newline or
+# an unmatched quote.
+#
+
+eval "set -- $(
+ printf '%s\n' "$DEFAULT_JVM_OPTS $JAVA_OPTS $GRADLE_OPTS" |
+ xargs -n1 |
+ sed ' s~[^-[:alnum:]+,./:=@_]~\\&~g; ' |
+ tr '\n' ' '
+ )" '"$@"'
+
+exec "$JAVACMD" "$@"
diff --git a/gradlew.bat b/gradlew.bat
@@ -0,0 +1,92 @@
+@rem
+@rem Copyright 2015 the original author or authors.
+@rem
+@rem Licensed under the Apache License, Version 2.0 (the "License");
+@rem you may not use this file except in compliance with the License.
+@rem You may obtain a copy of the License at
+@rem
+@rem https://www.apache.org/licenses/LICENSE-2.0
+@rem
+@rem Unless required by applicable law or agreed to in writing, software
+@rem distributed under the License is distributed on an "AS IS" BASIS,
+@rem WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+@rem See the License for the specific language governing permissions and
+@rem limitations under the License.
+@rem
+
+@if "%DEBUG%"=="" @echo off
+@rem ##########################################################################
+@rem
+@rem Gradle startup script for Windows
+@rem
+@rem ##########################################################################
+
+@rem Set local scope for the variables with windows NT shell
+if "%OS%"=="Windows_NT" setlocal
+
+set DIRNAME=%~dp0
+if "%DIRNAME%"=="" set DIRNAME=.
+@rem This is normally unused
+set APP_BASE_NAME=%~n0
+set APP_HOME=%DIRNAME%
+
+@rem Resolve any "." and ".." in APP_HOME to make it shorter.
+for %%i in ("%APP_HOME%") do set APP_HOME=%%~fi
+
+@rem Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script.
+set DEFAULT_JVM_OPTS="-Xmx64m" "-Xms64m"
+
+@rem Find java.exe
+if defined JAVA_HOME goto findJavaFromJavaHome
+
+set JAVA_EXE=java.exe
+%JAVA_EXE% -version >NUL 2>&1
+if %ERRORLEVEL% equ 0 goto execute
+
+echo.
+echo ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH.
+echo.
+echo Please set the JAVA_HOME variable in your environment to match the
+echo location of your Java installation.
+
+goto fail
+
+:findJavaFromJavaHome
+set JAVA_HOME=%JAVA_HOME:"=%
+set JAVA_EXE=%JAVA_HOME%/bin/java.exe
+
+if exist "%JAVA_EXE%" goto execute
+
+echo.
+echo ERROR: JAVA_HOME is set to an invalid directory: %JAVA_HOME%
+echo.
+echo Please set the JAVA_HOME variable in your environment to match the
+echo location of your Java installation.
+
+goto fail
+
+:execute
+@rem Setup the command line
+
+set CLASSPATH=%APP_HOME%\gradle\wrapper\gradle-wrapper.jar
+
+
+@rem Execute Gradle
+"%JAVA_EXE%" %DEFAULT_JVM_OPTS% %JAVA_OPTS% %GRADLE_OPTS% "-Dorg.gradle.appname=%APP_BASE_NAME%" -classpath "%CLASSPATH%" org.gradle.wrapper.GradleWrapperMain %*
+
+:end
+@rem End local scope for the variables with windows NT shell
+if %ERRORLEVEL% equ 0 goto mainEnd
+
+:fail
+rem Set variable GRADLE_EXIT_CONSOLE if you need the _script_ return code instead of
+rem the _cmd.exe /c_ return code!
+set EXIT_CODE=%ERRORLEVEL%
+if %EXIT_CODE% equ 0 set EXIT_CODE=1
+if not ""=="%GRADLE_EXIT_CONSOLE%" exit %EXIT_CODE%
+exit /b %EXIT_CODE%
+
+:mainEnd
+if "%OS%"=="Windows_NT" endlocal
+
+:omega
diff --git a/persolijn/build.gradle b/persolijn/build.gradle
@@ -0,0 +1,19 @@
+plugins {
+ id 'java'
+ id 'application' // using default 'app'-plugin
+ id 'eclipse' // using 'eclipse'-plugin for .project/.classpath/... files
+}
+
+repositories {
+ mavenCentral()
+}
+
+dependencies {
+ implementation project(':protobuf-native')
+}
+
+application {
+ mainClass = 'persolijn.WinschotenTest'
+ applicationDefaultJvmArgs = ['-Xmx12G']
+}
+
diff --git a/persolijn/src/main/java/persolijn/App.java b/persolijn/src/main/java/persolijn/App.java
@@ -0,0 +1,208 @@
+package persolijn;
+
+import java.io.BufferedReader;
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.io.OutputStreamWriter;
+import java.io.PrintWriter;
+import java.io.RandomAccessFile;
+import java.net.ServerSocket;
+import java.net.Socket;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import persolijn.entity.Interval;
+import persolijn.entity.Interval.IntervalFinal;
+import persolijn.entity.Passenger;
+import persolijn.geo.Point;
+import persolijn.osm.BlobSpliterator;
+import persolijn.osm.Graph;
+import persolijn.osm.message.Node;
+import persolijn.planner.Planner;
+import persolijn.planner.PlannerFunction;
+import persolijn.routing.Router;
+
+public class App {
+ public static void main(String[] args) throws FileNotFoundException, IOException, InterruptedException {
+ final Set<Point> garages = Set.of(
+ Point.of(53.20829864, 6.53445395), // Qbuzz Peizerweg
+ Point.of(53.32071373, 6.86684042), // Busstation Appingedam
+ Point.of(53.16379581, 6.38926087), // Leek Centrum
+ Point.of(53.25580130, 6.31031487), // Grijpskerk Station
+ Point.of(53.00901351, 6.75067072), // P+R Gieten
+ Point.of(52.78968295, 6.89922904) // P+R Emmen
+ );
+
+ final List<Passenger<Point>> passengerPoints = List.of(
+ // new Passenger<>(
+ // Point.of(53.1434560, 7.0370678), // 't Rond Winschoten
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(53.2150345, 7.1315000), // Hongerige Wolf
+ // null)
+ // new Passenger<>(
+ // Point.of(52.8501204, 7.0820963), // Ter Apel (Sluis 8)
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(52.9920213, 6.5706176), // Assen Station
+ // null)
+ // new Passenger<>(
+ // Point.of(53.1181842, 6.2524725), // De Wilp
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(53.1546455, 6.7558606), // Vue Hoogezand
+ // null),
+ // new Passenger<>(
+ // Point.of(53.2204108, 6.5756389), // UMCG
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(53.2270684, 6.6012394), // Rijksweg 24
+ // null)
+ new Passenger<>(
+ Point.of(53.2178670, 6.5691509), // Pipoos Groningen
+ Interval.fromInterval(IntervalFinal.START, 30),
+ Point.of(53.1034462, 6.8848578), // Veendam Station
+ null)
+ // new Passenger<>(
+ // Point.of(53.1910220, 6.5486747), // Martini Ziekenhuis
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(53.4095014, 6.6737685), // Uithuizen Station
+ // null),
+ // new Passenger<>(
+ // Point.of(53.0944752, 6.3713491), // Amerika (Een-West)
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(53.1459083, 7.0211043), // Prunuslaan 2
+ // null),
+ // new Passenger<>(
+ // Point.of(53.0936358, 6.6882855), // Zuidlaren Brink
+ // Interval.fromInterval(IntervalFinal.START, 30),
+ // Point.of(53.4105249, 6.1961188), // Lauwersoog Veerhaven
+ // null)
+ );
+
+ List<Point> keepPoints = new ArrayList<>(garages);
+ passengerPoints.forEach(keepPoints::addAll);
+
+ File file = new File("/home/friedel/osm-planet/groningen-drenthe-latest.osm.pbf");
+
+ Graph nodeMap = new BlobSpliterator(new RandomAccessFile(file, "r"),
+ System.out::println)
+ .stream()
+ .flatMap(List::stream)
+ .collect(Graph.asCollector(keepPoints));
+
+ System.out.println();
+
+ for (Point p : garages) {
+ System.out.printf("garage: %s -> %s (%dm)\n",
+ p, nodeMap.getNode(p),
+ Point.distance(p, nodeMap.getNode(p)));
+ }
+
+ for (Passenger<Point> p : passengerPoints) {
+ System.out.printf("start: %s -> %s (%dm)\ntarget: %s -> %s (%dm)\n",
+ p.startPoint, nodeMap.getNode(p.startPoint),
+ Point.distance(p.startPoint, nodeMap.getNode(p.startPoint)),
+ p.targetPoint, nodeMap.getNode(p.targetPoint),
+ Point.distance(p.targetPoint, nodeMap.getNode(p.targetPoint)));
+ }
+
+ List<Node> garageNodes = garages.stream()
+ .map(nodeMap::getNode)
+ .toList();
+
+ Set<Passenger<Node>> passengerNodes = passengerPoints.stream()
+ .map(p -> new Passenger<>(nodeMap.getNode(p.startPoint), p.startTime,
+ nodeMap.getNode(p.targetPoint),
+ p.targetTime))
+ .collect(Collectors.toCollection(HashSet::new));
+
+ System.out.printf("parsing done\n");
+
+ System.out.println();
+
+ // // Rijksweg 24 -> Assen Station
+ // System.out.println(
+ // nodeMap.route(Map.of(nodeMap.getNode(passengerPoints.get(0).targetPoint),
+ // 0l),
+ // nodeMap.getNode(passengerPoints.get(0).startPoint),
+ // 0));
+
+ PlannerFunction<Node, Passenger<Node>, Point> plannerFunction = new Planner();
+
+ /* List<List<Node>> path = */
+
+ garageNodes.stream()
+ .map(g -> plannerFunction.plan(new Router(nodeMap), g, passengerNodes))
+ .filter(Objects::nonNull)
+ .sorted(Comparator.comparingLong(p -> Point.distance(p)))
+ .toList();
+
+ // List<List<Node>> path = garageNodes.stream()
+ // .map(g -> plannerFunction.plan(g, passengerNodes, distanceFunction))
+ // .peek(x -> System.out.println())
+ // .filter(Objects::nonNull)
+ // .sorted(Comparator.comparingLong(p -> Point.distance(p)))
+ // .toList();
+
+ // writeSocket(Stream.concat(passengerNodes.stream()
+ // .flatMap(Passenger::stream), garageNodes.stream())
+ // .toList(), path);
+ }
+
+ public static void writeSocket(List<Node> nodes, List<List<Node>> path)
+ throws IOException, InterruptedException {
+ ServerSocket serverSocket = new ServerSocket(2020);
+ System.out.println("Server running on port: 2020");
+
+ // repeatedly wait for connections, and process
+ // while (true) {
+
+ Socket clientSocket = serverSocket.accept();
+
+ BufferedReader in = new BufferedReader(new InputStreamReader(clientSocket.getInputStream()));
+ PrintWriter out = new PrintWriter(
+ new BufferedWriter(new OutputStreamWriter(clientSocket.getOutputStream())),
+ true);
+
+ // String s;
+ // while ((s = in.readLine()) != null) {
+ // System.out.println(s);
+
+ out.write("HTTP/1.1 200 OK\r\n");
+ out.write("Content-Type: text/plain\r\n");
+ out.write("Access-Control-Allow-Origin: *\r\n");
+ out.write("\r\n");
+
+ int i = 0;
+
+ for (List<Node> p : path) {
+ if (i++ > 0) {
+ out.write('%');
+ }
+
+ out.print(Point.distance(p) / 1000);
+ out.write(';');
+
+ int j = 0;
+ for (Point node : p) {
+ if (j++ > 0)
+ out.write(';');
+ if (nodes.contains(node))
+ out.write('!');
+ out.write(String.format("%f,%f", node.getLatitude(), node.getLongitude()));
+ }
+ }
+
+ Thread.sleep(1000);
+
+ out.close();
+ in.close();
+ clientSocket.close();
+ serverSocket.close();
+ }
+}
diff --git a/persolijn/src/main/java/persolijn/WinschotenTest.java b/persolijn/src/main/java/persolijn/WinschotenTest.java
@@ -0,0 +1,101 @@
+package persolijn;
+
+import java.io.File;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import persolijn.entity.Passenger;
+import persolijn.geo.Point;
+import persolijn.osm.BlobSpliterator;
+import persolijn.osm.Graph;
+import persolijn.osm.message.Node;
+import persolijn.osm.message.Way;
+import persolijn.planner.Planner;
+import persolijn.planner.PlannerFunction;
+import persolijn.routing.Router;
+
+public class WinschotenTest {
+ public static void main(String[] args) throws FileNotFoundException, IOException, InterruptedException {
+ final Set<Point> garages = Set.of(
+ Point.of(53.1393398, 7.0365872) // Winschoten Station
+ );
+
+ final List<Passenger<Point>> passengerPoints = List.of(
+ new Passenger<>(
+ Point.of(53.1559083, 7.0511043), // Prunuslaan 2
+ Point.of(53.1234560, 7.0270678) // 't Rond
+ ));
+
+ List<Point> keepPoints = new ArrayList<>(garages);
+ passengerPoints.forEach(keepPoints::addAll);
+
+ File file = new File("/home/friedel/osm-planet/groningen-latest.osm.pbf");
+
+ Graph nodeMap = new BlobSpliterator(new RandomAccessFile(file, "r"),
+ System.out::println)
+ .stream()
+ .flatMap(List::stream)
+ .collect(Graph.asCollector(keepPoints));
+
+ for (Node n : nodeMap.pointNode.values()) {
+ System.out.printf("%s -> %s\n", n, nodeMap.neighbors.get(n.getID()));
+ for (Way w : nodeMap.neighbors.get(n.getID()).values())
+ System.out.printf(" -> %s\n", w.tags);
+ }
+
+ System.out.println();
+
+ for (Point p : garages) {
+ System.out.printf("garage: %s -> %s (%dm)\n",
+ p, nodeMap.getNode(p),
+ Point.distance(p, nodeMap.getNode(p)));
+ }
+
+ for (Passenger<Point> p : passengerPoints) {
+ System.out.printf("start: %s -> %s (%dm)\ntarget: %s -> %s (%dm)\n",
+ p.startPoint, nodeMap.getNode(p.startPoint),
+ Point.distance(p.startPoint, nodeMap.getNode(p.startPoint)),
+ p.targetPoint, nodeMap.getNode(p.targetPoint),
+ Point.distance(p.targetPoint, nodeMap.getNode(p.targetPoint)));
+ }
+
+ List<Node> garageNodes = garages.stream()
+ .map(nodeMap::getNode)
+ .toList();
+
+ Set<Passenger<Node>> passengerNodes = passengerPoints.stream()
+ .map(p -> new Passenger<>(nodeMap.getNode(p.startPoint), p.startTime,
+ nodeMap.getNode(p.targetPoint),
+ p.targetTime))
+ .collect(Collectors.toCollection(HashSet::new));
+
+ System.out.printf("parsing done\n");
+
+ System.out.println();
+
+ // // Rijksweg 24 -> Assen Station
+ // System.out.println(
+ // nodeMap.route(Map.of(nodeMap.getNode(passengerPoints.get(0).targetPoint),
+ // 0l),
+ // nodeMap.getNode(passengerPoints.get(0).startPoint),
+ // 0));
+
+ PlannerFunction<Node, Passenger<Node>, Point> plannerFunction = new Planner();
+
+ /* List<List<Node>> path = */
+
+ garageNodes.stream()
+ .map(g -> plannerFunction.plan(new Router(nodeMap), g, passengerNodes))
+ .filter(Objects::nonNull)
+ .sorted(Comparator.comparingLong(p -> Point.distance(p)))
+ .toList();
+ }
+}
diff --git a/persolijn/src/main/java/persolijn/common/Container.java b/persolijn/src/main/java/persolijn/common/Container.java
@@ -0,0 +1,9 @@
+package persolijn.common;
+
+public interface Container<T, A> {
+ void accumulate(A value);
+
+ T combine(T other);
+
+ void finish();
+}
diff --git a/persolijn/src/main/java/persolijn/common/ContainerCollector.java b/persolijn/src/main/java/persolijn/common/ContainerCollector.java
@@ -0,0 +1,61 @@
+package persolijn.common;
+
+import java.util.HashSet;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.BinaryOperator;
+import java.util.function.Function;
+import java.util.function.Supplier;
+import java.util.stream.Collector;
+
+public class ContainerCollector<T extends Container<T, A>, A> implements Collector<A, T, T> {
+ public static final int CONCURRENT = 1 << 0;
+ public static final int UNORDERED = 1 << 1;
+ public static final int IDENTITY_FINISH = 1 << 2;
+
+ private final Supplier<T> supplier;
+ private final int characteristics;
+
+ public ContainerCollector(Supplier<T> supplier, int characteristics) {
+ this.supplier = supplier;
+ this.characteristics = characteristics;
+ }
+
+ @Override
+ public Supplier<T> supplier() {
+ return supplier;
+ }
+
+ @Override
+ public BiConsumer<T, A> accumulator() {
+ return Container::accumulate;
+ }
+
+ @Override
+ public BinaryOperator<T> combiner() {
+ return Container::combine;
+ }
+
+ @Override
+ public Function<T, T> finisher() {
+ return c -> {
+ c.finish();
+ return c;
+ };
+ }
+
+ @Override
+ public Set<Characteristics> characteristics() {
+ Set<Characteristics> chars = new HashSet<>();
+ if ((characteristics & CONCURRENT) == 1)
+ chars.add(Characteristics.CONCURRENT);
+
+ if ((characteristics & UNORDERED) == 1)
+ chars.add(Characteristics.UNORDERED);
+
+ if ((characteristics & IDENTITY_FINISH) == 1)
+ chars.add(Characteristics.IDENTITY_FINISH);
+
+ return chars;
+ }
+}
diff --git a/persolijn/src/main/java/persolijn/common/Functions.java b/persolijn/src/main/java/persolijn/common/Functions.java
@@ -0,0 +1,14 @@
+package persolijn.common;
+
+import java.util.function.Function;
+import java.util.function.Supplier;
+
+public abstract class Functions {
+ public static <T> Function<?, T> supplierFunction(Supplier<T> supplier) {
+ return unused -> supplier.get();
+ }
+
+ public static <T> Supplier<T> constantSupplier(T value) {
+ return () -> value;
+ }
+}
diff --git a/persolijn/src/main/java/persolijn/common/RandomAccessFileInputStream.java b/persolijn/src/main/java/persolijn/common/RandomAccessFileInputStream.java
@@ -0,0 +1,44 @@
+package persolijn.common;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.RandomAccessFile;
+
+public class RandomAccessFileInputStream extends InputStream {
+ private final RandomAccessFile file;
+
+ public RandomAccessFileInputStream(RandomAccessFile file) {
+ this.file = file;
+ }
+
+ @Override
+ public int read() throws IOException {
+ return file.read();
+ }
+
+ @Override
+ public int available() throws IOException {
+ long av = file.length() - file.getFilePointer();
+ return av < Integer.MAX_VALUE
+ ? (int) av
+ : Integer.MAX_VALUE;
+
+ }
+
+ @Override
+ public int read(byte[] buffer) throws IOException {
+ return file.read(buffer);
+ }
+
+ @Override
+ public int read(byte[] buffer, int offset, int length) throws IOException {
+ return file.read(buffer, offset, length);
+ }
+
+ @Override
+ public long skip(long size) throws IOException {
+ long fp = file.getFilePointer();
+ file.seek(fp + size);
+ return size;
+ }
+}
diff --git a/persolijn/src/main/java/persolijn/common/TagMap.java b/persolijn/src/main/java/persolijn/common/TagMap.java
@@ -0,0 +1,167 @@
+package persolijn.common;
+
+import java.util.AbstractMap;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+public class TagMap implements Map<String, String> {
+ private final List<String> keys;
+ private final List<String> values;
+
+ public TagMap(List<String> keys, List<String> values) {
+ this.keys = keys;
+ this.values = values;
+ }
+
+ @Override
+ public int size() {
+ return keys.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return keys.isEmpty();
+ }
+
+ @Override
+ public boolean containsKey(Object key) {
+ return keys.contains(key);
+ }
+
+ @Override
+ public boolean containsValue(Object value) {
+ return values.contains(value);
+ }
+
+ @Override
+ public String get(Object key) {
+ if (!containsKey(key))
+ return null;
+
+ int index = keys.indexOf(key);
+ return values.get(index);
+ }
+
+ public int getInt(Object key) {
+ if (!containsKey(key))
+ return 0;
+ return Integer.parseInt(get(key));
+ }
+
+ public long getLong(Object key) {
+ if (!containsKey(key))
+ return 0;
+ return Long.parseLong(get(key));
+ }
+
+ public boolean getBoolean(Object key) {
+ if (!containsKey(key))
+ return false;
+
+ String value = get(key);
+ return switch (value) {
+ case "yes" -> true;
+ case "no" -> false;
+ default -> throw new RuntimeException(String.format("invalid boolean expression for '%s': %s", key, value));
+ };
+ }
+
+ public boolean getBoolean(Object key, Predicate<String> orElse) {
+ if (!containsKey(key))
+ return false;
+
+ String value = get(key);
+ return switch (value) {
+ case "yes" -> true;
+ case "no" -> false;
+ default -> orElse.test(value);
+ };
+ }
+
+ @Override
+ public String put(String key, String value) {
+ if (!containsKey(key)) {
+ keys.add(key);
+ values.add(value);
+ return null;
+ } else {
+ int index = keys.indexOf(key);
+ return values.set(index, value);
+ }
+ }
+
+ @Override
+ public String remove(Object key) {
+ if (!containsKey(key)) {
+ return null;
+ }
+
+ int index = keys.indexOf(key);
+ keys.remove(key);
+ return values.remove(index);
+ }
+
+ @Override
+ public void putAll(Map<? extends String, ? extends String> map) {
+ for (Entry<? extends String, ? extends String> entry : map.entrySet()) {
+ put(entry.getKey(), entry.getValue());
+ }
+ }
+
+ @Override
+ public void clear() {
+ keys.clear();
+ values.clear();
+ }
+
+ @Override
+ public Set<String> keySet() {
+ return Set.copyOf(keys);
+ }
+
+ @Override
+ public Collection<String> values() {
+ return Collections.unmodifiableCollection(values);
+ }
+
+ @Override
+ public Set<Entry<String, String>> entrySet() {
+ return Stream.iterate(0, i -> i < keys.size(), i -> i + 1)
+ .map(i -> new AbstractMap.SimpleImmutableEntry<>(keys.get(i), values.get(i)))
+ .collect(Collectors.toSet());
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder str = new StringBuilder("{ ");
+ boolean first = true;
+
+ for (Entry<String, String> entry : entrySet()) {
+ if (!first) {
+ str.append(", ");
+ }
+ first = false;
+ str.append(entry.getKey());
+ str.append("=");
+ str.append(entry.getValue());
+ }
+
+ str.append(" }");
+
+ return str.toString();
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (other instanceof TagMap otherMap) {
+ return keys.equals(otherMap.keys) && values.equals(otherMap.values);
+ }
+ return false;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/entity/Edge.java b/persolijn/src/main/java/persolijn/entity/Edge.java
@@ -0,0 +1,15 @@
+package persolijn.entity;
+
+import persolijn.osm.message.Node;
+
+public class Edge {
+ public final Node next;
+ public final long distance;
+ public final double time;
+
+ public Edge(Node next, long distance, double time) {
+ this.next = next;
+ this.distance = distance;
+ this.time = time;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/entity/Interval.java b/persolijn/src/main/java/persolijn/entity/Interval.java
@@ -0,0 +1,63 @@
+package persolijn.entity;
+
+public class Interval {
+ public static final long DEFAULT_INTERVAL = 30 * 60; // 30 min
+
+ public static enum IntervalFinal {
+ START,
+ END,
+ NONE
+ }
+
+ public final IntervalFinal isFinal;
+ public final long start;
+ public final long end;
+
+ public Interval(IntervalFinal isFinal, long start, long end) {
+ this.isFinal = isFinal;
+ this.start = start;
+ this.end = end;
+ }
+
+ public static Interval fromInterval(IntervalFinal isFinal, long time) {
+ return fromInterval(isFinal, time, DEFAULT_INTERVAL);
+ }
+
+ public static Interval fromInterval(IntervalFinal isFinal, long time, long offset) {
+ long start, end;
+ switch (isFinal) {
+ case START:
+ start = time;
+ end = time + offset;
+ break;
+ case END:
+ start = time - offset;
+ end = time;
+ break;
+ default: // NONE
+ start = time - (offset / 2);
+ end = time + (offset / 2);
+ }
+ return new Interval(isFinal, start, end);
+ }
+
+ public boolean isBetweenTime(long time) {
+ return switch (isFinal) {
+ case START -> time > start;
+ case END -> time < end;
+ case NONE -> true;
+ };
+ }
+
+ public long outsideTime(long time) {
+ if (!isBetweenTime(time))
+ return -1;
+
+ return Math.max(0, switch (isFinal) {
+ case START -> time - end;
+ case END -> start - time;
+ case NONE -> Math.max(start - time, time - end);
+ });
+ }
+
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/entity/Passenger.java b/persolijn/src/main/java/persolijn/entity/Passenger.java
@@ -0,0 +1,36 @@
+package persolijn.entity;
+
+import java.util.AbstractList;
+
+public class Passenger<T> extends AbstractList<T> {
+ public final Interval startTime;
+ public final T startPoint;
+ public final Interval targetTime;
+ public final T targetPoint;
+
+ public Passenger(T start, Interval startTime, T target, Interval targetTime) {
+ startPoint = start;
+ this.startTime = startTime;
+ targetPoint = target;
+ this.targetTime = targetTime;
+ }
+
+ public Passenger(T start, T target) {
+ startPoint = start;
+ this.startTime = null;
+ targetPoint = target;
+ this.targetTime = null;
+ }
+
+ public T get(int i) {
+ return switch (i) {
+ case 0 -> startPoint;
+ case 1 -> targetPoint;
+ default -> throw new IndexOutOfBoundsException("Passenger can only hold 2 points");
+ };
+ }
+
+ public int size() {
+ return 2;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/geo/Point.java b/persolijn/src/main/java/persolijn/geo/Point.java
@@ -0,0 +1,106 @@
+package persolijn.geo;
+
+import java.util.Collection;
+
+public interface Point {
+ public static final int EARTH_RADIUS = 6371; // km
+ public static final double DIRECT_DISTANCE_THRESHOLD = 50 * 50; // m^2
+
+ public static long distance(Point a, Point b) {
+ return distance(a.getLatitude(), a.getLongitude(), b.getLatitude(), b.getLongitude());
+ }
+
+ public static long distance(double aLat, double aLon, Point b) {
+ return distance(aLat, aLon, b.getLatitude(), b.getLongitude());
+ }
+
+ public static long distance(double aLat, double aLon, double bLat, double bLon) {
+ aLat = Math.toRadians(aLat);
+ bLat = Math.toRadians(bLat);
+ aLon = Math.toRadians(aLon);
+ bLon = Math.toRadians(bLon);
+
+ double a = 0.5 - Math.cos(bLat - aLat) / 2 + Math.cos(aLat) * Math.cos(bLat) * (1 - Math.cos(bLon - aLon)) / 2;
+
+ return Math.round(2.0 * 1000 * EARTH_RADIUS * Math.asin(Math.sqrt(a)));
+ }
+
+ public static Point center(Collection<? extends Point> points) {
+ double lat = 0;
+ double lon = 0;
+
+ for (Point point : points) {
+ lat += point.getLatitude();
+ lon += point.getLongitude();
+ }
+
+ return Point.of(lat / points.size(), lon / points.size());
+ }
+
+ public static double getAngle(Point a, Point b, Point c) {
+ if (a == null)
+ return 0;
+
+ return Math.atan2(c.getLongitude() - a.getLongitude(), c.getLatitude() - a.getLatitude()) -
+ Math.atan2(b.getLongitude() - a.getLongitude(), b.getLatitude() - a.getLatitude());
+ }
+
+ public static long distance(Iterable<? extends Point> path) {
+ long dist = 0;
+ Point prev = null;
+
+ for (Point current : path) {
+ if (prev != null)
+ dist += Point.distance(prev, current);
+
+ prev = current;
+ }
+
+ return dist;
+ }
+
+ public static Point of(double latitude, double longitude) {
+ return new Point() {
+ @Override
+ public double getLatitude() {
+ return latitude;
+ }
+
+ @Override
+ public double getLongitude() {
+ return longitude;
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (!(other instanceof Point))
+ return false;
+
+ return latitude == ((Point) other).getLatitude()
+ && longitude == ((Point) other).getLongitude();
+ }
+
+ @Override
+ public int hashCode() {
+ return Double.hashCode(latitude) + Double.hashCode(longitude);
+ }
+
+ @Override
+ public String toString() {
+ return String.format("Point[%f, %f]", getLatitude(), getLongitude());
+ }
+ };
+ }
+
+ default long distanceTo(Point other) {
+ return distance(this, other);
+ }
+
+ default long distanceTo(double latitude, double longitude) {
+ return distance(latitude, longitude, this);
+ }
+
+ double getLatitude();
+
+ double getLongitude();
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/BlobSpliterator.java b/persolijn/src/main/java/persolijn/osm/BlobSpliterator.java
@@ -0,0 +1,158 @@
+package persolijn.osm;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.RandomAccessFile;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Spliterator;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Consumer;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+import persolijn.common.RandomAccessFileInputStream;
+import persolijn.osm.message.Blob;
+import persolijn.osm.message.BlobHeader;
+import persolijn.osm.message.Entity;
+import persolijn.osm.message.HeaderBlock;
+
+public class BlobSpliterator implements Spliterator<List<Entity>> {
+ /**
+ * BlobHeader is never bigger then 64K.
+ */
+ private static final int MAX_HEADER_SIZE = 64 * 1024;
+
+ /**
+ * Blob is never bigger then 32M.
+ */
+ private static final int MAX_BLOB_SIZE = 32 * 1024 * 1024;
+
+ private final RandomAccessFile input;
+ private final InputStream stream;
+ private final Lock lock;
+ private final Consumer<HeaderBlock> onHeader;
+ private BlobHeader[] headers;
+
+ private final int start;
+ private int end = 0;
+ private int current = 0;
+
+ public BlobSpliterator(RandomAccessFile input, Consumer<HeaderBlock> onHeader) {
+ this.input = input;
+ this.onHeader = onHeader;
+ this.stream = new RandomAccessFileInputStream(input);
+ this.lock = new ReentrantLock();
+
+ List<BlobHeader> headerList = new ArrayList<>();
+ try {
+ while (input.getFilePointer() < input.length()) {
+ int headerLength = input.readInt();
+
+ if (headerLength > MAX_HEADER_SIZE)
+ throw new RuntimeException(
+ "blob header exceed " + MAX_HEADER_SIZE + "bytes (" + headerLength + ")");
+
+ BlobHeader header = new BlobHeader().parse(stream, headerLength);
+
+ if (header.size > MAX_BLOB_SIZE)
+ throw new RuntimeException("blob exceed " + MAX_BLOB_SIZE + "bytes (" + header.size + ")");
+
+ header.offset = input.getFilePointer();
+ headerList.add(header);
+
+ input.skipBytes(header.size);
+ }
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+
+ headers = new BlobHeader[headerList.size()];
+ headerList.toArray(headers);
+
+ start = 0;
+ current = 0;
+ end = headers.length;
+ }
+
+ private BlobSpliterator(RandomAccessFile input, Lock lock, Consumer<HeaderBlock> onHeader, BlobHeader[] headers,
+ int start, int end) {
+ this.input = input;
+ this.lock = lock;
+ this.onHeader = onHeader;
+ this.stream = new RandomAccessFileInputStream(input);
+ this.headers = headers;
+ this.start = start;
+ this.current = start;
+ this.end = end;
+ }
+
+ @Override
+ public Spliterator<List<Entity>> trySplit() {
+ // locking because of end
+ lock.lock();
+ if (current < end - 1)
+ return null;
+
+ int mid = (end - start) / 2;
+ int otherEnd = end;
+
+ end = start + mid;
+ lock.unlock();
+
+ return new BlobSpliterator(input, lock, onHeader, headers, end, otherEnd);
+ }
+
+ @Override
+ public boolean tryAdvance(Consumer<? super List<Entity>> action) {
+ // locking because of input, end
+ lock.lock();
+
+ if (current >= end)
+ return false;
+
+ BlobHeader header = headers[current++];
+
+ try {
+ input.seek(header.offset);
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+
+ Blob blob = new Blob(header.headerType).parse(stream, header.size);
+
+ // unlocking, every critical variable is unused
+ lock.unlock();
+
+ if (blob.header != null)
+ onHeader.accept(blob.header);
+
+ if (blob.primitive != null)
+ action.accept(blob.primitive);
+
+ return true;
+ }
+
+ @Override
+ public long estimateSize() {
+ return end - current;
+ }
+
+ @Override
+ public int characteristics() {
+ return DISTINCT | SUBSIZED | SIZED | NONNULL | IMMUTABLE | CONCURRENT;
+ }
+
+ public Stream<List<Entity>> stream(boolean parallel) {
+ return StreamSupport.stream(this, parallel);
+ }
+
+ public Stream<List<Entity>> stream() {
+ return stream(false);
+ }
+
+ public Stream<List<Entity>> parallelStream() {
+ return stream(true);
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/Graph.java b/persolijn/src/main/java/persolijn/osm/Graph.java
@@ -0,0 +1,121 @@
+package persolijn.osm;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.stream.Collector;
+
+import persolijn.common.Container;
+import persolijn.common.ContainerCollector;
+import persolijn.geo.Point;
+import persolijn.osm.message.Entity;
+import persolijn.osm.message.Node;
+import persolijn.osm.message.Way;
+
+public class Graph implements Container<Graph, Entity> {
+ public static final double NANO = 1e-9;
+
+ public static final double DISTANCE_RANGE = 5; // adding 5km to the result
+ public static final double DISTANCE_RANGE_MULTIPLIER = 1.25; // adding 25% to result
+
+ public static Collector<Entity, ?, Graph> asCollector(Collection<Point> points) {
+ Point center = Point.center(points);
+
+ long diameter = points.stream()
+ .mapToLong(center::distanceTo)
+ .max()
+ .orElseThrow();
+
+ long range = Math.round(DISTANCE_RANGE + DISTANCE_RANGE_MULTIPLIER * diameter);
+
+ return new ContainerCollector<>(() -> new Graph(points, center, range),
+ ContainerCollector.CONCURRENT | ContainerCollector.UNORDERED);
+ }
+
+ private final Collection<Point> points;
+ private final Point center;
+ private final long range;
+
+ public final Map<Long, Node> nodes = new HashMap<>();
+ public final Map<Long, Way> ways = new HashMap<>();
+ public final Map<Long, Map<Long, Way>> neighbors = new HashMap<>();
+ public final Map<Point, Node> pointNode = new HashMap<>();
+ public final Map<Point, Long> pointDistance = new HashMap<>();
+
+ public Graph(Collection<Point> points, Point center, long range) {
+ this.points = points;
+ this.center = center;
+ this.range = range;
+ }
+
+ @Override
+ public Graph combine(Graph other) {
+ nodes.putAll(other.nodes);
+ for (Entry<Long, Map<Long, Way>> neigh : other.neighbors.entrySet())
+ neighbors.computeIfAbsent(neigh.getKey(), k -> new HashMap<>())
+ .putAll(neigh.getValue());
+
+ return this;
+ }
+
+ @Override
+ public void finish() {
+ ways.forEach((i, w) -> connectWay(w));
+
+ for (Node node : nodes.values()) {
+ if (!neighbors.containsKey(node.getID()))
+ continue;
+
+ for (Point p : points) {
+ if (!pointNode.containsKey(p) || node.distanceTo(p) < pointDistance.get(p)) {
+ pointNode.put(p, node);
+ pointDistance.put(p, node.distanceTo(p));
+ }
+ }
+ }
+
+ System.out.printf("nodes: \t\t%d\nneighbors: \t%d\n", nodes.size(), neighbors.size());
+ }
+
+ protected void connectWay(Way w) {
+ long previous = -1;
+ Node previousNode = null;
+ for (int i = w.direction.getStartPoint(w.children.length); i >= 0
+ && i < w.children.length; i += w.direction.increment) {
+ long current = w.children[i];
+ if (!nodes.containsKey(current))
+ continue;
+
+ Node currentNode = nodes.get(current);
+
+ if (previousNode != null) {
+ neighbors.computeIfAbsent(previous, k -> new HashMap<>())
+ .put(current, w);
+ }
+ previous = current;
+ previousNode = currentNode;
+ }
+ }
+
+ @Override
+ public void accumulate(Entity element) {
+ if (element instanceof Node node) {
+ if (node.distanceTo(center) < range)
+ nodes.put(node.getID(), node);
+ } else if (element instanceof Way way) {
+ ways.put(way.getID(), way);
+ }
+ }
+
+ public Node getNode(Point point) {
+ return pointNode.get(point);
+ }
+
+ public Node getNode(long id) {
+ if (!nodes.containsKey(id))
+ throw new NullPointerException(String.format("node `%d` not found", id));
+
+ return nodes.get(id);
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/AbstractEntity.java b/persolijn/src/main/java/persolijn/osm/message/AbstractEntity.java
@@ -0,0 +1,139 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import persolijn.common.TagMap;
+import protobuf.Message;
+import protobuf.ProtobufReader;
+
+/**
+ * An abstract base class representing a generic entity with common properties
+ * for OSM data.
+ *
+ * @param <T> The type of the concrete entity extending this abstract class.
+ */
+public abstract class AbstractEntity<T> implements Message<T>, Entity {
+ // required int64 id = 1;
+ // repeated uint32 keys = 2 [packed = true];
+ // repeated uint32 vals = 3 [packed = true];
+
+ /**
+ * The PrimitiveBlock associated with this entity.
+ */
+ public final PrimitiveBlock block;
+
+ /**
+ * The unique identifier for the entity.
+ */
+ protected long id;
+
+ /**
+ * The list of keys associated with the entity's tags.
+ */
+ protected List<String> keys = new ArrayList<>();
+
+ /**
+ * The list of values associated with the entity's tags.
+ */
+ protected List<String> values = new ArrayList<>();
+
+ /**
+ * The TagMap representing the tags associated with the entity.
+ */
+ protected final TagMap tags = new TagMap(keys, values);
+
+ /**
+ * Constructs an AbstractEntity with the specified PrimitiveBlock.
+ *
+ * @param block The PrimitiveBlock associated with this entity.
+ */
+ public AbstractEntity(PrimitiveBlock block) {
+ this.block = block;
+ }
+
+ /**
+ * Gets the unique identifier of the entity.
+ *
+ * @return The entity's unique identifier.
+ */
+ @Override
+ public long getID() {
+ return id;
+ }
+
+ /**
+ * Gets the TagMap representing the tags associated with the entity.
+ *
+ * @return The TagMap containing the entity's tags.
+ */
+ @Override
+ public TagMap getTags() {
+ return tags;
+ }
+
+ /**
+ * Parses Protobuf data for the entity using a custom iterator.
+ *
+ * @param tags The iterator providing Protobuf data elements.
+ * @return The parsed entity.
+ */
+ @Override
+ public T parse(Iterator<ProtobufReader> tags) {
+ return parseRemaining(new Iterator<ProtobufReader>() {
+ @Override
+ public boolean hasNext() {
+ return tags.hasNext();
+ }
+
+ @Override
+ public ProtobufReader next() {
+ ProtobufReader message = tags.next();
+ switch (message.tag()) {
+ case 1 ->
+ id = message.varint64();
+ case 2 ->
+ message.packed(message::varint32, block.stringtable::get)
+ .forEachRemaining(keys::add);
+ case 3 ->
+ message.packed(message::varint32, block.stringtable::get)
+ .forEachRemaining(values::add);
+ }
+ return message;
+ };
+ });
+ }
+
+ /**
+ * Checks if the current entity is equal to another object.
+ *
+ * @param other The object to compare with.
+ * @return {@code true} if the entities are equal, {@code false} otherwise.
+ */
+ @Override
+ public boolean equals(Object other) {
+ if (other instanceof Entity otherEntity)
+ return otherEntity.getID() == id;
+
+ return false;
+ }
+
+ /**
+ * Generates a hash code for the entity based on its unique identifier.
+ *
+ * @return The hash code for the entity.
+ */
+ @Override
+ public int hashCode() {
+ return Long.hashCode(id);
+ }
+
+ /**
+ * Parses the remaining Protobuf data specific to the concrete entity.
+ *
+ * @param tags The iterator providing Protobuf data elements.
+ * @return The parsed entity.
+ */
+ protected abstract T parseRemaining(Iterator<ProtobufReader> tags);
+}
diff --git a/persolijn/src/main/java/persolijn/osm/message/Blob.java b/persolijn/src/main/java/persolijn/osm/message/Blob.java
@@ -0,0 +1,77 @@
+package persolijn.osm.message;
+
+import java.util.zip.Inflater;
+import java.util.Iterator;
+import java.util.List;
+import java.util.zip.DataFormatException;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// optional bytes raw = 1; // No compression
+// optional int32 raw_size = 2; // When compressed, the uncompressed size
+// optional bytes zlib_data = 3;
+// optional bytes lzma_data = 4;
+// optional bytes OBSOLETE_bzip2_data = 5 [deprecated=true]; // Don't reuse this tag number.
+public class Blob implements Message<Blob> {
+ public final String headerType;
+ public int size = 0;
+
+ public HeaderBlock header = null;
+ public List<Entity> primitive = null;
+
+ public Blob(String headerType) {
+ this.headerType = headerType;
+ }
+
+ @Override
+ public Blob parse(Iterator<ProtobufReader> tags) {
+ while (tags.hasNext()) {
+ ProtobufReader message = tags.next();
+ switch (message.tag()) {
+ case 2 -> size = message.varint32();
+ case 1 -> {
+ switch (headerType) {
+ case "OSMHeader" -> header = message.message(new HeaderBlock());
+ case "OSMData" -> primitive = message.message(new PrimitiveBlock());
+ }
+ }
+ case 3 -> {
+ switch (headerType) {
+ case "OSMHeader" -> message.delayed(new HeaderBlock(), this::decompress, this::setHeader);
+ case "OSMData" -> message.delayed(new PrimitiveBlock(), this::decompress, this::setPrimitive);
+ }
+ }
+ default -> message.skip();
+ }
+ }
+
+ return this;
+ }
+
+ private void setHeader(HeaderBlock header) {
+ this.header = header;
+ }
+
+ private void setPrimitive(List<Entity> primitive) {
+ this.primitive = primitive;
+ }
+
+ private byte[] decompress(byte[] block) {
+ Inflater decompresser = new Inflater();
+ decompresser.setInput(block);
+
+ try {
+ byte[] buffer = new byte[size];
+ int uncompressedSize = decompresser.inflate(buffer);
+
+ if (uncompressedSize != size) {
+ throw new RuntimeException("Invalid blob payload size");
+ }
+
+ return buffer;
+ } catch (DataFormatException exc) {
+ throw new RuntimeException(exc);
+ }
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/BlobHeader.java b/persolijn/src/main/java/persolijn/osm/message/BlobHeader.java
@@ -0,0 +1,29 @@
+package persolijn.osm.message;
+
+import java.util.Iterator;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// required string type = 1;
+// optional bytes indexdata = 2;
+// required int32 datasize = 3;
+public class BlobHeader implements Message<BlobHeader> {
+ public long offset;
+ public String headerType;
+ public int size;
+
+ @Override
+ public BlobHeader parse(Iterator<ProtobufReader> iter) {
+ while (iter.hasNext()) {
+ ProtobufReader message = iter.next();
+ switch (message.tag()) {
+ case 1 -> headerType = message.string();
+ case 3 -> size = message.varint32();
+ default -> message.skip();
+ }
+ }
+
+ return this;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/DenseNodes.java b/persolijn/src/main/java/persolijn/osm/message/DenseNodes.java
@@ -0,0 +1,104 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.function.Supplier;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// repeated sint64 id = 1 [packed = true]; // DELTA coded
+// optional DenseInfo denseinfo = 5;
+// repeated sint64 lat = 8 [packed = true]; // DELTA coded
+// repeated sint64 lon = 9 [packed = true]; // DELTA coded
+// repeated int32 keys_vals = 10 [packed = true];
+public class DenseNodes implements Message<List<Node>> {
+ public final PrimitiveBlock block;
+
+ public DenseNodes(PrimitiveBlock block) {
+ this.block = block;
+ }
+
+ private <T> void expandList(List<T> list, int index, Supplier<T> with) {
+ while (list.size() <= index)
+ list.add(with.get());
+ }
+
+ @Override
+ public List<Node> parse(Iterator<ProtobufReader> iter) {
+ boolean isKey = true;
+
+ int indexID = 0,
+ indexLatiude = 0,
+ indexLongitude = 0,
+ indexTags = 0;
+
+ List<Node> nodes = new ArrayList<>();
+
+ while (iter.hasNext()) {
+ ProtobufReader stream = iter.next();
+ switch (stream.tag()) {
+ case 1:
+ Iterator<Long> ids = stream.packed(stream::svarint64, 0l, Long::sum);
+ while (ids.hasNext()) {
+ expandList(nodes, indexID, () -> new Node(block));
+
+ nodes.get(indexID).id = ids.next();
+ indexID++;
+ }
+ break;
+ case 8:
+ Iterator<Double> lats = stream.packed(stream::svarint64,
+ n -> block.latitudeOffset + block.granularity * n,
+ 0.0d, Double::sum);
+ while (lats.hasNext()) {
+ expandList(nodes, indexLatiude, () -> new Node(block));
+
+ nodes.get(indexLatiude).latitude = lats.next();
+
+ indexLatiude++;
+ }
+ break;
+ case 9:
+ Iterator<Double> lons = stream.packed(stream::svarint64,
+ n -> block.longitudeOffset + block.granularity * n,
+ 0.0d, Double::sum);
+ while (lons.hasNext()) {
+ expandList(nodes, indexLongitude, () -> new Node(block));
+ nodes.get(indexLongitude).longitude = lons.next();
+
+ indexLongitude++;
+ }
+ break;
+ case 10:
+ Iterator<Integer> tags = stream.packed(stream::varint32);
+ while (tags.hasNext()) {
+ int strIndex = tags.next();
+ if (isKey) {
+ expandList(nodes, indexTags, () -> new Node(block));
+ if (strIndex == 0) {
+ indexTags++;
+ continue;
+ }
+ String key = block.stringtable.get(strIndex);
+ nodes.get(indexTags).keys.add(key);
+
+ isKey = false;
+ } else {
+ String value = block.stringtable.get(strIndex);
+ nodes.get(indexTags).values.add(value);
+
+ isKey = true;
+ }
+ }
+ break;
+ default:
+ stream.skip();
+ break;
+ }
+ }
+
+ return nodes;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/Entity.java b/persolijn/src/main/java/persolijn/osm/message/Entity.java
@@ -0,0 +1,9 @@
+package persolijn.osm.message;
+
+import persolijn.common.TagMap;
+
+public interface Entity {
+ long getID();
+
+ TagMap getTags();
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/HeaderBBox.java b/persolijn/src/main/java/persolijn/osm/message/HeaderBBox.java
@@ -0,0 +1,32 @@
+package persolijn.osm.message;
+
+import java.util.Iterator;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// required sint64 left = 1;
+// required sint64 right = 2;
+// required sint64 top = 3;
+// required sint64 bottom = 4;
+public class HeaderBBox implements Message<double[]> {
+ public static final double NANO = 1e-9;
+
+ @Override
+ public double[] parse(Iterator<ProtobufReader> iter) {
+ double[] bbox = new double[4];
+
+ while (iter.hasNext()) {
+ ProtobufReader message = iter.next();
+ switch (message.tag()) {
+ case 1 -> bbox[0] = NANO * message.svarint64();
+ case 2 -> bbox[1] = NANO * message.svarint64();
+ case 3 -> bbox[2] = NANO * message.svarint64();
+ case 4 -> bbox[3] = NANO * message.svarint64();
+ default -> message.skip();
+ }
+ }
+
+ return bbox;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/HeaderBlock.java b/persolijn/src/main/java/persolijn/osm/message/HeaderBlock.java
@@ -0,0 +1,46 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// optional HeaderBBox bbox = 1;
+// repeated string required_features = 4;
+// repeated string optional_features = 5;
+// optional string writingprogram = 16;
+// optional string source = 17; // From the bbox field.
+// optional int64 osmosis_replication_timestamp = 32;
+// optional int64 osmosis_replication_sequence_number = 33;
+// optional string osmosis_replication_base_url = 34;
+public class HeaderBlock implements Message<HeaderBlock> {
+ public final List<String> requiredFeatures = new ArrayList<>();
+ public final List<String> optionalFeatures = new ArrayList<>();
+ public double[] bbox = null;
+ public String writingProgram = null;
+ public String source = null;
+
+ @Override
+ public String toString() {
+ return String.format("required:\t%s\noptional:\t%s\nbound-box:\t%s", requiredFeatures, optionalFeatures,
+ List.of(bbox[0], bbox[1], bbox[2], bbox[3]));
+ }
+
+ @Override
+ public HeaderBlock parse(Iterator<ProtobufReader> iter) {
+ while (iter.hasNext()) {
+ ProtobufReader message = iter.next();
+ switch (message.tag()) {
+ case 1 -> bbox = message.message(new HeaderBBox());
+ case 4 -> requiredFeatures.add(message.string());
+ case 5 -> optionalFeatures.add(message.string());
+ case 16 -> writingProgram = message.string();
+ case 17 -> source = message.string();
+ default -> message.skip();
+ }
+ }
+ return this;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/Node.java b/persolijn/src/main/java/persolijn/osm/message/Node.java
@@ -0,0 +1,95 @@
+package persolijn.osm.message;
+
+import java.util.Iterator;
+
+import persolijn.routing.Routable;
+import protobuf.ProtobufReader;
+
+// required sint64 id = 1;
+// repeated uint32 keys = 2 [packed = true]; // String IDs.
+// repeated uint32 vals = 3 [packed = true]; // String IDs.
+// optional Info info = 4; // May be omitted in omitmeta
+// required sint64 lat = 8;
+// required sint64 lon = 9;
+public class Node extends AbstractEntity<Node> implements Routable<Node> {
+ protected double latitude, longitude;
+
+ protected Node parent = null;
+ protected long score = Long.MAX_VALUE,
+ heuristicScore = Long.MAX_VALUE;
+
+ public Node(PrimitiveBlock block) {
+ super(block);
+ }
+
+ @Override
+ public Node parseRemaining(Iterator<ProtobufReader> tags) {
+ while (tags.hasNext()) {
+ ProtobufReader message = tags.next();
+ switch (message.tag()) {
+ case 1, 2, 3 -> {
+ }
+ case 8 -> latitude = block.latitudeOffset + block.granularity * message.svarint64();
+ case 9 -> longitude = block.longitudeOffset + block.granularity * message.svarint64();
+ default -> message.skip();
+ }
+ }
+ return null;
+ }
+
+ @Override
+ public double getLatitude() {
+ return latitude;
+ }
+
+ @Override
+ public double getLongitude() {
+ return longitude;
+ }
+
+ @Override
+ public Node getParent() {
+ return parent;
+ }
+
+ @Override
+ public void setParent(Node parent) {
+ this.parent = parent;
+ }
+
+ @Override
+ public boolean hasParent() {
+ return parent != null;
+ }
+
+ @Override
+ public long getScore() {
+ return score;
+ }
+
+ @Override
+ public void setScore(long value) {
+ score = value;
+ }
+
+ @Override
+ public long getHeuristicScore() {
+ return heuristicScore;
+ }
+
+ @Override
+ public void setHeuristicScore(long value) {
+ heuristicScore = value;
+ }
+
+ @Override
+ public int compareTo(Node other) {
+ return Long.compare(other.getHeuristicScore(), getHeuristicScore());
+ }
+
+ @Override
+ public String toString() {
+ return String.format("Node#%d[%f, %f]", id, getLatitude(),
+ getLongitude(), id);
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/PrimitiveBlock.java b/persolijn/src/main/java/persolijn/osm/message/PrimitiveBlock.java
@@ -0,0 +1,45 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// required StringTable stringtable = 1;
+// repeated PrimitiveGroup primitivegroup = 2;
+// optional int32 granularity = 17 [default=100];
+// optional int64 lat_offset = 19 [default=0];
+// optional int64 lon_offset = 20 [default=0];
+// optional int32 date_granularity = 18 [default=1000];
+public class PrimitiveBlock implements Message<List<Entity>> {
+ public static final double NANO = 1e-9;
+
+ public List<String> stringtable = null;
+
+ public List<byte[]> groupBuffers = new ArrayList<>();
+
+ public double granularity = NANO * 100;
+ public double latitudeOffset = 0;
+ public double longitudeOffset = 0;
+
+ @Override
+ public List<Entity> parse(Iterator<ProtobufReader> iter) {
+ List<Entity> groups = new ArrayList<>();
+
+ while (iter.hasNext()) {
+ ProtobufReader message = iter.next();
+ switch (message.tag()) {
+ case 1 -> stringtable = message.message(new StringTable());
+ case 2 -> message.delayed(new PrimitiveGroup(this), groups::addAll);
+ case 17 -> granularity = NANO * message.varint32();
+ case 19 -> latitudeOffset = NANO * message.varint64();
+ case 20 -> longitudeOffset = NANO * message.varint64();
+ default -> message.skip();
+ }
+ }
+
+ return groups;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/PrimitiveGroup.java b/persolijn/src/main/java/persolijn/osm/message/PrimitiveGroup.java
@@ -0,0 +1,39 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// repeated Node nodes = 1;
+// optional DenseNodes dense = 2;
+// repeated Way ways = 3;
+// repeated Relation relations = 4;
+// repeated ChangeSet changesets = 5;
+public class PrimitiveGroup implements Message<List<Entity>> {
+ private final PrimitiveBlock block;
+
+ public PrimitiveGroup(PrimitiveBlock block) {
+ this.block = block;
+ }
+
+ @Override
+ public List<Entity> parse(Iterator<ProtobufReader> iter) {
+ List<Entity> elements = new ArrayList<>();
+
+ while (iter.hasNext()) {
+ ProtobufReader message = iter.next();
+ switch (message.tag()) {
+ case 1 -> elements.add(message.message(new Node(block)));
+ case 2 -> elements.addAll(message.message(new DenseNodes(block)));
+ case 3 -> elements.addAll(message.message(new Way.Message(block)));
+ case 4 -> elements.add(message.message(new Relation(block)));
+ default -> message.skip();
+ }
+ }
+
+ return elements;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/Relation.java b/persolijn/src/main/java/persolijn/osm/message/Relation.java
@@ -0,0 +1,35 @@
+package persolijn.osm.message;
+
+import java.util.Iterator;
+
+import protobuf.ProtobufReader;
+
+// enum MemberType {
+// NODE = 0;
+// WAY = 1;
+// RELATION = 2;
+// }
+// required int64 id = 1;
+// repeated uint32 keys = 2 [packed = true];
+// repeated uint32 vals = 3 [packed = true];
+// repeated int32 roles_sid = 8 [packed = true]; // This should have been defined as uint32 for consistency, but it is now too late to change it
+// repeated sint64 memids = 9 [packed = true]; // DELTA encoded
+// repeated MemberType types = 10 [packed = true];
+public class Relation extends AbstractEntity<Relation> {
+ public Relation(PrimitiveBlock block) {
+ super(block);
+ }
+
+ @Override
+ public Relation parseRemaining(Iterator<ProtobufReader> tags) {
+ while (tags.hasNext()) {
+ ProtobufReader message = tags.next();
+ switch (message.tag()) {
+ case 1, 2, 3 -> {
+ }
+ default -> message.skip();
+ }
+ }
+ return this;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/StringTable.java b/persolijn/src/main/java/persolijn/osm/message/StringTable.java
@@ -0,0 +1,25 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import protobuf.ProtobufReader;
+import protobuf.Message;
+
+// repeated bytes s = 1;
+public class StringTable implements Message<List<String>> {
+ @Override
+ public List<String> parse(Iterator<ProtobufReader> iter) {
+ List<String> table = new ArrayList<>();
+ while (iter.hasNext()) {
+ ProtobufReader message = iter.next();
+ switch (message.tag()) {
+ case 1 -> table.add(message.string());
+ default -> message.skip();
+ }
+ }
+
+ return table;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/osm/message/Way.java b/persolijn/src/main/java/persolijn/osm/message/Way.java
@@ -0,0 +1,162 @@
+package persolijn.osm.message;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import persolijn.common.TagMap;
+import protobuf.ProtobufReader;
+
+// required int64 id = 1;
+// repeated uint32 keys = 2 [packed = true];
+// repeated uint32 vals = 3 [packed = true];
+// optional Info info = 4;
+// repeated sint64 refs = 8 [packed = true]; // DELTA coded
+public class Way implements Entity {
+ public enum Direction {
+ FORWARDS(1), BACKWARDS(-1);
+
+ public final int increment;
+
+ private Direction(int increment) {
+ this.increment = increment;
+ }
+
+ public int getStartPoint(int size) {
+ return switch (increment) {
+ case 1 -> 0;
+ case -1 -> size - 1;
+ default -> throw new RuntimeException("increment must be -1 or 1");
+ };
+ }
+ }
+
+ public static class Message extends AbstractEntity<Set<Way>> {
+ public static final Set<String> WAY_NO_ALLOWED = Set.of(
+ "pedestrian",
+ "path",
+ "bridleway",
+ "cycleway",
+ "footway",
+ "steps");
+
+ public static final Map<String, String> WAY_DEFAULT_SPEED = Map.of(
+ "motorway", "120",
+ "trunk", "100",
+ "primary", "80",
+ "secondary", "80",
+ "tertiary", "60",
+ "unclassified", "60",
+ "residential", "50");
+
+ public static final String WAY_UNLIMITED_SPEED = "100";
+
+ public Message(PrimitiveBlock block) {
+ super(block);
+ }
+
+ protected boolean isAllowed(Direction direction) {
+ if (!tags.containsKey("highway"))
+ return false;
+
+ boolean allowed = !WAY_NO_ALLOWED.contains(tags.get("highway"))
+ || tags.getBoolean("access", v -> false)
+ || tags.getBoolean("motor_vehicle", v -> false)
+ || tags.getBoolean("taxi", v -> false)
+ || tags.getBoolean("psv", v -> false);
+
+ if (direction == Direction.BACKWARDS) {
+ if (tags.getBoolean("oneway"))
+ allowed = false;
+
+ allowed = allowed
+ || tags.getBoolean("access:backwards", v -> false)
+ || tags.getBoolean("motor_vehicle:backwards", v -> false)
+ || tags.getBoolean("psv:backwards", v -> false)
+ || tags.getBoolean("taxi:backwards", v -> false);
+ }
+
+ return allowed;
+ }
+
+ protected double getSpeed(Direction direction) {
+ String speed = "60";
+
+ speed = WAY_DEFAULT_SPEED.getOrDefault(tags.get("highway"), speed);
+ speed = tags.getOrDefault("maxspeed", speed);
+
+ if (direction == Direction.BACKWARDS)
+ speed = tags.getOrDefault("maxspeed:backwards", speed);
+
+ if (speed.equals("none"))
+ speed = WAY_UNLIMITED_SPEED;
+
+ return Double.parseDouble(speed) / 3.6;
+ }
+
+ @Override
+ public Set<Way> parseRemaining(Iterator<ProtobufReader> tags) {
+ List<Long> children = new ArrayList<>();
+ while (tags.hasNext()) {
+ ProtobufReader message = tags.next();
+ switch (message.tag()) {
+ case 1, 2, 3:
+ break;
+ case 8:
+ message.packed(message::svarint64, 0l, Long::sum)
+ .forEachRemaining(children::add);
+ break;
+ default:
+ message.skip();
+ break;
+ }
+ }
+
+ long[] array = new long[children.size()];
+
+ for (int i = 0; i < children.size(); i++)
+ array[i] = children.get(i);
+
+ Set<Way> result = new HashSet<>();
+ if (isAllowed(Direction.FORWARDS))
+ result.add(new Way(id, getTags(), array, Direction.FORWARDS, getSpeed(Direction.FORWARDS)));
+
+ if (isAllowed(Direction.BACKWARDS))
+ result.add(new Way(id, getTags(), array, Direction.BACKWARDS, getSpeed(Direction.BACKWARDS)));
+
+ return result;
+ }
+ }
+
+ public final long id;
+ public final TagMap tags;
+ public final long[] children;
+ public final Direction direction;
+ public final double speed;
+
+ public Way(long id, TagMap tags, long[] children, Direction direction, double speed) {
+ this.id = id;
+ this.tags = tags;
+ this.children = children;
+ this.direction = direction;
+ this.speed = speed;
+ }
+
+ @Override
+ public long getID() {
+ return id;
+ }
+
+ @Override
+ public TagMap getTags() {
+ return tags;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("Way#%d[%dnodes]", id, children.length);
+ }
+}
diff --git a/persolijn/src/main/java/persolijn/planner/BasePlanner.java b/persolijn/src/main/java/persolijn/planner/BasePlanner.java
@@ -0,0 +1,67 @@
+package persolijn.planner;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Stack;
+import java.util.Map.Entry;
+import java.util.concurrent.atomic.AtomicReference;
+
+import persolijn.entity.Passenger;
+import persolijn.routing.RouteFunction;
+
+public abstract class BasePlanner<N, P> implements PlannerFunction<N, Passenger<N>, P> {
+ @Override
+ public List<N> plan(RouteFunction<N, P> distanceFunction, N garage, Collection<Passenger<N>> targets) {
+ Stack<N> path = new Stack<>();
+
+ path.push(garage);
+
+ long pathLength = 0;
+ TargetIterable<Passenger<N>, N> targetIterable = new TargetIterable<>(garage, targets, path::peek,
+ p -> p.startPoint, p -> p.targetPoint);
+
+ for (TargetIterable<Passenger<N>, N>.TargetEntry currentTargets : targetIterable) {
+ Map<N, Long> targetEstimate = new HashMap<>();
+
+ for (N target : currentTargets.targets)
+ targetEstimate.put(target, estimateLength(distanceFunction, currentTargets, target));
+
+ System.out.printf("route(%s, %s, %s)\n", targetEstimate, path.peek(), pathLength);
+ List<N> subPath = distanceFunction.route(targetEstimate, path.peek(), pathLength);
+ if (subPath == null) {
+ System.out.println("nothing found searching for " + currentTargets);
+ return null;
+ }
+
+ path.addAll(subPath);
+ pathLength += getLength(distanceFunction, subPath);
+ }
+
+ return path;
+ }
+
+ protected long estimateLength(RouteFunction<N, P> distanceFunction,
+ TargetIterable<Passenger<N>, N>.TargetEntry entry,
+ N current) {
+ long pathLength = 0;
+
+ AtomicReference<N> currentRef = new AtomicReference<>();
+ currentRef.set(current);
+
+ for (TargetIterable<Passenger<N>, N>.TargetEntry currentTargets : new TargetIterable<Passenger<N>, N>(entry,
+ currentRef::get)) {
+ Entry<N, Long> subPath = distanceFunction.estimateRoute(currentTargets.targets, currentRef.get());
+
+ currentRef.set(subPath.getKey());
+ pathLength += subPath.getValue();
+ }
+
+ return pathLength;
+ }
+
+ protected abstract long getPathScore(RouteFunction<N, P> router, long length, Map<Passenger<N>, Long> passengers);
+
+ protected abstract long getLength(RouteFunction<N, P> router, List<N> path);
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/planner/Planner.java b/persolijn/src/main/java/persolijn/planner/Planner.java
@@ -0,0 +1,32 @@
+package persolijn.planner;
+
+import java.util.List;
+import java.util.Map;
+
+import persolijn.entity.Passenger;
+import persolijn.geo.Point;
+import persolijn.osm.message.Node;
+import persolijn.routing.RouteFunction;
+
+public class Planner extends BasePlanner<Node, Point> {
+ @Override
+ protected long getLength(RouteFunction<Node, Point> graph, List<Node> path) {
+ long distance = 0;
+ for (int i = 0; i < path.size() - 1; i++) {
+ Point left = path.get(i);
+ Point right = path.get(i + 1);
+
+ // distance += graph.neighbors.get(left).get(right).distance;
+ distance += left.distanceTo(right);
+ }
+ return distance;
+ }
+
+ @Override
+ protected long getPathScore(RouteFunction<Node, Point> graph, long length, Map<Passenger<Node>, Long> passengers) {
+ return Math.round(
+ passengers.values().stream().mapToDouble(v -> (double) v).sum()
+ / passengers.values().size())
+ + length;
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/planner/PlannerFunction.java b/persolijn/src/main/java/persolijn/planner/PlannerFunction.java
@@ -0,0 +1,11 @@
+package persolijn.planner;
+
+import java.util.Collection;
+import java.util.List;
+
+import persolijn.routing.RouteFunction;
+
+@FunctionalInterface
+public interface PlannerFunction<N, P, L> {
+ List<N> plan(RouteFunction<N, L> router, N garage, Collection<P> targets);
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/planner/TargetIterable.java b/persolijn/src/main/java/persolijn/planner/TargetIterable.java
@@ -0,0 +1,124 @@
+package persolijn.planner;
+
+import java.util.List;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.Function;
+import java.util.function.Supplier;
+
+public class TargetIterable<P, T> implements Iterable<TargetIterable<P, T>.TargetEntry> {
+ public static enum Visited {
+ PENDING,
+ BUSY,
+ FINISHED,
+ };
+
+ private final T garage;
+ private final Collection<P> targetList;
+ private final Supplier<T> supplier;
+ private final Function<P, T> startPoint;
+ private final Function<P, T> targetPoint;
+ private final Map<P, Visited> originalMap;
+
+ public class TargetEntry {
+ public final TargetIterator iterator;
+ public final List<T> targets;
+
+ public TargetEntry(TargetIterator iterator, List<T> targets) {
+ this.iterator = iterator;
+ this.targets = targets;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("TargetEntry(%s)", targets);
+ }
+ }
+
+ private class TargetIterator implements Iterator<TargetIterable<P, T>.TargetEntry> {
+ public final TargetIterable<P, T> iterable;
+ public final Map<P, Visited> targetMap;
+
+ public TargetIterator(TargetIterable<P, T> iterable) {
+ this.iterable = iterable;
+ this.targetMap = new HashMap<>(iterable.originalMap);
+ }
+
+ private Visited checkVisited(P p, T current) {
+ Visited visited = targetMap.getOrDefault(p, Visited.PENDING);
+
+ if (current == startPoint.apply(p) && visited == Visited.PENDING)
+ visited = Visited.BUSY;
+ else if (current == targetPoint.apply(p) && visited == Visited.BUSY)
+ visited = Visited.FINISHED;
+
+ return visited;
+ }
+
+ @Override
+ public boolean hasNext() {
+ T current = supplier.get();
+
+ return current != garage || targetList.stream()
+ .map(p -> checkVisited(p, current))
+ .anyMatch(v -> v == Visited.PENDING || v == Visited.BUSY);
+ }
+
+ @Override
+ public TargetIterable<P, T>.TargetEntry next() {
+ T current = supplier.get();
+
+ List<T> targetNodes = targetList.stream()
+ .map(p -> Map.entry(p, checkVisited(p, current)))
+ .peek(e -> targetMap.put(e.getKey(), e.getValue()))
+
+ .map(e -> switch (e.getValue()) {
+ case PENDING -> startPoint.apply(e.getKey());
+ case BUSY -> targetPoint.apply(e.getKey());
+ case FINISHED -> null;
+ })
+ .filter(Objects::nonNull)
+ .toList();
+
+ if (targetNodes.isEmpty() && current != garage)
+ return new TargetEntry(this, List.of(garage));
+
+ return new TargetEntry(this, targetNodes);
+ }
+ }
+
+ public TargetIterable(T garage, Collection<P> targetList,
+ Supplier<T> supplier, Function<P, T> startPoint, Function<P, T> targetPoint) {
+ this.garage = garage;
+ this.targetList = targetList;
+ this.supplier = supplier;
+ this.startPoint = startPoint;
+ this.targetPoint = targetPoint;
+ this.originalMap = Map.of();
+ }
+
+ public TargetIterable(TargetIterable<P, T> iterable, Supplier<T> supplier, Map<P, Visited> targetMap) {
+ this.garage = iterable.garage;
+ this.targetList = iterable.targetList;
+ this.startPoint = iterable.startPoint;
+ this.targetPoint = iterable.targetPoint;
+ this.supplier = supplier;
+ this.originalMap = targetMap;
+ }
+
+ public TargetIterable(TargetIterable<P, T>.TargetIterator iterator, Supplier<T> supplier) {
+ this(iterator.iterable, supplier, iterator.targetMap);
+ }
+
+ public TargetIterable(TargetIterable<P, T>.TargetEntry entry, Supplier<T> supplier) {
+ this(entry.iterator, supplier);
+ }
+
+ @Override
+ public Iterator<TargetIterable<P, T>.TargetEntry> iterator() {
+ return new TargetIterator(this);
+ }
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/routing/BaseRouter.java b/persolijn/src/main/java/persolijn/routing/BaseRouter.java
@@ -0,0 +1,223 @@
+package persolijn.routing;
+
+import java.util.List;
+import java.util.Map;
+import java.util.TreeSet;
+import java.util.stream.Stream;
+
+import persolijn.osm.message.Way;
+
+/**
+ * A base class for implementing routing algorithms between two points on a
+ * graph.
+ *
+ * @param <N> The type of nodes in the graph.
+ * @param <P> The type of points representing locations in the graph.
+ */
+public abstract class BaseRouter<N extends Routable<N>, P> implements RouteFunction<N, P> {
+ /**
+ * Represents a consumer function for processing edges in a graph during
+ * routing.
+ *
+ * @param <N> The type of nodes in the graph.
+ * @param <W> The type of ways or edges in the graph.
+ */
+ @FunctionalInterface
+ public interface EdgeConsumer<N, W> {
+
+ /**
+ * Accepts an edge in the graph and processes it.
+ *
+ * @param node The current node in the traversal.
+ * @param via The way or edge connecting the current node to the next node.
+ * @param distance The distance between the current and next nodes.
+ * @param time The time required to travel between the current and next
+ * nodes.
+ */
+ void accept(N node, W via, long distance, double time);
+ }
+
+ /**
+ * Gets the size of the history for a given node.
+ *
+ * @param node The node for which to calculate the history size.
+ * @return The size of the history for the given node.
+ */
+ public static <N extends Routable<N>> int getHistorySize(N node) {
+ int size = 0;
+
+ for (N c = node; c != null; c = c.getParent())
+ size++;
+
+ return size;
+ }
+
+ /**
+ * Retrieves the history of a node, including itself and its ancestors.
+ *
+ * @param node The node for which to retrieve the history.
+ * @return A list representing the history of the given node.
+ */
+ public List<N> getHistory(N node) {
+ N[] path = createHistoryArray(getHistorySize(node));
+ // N[] path = (N[]) new Object[getHistorySize(parents, node)];
+
+ for (int i = path.length - 1; i >= 0; i--) {
+ path[i] = node;
+
+ node = (N) node.getParent();
+ }
+
+ return List.of(path);
+ }
+
+ /**
+ * Retrieves the reverse history of a node, starting from itself and going to
+ * its ancestors.
+ *
+ * @param node The node for which to retrieve the reverse history.
+ * @return A stream representing the reverse history of the given node.
+ */
+ public Stream<N> getReverseHistory(N node) {
+ return Stream.iterate(node, Routable::hasParent, Routable::getParent);
+ }
+
+ /**
+ * Calculates the progress between the start and the current node.
+ *
+ * @param targets The target nodes and their distances.
+ * @param start The starting node.
+ * @param offset The offset value.
+ * @param current The current node.
+ * @return The progress between the start and current node as a percentage.
+ */
+ protected double getProgress(Map<N, Long> targets, N start, long offset, N current) {
+ double startDistance = offset + getStartDistance(start, current);
+ return startDistance / (startDistance + getClosestDistance(targets, current));
+ }
+
+ /**
+ * Finds the optimal route between the start node and a collection of target
+ * nodes.
+ *
+ * @param targets The target nodes and their distances.
+ * @param start The starting node.
+ * @param offset The offset value.
+ * @return A list representing the optimal route from the start to a target
+ * node.
+ */
+ @Override
+ public List<N> route(Map<N, Long> targets, N start, long offset) {
+ TreeSet<N> openNodes = new TreeSet<>();
+
+ double bestProgress = 0;
+
+ openNodes.add(start);
+
+ start.setScore(0L);
+ start.setHeuristicScore(getHeuristic(targets, start));
+
+ while (!openNodes.isEmpty()) {
+ N current = openNodes.first();
+
+ double currentProgress = getProgress(targets, start, offset, current);
+ if (currentProgress > bestProgress)
+ onProgress(bestProgress = currentProgress);
+
+ if (isTarget(targets, current))
+ return getHistory(current);
+
+ forNeighbor(current, (next, way, distance, time) -> {
+ if (next.equals(current))
+ return;
+
+ long totalWeight = current.getScore() + getCost(current, next, distance, time);
+
+ if (totalWeight >= next.getScore())
+ return;
+
+ next.setParent(current);
+ next.setScore(totalWeight);
+ next.setHeuristicScore(totalWeight + getHeuristic(targets, next));
+
+ openNodes.add(next);
+ });
+
+ openNodes.pollFirst();
+ }
+ return null;
+ }
+
+ /**
+ * Creates an array to store the history of a node with the given size.
+ *
+ * @param size The size of the history array.
+ * @return An array capable of storing the history of a node.
+ */
+ protected abstract N[] createHistoryArray(int size);
+
+ /**
+ * Calculates a heuristic value for a node based on its distance to target
+ * nodes.
+ *
+ * @param targets The target nodes and their distances.
+ * @param node The node for which to calculate the heuristic.
+ * @return The heuristic value for the given node.
+ */
+ protected abstract long getHeuristic(Map<N, Long> targets, N node);
+
+ /**
+ * Calculates the cost of moving from the current node to the next node.
+ *
+ * @param current The current node.
+ * @param next The next node to move to.
+ * @param distance The distance between the current and next nodes.
+ * @param time The time required to travel between the current and next
+ * nodes.
+ * @return The cost of moving from the current node to the next node.
+ */
+ protected abstract long getCost(N current, N next, long distance, double time);
+
+ /**
+ * Iterates over the neighbors of a node and applies the provided consumer
+ * function.
+ *
+ * @param node The node for which to iterate over neighbors.
+ * @param consumer The consumer function to apply to each neighbor.
+ */
+ protected abstract void forNeighbor(N node, EdgeConsumer<N, Way> consumer);
+
+ /**
+ * Gets the closest distance from a node to a set of target nodes.
+ *
+ * @param targets The target nodes and their distances.
+ * @param node The node for which to find the closest distance.
+ * @return The closest distance from the node to any of the target nodes.
+ */
+ protected abstract long getClosestDistance(Map<N, Long> targets, N node);
+
+ /**
+ * Called when progress is made during the route calculation.
+ *
+ * @param progress The progress made, represented as a percentage.
+ */
+ protected abstract void onProgress(double progress);
+
+ /**
+ * Checks if a node is a target node.
+ *
+ * @param targets The target nodes and their distances.
+ * @param node The node to check.
+ * @return {@code true} if the node is a target node, {@code false} otherwise.
+ */
+ protected abstract boolean isTarget(Map<N, Long> targets, N node);
+
+ /**
+ * Gets the distance from the start node to a given node.
+ *
+ * @param start The start node.
+ * @param node The node for which to calculate the distance.
+ * @return The distance from the start node to the given node.
+ */
+ protected abstract long getStartDistance(N start, N node);
+}
+\ No newline at end of file
diff --git a/persolijn/src/main/java/persolijn/routing/Routable.java b/persolijn/src/main/java/persolijn/routing/Routable.java
@@ -0,0 +1,19 @@
+package persolijn.routing;
+
+import persolijn.geo.Point;
+
+public interface Routable<N> extends Comparable<N>, Point {
+ long getScore();
+
+ void setScore(long value);
+
+ long getHeuristicScore();
+
+ void setHeuristicScore(long total);
+
+ boolean hasParent();
+
+ N getParent();
+
+ void setParent(N parent);
+}
diff --git a/persolijn/src/main/java/persolijn/routing/RouteFunction.java b/persolijn/src/main/java/persolijn/routing/RouteFunction.java
@@ -0,0 +1,39 @@
+package persolijn.routing;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+
+/**
+ * Represents a routing function for finding the optimal route between two
+ * points on a graph.
+ *
+ * @param <N> The type of nodes in the graph.
+ * @param <P> The type of points representing locations in the graph.
+ */
+public interface RouteFunction<N, P> {
+
+ /**
+ * Finds the optimal route between the start node and a collection of target
+ * nodes.
+ *
+ * @param targets The target nodes and their distances.
+ * @param start The starting node.
+ * @param offset The offset value.
+ * @return A list representing the optimal route from the start to a target
+ * node.
+ */
+ List<N> route(Map<N, Long> targets, N start, long offset);
+
+ /**
+ * Estimates the optimal route between a collection of target nodes and a
+ * starting node.
+ *
+ * @param targets The target nodes.
+ * @param start The starting node.
+ * @return An entry containing the best target node and its estimated distance.
+ */
+ Entry<N, Long> estimateRoute(Collection<N> targets, N start);
+
+}
diff --git a/persolijn/src/main/java/persolijn/routing/Router.java b/persolijn/src/main/java/persolijn/routing/Router.java
@@ -0,0 +1,207 @@
+package persolijn.routing;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.NoSuchElementException;
+
+import persolijn.geo.Point;
+import persolijn.osm.Graph;
+import persolijn.osm.message.Node;
+import persolijn.osm.message.Way;
+
+/**
+ * A concrete implementation of a router using a graph of nodes and ways.
+ */
+public class Router extends BaseRouter<Node, Point> {
+ /**
+ * The default speed for the router, in meters per second.
+ */
+ public static final double DEFAULT_SPEED = 60 / 3.6;
+
+ /**
+ * The map of nodes in the graph, indexed by their IDs.
+ */
+ private final Map<Long, Node> nodes;
+
+ /**
+ * The map of neighbors for each node in the graph.
+ */
+ private final Map<Long, Map<Long, Way>> neighbors;
+
+ /**
+ * Constructs a router using a graph.
+ *
+ * @param graph The graph containing nodes and ways.
+ */
+ public Router(Graph graph) {
+ this.nodes = graph.nodes;
+ this.neighbors = graph.neighbors;
+ }
+
+ /**
+ * Constructs a router with specified nodes and neighbors.
+ *
+ * @param nodes The map of nodes in the graph.
+ * @param neighbors The map of neighbors for each node.
+ */
+ public Router(Map<Long, Node> nodes, Map<Long, Map<Long, Way>> neighbors) {
+ this.nodes = nodes;
+ this.neighbors = neighbors;
+ }
+
+ /**
+ * Retrieves a node from the graph using its ID.
+ *
+ * @param id The ID of the node to retrieve.
+ * @return The node with the specified ID.
+ * @throws NoSuchElementException If the node with the given ID is not found.
+ */
+ public Node getNode(long id) throws NoSuchElementException {
+ if (!nodes.containsKey(id))
+ throw new NoSuchElementException(String.format("node `%d` not found", id));
+
+ return nodes.get(id);
+ }
+
+ @Override
+ public Entry<Node, Long> estimateRoute(Collection<Node> targets, Node start) {
+ Node bestNode = null;
+ long bestDist = Long.MAX_VALUE;
+
+ for (Node target : targets) {
+ long startDist = target.distanceTo(start);
+ if (startDist < bestDist) {
+ bestNode = target;
+ bestDist = startDist;
+ }
+ }
+
+ return Map.entry(bestNode, bestDist);
+ }
+
+ @Override
+ public long getCost(Node current, Node next, long distance, double speed) {
+ // time += Math.abs(
+ // Point.getAngle((Node) from.getParent(), from, to)) / Math.PI * 30;
+ return current.distanceTo(next);
+ // return Math.round(distance / DEFAULT_SPEED * 0.2 + time * 0.8);
+ }
+
+ @Override
+ public long getClosestDistance(Map<Node, Long> targets, Node node) {
+ return targets.entrySet().stream()
+ .map(e -> e.getKey().distanceTo(node) + e.getValue())
+ .min(Long::compare)
+ .orElseThrow();
+ }
+
+ @Override
+ public void onProgress(double progress) {
+ System.out.printf("%6.2f%% [%s>%s]\r",
+ progress * 100,
+ "=".repeat((int) Math.round(progress * 80)),
+ " ".repeat((int) Math.round((1 - progress) * 80)));
+ }
+
+ @Override
+ public boolean isTarget(Map<Node, Long> targets, Node node) {
+ return targets.containsKey(node);
+ }
+
+ @Override
+ public long getHeuristic(Map<Node, Long> targets, Node node) {
+ long dist = targets.entrySet().stream()
+ .map(e -> e.getKey().distanceTo(node))// + e.getValue())
+ .min(Long::compare)
+ .orElseThrow();
+
+ return dist >> 1;
+ }
+
+ @Override
+ protected long getStartDistance(Node start, Node node) {
+ return start.distanceTo(node);
+ }
+
+ @Override
+ protected void forNeighbor(Node node, EdgeConsumer<Node, Way> consumer) {
+ // System.out.printf("%s: %s\n", node, neighbors.get(node.getID()));
+
+ if (!neighbors.containsKey(node.getID()))
+ return;
+
+ neighbors.get(node.getID()).forEach((n, w) -> {
+ // if neighbors is out-of-scope or has no neighbors
+ if (!nodes.containsKey(n)) {
+ // System.out.printf("! %s -> %s (%f)\n", node, n, t);
+ return;
+ }
+ consumer.accept(nodes.get(n), w, nodes.get(n).distanceTo(node), w.speed);
+ });
+ }
+
+ // private static record WalkTuple(Node previous, long previousID, long
+ // currentID, double speed,
+ // long distance, double time) {
+ // }
+ // @Override
+ // protected void forNeighbor(Node node, EdgeConsumer<Node> consumer) {
+ // final int NEIGHBOR_MAX_DISTANCE = 10000; // 10km
+
+ // if (!neighbors.containsKey(node.getID()))
+ // return;
+
+ // Set<Long> visited = new HashSet<>();
+ // Stack<WalkTuple> stack = new Stack<>();
+
+ // visited.add(node.getID());
+
+ // for (Entry<Long, Double> neighbor : neighbors.get(node.getID()).entrySet())
+ // stack.push(new WalkTuple(node, node.getID(), neighbor.getKey(),
+ // neighbor.getValue(), 0, 0));
+
+ // int count = 0;
+ // while (!stack.isEmpty()) {
+ // WalkTuple wi = stack.pop();
+
+ // long currentID = wi.currentID;
+ // if (visited.contains(currentID))
+ // continue;
+
+ // visited.add(currentID);
+
+ // long distance = wi.distance;
+ // double time = wi.time;
+
+ // Node current = wi.previous;
+ // if (nodes.containsKey(currentID)) {
+ // current = getNode(currentID);
+ // distance += wi.previous.distanceTo(current);
+ // time += (double) wi.previous.distanceTo(current) / wi.speed;
+ // }
+
+ // if (current != wi.previous && current != node
+ // && (!neighbors.containsKey(currentID) || neighbors.get(currentID).size() !=
+ // 2)) {
+ // consumer.accept(current, distance, time);
+ // count++;
+ // } else if (neighbors.containsKey(currentID) && distance <
+ // NEIGHBOR_MAX_DISTANCE) {
+ // for (Entry<Long, Double> n : neighbors.get(currentID).entrySet()) {
+ // if (n.getKey() == currentID || n.getKey() == wi.previousID)
+ // continue;
+
+ // stack.push(new WalkTuple(current, currentID, n.getKey(), n.getValue(),
+ // distance, time));
+ // }
+ // }
+ // }
+ // System.out.println(count);
+ // }
+
+ @Override
+ protected Node[] createHistoryArray(int size) {
+ return new Node[size];
+ }
+}
diff --git a/persolijn/src/main/proto/fileformat.proto b/persolijn/src/main/proto/fileformat.proto
@@ -0,0 +1,47 @@
+/** Copyright (c) 2010 Scott A. Crosby. <[email protected]>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+*/
+
+option optimize_for = LITE_RUNTIME;
+option java_package = "crosby.binary";
+package OSMPBF;
+
+//protoc --java_out=../.. fileformat.proto
+
+
+//
+// STORAGE LAYER: Storing primitives.
+//
+
+message Blob {
+ optional bytes raw = 1; // No compression
+ optional int32 raw_size = 2; // When compressed, the uncompressed size
+
+ // Possible compressed versions of the data.
+ optional bytes zlib_data = 3;
+
+ // PROPOSED feature for LZMA compressed data. SUPPORT IS NOT REQUIRED.
+ optional bytes lzma_data = 4;
+
+ // Formerly used for bzip2 compressed data. Depreciated in 2010.
+ optional bytes OBSOLETE_bzip2_data = 5 [deprecated=true]; // Don't reuse this tag number.
+}
+
+/* A file contains an sequence of fileblock headers, each prefixed by
+their length in network byte order, followed by a data block
+containing the actual data. types staring with a "_" are reserved.
+*/
+
+message BlobHeader {
+ required string type = 1;
+ optional bytes indexdata = 2;
+ required int32 datasize = 3;
+}
+
+
diff --git a/persolijn/src/main/proto/osmformat.proto b/persolijn/src/main/proto/osmformat.proto
@@ -0,0 +1,253 @@
+/** Copyright (c) 2010 Scott A. Crosby. <[email protected]>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+*/
+
+option optimize_for = LITE_RUNTIME;
+option java_package = "crosby.binary";
+package OSMPBF;
+
+/* OSM Binary file format
+
+This is the master schema file of the OSM binary file format. This
+file is designed to support limited random-access and future
+extendability.
+
+A binary OSM file consists of a sequence of FileBlocks (please see
+fileformat.proto). The first fileblock contains a serialized instance
+of HeaderBlock, followed by a sequence of PrimitiveBlock blocks that
+contain the primitives.
+
+Each primitiveblock is designed to be independently parsable. It
+contains a string table storing all strings in that block (keys and
+values in tags, roles in relations, usernames, etc.) as well as
+metadata containing the precision of coordinates or timestamps in that
+block.
+
+A primitiveblock contains a sequence of primitive groups, each
+containing primitives of the same type (nodes, densenodes, ways,
+relations). Coordinates are stored in signed 64-bit integers. Lat&lon
+are measured in units <granularity> nanodegrees. The default of
+granularity of 100 nanodegrees corresponds to about 1cm on the ground,
+and a full lat or lon fits into 32 bits.
+
+Converting an integer to a lattitude or longitude uses the formula:
+$OUT = IN * granularity / 10**9$. Many encoding schemes use delta
+coding when representing nodes and relations.
+
+*/
+
+//////////////////////////////////////////////////////////////////////////
+//////////////////////////////////////////////////////////////////////////
+
+/* Contains the file header. */
+
+message HeaderBlock {
+ optional HeaderBBox bbox = 1;
+ /* Additional tags to aid in parsing this dataset */
+ repeated string required_features = 4;
+ repeated string optional_features = 5;
+
+ optional string writingprogram = 16;
+ optional string source = 17; // From the bbox field.
+
+ /* Tags that allow continuing an Osmosis replication */
+
+ // replication timestamp, expressed in seconds since the epoch,
+ // otherwise the same value as in the "timestamp=..." field
+ // in the state.txt file used by Osmosis
+ optional int64 osmosis_replication_timestamp = 32;
+
+ // replication sequence number (sequenceNumber in state.txt)
+ optional int64 osmosis_replication_sequence_number = 33;
+
+ // replication base URL (from Osmosis' configuration.txt file)
+ optional string osmosis_replication_base_url = 34;
+}
+
+
+/** The bounding box field in the OSM header. BBOX, as used in the OSM
+header. Units are always in nanodegrees -- they do not obey
+granularity rules. */
+
+message HeaderBBox {
+ required sint64 left = 1;
+ required sint64 right = 2;
+ required sint64 top = 3;
+ required sint64 bottom = 4;
+}
+
+
+///////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////
+
+
+message PrimitiveBlock {
+ required StringTable stringtable = 1;
+ repeated PrimitiveGroup primitivegroup = 2;
+
+ // Granularity, units of nanodegrees, used to store coordinates in this block
+ optional int32 granularity = 17 [default=100];
+ // Offset value between the output coordinates coordinates and the granularity grid in unites of nanodegrees.
+ optional int64 lat_offset = 19 [default=0];
+ optional int64 lon_offset = 20 [default=0];
+
+// Granularity of dates, normally represented in units of milliseconds since the 1970 epoch.
+ optional int32 date_granularity = 18 [default=1000];
+
+
+ // Proposed extension:
+ //optional BBox bbox = XX;
+}
+
+// Group of OSMPrimitives. All primitives in a group must be the same type.
+message PrimitiveGroup {
+ repeated Node nodes = 1;
+ optional DenseNodes dense = 2;
+ repeated Way ways = 3;
+ repeated Relation relations = 4;
+ repeated ChangeSet changesets = 5;
+}
+
+
+/** String table, contains the common strings in each block.
+
+ Note that we reserve index '0' as a delimiter, so the entry at that
+ index in the table is ALWAYS blank and unused.
+
+ */
+message StringTable {
+ repeated bytes s = 1;
+}
+
+/* Optional metadata that may be included into each primitive. */
+message Info {
+ optional int32 version = 1 [default = -1];
+ optional int64 timestamp = 2;
+ optional int64 changeset = 3;
+ optional int32 uid = 4;
+ optional uint32 user_sid = 5; // String IDs
+
+ // The visible flag is used to store history information. It indicates that
+ // the current object version has been created by a delete operation on the
+ // OSM API.
+ // When a writer sets this flag, it MUST add a required_features tag with
+ // value "HistoricalInformation" to the HeaderBlock.
+ // If this flag is not available for some object it MUST be assumed to be
+ // true if the file has the required_features tag "HistoricalInformation"
+ // set.
+ optional bool visible = 6;
+}
+
+/** Optional metadata that may be included into each primitive. Special dense format used in DenseNodes. */
+message DenseInfo {
+ repeated int32 version = 1 [packed = true];
+ repeated sint64 timestamp = 2 [packed = true]; // DELTA coded
+ repeated sint64 changeset = 3 [packed = true]; // DELTA coded
+ repeated sint32 uid = 4 [packed = true]; // DELTA coded
+ repeated sint32 user_sid = 5 [packed = true]; // String IDs for usernames. DELTA coded
+
+ // The visible flag is used to store history information. It indicates that
+ // the current object version has been created by a delete operation on the
+ // OSM API.
+ // When a writer sets this flag, it MUST add a required_features tag with
+ // value "HistoricalInformation" to the HeaderBlock.
+ // If this flag is not available for some object it MUST be assumed to be
+ // true if the file has the required_features tag "HistoricalInformation"
+ // set.
+ repeated bool visible = 6 [packed = true];
+}
+
+
+// THIS IS STUB DESIGN FOR CHANGESETS. NOT USED RIGHT NOW.
+// TODO: REMOVE THIS?
+message ChangeSet {
+ required int64 id = 1;
+//
+// // Parallel arrays.
+// repeated uint32 keys = 2 [packed = true]; // String IDs.
+// repeated uint32 vals = 3 [packed = true]; // String IDs.
+//
+// optional Info info = 4;
+
+// optional int64 created_at = 8;
+// optional int64 closetime_delta = 9;
+// optional bool open = 10;
+// optional HeaderBBox bbox = 11;
+}
+
+
+message Node {
+ required sint64 id = 1;
+ // Parallel arrays.
+ repeated uint32 keys = 2 [packed = true]; // String IDs.
+ repeated uint32 vals = 3 [packed = true]; // String IDs.
+
+ optional Info info = 4; // May be omitted in omitmeta
+
+ required sint64 lat = 8;
+ required sint64 lon = 9;
+}
+
+/* Used to densly represent a sequence of nodes that do not have any tags.
+
+We represent these nodes columnwise as five columns: ID's, lats, and
+lons, all delta coded. When metadata is not omitted,
+
+We encode keys & vals for all nodes as a single array of integers
+containing key-stringid and val-stringid, using a stringid of 0 as a
+delimiter between nodes.
+
+ ( (<keyid> <valid>)* '0' )*
+ */
+
+message DenseNodes {
+ repeated sint64 id = 1 [packed = true]; // DELTA coded
+
+ //repeated Info info = 4;
+ optional DenseInfo denseinfo = 5;
+
+ repeated sint64 lat = 8 [packed = true]; // DELTA coded
+ repeated sint64 lon = 9 [packed = true]; // DELTA coded
+
+ // Special packing of keys and vals into one array. May be empty if all nodes in this block are tagless.
+ repeated int32 keys_vals = 10 [packed = true];
+}
+
+
+message Way {
+ required int64 id = 1;
+ // Parallel arrays.
+ repeated uint32 keys = 2 [packed = true];
+ repeated uint32 vals = 3 [packed = true];
+
+ optional Info info = 4;
+
+ repeated sint64 refs = 8 [packed = true]; // DELTA coded
+}
+
+message Relation {
+ enum MemberType {
+ NODE = 0;
+ WAY = 1;
+ RELATION = 2;
+ }
+ required int64 id = 1;
+
+ // Parallel arrays.
+ repeated uint32 keys = 2 [packed = true];
+ repeated uint32 vals = 3 [packed = true];
+
+ optional Info info = 4;
+
+ // Parallel arrays
+ repeated int32 roles_sid = 8 [packed = true]; // This should have been defined as uint32 for consistency, but it is now too late to change it
+ repeated sint64 memids = 9 [packed = true]; // DELTA encoded
+ repeated MemberType types = 10 [packed = true];
+}
+
diff --git a/protobuf-native/build.gradle b/protobuf-native/build.gradle
@@ -0,0 +1,12 @@
+plugins {
+ id 'java'
+ id 'java-library'
+ id 'eclipse' // using 'eclipse'-plugin for .project/.classpath/... files
+}
+
+repositories {
+ mavenCentral()
+}
+
+dependencies {
+}
diff --git a/protobuf-native/src/main/java/protobuf/Message.java b/protobuf-native/src/main/java/protobuf/Message.java
@@ -0,0 +1,43 @@
+package protobuf;
+
+import java.io.ByteArrayInputStream;
+import java.io.InputStream;
+import java.util.Iterator;
+
+/**
+ * Functional interface representing a message parser for Protobuf data.
+ *
+ * @param <T> The type of the parsed message.
+ */
+@FunctionalInterface
+public interface Message<T> {
+
+ /**
+ * Parses a byte array as a message.
+ *
+ * @param input The byte array containing Protobuf data.
+ * @return The parsed message.
+ */
+ default T parse(byte[] input) {
+ return parse(new ByteArrayInputStream(input), input.length);
+ }
+
+ /**
+ * Parses an input stream with a specified length as a message.
+ *
+ * @param input The input stream containing Protobuf data.
+ * @param length The length of the Protobuf data in the input stream.
+ * @return The parsed message.
+ */
+ default T parse(InputStream input, int length) {
+ return parse(new MessageIterator(input, length));
+ }
+
+ /**
+ * Parses Protobuf data using a custom iterator.
+ *
+ * @param tags The iterator providing Protobuf data elements.
+ * @return The parsed message.
+ */
+ T parse(Iterator<ProtobufReader> tags);
+}
diff --git a/protobuf-native/src/main/java/protobuf/MessageIterator.java b/protobuf-native/src/main/java/protobuf/MessageIterator.java
@@ -0,0 +1,108 @@
+package protobuf;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import protobuf.exception.InputException;
+import protobuf.exception.OverflowException;
+
+/**
+ * Iterator for parsing Protocol Buffers from an input stream.
+ *
+ * <p>
+ * The iterator reads and parses wire streams from the provided input stream and
+ * produces {@link ProtobufReader} instances, representing the parsed
+ * messages.
+ *
+ * @see ProtobufReader
+ */
+public class MessageIterator implements Iterator<ProtobufReader> {
+ /**
+ * The input stream from which the Protocol Buffers are read.
+ */
+ protected final InputStream input;
+
+ /**
+ * The remaining length of the input stream. It is decremented as messages are
+ * read.
+ */
+ protected int length;
+
+ /**
+ * A list of delayed operations to be executed when there are no more messages
+ * to read.
+ */
+ protected List<Runnable> delayed = new ArrayList<>();
+
+ /**
+ * Constructs a new MessageIterator with the given input stream and length.
+ *
+ * @param input The input stream containing the Protocol Buffers.
+ * @param length The initial length of the input stream.
+ */
+ public MessageIterator(InputStream input, int length) {
+ this.input = input;
+ this.length = length;
+ }
+
+ /**
+ * Reads a variable-length integer (varint) from the input stream.
+ *
+ * @return The parsed varint value.
+ * @throws OverflowException If the input exceeds the expected size.
+ * @throws InputException If an I/O error occurs during reading.
+ */
+ private int varint() {
+ int result = 0;
+ int b = 0;
+ int shift = 0;
+ while (shift < 32 && length > 0) {
+ try {
+ b = input.read();
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ if (b == -1)
+ break;
+ length--;
+
+ result |= (b & 0x7f) << shift;
+ shift += 7;
+ if ((b & 0x80) == 0)
+ return result;
+ }
+ throw new OverflowException("input exceed");
+ }
+
+ /**
+ * Checks if there are more Protocol Buffers messages to be read.
+ *
+ * @return {@code true} if there are more messages; {@code false} otherwise.
+ */
+ @Override
+ public boolean hasNext() {
+ if (length == 0) {
+ delayed.forEach(Runnable::run);
+ delayed.clear();
+ }
+ return length > 0;
+ }
+
+ /**
+ * Reads the next wire stream and creates a {@link ProtobufReader}
+ * instance.
+ *
+ * @return The parsed {@link ProtobufReader} instance.
+ */
+ @Override
+ public ProtobufReader next() {
+ int tag = varint();
+
+ // least-significant 3 bits are the type, remaining is the tag value
+ // type = tag & 0b00000111
+ return new SimpleProtobufReader(this, WireType.values()[tag & 0x07], tag >> 3);
+ }
+}
+\ No newline at end of file
diff --git a/protobuf-native/src/main/java/protobuf/ProtobufReader.java b/protobuf-native/src/main/java/protobuf/ProtobufReader.java
@@ -0,0 +1,231 @@
+package protobuf;
+
+import java.io.InputStream;
+import java.util.Iterator;
+import java.util.function.BinaryOperator;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Supplier;
+import java.util.function.UnaryOperator;
+
+/**
+ * Represents an interface for parsing Protobuf wire elements, providing methods
+ * for reading various Protobuf data types.
+ */
+public interface ProtobufReader {
+
+ /**
+ * Gets the underlying input stream.
+ *
+ * @return The input stream.
+ */
+ InputStream getInputStream();
+
+ /**
+ * Gets the Protobuf wire type.
+ *
+ * @return The wire type.
+ */
+ WireType getType();
+
+ /**
+ * Resets the Protobuf wire type.
+ * Useful for parsing packed streams.
+ */
+ void resetType();
+
+ /**
+ * Gets the tag associated with the wire element.
+ *
+ * @return The wire tag.
+ */
+ int tag();
+
+ /**
+ * Reads a signed variable-length integer as a 64-bit integer.
+ *
+ * @return The parsed signed 64-bit integer.
+ */
+ long svarint64();
+
+ /**
+ * Parses a variable-length integer as a signed 64-bit integer.
+ *
+ * @return The parsed signed 64-bit integer.
+ */
+ long varint64();
+
+ /**
+ * Reads a signed variable-length integer as a 32-bit integer.
+ *
+ * @return The parsed signed 32-bit integer.
+ */
+ long svarint32();
+
+ /**
+ * Parses a variable-length integer as a signed 32-bit integer.
+ *
+ * @return The parsed signed 32-bit integer.
+ */
+ int varint32();
+
+ /**
+ * Skips the variable-length integer.
+ */
+ void skipVarint();
+
+ /**
+ * Reads a fixed 64-bit integer.
+ *
+ * @return The parsed 64-bit integer.
+ */
+ long fixed64();
+
+ /**
+ * Skips a fixed 64-bit integer.
+ */
+ void skip64();
+
+ /**
+ * Reads a fixed 32-bit integer.
+ *
+ * @return The parsed 32-bit integer.
+ */
+ int fixed32();
+
+ /**
+ * Skips a fixed 32-bit integer.
+ */
+ void skip32();
+
+ /**
+ * Reads a byte array.
+ *
+ * @return The read byte array.
+ */
+ byte[] bytes();
+
+ /**
+ * Skips a byte array.
+ */
+ void skipBytes();
+
+ /**
+ * Reads a string.
+ *
+ * @return The read string.
+ */
+ String string();
+
+ /**
+ * Reads a message using the provided handler.
+ *
+ * @param handler The message handler.
+ * @param <T> The type of the parsed message.
+ * @return The parsed message.
+ */
+ <T> T message(Message<T> handler);
+
+ /**
+ * Reads a message using the provided handler and applies a mapping function to
+ * the byte array.
+ *
+ * @param handler The message handler.
+ * @param map The mapping function for the byte array.
+ * @param <T> The type of the parsed message.
+ * @return The parsed message.
+ */
+ <T> T message(Message<T> handler, UnaryOperator<byte[]> map);
+
+ /**
+ * Creates an iterator for packed values.
+ *
+ * @param scalar The scalar supplier.
+ * @param <T> The type of the scalar values.
+ * @return The iterator for packed values.
+ */
+ <T> Iterator<T> packed(Supplier<T> scalar);
+
+ /**
+ * Creates an iterator for packed values, applying a mapping function to each
+ * scalar value.
+ *
+ * @param scalar The scalar supplier.
+ * @param map The mapping function for scalar values.
+ * @param <T> The type of the scalar values.
+ * @param <M> The type of the mapped values.
+ * @return The iterator for packed values.
+ */
+ <T, M> Iterator<M> packed(Supplier<T> scalar, Function<T, M> map);
+
+ /**
+ * Creates an iterator for packed values with an initial value and a binary
+ * operator.
+ *
+ * @param scalar The scalar supplier.
+ * @param init The initial value.
+ * @param operator The binary operator.
+ * @param <T> The type of the scalar values.
+ * @return The iterator for packed values.
+ */
+ <T> Iterator<T> packed(Supplier<T> scalar, T init, BinaryOperator<T> operator);
+
+ /**
+ * Creates an iterator for packed values with an initial value, a binary
+ * operator, and a mapping function.
+ *
+ * @param scalar The scalar supplier.
+ * @param map The mapping function for scalar values.
+ * @param init The initial value.
+ * @param operator The binary operator.
+ * @param <T> The type of the scalar values.
+ * @param <M> The type of the mapped values.
+ * @return The iterator for packed values.
+ */
+ <T, M> Iterator<M> packed(Supplier<T> scalar, Function<T, M> map, M init, BinaryOperator<M> operator);
+
+ /**
+ * Defers the execution of a consumer with a supplied value.
+ *
+ * @param supplier The value supplier.
+ * @param defer The consumer to be deferred.
+ * @param <T> The type of the supplied value.
+ */
+ <T> void delayed(Supplier<T> supplier, Consumer<T> defer);
+
+ /**
+ * Defers the execution of a consumer with a mapped supplied value.
+ *
+ * @param supplier The value supplier.
+ * @param map The mapping function for the supplied value.
+ * @param defer The consumer to be deferred.
+ * @param <T> The type of the supplied value.
+ */
+ <T> void delayed(Supplier<T> supplier, UnaryOperator<T> map, Consumer<T> defer);
+
+ /**
+ * Defers the execution of a consumer with a parsed message using the provided
+ * handler.
+ *
+ * @param handler The message handler.
+ * @param defer The consumer to be deferred.
+ * @param <T> The type of the parsed message.
+ */
+ <T> void delayed(Message<T> handler, Consumer<T> defer);
+
+ /**
+ * Defers the execution of a consumer with a mapped parsed message using the
+ * provided handler.
+ *
+ * @param handler The message handler.
+ * @param map The mapping function for the parsed message.
+ * @param defer The consumer to be deferred.
+ * @param <T> The type of the parsed message.
+ */
+ <T> void delayed(Message<T> handler, UnaryOperator<byte[]> map, Consumer<T> defer);
+
+ /**
+ * Skips the current wire element based on its type.
+ */
+ void skip();
+}
diff --git a/protobuf-native/src/main/java/protobuf/SimpleProtobufReader.java b/protobuf-native/src/main/java/protobuf/SimpleProtobufReader.java
@@ -0,0 +1,403 @@
+package protobuf;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.nio.charset.StandardCharsets;
+import java.util.Iterator;
+import java.util.function.BinaryOperator;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Supplier;
+import java.util.function.UnaryOperator;
+
+import protobuf.exception.InputException;
+import protobuf.exception.OverflowException;
+import protobuf.exception.WireTypeException;
+
+class SimpleProtobufReader implements ProtobufReader {
+ private final MessageIterator message;
+ private final WireType type;
+ private final int tag;
+ private boolean resetType = false;
+
+ public SimpleProtobufReader(MessageIterator message, WireType type, int tag) {
+ this.message = message;
+ this.type = type;
+ this.tag = tag;
+ }
+
+ @Override
+ public InputStream getInputStream() {
+ return message.input;
+ }
+
+ @Override
+ public WireType getType() {
+ return resetType ? null : type;
+ }
+
+ @Override
+ public void resetType() {
+ resetType = true;
+ }
+
+ @Override
+ public int tag() {
+ return tag;
+ }
+
+ @Override
+ public long svarint64() {
+ long n = varint64();
+ return (n & 0x01) == 0
+ ? (n >> 1)
+ : -(n >> 1);
+ }
+
+ @Override
+ public long varint64() {
+ return varint64(false);
+ }
+
+ public long varint64(boolean ignoreType) {
+ if (!ignoreType && getType() != null && getType() != WireType.VARINT)
+ throw new WireTypeException(WireType.VARINT, getType());
+
+ long result = 0;
+ long b = 0;
+ int shift = 0;
+ while (shift < 64 && message.length > 0) {
+ try {
+ b = message.input.read();
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ if (b == -1)
+ break;
+
+ message.length--;
+
+ result |= (b & 0x7f) << shift;
+ shift += 7;
+ if ((b & 0x80) == 0)
+ return result;
+ }
+
+ throw new OverflowException("input exceed");
+ }
+
+ @Override
+ public long svarint32() {
+ int n = varint32();
+ return (n & 0x01) == 0
+ ? (n >> 1)
+ : -(n >> 1);
+
+ }
+
+ @Override
+ public int varint32() {
+ return varint32(false);
+ }
+
+ public int varint32(boolean ignoreType) {
+ if (!ignoreType && getType() != null && getType() != WireType.VARINT)
+ throw new WireTypeException(WireType.VARINT, getType());
+
+ int result = 0;
+ int b = 0;
+ int shift = 0;
+ while (shift < 32 && message.length > 0) {
+ try {
+ b = message.input.read();
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ if (b == -1)
+ break;
+
+ message.length--;
+
+ result |= (b & 0x7f) << shift;
+ shift += 7;
+ if ((b & 0x80) == 0)
+ return result;
+ }
+ throw new OverflowException("input exceed");
+ }
+
+ @Override
+ public void skipVarint() {
+ if (getType() != null && getType() != WireType.VARINT)
+ throw new WireTypeException(WireType.VARINT, getType());
+
+ int b = 0;
+ while (message.length > 0) {
+ try {
+ b = message.input.read();
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ if (b == -1)
+ break;
+
+ message.length--;
+ if ((b & 0x80) == 0)
+ return;
+ }
+ throw new OverflowException("input exceed");
+ }
+
+ @Override
+ public long fixed64() {
+ if (getType() != null && getType() != WireType.I64)
+ throw new WireTypeException(WireType.I64, getType());
+
+ if (message.length < 8)
+ throw new OverflowException("input exceed");
+
+ byte[] bytes;
+ try {
+ bytes = message.input.readNBytes(8);
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ long result = 0;
+
+ for (int i = bytes.length - 1; i >= 0; i--) {
+ result <<= 8;
+ result |= bytes[i];
+ }
+
+ return result;
+ }
+
+ @Override
+ public void skip64() {
+ if (getType() != null && getType() != WireType.I64)
+ throw new WireTypeException(WireType.I64, getType());
+
+ if (message.length < 8)
+ throw new OverflowException("input exceed");
+
+ message.length -= 8;
+ try {
+ message.input.skipNBytes(8);
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ }
+
+ @Override
+ public int fixed32() {
+ if (getType() != null && getType() != WireType.I32)
+ throw new WireTypeException(WireType.I32, getType());
+
+ if (message.length < 4)
+ throw new OverflowException("input exceed");
+
+ byte[] bytes;
+ try {
+ bytes = message.input.readNBytes(4);
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ int result = 0;
+
+ for (int i = bytes.length - 1; i >= 0; i--) {
+ result <<= 8;
+ result |= bytes[i];
+ }
+
+ return result;
+ }
+
+ @Override
+ public void skip32() {
+ if (getType() != null && getType() != WireType.I32)
+ throw new WireTypeException(WireType.I32, getType());
+
+ if (message.length < 4)
+ throw new OverflowException("input exceed");
+
+ message.length -= 4;
+ try {
+ message.input.skipNBytes(4);
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ }
+
+ @Override
+ public byte[] bytes() {
+ if (getType() != null && getType() != WireType.LEN)
+ throw new WireTypeException(WireType.LEN, getType());
+
+ int len = varint32(true);
+ if (message.length < len)
+ throw new OverflowException("input exceed");
+
+ message.length -= len;
+ try {
+ return message.input.readNBytes(len);
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ }
+
+ @Override
+ public void skipBytes() {
+ if (getType() != null && getType() != WireType.LEN)
+ throw new WireTypeException(WireType.LEN, getType());
+
+ int len = varint32(true);
+ if (message.length < len)
+ throw new OverflowException("input exceed");
+
+ message.length -= len;
+ try {
+ message.input.skipNBytes(len);
+ } catch (IOException exc) {
+ throw new InputException(exc);
+ }
+ }
+
+ @Override
+ public String string() {
+ return new String(bytes(), StandardCharsets.UTF_8);
+ }
+
+ @Override
+ public <T> T message(Message<T> handler) {
+ if (getType() != null && getType() != WireType.LEN)
+ throw new WireTypeException(WireType.LEN, getType());
+
+ int len = varint32(true);
+ if (message.length < len)
+ throw new OverflowException("input exceed");
+
+ message.length -= len;
+
+ return handler.parse(message.input, len);
+ }
+
+ @Override
+ public <T> T message(Message<T> handler, UnaryOperator<byte[]> map) {
+ byte[] buffer = bytes();
+ return handler.parse(map.apply(buffer));
+ }
+
+ @Override
+ public <T> Iterator<T> packed(Supplier<T> scalar) {
+ return packed(scalar, v -> v);
+ }
+
+ @Override
+ public <T, M> Iterator<M> packed(Supplier<T> scalar, Function<T, M> map) {
+ if (getType() != null && getType() != WireType.LEN)
+ throw new WireTypeException(WireType.LEN, getType());
+
+ int len = varint32(true);
+ if (message.length < len)
+ throw new OverflowException("input exceed");
+
+ int end = message.length - len;
+
+ resetType();
+
+ return new Iterator<>() {
+ @Override
+ public boolean hasNext() {
+ if (message.length < end)
+ throw new OverflowException("packed string overused");
+ return message.length > end;
+ }
+
+ @Override
+ public M next() {
+ return map.apply(scalar.get());
+ }
+ };
+ }
+
+ @Override
+ public <T> Iterator<T> packed(Supplier<T> scalar, T init, BinaryOperator<T> operator) {
+ return packed(scalar, v -> v, init, operator);
+ }
+
+ @Override
+ public <T, M> Iterator<M> packed(Supplier<T> scalar, Function<T, M> map, M init, BinaryOperator<M> operator) {
+ if (getType() != null && getType() != WireType.LEN)
+ throw new WireTypeException(WireType.LEN, getType());
+
+ int len = varint32(true);
+ if (message.length < len)
+ throw new OverflowException("input exceed");
+
+ int end = message.length - len;
+
+ resetType();
+
+ return new Iterator<>() {
+ M value = init;
+
+ @Override
+ public boolean hasNext() {
+ if (message.length < end)
+ throw new OverflowException("packed string overused");
+ return message.length > end;
+ }
+
+ @Override
+ public M next() {
+ return value = operator.apply(value, map.apply(scalar.get()));
+ }
+ };
+ }
+
+ @Override
+ public <T> void delayed(Supplier<T> supplier, Consumer<T> defer) {
+ T buffer = supplier.get();
+ message.delayed.add(() -> defer.accept(buffer));
+ }
+
+ @Override
+ public <T> void delayed(Supplier<T> supplier, UnaryOperator<T> map, Consumer<T> defer) {
+ T buffer = supplier.get();
+ message.delayed.add(() -> defer.accept(map.apply(buffer)));
+ }
+
+ /// make sure that parameters are ready, thus execute it after loop
+ @Override
+ public <T> void delayed(Message<T> handler, Consumer<T> defer) {
+ byte[] buffer = bytes();
+ message.delayed.add(() -> defer.accept(handler.parse(buffer)));
+ }
+
+ @Override
+ public <T> void delayed(Message<T> handler, UnaryOperator<byte[]> map, Consumer<T> defer) {
+ byte[] buffer = bytes();
+ message.delayed.add(() -> defer.accept(handler.parse(map.apply(buffer))));
+ }
+
+ @Override
+ public void skip() {
+ switch (getType()) {
+ case VARINT:
+ skipVarint();
+ break;
+ case I64:
+ skip64();
+ break;
+ case LEN:
+ skipBytes();
+ break;
+ case I32:
+ skip32();
+ break;
+ case SGROUP:
+ case EGROUP:
+ throw new UnsupportedOperationException("cannot skip sgroup of egroup");
+ }
+ }
+}
diff --git a/protobuf-native/src/main/java/protobuf/WireType.java b/protobuf-native/src/main/java/protobuf/WireType.java
@@ -0,0 +1,94 @@
+package protobuf;
+
+/**
+ * Enum representing Protobuf wire types along with their associated possible
+ * Protobuf types.
+ */
+public enum WireType {
+
+ /**
+ * Wire type for variable-length integers.
+ */
+ VARINT(0, new String[] { "int32", "int64", "uint32", "uint64", "sint32", "sint64", "bool", "enum" }),
+
+ /**
+ * Wire type for 64-bit fixed-length values.
+ */
+ I64(1, new String[] { "fixed64", "sfixed64", "double" }),
+
+ /**
+ * Wire type for length-delimited data (strings, bytes, embedded messages, and
+ * packed repeated fields).
+ */
+ LEN(2, new String[] { "string", "bytes", "embedded messages", "packed repeated fields" }),
+
+ /**
+ * Wire type for the start of a deprecated group.
+ */
+ SGROUP(3, new String[] { "group start (deprecated)" }),
+
+ /**
+ * Wire type for the end of a deprecated group.
+ */
+ EGROUP(4, new String[] { "group end (deprecated)" }),
+
+ /**
+ * Wire type for 32-bit fixed-length values.
+ */
+ I32(5, new String[] { "fixed32", "sfixed32", "float" });
+
+ /**
+ * The numeric value associated with the wire type.
+ */
+ public final int value;
+
+ /**
+ * An array of possible Protobuf types associated with this wire type.
+ */
+ private final String[] possibleTypes;
+
+ /**
+ * Constructs a WireType enum constant with the specified value and possible
+ * types.
+ *
+ * @param value The numeric value associated with the wire type.
+ * @param possibleTypes An array of possible Protobuf types associated with this
+ * wire type.
+ */
+ private WireType(int value, String[] possibleTypes) {
+ this.value = value;
+ this.possibleTypes = possibleTypes;
+ }
+
+ /**
+ * Gets the possible Protobuf types associated with this wire type.
+ *
+ * @return An array of possible Protobuf types.
+ */
+ public String[] getPossibleTypes() {
+ return possibleTypes;
+ }
+
+ /**
+ * Returns a string representation of this wire type, including its name and
+ * possible types.
+ *
+ * @return A string representation of this wire type.
+ */
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder();
+ builder.append(this.name());
+ builder.append(" (");
+
+ for (int i = 0; i < possibleTypes.length; i++) {
+ if (i > 0)
+ builder.append(", ");
+ builder.append(possibleTypes[i]);
+ builder.append(')');
+ }
+ builder.append(')');
+
+ return builder.toString();
+ }
+}
+\ No newline at end of file
diff --git a/protobuf-native/src/main/java/protobuf/exception/InputException.java b/protobuf-native/src/main/java/protobuf/exception/InputException.java
@@ -0,0 +1,15 @@
+package protobuf.exception;
+
+public class InputException extends RuntimeException {
+ public InputException(String message) {
+ super(message);
+ }
+
+ public InputException(String message, Throwable cause) {
+ super(message, cause);
+ }
+
+ public InputException(Throwable cause) {
+ super(cause);
+ }
+}
+\ No newline at end of file
diff --git a/protobuf-native/src/main/java/protobuf/exception/OverflowException.java b/protobuf-native/src/main/java/protobuf/exception/OverflowException.java
@@ -0,0 +1,15 @@
+package protobuf.exception;
+
+public class OverflowException extends RuntimeException {
+ public OverflowException(String message) {
+ super(message);
+ }
+
+ public OverflowException(String message, Throwable cause) {
+ super(message, cause);
+ }
+
+ public OverflowException(Throwable cause) {
+ super(cause);
+ }
+}
diff --git a/protobuf-native/src/main/java/protobuf/exception/WireTypeException.java b/protobuf-native/src/main/java/protobuf/exception/WireTypeException.java
@@ -0,0 +1,21 @@
+package protobuf.exception;
+
+import protobuf.WireType;
+
+public class WireTypeException extends RuntimeException {
+ public WireTypeException(String message) {
+ super(message);
+ }
+
+ public WireTypeException(WireType expected, WireType got) {
+ super(String.format("expected type %s, but got %s", expected, got));
+ }
+
+ public WireTypeException(String message, Throwable cause) {
+ super(message, cause);
+ }
+
+ public WireTypeException(Throwable cause) {
+ super(cause);
+ }
+}
diff --git a/settings.gradle b/settings.gradle
@@ -0,0 +1,12 @@
+/*
+ * This file was generated by the Gradle 'init' task.
+ *
+ * The settings file is used to specify which projects to include in your build.
+ *
+ * Detailed information about configuring a multi-project build in Gradle can be found
+ * in the user manual at https://docs.gradle.org/7.6/userguide/multi_project_builds.html
+ */
+
+rootProject.name = 'persolijn'
+include('persolijn')
+include('protobuf-native')
