//=======================================================================

// Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com>

//

// Distributed under the Boost Software License, Version 1.0.

// (See accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//=======================================================================

// Dominator tree computation

#ifndef BOOST_GRAPH_DOMINATOR_HPP

#define BOOST_GRAPH_DOMINATOR_HPP

#include <boost/config.hpp>

#include <deque>

#include <set>

#include <boost/graph/depth_first_search.hpp>

namespace boost {

  namespace detail {

    /**

     * An extended time_stamper which also records vertices for each dfs number

     */

    template<class TimeMap, class VertexVector, class TimeT, class Tag>

    class time_stamper_with_vertex_vector

      : public base_visitor<

      time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >

    {

    public :

      typedef Tag event_filter;

      time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, 

                                      TimeT& t)

        : timeStamper_(timeMap, t), v_(v) { }

      template<class Graph>

      void 

      operator()(const typename property_traits<TimeMap>::key_type& v, 

                 const Graph& g)

      {

        timeStamper_(v, g);

        v_[timeStamper_.m_time] = v;

      }

    private :

      time_stamper<TimeMap, TimeT, Tag> timeStamper_;

      VertexVector& v_;

    };

    /**

     * A convenient way to create a time_stamper_with_vertex_vector

     */

    template<class TimeMap, class VertexVector, class TimeT, class Tag>

    time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>

    stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,

                                   Tag)

    {

      return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, 

                                             Tag>(timeMap, v, t);

    }

    template<class Graph, class IndexMap, class TimeMap, class PredMap,

             class DomTreePredMap>

    class dominator_visitor

    {

      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

      typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    public :

      /**

       * @param g [in] the target graph of the dominator tree

       * @param entry [in] the entry node of g

       * @param domTreePredMap [out] the immediate dominator map

       *                             (parent map in dominator tree)

       */

      dominator_visitor(const Graph& g, const Vertex& entry,

                        DomTreePredMap domTreePredMap)

        : semi_(num_vertices(g)),

          ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),

          samedom_(ancestor_),

          best_(semi_),

          semiMap_(make_iterator_property_map(semi_.begin(), 

                                              get(vertex_index, g))),

          ancestorMap_(make_iterator_property_map(ancestor_.begin(), 

                                                  get(vertex_index, g))),

          bestMap_(make_iterator_property_map(best_.begin(), 

                                              get(vertex_index, g))),

          buckets_(num_vertices(g)),

          bucketMap_(make_iterator_property_map(buckets_.begin(), 

                                                get(vertex_index, g))),

          entry_(entry),

          domTreePredMap_(domTreePredMap),

          samedomMap(make_iterator_property_map(samedom_.begin(), 

                                                get(vertex_index, g)))

      {

      }

      void 

      operator()(const Vertex& n, const TimeMap& dfnumMap, 

                 const PredMap& parentMap, const Graph& g)

      {

        if (n == entry_) return;

        const VerticesSizeType numOfVertices = num_vertices(g);

        const Vertex p(get(parentMap, n));

        Vertex s(p);

        // 1. Calculate the semidominator of n,

        // based on the semidominator thm.

        // * Semidominator thm. : To find the semidominator of a node n,

        //   consider all predecessors v of n in the CFG (Control Flow Graph).

        //  - If v is a proper ancestor of n in the spanning tree

        //    (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n)

        //  - If v is a non-ancestor of n (so dfnum(v) > dfnum(n))

        //    then for each u that is an ancestor of v (or u = v),

        //    Let semi(u) be a candidate for semi(n)

        //   of all these candidates, the one with lowest dfnum is

        //   the semidominator of n.

        // For each predecessor of n

        typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;

        for (tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)

          {

            const Vertex v = source(*inItr, g);

            // To deal with unreachable nodes

            if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices)

              continue;

            Vertex s2;

            if (get(dfnumMap, v) <= get(dfnumMap, n))

              s2 = v;

            else

              s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));

            if (get(dfnumMap, s2) < get(dfnumMap, s))

              s = s2;

          }

        put(semiMap_, n, s);

        // 2. Calculation of n's dominator is deferred until

        // the path from s to n has been linked into the forest

        get(bucketMap_, s).push_back(n);

        get(ancestorMap_, n) = p;

        get(bestMap_, n) = n;

        // 3. Now that the path from p to v has been linked into

        // the spanning forest, these lines calculate the dominator of v,

        // based on the dominator thm., or else defer the calculation

        // until y's dominator is known

        // * Dominator thm. : On the spanning-tree path below semi(n) and

        //   above or including n, let y be the node

        //   with the smallest-numbered semidominator. Then,

        //      

        //  idom(n) = semi(n) if semi(y)=semi(n) or

        //            idom(y) if semi(y) != semi(n)

        typename std::deque<Vertex>::iterator buckItr;

        for (buckItr = get(bucketMap_, p).begin();

             buckItr != get(bucketMap_, p).end();

             ++buckItr)

          {

            const Vertex v(*buckItr);

            const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));

            if (get(semiMap_, y) == get(semiMap_, v))

              put(domTreePredMap_, v, p);

            else

              put(samedomMap, v, y);

          }

        get(bucketMap_, p).clear();

      }

    protected :

      /**

       * Evaluate function in Tarjan's path compression

       */

      const Vertex 

      ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)

      {

        const Vertex a(get(ancestorMap_, v));

        if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())

          {

            const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));

            put(ancestorMap_, v, get(ancestorMap_, a));

            if (get(dfnumMap, get(semiMap_, b)) <

                get(dfnumMap, get(semiMap_, get(bestMap_, v))))

              put(bestMap_, v, b);

          }

        return get(bestMap_, v);

      }

      std::vector<Vertex> semi_, ancestor_, samedom_, best_;

      PredMap semiMap_, ancestorMap_, bestMap_;

      std::vector< std::deque<Vertex> > buckets_;

      iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,

                            IndexMap> bucketMap_;

      const Vertex& entry_;

      DomTreePredMap domTreePredMap_;

    public :

      PredMap samedomMap;

    };

  } // namespace detail

  /**

   * @brief Build dominator tree using Lengauer-Tarjan algorithm.

   *                It takes O((V+E)log(V+E)) time.

   *

   * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding

   *      indexMap.

   *      If dfs has already run before,

   *      this function would be good for saving computations.

   * @pre Unreachable nodes must be masked as

   *      graph_traits<Graph>::null_vertex in parentMap.

   * @pre Unreachable nodes must be masked as

   *      (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap.

   * 

   * @param domTreePredMap [out] : immediate dominator map (parent map

   * in dom. tree)

   *

   * @note reference Appel. p. 452~453. algorithm 19.9, 19.10.

   *

   * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis

   */

  template<class Graph, class IndexMap, class TimeMap, class PredMap, 

           class VertexVector, class DomTreePredMap>

  void

  lengauer_tarjan_dominator_tree_without_dfs

    (const Graph& g,

     const typename graph_traits<Graph>::vertex_descriptor& entry,

     const IndexMap& indexMap,

     TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,

     DomTreePredMap domTreePredMap)

  {

    // Typedefs and concept check

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    function_requires< BidirectionalGraphConcept<Graph> >();

    const VerticesSizeType numOfVertices = num_vertices(g);

    if (numOfVertices == 0) return;

    // 1. Visit each vertex in reverse post order and calculate sdom.

    detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>

      visitor(g, entry, domTreePredMap);

    VerticesSizeType i;

    for (i = 0; i < numOfVertices; ++i)

      {

        const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);

        if (u != graph_traits<Graph>::null_vertex())

          visitor(u, dfnumMap, parentMap, g);

      }

    // 2. Now all the deferred dominator calculations,

    // based on the second clause of the dominator thm., are performed

    for (i = 0; i < numOfVertices; ++i)

      {

        const Vertex n(verticesByDFNum[i]);

        if (n == entry || n == graph_traits<Graph>::null_vertex())

          continue;

        Vertex u = get(visitor.samedomMap, n);

        if (u != graph_traits<Graph>::null_vertex())

          {

            put(domTreePredMap, n, get(domTreePredMap, u));

          }

      }

  }

  /**

   * Unlike lengauer_tarjan_dominator_tree_without_dfs,

   * dfs is run in this function and

   * the result is written to dfnumMap, parentMap, vertices.

   *

   * If the result of dfs required after this algorithm,

   * this function can eliminate the need of rerunning dfs.

   */

  template<class Graph, class IndexMap, class TimeMap, class PredMap, 

           class VertexVector, class DomTreePredMap>

  void

  lengauer_tarjan_dominator_tree

    (const Graph& g,

     const typename graph_traits<Graph>::vertex_descriptor& entry,

     const IndexMap& indexMap,

     TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,

     DomTreePredMap domTreePredMap)

  {

    // Typedefs and concept check

    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    function_requires< BidirectionalGraphConcept<Graph> >();

    // 1. Depth first visit

    const VerticesSizeType numOfVertices = num_vertices(g);

    if (numOfVertices == 0) return;

    VerticesSizeType time =

      (std::numeric_limits<VerticesSizeType>::max)();

    std::vector<default_color_type> 

      colors(numOfVertices, color_traits<default_color_type>::white());

    depth_first_visit

      (g, entry,

       make_dfs_visitor

         (make_pair(record_predecessors(parentMap, on_tree_edge()),

                    detail::stamp_times_with_vertex_vector

                      (dfnumMap, verticesByDFNum, time, on_discover_vertex()))),

       make_iterator_property_map(colors.begin(), indexMap));

    // 2. Run main algorithm.

    lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap, 

                                               parentMap, verticesByDFNum, 

                                               domTreePredMap);

  }

  /**

   * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum

   * internally.

   * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum),

   * this function would be more convenient one.

   */

  template<class Graph, class DomTreePredMap>

  void

  lengauer_tarjan_dominator_tree

    (const Graph& g,

     const typename graph_traits<Graph>::vertex_descriptor& entry,

     DomTreePredMap domTreePredMap)

  {

    // typedefs

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;

    typedef

      iterator_property_map<typename std::vector<VerticesSizeType>::iterator,

                            IndexMap> TimeMap;

    typedef

      iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap>

      PredMap;

    // Make property maps

    const VerticesSizeType numOfVertices = num_vertices(g);

    if (numOfVertices == 0) return;

    const IndexMap indexMap = get(vertex_index, g);

    std::vector<VerticesSizeType> dfnum(numOfVertices, 0);

    TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));

    std::vector<Vertex> parent(numOfVertices, 

                               graph_traits<Graph>::null_vertex());

    PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));

    std::vector<Vertex> verticesByDFNum(parent);

    // Run main algorithm

    lengauer_tarjan_dominator_tree(g, entry,

                                   indexMap, dfnumMap, parentMap, 

                                   verticesByDFNum, domTreePredMap);

  }

  /**

   * Muchnick. p. 182, 184

   *

   * using iterative bit vector analysis

   */

  template<class Graph, class IndexMap, class DomTreePredMap>

  void

  iterative_bit_vector_dominator_tree

    (const Graph& g,

     const typename graph_traits<Graph>::vertex_descriptor& entry,

     const IndexMap& indexMap,

     DomTreePredMap domTreePredMap)

  {

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename graph_traits<Graph>::vertex_iterator vertexItr;

    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    typedef

      iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,

                            IndexMap> vertexSetMap;

    function_requires<BidirectionalGraphConcept<Graph> >();

    // 1. Finding dominator

    // 1.1. Initialize

    const VerticesSizeType numOfVertices = num_vertices(g);

    if (numOfVertices == 0) return;

    vertexItr vi, viend;

    tie(vi, viend) = vertices(g);

    const std::set<Vertex> N(vi, viend);

    bool change = true;

    std::vector< std::set<Vertex> > dom(numOfVertices, N);

    vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap));

    get(domMap, entry).clear();

    get(domMap, entry).insert(entry);

    while (change)

      {

        change = false;

        for (tie(vi, viend) = vertices(g); vi != viend; ++vi)

          {

            if (*vi == entry) continue;

            std::set<Vertex> T(N);

            typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;

            for (tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr)

              {

                const Vertex p = source(*inItr, g);

                std::set<Vertex> tempSet;

                std::set_intersection(T.begin(), T.end(), 

                                      get(domMap, p).begin(), 

                                      get(domMap, p).end(),

                                      std::inserter(tempSet, tempSet.begin()));

                T.swap(tempSet);

              }

            T.insert(*vi);

            if (T != get(domMap, *vi))

              {

                change = true;

                get(domMap, *vi).swap(T);

              }

          } // end of for (tie(vi, viend) = vertices(g)

      } // end of while(change)

    // 2. Build dominator tree

    for (tie(vi, viend) = vertices(g); vi != viend; ++vi)

      get(domMap, *vi).erase(*vi);

    Graph domTree(numOfVertices);

    for (tie(vi, viend) = vertices(g); vi != viend; ++vi)

      {

        if (*vi == entry) continue;

        // We have to iterate through copied dominator set

        const std::set<Vertex> tempSet(get(domMap, *vi));

        typename std::set<Vertex>::const_iterator s;

        for (s = tempSet.begin(); s != tempSet.end(); ++s)

          {

            typename std::set<Vertex>::iterator t;

            for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); )

              {

        typename std::set<Vertex>::iterator old_t = t;

        ++t; // Done early because t may become invalid

                if (*old_t == *s) continue;

                if (get(domMap, *s).find(*old_t) != get(domMap, *s).end())

                  get(domMap, *vi).erase(old_t);

              }

          }

      }

    for (tie(vi, viend) = vertices(g); vi != viend; ++vi)

      {

        if (*vi != entry && get(domMap, *vi).size() == 1)

          {

            Vertex temp = *get(domMap, *vi).begin();

            put(domTreePredMap, *vi, temp);

          }

      }

  }

  template<class Graph, class DomTreePredMap>

  void

  iterative_bit_vector_dominator_tree

    (const Graph& g,

     const typename graph_traits<Graph>::vertex_descriptor& entry,

     DomTreePredMap domTreePredMap)

  {

    typename property_map<Graph, vertex_index_t>::const_type

      indexMap = get(vertex_index, g);

    iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap);

  }

} // namespace boost

#endif // BOOST_GRAPH_DOMINATOR_HPP