Method getMaxMedianCoverageLeft

src/rnabloom/util/GraphUtils.java:375–436

(final BloomFilterDeBruijnGraph graph, final Kmer source, final int lookahead)

    }

    public static float getMaxMedianCoverageLeft(final BloomFilterDeBruijnGraph graph, final Kmer source, final int lookahead) {
        int k = graph.getK();
        int numHash = graph.getCbfNumHash();
        
        ArrayDeque<Kmer> neighbors = source.getPredecessors(k, numHash, graph);
        
        if (neighbors.isEmpty()) {
            if (lookahead > 0) {
                return 0;
            }
            else {
                return source.count;
            }
        }
        else {
            ArrayDeque<Kmer> path = new ArrayDeque<>(lookahead); 
            path.add(source);
            
            Kmer cursor = neighbors.removeFirst();
            path.add(cursor);

            ArrayDeque<ArrayDeque<Kmer>> frontier = new ArrayDeque<>(lookahead);
            frontier.add(neighbors);

            float bestCov = 0;

            while (!frontier.isEmpty()) {
                if (path.size() < lookahead) {
                    neighbors = cursor.getPredecessors(k, numHash, graph);
                    if (!neighbors.isEmpty()) {
                        cursor = neighbors.removeFirst();
                        path.add(cursor);
                        frontier.add(neighbors);
                        continue;
                    }
                }

                if (path.size() == lookahead) {
                    // we only calculate coverage if path is long enough
                    float pathCov = getMinimumKmerCoverage(path);
                    if (bestCov < pathCov) {
                        bestCov = pathCov;
                    }
                }

                while (!frontier.isEmpty()) {
                    neighbors = frontier.getLast();
                    path.removeLast();
                    if (neighbors.isEmpty()) {
                        frontier.removeLast();
                    }
                    else {
                        cursor = neighbors.removeFirst();
                        path.add(cursor);
                        break;
                    }
                }
            }