Anonymous user
Algebraic data types: Difference between revisions
C++
(→{{header|REXX}}: added the REXX language.) |
(C++) |
||
Line 94:
)
);</lang>
=={{header|C++}}==
{{trans|Haskell}}
===Compile time===
C++ templates have a robust pattern matching facility, with some warts - for example, nested templates cannot be fully specialized, so we must use a dummy template parameter. This implementation uses C++17 deduced template parameters for genericity.
<lang c++>enum Color { R, B };
template<Color, class, auto, class> struct T;
struct E;
template<Color col, class a, auto x, class b> struct balance {
using type = T<col, a, x, b>;
};
template<class a, auto x, class b, auto y, class c, auto z, class d>
struct balance<B, T<R, T<R, a, x, b>, y, c>, z, d> {
using type = T<R, T<B, a, x, b>, y, T<B, c, z, d>>;
};
template<class a, auto x, class b, auto y, class c, auto z, class d>
struct balance<B, T<R, a, x, T<R, b, y, c>>, z, d> {
using type = T<R, T<B, a, x, b>, y, T<B, c, z, d>>;
};
template<class a, auto x, class b, auto y, class c, auto z, class d>
struct balance<B, a, x, T<R, T<R, b, y, c>, z, d>> {
using type = T<R, T<B, a, x, b>, y, T<B, c, z, d>>;
};
template<class a, auto x, class b, auto y, class c, auto z, class d>
struct balance<B, a, x, T<R, b, y, T<R, c, z, d>>> {
using type = T<R, T<B, a, x, b>, y, T<B, c, z, d>>;
};
template<auto x, class s> struct insert {
template<class, class = void> struct ins;
template<class _> struct ins<E, _> { using type = T<R, E, x, E>; };
template<Color col, class a, auto y, class b> struct ins<T<col, a, y, b>> {
template<int, class = void> struct cond;
template<class _> struct cond<-1, _> : balance<col, typename ins<a>::type, y, b> {};
template<class _> struct cond<1, _> : balance<col, a, y, typename ins<b>::type> {};
template<class _> struct cond<0, _> { using type = T<col, a, y, b>; };
using type = typename cond<x < y ? -1 : y < x ? 1 : 0>::type;
};
template<class> struct repaint;
template<Color col, class a, auto y, class b>
struct repaint<T<col, a, y, b>> { using type = T<B, a, y, b>; };
using type = typename repaint<typename ins<s>::type>::type;
};
template<auto x, class s> using insert_t = typename insert<x, s>::type;
template<class> void print();
int main() {
print<insert_t<1, insert_t<2, insert_t<0, insert_t<4, E>>>>>();
}</lang>
===Run time===
Although C++ has structured bindings and pattern matching through function overloading, it is not yet possible to use them together so we must match the structure of the tree being rebalanced separately from decomposing it into its elements. A further issue is that function overloads are not ordered, so to avoid ambiguity we must explicitly reject any (ill-formed) trees that would match more than one case during rebalance.
<lang c++>#include <memory>
#include <variant>
template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
enum Color { R, B };
using E = std::monostate;
template<class, Color> struct Node;
template<class T, Color C> using Ptr = std::unique_ptr<Node<T, C>>;
template<class T> using Tree = std::variant<E, Ptr<T, R>, Ptr<T, B>>;
template<class T, Color Col> struct Node {
static constexpr auto C = Col;
Tree<T> left;
T value;
Tree<T> right;
};
template<Color C, class A, class T, class B> Tree<T> tree(A&& a, T& x, B&& b) {
return Tree<T>{Ptr<T, C>{new Node<T, C>{std::move(a), std::move(x), std::move(b)}}};
}
template<class T> Tree<T> balance(Tree<T> s) {
auto&& ll = [](Ptr<T, R>& s, Ptr<T, R>& t, auto&, Ptr<T, B>& u, auto&, auto&, auto&) {
auto& [a, x, b] = *s;
auto& [s_, y, c] = *t;
auto& [t_, z, d] = *u;
return tree<R>(tree<B>(a, x, b), y, tree<B>(c, z, d));
};
auto&& lr = [](auto&, Ptr<T, R>& s, Ptr<T, R>& t, Ptr<T, B>& u, auto&, auto&, auto&) {
auto& [a, x, t_] = *s;
auto& [b, y, c] = *t;
auto& [s_, z, d] = *u;
return tree<R>(tree<B>(a, x, b), y, tree<B>(c, z, d));
};
auto&& rl = [](auto&, auto&, auto&, Ptr<T, B>& s, Ptr<T, R>& t, Ptr<T, R>& u, auto&) {
auto& [a, x, u_] = *s;
auto& [b, y, c] = *t;
auto& [t_, z, d] = *u;
return tree<R>(tree<B>(a, x, b), y, tree<B>(c, z, d));
};
auto&& rr = [](auto&, auto&, auto&, Ptr<T, B>& s, auto&, Ptr<T, R>& t, Ptr<T, R>& u) {
auto& [a, x, t_] = *s;
auto& [b, y, u_] = *t;
auto& [c, z, d] = *u;
return tree<R>(tree<B>(a, x, b), y, tree<B>(c, z, d));
};
auto&& l = [](auto& s) -> Tree<T>& {
return *std::visit(overloaded{[&](E) { return &s; }, [](auto& t) { return &t->left; }}, s);
};
auto&& r = [](auto& s) -> Tree<T>& {
return *std::visit(overloaded{[&](E) { return &s; }, [](auto& t) { return &t->right; }}, s);
};
return std::visit([&](auto&... ss) -> Tree<T> {
if constexpr (1 <
std::is_invocable_v<decltype(ll), decltype(ss)...> +
std::is_invocable_v<decltype(lr), decltype(ss)...> +
std::is_invocable_v<decltype(rl), decltype(ss)...> +
std::is_invocable_v<decltype(rr), decltype(ss)...>)
throw std::logic_error{""};
else
return overloaded{ll, lr, rl, rr, [&](auto&... ss) { return std::move(s); }}(ss...);
}, l(l(s)), l(s), r(l(s)), s, l(r(s)), r(s), r(r(s)));
}
template<class T> Tree<T> ins(T& x, Tree<T>& s) {
return std::visit(overloaded{
[&](E) -> Tree<T> { return tree<R>(s, x, s); },
[&](auto& t) {
auto& [a, y, b] = *t;
static constexpr auto Col = std::remove_reference_t<decltype(*t)>::C;
return x < y ? balance(tree<Col>(ins(x, a), y, b)) :
y < x ? balance(tree<Col>(a, y, ins(x, b))) :
std::move(s);
},
}, s);
}
template<class T> Tree<T> insert(T x, Tree<T> s) {
return std::visit(overloaded{
[](E) -> Tree<T> { throw std::logic_error{""}; },
[](auto&& t) {
auto& [a, y, b] = *t;
return tree<B>(a, y, b);
}
}, ins(x, s));
}
#include <iostream>
template<class T> void print(Tree<T> const& s, int i = 0) {
std::visit(overloaded{
[](E) {},
[&](auto& t) {
auto& [a, y, b] = *t;
print(a, i + 1);
std::cout << std::string(i, ' ') << "RB"[t->C] << " " << y << "\n";
print(b, i + 1);
}
}, s);
}
int main(int argc, char* argv[]) {
auto t = Tree<std::string>{};
for (auto i = 1; i != argc; ++i)
t = insert(std::string{argv[i]}, std::move(t));
print(t);
}</lang>
=={{header|Clojure}}==
Line 1,536 ⟶ 1,694:
{{omit from|Ada}}
{{Omit from|C}}
{{Omit from|Go}}
| |||