commit 426c5db37f16561be6aa33019ff0a522b14f74a6 parent 33c35d2de66644cede5457682d4ec65865b6cc68 Author: Friedel Schön <[email protected]> Date: Sun, 17 Dec 2023 21:56:50 +0100 a lot Diffstat:
81 files changed, 3572 insertions(+), 2413 deletions(-)
diff --git a/osm-protobuf/build.gradle b/osm-protobuf/build.gradle @@ -0,0 +1,13 @@ +plugins { + id 'java-library' +} + +repositories { + mavenCentral() +} + +dependencies { + implementation project(':protobuf-native') + + testImplementation 'junit:junit:4.13.2' +} diff --git a/osm-protobuf/src/main/java/osm/common/ArrayIterable.java b/osm-protobuf/src/main/java/osm/common/ArrayIterable.java @@ -0,0 +1,28 @@ +package osm.common; + +import java.util.Iterator; + +public class ArrayIterable<T> implements Iterable<T> { + private final T[] array; + + public ArrayIterable(T[] array) { + this.array = array; + } + + @Override + public Iterator<T> iterator() { + return new Iterator<T>() { + int index = 0; + + @Override + public boolean hasNext() { + return index < array.length; + } + + @Override + public T next() { + return array[index++]; + } + }; + } +} diff --git a/osm-protobuf/src/main/java/osm/common/ConsumingIterator.java b/osm-protobuf/src/main/java/osm/common/ConsumingIterator.java @@ -0,0 +1,44 @@ +package osm.common; + +import java.util.Iterator; +import java.util.function.Consumer; +import java.util.function.Predicate; + +public class ConsumingIterator<T> implements Iterator<T> { + private final Iterator<T> original; + private final Predicate<T> consumeWhere; + private final Consumer<T> consumer; + + private T next = null; + + public ConsumingIterator(Iterator<T> original, Predicate<T> consumeWhere, Consumer<T> consumer) { + this.original = original; + this.consumeWhere = consumeWhere; + this.consumer = consumer; + } + + @Override + public boolean hasNext() { + if (next != null) + return true; + + while (original.hasNext()) { + next = original.next(); + if (!consumeWhere.test(next)) + return true; + + consumer.accept(next); + } + return false; + } + + @Override + public T next() { + if (!hasNext()) + return null; + + T willNext = next; + next = null; + return willNext; + } +} diff --git a/osm-protobuf/src/main/java/osm/common/Container.java b/osm-protobuf/src/main/java/osm/common/Container.java @@ -0,0 +1,9 @@ +package osm.common; + +public interface Container<T, A> { + void accumulate(A value); + + void fold(T other); + + void finish(); +} diff --git a/osm-protobuf/src/main/java/osm/common/ContainerCollector.java b/osm-protobuf/src/main/java/osm/common/ContainerCollector.java @@ -0,0 +1,53 @@ +package osm.common; + +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 Set<Characteristics> characteristics; + + public ContainerCollector(Supplier<T> supplier, Set<Characteristics> 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 (a, b) -> { + a.fold(b); + return a; + }; + } + + @Override + public Function<T, T> finisher() { + return c -> { + c.finish(); + return c; + }; + } + + @Override + public Set<Characteristics> characteristics() { + return characteristics; + } +} diff --git a/osm-protobuf/src/main/java/osm/common/Edge.java b/osm-protobuf/src/main/java/osm/common/Edge.java @@ -0,0 +1,31 @@ +package osm.common; + +import osm.message.Node; +import osm.routing.RoutingEdge; + +public class Edge implements RoutingEdge<Node> { + 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; + } + + @Override + public Node getDestination() { + return destination; + } + + @Override + public long getDistance() { + return distance; + } + + @Override + public double getTime() { + return time; + } +} diff --git a/osm-protobuf/src/main/java/osm/common/RandomAccessFileInputStream.java b/osm-protobuf/src/main/java/osm/common/RandomAccessFileInputStream.java @@ -0,0 +1,48 @@ +package osm.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; + } + + @Override + public void close() throws IOException { + file.close(); + } +} diff --git a/osm-protobuf/src/main/java/osm/common/TagMap.java b/osm-protobuf/src/main/java/osm/common/TagMap.java @@ -0,0 +1,167 @@ +package osm.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/osm-protobuf/src/main/java/osm/geo/Point.java b/osm-protobuf/src/main/java/osm/geo/Point.java @@ -0,0 +1,203 @@ +package osm.geo; + +import java.util.Collection; + +import osm.common.ArrayIterable; + +/** + * Represents a geographical point with latitude and longitude coordinates. + */ +public interface Point { + + /** Earth radius in kilometers. */ + public static final int EARTH_RADIUS = 6371; + + /** Threshold for direct distance in meters squared. */ + public static final double DIRECT_DISTANCE_THRESHOLD = 50 * 50; + + /** + * Calculates the distance between two points using their latitude and + * longitude. + * + * @param a The first point. + * @param b The second point. + * @return The distance between the two points in meters. + */ + public static long distance(Point a, Point b) { + return distance(a.getLatitude(), a.getLongitude(), b.getLatitude(), b.getLongitude()); + } + + /** + * Calculates the distance between a point and specified latitude and longitude. + * + * @param aLat The latitude of the first point. + * @param aLon The longitude of the first point. + * @param b The second point. + * @return The distance between the two points in meters. + */ + public static long distance(double aLat, double aLon, Point b) { + return distance(aLat, aLon, b.getLatitude(), b.getLongitude()); + } + + /** + * Calculates the distance between two sets of latitude and longitude + * coordinates. + * + * @param aLat The latitude of the first point. + * @param aLon The longitude of the first point. + * @param bLat The latitude of the second point. + * @param bLon The longitude of the second point. + * @return The distance between the two points in meters. + */ + 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))); + } + + /** + * Calculates the center point of a collection of points. + * + * @param points The collection of points. + * @return The center point. + */ + 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()); + } + + /** + * Calculates the angle formed by three points. + * + * @param a The first point. + * @param b The second point. + * @param c The third point. + * @return The angle in radians. + */ + 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()); + } + + /** + * Calculates the total distance along a path defined by an array of points. + * + * @param path The array of points defining the path. + * @return The total distance along the path in meters. + */ + public static long distance(Point... path) { + return distance(new ArrayIterable<>(path)); + } + + /** + * Calculates the total distance along a path defined by an iterable collection + * of points. + * + * @param path The iterable collection of points defining the path. + * @return The total distance along the path in meters. + */ + 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; + } + + /** + * Creates a new Point instance with the specified latitude and longitude. + * + * @param latitude The latitude of the point. + * @param longitude The longitude of the point. + * @return A new Point instance. + */ + 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()); + } + }; + } + + /** + * Calculates the distance from this point to another point. + * + * @param other The other point. + * @return The distance to the other point in meters. + */ + default long distanceTo(Point other) { + return distance(this, other); + } + + /** + * Calculates the distance from this point to a specified latitude and + * longitude. + * + * @param latitude The latitude of the target point. + * @param longitude The longitude of the target point. + * @return The distance to the target point in meters. + */ + default long distanceTo(double latitude, double longitude) { + return distance(latitude, longitude, this); + } + + /** + * Gets the latitude of the point. + * + * @return The latitude. + */ + double getLatitude(); + + /** + * Gets the longitude of the point. + * + * @return The longitude. + */ + double getLongitude(); +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/AbstractEntity.java b/osm-protobuf/src/main/java/osm/message/AbstractEntity.java @@ -0,0 +1,130 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import osm.common.ConsumingIterator; +import osm.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. + */ +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 ConsumingIterator<>(tags, + message -> message.tag() == 1 || message.tag() == 2 || message.tag() == 3, + message -> { + 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); + } + })); + } + + /** + * 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/osm-protobuf/src/main/java/osm/message/Blob.java b/osm-protobuf/src/main/java/osm/message/Blob.java @@ -0,0 +1,78 @@ +package osm.message; + +import java.util.zip.Inflater; + +import protobuf.Message; +import protobuf.ProtobufReader; + +import java.util.Iterator; +import java.util.List; +import java.util.zip.DataFormatException; + +// 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 1 -> { + switch (headerType) { + case "OSMHeader" -> header = message.message(new HeaderBlock()); + case "OSMData" -> primitive = message.message(new PrimitiveBlock()); + } + } + case 2 -> size = message.varint32(); + 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.throwUnexpected(); + } + } + + 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/osm-protobuf/src/main/java/osm/message/BlobHeader.java b/osm-protobuf/src/main/java/osm/message/BlobHeader.java @@ -0,0 +1,31 @@ +package osm.message; + +import java.util.Iterator; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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 2 -> message.skip(); + case 3 -> size = message.varint32(); + default -> message.throwUnexpected(); + } + } + + return this; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/DenseNodes.java b/osm-protobuf/src/main/java/osm/message/DenseNodes.java @@ -0,0 +1,107 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.function.Supplier; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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 5: + stream.skip(); + 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.throwUnexpected(); + break; + } + } + + return nodes; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/Entity.java b/osm-protobuf/src/main/java/osm/message/Entity.java @@ -0,0 +1,9 @@ +package osm.message; + +import osm.common.TagMap; + +public interface Entity { + long getID(); + + TagMap getTags(); +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/HeaderBBox.java b/osm-protobuf/src/main/java/osm/message/HeaderBBox.java @@ -0,0 +1,32 @@ +package osm.message; + +import java.util.Iterator; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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.throwUnexpected(); + } + } + + return bbox; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/HeaderBlock.java b/osm-protobuf/src/main/java/osm/message/HeaderBlock.java @@ -0,0 +1,47 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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(); + case 32, 33, 34 -> message.skip(); + default -> message.throwUnexpected(); + } + } + return this; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/Node.java b/osm-protobuf/src/main/java/osm/message/Node.java @@ -0,0 +1,88 @@ +package osm.message; + +import java.util.Iterator; + +import osm.routing.RoutingNode; +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 RoutingNode<Node> { + protected double latitude, longitude; + + protected Node parent = null; + protected long score = Long.MAX_VALUE; + protected long 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 4 -> message.skip(); + case 8 -> latitude = block.latitudeOffset + block.granularity * message.svarint64(); + case 9 -> longitude = block.longitudeOffset + block.granularity * message.svarint64(); + default -> message.throwUnexpected(); + } + } + 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 String toString() { + return String.format("Node#%d", id); + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/PrimitiveBlock.java b/osm-protobuf/src/main/java/osm/message/PrimitiveBlock.java @@ -0,0 +1,46 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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 18 -> message.skip(); + case 19 -> latitudeOffset = NANO * message.varint64(); + case 20 -> longitudeOffset = NANO * message.varint64(); + default -> message.throwUnexpected(); + } + } + + return groups; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/PrimitiveGroup.java b/osm-protobuf/src/main/java/osm/message/PrimitiveGroup.java @@ -0,0 +1,40 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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.add(message.message(new Way(block))); + case 4 -> elements.add(message.message(new Relation(block))); + case 5 -> message.skip(); + default -> message.throwUnexpected(); + } + } + + return elements; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/Relation.java b/osm-protobuf/src/main/java/osm/message/Relation.java @@ -0,0 +1,35 @@ +package 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]; +// optional Info info = 4; +// 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 4, 8, 9, 10 -> message.skip(); + default -> message.throwUnexpected(); + } + } + return this; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/StringTable.java b/osm-protobuf/src/main/java/osm/message/StringTable.java @@ -0,0 +1,25 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import protobuf.Message; +import protobuf.ProtobufReader; + +// 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.throwUnexpected(); + } + } + + return table; + } +} +\ No newline at end of file diff --git a/osm-protobuf/src/main/java/osm/message/Way.java b/osm-protobuf/src/main/java/osm/message/Way.java @@ -0,0 +1,126 @@ +package osm.message; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; + +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 extends AbstractEntity<Way> { + 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 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); + } + + 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 Way parseRemaining(Iterator<ProtobufReader> tags) { + while (tags.hasNext()) { + ProtobufReader message = tags.next(); + switch (message.tag()) { + case 4 -> message.skip(); + case 8 -> message.packed(message::svarint64, 0l, Long::sum) + .forEachRemaining(children::add); + default -> message.throwUnexpected(); + } + } + + if (isAllowed(Direction.FORWARDS)) + speedForwards = getSpeed(Direction.FORWARDS); + + if (isAllowed(Direction.BACKWARDS)) + speedBackwards = getSpeed(Direction.BACKWARDS); + + return this; + } + + @Override + public String toString() { + return String.format("Way#%d[%dnodes]", id, children.size()); + } +} diff --git a/osm-protobuf/src/main/java/osm/protobuf/BlobSpliterator.java b/osm-protobuf/src/main/java/osm/protobuf/BlobSpliterator.java @@ -0,0 +1,186 @@ +package osm.protobuf; + +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 osm.common.RandomAccessFileInputStream; +import osm.message.Blob; +import osm.message.BlobHeader; +import osm.message.Entity; +import osm.message.HeaderBlock; + +/** + * A {@link Spliterator} implementation for iterating over lists of + * {@link Entity} objects parsed from OpenStreetMap blobs. + */ +public class BlobSpliterator implements Spliterator<List<Entity>> { + /** + * BlobHeader is never bigger than 64K. + */ + private static final int MAX_HEADER_SIZE = 64 * 1024; + + /** + * Blob is never bigger than 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; + + /** + * Constructs a BlobSpliterator with the specified parameters. + * + * @param input The {@link RandomAccessFile} used for reading blobs. + * @param onHeader A {@link Consumer} to handle the parsed {@link HeaderBlock} + * objects. + */ + 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 exceeds " + MAX_HEADER_SIZE + " bytes (" + headerLength + ")"); + + BlobHeader header = new BlobHeader().parse(stream, headerLength); + + if (header.size > MAX_BLOB_SIZE) + throw new RuntimeException("blob exceeds " + 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; + } + + /** + * Creates a sequential or parallel {@link Stream} from this + * {@link BlobSpliterator}. + * + * @param parallel A boolean indicating whether the stream should be parallel. + * @return A {@link Stream} of lists of {@link Entity} objects. + */ + public Stream<List<Entity>> stream(boolean parallel) { + return StreamSupport.stream(this, parallel); + } + + /** + * Creates a sequential stream from this {@link BlobSpliterator}. + * + * @return A sequential {@link Stream} of lists of {@link Entity} objects. + */ + public Stream<List<Entity>> stream() { + return stream(false); + } + + /** + * Creates a parallel stream from this {@link BlobSpliterator}. + * + * @return A parallel {@link Stream} of lists of {@link Entity} objects. + */ + public Stream<List<Entity>> parallelStream() { + return stream(true); + } +} diff --git a/osm-protobuf/src/main/java/osm/protobuf/Graph.java b/osm-protobuf/src/main/java/osm/protobuf/Graph.java @@ -0,0 +1,312 @@ +package osm.protobuf; + +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Map.Entry; +import java.util.NoSuchElementException; +import java.util.Set; +import java.util.function.Consumer; +import java.util.stream.Collector; +import java.util.stream.Collector.Characteristics; + +import osm.common.Container; +import osm.common.ContainerCollector; +import osm.common.Edge; +import osm.geo.Point; +import osm.message.Entity; +import osm.message.Node; +import osm.message.Way; +import osm.routing.RoutingGraph; + +/** + * Represents a graph used for routing on OpenStreetMap data. Implements the + * {@link Container} and {@link RoutingGraph} interfaces. + */ +public class Graph implements Container<Graph, Entity>, RoutingGraph<Node, Edge> { + /** + * Constant representing the nanosecond unit. + */ + public static final double NANO = 1e-9; + + /** + * The default speed for the router, in meters per second. + */ + public static final double DEFAULT_SPEED = 60 / 3.6; + + /** + * Constant representing the additional distance range when searching for nodes. + */ + public static final double DISTANCE_RANGE = 5; // adding 5km to the result + + /** + * Constant representing the multiplier for the additional distance range. + */ + public static final double DISTANCE_RANGE_MULTIPLIER = 1.25; // adding 25% to result + + /** + * Returns a {@link Collector} that accumulates elements into a {@link Graph}. + * + * @param points The collection of points to center the graph around. + * @return A {@link Collector} for accumulating elements into a {@link Graph}. + */ + 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), + Set.of(Characteristics.CONCURRENT, Characteristics.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<Node, Set<Edge>> neighbors = new HashMap<>(); + public final Map<Point, Node> pointNode = new HashMap<>(); + public final Map<Point, Long> pointDistance = new HashMap<>(); + + /** + * Constructs a {@link Graph} with the specified points, center, and range. + * + * @param points The collection of points in the graph. + * @param center The center point of the graph. + * @param range The range around the center within which nodes are considered. + */ + public Graph(Collection<Point> points, Point center, long range) { + this.points = points; + this.center = center; + this.range = range; + } + + /** + * Combines this graph with another graph, updating its nodes and neighbors. + * + * @param other The other graph to combine with. + * @return The combined graph. + */ + @Override + public void fold(Graph other) { + nodes.putAll(other.nodes); + for (Entry<Node, Set<Edge>> neigh : other.neighbors.entrySet()) + neighbors.computeIfAbsent(neigh.getKey(), k -> new HashSet<>()) + .addAll(neigh.getValue()); + } + + /** + * Finalizes the graph by connecting ways and determining the closest nodes to + * each point. + */ + @Override + public void finish() { + ways.forEach((i, w) -> connectWay(w)); + + for (Node node : nodes.values()) { + if (!neighbors.containsKey(node)) + 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()); + } + + /** + * Connects the nodes of a way by creating edges between consecutive nodes. + * + * @param w The way to connect. + */ + protected void connectWay(Way w) { + Node previous = null; + + for (long currentID : w.children) { + if (!nodes.containsKey(currentID)) + continue; + + Node current = nodes.get(currentID); + + if (previous != null) { + long dist = current.distanceTo(previous); + + 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; + } + } + + /** + * Accumulates an entity into the graph by adding nodes and ways based on their + * distance to the graph center. + * + * @param element The entity to accumulate. + */ + @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); + } + } + + /** + * Retrieves a node from the graph based on its point location. + * + * @param point The point location of the node to retrieve. + * @return The node corresponding to the specified point. + */ + public Node getNode(Point point) { + return pointNode.get(point); + } + + /** + * 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); + } + + /** + * 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. + * @return The cost of moving from the current node to the next node. + */ + @Override + public long getCost(Node current, Edge next) { + double time = next.getTime() + + Math.abs(Point.getAngle(current.getParent(), current, next.getDestination())) / Math.PI * 30; + return Math.round(next.getDistance() / DEFAULT_SPEED * 0.2 + time * 0.8); + } + + /** + * 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. + */ + @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(); + } + + /** + * Called when progress is made during the route calculation. + * + * @param progress The progress made, represented as a percentage. + * @param start The starting node. + * @param targets The target nodes. + */ + @Override + public void onProgress(double progress, Node start, Collection<Node> targets) { + System.out.printf("%s -> %s %6.2f%% [%s>%s]\r", + start, targets, + progress * 100, + "=".repeat((int) Math.round(progress * 50)), + " ".repeat((int) Math.round((1 - progress) * 50))); + } + + /** + * 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. + */ + @Override + public boolean isTarget(Map<Node, Long> targets, Node node) { + return targets.containsKey(node); + } + + /** + * 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. + */ + @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 Math.round(0.5 * dist / DEFAULT_SPEED); + } + + /** + * 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. + */ + @Override + public long getStartDistance(Node start, Node node) { + return start.distanceTo(node); + } + + /** + * 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. + */ + @Override + public void forNeighbor(Node node, Consumer<Edge> 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); + }); + } + + /** + * 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. + */ + @Override + public Node[] createHistoryArray(int size) { + return new Node[size]; + } +} diff --git a/osm-protobuf/src/main/java/osm/routing/RoutingEdge.java b/osm-protobuf/src/main/java/osm/routing/RoutingEdge.java @@ -0,0 +1,30 @@ +package osm.routing; + +/** + * Represents an edge in a routing graph, connecting two routing nodes. + * + * @param <N> the type of RoutingNode associated with this edge. + */ +public interface RoutingEdge<N extends RoutingNode<N>> { + + /** + * Gets the destination node of this edge. + * + * @return the destination node. + */ + N getDestination(); + + /** + * Gets the distance associated with this edge. + * + * @return the distance value. + */ + long getDistance(); + + /** + * Gets the time associated with traversing this edge. + * + * @return the time value. + */ + double getTime(); +} diff --git a/osm-protobuf/src/main/java/osm/routing/RoutingGraph.java b/osm-protobuf/src/main/java/osm/routing/RoutingGraph.java @@ -0,0 +1,207 @@ +package osm.routing; + +import java.util.Collection; +import java.util.Map; +import java.util.function.Consumer; +import java.util.stream.Stream; + +/** + * Represents a routing graph, consisting of nodes and edges, and provides + * functionality for route calculation. + * + * @param <N> The type of nodes in the graph. + * @param <E> The type of edges connecting the nodes. + */ +public interface RoutingGraph<N extends RoutingNode<N>, E extends RoutingEdge<N>> { + + /** + * Represents a route in a routing graph, consisting of a target node, a path, + * and the length of the route. + * + * @param <N> The type of nodes in the route. + */ + public static class Route<N> { + private final N target; + private final N[] path; + private final long length; + + /** + * Constructs a Route object. + * + * @param target The target node of the route. + * @param path The array of nodes representing the path from the source to the + * target. + * @param length The length of the route. + */ + public Route(N target, N[] path, long length) { + this.target = target; + this.path = path; + this.length = length; + } + + /** + * Gets the target node of the route. + * + * @return The target node. + */ + public N getTarget() { + return target; + } + + /** + * Checks if the route has a valid path. + * + * @return True if the route has a path, false otherwise. + */ + public boolean hasPath() { + return path != null; + } + + /** + * Gets the array of nodes representing the path from the source to the target. + * + * @return The array of nodes in the path. + */ + public N[] getPath() { + return path; + } + + /** + * Gets the length of the route. + * + * @return The length of the route. + */ + public long getLength() { + return length; + } + } + + /** + * 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. + */ + default double getProgress(Map<N, Long> targets, N start, long offset, N current) { + double startDistance = offset + getStartDistance(start, current); + return startDistance / (startDistance + getClosestDistance(targets, current)); + } + + /** + * 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. + */ + default 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. + */ + default 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 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. + */ + default Stream<N> getReverseHistory(N node) { + return Stream.iterate(node, RoutingNode::hasParent, RoutingNode::getParent); + } + + /** + * 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. + */ + 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. + */ + 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. + * nodes. + * @return The cost of moving from the current node to the next node. + */ + long getCost(N current, E next); + + /** + * 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. + */ + void forNeighbor(N node, Consumer<E> 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. + */ + 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. + */ + void onProgress(double progress, N start, Collection<N> targets); + + /** + * 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. + */ + 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. + */ + long getStartDistance(N start, N node); +} diff --git a/osm-protobuf/src/main/java/osm/routing/RoutingNode.java b/osm-protobuf/src/main/java/osm/routing/RoutingNode.java @@ -0,0 +1,81 @@ +package osm.routing; + +import java.util.Comparator; + +import osm.geo.Point; + +/** + * Represents a node in a routing graph that implements the {@link Point} + * interface. + * + * @param <N> The type of the node. + */ +public interface RoutingNode<N> extends Point { + + /** + * Gets the score associated with the node. + * + * @return The score value. + */ + long getScore(); + + /** + * Sets the score value for the node. + * + * @param value The score value to set. + */ + void setScore(long value); + + /** + * Gets the heuristic score associated with the node. + * + * @return The heuristic score value. + */ + long getHeuristicScore(); + + /** + * Sets the heuristic score for the node. + * + * @param total The total heuristic score to set. + */ + void setHeuristicScore(long total); + + /** + * Checks if the node has a parent. + * + * @return True if the node has a parent, false otherwise. + */ + boolean hasParent(); + + /** + * Gets the parent node. + * + * @return The parent node. + */ + N getParent(); + + /** + * Sets the parent node for this node. + * + * @param parent The parent node to set. + */ + void setParent(N parent); + + /** + * Creates a comparator based on the heuristic score for sorting nodes. + * + * @return A comparator for heuristic score sorting. + */ + static Comparator<RoutingNode<?>> heuristicComparator() { + return Comparator.comparingLong(RoutingNode::getHeuristicScore); + } + + /** + * Creates a comparator based on the score for sorting nodes. + * + * @return A comparator for score sorting. + */ + static Comparator<RoutingNode<?>> scoreComparator() { + return Comparator.comparingLong(RoutingNode::getScore); + } +} diff --git a/osm-protobuf/src/test/java/osm/protobuf/Protobuf.java b/osm-protobuf/src/test/java/osm/protobuf/Protobuf.java @@ -0,0 +1,475 @@ +package osm.protobuf; + +import crosby.binary.Osmformat.*; +import crosby.binary.file.BlockInputStream; +import crosby.binary.file.BlockReaderAdapter; +import osm.common.TagMap; + +import org.junit.Assert; +import org.junit.Test; + +import java.io.InputStream; +import java.io.PrintWriter; +import java.io.StringWriter; +import java.util.List; + +/** + * Demonstrates how to read a file. Reads sample.pbf from the resources folder + * and prints details about it to the standard output. + * + * @author Michael Tandy + */ +public class Protobuf { + static record TestRow(Class<?> type, int id, TagMap tags, Point location, long[] children) { + } + + @Test + public void test() throws Exception { + String expected = ("" + + "Got header block.\n" + + "Dense node, ID 653970877 @ 51.763603,-0.228757\n" + + "Dense node, ID 647105170 @ 51.763591,-0.234465\n" + + "Dense node, ID 672663476 @ 51.765749,-0.229070\n" + + "Dense node, ID 241806356 @ 51.768945,-0.232662\n" + + "Dense node, ID 692945017 @ 51.766185,-0.230069\n" + + "Dense node, ID 1709246734 @ 51.766433,-0.230854\n" + + "Dense node, ID 175685506 @ 51.765169,-0.229374\n" + + "Dense node, ID 647105129 @ 51.769327,-0.218457\n" + + "Dense node, ID 647105160 @ 51.768192,-0.231686\n" + + "Dense node, ID 672663473 @ 51.765530,-0.229187\n" + + "Dense node, ID 647105141 @ 51.773204,-0.222598\n" + + "Dense node, ID 25365926 @ 51.766340,-0.233556\n" + + "Dense node, ID 1685167296 @ 51.766924,-0.234783\n" + + "Dense node, ID 677439943 @ 51.763178,-0.230230\n" + + "Dense node, ID 1701110757 @ 51.766400,-0.228489\n" + + "Dense node, ID 663806673 @ 51.765470,-0.229220\n" + + "Dense node, ID 502550970 @ 51.765118,-0.233667\n" + + "Dense node, ID 692887095 @ 51.766318,-0.229190\n" + + "Dense node, ID 1685167376 @ 51.760411,-0.241161\n" + + "Dense node, ID 175697821 @ 51.765000,-0.232204\n" + + "Dense node, ID 677438877 @ 51.764126,-0.228303\n" + + "Dense node, ID 175685111 @ 51.764882,-0.229966\n" + + "Dense node, ID 647105131 @ 51.769022,-0.217223\n" + + "Dense node, ID 240134267 @ 51.764217,-0.233120\n" + + "Dense node, ID 691203111 @ 51.765755,-0.230230\n" + + "Dense node, ID 1685167394 @ 51.761213,-0.240218\n" + + "Dense node, ID 534873274 @ 51.763918,-0.236563\n" + + "Dense node, ID 676945192 @ 51.765148,-0.230615\n" + + "Dense node, ID 691203106 @ 51.764494,-0.233449\n" + + "Dense node, ID 647105155 @ 51.769580,-0.232061\n" + + "Dense node, ID 32950368 @ 51.769048,-0.232790\n" + + "Dense node, ID 647105133 @ 51.769183,-0.216784\n" + + "Dense node, ID 175683944 @ 51.763140,-0.232112\n" + + "Dense node, ID 623540467 @ 51.765719,-0.225990\n" + + "Dense node, ID 647225601 @ 51.762732,-0.231722\n" + + "Dense node, ID 32953195 @ 51.761987,-0.231091\n" + + "Dense node, ID 653970876 @ 51.763436,-0.229153\n" + + "Dense node, ID 676945352 @ 51.765646,-0.228469\n" + + "Dense node, ID 663806670 @ 51.765540,-0.228771\n" + + "Dense node, ID 1709246676 @ 51.766438,-0.231121\n" + + "Dense node, ID 647105047 @ 51.774057,-0.222895\n" + + "Dense node, ID 175697862 @ 51.765004,-0.232747\n" + + "Dense node, ID 647105145 @ 51.771007,-0.230355\n" + + "Dense node, ID 647105167 @ 51.762860,-0.236278\n" + + "Dense node, ID 1111758067 @ 51.771433,-0.216984\n" + + "Dense node, ID 647105166 @ 51.767468,-0.234229\n" + + "Dense node, ID 692887118 @ 51.766186,-0.228918\n" + + "Dense node, ID 663806658 @ 51.765679,-0.228614\n" + + "Dense node, ID 175685507 @ 51.765508,-0.229788\n" + + "Dense node, ID 647224486 @ 51.766388,-0.228706\n" + + "Dense node, ID 502552074 @ 51.766711,-0.229590\n" + + "Dense node, ID 647105132 @ 51.768905,-0.216932\n" + + "Dense node, ID 25365925 @ 51.766651,-0.233518\n" + + "Dense node, ID 623540472 @ 51.765321,-0.225475\n" + + "Dense node, ID 691202857 @ 51.766804,-0.231711\n" + + "Dense node, ID 175686201 @ 51.765721,-0.228361\n" + + "Dense node, ID 927070648 @ 51.763087,-0.232061\n" + + "Dense node, ID 25365924 @ 51.767090,-0.233453\n" + + "Dense node, ID 676945335 @ 51.765388,-0.228437\n" + + "Dense node, ID 647105127 @ 51.769321,-0.219637\n" + + "Dense node, ID 647105134 @ 51.769124,-0.216290\n" + + "Dense node, ID 30983853 @ 51.764268,-0.233185\n" + + "Dense node, ID 647105164 @ 51.767548,-0.233295\n" + + "Dense node, ID 502552081 @ 51.766833,-0.233484\n" + + "Dense node, ID 691202855 @ 51.766809,-0.231946\n" + + "Dense node, ID 647057820 @ 51.765382,-0.226710\n" + + "Dense node, ID 691202869 @ 51.767216,-0.231947\n" + + "Dense node, ID 647105159 @ 51.768849,-0.232458\n" + + "Dense node, ID 1739780291 @ 51.764890,-0.226086\n" + + "Dense node, ID 676945267 @ 51.763905,-0.228040\n" + + "Dense node, ID 663806664 @ 51.765444,-0.229274\n" + + "Dense node, ID 647105143 @ 51.771399,-0.230034\n" + + "Dense node, ID 691202858 @ 51.765928,-0.232698\n" + + "Dense node, ID 1701110775 @ 51.766290,-0.228709\n" + + "Dense node, ID 365548881 @ 51.763854,-0.232807\n" + + "Dense node, ID 647224465 @ 51.765604,-0.226263\n" + + "Dense node, ID 691202873 @ 51.766711,-0.232826\n" + + "Dense node, ID 287659881 @ 51.766233,-0.228823\n" + + "Dense node, ID 1685167328 @ 51.765389,-0.235803\n" + + "Dense node, ID 1685167381 @ 51.762135,-0.238938\n" + + "Dense node, ID 1685167371 @ 51.768683,-0.233758\n" + + "Dense node, ID 1709246791 @ 51.765771,-0.229747\n" + + "Dense node, ID 647105156 @ 51.769420,-0.232072\n" + + "Dense node, ID 647105139 @ 51.773291,-0.221257\n" + + "Dense node, ID 32953193 @ 51.763418,-0.232387\n" + + "Dense node, ID 676945199 @ 51.765151,-0.230782\n" + + "Dense node, ID 647105147 @ 51.770210,-0.231976\n" + + "Dense node, ID 672628083 @ 51.764391,-0.225433\n" + + "Dense node, ID 25365922 @ 51.768145,-0.233167\n" + + "Dense node, ID 1709246741 @ 51.765960,-0.229886\n" + + "Dense node, ID 647105153 @ 51.769673,-0.232265\n" + + "Dense node, ID 30983851 @ 51.765372,-0.233546\n" + + "Dense node, ID 691202863 @ 51.765224,-0.232225\n" + + "Dense node, ID 691202838 @ 51.767798,-0.233387\n" + + "Dense node, ID 175684459 @ 51.763370,-0.231564\n" + + "Dense node, ID 1685167313 @ 51.762503,-0.238485\n" + + "Dense node, ID 692945016 @ 51.765714,-0.230069\n" + + "Dense node, ID 25365921 @ 51.768513,-0.232722\n" + + "Dense node, ID 676945322 @ 51.765118,-0.229479\n" + + "Dense node, ID 534873251 @ 51.763658,-0.236760\n" + + "Dense node, ID 1685167341 @ 51.768171,-0.234063\n" + + "Dense node, ID 691203110 @ 51.765769,-0.230874\n" + + "Dense node, ID 676945292 @ 51.764506,-0.228754\n" + + "Dense node, ID 1685167391 @ 51.761506,-0.239827\n" + + "Dense node, ID 676945241 @ 51.763212,-0.229644\n" + + "Dense node, ID 663806653 @ 51.765898,-0.228877\n" + + "Dense node, ID 623624259 @ 51.764905,-0.234965\n" + + "Dense node, ID 1685167373 @ 51.763777,-0.237235\n" + + "Dense node, ID 676945320 @ 51.765375,-0.230143\n" + + "Dense node, ID 240134268 @ 51.764403,-0.232382\n" + + "Dense node, ID 676945316 @ 51.764949,-0.230532\n" + + "Dense node, ID 623624154 @ 51.765244,-0.234365\n" + + "Dense node, ID 647105142 @ 51.774147,-0.226321\n" + + "Dense node, ID 1739780285 @ 51.764824,-0.226000\n" + + "Dense node, ID 175697671 @ 51.765012,-0.233620\n" + + "Dense node, ID 647224613 @ 51.764970,-0.229134\n" + + "Dense node, ID 647105121 @ 51.769055,-0.221268\n" + + "Dense node, ID 692887101 @ 51.766293,-0.228488\n" + + "Dense node, ID 175683342 @ 51.763273,-0.229558\n" + + "Dense node, ID 240134269 @ 51.765577,-0.230133\n" + + "Dense node, ID 691203053 @ 51.766871,-0.230638\n" + + "Dense node, ID 1697422651 @ 51.763725,-0.228467\n" + + "Dense node, ID 534873285 @ 51.764110,-0.236786\n" + + "Dense node, ID 647105148 @ 51.770131,-0.232104\n" + + "Dense node, ID 647105165 @ 51.767482,-0.233317\n" + + "Dense node, ID 534873185 @ 51.763403,-0.236752\n" + + "Dense node, ID 175685104 @ 51.764391,-0.231506\n" + + "Dense node, ID 647105163 @ 51.768079,-0.233048\n" + + "Dense node, ID 651652536 @ 51.764591,-0.224432\n" + + "Dense node, ID 647105115 @ 51.766990,-0.227373\n" + + "Dense node, ID 677439944 @ 51.763332,-0.229790\n" + + "Dense node, ID 647105162 @ 51.768232,-0.232866\n" + + "Dense node, ID 676945319 @ 51.765218,-0.230449\n" + + "Dense node, ID 1539682123 @ 51.769102,-0.232828\n" + + "Dense node, ID 534873208 @ 51.763536,-0.236889\n" + + "Dense node, ID 647105128 @ 51.769354,-0.219090\n" + + "Dense node, ID 1739780280 @ 51.764758,-0.225914\n" + + "Dense node, ID 175698323 @ 51.767216,-0.231110\n" + + "Dense node, ID 676945189 @ 51.764650,-0.230926\n" + + "Dense node, ID 1739780294 @ 51.764955,-0.224922\n" + + "Dense node, ID 676945326 @ 51.765291,-0.229382\n" + + "Dense node, ID 663806672 @ 51.765417,-0.229059\n" + + "Dense node, ID 45169425 @ 51.769130,-0.233478\n" + + "Dense node, ID 672663469 @ 51.765930,-0.229036\n" + + "Dense node, ID 675146 @ 51.769270,-0.232860\n" + + "Dense node, ID 691203054 @ 51.766658,-0.230273\n" + + "Dense node, ID 1606957353 @ 51.760049,-0.241558\n" + + "Dense node, ID 647105125 @ 51.769248,-0.220260\n" + + "Dense node, ID 534874147 @ 51.765262,-0.235825\n" + + "Dense node, ID 14713407 @ 51.765828,-0.227391\n" + + "Dense node, ID 818056434 @ 51.766040,-0.233470\n" + + "Dense node, ID 1111758069 @ 51.769198,-0.216444\n" + + "Dense node, ID 175699187 @ 51.765663,-0.231004\n" + + "Dense node, ID 175698155 @ 51.767389,-0.230809\n" + + "Dense node, ID 691202861 @ 51.765516,-0.231002\n" + + "Dense node, ID 651594517 @ 51.763745,-0.228419\n" + + "Dense node, ID 691203051 @ 51.765901,-0.231217\n" + + "Dense node, ID 647224485 @ 51.765127,-0.226399\n" + + "Dense node, ID 1709246749 @ 51.765632,-0.230025\n" + + "Dense node, ID 677440300 @ 51.762625,-0.231624\n" + + "Dense node, ID 647105172 @ 51.764294,-0.233070\n" + + "Dense node, ID 175686498 @ 51.765424,-0.228052\n" + + "Dense node, ID 692944963 @ 51.764665,-0.233953\n" + + "Dense node, ID 663806656 @ 51.765763,-0.228715\n" + + "Dense node, ID 647105154 @ 51.769626,-0.232179\n" + + "Dense node, ID 676945317 @ 51.765015,-0.230385\n" + + "Dense node, ID 647105169 @ 51.763033,-0.235323\n" + + "Dense node, ID 692945021 @ 51.766617,-0.229479\n" + + "Dense node, ID 1709246789 @ 51.766231,-0.230173\n" + + "Dense node, ID 175686499 @ 51.765976,-0.228635\n" + + "Dense node, ID 691202866 @ 51.767110,-0.232955\n" + + "Dense node, ID 1111758072 @ 51.769507,-0.216315\n" + + "Dense node, ID 647105123 @ 51.769155,-0.220818\n" + + "Dense node, ID 672663468 @ 51.765622,-0.228672\n" + + "Dense node, ID 676945197 @ 51.765281,-0.230541\n" + + "Dense node, ID 692945020 @ 51.766471,-0.229673\n" + + "Dense node, ID 175697881 @ 51.764664,-0.232747\n" + + "Dense node, ID 175685109 @ 51.764946,-0.230095\n" + + "Dense node, ID 1685167304 @ 51.760787,-0.240738\n" + + "Dense node, ID 692944951 @ 51.764943,-0.234254\n" + + "Dense node, ID 692945019 @ 51.766225,-0.229673\n" + + "Dense node, ID 676945334 @ 51.765467,-0.228255\n" + + "Dense node, ID 175684463 @ 51.765445,-0.226790\n" + + "Dense node, ID 692944957 @ 51.764651,-0.234168\n" + + "Dense node, ID 647105144 @ 51.771332,-0.229905\n" + + "Dense node, ID 691203055 @ 51.765928,-0.230187\n" + + "Dense node, ID 676945331 @ 51.765589,-0.229749\n" + + "Dense node, ID 672663474 @ 51.765638,-0.229315\n" + + "Dense node, ID 647105146 @ 51.770283,-0.231836\n" + + "Dense node, ID 534873171 @ 51.763005,-0.237147\n" + + "Dense node, ID 647105157 @ 51.769307,-0.232308\n" + + "Dense node, ID 676945327 @ 51.765347,-0.229744\n" + + "Dense node, ID 675150 @ 51.766907,-0.229904\n" + + "Dense node, ID 663806666 @ 51.765165,-0.228973\n" + + "Dense node, ID 691202871 @ 51.766950,-0.232826\n" + + "Dense node, ID 672663477 @ 51.765646,-0.228948\n" + + "Dense node, ID 647105158 @ 51.769015,-0.232297\n" + + "Dense node, ID 673784380 @ 51.762202,-0.231241\n" + + "Dense node, ID 647105152 @ 51.769739,-0.232330\n" + + "Dense node, ID 692945022 @ 51.766344,-0.228825\n" + + "Dense node, ID 676945315 @ 51.764929,-0.230336\n" + + "Dense node, ID 676945346 @ 51.765450,-0.228506\n" + + "Dense node, ID 647105119 @ 51.768119,-0.223854\n" + + "Dense node, ID 175698430 @ 51.766924,-0.231110\n" + + "Dense node, ID 1685167387 @ 51.765901,-0.235408\n" + + "Dense node, ID 175685910 @ 51.766003,-0.227820\n" + + "Dense node, ID 820969139 @ 51.767836,-0.231358\n" + + "Dense node, ID 647105102 @ 51.763883,-0.232727\n" + + "Dense node, ID 675151 @ 51.766141,-0.228136\n" + + "Dense node, ID 175698324 @ 51.766008,-0.231131\n" + + "Dense node, ID 1685167282 @ 51.762958,-0.237989\n" + + "Dense node, ID 502552090 @ 51.765557,-0.233577\n" + + "Dense node, ID 623624155 @ 51.765449,-0.234590\n" + + "Dense node, ID 267826070 @ 51.764017,-0.232970\n" + + "Dense node, ID 25365930 @ 51.766791,-0.234972\n" + + "Dense node, ID 676945195 @ 51.765156,-0.230570\n" + + "Dense node, ID 1709246675 @ 51.766423,-0.230168\n" + + "Dense node, ID 647105137 @ 51.774248,-0.218055\n" + + "Dense node, ID 651652534 @ 51.764261,-0.225160\n" + + "Dense node, ID 676945293 @ 51.764816,-0.229133\n" + + "Dense node, ID 1692947499 @ 51.773860,-0.225851\n" + + "Dense node, ID 623624257 @ 51.765396,-0.234075\n" + + "Dense node, ID 175697824 @ 51.764998,-0.232032\n" + + "Dense node, ID 672663478 @ 51.765575,-0.229104\n" + + "Dense node, ID 1685167290 @ 51.763311,-0.237639\n" + + "Dense node, ID 390911769 @ 51.766861,-0.229798\n" + + "Dense node, ID 676945323 @ 51.765506,-0.229937\n" + + "Dense node, ID 647105136 @ 51.773720,-0.217976\n" + + "Dense node, ID 1539682039 @ 51.768036,-0.233265\n" + + "Dense node, ID 691202860 @ 51.766247,-0.230595\n" + + "Dense node, ID 1145410964 @ 51.769148,-0.232860\n" + + "Dense node, ID 647105130 @ 51.769188,-0.217728\n" + + "Dense node, ID 691203049 @ 51.766645,-0.234564\n" + + "Dense node, ID 1539682089 @ 51.768368,-0.232938\n" + + "Dense node, ID 175698550 @ 51.766911,-0.230809\n" + + "Dense node, ID 623540479 @ 51.765560,-0.224961\n" + + "Dense node, ID 677439941 @ 51.763240,-0.230472\n" + + "Dense node, ID 25365927 @ 51.766333,-0.232681\n" + + "Dense node, ID 647105135 @ 51.770431,-0.216476\n" + + "Dense node, ID 30983852 @ 51.764773,-0.233577\n" + + "Dense node, ID 647105150 @ 51.769938,-0.232265\n" + + "Dense node, ID 623624261 @ 51.764407,-0.235985\n" + + "Dense node, ID 647105149 @ 51.770024,-0.232212\n" + + "Dense node, ID 677439946 @ 51.763219,-0.229690\n" + + "Dense node, ID 691203109 @ 51.765671,-0.232912\n" + + "Dense node, ID 647105171 @ 51.764248,-0.233242\n" + + "Dense node, ID 1709246746 @ 51.766196,-0.230058\n" + + "Dense node, ID 175685106 @ 51.764728,-0.230781\n" + + "Dense node, ID 663806661 @ 51.765857,-0.228507\n" + + "Dense node, ID 677439947 @ 51.764197,-0.228387\n" + + "Dense node, ID 647105117 @ 51.767435,-0.226150\n" + + "Dense node, ID 647105168 @ 51.762754,-0.235838\n" + + "Dense node, ID 623624267 @ 51.764016,-0.233964\n" + + "Dense node, ID 1709246737 @ 51.766423,-0.230671\n" + + "Dense node, ID 175684462 @ 51.764271,-0.229245\n" + + "Dense node, ID 175698551 @ 51.766539,-0.230166\n" + + "Dense node, ID 675148 @ 51.768657,-0.232378\n" + + "Dense node, ID 676945332 @ 51.764887,-0.229157\n" + + "Dense node, ID 675149 @ 51.767913,-0.231459\n" + + "Dense node, ID 692945018 @ 51.766178,-0.229758\n" + + "Dense node, ID 623540483 @ 51.765155,-0.224456\n" + + "Dense node, ID 676945350 @ 51.765533,-0.228712\n" + + "Dense node, ID 175698975 @ 51.765729,-0.233577\n" + + "Dense node, ID 175685102 @ 51.764176,-0.232069\n" + + "Dense node, ID 676945347 @ 51.765417,-0.228572\n" + + "Dense node, ID 534873262 @ 51.763775,-0.236889\n" + + "Dense node, ID 25365931 @ 51.765437,-0.236066\n" + + "Dense node, ID 672663470 @ 51.765668,-0.229614\n" + + "Dense node, ID 647105138 @ 51.773941,-0.221418\n" + + "Dense node, ID 647105151 @ 51.769819,-0.232340\n" + + "Dense node, ID 32953194 @ 51.762232,-0.231263\n" + + "Dense node, ID 1685167315 @ 51.766349,-0.235121\n" + + "Dense node, ID 1111758071 @ 51.769058,-0.216775\n" + + "Dense node, ID 691203098 @ 51.764324,-0.234279\n" + + "Dense node, ID 175698553 @ 51.766253,-0.230172\n" + + "Dense node, ID 1685167287 @ 51.767572,-0.234395\n" + + "Dense node, ID 672663471 @ 51.765452,-0.229359\n" + + "Dense node, ID 676945325 @ 51.765209,-0.229575\n" + + "Dense node, ID 623624156 @ 51.765622,-0.234693\n" + + "Dense node, ID 647105140 @ 51.773198,-0.222341\n" + + "Dense node, ID 25365928 @ 51.766333,-0.232198\n" + + "Dense node, ID 676945329 @ 51.765389,-0.229634\n" + + "Dense node, ID 663806668 @ 51.765337,-0.228533\n" + + "Dense node, ID 692944966 @ 51.764977,-0.233985\n" + + "Dense node, ID 691203099 @ 51.764162,-0.234157\n" + + "Dense node, ID 175685100 @ 51.764091,-0.232103\n" + + "Dense node, ID 25365923 @ 51.767521,-0.233449\n" + + "Dense node, ID 647105161 @ 51.767973,-0.232169\n" + + "Dense node, ID 672663467 @ 51.765478,-0.228989\n" + + "Dense node, ID 691202854 @ 51.766818,-0.232419\n" + + "Way ID 158788812\n" + + " Nodes: 1709246789 1709246746 1709246741 1709246791 \n" + + " Key=value pairs: highway=footway \n" + + "Way ID 53588781\n" + + " Nodes: 676945323 676945327 676945325 676945326 676945331 676945323 \n" + + " Key=value pairs: landuse=garages source=survey \n" + + "Way ID 158788810\n" + + " Nodes: 1709246675 1709246737 1709246734 1709246676 \n" + + " Key=value pairs: highway=footway \n" + + "Way ID 156255508\n" + + " Nodes: 45169425 1685167371 1685167341 1685167287 1685167296 1685167315 1685167387 1685167328 1685167373 1685167290 1685167282 1685167313 1685167381 1685167391 1685167394 1685167304 1685167376 1606957353 \n" + + + " Key=value pairs: carriageway_ref=A highway=motorway lanes=3 layer=-1 lit=yes maxspeed=national name=Hatfield Tunnel oneway=yes ref=A1(M) source:maxspeed=local_knowledge tunnel=yes \n" + + + "Way ID 54932035\n" + + " Nodes: 691202854 691202855 691202857 \n" + + " Key=value pairs: highway=residential name=Jasmine Gardens source=OS_OpenData_StreetView \n" + + "Way ID 16946553\n" + + " Nodes: 175697671 175697862 175697821 175697824 \n" + + " Key=value pairs: highway=residential name=Oak Tree Close \n" + + "Way ID 52083876\n" + + " Nodes: 663806653 663806656 663806658 \n" + + " Key=value pairs: highway=service \n" + + "Way ID 55081202\n" + + " Nodes: 692944951 692944957 692944963 692944966 692944951 \n" + + " Key=value pairs: leisure=common source=yahoo \n" + + "Way ID 16946600\n" + + " Nodes: 175698430 175698550 691203053 691203054 175698551 1709246675 175698553 1709246789 691203055 \n" + + + " Key=value pairs: highway=residential name=Harmony Close source=OS_OpenData_StreetView \n" + + "Way ID 16946559\n" + + " Nodes: 175697862 175697881 \n" + + " Key=value pairs: created_by=Potlatch 0.5d highway=residential name=Oak Tree Close \n" + + "Way ID 16945846\n" + + " Nodes: 175684459 175685100 175685102 175685104 676945189 175685106 676945315 175685109 175685111 175684462 \n" + + + " Key=value pairs: highway=residential name=Stockbreach Close \n" + + "Way ID 54932037\n" + + " Nodes: 175698553 691202860 \n" + + " Key=value pairs: highway=residential name=Harmony Close source=OS_OpenData_StreetView \n" + + "Way ID 16946584\n" + + " Nodes: 175698155 175698323 175698430 1709246676 175698324 691203051 \n" + + " Key=value pairs: highway=residential name=The Minims source=OS_OpenData_StreetView \n" + + "Way ID 8361329\n" + + " Nodes: 25365926 25365927 25365928 \n" + + " Key=value pairs: highway=residential name=The Paddock source=OS_OpenData_StreetView \n" + + "Way ID 16945926\n" + + " Nodes: 175686498 175686201 663806661 175686499 \n" + + " Key=value pairs: highway=residential name=Wellfield Close \n" + + "Way ID 52083878\n" + + " Nodes: 663806664 663806666 663806668 663806670 663806672 663806673 663806664 \n" + + " Key=value pairs: leisure=common source=yahoo \n" + + "Way ID 3084923\n" + + " Nodes: 675146 1145410964 1539682123 32950368 241806356 675148 675149 820969139 175698155 675150 390911769 647224486 675151 175685910 14713407 175684463 647057820 647224485 1739780291 \n" + + + " Key=value pairs: abutters=residential highway=secondary name=Wellfield Road ref=B197 \n" + + "Way ID 8361331\n" + + " Nodes: 25365925 691203049 25365930 25365931 \n" + + " Key=value pairs: highway=residential name=Walsingham Close source=OS_OpenData_StreetView \n" + + "Way ID 54932038\n" + + " Nodes: 175699187 691202861 \n" + + " Key=value pairs: highway=residential name=Middlefield source=OS_OpenData_StreetView \n" + + "Way ID 16946620\n" + + " Nodes: 175698975 691203109 175699187 691203110 691203111 \n" + + " Key=value pairs: highway=residential name=Middlefield source=OS_OpenData_StreetView \n" + + "Way ID 157868709\n" + + " Nodes: 1701110757 1701110775 \n" + + " Key=value pairs: bridge=yes cycleway=track highway=cycleway layer=1 name=Alban Way ncn_ref=61 railway=abandoned \n" + + + "Way ID 52083877\n" + + " Nodes: 663806656 663806661 \n" + + " Key=value pairs: highway=service \n" + + "Way ID 53588764\n" + + " Nodes: 676945267 677438877 677439947 676945292 676945293 676945332 647224613 175686498 \n" + + " Key=value pairs: highway=footway \n" + + "Way ID 49161822\n" + + " Nodes: 30983851 623624257 623624154 623624259 623624261 \n" + + " Key=value pairs: highway=residential name=Worcester Road \n" + + "Way ID 49161823\n" + + " Nodes: 623624259 691203098 691203099 623624267 \n" + + " Key=value pairs: highway=residential name=Ely Close \n" + + "Way ID 53588782\n" + + " Nodes: 676945327 676945329 \n" + + " Key=value pairs: bicycle=no highway=footway source=survey \n" + + "Way ID 54932044\n" + + " Nodes: 691202869 691202855 \n" + + " Key=value pairs: highway=residential name=Jasmine Gardens source=OS_OpenData_StreetView \n" + + "Way ID 49161817\n" + + " Nodes: 623624154 623624155 623624156 \n" + + " Key=value pairs: highway=residential name=Malvern Close \n" + + "Way ID 53588780\n" + + " Nodes: 676945350 676945352 676945334 676945335 676945346 676945347 676945350 \n" + + " Key=value pairs: building=yes name=Friendship House source=survey \n" + + "Way ID 53588749\n" + + " Nodes: 676945199 676945316 676945317 676945195 676945319 676945197 676945199 \n" + + " Key=value pairs: landuse=garages source=survey \n" + + "Way ID 4673618\n" + + " Nodes: 675148 25365921 1539682089 25365922 1539682039 691202838 25365923 25365924 25365925 25365926 175698975 30983851 175697671 30983852 691203106 30983853 240134267 267826070 365548881 32953193 175683944 927070648 647225601 677440300 32953194 673784380 32953195 \n" + + + " Key=value pairs: highway=tertiary name=Lemsford Road \n" + + "Way ID 53638158\n" + + " Nodes: 677439941 677439943 677439944 677439946 676945241 175683342 653970876 653970877 1697422651 651594517 676945267 677438877 677439947 647224485 1739780291 1739780285 1739780280 672628083 651652534 651652536 1739780294 623540483 623540479 623540472 623540467 647224465 647057820 175684463 14713407 175685910 675151 692887101 647224486 647105115 647105117 647105119 647105121 647105123 647105125 647105127 647105128 647105129 647105130 647105131 647105132 1111758071 647105133 1111758069 647105134 1111758072 647105135 1111758067 647105136 647105137 647105138 647105139 647105140 647105141 647105047 1692947499 647105142 647105143 647105144 647105145 647105146 647105147 647105148 647105149 647105150 647105151 647105152 647105153 647105154 647105155 647105156 647105157 647105158 647105159 647105160 647105161 647105162 647105163 647105164 647105165 647105166 534874147 534873285 534873274 534873262 534873251 534873208 534873185 534873171 647105167 647105168 647105169 647105170 647105171 647105172 647105102 647225601 677439941 \n" + + + " Key=value pairs: landuse=residential \n" + + "Way ID 53588748\n" + + " Nodes: 676945322 676945325 676945327 676945320 676945192 676945315 \n" + + " Key=value pairs: bicycle=no highway=footway source=survey \n" + + "Way ID 50772651\n" + + " Nodes: 175685111 676945322 175685506 647224613 \n" + + " Key=value pairs: highway=residential name=Town Fields \n" + + "Way ID 158788824\n" + + " Nodes: 175685507 1709246749 \n" + + " Key=value pairs: highway=footway \n" + + "Way ID 54932042\n" + + " Nodes: 691202866 691202871 691202873 \n" + + " Key=value pairs: highway=residential name=Jasmine Gardens source=OS_OpenData_StreetView \n" + + "Way ID 53152061\n" + + " Nodes: 672663467 672663468 672663469 672663470 672663471 672663473 672663474 672663476 672663477 672663478 672663467 \n" + + + " Key=value pairs: amenity=retirement _home building=yes name=Greenacres source:area=yahoo source:name=survey \n" + + + "Way ID 53638215\n" + + " Nodes: 175685506 676945329 175685507 \n" + + " Key=value pairs: highway=service source=survey \n" + + "Way ID 157868710\n" + + " Nodes: 1701110775 287659881 692887118 1709246791 1709246749 240134269 240134268 \n" + + " Key=value pairs: cycleway=track highway=cycleway name=Alban Way ncn_ref=61 railway=abandoned \n" + + "Way ID 54932036\n" + + " Nodes: 25365927 691202858 \n" + + " Key=value pairs: highway=residential name=The Paddock source=OS_OpenData_StreetView \n" + + "Way ID 54932039\n" + + " Nodes: 175697821 691202863 \n" + + " Key=value pairs: highway=residential name=Oak Tree Close source=OS_OpenData_StreetView \n" + + "Way ID 55081204\n" + + " Nodes: 692945016 692945017 692945018 692945019 692945020 692945021 692945022 692945016 \n" + + " Key=value pairs: leisure=common \n" + + "Way ID 55071941\n" + + " Nodes: 692887118 692887101 \n" + + " Key=value pairs: foot=yes highway=footway \n" + + "Way ID 157868707\n" + + " Nodes: 240134268 240134269 1709246749 1709246791 692887118 287659881 \n" + + " Key=value pairs: cycleway=track highway=cycleway name=Alban Way ncn_ref=61 \n" + + "Got some relations to parse.\n" + + "Complete!\n").replace("\n", System.lineSeparator()); + + new BlobSpliterator(); + try (InputStream input = Protobuf.class.getResource("/sample.pbf"); + StringWriter stringWriter = new StringWriter(); + PrintWriter printWriter = new PrintWriter(stringWriter)) { + BlockReaderAdapter brad = new TestBinaryParser(printWriter); + new BlockInputStream(input, brad).process(); + + Assert.assertEquals(expected, stringWriter.toString()); + } + } +} +\ No newline at end of file diff --git a/osm-routing/build.gradle b/osm-routing/build.gradle @@ -0,0 +1,12 @@ +plugins { + id 'java-library' +} + +repositories { + mavenCentral() +} + +dependencies { + implementation project(':osm-protobuf') + implementation project(':protobuf-native') +} diff --git a/osm-routing/src/main/java/osm/planner/BasePlanner.java b/osm-routing/src/main/java/osm/planner/BasePlanner.java @@ -0,0 +1,116 @@ +package osm.planner; + +import java.util.Collection; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Stack; +import java.util.concurrent.atomic.AtomicReference; + +import osm.planner.TargetIterable.TargetSet; +import osm.routing.RoutingEdge; +import osm.routing.RoutingGraph; +import osm.routing.RoutingNode; +import osm.routing.RoutingStrategy; +import osm.routing.RoutingGraph.Route; +import osm.routing.entity.Passenger; + +/** + * An abstract base class implementing the {@link PlannerFunction} interface for + * planning routes in a routing graph. + * + * @param <N> The type of nodes in the graph. + * @param <E> The type of edges connecting the nodes. + */ +public abstract class BasePlanner<N extends RoutingNode<N>, E extends RoutingEdge<N>> implements PlannerFunction<N, E> { + + /** + * Plans a route based on the specified routing graph, distance function, + * estimate function, garage node, and targets. + * + * @param router The routing graph. + * @param distanceFunction The strategy for calculating distance between nodes. + * @param estimateFunction The strategy for estimating remaining distance to + * targets. + * @param garage The starting node representing the garage or initial + * location. + * @param targets The collection of passengers with their destination + * nodes. + * @return A list of nodes representing the planned route. + */ + @Override + public List<N> plan( + RoutingGraph<N, E> router, + RoutingStrategy<N, E> distanceFunction, + RoutingStrategy<N, E> estimateFunction, + 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 (TargetSet<Passenger<N>, N> currentTargets : targetIterable) { + Map<N, Long> targetEstimate = new HashMap<>(); + + for (N target : currentTargets.targets) + targetEstimate.put(target, estimateLength(router, estimateFunction, currentTargets, target)); + + Route<N> subPath = distanceFunction.route(router, targetEstimate, path.peek(), pathLength); + if (subPath == null) { + System.out.println("nothing found searching for " + currentTargets); + return null; + } + + path.addAll(List.of(subPath.getPath())); + pathLength += subPath.getLength(); + } + + return path; + } + + /** + * Estimates the length of a route based on the specified routing graph, + * estimate function, entry, and current node. + * + * @param router The routing graph. + * @param estimateFunction The strategy for estimating remaining distance to + * targets. + * @param entry The set of current targets and their visitation + * states. + * @param current The current node. + * @return The estimated length of the route. + */ + protected long estimateLength(RoutingGraph<N, E> router, + RoutingStrategy<N, E> estimateFunction, + TargetSet<Passenger<N>, N> entry, N current) { + long pathLength = 0; + + AtomicReference<N> currentRef = new AtomicReference<>(); + currentRef.set(current); + + for (TargetSet<Passenger<N>, N> currentTargets : entry.doContinue(currentRef::get)) { + Route<N> subPath = estimateFunction.route(router, currentTargets.targets, currentRef.get(), 0); + + currentRef.set(subPath.getTarget()); + pathLength += subPath.getLength(); + } + + return pathLength; + } + + /** + * Calculates the path score based on the specified routing graph, route length, + * and passenger distances. + * + * @param router The routing graph. + * @param length The length of the calculated route. + * @param passengers A map containing passengers and their respective distances. + * @return The calculated path score, considering the average passenger distance + * and the total route length. + */ + protected abstract long getPathScore(RoutingGraph<N, E> router, long length, Map<Passenger<N>, Long> passengers); +} diff --git a/osm-routing/src/main/java/osm/planner/Planner.java b/osm-routing/src/main/java/osm/planner/Planner.java @@ -0,0 +1,35 @@ +package osm.planner; + +import java.util.Map; + +import osm.common.Edge; +import osm.message.Node; +import osm.routing.RoutingGraph; +import osm.routing.entity.Passenger; + +/** + * A concrete implementation of the base planner for a graph with nodes of type + * {@link Node} and edges of type {@link Edge}. + * This implementation calculates the path score based on the average passenger + * distance and the total length of the route. + */ +public class Planner extends BasePlanner<Node, Edge> { + + /** + * Calculates the path score based on the specified routing graph, route length, + * and passenger distances. + * + * @param graph The routing graph. + * @param length The length of the calculated route. + * @param passengers A map containing passengers and their respective distances. + * @return The calculated path score, considering the average passenger distance + * and the total route length. + */ + @Override + protected long getPathScore(RoutingGraph<Node, Edge> graph, long length, Map<Passenger<Node>, Long> passengers) { + return Math.round( + passengers.values().stream().mapToDouble(v -> (double) v).sum() + / passengers.values().size()) + + length; + } +} diff --git a/osm-routing/src/main/java/osm/planner/PlannerFunction.java b/osm-routing/src/main/java/osm/planner/PlannerFunction.java @@ -0,0 +1,41 @@ +package osm.planner; + +import java.util.Collection; +import java.util.List; + +import osm.routing.RoutingEdge; +import osm.routing.RoutingGraph; +import osm.routing.RoutingNode; +import osm.routing.RoutingStrategy; +import osm.routing.entity.Passenger; + +/** + * Represents a planner function that generates a list of nodes for a given + * routing scenario. + * + * @param <N> The type of nodes in the graph. + * @param <E> The type of edges connecting the nodes. + */ +@FunctionalInterface +public interface PlannerFunction<N extends RoutingNode<N>, E extends RoutingEdge<N>> { + + /** + * Plans a route based on the specified routing graph, distance function, + * estimate function, garage node, and targets. + * + * @param router The routing graph. + * @param distanceFunction The strategy for calculating distance between nodes. + * @param estimateFunction The strategy for estimating remaining distance to + * targets. + * @param garage The starting node representing the garage or initial + * location. + * @param targets The collection of passengers with their destination + * nodes. + * @return A list of nodes representing the planned route. + */ + List<N> plan( + RoutingGraph<N, E> router, + RoutingStrategy<N, E> distanceFunction, + RoutingStrategy<N, E> estimateFunction, + N garage, Collection<Passenger<N>> targets); +} diff --git a/osm-routing/src/main/java/osm/planner/TargetIterable.java b/osm-routing/src/main/java/osm/planner/TargetIterable.java @@ -0,0 +1,254 @@ +package osm.planner; + +import java.util.List; +import java.util.AbstractSet; +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; + +/** + * An iterable representing a set of target entries, each associated with a + * visitation state. + * + * @param <P> The type of target points. + * @param <T> The type of elements in the iterable. + */ +public class TargetIterable<P, T> implements Iterable<TargetIterable.TargetSet<P, T>> { + + /** + * Enumeration representing the visitation states of target points in the + * {@link TargetIterable}. + */ + public static enum Visited { + /** + * Represents a target point that has finished processing. + */ + FINISHED(false, null), + + /** + * Represents a target point that is currently being processed. + */ + BUSY(true, FINISHED), + + /** + * Represents a target point that is pending processing. + */ + PENDING(true, BUSY); + + private final boolean include; + private final Visited next; + + /** + * Constructs a Visited enum with the specified inclusion flag and the next + * visitation state. + * + * @param include The flag indicating whether the target point should be + * included in processing. + * @param next The next visitation state after this one. + */ + private Visited(boolean include, Visited next) { + this.include = include; + this.next = next; + } + + /** + * Gets the next visitation state after this one. + * + * @return The next visitation state. + */ + public Visited getNext() { + return next; + } + + /** + * Checks if the target point should be included in processing. + * + * @return {@code true} if the target point should be included, {@code false} + * otherwise. + */ + public boolean doInclude() { + return include; + } + } + + /** + * Represents a set of target entries associated with their visitation states. + * + * @param <P> The type of target points. + * @param <T> The type of elements in the set. + */ + public static class TargetSet<P, T> extends AbstractSet<T> { + + /** + * The iterable to which this set belongs. + */ + public final TargetIterable<P, T> iterable; + + /** + * A map associating each target point with its visitation state. + */ + public final Map<P, Visited> targetMap; + + /** + * The list of target elements in this set. + */ + public final List<T> targets; + + /** + * Constructs a TargetSet with the specified iterable, target map, and target + * elements. + * + * @param iterable The iterable to which this set belongs. + * @param targetMap A map associating each target point with its visitation + * state. + * @param targets The list of target elements in this set. + */ + private TargetSet(TargetIterable<P, T> iterable, Map<P, Visited> targetMap, List<T> targets) { + this.iterable = iterable; + this.targetMap = targetMap; + this.targets = targets; + } + + /** + * Returns a string representation of this TargetSet. + * + * @return A string representation of this TargetSet. + */ + @Override + public String toString() { + return String.format("TargetSet(%s)", targets); + } + + /** + * Returns the number of elements in this set. + * + * @return The number of elements in this set. + */ + @Override + public int size() { + return targets.size(); + } + + /** + * Returns an iterator over the elements in this set. + * + * @return An iterator over the elements in this set. + */ + @Override + public Iterator<T> iterator() { + return targets.iterator(); + } + + /** + * Creates a new iterable to continue processing with additional targets. + * + * @param supplier A supplier providing the next element. + * @return An iterable with additional targets. + */ + public Iterable<TargetSet<P, T>> doContinue(Supplier<T> supplier) { + return new TargetIterable<>(iterable.garage, iterable.targetList, targetMap, + supplier, iterable.startPoint, iterable.targetPoint); + } + } + + 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; + + /** + * Constructs a TargetIterable. + * + * @param garage The garage element. + * @param targetList The list of target points. + * @param targetMap A map associating each target point with its visitation + * state. + * @param supplier A supplier providing the next element. + * @param startPoint A function providing the starting point for a target. + * @param targetPoint A function providing the target point for a target. + */ + public TargetIterable(T garage, Collection<P> targetList, Map<P, Visited> targetMap, + 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 = targetMap; + } + + /** + * Constructs a TargetIterable with an empty target map. + * + * @param garage The garage element. + * @param targetList The list of target points. + * @param supplier A supplier providing the next element. + * @param startPoint A function providing the starting point for a target. + * @param targetPoint A function providing the target point for a target. + */ + 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(); + } + + @Override + public Iterator<TargetSet<P, T>> iterator() { + return new Iterator<TargetIterable.TargetSet<P, T>>() { + final Map<P, Visited> targetMap = new HashMap<>(TargetIterable.this.originalMap); + + private Visited checkVisited(P p, T current) { + Visited visited = targetMap.getOrDefault(p, Visited.PENDING); + + if (startPoint.apply(p).equals(current) && visited == Visited.PENDING) + visited = visited.getNext(); + + if (targetPoint.apply(p).equals(current) && visited == Visited.BUSY) + visited = visited.getNext(); + + return visited; + } + + @Override + public boolean hasNext() { + T current = supplier.get(); + + return current != garage || targetList.stream() + .map(p -> checkVisited(p, current)) + .anyMatch(Visited::doInclude); + } + + @Override + public TargetSet<P, T> 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 TargetSet<>(TargetIterable.this, targetMap, List.of(garage)); + + return new TargetSet<>(TargetIterable.this, targetMap, targetNodes); + } + }; + } +} diff --git a/osm-routing/src/main/java/osm/routing/RoutingStrategy.java b/osm-routing/src/main/java/osm/routing/RoutingStrategy.java @@ -0,0 +1,46 @@ +package osm.routing; + +import java.util.Collection; +import java.util.Map; +import java.util.stream.Collectors; + +import osm.routing.RoutingGraph.Route; + +/** + * Represents a routing strategy for finding the optimal route between two + * points on a graph. + * + * @param <N> The type of nodes in the graph. + * @param <E> The type of edges connecting the nodes. + */ +@FunctionalInterface +public interface RoutingStrategy<N extends RoutingNode<N>, E extends RoutingEdge<N>> { + + /** + * Finds the optimal route between the start node and a collection of target + * nodes using the default offset value of 0. + * + * @param router The routing graph. + * @param targets The target nodes and their distances. + * @param start The starting node. + * @return A Route object representing the optimal route from the start to a + * target node. + */ + default Route<N> route(RoutingGraph<N, E> router, Collection<N> targets, N start, long offset) { + Map<N, Long> targetMap = targets.stream().collect(Collectors.toMap(k -> k, v -> 0L)); + return route(router, targetMap, start, offset); + } + + /** + * Finds the optimal route between the start node and a collection of target + * nodes with a specified offset value. + * + * @param router The routing graph. + * @param targets The target nodes and their distances. + * @param start The starting node. + * @param offset The offset value. + * @return A Route object representing the optimal route from the start to a + * target node. + */ + Route<N> route(RoutingGraph<N, E> router, Map<N, Long> targets, N start, long offset); +} diff --git a/osm-routing/src/main/java/osm/routing/entity/Interval.java b/osm-routing/src/main/java/osm/routing/entity/Interval.java @@ -0,0 +1,63 @@ +package osm.routing.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/osm-routing/src/main/java/osm/routing/entity/Passenger.java b/osm-routing/src/main/java/osm/routing/entity/Passenger.java @@ -0,0 +1,38 @@ +package osm.routing.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; + } + + @Override + public T get(int i) { + return switch (i) { + case 0 -> startPoint; + case 1 -> targetPoint; + default -> throw new IndexOutOfBoundsException("Passenger can only hold 2 points"); + }; + } + + @Override + public int size() { + return 2; + } +} +\ No newline at end of file diff --git a/osm-routing/src/main/java/osm/routing/strategy/BestFirstRouter.java b/osm-routing/src/main/java/osm/routing/strategy/BestFirstRouter.java @@ -0,0 +1,76 @@ +package osm.routing.strategy; + +import java.util.HashSet; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Set; + +import osm.geo.Point; +import osm.routing.RoutingEdge; +import osm.routing.RoutingGraph; +import osm.routing.RoutingNode; +import osm.routing.RoutingStrategy; +import osm.routing.RoutingGraph.Route; + +/** + * 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 class BestFirstRouter<N extends RoutingNode<N>, E extends RoutingEdge<N>, P> implements RoutingStrategy<N, E> { + /** + * 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(RoutingGraph<N, E> graph, Map<N, Long> targets, N start, long offset) { + Queue<N> openNodes = new PriorityQueue<>(RoutingNode.scoreComparator()); + Set<N> closedNodes = new HashSet<>(); + + double bestProgress = 0; + + openNodes.add(start); + closedNodes.add(start); + + start.setScore(0L); + + while (!openNodes.isEmpty()) { + N current = openNodes.poll(); + + double currentProgress = graph.getProgress(targets, start, offset, current); + if (currentProgress > bestProgress) + graph.onProgress(bestProgress = currentProgress, start, targets.keySet()); + + if (graph.isTarget(targets, current)) { + N[] history = graph.getHistory(current); + return new Route<>(current, history, Point.distance(history)); + } + + graph.forNeighbor(current, edge -> { + N next = edge.getDestination(); + + if (closedNodes.contains(next)) + return; + + long totalWeight = current.getScore() + graph.getCost(current, edge); + + next.setParent(current); + next.setScore(totalWeight); + + closedNodes.add(next); + openNodes.add(next); + }); + } + return null; + } + +} +\ No newline at end of file diff --git a/osm-routing/src/main/java/osm/routing/strategy/DijkstraRouter.java b/osm-routing/src/main/java/osm/routing/strategy/DijkstraRouter.java @@ -0,0 +1,78 @@ +package osm.routing.strategy; + +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Queue; + +import osm.geo.Point; +import osm.routing.RoutingEdge; +import osm.routing.RoutingGraph; +import osm.routing.RoutingNode; +import osm.routing.RoutingStrategy; +import osm.routing.RoutingGraph.Route; + +/** + * A base class for implementing routing algorithms between two points on a + * graph using Dijkstra's algorithm. + * + * @param <N> The type of nodes in the graph. + * @param <E> The type of edges in the graph. + */ +public class DijkstraRouter<N extends RoutingNode<N>, E extends RoutingEdge<N>> implements RoutingStrategy<N, E> { + + /** + * Finds the optimal route between the start node and a collection of target + * nodes using Dijkstra's algorithm. + * + * @param graph The graph on which the routing is performed. + * @param targets The target nodes and their distances. + * @param start The starting node. + * @param offset The offset value. + * @return A {@link Route} representing the optimal route from the start to a + * target + * node, or null if no route is found. + */ + @Override + public Route<N> route(RoutingGraph<N, E> graph, Map<N, Long> targets, N start, long offset) { + Queue<N> openNodes = new PriorityQueue<>(RoutingNode.heuristicComparator()); + + double bestProgress = 0; + + openNodes.add(start); + + start.setScore(0L); + start.setHeuristicScore(graph.getHeuristic(targets, start)); + + while (!openNodes.isEmpty()) { + N current = openNodes.poll(); + + double currentProgress = graph.getProgress(targets, start, offset, current); + if (currentProgress > bestProgress) + graph.onProgress(bestProgress = currentProgress, start, targets.keySet()); + + if (graph.isTarget(targets, current)) { + N[] history = graph.getHistory(current); + return new Route<>(current, history, Point.distance(history)); + } + + graph.forNeighbor(current, edge -> { + N next = edge.getDestination(); + if (next.equals(current)) + return; + + long totalWeight = current.getScore() + graph.getCost(current, edge); + + if (totalWeight >= next.getScore()) + return; + + next.setParent(current); + next.setScore(totalWeight); + next.setHeuristicScore(totalWeight + graph.getHeuristic(targets, next)); + + if (!openNodes.contains(next)) + openNodes.add(next); + }); + } + return null; + } +} diff --git a/osm-routing/src/main/java/osm/routing/strategy/EuclidianRouter.java b/osm-routing/src/main/java/osm/routing/strategy/EuclidianRouter.java @@ -0,0 +1,47 @@ +package osm.routing.strategy; + +import java.util.Map; +import java.util.Map.Entry; + +import osm.message.Node; +import osm.routing.RoutingEdge; +import osm.routing.RoutingGraph; +import osm.routing.RoutingStrategy; +import osm.routing.RoutingGraph.Route; + +/** + * A routing strategy that calculates the route based on Euclidean distance from + * the + * start node to the target nodes. + * + * @param <E> The type of edges connecting the nodes. + */ +public class EuclidianRouter<E extends RoutingEdge<Node>> implements RoutingStrategy<Node, E> { + + /** + * Calculates the route based on Euclidean distance from the start node to the + * target nodes. + * + * @param router The routing graph. + * @param targets The target nodes and their distances. + * @param start The starting node. + * @param offset The offset value. + * @return A Route object representing the optimal route based on Euclidean + * distance. + */ + @Override + public Route<Node> route(RoutingGraph<Node, E> router, 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/build.gradle b/persolijn/build.gradle @@ -1,7 +1,6 @@ plugins { id 'java' id 'application' // using default 'app'-plugin - id 'eclipse' // using 'eclipse'-plugin for .project/.classpath/... files } repositories { @@ -9,6 +8,8 @@ repositories { } dependencies { + implementation project(':osm-protobuf') + implementation project(':osm-routing') implementation project(':protobuf-native') } diff --git a/persolijn/src/main/java/persolijn/App.java b/persolijn/src/main/java/persolijn/App.java @@ -19,17 +19,18 @@ 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.DijkstraRouter; -import persolijn.routing.EuclidianRouter; +import osm.routing.entity.Interval; +import osm.routing.entity.Passenger; +import osm.routing.entity.Interval.IntervalFinal; +import osm.routing.strategy.DijkstraRouter; +import osm.routing.strategy.EuclidianRouter; +import osm.common.Edge; +import osm.geo.Point; +import osm.message.Node; +import osm.planner.Planner; +import osm.planner.PlannerFunction; +import osm.protobuf.BlobSpliterator; +import osm.protobuf.Graph; public class App { public static void main(String[] args) throws FileNotFoundException, IOException, InterruptedException { @@ -133,15 +134,17 @@ public class App { // nodeMap.getNode(passengerPoints.get(0).startPoint), // 0)); - PlannerFunction<Node, Passenger<Node>> plannerFunction = new Planner(); + PlannerFunction<Node, Edge> plannerFunction = new Planner(); /* List<List<Node>> path = */ garageNodes.stream() - .map(g -> plannerFunction.plan(new DijkstraRouter(nodeMap), - new EuclidianRouter(), g, passengerNodes)) + .map(g -> plannerFunction.plan( + nodeMap, + new DijkstraRouter<>(), new EuclidianRouter<>(), + g, passengerNodes)) .filter(Objects::nonNull) - .sorted(Comparator.comparingLong(p -> Point.distance(p))) + .sorted(Comparator.comparingLong(Point::distance)) .toList(); // List<List<Node>> path = garageNodes.stream() diff --git a/persolijn/src/main/java/persolijn/WinschotenTest.java b/persolijn/src/main/java/persolijn/WinschotenTest.java @@ -12,15 +12,16 @@ 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.planner.Planner; -import persolijn.planner.PlannerFunction; -import persolijn.routing.DijkstraRouter; -import persolijn.routing.EuclidianRouter; +import osm.common.Edge; +import osm.geo.Point; +import osm.message.Node; +import osm.planner.Planner; +import osm.planner.PlannerFunction; +import osm.protobuf.BlobSpliterator; +import osm.protobuf.Graph; +import osm.routing.entity.Passenger; +import osm.routing.strategy.DijkstraRouter; +import osm.routing.strategy.EuclidianRouter; public class WinschotenTest { public static void main(String[] args) throws FileNotFoundException, IOException, InterruptedException { @@ -30,9 +31,8 @@ public class WinschotenTest { final List<Passenger<Point>> passengerPoints = List.of( new Passenger<>( - Point.of(53.1481486, 7.0560514), - Point.of(53.1440320, 7.0449292) // - )); + Point.of(53.1440204, 7.0442075), // + Point.of(53.1481486, 7.0560514))); List<Point> keepPoints = new ArrayList<>(garages); passengerPoints.forEach(keepPoints::addAll); @@ -82,15 +82,17 @@ public class WinschotenTest { // nodeMap.getNode(passengerPoints.get(0).startPoint), // 0)); - PlannerFunction<Node, Passenger<Node>> plannerFunction = new Planner(); + PlannerFunction<Node, Edge> plannerFunction = new Planner(); /* List<List<Node>> path = */ garageNodes.stream() - .map(g -> plannerFunction.plan(new DijkstraRouter(nodeMap), - new EuclidianRouter(), g, passengerNodes)) + .map(g -> plannerFunction.plan( + nodeMap, + new DijkstraRouter<>(), new EuclidianRouter<>(), + g, passengerNodes)) .filter(Objects::nonNull) - .sorted(Comparator.comparingLong(p -> Point.distance(p))) + .sorted(Comparator.comparingLong(Point::distance)) .toList(); } } diff --git a/persolijn/src/main/java/persolijn/common/Container.java b/persolijn/src/main/java/persolijn/common/Container.java @@ -1,9 +0,0 @@ -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 @@ -1,61 +0,0 @@ -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) != 0) - chars.add(Characteristics.CONCURRENT); - - if ((characteristics & UNORDERED) != 0) - chars.add(Characteristics.UNORDERED); - - if ((characteristics & IDENTITY_FINISH) != 0) - 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 @@ -1,14 +0,0 @@ -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 @@ -1,44 +0,0 @@ -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 @@ -1,167 +0,0 @@ -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/Interval.java b/persolijn/src/main/java/persolijn/entity/Interval.java @@ -1,63 +0,0 @@ -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 @@ -1,36 +0,0 @@ -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 @@ -1,106 +0,0 @@ -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 @@ -1,158 +0,0 @@ -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 @@ -1,127 +0,0 @@ -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; -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<Node, Set<Edge>> 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<Node, Set<Edge>> neigh : other.neighbors.entrySet()) - neighbors.computeIfAbsent(neigh.getKey(), k -> new HashSet<>()) - .addAll(neigh.getValue()); - - return this; - } - - @Override - public void finish() { - ways.forEach((i, w) -> connectWay(w)); - - for (Node node : nodes.values()) { - if (!neighbors.containsKey(node)) - 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) { - Node previous = null; - - for (long currentID : w.children) { - if (!nodes.containsKey(currentID)) - continue; - - Node current = nodes.get(currentID); - - if (previous != null) { - long dist = current.distanceTo(previous); - - 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; - } - } - - @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/common/Edge.java b/persolijn/src/main/java/persolijn/osm/common/Edge.java @@ -1,15 +0,0 @@ -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/AbstractEntity.java b/persolijn/src/main/java/persolijn/osm/message/AbstractEntity.java @@ -1,139 +0,0 @@ -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 @@ -1,77 +0,0 @@ -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 @@ -1,29 +0,0 @@ -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 @@ -1,104 +0,0 @@ -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 @@ -1,9 +0,0 @@ -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 @@ -1,32 +0,0 @@ -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 @@ -1,46 +0,0 @@ -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 @@ -1,95 +0,0 @@ -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; - protected long 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(getHeuristicScore(), other.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 @@ -1,45 +0,0 @@ -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 @@ -1,39 +0,0 @@ -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.add(message.message(new Way(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 @@ -1,35 +0,0 @@ -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 @@ -1,25 +0,0 @@ -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 @@ -1,131 +0,0 @@ -package persolijn.osm.message; - -import java.util.ArrayList; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.Set; - -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 extends AbstractEntity<Way> { - 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 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); - } - - 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 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; - } - } - - if (isAllowed(Direction.FORWARDS)) - speedForwards = getSpeed(Direction.FORWARDS); - - if (isAllowed(Direction.BACKWARDS)) - speedBackwards = getSpeed(Direction.BACKWARDS); - - return this; - } - - @Override - public String toString() { - 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 @@ -1,66 +0,0 @@ -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.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>> { - @Override - public List<N> plan(RouteFunction<N> distanceFunction, RouteFunction<N> estimateFunction, 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(estimateFunction, currentTargets, target)); - - System.out.printf("route(%s, %s, %s)\n", 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.getPath()); - pathLength += subPath.getLength(); - } - - return path; - } - - protected long estimateLength(RouteFunction<N> estimateFunction, - 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)) { - - 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> 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,18 +0,0 @@ -package persolijn.planner; - -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 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()) - + 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 @@ -1,11 +0,0 @@ -package persolijn.planner; - -import java.util.Collection; -import java.util.List; - -import persolijn.routing.RouteFunction; - -@FunctionalInterface -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/planner/TargetIterable.java b/persolijn/src/main/java/persolijn/planner/TargetIterable.java @@ -1,124 +0,0 @@ -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/AbstractDijkstraRouter.java b/persolijn/src/main/java/persolijn/routing/AbstractDijkstraRouter.java @@ -1,224 +0,0 @@ -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/DijkstraRouter.java b/persolijn/src/main/java/persolijn/routing/DijkstraRouter.java @@ -1,186 +0,0 @@ -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 @@ -1,25 +0,0 @@ -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/Routable.java b/persolijn/src/main/java/persolijn/routing/Routable.java @@ -1,19 +0,0 @@ -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 @@ -1,60 +0,0 @@ -package persolijn.routing; - -import java.util.Collection; -import java.util.List; -import java.util.Map; -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. - */ -@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 - * 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. - */ - Route<N> route(Map<N, Long> targets, N start, long offset); -} diff --git a/protobuf-native/build.gradle b/protobuf-native/build.gradle @@ -1,7 +1,5 @@ plugins { - id 'java' id 'java-library' - id 'eclipse' // using 'eclipse'-plugin for .project/.classpath/... files } repositories { diff --git a/protobuf-native/src/main/java/protobuf/ProtobufReader.java b/protobuf-native/src/main/java/protobuf/ProtobufReader.java @@ -228,4 +228,9 @@ public interface ProtobufReader { * Skips the current wire element based on its type. */ void skip(); + + /** + * Throws an {@link UnexpectedTagException} for the current tag. + */ + void throwUnexpected(); } diff --git a/protobuf-native/src/main/java/protobuf/SimpleProtobufReader.java b/protobuf-native/src/main/java/protobuf/SimpleProtobufReader.java @@ -12,6 +12,7 @@ import java.util.function.UnaryOperator; import protobuf.exception.InputException; import protobuf.exception.OverflowException; +import protobuf.exception.UnexpectedTagException; import protobuf.exception.WireTypeException; class SimpleProtobufReader implements ProtobufReader { @@ -400,4 +401,9 @@ class SimpleProtobufReader implements ProtobufReader { throw new UnsupportedOperationException("cannot skip sgroup of egroup"); } } + + @Override + public void throwUnexpected() { + throw new UnexpectedTagException(tag); + } } diff --git a/protobuf-native/src/main/java/protobuf/WireType.java b/protobuf-native/src/main/java/protobuf/WireType.java @@ -9,33 +9,33 @@ public enum WireType { /** * Wire type for variable-length integers. */ - VARINT(0, new String[] { "int32", "int64", "uint32", "uint64", "sint32", "sint64", "bool", "enum" }), + VARINT(0, "int32", "int64", "uint32", "uint64", "sint32", "sint64", "bool", "enum"), /** * Wire type for 64-bit fixed-length values. */ - I64(1, new String[] { "fixed64", "sfixed64", "double" }), + I64(1, "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" }), + LEN(2, "string", "bytes", "embedded messages", "packed repeated fields"), /** * Wire type for the start of a deprecated group. */ - SGROUP(3, new String[] { "group start (deprecated)" }), + SGROUP(3, "group start (deprecated)"), /** * Wire type for the end of a deprecated group. */ - EGROUP(4, new String[] { "group end (deprecated)" }), + EGROUP(4, "group end (deprecated)"), /** * Wire type for 32-bit fixed-length values. */ - I32(5, new String[] { "fixed32", "sfixed32", "float" }); + I32(5, "fixed32", "sfixed32", "float"); /** * The numeric value associated with the wire type. @@ -55,7 +55,7 @@ public enum WireType { * @param possibleTypes An array of possible Protobuf types associated with this * wire type. */ - private WireType(int value, String[] possibleTypes) { + private WireType(int value, String... possibleTypes) { this.value = value; this.possibleTypes = possibleTypes; } diff --git a/protobuf-native/src/main/java/protobuf/exception/UnexpectedTagException.java b/protobuf-native/src/main/java/protobuf/exception/UnexpectedTagException.java @@ -0,0 +1,7 @@ +package protobuf.exception; + +public class UnexpectedTagException extends RuntimeException { + public UnexpectedTagException(int tag) { + super(String.format("Unhandled tag `%d`", tag)); + } +} diff --git a/settings.gradle b/settings.gradle @@ -1,12 +1,6 @@ -/* - * 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') + +include 'osm-protobuf' +include 'osm-routing' +include 'protobuf-native' +include 'persolijn'