// Copyright David Abrahams 2002.
// 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)
#include 
#include 
#include 
#include 
#if _MSC_FULL_VER >= 13102171 && _MSC_FULL_VER 
  index_entry_interface;
  typedef index_entry_interface::inherited index_entry;
  enum { ksrc_static_t, kvertex, kdynamic_id };
  
  typedef std::vector type_index_t;

  
  type_index_t& type_index()
  {
      static type_index_t x;
      return x;
  }

  template 
  struct select1st
  {
      typedef typename tuples::element::type result_type;
      
      result_type const& operator()(Tuple const& x) const
      {
          return tuples::get(x);
      }
  };
  
  // map a type to a position in the index
  inline type_index_t::iterator type_position(class_id type)
  {
      using namespace boost::placeholders;
      typedef index_entry entry;
      
      return std::lower_bound(
          type_index().begin(), type_index().end()
          , boost::make_tuple(type, vertex_t(), dynamic_id_function(0))
          , boost::bind(std::less()
               , boost::bind(select1st(), _1)
               , boost::bind(select1st(), _2)));
  }

  inline index_entry* seek_type(class_id type)
  {
      type_index_t::iterator p = type_position(type);
      if (p == type_index().end() || tuples::get(*p) != type)
          return 0;
      else
          return &*p;
  }
  
  // Get the entry for a type, inserting if necessary
  inline type_index_t::iterator demand_type(class_id type)
  {
      type_index_t::iterator p = type_position(type);

      if (p != type_index().end() && tuples::get(*p) == type)
          return p;

      vertex_t v = add_vertex(full_graph().topology());
      vertex_t v2 = add_vertex(up_graph().topology());
      unused_variable(v2);
      assert(v == v2);
      return type_index().insert(p, boost::make_tuple(type, v, dynamic_id_function(0)));
  }

  // Map a two types to a vertex in the graph, inserting if necessary
  typedef std::pair
        type_index_iterator_pair;
  
  inline type_index_iterator_pair
  demand_types(class_id t1, class_id t2)
  {
      // be sure there will be no reallocation
      type_index().reserve(type_index().size() + 2);
      type_index_t::iterator first = demand_type(t1);
      type_index_t::iterator second = demand_type(t2);
      if (first == second)
          ++first;
      return std::make_pair(first, second);
  }

  struct q_elt
  {
      q_elt(std::size_t distance
            , void* src_address
            , vertex_t target
            , cast_function cast
            )
          : distance(distance)
          , src_address(src_address)
          , target(target)
          , cast(cast)
      {}
      
      std::size_t distance;
      void* src_address;
      vertex_t target;
      cast_function cast;

      bool operatorkey == seek.key)
      {
          return cache_pos->offset == cache_element::not_found
              ? 0 : (char*)p + cache_pos->offset;
      }

      // If we are starting at the most-derived type, only look in the up graph
      smart_graph const& g = polymorphic && dynamic_id.second != src_t
          ? full_graph() : up_graph();
    
      void* result = search(
          g, p, tuples::get(*src_p)
          , tuples::get(*dst_p));

      // update the cache
      c.insert(cache_pos, seek)->offset
          = (result == 0) ? cache_element::not_found : (char*)result - (char*)p;

      return result;
  }
}

namespace python { namespace objects {

BOOST_PYTHON_DECL void* find_dynamic_type(void* p, class_id src_t, class_id dst_t)
{
    return convert_type(p, src_t, dst_t, true);
}

BOOST_PYTHON_DECL void* find_static_type(void* p, class_id src_t, class_id dst_t)
{
    return convert_type(p, src_t, dst_t, false);
}

BOOST_PYTHON_DECL void add_cast(
    class_id src_t, class_id dst_t, cast_function cast, bool is_downcast)
{
    BOOST_PYTHON_LOCK_STATE();

    // adding an edge will invalidate any record of unreachability in
    // the cache.
    static std::size_t expected_cache_len = 0;
    cache_t& c = cache();
    if (c.size() > expected_cache_len)
    {
        c.erase(std::remove_if(
                    c.begin(), c.end(),
                    mem_fn(&cache_element::unreachable))
                , c.end());

        // If any new cache entries get added, we'll have to do this
        // again when the next edge is added
        expected_cache_len = c.size();
    }
    
    type_index_iterator_pair types = demand_types(src_t, dst_t);
    vertex_t src = tuples::get(*types.first);
    vertex_t dst = tuples::get(*types.second);

    cast_graph* const g[2] = { &up_graph().topology(), &full_graph().topology() };
    
    for (cast_graph*const* p = g + (is_downcast ? 1 : 0); p < g + 2; ++p)
    {
        edge_t e;
        bool added;

        tie(e, added) = add_edge(src, dst, **p);
        assert(added);

        put(get(edge_cast, **p), e, cast);
        put(get(edge_index, **p), e, num_edges(full_graph().topology()) - 1);
    }
}

BOOST_PYTHON_DECL void register_dynamic_id_aux(
    class_id static_id, dynamic_id_function get_dynamic_id)
{
    BOOST_PYTHON_LOCK_STATE();
    tuples::get(*demand_type(static_id)) = get_dynamic_id;
}

}}} // namespace boost::python::objects