View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package com.github.dexecutor.executor.graph;
19  
20  import java.util.ArrayList;
21  import java.util.Collection;
22  import java.util.HashMap;
23  import java.util.LinkedHashSet;
24  import java.util.Map;
25  import java.util.Map.Entry;
26  import java.util.Set;
27  
28  /**
29   * Default implementation of Graph
30   * 
31   * @author Nadeem Mohammad
32   *
33   * @param <T> Type of Node/Task ID
34   * @param <R> Type of Node/Task result
35   */
36  public final class DefaultGraph<T extends Comparable<T>, R> implements Graph<T, R> {
37  
38  	private Map<T, Node<T, R>> nodes = new HashMap<T, Node<T, R>>();
39  
40  	public void addIndependent(final T nodeValue) {
41  		addOrGet(nodeValue);
42  	}
43  
44  	public void addDependency(final T evalFirstNode, final T evalLaterNode) {
45  		Node<T, R> firstNode = addOrGet(evalFirstNode);
46  		Node<T, R> afterNode = addOrGet(evalLaterNode);
47  
48  		addEdges(firstNode, afterNode);
49  	}
50  
51  	private void addEdges(final Node<T, R> firstNode, final Node<T, R> afterNode) {
52  		if (!firstNode.equals(afterNode)) {
53  			firstNode.addOutGoingNode(afterNode);
54  			afterNode.addInComingNode(firstNode);			
55  		}
56  	}
57  
58  	private Node<T, R> addOrGet(final T nodeValue) {
59  		Node<T, R> graphNode = null;
60  		if (this.nodes.containsKey(nodeValue)) {
61  			graphNode = this.nodes.get(nodeValue);
62  		} else {
63  			graphNode = createNode(nodeValue);
64  			this.nodes.put(nodeValue, graphNode);
65  		}
66  		return graphNode;
67  	}
68  
69  	private Node<T, R> createNode(final T value) {
70  		Node<T, R> node = new Node<T, R>(value);
71  		return node;
72  	}
73  
74  	public Set<Node<T, R>> getInitialNodes() {
75  		Set<Node<T, R>> initialNodes = new LinkedHashSet<Node<T, R>>();
76  		for (Entry<T, Graph.Node<T, R>> entry : this.nodes.entrySet()) {
77  			Graph.Node<T, R> node = entry.getValue();
78  			if (node.getInComingNodes().isEmpty()) {				
79  				initialNodes.add(node);
80  			}
81  		}
82  		return initialNodes;
83  	}
84  
85  	public int size() {
86  		return this.nodes.size();
87  	}
88  
89  	public Collection<Graph.Node<T, R>> allNodes() {
90  		return new ArrayList<Graph.Node<T, R>>(this.nodes.values());
91  	}
92  
93  	public Set<Graph.Node<T, R>> getLeafNodes() {
94  		Set<Node<T, R>> leafNodes = new LinkedHashSet<Node<T, R>>();
95  		for (Entry<T, Graph.Node<T, R>> entry : this.nodes.entrySet()) {
96  			Graph.Node<T, R> node = entry.getValue();
97  			if (node.getOutGoingNodes().isEmpty()) {				
98  				leafNodes.add(node);
99  			}
100 		}
101 		return leafNodes;
102 	}
103 }