fork download
copy 
  1. // Copyright 2014 Jarod42 aka Joris Dauphin
  2.  
  3. #include <cstdint>
  4. #include <tuple>
  5. #include <type_traits>
  6.  
  7. #if 1 // multiple dispatch
  8.  
  9. // sequence of size_t // not in C++11
  10. template <std::size_t ...> struct index_sequence {};
  11.  
  12. // Create index_sequence<0, >
  13. template <std::size_t N, std::size_t ...Is>
  14. struct make_index_sequence : make_index_sequence < N - 1, N - 1, Is... > {};
  15.  
  16. template <std::size_t ... Is>
  17. struct make_index_sequence<0, Is...> : index_sequence<Is...> {};
  18.  
  19. // Generic IVisitor
  20. // Do: using MyIVisitor = IVisitorTs<Child1, Child2, ...>
  21. template <typename ... Ts> class IVisitorTs;
  22.  
  23. template <typename T, typename ... Ts>
  24. class IVisitorTs<T, Ts...> : public IVisitorTs<Ts...>
  25. {
  26. public:
  27.     using tuple_type = std::tuple<T, Ts...>;
  28.     using IVisitorTs<Ts...>::visit;
  29.  
  30.     virtual void visit(const T &t) = 0;
  31. };
  32.  
  33. template <typename T> class IVisitorTs<T>
  34. {
  35. public:
  36.     using tuple_type = std::tuple<T>;
  37.  
  38.     virtual void visit(const T &t) = 0;
  39. };
  40.  
  41. namespace detail
  42. {
  43.  
  44. // retrieve the index of T in Ts...
  45. template <typename T, typename ... Ts> struct get_index;
  46.  
  47. template <typename T, typename ... Ts>
  48. struct get_index<T, T, Ts...> : std::integral_constant<std::size_t, 0> {};
  49.  
  50. template <typename T, typename Tail,  typename ... Ts>
  51. struct get_index<T, Tail, Ts...> :
  52.         std::integral_constant < std::size_t, 1 + get_index<T, Ts...>::value > {};
  53.  
  54. // retrieve the index of T in Tuple<Ts...>
  55. template <typename T, typename Tuple> struct get_index_in_tuple;
  56.  
  57. template <typename T, template <typename...> class C, typename ... Ts>
  58. struct get_index_in_tuple<T, C<Ts...>> : get_index<T, Ts...> {};
  59.  
  60. // tuple_contain
  61.  
  62. template <typename T, typename Tuple> struct tuple_contain;
  63.  
  64. template <typename T, typename ... Ts>
  65. struct tuple_contain<T, std::tuple<T, Ts...>> : std::true_type {};
  66.  
  67. template <typename T>
  68. struct tuple_contain<T, std::tuple<>> : std::false_type {};
  69.  
  70. template <typename T, typename T1, typename ... Ts>
  71. struct tuple_contain<T, std::tuple<T1, Ts...>> :
  72.     tuple_contain<T, std::tuple<Ts...>> {};
  73.  
  74. // get element of a multiarray
  75. template <std::size_t I>
  76. struct multi_array_getter {
  77.     template <typename T, std::size_t N>
  78.     static constexpr auto get(const T &a, const std::array<std::size_t, N> &indices)
  79.     -> decltype(multi_array_getter<I - 1>::get(a[indices[N - I]], indices))
  80.     {
  81.         return multi_array_getter<I - 1>::get(a[indices[N - I]], indices);
  82.     }
  83. };
  84.  
  85. template <>
  86. struct multi_array_getter<0> {
  87.     template <typename T, std::size_t N>
  88.     static constexpr auto get(const T &a, const std::array<std::size_t, N> &)
  89.     -> decltype(a)
  90.     {
  91.         return a;
  92.     }
  93. };
  94.  
  95. // Provide an implementation of visitor
  96. // by forwarding to C implementation (which may be non virtual)
  97. template <typename IVisitor, typename C, typename...Ts> struct IVisitorImpl;
  98.  
  99. template <typename IVisitor, typename C, typename T, typename...Ts>
  100. struct IVisitorImpl<IVisitor, C, T, Ts...> : IVisitorImpl<IVisitor, C, Ts...> {
  101.     virtual void visit(const T &t) override { C::visit(t); }
  102. };
  103.  
  104. template <typename IVisitor, typename C, typename T>
  105. struct IVisitorImpl<IVisitor, C, T> : IVisitor, C {
  106.     virtual void visit(const T &t) override { C::visit(t); }
  107. };
  108.  
  109. // helper to expand child type to IVisitorImpl
  110. template <typename IVisitor, typename C>
  111. struct IVisitorImplType;
  112.  
  113. template <typename ... Ts, typename C>
  114. struct IVisitorImplType<IVisitorTs<Ts...>, C> {
  115.     using type = IVisitorImpl<IVisitorTs<Ts...>, C, Ts...>;
  116. };
  117.  
  118. template <template <typename> class F, typename Tuple>
  119. struct to_index_sequence;
  120.  
  121. template <template <typename> class F, typename... Ts>
  122. struct to_index_sequence<F, std::tuple<Ts...>>
  123. {
  124.     using type = index_sequence<F<Ts>::value...>;
  125. };
  126.  
  127. template <typename Tuple, typename SeqFilter, typename...Res>
  128. struct filter_tuple;
  129.  
  130. template <typename...Res>
  131. struct filter_tuple<std::tuple<>, index_sequence<>, Res...>
  132. {
  133.     using type = std::tuple<Res...>;
  134. };
  135.  
  136. template <typename T, typename... Ts, std::size_t...Is, typename...Res>
  137. struct filter_tuple<std::tuple<T, Ts...>, index_sequence<0, Is...>, Res...>
  138. {
  139.     using type = typename filter_tuple<std::tuple<Ts...>,
  140.                                        index_sequence<Is...>,
  141.                                        Res...>::type;
  142. };
  143.  
  144. template <typename T, typename... Ts, std::size_t I,  std::size_t...Is, typename...Res>
  145. struct filter_tuple<std::tuple<T, Ts...>, index_sequence<I, Is...>, Res...>
  146. {
  147.     using type = typename filter_tuple<std::tuple<Ts...>,
  148.                                        index_sequence<Is...>,
  149.                                        Res..., T>::type;
  150. };
  151.  
  152. template <typename T> struct BUG; // TODO : REMOVE
  153.  
  154. // Create an multi array of pointer of function
  155. // (with all combinaisons of overload).
  156. template <typename Ret, typename F, typename Arg>
  157. class GetAllOverload
  158. {
  159. private:
  160.     template<std::size_t N, typename Tuple>
  161.     struct RestrictedTuple
  162.     {
  163.     private:
  164.         constexpr static std::size_t ArgSize = std::tuple_size<Arg>::value;
  165.         using baseArg = typename std::decay<typename std::tuple_element<ArgSize - N, Arg>::type>::type;
  166.         template <typename T>
  167.         using FilterDerivedOf = std::is_base_of<baseArg, T>;
  168.         using FilterIndex = typename to_index_sequence<FilterDerivedOf, Tuple>::type;
  169.     public:
  170.         using type = typename filter_tuple<Tuple, FilterIndex>::type;
  171.     };
  172.  
  173.     template <typename...Ts>
  174.     struct Functor {
  175.         // function which will be in array.
  176.         static Ret call(F &f, const Arg &arg)
  177.         {
  178.             return call_helper(f, arg, make_index_sequence<sizeof...(Ts)>());
  179.         }
  180.     private:
  181.         // The final dispatched function
  182.         template <std::size_t ... Is>
  183.         static Ret call_helper(F &f, const Arg &arg, index_sequence<Is...>)
  184.         {
  185.             using RetTuple = std::tuple<Ts &...>;
  186.             return f(static_cast<typename std::tuple_element<Is, RetTuple>::type>(std::get<Is>(arg))...);
  187.         }
  188.     };
  189.  
  190.     // helper class to create the multi array of function pointer
  191.     template <std::size_t N, typename Tuple, typename TupleForArg, typename...Ts>
  192.     struct Builder;
  193.  
  194.     template <typename Tuple, typename...Ts, typename...Ts2>
  195.     struct Builder<1, Tuple, std::tuple<Ts...>, Ts2...> {
  196.         using RetType = std::array<Ret(*)(F &, const Arg &), sizeof...(Ts)>;
  197.  
  198.         static constexpr RetType build()
  199.         {
  200.             return RetType { &Functor<Ts2..., Ts>::call... };
  201.         }
  202.     };
  203.  
  204.     template <std::size_t N, typename Tuple, typename ...Ts, typename...Ts2>
  205.     struct Builder<N, Tuple, std::tuple<Ts...>, Ts2...> {
  206.         using RecTuple = typename RestrictedTuple<N - 1, Tuple>::type;
  207.         template <typename T>
  208.         using RecType = Builder<N - 1, Tuple, RecTuple, Ts2..., T>;
  209.         using T0 = typename std::tuple_element<0u, std::tuple<Ts...>>::type;
  210.         using RetType = std::array<decltype(RecType<T0>::build()), sizeof...(Ts)>;
  211.  
  212.         static constexpr RetType build()
  213.         {
  214.             return RetType { RecType<Ts>::build()... };
  215.         }
  216.     };
  217.  
  218. public:
  219.     template <std::size_t N, typename VisitorTuple>
  220.     static constexpr auto get()
  221.     -> decltype(Builder<N, VisitorTuple, typename RestrictedTuple<N, VisitorTuple>::type>::build())
  222.     {
  223.         return Builder<N, VisitorTuple, typename RestrictedTuple<N, VisitorTuple>::type>::build();
  224.     }
  225. };
  226.  
  227.  
  228. template <typename Ret, typename IVisitor, typename F, std::size_t N>
  229. class dispatcher
  230. {
  231. private:
  232.     std::array<std::size_t, N> index;
  233.  
  234.     template<typename Arg>
  235.     struct visitorCallImpl {
  236.         template <typename T>
  237.         using FilterDerivedOf = std::is_base_of<Arg, T>;
  238.  
  239.         using Tuple = typename IVisitor::tuple_type;
  240.         using FilterIndex = typename to_index_sequence<FilterDerivedOf, Tuple>::type;
  241.         using FilteredTuple = typename filter_tuple<Tuple, FilterIndex>::type;
  242.  
  243.         template <typename T>
  244.         typename std::enable_if<tuple_contain<T, FilteredTuple>::value>::type
  245.         visit(const T &) const
  246.         {
  247.             *index = get_index_in_tuple<T, FilteredTuple>::value;
  248.         }
  249.  
  250.         template <typename T>
  251.         typename std::enable_if<!tuple_contain<T, FilteredTuple>::value>::type
  252.         visit(const T &) const
  253.         {
  254.             // should not be called.
  255.         }
  256.  
  257.         void setIndexPtr(std::size_t &index) { this->index = &index; }
  258.     private:
  259.         std::size_t *index = nullptr;
  260.     };
  261.  
  262.     template <std::size_t I, typename Tuple>
  263.     void set_index(const Tuple &t)
  264.     {
  265.         using ElementType = typename std::decay<typename std::tuple_element<I, Tuple>::type>::type;
  266.         using VisitorType = typename IVisitorImplType<IVisitor, visitorCallImpl<ElementType>>::type;
  267.         VisitorType visitor;
  268.         visitor.setIndexPtr(index[I]);
  269.  
  270.         std::get<I>(t).accept(visitor);
  271.     }
  272. public:
  273.     template <typename Tuple, std::size_t ... Is>
  274.     Ret operator()(F &&f, const Tuple &t, index_sequence<Is...>)
  275.     {
  276.         const int dummy[] = {(set_index<Is>(t), 0)...};
  277.         static_cast<void>(dummy); // silent the warning unused varaible
  278.         constexpr auto a = GetAllOverload < Ret, F &&, Tuple >::
  279.                            template get<sizeof...(Is), typename IVisitor::tuple_type>();
  280.         auto func = multi_array_getter<N>::get(a, index);
  281.         return (*func)(f, t);
  282.     }
  283. };
  284.  
  285. } // namespace detail
  286.  
  287. template <typename Ret, typename Visitor, typename F, typename ... Ts>
  288. Ret dispatch(F &&f, Ts &...args)
  289. {
  290.     constexpr std::size_t size = sizeof...(Ts);
  291.     detail::dispatcher<Ret, Visitor, F&&, size> d;
  292.     return d(std::forward<F>(f), std::tie(args...), make_index_sequence<size>());
  293. }
  294.  
  295. #endif // multiple dispatch
  296.  
  297. #if 1 // multiple dispatch usage
  298. struct Square;
  299. struct Rect;
  300. struct Circle;
  301.  
  302. using IShapeVisitor = IVisitorTs<Square, Rect, Circle>;
  303.  
  304. struct IShape {
  305.     virtual ~IShape() = default;
  306.     virtual void accept(IShapeVisitor &) const = 0;
  307. };
  308. struct Rect : IShape {
  309.     virtual void accept(IShapeVisitor &v) const override { v.visit(*this); }
  310. };
  311.  
  312. struct Square : Rect {
  313.     virtual void accept(IShapeVisitor &v) const override { v.visit(*this); }
  314. };
  315. struct Circle : IShape {
  316.     virtual void accept(IShapeVisitor &v) const override { v.visit(*this); }
  317. };
  318.  
  319. #include <iostream>
  320. class ShapePrinter : public IShapeVisitor
  321. {
  322. public:
  323.     void visit(const Rect &s) override { std::cout << "Rect"; }
  324.     void visit(const Square &s) override { std::cout << "Square"; }
  325.     void visit(const Circle &s) override { std::cout << "Circle"; }
  326. };
  327.  
  328. struct Printer
  329. {
  330.     void operator() (const Rect &s) const { std::cout << "Rect"; }
  331.     void operator() (const Square &s) const { std::cout << "Square"; }
  332.     void operator() (const Circle &s) const { std::cout << "Circle"; }
  333. };
  334.  
  335. struct P3
  336. {
  337.     template <typename S1, typename S2, typename S3>
  338.     void operator() (const S1& s1, const S2& s2, const S3& s3)
  339.     {
  340.         Printer()(s1); std::cout << " ";
  341.         Printer()(s2); std::cout << " ";
  342.         Printer()(s3); std::cout << std::endl;
  343.     }
  344. };
  345.  
  346.  
  347. struct IsEqual {
  348.     bool operator()(IShape &s1, IShape &s2) const
  349.     {
  350.         ShapePrinter printer;
  351.         s1.accept(printer);
  352.         std::cout << " != ";
  353.         s2.accept(printer);
  354.         std::cout << std::endl;
  355.         return false;
  356.     }
  357.  
  358.     template <typename S>
  359.     bool operator()(S &s1, S &s2) const
  360.     {
  361.         ShapePrinter printer;
  362.         s1.accept(printer);
  363.         std::cout << " == ";
  364.         s2.accept(printer);
  365.         std::cout << std::endl;
  366.         return true;
  367.     }
  368. };
  369.  
  370. int main(int argc, char *argv[])
  371. {
  372.     Rect rect;
  373.     Square sq;
  374.     Circle c;
  375.     IShape *shapes[] = { &rect, &sq, &c };
  376.  
  377.     for (auto shape1 : shapes) {
  378.         for (auto shape2 : shapes) {
  379.             dispatch<bool, IShapeVisitor>(IsEqual(), *shape1, *shape2);
  380.         }
  381.     }
  382.     dispatch<void, IShapeVisitor>(Printer(), sq);
  383.     dispatch<void, IShapeVisitor>(Printer(), *shapes[0]);
  384.  
  385.     dispatch<bool, IShapeVisitor>(IsEqual(), rect, *shapes[0]);
  386.     dispatch<bool, IShapeVisitor>(IsEqual(), *shapes[0], rect);
  387.  
  388.     dispatch<bool, IShapeVisitor>(IsEqual(), rect, sq);
  389.  
  390.     dispatch<void, IShapeVisitor>(P3(), c, rect, sq);
  391.  
  392.     return 0;
  393. }
  394.  
  395. #endif // multiple dispatch usage
  396.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Rect == Rect
Rect != Square
Rect != Circle
Square != Rect
Square == Square
Square != Circle
Circle != Rect
Circle != Square
Circle == Circle
SquareRectRect == Rect
Rect == Rect
Rect != Square
Circle Rect Square
https://ideone.com/ePgYK7
language:
C++14 (gcc 8.3)
created:
18 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!