package edu.neu.ccs.demeter.aplib;

import java.util.*;

/**
 * A compact, efficient representation of a set of paths through a
 * class graph that can be used to guide a traversal of an object
 * graph.
 */
public abstract class Traversal {
  /** The version string for this version of the AP Library. */
  public static String getVersion() {
    return "AP Library version 0.8.6";
  }

  protected Traversal(ClassGraphI cg) {
    classGraph = cg;
  }

  /**
   * Compute the traversal determined by an encapsulated strategy and
   * a class graph.
   *
   * @throws TraversalException if the resulting traversal graph is empty.
   */	
  public static Traversal compute(StrategyI S, ClassGraphI G)
    throws TraversalException
  {
    return compute(S, G, null, null);
  }

  /**
   * Compute the traversal determined by an encapsulated strategy,
   * a class graph, a name map, and a constraint map.  The two maps,
   * if not null, are combined with the maps in the encapsulated
   * strategy.
   *
   * @throws TraversalException if:
   * <ul>
   *   <li>N maps symbolic node names in S to nodes that don't exist in G; or
   *   <li>TG(S,G,N,B) is empty; or
   *   <li>S is not a simple strategy or a strategy intersection.
   * </ul>
   */	
  public static Traversal compute(StrategyI S, ClassGraphI G,
				  NameMapI N, ConstraintMapI B)
    throws TraversalException
  {
    if (S.isSimpleStrategy())
      return new TraversalGraph(S.toSimpleStrategy(),G,N,B);
    else if (S.isStrategyCombination()) {
      StrategyCombinationI SC = S.toStrategyCombination();
      Traversal left =
	compute(SC.getLeftStrategy(), G, N, B);
      Traversal right =
	compute(SC.getRightStrategy(), G, N, B);
      if (SC.isStrategyIntersection())
	return left.intersect(right);
    }
    throw new TraversalException("Unknown strategy type: " + S);
  }

  /**
   * The intersection of this traversal with another traversal, that
   * is, the set of paths that are in both traversals.
   */
  public Traversal intersect(Traversal t)
    throws IncompatibleClassGraphsException
  {
    return new TraversalIntersection(this, t);
  }

  /** The class graph G used in computing this traversal. */
  public ClassGraphI getClassGraph() { return classGraph; }
  ClassGraphI classGraph;

  /**
   * An unmodifiable list of NodeSet objects representing the nodes in
   * the traversal.
   *
   * @see NodeSet
   */
  public abstract List getNodeSets();

  /**
   * The set of copies of class graph node v in the traversal, or null
   * if there are none.
   */
  public abstract NodeSet getNodeSet(Object v);

  /**
   * An unmodifiable List of NodeSet objects representing the start
   * set of the traversal (T<sub>s</sub>).
   */
  public abstract List getStartSet();

  /**
   * A NodeSet representing the start set of tokens (indices) for the
   * class graph node v, or null if v has no start tokens in the
   * traversal.
   */
  public abstract NodeSet getStartSet(Object v);

  /**
   * An unmodifiable List of NodeSet objects representing the finish
   * set of the traversal (T<sub>f</sub>).
   */
  public abstract List getFinishSet();

  /**
   * A NodeSet representing the finish set of tokens (indices) for the
   * class graph node v, or null if v has no finish tokens in the
   * traversal.
   */
  public abstract NodeSet getFinishSet(Object v);

  /**
   * A set of nodes v<sup>i</sup> in a traversal, where the nodes in the
   * set are all copies of the same class graph node v with different
   * indices i.
   */
  public abstract class NodeSet {
    NodeSet(Object v) { node = v; }

    /** The class graph node v corresponding to this node set. */
    public Object getNode() { return node; }
    Object node;

    /** Is s a set of copies of the same node as this? */
    public boolean sameNode(NodeSet s) {
      return node == null || s.node == null || node.equals(s.node);
    }

    public boolean equals(Object x) {
      return x instanceof NodeSet && sameNode((NodeSet) x);
    }

    public String toString() { return node + ": " + indicesToString(); }
    abstract String indicesToString();

    /**
     * An unmodifiable list of EdgeSet objects representing the
     * edges in the traversal going out of the nodes in this
     * set.  Each EdgeSet will be nonempty and have a nonempty
     * target NodeSet.
     */
    public List getOutgoingEdgeSets() {
      return Collections.unmodifiableList(getIncidentEdgeSets(true));
    }

    /**
     * An unmodifiable list of EdgeSet objects representing the
     * edges in the traversal coming into the nodes in this
     * set.  Each EdgeSet will be nonempty and have a nonempty
     * source NodeSet.
     */
    public List getIncomingEdgeSets() {
      return Collections.unmodifiableList(getIncidentEdgeSets(false));
    }

    /**
     * A list of EdgeSet objects representing the edges in the
     * traversal going out of (if outgoing is true) or coming
     * into (if outgoing is false) the nodes in this set.  Each
     * EdgeSet will be nonempty and have nonempty source and target
     * NodeSets.
     */
    abstract List getIncidentEdgeSets(boolean outgoing);
  }

  /**
   * An unmodifiable list of EdgeSet objects representing the edges
   * in the traversal.
   *
   * @see EdgeSet
   */
  public abstract List getEdgeSets();

  /**
   * The set of copies of the class graph edge with the given key in
   * the traversal, or null if there are none.
   */
  public abstract EdgeSet getEdgeSet(String key);

  /**
   * The set of copies of class graph edge e in the traversal graph,
   * or null if there are none.
   */
  public EdgeSet getEdgeSet(EdgeI e) {
    return getEdgeSet(edgeKey(e));
  }

  /**
   * The set of copies of class graph construction edge u
   * <code>-l-&gt;</code> v in the traversal, or null if there
   * are none.  Note that u and v may be either nodes or their string
   * representations.
   */
  public EdgeSet getConstructionEdgeSet(Object u, String l, Object v) {
    return getEdgeSet(cedgeKey(u, l, v));
  }

  /**
   * The set of copies of class graph alternation edge u
   * <code>=&gt;</code> v in the traversal, or null if there are none.
   * Note that u and v may be either nodes or their string
   * representations.
   */
  public EdgeSet getAlternationEdgeSet(Object u, Object v) {
    return getEdgeSet(aedgeKey(u, v));
  }

  /**
   * The set of copies of class graph inheritance edge u
   * <code>:&gt;</code> v in the traversal, or null if there are none.
   * Note that u and v may be either nodes or their string
   * representations.
   */
  public EdgeSet getInheritanceEdgeSet(Object u, Object v) {
    return getEdgeSet(iedgeKey(u, v));
  }

  /**
   * A set of edges u<sup>i</sup> <code>-l-&gt;</code> v<sup>j</sup>
   * in a traversal graph, where the edges in the set are all copies
   * of the same class graph edge u <code>-l-&gt;</code> v with
   * different endpoint indices i and j.
   */
  public abstract class EdgeSet {
    EdgeSet(EdgeI e) { edge = e; }

    /**
     * The class graph edge u <code>-l-&gt;</code> v corresponding to
     * this edge set.
     */
    public EdgeI getEdge() { return edge; }
    EdgeI edge;

    /** Is s a set of copies of the same edge as this? */
    public boolean sameEdge(EdgeSet s) {
      return edge.equals(s.edge);
    }

    public boolean equals(Object x) {
      return x instanceof EdgeSet && sameEdge((EdgeSet) x);
    }

    public String toString() {
      return edgeKey(edge) + ": " + indicesToString();
    }

    abstract String indicesToString();

    /** The set of target nodes of edges in this set. */
    public abstract NodeSet getTargetNodeSet();
  }

  /**
   * A unique identifying string for the given edge.  Useful for
   * hashing.
   */
  public static String edgeKey(EdgeI e) {
    return
      e == null ? "null" :
      e.isConstructionEdge() ? cedgeKey(e.getSource(),
					e.getLabel(),
					e.getTarget()) :
      e.isAlternationEdge() ? aedgeKey(e.getSource(), e.getTarget()) :
      e.isInheritanceEdge() ? iedgeKey(e.getSource(), e.getTarget()) :
      null;
  }

  /**
   * A unique identifying string for the construction edge
   * u <code>-l-&gt;</code> v.
   */
  static String cedgeKey(Object u, String l, Object v) {
    return "-> " + u + "," + l + "," + v;
  }

  /**
   * A unique identifying string for the alternation edge
   * u <code>=&gt;</code> v.
   */
  static String aedgeKey(Object u, Object v) {
    return "=> " + u + "," + v;
  }

  /**
   * A unique identifying string for the inheritance edge
   * u <code>:&gt;</code> v.
   */
  static String iedgeKey(Object u, Object v) {
    return ":> " + u + "," + v;
  }

  /** A string representation of the nodes and edges in the traversal. */
  public String toCompactString() {
    String s = "";
    s += "Start set: " + getStartSet() + "\n";
    s += "Nodes:\n";
    for (Iterator it = getNodeSets().iterator(); it.hasNext();)
      s += " " + it.next() + "\n";
    s += "Edges:\n";
    for (Iterator it = getEdgeSets().iterator(); it.hasNext();)
      s += " " + it.next() + "\n";
    s += "Finish set: " + getFinishSet() + "\n";
    return s;
  }

}