package javakurs.musterloesung.uebung08;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * {@link DirectedGraphBase} represents a directed graph. Vertices are
 * represented as ints, their edges are managed in lists using the ints as
 * index.
 *
 * @param <EdgeInfo>
 *          the kind of edge info used in this graph
 *
 * @author Bernd Kiefer, DFKI
 * @author Joerg Steffen, DFKI
 * @version $Id: DirectedGraphBase.java,v 1.4 2011/01/12 16:30:18 steffen Exp $
 */
public abstract class DirectedGraphBase<EdgeInfo> {

  /**
   * The default result for empty edge lists.
   */
  protected final List<Edge<EdgeInfo>> _defaultEmptyResult =
    Collections.unmodifiableList(new ArrayList<Edge<EdgeInfo>>());

  /**
   * For each vertex, these contain the outgoing and incoming edges of this
   * graph.
   */
  protected ArrayList<ArrayList<Edge<EdgeInfo>>> _outEdges;
  protected ArrayList<ArrayList<Edge<EdgeInfo>>> _inEdges;

  /** A list of ints representing deleted vertices */
  protected BitSet _deletedVertices;

  /** property maps for non-boolean values registered with this DirectedGraph */
  protected HashMap<String, VertexPropertyMap<?>> _vertexPropertyMaps;

  /** property maps for boolean values registered with this DirectedGraph */
  protected HashMap<String, BitSet> _vertexBooleanPropertyMaps;


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

    _outEdges = new ArrayList<ArrayList<Edge<EdgeInfo>>>();
    _inEdges = new ArrayList<ArrayList<Edge<EdgeInfo>>>();
    _deletedVertices = new BitSet();
    _vertexPropertyMaps = new HashMap<String, VertexPropertyMap<?>>();
    _vertexBooleanPropertyMaps = new HashMap<String, BitSet>();
  }


  /**
   * Helper method that returns for the given vertex the assigned edge list from
   * the given edges lists.
   *
   * @param edges
   *          the edges list
   * @param vertex
   *          the vertex
   * @return the edge list for the vertex
   */
  private List<Edge<EdgeInfo>>
      getEdgeList(ArrayList<ArrayList<Edge<EdgeInfo>>> edges, int vertex) {

    ArrayList<Edge<EdgeInfo>> edgeList = edges.get(vertex);
    if (edgeList == null) {
      edgeList = new ArrayList<Edge<EdgeInfo>>(3);
      edges.set(vertex, edgeList);
    }
    return edgeList;
  }


  /**
   * Sets the start vertex of the given edge to the given vertex and adapts the
   * outgoing edge list.
   *
   * @param edge
   *          the edge
   * @param from
   *          the start vertex
   */
  protected void setFrom(Edge<EdgeInfo> edge, int from) {

    edge.setStartVertex(from);
    getEdgeList(_outEdges, from).add(edge);
  }


  /**
   * Sets the end vertex of the given edge to the given vertex and adapts the
   * incoming edges list.
   *
   * @param edge
   *          the edge
   * @param to
   *          the end vertex
   */
  protected void setTo(Edge<EdgeInfo> edge, int to) {

    edge.setEndVertex(to);
    getEdgeList(_inEdges, to).add(edge);
  }


  /**
   * Returns the number of vertices in this graph (including deleted vertices).
   *
   * @return number of vertices
   */
  public int getNumberOfVertices() {

    return _outEdges.size();
  }


  /**
   * Checks if the given vertex is a deleted vertex of this graph.<br/>
   * Precondition: vertex must be smaller than nextFreeVertex
   *
   * @param vertex
   *          the vertex to check
   * @return {@code true} if the vertex is deleted, {@code false} otherwise.
   */
  public boolean isDeletedVertex(int vertex) {

    return _deletedVertices.get(vertex);
  }


  /**
   * Checks if the given vertex is a non-deleted vertex of this graph.
   *
   * @param vertex
   *          the vertex to check
   * @return {@code true} if the vertex is non-deleted, {@code false} otherwise
   */
  public boolean isVertex(int vertex) {

    return vertex < _outEdges.size() && !isDeletedVertex(vertex);
  }


  /**
   * Returns an iterator over all non-deleted vertices of the graph. See
   * {@link DirectedGraphBase.VertexIterator}.
   *
   * @return the vertex iterator
   */
  public Iterator<Integer> getVerticesIterator() {

    return new VertexIterator();
  }


  /**
   * Returns the edges emerging from the given vertex.
   *
   * @param vertex
   *          the vertex
   * @return the outgoing edges; may be empty
   */
  public List<Edge<EdgeInfo>> getOutEdges(int vertex) {

    List<Edge<EdgeInfo>> result = _outEdges.get(vertex);
    return (result == null) ? _defaultEmptyResult
      : Collections.unmodifiableList(result);
  }


  /**
   * Returns the edges ending in the given vertex.
   *
   * @param vertex
   *          the vertex
   * @return the incoming edges; may be empty
   */
  public List<Edge<EdgeInfo>> getInEdges(int vertex) {

    List<Edge<EdgeInfo>> result = _inEdges.get(vertex);
    return (result == null) ? _defaultEmptyResult
      : Collections.unmodifiableList(result);
  }


  /**
   * Returns an available vertex number. It either takes an available deleted
   * vertex or returns the next available vertex number.<br/>
   *
   * Iff a new vertex number is returned, the edge lists are extended properly.
   *
   * @return an available vertex number
   */
  public abstract int newVertex();


  /**
   * Creates a new edge with the given edge info and returns it. The edge is
   * part of this directed graph.
   *
   * @param edgeInfo
   *          the info assigned to the newly created edge
   * @param from
   *          the start vertex of the edge, which must be a valid vertex of the
   *          graph
   * @param to
   *          the end vertex of the edge, which must be a valid vertex of the
   *          graph
   * @return a newly created edge
   */
  public abstract Edge<EdgeInfo> newEdge(EdgeInfo edgeInfo, int from, int to);


  /**
   * Removes the given edge by modifying the edge lists of the adjacent
   * vertices.
   *
   * @param edge
   *          the edge to remove
   */
  public abstract void removeEdge(Edge<EdgeInfo> edge);


  /**
   * Removes the given vertex from this directed graph.<br/>
   *
   * Requires:
   * <li> removing all edges in and out of the vertex</li>
   * <li> removing all properties associated with the vertex</li>
   * <li> marking the vertex as being deleted</li>
   *
   * @param vertex
   *          the vertex to remove from the graph
   */
  public abstract void removeVertex(int vertex);


  /**
   * Changes the start vertex of this edge to the given vertex.
   *
   * @param startVertex
   *          the new start vertex
   */
  public void changeStartVertex(Edge<EdgeInfo> edge, int startVertex) {

    // remove edge from old start vertex's outgoing edge list
    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);
    }

    // set new start vertex
    setFrom(edge, startVertex);
  }


  /**
   * Changes the end vertex of this edge to the given vertex.
   *
   * @param endVertex
   *          the new end vertex
   */
  public void changeEndVertex(Edge<EdgeInfo> edge, int endVertex) {

    // remove edge from old end vertex's incoming edge list
    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);
    }

    // set new end vertex
    setTo(edge, endVertex);
  }


  /**
   * Returns the first edge emerging from the given vertex where the edge info
   * is compatible to the given edge info according to the given comparator.
   *
   * @param vertex
   *          the vertex
   * @param edgeInfo
   *          the edge info for which to find matching edges
   * @param comp
   *          a comparator to compare the edge info
   * @return the first edge that matches or {@code null} if no matching edge is
   *         found
   */
  public abstract Edge<EdgeInfo> findEdge(
      int vertex, EdgeInfo edgeInfo, Comparator<EdgeInfo> comp);


  /**
   * Returns all edges emerging from the given vertex where the edge info is
   * compatible to the given edge info according to the given comparator.
   *
   * @param vertex
   *          the vertex
   * @param edgeInfo
   *          the edge info for which to find matching edges
   * @param comp
   *          a comparator to compare the edge info
   * @return the list of matching edges; may be empty
   */
  public abstract List<Edge<EdgeInfo>> findEdges(
      int vertex, EdgeInfo edgeInfo, Comparator<EdgeInfo> comp);


  /**
   * Returns all edges from this directed graph where the edge info is
   * compatible to the given edge info according to the given comparator.
   *
   * @param edgeInfo
   *          the edge info for which to find matching edges
   * @param comp
   *          a comparator to compare the edge info
   * @return the list of matching edges; may be empty
   */
  public List<Edge<EdgeInfo>> findEdges(
      EdgeInfo edgeInfo,
      Comparator<EdgeInfo> comp) {

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

    for (int vertex = 0; vertex < _outEdges.size(); ++vertex) {
      if (!isDeletedVertex(vertex) && _outEdges.get(vertex) != null) {
        result.addAll(findEdges(vertex, edgeInfo, comp));
      }
    }
    return result;
  }


  /**
   * Helper method for compact that performs the renumbering of a single vertex.
   *
   * @param oldVertex
   *          the old vertex number
   * @param newVertex
   *          the new vertex number
   */
  private void renumberVertex(int oldVertex, int newVertex) {

    assert (isDeletedVertex(newVertex));
    // renumber all incoming and outgoing edges
    // outgoing edges:
    if (_outEdges.get(oldVertex) != null) {
      for (Edge<EdgeInfo> edge : _outEdges.get(oldVertex)) {
        edge.setStartVertex(newVertex);
      }
    }
    _outEdges.set(newVertex, _outEdges.get(oldVertex));
    _outEdges.set(oldVertex, null);
    // incoming edges:
    if (_inEdges.get(oldVertex) != null) {
      for (Edge<EdgeInfo> edge : _inEdges.get(oldVertex)) {
        edge.setEndVertex(newVertex);
      }
    }
    _inEdges.set(newVertex, _inEdges.get(oldVertex));
    _inEdges.set(oldVertex, null);

    // revive new vertex to not violate assertions in property vector
    _deletedVertices.clear(newVertex);

    // exchange the entries in the registered property maps
    for (VertexPropertyMap map : _vertexPropertyMaps.values()) {
      map.put(newVertex, map.get(oldVertex));
      map.remove(oldVertex);
    }

    // exchange the entries in the registered boolean property maps
    for (BitSet map : _vertexBooleanPropertyMaps.values()) {
      map.set(newVertex, map.get(oldVertex));
      map.clear(oldVertex);
    }

    // register old vertex as being deleted
    _deletedVertices.set(oldVertex);
  }


  /**
   * Compact this graph, i.e., fill the deleted vertices (holes) through
   * renumbering the vertices with the highest numbers.
   */
  public void compact() {

    // get the lowest deleted and the highest non-deleted vertex
    int currentLast = getNumberOfVertices();

    int firstDeletedVertex = _deletedVertices.nextSetBit(0);
    int lastVertex = currentLast - 1;
    while (firstDeletedVertex > 0 && firstDeletedVertex < lastVertex) {
      while (isDeletedVertex(lastVertex)) {
        --lastVertex;
      }
      if (firstDeletedVertex < lastVertex) {
        renumberVertex(lastVertex, firstDeletedVertex);
      }
      firstDeletedVertex = _deletedVertices.nextSetBit(firstDeletedVertex + 1);
      --lastVertex;
    }

    // check that everything is OK
    lastVertex = currentLast - 1;
    while (isDeletedVertex(lastVertex)) {
      --lastVertex;
    }
    ++lastVertex;
    if (_deletedVertices.nextSetBit(0) > 0
        && _deletedVertices.nextSetBit(0) != lastVertex) {
      System.out.println(_deletedVertices);
      System.out.println(lastVertex);
      assert (false);
    }

    for (int i = currentLast - 1; i >= lastVertex; --i) {
      _outEdges.remove(i);
      _inEdges.remove(i);
    }
  }


  /**
   * Registers a property map with this graph, so that it can be retrieved by
   * name and will be synchronized regarding delete and compact operations.
   *
   * @param name
   *          the name under which to register the property map
   * @param map
   *          the property map to register
   */
  public void register(String name, VertexPropertyMap<?> map) {

    _vertexPropertyMaps.put(name, map);
  }


  /**
   * Returns the property map registered under the given name.
   *
   * @param name
   *          the name of the registered property map
   * @return the property map of {@code null} if it doesn't exist
   */
  public VertexPropertyMap<?> getPropertyMap(String name) {

    return _vertexPropertyMaps.get(name);
  }


  /**
   * Registers a boolean property map with this graph, so that it can be
   * retrieved by name and will be synchronized regarding delete and compact
   * operations.
   *
   * @param name
   *          the name under which to register the property map
   * @param map
   *          the boolean property map to register
   */
  public void register(String name, BitSet map) {

    _vertexBooleanPropertyMaps.put(name, map);
  }


  /**
   * Returns the boolean property map registered under the given name.
   *
   * @param name
   *          the name of the registered property map
   * @return the property map of {@code null} if it doesn't exist
   */
  public BitSet getBooleanPropertyMap(String name) {

    return _vertexBooleanPropertyMaps.get(name);
  }


  /**
   * Returns a string representation of the given vertex using the (possibly)
   * given VertexPropertyMap. If propMap is null, the vertex number will be
   * used.
   *
   * @param vertex
   *          the vertex
   * @param propMap
   *          a property map
   * @return a string representation of the vertex
   */
  public String toString(int vertex, VertexPropertyMap<?> propMap) {

    StringBuilder strRep = new StringBuilder();

    String newline = System.getProperty("line.separator");

    if (!isDeletedVertex(vertex)) {
      if (_outEdges.get(vertex) != null) {
        for (Edge<EdgeInfo> edge : _outEdges.get(vertex)) {
          strRep.append(edge.toString(propMap)).append(newline);
        }
      }
      // ignore incoming edges since they are already printed as outgoing edges
      // of other vertices
      if (_outEdges.get(vertex) == null
          && _inEdges.get(vertex) == null) {
        // print vertices having no edges
        if (null != propMap) {
          strRep.append(propMap.get(vertex));
        }
        else {
          strRep.append(vertex + "");
        }
        strRep.append(newline);
      }
    }
    return strRep.toString();
  }


  /**
   * Returns a string representation of this graph using the (possibly) given
   * VertexPropertyMap to create a readable representation for the vertices. If
   * propMap is null, the vertex number will be used.
   *
   * @param propMap
   *          a property map
   * @return a string representation of this graph
   */
  public String toString(VertexPropertyMap<? extends Object> propMap) {

    StringBuilder strRep = new StringBuilder();

    for (Iterator<Integer> it = getVerticesIterator(); it.hasNext();) {
      int vertex = it.next();
      strRep.append(toString(vertex, propMap));
    }

    return strRep.toString();
  }


  /**
   * This overrides @see java.lang.Object#toString().
   *
   * @return a {@code String} representation of this graph
   */
  @Override
  public String toString() {

    return this.toString(getPropertyMap("names"));
  }


  /**
   * Recursive helper function for the dfs methods.<br/>
   *
   * The U set is implemented using the given BitSet {@code visited}.
   *
   * @param vertex
   *          the vertex where to start the recursive procedure
   * @param visitor
   *          the DFS visitor to use
   * @param visited
   *          the implementation of the U set (see slides)
   */
  protected abstract void dfsVisit(
      int vertex, DfsGraphVisitor<EdgeInfo> visitor, BitSet visited);


  /**
   * Visits all vertices of this graph in a depth first manner. The vertex list
   * is traversed in order, and every non-visited vertex is then taken as start
   * vertex, consecutively. The desired functionality can be implemented by the
   * given {@link GraphVisitorBase} argument.
   *
   * @param visitor
   *          the DFS visitor to use
   */
  public abstract void dfs(DfsGraphVisitor<EdgeInfo> visitor);


  /**
   * Visits the vertices of this graph that are reachable from vertex in a depth
   * first manner. The desired functionality can be implemented by the given
   * {@link GraphVisitorBase} argument.
   *
   * @param vertex
   *          the vertex where to start
   * @param visitor
   *          the DFS visitor to use
   */
  public void dfs(int vertex, DfsGraphVisitor<EdgeInfo> visitor) {

    if (!isDeletedVertex(vertex)) {
      visitor.startVertex(vertex, this);
      dfsVisit(vertex, visitor, new BitSet());
    }
  }


  /**
   * Helper function for the bfs methods.<br/>
   *
   * Visits all vertices of this graph in a breadth first manner. The vertex
   * list is traversed in order, and every non-visited vertex is then put onto a
   * queue, consecutively. The desired functionality can be implemented by the
   * given {@link GraphVisitorBase} argument.
   *
   * @param vertex
   *          the vertex where to start the procedure
   * @param visitor
   *          the BFS visitor to use
   * @param visited
   *          the implementation of the U set (see slides)
   */
  protected abstract void bfsVisit(
      int vertex, BfsGraphVisitor<EdgeInfo> visitor, BitSet visited);


  /**
   * Visits all vertices of this graph in a breadth first manner. The vertex
   * list is traversed in order, and every non-visited vertex is then put onto a
   * queue, consecutively. The desired functionality can be implemented by the
   * given {@link GraphVisitorBase} argument.
   *
   * @param visitor
   *          the BFS visitor to use
   */
  public abstract void bfs(BfsGraphVisitor<EdgeInfo> visitor);


  /**
   * Visits the vertices of this graph that are reachable from vertex in a
   * breadth first manner. The desired functionality can be implemented by the
   * given {@link GraphVisitorBase} argument.
   *
   * @param vertex
   *          the vertex where to start
   * @param visitor
   *          the BFS visitor to use
   */
  public void bfs(int vertex, BfsGraphVisitor<EdgeInfo> visitor) {

    if (!isDeletedVertex(vertex)) {
      visitor.startVertex(vertex, this);
      bfsVisit(vertex, visitor, new BitSet());
    }
  }


  /**
   * {@link VertexIterator} provides an iterator over the vertices of the graph.
   */
  public class VertexIterator implements Iterator<Integer> {

    /**
     * Keeps track of the current vertex.
     */
    private int _current;


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

      _current = 0;
      // move to the first non-delete vertex
      while (isDeletedVertex(_current)) {
        ++_current;
      }
    }


    /**
     * Checks if the iterator has a next element.
     *
     * @return a flag indicating if there is a next element.
     */
    @Override
    public boolean hasNext() {

      return _current < _outEdges.size();
    }


    /**
     * Returns the next non-delete vertex.
     *
     * @return the next vertex
     */
    @Override
    public Integer next() {

      int result = _current;
      // move to the next non-deleted vertex
      ++_current;
      while (hasNext() && isDeletedVertex(_current)) {
        ++_current;
      }
      return result;
    }


    /**
     * {@inheritDoc}
     */
    @Override
    public void remove() {

      // the remove operation is not supported by this iterator.
      throw new UnsupportedOperationException("Removing not supported");
    }
  }
}
