API tools faq
paste
aydarbiktimirov

Untitled

aydarbiktimirov
May 8th, 2014
210
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.07 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2.  
  3. namespace predicates
  4. {
  5.  
  6.     template<bool B>
  7.     struct bool_const { using value = bool_const; };
  8.  
  9.     //
  10.  
  11.     namespace helpers
  12.     {
  13.  
  14.         template<typename A, typename B>
  15.         struct bool_and;
  16.  
  17.         template<typename B>
  18.         struct bool_and<bool_const<true>, B> { using value = typename B::value; };
  19.  
  20.         template<typename B>
  21.         struct bool_and<bool_const<false>, B> { using value = bool_const<false>; };
  22.  
  23.         template<typename A, typename B>
  24.         struct bool_and { using value = typename bool_and<typename A::value, B>::value; };
  25.  
  26.         //
  27.  
  28.         template<typename A>
  29.         struct bool_not;
  30.  
  31.         template<bool B>
  32.         struct bool_not<bool_const<B>> { using value = bool_const<!B>; };
  33.  
  34.         template<typename A>
  35.         struct bool_not { using value = typename bool_not<typename A::value>::value; };
  36.  
  37.         template<typename A, typename B>
  38.         struct eq;
  39.  
  40.         template<typename A>
  41.         struct eq<A, A> { using value = bool_const<true>; };
  42.  
  43.         template<typename A, typename B>
  44.         struct eq { using value = bool_const<false>; };
  45.  
  46.         template<typename A, typename T, typename F>
  47.         struct cond;
  48.  
  49.         template<typename T, typename F>
  50.         struct cond<bool_const<true>, T, F> { using value = T; };
  51.  
  52.         template<typename T, typename F>
  53.         struct cond<bool_const<false>, T, F> { using value = F; };
  54.  
  55.         template<typename A, typename T, typename F>
  56.         struct cond { using value = typename cond<typename A::value, T, F>::value; };
  57.  
  58.     }
  59.  
  60.     //
  61.  
  62.     template<typename A, typename B>
  63.     using bool_and = typename helpers::bool_and<A, B>::value;
  64.  
  65.     template<typename A>
  66.     using bool_not = typename helpers::bool_not<A>::value;
  67.  
  68.     template<typename A, typename B>
  69.     using bool_or = bool_not<bool_and<bool_not<A>, bool_not<B>>>;
  70.  
  71.     template<typename A, typename B>
  72.     using eq = typename helpers::eq<A, B>::value;
  73.  
  74.     template<typename A, typename B>
  75.     using ne = bool_not<eq<A, B>>;
  76.  
  77.     template<typename A, typename T, typename F>
  78.     using cond = typename helpers::cond<A, T, F>::value;
  79.  
  80.     //
  81.  
  82.     template<bool B>
  83.     std::ostream &operator<<(std::ostream &stream, const bool_const<B> &)
  84.     {
  85.         return stream << (B ? "true" : "false");
  86.     }
  87.  
  88. }
  89.  
  90. namespace numbers
  91. {
  92.  
  93.     template<int N>
  94.     struct num { using value = num; };
  95.  
  96.     //
  97.  
  98.     namespace helpers
  99.     {
  100.  
  101.         template<typename N1, typename N2>
  102.         struct add;
  103.  
  104.         template<int N1, int N2>
  105.         struct add<num<N1>, num<N2>> { using value = num<N1 + N2>; };
  106.  
  107.         template<typename N1, typename N2>
  108.         struct sub;
  109.  
  110.         template<int N1, int N2>
  111.         struct sub<num<N1>, num<N2>> { using value = num<N1 - N2>; };
  112.  
  113.         template<typename N1, typename N2>
  114.         struct mult;
  115.  
  116.         template<int N1, int N2>
  117.         struct mult<num<N1>, num<N2>> { using value = num<N1 * N2>; };
  118.  
  119.         template<typename N1, typename N2>
  120.         struct div;
  121.  
  122.         template<int N>
  123.         struct div<num<N>, num<0>> {};
  124.  
  125.         template<int N1, int N2>
  126.         struct div<num<N1>, num<N2>> { using value = num<N1 / N2>; };
  127.  
  128.     }
  129.  
  130.     //
  131.  
  132.     template<typename N1, typename N2>
  133.     using add = typename helpers::add<N1, N2>::value;
  134.  
  135.     template<typename N1, typename N2>
  136.     using sub = typename helpers::sub<N1, N2>::value;
  137.  
  138.     template<typename N1, typename N2>
  139.     using mult = typename helpers::mult<N1, N2>::value;
  140.  
  141.     template<typename N1, typename N2>
  142.     using div = typename helpers::div<N1, N2>::value;
  143.  
  144.     //
  145.  
  146.     template<int N>
  147.     std::ostream &operator<<(std::ostream &stream, const num<N> &)
  148.     {
  149.         return stream << N;
  150.     }
  151.  
  152.     namespace predicates
  153.     // inline namespace predicates
  154.     {
  155.  
  156.         namespace helpers
  157.         {
  158.  
  159.             template<typename A, typename B>
  160.             struct lt;
  161.  
  162.             template<int A, int B>
  163.             struct lt<num<A>, num<B>> { using value = ::predicates::bool_const<A < B>; };
  164.  
  165.             template<typename A, typename B>
  166.             struct le;
  167.  
  168.             template<int A, int B>
  169.             struct le<num<A>, num<B>> { using value = ::predicates::bool_const<A <= B>; };
  170.  
  171.             template<typename A, typename B>
  172.             struct gt;
  173.  
  174.             template<int A, int B>
  175.             struct gt<num<A>, num<B>> { using value = ::predicates::bool_const<(A > B)>; };
  176.  
  177.             template<typename A, typename B>
  178.             struct ge;
  179.  
  180.             template<int A, int B>
  181.             struct ge<num<A>, num<B>> { using value = ::predicates::bool_const<A >= B>; };
  182.  
  183.         }
  184.  
  185.         template<typename A, typename B>
  186.         using lt = typename helpers::lt<A, B>::value;
  187.  
  188.         template<typename A, typename B>
  189.         using le = typename helpers::le<A, B>::value;
  190.  
  191.         template<typename A, typename B>
  192.         using gt = typename helpers::gt<A, B>::value;
  193.  
  194.         template<typename A, typename B>
  195.         using ge = typename helpers::ge<A, B>::value;
  196.  
  197.     }
  198.  
  199.     using namespace predicates;
  200.  
  201.     template<typename N>
  202.     using absolute_value = typename ::predicates::cond<lt<N, num<0>>, sub<num<0>, N>, N>;
  203.  
  204. }
  205.  
  206. namespace pairs
  207. {
  208.  
  209.     template<typename A, typename B>
  210.     struct pair { using value = pair; };
  211.  
  212.     namespace helpers
  213.     {
  214.  
  215.         template<typename P>
  216.         struct fst;
  217.  
  218.         template<typename A, typename B>
  219.         struct fst<pair<A, B>> { using value = A; };
  220.  
  221.         template<typename P>
  222.         struct snd;
  223.  
  224.         template<typename A, typename B>
  225.         struct snd<pair<A, B>> { using value = B; };
  226.  
  227.     }
  228.  
  229.     template<typename P>
  230.     using fst = typename helpers::fst<P>::value;
  231.  
  232.     template<typename P>
  233.     using snd = typename helpers::snd<P>::value;
  234.  
  235.     //
  236.  
  237.     template<typename A, typename B>
  238.     std::ostream &operator<<(std::ostream &stream, const pair<A, B> &)
  239.     {
  240.         return stream << "(" << A() << ", " << B() << ")";
  241.     }
  242.  
  243. }
  244.  
  245. namespace lists
  246. {
  247.  
  248.     template<typename List>
  249.     struct list;
  250.  
  251.     struct nil {};
  252.  
  253.     template<typename Head, typename Tail>
  254.     struct cons {};
  255.  
  256.     template<>
  257.     struct list<nil> { using value = list; };
  258.  
  259.     template<typename Head, typename Tail>
  260.     struct list<cons<Head, Tail>> { using value = list; };
  261.  
  262.     //
  263.  
  264.     namespace helpers
  265.     {
  266.  
  267.         template<typename List>
  268.         struct length;
  269.  
  270.         template<>
  271.         struct length<list<nil>> { using value = ::numbers::num<0>; };
  272.  
  273.         template<typename Head, typename Tail>
  274.         struct length<list<cons<Head, Tail>>> { using value = ::numbers::add<::numbers::num<1>, typename length<Tail>::value>; };
  275.  
  276.         //
  277.  
  278.         template<typename List>
  279.         struct head;
  280.  
  281.         template<typename Head, typename Tail>
  282.         struct head<list<cons<Head, Tail>>> { using value = Head; };
  283.  
  284.         //
  285.  
  286.         template<typename List>
  287.         struct tail;
  288.  
  289.         template<typename Head, typename Tail>
  290.         struct tail<list<cons<Head, Tail>>> { using value = Tail; };
  291.  
  292.         //
  293.  
  294.         template<typename L1, typename L2>
  295.         struct append;
  296.  
  297.         template<typename List>
  298.         struct append<list<nil>, List> { using value = List; };
  299.  
  300.         template<typename Head, typename Tail, typename List>
  301.         struct append<list<cons<Head, Tail>>, List> { using value = list<cons<Head, typename append<Tail, List>::value>>; };
  302.        
  303.         //
  304.  
  305.         template<template<typename, typename> class F, typename Init, typename List>
  306.         struct fold;
  307.  
  308.         template<template<typename, typename> class F, typename Init>
  309.         struct fold<F, Init, list<nil>> { using value = Init; };
  310.  
  311.         template<template<typename, typename> class F, typename Init, typename Head, typename Tail>
  312.         struct fold<F, Init, list<cons<Head, Tail>>> { using value = typename fold<F, typename F<Init, Head>::value, Tail>::value; };
  313.  
  314.         //
  315.  
  316.         template<template<typename> class F, typename List>
  317.         struct map;
  318.  
  319.         template<template<typename> class F>
  320.         struct map<F, list<nil>> { using value = list<nil>; };
  321.  
  322.         template<template<typename> class F, typename Head, typename Tail>
  323.         struct map<F, list<cons<Head, Tail>>> { using value = list<cons<typename F<Head>::value, typename map<F, Tail>::value>>; };
  324.  
  325.         template<typename X, typename List, template<typename, typename> class Cmp, typename Acc>
  326.         struct partition_;
  327.  
  328.         template<typename X, template<typename, typename> class Cmp, typename Acc>
  329.         struct partition_<X, list<nil>, Cmp, Acc> { using value = Acc; };
  330.  
  331.         template<typename X, typename Head, typename Tail, template<typename, typename> class Cmp, typename Acc>
  332.         struct partition_<X, list<cons<Head, Tail>>, Cmp, Acc>
  333.         {
  334.             using value = typename partition_<X, Tail, Cmp,
  335.                 ::predicates::cond<Cmp<Head, X>, ::pairs::pair<list<cons<Head, ::pairs::fst<Acc>>>, ::pairs::snd<Acc>>,
  336.                 ::pairs::pair<pairs::fst<Acc>, list<cons<Head, ::pairs::snd<Acc>>>>>>::value;
  337.         };
  338.  
  339.         template<typename X, typename List, template<typename, typename> class Cmp>
  340.         using partition = typename partition_<X, List, Cmp, ::pairs::pair<list<nil>, list<nil>>>::value;
  341.  
  342.         template<typename List, template<typename, typename> class Cmp>
  343.         struct qsort;
  344.  
  345.         template<template<typename, typename> class Cmp>
  346.         struct qsort<list<nil>, Cmp> { using value = list<nil>; };
  347.  
  348.         template<typename Head, typename Tail, template<typename, typename> class Cmp>
  349.         struct qsort<list<cons<Head, Tail>>, Cmp> { using value = typename append<
  350.             typename qsort<::pairs::fst<partition<Head, Tail, Cmp>>, Cmp>::value,
  351.             list<cons<Head, typename qsort<::pairs::snd<partition<Head, Tail, Cmp>>, Cmp>::value>>>::value; };
  352.  
  353.     }
  354.  
  355.     //
  356.  
  357.     template<typename List>
  358.     using lenght = typename helpers::length<List>::value;
  359.  
  360.     template<typename List>
  361.     using head = typename helpers::head<List>::value;
  362.  
  363.     template<typename List>
  364.     using tail = typename helpers::tail<List>::value;
  365.  
  366.     template<typename L1, typename L2>
  367.     using append = typename helpers::append<L1, L2>::value;
  368.  
  369.     template<template<typename, typename> class F, typename Init, typename List>
  370.     using fold = typename helpers::fold<F, Init, List>::value;
  371.  
  372.     template<template<typename> class F, typename List>
  373.     using map = typename helpers::map<F, List>::value;
  374.  
  375.     template<typename List, template<typename, typename> class Cmp>
  376.     using quick_sort = typename helpers::qsort<List, Cmp>::value;
  377.  
  378.     //
  379.  
  380.     template<typename List>
  381.     std::ostream &operator<<(std::ostream &, const list<List> &);
  382.  
  383.     template<>
  384.     std::ostream &operator<<(std::ostream &stream, const list<nil> &)
  385.     {
  386.         return stream << "[]";
  387.     }
  388.  
  389.     template<typename Head, typename Tail>
  390.     std::ostream &operator<<(std::ostream &stream, const list<cons<Head, Tail>> &)
  391.     {
  392.         return stream << "(" << Head() << "):" << Tail();
  393.     }
  394.  
  395. }
  396.  
  397. using namespace ::predicates;
  398. using namespace ::numbers;
  399. using namespace ::pairs;
  400. using namespace ::lists;
  401.  
  402. template<typename N>
  403. using inc = add<N, num<1>>;
  404.  
  405. template<typename A, typename B>
  406. using abs_lt = lt<absolute_value<A>, absolute_value<B>>;
  407.  
  408. int main()
  409. {
  410.     std::cout << list<nil>() << std::endl;
  411.     using test_list = list<cons<num<10>, list<cons<num<2>, list<cons<num<3>, list<cons<num<-7>, list<cons<num<8>, list<cons<num<2>, list<nil>>>>>>>>>>>>>;
  412.     std::cout << "length " << test_list() << " = " << lenght<test_list>() << std::endl;
  413.     std::cout << test_list() << " = " << head<test_list>() << " ++ " << tail<test_list>() << std::endl;
  414.     std::cout << "5 + 8 = " << add<num<5>, num<8>>() << std::endl;
  415.     std::cout << "fold (+) 0 " << test_list() << " = " << fold<add, num<0>, test_list>() << std::endl;
  416.     std::cout << lt<num<15>, num<2>>() << std::endl;
  417.     std::cout << lt<num<15>, num<20>>() << std::endl;
  418.     std::cout << "map (+ 1) c = " << map<inc, test_list>() << std::endl;
  419.     using new_list = append<test_list, map<inc, test_list>>;
  420.     std::cout << new_list() << std::endl;
  421.     std::cout << quick_sort<new_list, lt>() << std::endl;
  422.     std::cout << quick_sort<new_list, gt>() << std::endl;
  423.     std::cout << quick_sort<new_list, abs_lt>() << std::endl;
  424.     return 0;
  425. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!