diff options
Diffstat (limited to 'src/main/java/com/google/devtools/build/lib/actions/BipartiteVisitor.java')
-rw-r--r-- | src/main/java/com/google/devtools/build/lib/actions/BipartiteVisitor.java | 98 |
1 files changed, 98 insertions, 0 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/actions/BipartiteVisitor.java b/src/main/java/com/google/devtools/build/lib/actions/BipartiteVisitor.java new file mode 100644 index 0000000000..61803c8dd1 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/actions/BipartiteVisitor.java @@ -0,0 +1,98 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.actions; + +import java.util.HashMap; +import java.util.Map; + +/** + * A visitor helper class for bipartite graphs. The alternate kinds of nodes + * are arbitrarily designated "black" or "white". + * + * <p> Subclasses implement the black() and white() hook functions which are + * called as nodes are visited. The class holds a mapping from each node to a + * small integer; this is available to subclasses if they wish. + */ +public abstract class BipartiteVisitor<BLACK, WHITE> { + + protected BipartiteVisitor() {} + + private int nextNodeId = 0; + + // Maps each visited black node to a small integer. + protected final Map<BLACK, Integer> visitedBlackNodes = new HashMap<>(); + + // Maps each visited white node to a small integer. + protected final Map<WHITE, Integer> visitedWhiteNodes = new HashMap<>(); + + /** + * Visit the specified black node. If this node has not already been + * visited, the black() hook is called and true is returned; otherwise, + * false is returned. + */ + public final boolean visitBlackNode(BLACK blackNode) { + if (blackNode == null) { throw new NullPointerException(); } + if (!visitedBlackNodes.containsKey(blackNode)) { + visitedBlackNodes.put(blackNode, nextNodeId++); + black(blackNode); + return true; + } + return false; + } + + /** + * Visit all specified black nodes. + */ + public final void visitBlackNodes(Iterable<BLACK> blackNodes) { + for (BLACK blackNode : blackNodes) { + visitBlackNode(blackNode); + } + } + + /** + * Visit the specified white node. If this node has not already been + * visited, the white() hook is called and true is returned; otherwise, + * false is returned. + */ + public final boolean visitWhiteNode(WHITE whiteNode) { + if (whiteNode == null) { + throw new NullPointerException(); + } + if (!visitedWhiteNodes.containsKey(whiteNode)) { + visitedWhiteNodes.put(whiteNode, nextNodeId++); + white(whiteNode); + return true; + } + return false; + } + + /** + * Visit all specified white nodes. + */ + public final void visitWhiteNodes(Iterable<WHITE> whiteNodes) { + for (WHITE whiteNode : whiteNodes) { + visitWhiteNode(whiteNode); + } + } + + /** + * Called whenever a white node is visited. Hook for subclasses. + */ + protected abstract void white(WHITE whiteNode); + + /** + * Called whenever a black node is visited. Hook for subclasses. + */ + protected abstract void black(BLACK blackNode); +} |