commit 33c35d2de66644cede5457682d4ec65865b6cc68 parent 5b1d3bdbce4fb4e233306ba191186d86d5c2a18e Author: Friedel Schön <[email protected]> Date: Mon, 4 Dec 2023 11:50:13 +0100 fixing signed-int parsing and split up RouterFunction Diffstat:
21 files changed, 627 insertions(+), 945 deletions(-)
diff --git a/persolijn/src/main/java/persolijn/App.java b/persolijn/src/main/java/persolijn/App.java @@ -28,7 +28,8 @@ import persolijn.osm.Graph; import persolijn.osm.message.Node; import persolijn.planner.Planner; import persolijn.planner.PlannerFunction; -import persolijn.routing.Router; +import persolijn.routing.DijkstraRouter; +import persolijn.routing.EuclidianRouter; public class App { public static void main(String[] args) throws FileNotFoundException, IOException, InterruptedException { @@ -132,12 +133,13 @@ public class App { // nodeMap.getNode(passengerPoints.get(0).startPoint), // 0)); - PlannerFunction<Node, Passenger<Node>, Point> plannerFunction = new Planner(); + PlannerFunction<Node, Passenger<Node>> plannerFunction = new Planner(); /* List<List<Node>> path = */ garageNodes.stream() - .map(g -> plannerFunction.plan(new Router(nodeMap), g, passengerNodes)) + .map(g -> plannerFunction.plan(new DijkstraRouter(nodeMap), + new EuclidianRouter(), g, passengerNodes)) .filter(Objects::nonNull) .sorted(Comparator.comparingLong(p -> Point.distance(p))) .toList(); diff --git a/persolijn/src/main/java/persolijn/WinschotenTest.java b/persolijn/src/main/java/persolijn/WinschotenTest.java @@ -17,21 +17,21 @@ 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; +import persolijn.routing.DijkstraRouter; +import persolijn.routing.EuclidianRouter; 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 + Point.of(53.1524412, 7.0408714) // 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 + Point.of(53.1481486, 7.0560514), + Point.of(53.1440320, 7.0449292) // )); List<Point> keepPoints = new ArrayList<>(garages); @@ -45,12 +45,6 @@ public class WinschotenTest { .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) { @@ -88,12 +82,13 @@ public class WinschotenTest { // nodeMap.getNode(passengerPoints.get(0).startPoint), // 0)); - PlannerFunction<Node, Passenger<Node>, Point> plannerFunction = new Planner(); + PlannerFunction<Node, Passenger<Node>> plannerFunction = new Planner(); /* List<List<Node>> path = */ garageNodes.stream() - .map(g -> plannerFunction.plan(new Router(nodeMap), g, passengerNodes)) + .map(g -> plannerFunction.plan(new DijkstraRouter(nodeMap), + new EuclidianRouter(), g, passengerNodes)) .filter(Objects::nonNull) .sorted(Comparator.comparingLong(p -> Point.distance(p))) .toList(); diff --git a/persolijn/src/main/java/persolijn/common/ContainerCollector.java b/persolijn/src/main/java/persolijn/common/ContainerCollector.java @@ -47,13 +47,13 @@ public class ContainerCollector<T extends Container<T, A>, A> implements Collect @Override public Set<Characteristics> characteristics() { Set<Characteristics> chars = new HashSet<>(); - if ((characteristics & CONCURRENT) == 1) + if ((characteristics & CONCURRENT) != 0) chars.add(Characteristics.CONCURRENT); - if ((characteristics & UNORDERED) == 1) + if ((characteristics & UNORDERED) != 0) chars.add(Characteristics.UNORDERED); - if ((characteristics & IDENTITY_FINISH) == 1) + if ((characteristics & IDENTITY_FINISH) != 0) chars.add(Characteristics.IDENTITY_FINISH); return chars; diff --git a/persolijn/src/main/java/persolijn/entity/Edge.java b/persolijn/src/main/java/persolijn/entity/Edge.java @@ -1,15 +0,0 @@ -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/osm/Graph.java b/persolijn/src/main/java/persolijn/osm/Graph.java @@ -2,12 +2,15 @@ package persolijn.osm; import java.util.Collection; import java.util.HashMap; +import java.util.HashSet; import java.util.Map; +import java.util.Set; import java.util.Map.Entry; import java.util.stream.Collector; import persolijn.common.Container; import persolijn.common.ContainerCollector; +import persolijn.osm.common.Edge; import persolijn.geo.Point; import persolijn.osm.message.Entity; import persolijn.osm.message.Node; @@ -39,7 +42,7 @@ public class Graph implements Container<Graph, Entity> { 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<Node, Set<Edge>> neighbors = new HashMap<>(); public final Map<Point, Node> pointNode = new HashMap<>(); public final Map<Point, Long> pointDistance = new HashMap<>(); @@ -52,9 +55,9 @@ public class Graph implements Container<Graph, Entity> { @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()); + for (Entry<Node, Set<Edge>> neigh : other.neighbors.entrySet()) + neighbors.computeIfAbsent(neigh.getKey(), k -> new HashSet<>()) + .addAll(neigh.getValue()); return this; } @@ -64,7 +67,7 @@ public class Graph implements Container<Graph, Entity> { ways.forEach((i, w) -> connectWay(w)); for (Node node : nodes.values()) { - if (!neighbors.containsKey(node.getID())) + if (!neighbors.containsKey(node)) continue; for (Point p : points) { @@ -79,22 +82,25 @@ public class Graph implements Container<Graph, Entity> { } 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)) + Node previous = null; + + for (long currentID : w.children) { + if (!nodes.containsKey(currentID)) continue; - Node currentNode = nodes.get(current); + Node current = nodes.get(currentID); + + if (previous != null) { + long dist = current.distanceTo(previous); - if (previousNode != null) { - neighbors.computeIfAbsent(previous, k -> new HashMap<>()) - .put(current, w); + neighbors.computeIfAbsent(previous, k -> new HashSet<>()) + .add(new Edge(current, dist, (double) dist / w.speedForwards)); + + neighbors.computeIfAbsent(current, k -> new HashSet<>()) + .add(new Edge(previous, dist, (double) dist / w.speedBackwards)); } + previous = current; - previousNode = currentNode; } } diff --git a/persolijn/src/main/java/persolijn/osm/common/Edge.java b/persolijn/src/main/java/persolijn/osm/common/Edge.java @@ -0,0 +1,15 @@ +package persolijn.osm.common; + +import persolijn.osm.message.Node; + +public class Edge { + public final Node destination; + public final long distance; + public final double time; + + public Edge(Node destination, long distance, double time) { + this.destination = destination; + this.distance = distance; + this.time = time; + } +} diff --git a/persolijn/src/main/java/persolijn/osm/message/Node.java b/persolijn/src/main/java/persolijn/osm/message/Node.java @@ -15,8 +15,8 @@ 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; + protected long score = Long.MAX_VALUE; + protected long heuristicScore = Long.MAX_VALUE; public Node(PrimitiveBlock block) { super(block); @@ -84,7 +84,7 @@ public class Node extends AbstractEntity<Node> implements Routable<Node> { @Override public int compareTo(Node other) { - return Long.compare(other.getHeuristicScore(), getHeuristicScore()); + return Long.compare(getHeuristicScore(), other.getHeuristicScore()); } @Override diff --git a/persolijn/src/main/java/persolijn/osm/message/PrimitiveGroup.java b/persolijn/src/main/java/persolijn/osm/message/PrimitiveGroup.java @@ -28,7 +28,7 @@ public class PrimitiveGroup implements Message<List<Entity>> { 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 3 -> elements.add(message.message(new Way(block))); case 4 -> elements.add(message.message(new Relation(block))); default -> message.skip(); } diff --git a/persolijn/src/main/java/persolijn/osm/message/Way.java b/persolijn/src/main/java/persolijn/osm/message/Way.java @@ -1,13 +1,11 @@ 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; @@ -15,7 +13,7 @@ import protobuf.ProtobufReader; // repeated uint32 vals = 3 [packed = true]; // optional Info info = 4; // repeated sint64 refs = 8 [packed = true]; // DELTA coded -public class Way implements Entity { +public class Way extends AbstractEntity<Way> { public enum Direction { FORWARDS(1), BACKWARDS(-1); @@ -34,129 +32,100 @@ public class Way implements Entity { } } - 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); - } + 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 final List<Long> children = new ArrayList<>(); + public double speedForwards = 0; + public double speedBackwards = 0; + + public Way(PrimitiveBlock block) { + super(block); + } - return allowed; + 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); } - 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); + return allowed; + } - if (speed.equals("none")) - speed = WAY_UNLIMITED_SPEED; + protected double getSpeed(Direction direction) { + String speed = "60"; - 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; - } - } + speed = WAY_DEFAULT_SPEED.getOrDefault(tags.get("highway"), speed); + speed = tags.getOrDefault("maxspeed", speed); - long[] array = new long[children.size()]; + if (direction == Direction.BACKWARDS) + speed = tags.getOrDefault("maxspeed:backwards", speed); - for (int i = 0; i < children.size(); i++) - array[i] = children.get(i); + if (speed.equals("none")) + speed = WAY_UNLIMITED_SPEED; - 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 Double.parseDouble(speed) / 3.6; + } - return result; + @Override + public Way parseRemaining(Iterator<ProtobufReader> tags) { + 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; + } } - } - 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; - } + if (isAllowed(Direction.FORWARDS)) + speedForwards = getSpeed(Direction.FORWARDS); - @Override - public long getID() { - return id; - } + if (isAllowed(Direction.BACKWARDS)) + speedBackwards = getSpeed(Direction.BACKWARDS); - @Override - public TagMap getTags() { - return tags; + return this; } @Override public String toString() { - return String.format("Way#%d[%dnodes]", id, children.length); + return String.format("Way#%d[%dnodes]", id, children.size()); } } diff --git a/persolijn/src/main/java/persolijn/planner/BasePlanner.java b/persolijn/src/main/java/persolijn/planner/BasePlanner.java @@ -5,15 +5,16 @@ 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; +import persolijn.routing.RouteFunction.Route; -public abstract class BasePlanner<N, P> implements PlannerFunction<N, Passenger<N>, P> { +public abstract class BasePlanner<N, P> implements PlannerFunction<N, Passenger<N>> { @Override - public List<N> plan(RouteFunction<N, P> distanceFunction, N garage, Collection<Passenger<N>> targets) { + public List<N> plan(RouteFunction<N> distanceFunction, RouteFunction<N> estimateFunction, N garage, + Collection<Passenger<N>> targets) { Stack<N> path = new Stack<>(); path.push(garage); @@ -26,25 +27,24 @@ public abstract class BasePlanner<N, P> implements PlannerFunction<N, Passenger< Map<N, Long> targetEstimate = new HashMap<>(); for (N target : currentTargets.targets) - targetEstimate.put(target, estimateLength(distanceFunction, currentTargets, target)); + targetEstimate.put(target, estimateLength(estimateFunction, currentTargets, target)); System.out.printf("route(%s, %s, %s)\n", targetEstimate, path.peek(), pathLength); - List<N> subPath = distanceFunction.route(targetEstimate, path.peek(), pathLength); + Route<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); + path.addAll(subPath.getPath()); + pathLength += subPath.getLength(); } return path; } - protected long estimateLength(RouteFunction<N, P> distanceFunction, - TargetIterable<Passenger<N>, N>.TargetEntry entry, - N current) { + protected long estimateLength(RouteFunction<N> estimateFunction, + TargetIterable<Passenger<N>, N>.TargetEntry entry, N current) { long pathLength = 0; AtomicReference<N> currentRef = new AtomicReference<>(); @@ -52,16 +52,15 @@ public abstract class BasePlanner<N, P> implements PlannerFunction<N, Passenger< 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(); + Route<N> subPath = estimateFunction.route(currentTargets.targets, currentRef.get(), 0); + + currentRef.set(subPath.getTarget()); + pathLength += subPath.getLength(); } 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); + protected abstract long getPathScore(RouteFunction<N> router, long length, Map<Passenger<N>, Long> passengers); } \ 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 @@ -1,6 +1,5 @@ package persolijn.planner; -import java.util.List; import java.util.Map; import persolijn.entity.Passenger; @@ -10,20 +9,7 @@ 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) { + protected long getPathScore(RouteFunction<Node> graph, long length, Map<Passenger<Node>, Long> passengers) { return Math.round( passengers.values().stream().mapToDouble(v -> (double) v).sum() / passengers.values().size()) diff --git a/persolijn/src/main/java/persolijn/planner/PlannerFunction.java b/persolijn/src/main/java/persolijn/planner/PlannerFunction.java @@ -6,6 +6,6 @@ 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); +public interface PlannerFunction<N, P> { + List<N> plan(RouteFunction<N> router, RouteFunction<N> estimate, N garage, Collection<P> targets); } \ No newline at end of file diff --git a/persolijn/src/main/java/persolijn/routing/AbstractDijkstraRouter.java b/persolijn/src/main/java/persolijn/routing/AbstractDijkstraRouter.java @@ -0,0 +1,224 @@ +package persolijn.routing; + +import java.util.List; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.stream.Stream; + +import persolijn.geo.Point; +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 AbstractDijkstraRouter<N extends Routable<N>, P> implements RouteFunction<N> { + /** + * 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 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, 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)); + + for (int i = path.length - 1; i >= 0; i--) { + path[i] = node; + + node = 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 Route<N> route(Map<N, Long> targets, N start, long offset) { + Queue<N> openNodes = new PriorityQueue<>(); + + double bestProgress = 0; + + openNodes.add(start); + + start.setScore(0L); + start.setHeuristicScore(getHeuristic(targets, start)); + + while (!openNodes.isEmpty()) { + N current = openNodes.poll(); + + double currentProgress = getProgress(targets, start, offset, current); + if (currentProgress > bestProgress) + onProgress(bestProgress = currentProgress); + + if (isTarget(targets, current)) { + List<N> history = getHistory(current); + return new Route<>(current, history, Point.distance(history)); + } + + forNeighbor(current, (next, 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)); + + if (!openNodes.contains(next)) + openNodes.add(next); + }); + } + 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/BaseRouter.java b/persolijn/src/main/java/persolijn/routing/BaseRouter.java @@ -1,223 +0,0 @@ -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/DijkstraRouter.java b/persolijn/src/main/java/persolijn/routing/DijkstraRouter.java @@ -0,0 +1,186 @@ +package persolijn.routing; + +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.Set; + +import persolijn.osm.common.Edge; +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 DijkstraRouter extends AbstractDijkstraRouter<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<Node, Set<Edge>> neighbors; + + /** + * Constructs a router using a graph. + * + * @param graph The graph containing nodes and ways. + */ + public DijkstraRouter(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 DijkstraRouter(Map<Long, Node> nodes, Map<Node, Set<Edge>> 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 long getCost(Node current, Node next, long distance, double speed) { + // time += Math.abs( + // Point.getAngle((Node) from.getParent(), from, to)) / Math.PI * 30; + return distance; + // 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)) + return; + + neighbors.get(node).forEach(n -> { + consumer.accept(n.destination, n.distance, n.time); + }); + } + + // 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/java/persolijn/routing/EuclidianRouter.java b/persolijn/src/main/java/persolijn/routing/EuclidianRouter.java @@ -0,0 +1,25 @@ +package persolijn.routing; + +import java.util.Map; +import java.util.Map.Entry; + +import persolijn.osm.message.Node; + +public class EuclidianRouter implements RouteFunction<Node> { + + @Override + public Route<Node> route(Map<Node, Long> targets, Node start, long offset) { + Node bestNode = null; + long bestDist = Long.MAX_VALUE; + + for (Entry<Node, Long> target : targets.entrySet()) { + long startDist = target.getKey().distanceTo(start) + target.getValue(); + if (startDist < bestDist) { + bestNode = target.getKey(); + bestDist = startDist; + } + } + + return new Route<Node>(bestNode, null, bestDist); + } +} diff --git a/persolijn/src/main/java/persolijn/routing/RouteFunction.java b/persolijn/src/main/java/persolijn/routing/RouteFunction.java @@ -3,16 +3,48 @@ package persolijn.routing; import java.util.Collection; import java.util.List; import java.util.Map; -import java.util.Map.Entry; +import java.util.stream.Collectors; /** * 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> { +@FunctionalInterface +public interface RouteFunction<N> { + public static class Route<N> { + private final N target; + private final List<N> path; + private final long length; + + public Route(N target, List<N> path, long length) { + this.target = target; + this.path = path; + this.length = length; + } + + public N getTarget() { + return target; + } + + public boolean hasPath() { + return path != null; + } + + public List<N> getPath() { + return path; + } + + public long getLength() { + return length; + } + } + + default Route<N> route(Collection<N> targets, N start, long offset) { + Map<N, Long> targetMap = targets.stream().collect(Collectors.toMap(k -> k, v -> 0L)); + return route(targetMap, start, offset); + } /** * Finds the optimal route between the start node and a collection of target @@ -24,16 +56,5 @@ public interface RouteFunction<N, P> { * @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); - + Route<N> route(Map<N, Long> targets, N start, long offset); } diff --git a/persolijn/src/main/java/persolijn/routing/Router.java b/persolijn/src/main/java/persolijn/routing/Router.java @@ -1,207 +0,0 @@ -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 @@ -1,47 +0,0 @@ -/** 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 @@ -1,253 +0,0 @@ -/** 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/src/main/java/protobuf/SimpleProtobufReader.java b/protobuf-native/src/main/java/protobuf/SimpleProtobufReader.java @@ -51,7 +51,7 @@ class SimpleProtobufReader implements ProtobufReader { long n = varint64(); return (n & 0x01) == 0 ? (n >> 1) - : -(n >> 1); + : -(n >> 1) - 1; } @Override