content: /**
   * Copyright (c) 2019, the Alpha Team.
   * All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions are met:
   *
   * 1) Redistributions of source code must retain the above copyright notice, this
   *    list of conditions and the following disclaimer.
   *
   * 2) Redistributions in binary form must reproduce the above copyright notice,
   *    this list of conditions and the following disclaimer in the documentation
   *    and/or other materials provided with the distribution.
   *
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
   * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   */
  package at.ac.tuwien.kr.alpha.core.depgraph;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  import at.ac.tuwien.kr.alpha.api.programs.analysis.DependencyGraph;
  import org.slf4j.Logger;
  import org.slf4j.LoggerFactory;
  
  import at.ac.tuwien.kr.alpha.api.programs.Predicate;
  import at.ac.tuwien.kr.alpha.api.programs.atoms.Atom;
  import at.ac.tuwien.kr.alpha.api.programs.literals.FixedInterpretationLiteral;
  import at.ac.tuwien.kr.alpha.api.programs.literals.Literal;
  import at.ac.tuwien.kr.alpha.commons.Predicates;
  import at.ac.tuwien.kr.alpha.core.programs.rules.CompiledRule;
  
  /**
   * Internal representation of an {@link at.ac.tuwien.kr.alpha.core.programs.InternalProgram}'s dependency graph. The dependency graph tracks dependencies
   * between rules of a program. Each {@link NodeImpl} of the graph represents a {@link Predicate} occurring in the program. A node has an incoming {@link EdgeImpl} for
   * every {@link Literal} in some rule body that depends on it, i.e. the predicate of the literal in question is the same as that of the node. The "sign" flag of
   * an {@link EdgeImpl} indicates whether the dependency is a positive or negative one, i.e. if the atom in question is preceded by a "not".
   * 
   * Note that constraints are represented by one dummy predicate (named "constr_{num}"). Each constraint node has a negative edge to itself to express the
   * notation of a constraint ":- a, b." as "x :- a, b, not x.".
   * 
   * Copyright (c) 2019-2020, the Alpha Team.
   */
  public final class DependencyGraphImpl  implements DependencyGraph {
  
  	private static final Logger LOGGER = LoggerFactory.getLogger(DependencyGraphImpl.class);
  
  	/*
  	 * Maps nodes to outgoing edges of that node.
  	 * Note: using List<EdgeImpl> rather than Map<Integer,Boolean> as one node may have positive and negative edges to
  	 * another.
  	 */
  	private final Map<Node, List<Edge>> adjacencyMap;
  
  	private final Map<Predicate, Node> nodesByPredicate;
  
  	private DependencyGraphImpl(Map<Node, List<Edge>> adjacencyMap, Map<Predicate, Node> nodesByPredicate) {
  		this.adjacencyMap = adjacencyMap;
  		this.nodesByPredicate = nodesByPredicate;
  	}
  
  	public static DependencyGraphImpl buildDependencyGraph(Map<Integer, CompiledRule> nonGroundRules) {
  		return new DependencyGraphImpl.Builder(nonGroundRules.values()).build();
  	}
  
  	@Override
  	public Node getNodeForPredicate(Predicate p) {
  		return nodesByPredicate.get(p);
  	}
  
  	@Override
  	public Map<Node, List<Edge>> getAdjancencyMap() {
  		return Collections.unmodifiableMap(adjacencyMap);
  	}
  
  	private static class Builder {
  
  		private static final String CONSTRAINT_PREDICATE_FORMAT = "[constr_%d]";
  
  		private int constraintNumber;
  		private Collection<CompiledRule> rules;
  
  		private Map<Node, List<Edge>> adjacentNodesMap = new HashMap<>();
  		private Map<Predicate, Node>      nodesByPredicate = new HashMap<>();
  
  		private Builder(Collection<CompiledRule> rules) {
  			this.rules = rules;
  			this.constraintNumber = 0;
  		}
  
  		private DependencyGraphImpl build() {
  			for (CompiledRule rule : rules) {
  				LOGGER.debug("Processing rule: {}", rule);
  				Node headNode = handleRuleHead(rule);
  				for (Literal literal : rule.getBody()) {
  					LOGGER.trace("Processing rule body literal: {}", literal);
  					if (literal instanceof FixedInterpretationLiteral) {
  						LOGGER.trace("Ignoring FixedInterpretationLiteral {}", literal);
  						continue;
  					}
  					handleRuleBodyLiteral(headNode, literal);
  				}
  			}
  			return new DependencyGraphImpl(adjacentNodesMap, nodesByPredicate);
  		}
  
  		private Node handleRuleHead(CompiledRule rule) {
  			LOGGER.trace("Processing head of rule: {}", rule);
  			Node headNode;
  			if (rule.isConstraint()) {
  				Predicate pred = generateConstraintDummyPredicate();
  				headNode = new NodeImpl(pred);
  				List<Edge> dependencies = new ArrayList<>();
  				dependencies.add(new EdgeImpl(headNode, false));
  				if (adjacentNodesMap.containsKey(headNode)) {
  					throw new IllegalStateException("Dependency graph already contains node for constraint " + pred.toString() + "!");
  				}
  				adjacentNodesMap.put(headNode, dependencies);
  				nodesByPredicate.put(pred, headNode);
  			} else {
  				Atom head = rule.getHeadAtom();
  				Predicate pred = head.getPredicate();
  				if (!nodesByPredicate.containsKey(pred)) {
  					headNode = new NodeImpl(pred);
  					adjacentNodesMap.put(headNode, new ArrayList<>());
  					nodesByPredicate.put(pred, headNode);
  				} else {
  					headNode = nodesByPredicate.get(pred);
  				}
  			}
  			return headNode;
  		}
  
  		private void handleRuleBodyLiteral(Node headNode, Literal lit) {
  			List<Edge> dependants;
  			Node bodyNode;
  			Predicate bodyPred = lit.getPredicate();
  			if (!nodesByPredicate.containsKey(bodyPred)) {
  				LOGGER.trace("Creating new node for bodyPred {}", bodyPred);
  				dependants = new ArrayList<>();
  				bodyNode = new NodeImpl(bodyPred);
  				nodesByPredicate.put(bodyPred, bodyNode);
  				adjacentNodesMap.put(bodyNode, dependants);
  			} else {
  				LOGGER.trace("Node for bodyPred {} already exists", bodyPred);
  				bodyNode = nodesByPredicate.get(bodyPred);
  				dependants = adjacentNodesMap.get(bodyNode);
  			}
  			Edge tmpEdge = new EdgeImpl(headNode, !lit.isNegated());
  			if (!dependants.contains(tmpEdge)) {
  				LOGGER.trace("Adding dependency: {} -> {} ({})", bodyNode.getPredicate(), headNode.getPredicate(), tmpEdge.getSign() ? "+" : "-");
  				dependants.add(tmpEdge);
  			}
  			nodesByPredicate.put(bodyPred, bodyNode);
  		}
  
  		private Predicate generateConstraintDummyPredicate() {
  			return Predicates.getPredicate(String.format(DependencyGraphImpl.Builder.CONSTRAINT_PREDICATE_FORMAT, ++constraintNumber), 0);
  		}
  	}
  }
  