package io.sigpipe.sing.query;

import java.io.IOException;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import io.sigpipe.sing.dataset.feature.FeatureType;
import io.sigpipe.sing.graph.DataContainer;
import io.sigpipe.sing.graph.Vertex;
import io.sigpipe.sing.serialization.SerializationOutputStream;

public class RelationalQuery extends Query {

    private Set<Vertex> pruned;

    public RelationalQuery() {

    }

    @Override
    public void execute(Vertex root)
    throws IOException, QueryException {
        this.pruned = new HashSet<Vertex>();
        System.out.println("expressions: " + expressions.size());
        prune(root, 0);
        System.out.println("Pruned " + pruned.size() + " vertices");
    public void serializeResults(Vertex vertex, SerializationOutputStream out)
    throws IOException {
        if (pruned.contains(vertex)) {
            return;
        }

        vertex.getLabel().serialize(out);
        if (vertex.hasData() == false) {
            vertex.setData(new DataContainer());
        }
        vertex.getData().serialize(out);

        /* How many neighbors are still valid after the pruning process? */
        int numNeighbors = 0;
        for (Vertex v : vertex.getAllNeighbors()) {
            if (pruned.contains(v) == false) {
                numNeighbors++;
            }
        }
        out.writeInt(numNeighbors);

        for (Vertex v : vertex.getAllNeighbors()) {
            if (pruned.contains(v) == false) {
                serializeResults(v, out);
            }
        }
    }

    private boolean prune(Vertex vertex, int expressionsEvaluated)
    throws QueryException {
        if (expressionsEvaluated == this.expressions.size()) {
            /* There are no further expressions to evaluate. Therefore, we must
             * assume all children from this point are relevant to the query. */
            return true;
        }

        boolean foundSubMatch = false;
        String childFeature = vertex.getFirstNeighbor().getLabel().getName();
        List<Expression> expList = this.expressions.get(childFeature);
        if (expList != null) {
            Set<Vertex> matches = evaluate(vertex, expList);
            if (matches.size() == 0) {
                pruned.add(vertex);
                return false;
            }

            for (Vertex match : matches) {
                if (match == null) {
                    continue;
                }

                if (match.getLabel().getType() == FeatureType.NULL) {
                    continue;
                }

                if (prune(match, expressionsEvaluated + 1) == true) {
                    foundSubMatch = true;
                }
            }

            Set<Vertex> nonMatches = new HashSet<>(vertex.getAllNeighbors());
            nonMatches.removeAll(matches);
            for (Vertex nonMatch : nonMatches) {
                pruned.add(nonMatch);
            }
        } else {
            /* No expression operates on this vertex. Consider all children. */
            for (Vertex neighbor : vertex.getAllNeighbors()) {
                if (prune(neighbor, expressionsEvaluated) == true) {
                    foundSubMatch = true;
                }
            }
        }

        if (foundSubMatch == false) {
            pruned.add(vertex);
        }

        return foundSubMatch;
    }
}

@@ -221,16 +221,59 @@
 tainer;%0A
+import io.sigpipe.sing.graph.GraphMetrics;%0A
 import i
@@ -301,16 +301,16 @@
 Vertex;%0A
-
 import i
@@ -443,16 +443,50 @@
  pruned;
+%0A    private GraphMetrics metrics;
 %0A%0A    pu
@@ -514,24 +514,113 @@
 ) %7B%0A%0A    %7D%0A%0A
+    public RelationalQuery(GraphMetrics metrics) %7B%0A        this.metrics = metrics;%0A    %7D%0A
     @Overrid
@@ -711,44 +711,406 @@
     
-this.pruned = new HashSet%3CVertex%3E();
+if (this.metrics != null) %7B%0A            /* To make sure we don't spend time resizing the pruned HashSet, set%0A             * it to the number of vertices in the graph divided by the default%0A             * load factor. */%0A            this.pruned = new HashSet%3CVertex%3E(%0A                    (int) (metrics.getVertexCount() / 0.75));%0A        %7D else %7B%0A            this.pruned = new HashSet%3C%3E();%0A        %7D
 %0A   

Add smart set construction based on graph metrics