This method does the actual map matching.
<p>

@param gpxList the input list with GPX points which should match to edges
of the graph specified in the constructor
7317
public MatchResult doWork(List<Observation> gpxList) {
        // filter the entries:
        List<Observation> filteredGPXEntries = filterGPXEntries(gpxList);

        // now find each of the entries in the graph:
        List<Collection<QueryResult>> queriesPerEntry = lookupGPXEntries(filteredGPXEntries, DefaultEdgeFilter.allEdges(weighting.getFlagEncoder()));

        // Add virtual nodes and edges to the graph so that candidates on edges can be represented
        // by virtual nodes.
        QueryGraph queryGraph = new QueryGraph(routingGraph).setUseEdgeExplorerCache(true);
        List<QueryResult> allQueryResults = new ArrayList<>();
        for (Collection<QueryResult> qrs : queriesPerEntry) {
            allQueryResults.addAll(qrs);
        }
        queryGraph.lookup(allQueryResults);

        // Different QueryResults can have the same tower node as their closest node.
        // Hence, we now dedupe the query results of each GPX entry by their closest node (#91).
        // This must be done after calling queryGraph.lookup() since this replaces some of the
        // QueryResult nodes with virtual nodes. Virtual nodes are not deduped since there is at
        // most one QueryResult per edge and virtual nodes are inserted into the middle of an edge.
        // Reducing the number of QueryResults improves performance since less shortest/fastest
        // routes need to be computed.
        queriesPerEntry = deduplicateQueryResultsByClosestNode(queriesPerEntry);

        logger.debug("================= Query results =================");
        int i = 1;
        for (Collection<QueryResult> entries : queriesPerEntry) {
            logger.debug("Query results for GPX entry {}", i++);
            for (QueryResult qr : entries) {
                logger.debug("Node id: {}, virtual: {}, snapped on: {}, pos: {},{}, "
                                + "query distance: {}", qr.getClosestNode(),
                        isVirtualNode(qr.getClosestNode()), qr.getSnappedPosition(),
                        qr.getSnappedPoint().getLat(), qr.getSnappedPoint().getLon(),
                        qr.getQueryDistance());
            }
        }

        // Creates candidates from the QueryResults of all GPX entries (a candidate is basically a
        // QueryResult + direction).
        List<TimeStep<State, Observation, Path>> timeSteps =
                createTimeSteps(filteredGPXEntries, queriesPerEntry, queryGraph);
        logger.debug("=============== Time steps ===============");
        i = 1;
        for (TimeStep<State, Observation, Path> ts : timeSteps) {
            logger.debug("Candidates for time step {}", i++);
            for (State candidate : ts.candidates) {
                logger.debug(candidate.toString());
            }
        }

        // Compute the most likely sequence of map matching candidates:
        List<SequenceState<State, Observation, Path>> seq = computeViterbiSequence(timeSteps, gpxList.size(), queryGraph);

        logger.debug("=============== Viterbi results =============== ");
        i = 1;
        for (SequenceState<State, Observation, Path> ss : seq) {
            logger.debug("{}: {}, path: {}", i, ss.state,
                    ss.transitionDescriptor != null ? ss.transitionDescriptor.calcEdges() : null);
            i++;
        }

        final EdgeExplorer explorer = queryGraph.createEdgeExplorer(DefaultEdgeFilter.allEdges(weighting.getFlagEncoder()));
        final Map<String, EdgeIteratorState> virtualEdgesMap = createVirtualEdgesMap(queriesPerEntry, explorer);
        MatchResult matchResult = computeMatchResult(seq, virtualEdgesMap, gpxList, queryGraph);
        logger.debug("=============== Matched real edges =============== ");
        i = 1;
        for (EdgeMatch em : matchResult.getEdgeMatches()) {
            logger.debug("{}: {}", i, em.getEdgeState());
            i++;
        }
        return matchResult;
    }
943717
@SuppressWarnings({ "unchecked", "rawtypes" })
	public <NV> Graph<K, NV, EV> mapVertices(final MapFunction<Vertex<K, VV>, NV> mapper) {

		TypeInformation<K> keyType = ((TupleTypeInfo<?>) vertices.getType()).getTypeAt(0);

		TypeInformation<NV> valueType;

		if (mapper instanceof ResultTypeQueryable) {
			valueType = ((ResultTypeQueryable) mapper).getProducedType();
		} else {
			valueType = TypeExtractor.createTypeInfo(MapFunction.class, mapper.getClass(), 1, vertices.getType(), null);
		}

		TypeInformation<Vertex<K, NV>> returnType = (TypeInformation<Vertex<K, NV>>) new TupleTypeInfo(
				Vertex.class, keyType, valueType);

		return mapVertices(mapper, returnType);
	}
75562
private void readWaypoint(final Element waypoint, final List<GraphObjectMap> resultList) {

		final GraphObjectMap item = readPoint(waypoint);
		if (item != null) {

			resultList.add(item);
		}
	}
1236394
public synchronized void matchNode(RenderCallback renderCallback, final RenderContext renderContext, PointOfInterest poi) {
        MatchingCacheKey matchingCacheKey = new MatchingCacheKey(poi.tags, renderContext.rendererJob.tile.zoomLevel, Closed.NO);

        List<RenderInstruction> matchingList = this.poiMatchingCache.get(matchingCacheKey);
        if (matchingList != null) {
            // cache hit
            for (int i = 0, n = matchingList.size(); i < n; ++i) {
                matchingList.get(i).renderNode(renderCallback, renderContext, poi);
            }
            return;
        }

        // cache miss
        matchingList = new ArrayList<RenderInstruction>();

        for (int i = 0, n = this.rulesList.size(); i < n; ++i) {
            this.rulesList.get(i).matchNode(renderCallback, renderContext, matchingList, poi);
        }
        this.poiMatchingCache.put(matchingCacheKey, matchingList);
    }
488201
private void findMatchingValues(NavigableMap<Endpoint, Integer> map, Endpoint endpoint, List<UUID> result) {
        // Mark this endpoint as a marker, because it is used to do a tailMap traversal to query matching edges
        endpoint.setMarker();
        
        // Find the first key 
        Endpoint floorKey = map.floorKey(endpoint);
        
        Map<Endpoint, Integer> view;
        if (floorKey == null) {
            // This means that the element being searched is the minimum
            view = map;
        } else {
            view = map.tailMap(floorKey);
        }
        
        boolean isFirst = true;
        for (Map.Entry<Endpoint, Integer> entry : view.entrySet()) {
            Endpoint key = entry.getKey();

            if (endpoint.isMatch(key)) {
                // Matching entry, must be added to result
                result.add(key.getEdgeId());
            } else {
                // Done with the search -- the tree map is sorted
                
                if (isFirst) {
                    // continue
                } else {
                    break;
                }
            }
            
            isFirst = false;
        }
    }
396496
def neighbors_of( p )
      Set.new.tap do |neighbors|
        i = index_mapping[p]
        (0..index_mapping.size-1).each do |j|
          neighbors.add(points[j]) if adjacency_matrix.lookup(i,j) <= eps
        end
      end
    end
328809
public void setClazzToPuMap(Map<String, List<String>> map)
    {
        if (clazzToPuMap == null)
        {
            this.clazzToPuMap = map;
        }
        else
        {
            clazzToPuMap.putAll(map);
        }
    }
612476
public void setClientPropertiesList(java.util.Collection<ClientPropertiesResult> clientPropertiesList) {
        if (clientPropertiesList == null) {
            this.clientPropertiesList = null;
            return;
        }

        this.clientPropertiesList = new com.amazonaws.internal.SdkInternalList<ClientPropertiesResult>(clientPropertiesList);
    }
180441
public void setGraphqlApis(java.util.Collection<GraphqlApi> graphqlApis) {
        if (graphqlApis == null) {
            this.graphqlApis = null;
            return;
        }

        this.graphqlApis = new java.util.ArrayList<GraphqlApi>(graphqlApis);
    }
705643
public void lookup(List<QueryResult> resList) {
        if (isInitialized())
            throw new IllegalStateException("Call lookup only once. Otherwise you'll have problems for queries sharing the same edge.");

        // initialize all none-final variables
        virtualEdges = new ArrayList<>(resList.size() * 2);
        virtualNodes = new PointList(resList.size(), mainNodeAccess.is3D());
        queryResults = new ArrayList<>(resList.size());
        baseGraph.virtualEdges = virtualEdges;
        baseGraph.virtualNodes = virtualNodes;
        baseGraph.queryResults = queryResults;

        GHIntObjectHashMap<List<QueryResult>> edge2res = new GHIntObjectHashMap<>(resList.size());

        // Phase 1
        // calculate snapped point and swap direction of closest edge if necessary
        for (QueryResult res : resList) {
            // Do not create virtual node for a query result if it is directly on a tower node or not found
            if (res.getSnappedPosition() == QueryResult.Position.TOWER)
                continue;

            EdgeIteratorState closestEdge = res.getClosestEdge();
            if (closestEdge == null)
                throw new IllegalStateException("Do not call QueryGraph.lookup with invalid QueryResult " + res);

            int base = closestEdge.getBaseNode();

            // Force the identical direction for all closest edges.
            // It is important to sort multiple results for the same edge by its wayIndex
            boolean doReverse = base > closestEdge.getAdjNode();
            if (base == closestEdge.getAdjNode()) {
                // check for special case #162 where adj == base and force direction via latitude comparison
                PointList pl = closestEdge.fetchWayGeometry(0);
                if (pl.size() > 1)
                    doReverse = pl.getLatitude(0) > pl.getLatitude(pl.size() - 1);
            }

            if (doReverse) {
                closestEdge = closestEdge.detach(true);
                PointList fullPL = closestEdge.fetchWayGeometry(3);
                res.setClosestEdge(closestEdge);
                if (res.getSnappedPosition() == QueryResult.Position.PILLAR)
                    // ON pillar node
                    res.setWayIndex(fullPL.getSize() - res.getWayIndex() - 1);
                else
                    // for case "OFF pillar node"
                    res.setWayIndex(fullPL.getSize() - res.getWayIndex() - 2);

                if (res.getWayIndex() < 0)
                    throw new IllegalStateException("Problem with wayIndex while reversing closest edge:" + closestEdge + ", " + res);
            }

            // find multiple results on same edge
            int edgeId = closestEdge.getEdge();
            List<QueryResult> list = edge2res.get(edgeId);
            if (list == null) {
                list = new ArrayList<>(5);
                edge2res.put(edgeId, list);
            }
            list.add(res);
        }

        // Phase 2 - now it is clear which points cut one edge
        // 1. create point lists
        // 2. create virtual edges between virtual nodes and its neighbor (virtual or normal nodes)
        edge2res.forEach(new IntObjectPredicate<List<QueryResult>>() {
            @Override
            public boolean apply(int edgeId, List<QueryResult> results) {
                // we can expect at least one entry in the results
                EdgeIteratorState closestEdge = results.get(0).getClosestEdge();
                final PointList fullPL = closestEdge.fetchWayGeometry(3);
                int baseNode = closestEdge.getBaseNode();
                Collections.sort(results, new Comparator<QueryResult>() {
                    @Override
                    public int compare(QueryResult o1, QueryResult o2) {
                        int diff = Integer.compare(o1.getWayIndex(), o2.getWayIndex());
                        if (diff == 0) {
                            return Double.compare(distanceOfSnappedPointToPillarNode(o1), distanceOfSnappedPointToPillarNode(o2));
                        } else {
                            return diff;
                        }
                    }
                    private double distanceOfSnappedPointToPillarNode(QueryResult o) {
                        GHPoint snappedPoint = o.getSnappedPoint();
                        double fromLat = fullPL.getLatitude(o.getWayIndex());
                        double fromLon = fullPL.getLongitude(o.getWayIndex());
                        return Helper.DIST_PLANE.calcNormalizedDist(fromLat, fromLon, snappedPoint.lat, snappedPoint.lon);
                    }
                });

                GHPoint3D prevPoint = fullPL.get(0);
                int adjNode = closestEdge.getAdjNode();
                int origEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), false);
                int origRevEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), true);
                int prevWayIndex = 1;
                int prevNodeId = baseNode;
                int virtNodeId = virtualNodes.getSize() + mainNodes;
                boolean addedEdges = false;

                // Create base and adjacent PointLists for all none-equal virtual nodes.
                // We do so via inserting them at the correct position of fullPL and cutting the
                // fullPL into the right pieces.
                for (QueryResult res : results) {
                    if (res.getClosestEdge().getBaseNode() != baseNode)
                        throw new IllegalStateException("Base nodes have to be identical but were not: " + closestEdge + " vs " + res.getClosestEdge());

                    GHPoint3D currSnapped = res.getSnappedPoint();

                    // no new virtual nodes if exactly the same snapped point
                    if (prevPoint.equals(currSnapped)) {
                        res.setClosestNode(prevNodeId);
                        continue;
                    }

                    queryResults.add(res);
                    boolean isPillar = res.getSnappedPosition() == QueryResult.Position.PILLAR;
                    createEdges(origEdgeKey, origRevEdgeKey,
                            prevPoint, prevWayIndex, isPillar,
                            res.getSnappedPoint(), res.getWayIndex(),
                            fullPL, closestEdge, prevNodeId, virtNodeId);

                    virtualNodes.add(currSnapped.lat, currSnapped.lon, currSnapped.ele);

                    // add edges again to set adjacent edges for newVirtNodeId
                    if (addedEdges) {
                        virtualEdges.add(virtualEdges.get(virtualEdges.size() - 2));
                        virtualEdges.add(virtualEdges.get(virtualEdges.size() - 2));
                    }

                    addedEdges = true;
                    res.setClosestNode(virtNodeId);
                    prevNodeId = virtNodeId;
                    prevWayIndex = res.getWayIndex() + 1;
                    prevPoint = currSnapped;
                    virtNodeId++;
                }

                // two edges between last result and adjacent node are still missing if not all points skipped
                if (addedEdges)
                    createEdges(origEdgeKey, origRevEdgeKey,
                            prevPoint, prevWayIndex, false,
                            fullPL.get(fullPL.getSize() - 1), fullPL.getSize() - 2,
                            fullPL, closestEdge, virtNodeId - 1, adjNode);

                return true;
            }
        });
    }
144886
private void printTimeOfMapMatchQuery(final GraphHopper hopper, final MapMatching mapMatching) {

        // pick random start/end points to create a route, then pick random points from the route,
        // and then run the random points through map-matching.
        final double latDelta = bbox.maxLat - bbox.minLat;
        final double lonDelta = bbox.maxLon - bbox.minLon;
        final Random rand = new Random(seed);
        MiniPerfTest miniPerf = new MiniPerfTest() {
            @Override
            public int doCalc(boolean warmup, int run) {
                // keep going until we find a path (which we may not for certain start/end points)
                while (true) {
                    // create random points and find route between:
                    double lat0 = bbox.minLat + rand.nextDouble() * latDelta;
                    double lon0 = bbox.minLon + rand.nextDouble() * lonDelta;
                    double lat1 = bbox.minLat + rand.nextDouble() * latDelta;
                    double lon1 = bbox.minLon + rand.nextDouble() * lonDelta;
                    GHResponse r = hopper.route(new GHRequest(lat0, lon0, lat1, lon1));

                    // if found, use it for map matching:
                    if (!r.hasErrors()) {
                        double sampleProportion = rand.nextDouble();
                        GHPoint prev = null;
                        List<Observation> mock = new ArrayList<>();
                        PointList points = r.getBest().getPoints();
                        // loop through points and add (approximately) sampleProportion of them:
                        for (GHPoint p : points) {
                            if (null != prev && rand.nextDouble() < sampleProportion) {
                                // randomise the point lat/lon (i.e. so it's not
                                // exactly on the route):
                                GHPoint randomised = distCalc.projectCoordinate(p.lat, p.lon,
                                        20 * rand.nextDouble(), 360 * rand.nextDouble());
                                mock.add(new Observation(randomised));
                            }
                            prev = p;
                        }
                        // now match, provided there are enough points
                        if (mock.size() > 2) {
                            MatchResult match = mapMatching.doWork(mock);
                            // return something non-trivial, to avoid JVM optimizing away
                            return match.getEdgeMatches().size();
                        }
                    }
                }
            }
        }.setIterations(count).start();
        print("map_match", miniPerf);
    }
820383
private void createDetectedList(int which, List<PointIndex2D_F64> pixels) {
		detected2D3D.clear();
		List<Point2D3D> all = getControl3D(which);
		for (int i = 0; i < pixels.size(); i++) {
			PointIndex2D_F64 a = pixels.get(i);
			Point2D3D b = all.get(i);

			pixelToNorm.compute(a.x,a.y, b.observation);
			detected2D3D.add( b );
		}
	}
420656
public static <K, V> void mapfx(Map<K, V> map, MapFunction<K, V> fx) {
        Set<Entry<K, V>> entries = entries(map);
        for (final Entry<K, V> entry : entries) {
            K key = entry.getKey();
            V value = entry.getValue();
            fx.apply(key, value);
        }
    }
968470
public <S extends Solution<?>> void execute(List<S> solutionsList) {
    switch (config.scalarizationType) {
      case ANGLE_UTILITY:
        if (config.extremePoints == null)
          ScalarizationUtils.angleUtility(solutionsList);
        else
          ScalarizationUtils.angleUtility(solutionsList, config.extremePoints);
        break;
      case CHEBYSHEV:
        if (config.idealValues == null)
          ScalarizationUtils.chebyshev(solutionsList);
        else
          ScalarizationUtils.chebyshev(solutionsList, config.idealValues);
        break;
      case NASH:
        if (config.nadirValues == null)
          ScalarizationUtils.nash(solutionsList);
        else
          ScalarizationUtils.nash(solutionsList, config.nadirValues);
        break;
      case SUM_OF_OBJECTIVES:
        ScalarizationUtils.sumOfObjectives(solutionsList);
        break;
      case PRODUCT_OF_OBJECTIVES:
        ScalarizationUtils.productOfObjectives(solutionsList);
        break;
      case TRADEOFF_UTILITY:
        ScalarizationUtils.tradeoffUtility(solutionsList);
        break;
      case UNIFORM:
        ScalarizationUtils.uniform(solutionsList);
        break;
      case WEIGHTED_CHEBYSHEV:
        if (config.idealValues == null)
          ScalarizationUtils.weightedChebyshev(solutionsList, config.weights);
        else
          ScalarizationUtils.weightedChebyshev(solutionsList, config.idealValues, config.weights);
        break;
      case WEIGHTED_PRODUCT:
        ScalarizationUtils.weightedProduct(solutionsList, config.weights);
        break;
      case WEIGHTED_SUM:
        ScalarizationUtils.weightedSum(solutionsList, config.weights);
        break;
    }
  }
455781
@Override
    synchronized public final void set(List<Map<Integer, Integer>> list) {
        this.clear();
        mappings.addAll(list);
    }
446828
public void setPathToObjectIdentifiersList(java.util.Collection<PathToObjectIdentifiers> pathToObjectIdentifiersList) {
        if (pathToObjectIdentifiersList == null) {
            this.pathToObjectIdentifiersList = null;
            return;
        }

        this.pathToObjectIdentifiersList = new java.util.ArrayList<PathToObjectIdentifiers>(pathToObjectIdentifiersList);
    }
1133904
private int[][] computeSortAndUniqueMapping(String[] keyList, int size)
      throws IOException {
    if (!closed) {
      if (size > 0) {
        SortedMap<String, int[]> sortedMap = new TreeMap<>();
        for (int i = 0; i < size; i++) {
          if (sortedMap.containsKey(keyList[i])) {
            int[] previousList = sortedMap.get(keyList[i]);
            int[] newList = new int[previousList.length + 1];
            System.arraycopy(previousList, 0, newList, 0, previousList.length);
            newList[previousList.length] = i;
            sortedMap.put(keyList[i], newList);
          } else {
            sortedMap.put(keyList[i], new int[] { i });
          }
        }
        Collection<int[]> values = sortedMap.values();
        int[][] result = new int[sortedMap.size()][];
        return values.toArray(result);
      } else {
        return null;
      }
    } else {
      throw new IOException("already closed");
    }
  }