class RouteSearch {

    public final RouteSearchResult calculateRoute()
            throws OpenLREncoderProcessingException {
        if (LOG.isDebugEnabled()) {
            LOG.debug("route search between start (" + startLine.getID()
                    + ") and dest (" + destLine.getID() + ")");
        }
        RouteSearchResult result = null;

        // start and end are equals but there is a path in between
        // so skip the start and proceed with the next line in the location
        if (startLine.getID() == destLine.getID() && location.size() > 1) {
            List<Line> route = new ArrayList<Line>(1);
            route.add(startLine);
            result = new RouteSearchResult(
                    RouteSearchReturnCode.INTERMEDIATE_FOUND, route, location
                    .get(1), 1);
        } else if (startLoopIndex == 0) {
            // there is a loop of a single line in the location
            List<Line> route = new ArrayList<Line>();
            route.add(startLine);
            result = new RouteSearchResult(RouteSearchReturnCode.INTERMEDIATE_FOUND, route, location.get(1), 1);
        } else {
            //we have to start a search
            // global data structures
            IntermediateHandler iHandler = new IntermediateHandler(location);
            RouteSearchData data = new RouteSearchData();

            // for the use of the heuristic
            Node e = destLine.getEndNode();
            destX = e.getLongitudeDeg();
            destY = e.getLatitudeDeg();

            // initialize the open list with the start element
            int startLength = startLine.getLineLength();
            PQElem startElem = new PQElem(startLine, 0/* HACK */, startLength,
                    null);
            data.addToOpen(startElem);
            // open.add(startElem);
            // bestValues.put(startLine.getID(), startLength);
            OpenLongHashSet locationIDs = new OpenLongHashSet(location.size());
            for (Line l : location) {
                locationIDs.put(l.getID());
            }

            // main loop
            while (!data.isOpenEmpty()) {
                // stop if route or intermediate is found or if no further line
                // is
                // available

                // get the top element of the open list
                PQElem actualElement = data.pollElement();

                // check the location being part of the shortest path tree and
                // if not change the state to INTERMEDIATE_FOUND
                if (locationIDs.containsKey(actualElement.getLine().getID())) {
                    result = iHandler.checkIntermediate(actualElement, data);
                    if (result != null) {
                        break;
                    }
                }

                // check if we have found the destination and if so then
                // construct the route and stop calculation
                if (actualElement.getLine().getID() == destLine.getID()) {
                    if (endLoopIndex >= 0) {
                        //route found until the end loop starts
                        //break here and add intermediate
                        List<Line> route = PathUtils
                                .constructPath(actualElement.getPrevious());
                        result = new RouteSearchResult(
                                RouteSearchReturnCode.INTERMEDIATE_FOUND,
                                route, destLine, endLoopIndex);
                        break;
                    } else {
                        List<Line> route = PathUtils
                                .constructPath(actualElement);
                        if (route.isEmpty()) {
                            // strange error
                            throw new OpenLREncoderProcessingException(
                                    EncoderProcessingError.ROUTE_CONSTRUCTION_ERROR);
                        } else {
                            // route found and constructed
                            result = new RouteSearchResult(
                                    RouteSearchResult.RouteSearchReturnCode.ROUTE_FOUND,
                                    route);
                            break;
                        }
                    }
                }

                //check for loops at start
                if (startLoopIndex > 0
                        && iHandler.getLastElemOnRoutePos() == startLoopIndex) {
                    // the start loop is completed and route search needs to be
                    // interrupted, add intermediate
                    if (LOG.isDebugEnabled()) {
                        LOG.debug("loop is traversed, intermediate found");
                    }
                    List<Line> route = PathUtils.constructPath(actualElement.getPrevious());
                    result = new RouteSearchResult(
                            RouteSearchReturnCode.INTERMEDIATE_FOUND, route,
                            startLine, startLoopIndex);
                    break;
                }
                //route search can continue so
                // iterate over the successors, because we have not reached the
                // end
                extractNextLines(actualElement, data);
            }
            if (result == null) {
                //no route found
                result = new RouteSearchResult(RouteSearchReturnCode.NO_ROUTE_FOUND);
            }
        }
        return result;
    }

    public  RouteSearch(final List<? extends Line> loc);

}