fork download
copy 
  1. #include <iostream>
  2. #include <type_traits>
  3.  
  4. template <std::size_t...> struct index_sequence {};
  5.  
  6. template <std::size_t N, std::size_t... Is>
  7. struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};
  8.  
  9. template <std::size_t... Is>
  10. struct make_index_sequence_helper<0, Is...> {
  11.     using type = index_sequence<Is...>;
  12. };
  13.  
  14. template <std::size_t N>
  15. using make_index_sequence = typename make_index_sequence_helper<N>::type;
  16.  
  17. // Merging two packs of numbers.
  18. template <typename, typename> struct Merge;
  19.  
  20. template <template <std::size_t...> class P1, template <std::size_t...> class P2, std::size_t... Is, std::size_t... Js>
  21. struct Merge<P1<Is...>, P2<Js...>> {
  22. 	using type = P1<Is..., Js...>;
  23. };
  24.  
  25. // Obtaining the last element from a pack.
  26. template <typename, typename> struct LastType;
  27.  
  28. template <typename T, template <T...> class P, T Last>
  29. struct LastType<T, P<Last>> : std::integral_constant<T, Last> {};
  30.  
  31. template <typename T, template <T...> class P, T First, T... Rest>
  32. struct LastType<T, P<First, Rest...>> : LastType<T, P<Rest...>> {};
  33.  
  34. // Checking if t of type T exists in a pack of T objects.
  35. template <typename T, T t, T...> struct ExistsInPack;
  36.  
  37. template <typename T, T t, T First, T... Rest>
  38. struct ExistsInPack<T, t, First, Rest...> : ExistsInPack<T, t, Rest...> {};
  39.  
  40. template <typename T, T t, T... Rest>
  41. struct ExistsInPack<T, t, t, Rest...> : std::true_type {};
  42.  
  43. template <typename T, T t>
  44. struct ExistsInPack<T, t> : std::false_type {};
  45.  
  46. // Checking if t of type T is a last child.  Using ExistsInPack will not work correctly here.
  47. template <typename T, T t, T...> struct IsALastChild;
  48.  
  49. template <typename T, T t, T Child, T Parent, T... Rest>
  50. struct IsALastChild<T, t, Child, Parent, Rest...> : IsALastChild<T, t, Rest...> {};  // Here is the difference with ExistsInPack.  We must skip the parent and check the next child (if any) because we don't want the child to be read as a parent.
  51.  
  52. template <typename T, T t, T Parent, T... Rest>
  53. struct IsALastChild<T, t, t, Parent, Rest...> : std::true_type {};
  54.  
  55. template <typename T, T t>
  56. struct IsALastChild<T, t> : std::false_type {};
  57.  
  58. // Obtaining the adjacent vertices of a given vertex.
  59. template <std::size_t, typename, typename> struct AdjacentVerticesHelper;
  60.  
  61. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t From, std::size_t To, std::size_t... RemainingPairs, std::size_t... Accumulated>
  62. struct AdjacentVerticesHelper<Vertex, P<From, To, RemainingPairs...>, P<Accumulated...>> : AdjacentVerticesHelper<Vertex, P<RemainingPairs...>, P<Accumulated...>> {};
  63.  
  64. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t To, std::size_t... RemainingPairs, std::size_t... Accumulated>
  65. struct AdjacentVerticesHelper<Vertex, P<Vertex, To, RemainingPairs...>, P<Accumulated...>> : AdjacentVerticesHelper<Vertex, P<RemainingPairs...>, P<Accumulated..., To>> {};
  66.  
  67. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t... Accumulated>
  68. struct AdjacentVerticesHelper<Vertex, P<>, P<Accumulated...>> {
  69. 	using type = P<Accumulated...>;
  70. 	static const bool nonempty = sizeof...(Accumulated) > 0;
  71. };
  72.  
  73. template <std::size_t, typename> struct AdjacentVertices;
  74.  
  75. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t... Edges>
  76. struct AdjacentVertices<Vertex, P<Edges...>> : AdjacentVerticesHelper<Vertex, P<Edges...>, P<>> {};
  77.  
  78. // Given Child, find its parent from the pack P<LastChildAndParent...>.
  79. template <std::size_t Child, std::size_t First, std::size_t Second, std::size_t... Rest>
  80. struct GetParent : GetParent<Child, Rest...> {};
  81.  
  82. template <std::size_t Child, std::size_t Parent, std::size_t... Rest>
  83. struct GetParent<Child, Child, Parent, Rest...> : std::integral_constant<std::size_t, Parent> {};
  84.  
  85. template <std::size_t, typename, typename> struct RemoveChildAndParentHelper;
  86.  
  87. // Given Child, remove Child and its parent from P<LastChildAndParent...>.
  88. template <template <std::size_t...> class P, std::size_t Child, std::size_t First, std::size_t Second, std::size_t... Rest, std::size_t... Accumulated>
  89. struct RemoveChildAndParentHelper<Child, P<First, Second, Rest...>, P<Accumulated...>> : RemoveChildAndParentHelper<Child, P<Rest...>, P<Accumulated..., First, Second>> {};
  90.  
  91. template <template <std::size_t...> class P, std::size_t Child, std::size_t Parent, std::size_t... Rest, std::size_t... Accumulated>
  92. struct RemoveChildAndParentHelper<Child, P<Child, Parent, Rest...>, P<Accumulated...>> {
  93. 	using type = P<Accumulated..., Rest...>;
  94. };
  95.  
  96. template <template <std::size_t...> class P, std::size_t Child, std::size_t... Accumulated>
  97. struct RemoveChildAndParentHelper<Child, P<>, P<Accumulated...>> {
  98. 	using type = P<Accumulated...>;
  99. };
  100.  
  101. template <std::size_t, typename> struct RemoveChildAndParent;
  102.  
  103. template <template <std::size_t...> class P, std::size_t Child, std::size_t... LastChildAndParent>
  104. struct RemoveChildAndParent<Child, P<LastChildAndParent...>> : RemoveChildAndParentHelper<Child, P<LastChildAndParent...>, P<>> {};
  105.  
  106. // Removing from a pack all the elements in P<Visited...>.
  107. template <typename, typename, typename, typename> struct RemoveThoseAlreadyVisitedHelper;
  108.  
  109. template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Accumulated>
  110. struct RemoveThoseAlreadyVisitedHelper<T, P<First, Rest...>, P<Visited...>, P<Accumulated...>> : std::conditional<ExistsInPack<T, First, Visited...>::value,
  111. 		RemoveThoseAlreadyVisitedHelper<T, P<Rest...>, P<Visited...>, P<Accumulated...>>,
  112. 		RemoveThoseAlreadyVisitedHelper<T, P<Rest...>, P<Visited...>, P<Accumulated..., First>>
  113. 	>::type {};
  114.  
  115. template <typename T, template <T...> class P, T... Visited, T... Accumulated>
  116. struct RemoveThoseAlreadyVisitedHelper<T, P<>, P<Visited...>, P<Accumulated...>> {
  117. 	using type = P<Accumulated...>;
  118. };
  119.  
  120. template <typename, typename, typename> struct RemoveThoseAlreadyVisited;
  121.  
  122. template <typename T, template <T...> class P, T... Ts, T... Visited>
  123. struct RemoveThoseAlreadyVisited<T, P<Ts...>, P<Visited...>> : RemoveThoseAlreadyVisitedHelper<T, P<Ts...>, P<Visited...>, P<>> {};
  124.  
  125. template <typename T, template <T...> class P, T... Ts>
  126. struct RemoveThoseAlreadyVisited<T, P<Ts...>, P<>> {  // These remaining specializations are to avoid using the above specialization since 'type' is immediately obvious and needs no computation.
  127. 	using type = P<Ts...>;
  128. };
  129.  
  130. template <typename T, template <T...> class P, T... Visited>
  131. struct RemoveThoseAlreadyVisited<T, P<>, P<Visited...>> {
  132. 	using type = P<>;
  133. };
  134.  
  135. template <typename T, template <T...> class P>
  136. struct RemoveThoseAlreadyVisited<T, P<>, P<>> {  // This is needed to avoid ambiguity with the above two specializations.
  137. 	using type = P<>;
  138. };
  139.  
  140. // Removing duplicates from a pack.  This is only used for the alternate Graph class that allows using any values for its vertices (not necessarily consecutive).
  141. template <typename, typename, typename> struct RemoveDuplicatesHelper;
  142.  
  143. template <typename T, template <T...> class P, T First, T... Rest, T... Accumulated>
  144. struct RemoveDuplicatesHelper<T, P<First, Rest...>, P<Accumulated...>> : std::conditional<ExistsInPack<T, First, Accumulated..., Rest...>::value,
  145. 		RemoveDuplicatesHelper<T, P<Rest...>, P<Accumulated...>>,
  146. 		RemoveDuplicatesHelper<T, P<Rest...>, P<Accumulated..., First>>
  147. 	>::type {};
  148.  
  149. template <typename T, template <T...> class P, T... Accumulated>
  150. struct RemoveDuplicatesHelper<T, P<>, P<Accumulated...>> {
  151. 	using type = P<Accumulated...>;
  152. };
  153.  
  154. template <typename, typename> struct RemoveDuplicates;
  155.  
  156. template <typename T, template <T...> class P, T... Ts>
  157. struct RemoveDuplicates<T, P<Ts...>> : RemoveDuplicatesHelper<T, P<Ts...>, P<>> {};
  158.  
  159. // Now the main structs.
  160. template <typename, typename, typename, typename, typename> struct TopologicalSort;
  161. template <typename, typename, typename, typename, typename, typename> struct TopologicalSortHelper;
  162. template <typename, typename, typename, typename, typename, bool> struct CheckIfLastAdjacentVertex;
  163.  
  164. // End of the topological sort loop.  Replacing P<Visited...> with typename Visited and/or P<Edges...> with typename Edges and/or P<Vertices...> with typename Stack will cause ambiguity compiling error since neither this nor the above partial specialization is more specialized than the other. 
  165. template <template <std::size_t...> class P, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>
  166. struct TopologicalSort<P<>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>> {
  167. 	using topological_sort = P<Vertices...>;  // The final stack of vertices describing a topological order.
  168. };
  169.  
  170. // The topological sort loop.
  171. template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>  // First, Rest... are the vertices to be visited now (in that order).
  172. struct TopologicalSort<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>> :
  173. 	TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited..., First>, P<LastChildAndParent...>, P<Vertices...>,  // Append First to P<Visited...>.
  174. 			typename RemoveThoseAlreadyVisited<std::size_t, typename AdjacentVertices<First, P<Edges...>>::type, P<Visited...>>::type> {}; // Pass the adjacent vertices of First (if any), except those that have already been visited.
  175.  
  176. // First has adjacent edges, so visit its adjacent vertices, and prepend First to P<Vertices...> AFTER these visits.  To ensure this last part, add First and its last child into P<LastChildAndParent...>, and check later on when this last child of First is visited.  Note that since all vertices have UNIQUE std::size_t ID numbers, there will be no mix-up with other vertices when this last child is visited.
  177. template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices, typename AdjacentVertices>
  178. struct TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, AdjacentVertices> :
  179. 	CheckIfLastAdjacentVertex<typename Merge<AdjacentVertices, P<Rest...>>::type, P<Edges...>, P<Visited...>,  // Go into CheckIfLastAdjacentVertex, because it First is the last adjacent vertex of some parent vertex, that parent vertex shall be prepended to P<Vertices...> immediate after First is prepended to P<Vertices...>.
  180. 		P<LastChildAndParent..., LastType<std::size_t, AdjacentVertices>::value, First>, P<Vertices...>, IsALastChild<std::size_t, First, LastChildAndParent...>::value> {};
  181.  
  182. // First has no adjacent vertices, so prepend it to P<Vertices...>.  Here too, we must go into CheckIfLastAdjacentVertex in case First is the last adjacent vertex of some parent vertex.
  183. template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>
  184. struct TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, P<>> :
  185. 	CheckIfLastAdjacentVertex<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<First, Vertices...>, IsALastChild<std::size_t, First, LastChildAndParent...>::value> {};
  186.  
  187. // First is the last adjacent vertex of some parent vertex, so prepend its parent vertex to P<Vertices...>.  Note that First cannot be mixed up with another vertex because all vertices in the Graph have UNIQUE values.
  188. template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>
  189. struct CheckIfLastAdjacentVertex<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, true> :  // First and its parent vertex must be removed from P<LastChildAndParent...> right now.
  190. 	TopologicalSort<typename RemoveThoseAlreadyVisited<std::size_t, P<Rest...>, P<Visited...>>::type, P<Edges...>, P<Visited...>,  // We MUST remove all vertices that have already been visited before going into TopologicalSort, since TopologicalSort always assumes First has not been visited before.
  191. 		typename RemoveChildAndParent<First, P<LastChildAndParent...>>::type, P<GetParent<First, LastChildAndParent...>::value, Vertices...>> {};  // Do NOT prepend First into P<Vertices...> because this was already done in TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, P<>>.
  192.  
  193. // First is not the last adjacent vertex of some parent vertex, so simply do the regular TopologicalSort (but removing the vertices already visited first, of course).
  194. template <template <std::size_t...> class P, std::size_t... ToVisit, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>  // No need for First, Rest... here since First needs not be identified in this case.
  195. struct CheckIfLastAdjacentVertex<P<ToVisit...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, false> :
  196. 	TopologicalSort<typename RemoveThoseAlreadyVisited<std::size_t, P<ToVisit...>, P<Visited...>>::type, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>> {};
  197.  
  198. template <std::size_t N, std::size_t... Edges>
  199. struct Graph : TopologicalSort<make_index_sequence<N>, index_sequence<Edges...>, index_sequence<>, index_sequence<>, index_sequence<>> {};
  200.  
  201. // -------------------------- Testing --------------------------
  202. template <std::size_t Last>
  203. struct index_sequence<Last> {
  204.     static void print() {std::cout << Last << std::endl;}
  205. };
  206.  
  207. template <std::size_t First, std::size_t... Rest>
  208. struct index_sequence<First, Rest...> {
  209.     static void print() {std::cout << First << ' ';  index_sequence<Rest...>::print();}
  210. };
  211.  
  212. int main() {
  213. 	using DAG1 = Graph<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>;
  214. 	DAG1::topological_sort::print();  // 5 4 2 3 1 0
  215. 	std::cout << std::boolalpha << std::is_same<DAG1::topological_sort, index_sequence<5,4,2,3,1,0>>::value << std::endl;  // true
  216.  
  217. 	using DAG2 = Graph<8, 0,1, 0,2, 0,3, 1,4, 1,5, 2,4, 2,6, 3,5, 3,6, 4,7, 5,7, 6,7>;
  218. 	DAG2::topological_sort::print();  // 0 3 2 6 1 5 4 7
  219. 	std::cout << std::boolalpha << std::is_same<DAG2::topological_sort, index_sequence<0,3,2,6,1,5,4,7>>::value << std::endl;  // true
  220. }
Success #stdin #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5 4 2 3 1 0
true
0 3 2 6 1 5 4 7
true
https://ideone.com/9DKh4s
language:
C++14 (gcc 8.3)
created:
9 years 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!