package javakurs.musterloesung.uebung08;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * {@link DirectedGraph} extends {@link DirectedGraphBase} with more
 * functionality.
 *
 * @param <EdgeInfo>
 *          the kind of edge info used in this graph
 *
 * @author Joerg Steffen, DFKI
 * @author Bernd Kiefer, DFKI
 * @version $Id: DirectedGraph.java,v 1.3 2011/01/12 16:30:18 steffen Exp $
 */
public class DirectedGraph<EdgeInfo> extends DirectedGraphBase<EdgeInfo> {

  /**
   * This creates a new instance of {@link DirectedGraph}.
   */
  public DirectedGraph() {

    super();
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public int newVertex() {

    if (_deletedVertices.isEmpty()) {
      // extend the edge lists
      _outEdges.add(null);
      _inEdges.add(null);
      return _outEdges.size() - 1;
    }
    // get next available previous deleted vertex
    int vertex = _deletedVertices.nextSetBit(0);
    _deletedVertices.clear(vertex);
    return vertex;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public Edge<EdgeInfo> newEdge(EdgeInfo edgeInfo, int from, int to) {

    assert (isVertex(from) && isVertex(to));
    Edge<EdgeInfo> edge = new Edge<EdgeInfo>(edgeInfo);
    setFrom(edge, from);
    setTo(edge, to);
    return edge;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public void removeEdge(Edge<EdgeInfo> edge) {

    // outgoing edges of start vertex
    ArrayList<Edge<EdgeInfo>> startVertexOut =
      _outEdges.get(edge.getStartVertex());
    startVertexOut.remove(edge);
    // set to null if list is empty
    if (startVertexOut.isEmpty()) {
      _outEdges.set(edge.getStartVertex(), null);
    }

    // incoming edges of end vertex
    ArrayList<Edge<EdgeInfo>> endVertexIn =
      _inEdges.get(edge.getEndVertex());
    endVertexIn.remove(edge);
    // set to null if list is empty
    if (endVertexIn.isEmpty()) {
      _inEdges.set(edge.getEndVertex(), null);
    }
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public void removeVertex(int vertex) {

    if (isVertex(vertex)) {
      // remove the edges from and to this vertex from other vertices
      // edge lists
      // outgoing edges:
      List<Edge<EdgeInfo>> out = _outEdges.get(vertex);
      if (out != null) {
        for (Edge<EdgeInfo> edge : out) {
          removeEdge(edge);
        }
        _outEdges.set(vertex, null);
      }
      // incoming edges:
      List<Edge<EdgeInfo>> in = _inEdges.get(vertex);
      if (in != null) {
        for (Edge<EdgeInfo> edge : in) {
          removeEdge(edge);
        }
        _inEdges.set(vertex, null);
      }
      // register this vertex as being deleted
      _deletedVertices.set(vertex);

      // clear the entries in the registered property maps
      for (VertexPropertyMap<?> map : _vertexPropertyMaps.values()) {
        map.remove(vertex);
      }

      // clear the entries in the registered boolean property maps
      for (BitSet map : _vertexBooleanPropertyMaps.values()) {
        map.clear(vertex);
      }
    }
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public Edge<EdgeInfo> findEdge(
      int vertex, EdgeInfo edgeInfo, Comparator<EdgeInfo> comp) {

    ArrayList<Edge<EdgeInfo>> edges = _outEdges.get(vertex);
    if (edges == null) {
      return null;
    }
    for (int i = 0; i < edges.size(); ++i) {
      Edge<EdgeInfo> edge = edges.get(i);
      if (comp.compare(edge.getEdgeInfo(), edgeInfo) == 0) {
        return edge;
      }
    }
    return null;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public List<Edge<EdgeInfo>> findEdges(
      int vertex, EdgeInfo edgeInfo, Comparator<EdgeInfo> comp) {

    List<Edge<EdgeInfo>> result = new LinkedList<Edge<EdgeInfo>>();

    ArrayList<Edge<EdgeInfo>> edges = _outEdges.get(vertex);
    if (edges == null) {
      return result;
    }

    for (int i = 0; i < edges.size(); ++i) {
      Edge<EdgeInfo> edge = edges.get(i);
      if (comp.compare(edge.getEdgeInfo(), edgeInfo) == 0) {
        result.add(edge);
      }
    }
    return result;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  protected void dfsVisit(
      int vertex, DfsGraphVisitor<EdgeInfo> visitor, BitSet visited) {

    // ignore deleted vertices
    if (isDeletedVertex(vertex)) {
      return;
    }

    // vertex gets gray:
    visited.set(vertex);
    visitor.discoverVertex(vertex, this);
    List<Edge<EdgeInfo>> out = getOutEdges(vertex);
    for (Edge<EdgeInfo> edge : out) {
      int target = edge.getEndVertex();
      // is the target vertex white?
      if (!visited.get(target)) {
        visitor.treeEdgeBefore(edge, this);
        dfsVisit(target, visitor, visited);
        visitor.treeEdgeAfter(edge, this);
      }
      else {
        visitor.nonTreeEdge(edge, this);
      }
    }
    // vertex gets black:
    visitor.finishVertex(vertex, this);
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public void dfs(DfsGraphVisitor<EdgeInfo> visitor) {

    BitSet visited = new BitSet();
    for (int vertex = 0; vertex < _outEdges.size(); ++vertex) {
      if (!visited.get(vertex)) {
        visitor.startVertex(vertex, this);
        dfsVisit(vertex, visitor, visited);
      }
    }
  }


  /**
   * {@inheritDoc}
   */
  @Override
  protected void bfsVisit(
      int vertex, BfsGraphVisitor<EdgeInfo> visitor, BitSet visited) {

    // ignore deleted vertices
    if (isDeletedVertex(vertex)) {
      return;
    }

    Queue<Integer> active = new LinkedList<Integer>();
    active.offer(vertex);
    // vertex gets gray:
    visited.set(vertex);
    visitor.discoverVertex(vertex, this);
    while (active.peek() != null) {
      int nextVertex = active.poll();
      for (Edge<EdgeInfo> outEdge : _outEdges.get(nextVertex)) {
        int target = outEdge.getEndVertex();
        if (!visited.get(target)) {
          active.offer(target);
          // vertex gets gray:
          visited.set(target);
          visitor.treeEdge(outEdge, this);
          visitor.discoverVertex(target, this);
        }
        else {
          visitor.nonTreeEdge(outEdge, this);
        }
      }
      // vertex gets black
      visitor.finishVertex(nextVertex, this);
    }
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public void bfs(BfsGraphVisitor<EdgeInfo> visitor) {

    // all bits are initially false:
    BitSet visited = new BitSet();
    for (int vertex = 0; vertex < _outEdges.size(); ++vertex) {
      if (!visited.get(vertex)) {
        visitor.startVertex(vertex, this);
        bfsVisit(vertex, visitor, visited);
      }
    }
  }
}
