Last active
February 14, 2022 07:54
-
-
Save ifd3f/f1289da366222a6f94acbc32f298427e to your computer and use it in GitHub Desktop.
A compile-time binary search tree implementation using C++ templates.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
template <bool condition, typename T, typename F> | |
struct Conditional { | |
typedef F result; | |
}; | |
template <typename T, typename F> | |
struct Conditional<true, T, F> { | |
typedef T result; | |
}; | |
template <int a, int b, typename L, typename E, typename G> | |
struct Compare { | |
typedef typename Conditional< | |
a < b, | |
L, | |
typename Conditional<a == b, E, G>::result | |
>::result result; | |
}; | |
template <int k, int v, typename L, typename R> | |
struct Tree { | |
static constexpr int key = k; | |
static constexpr int value = v; | |
typedef L left; | |
typedef R right; | |
}; | |
template <int k, typename Tree> | |
struct Search; | |
template <int k> | |
struct Search<k, void> { | |
typedef void result; | |
}; | |
template <int k, int ek, int ev, typename L, typename R> | |
struct Search<k, Tree<ek, ev, L, R>> { | |
typedef typename Compare< | |
k, ek, | |
typename Search<k, L>::result, | |
Tree<ek, ev, L, R>, | |
typename Search<k, R>::result | |
>::result result; | |
}; | |
template <int k, int v, typename Tree> | |
struct Insert; | |
template <int k, int v, int ek, int ev, typename L, typename R> | |
struct Insert<k, v, Tree<ek, ev, L, R>> { | |
typedef typename Compare< | |
k, ek, | |
Tree<ek, ev, typename Insert<k, v, L>::result, R>, | |
Tree<k, v, L, R>, | |
Tree<ek, ev, L, typename Insert<k, v, R>::result> | |
>::result result; | |
}; | |
template <int k, int v> | |
struct Insert<k, v, void> { | |
typedef Tree<k, v, void, void> result; | |
}; | |
template <typename Tree> | |
struct Count; | |
template <> | |
struct Count<void> { | |
static const int value = 0; | |
}; | |
template <int ek, int ev, typename L, typename R> | |
struct Count<Tree<ek, ev, L, R>> { | |
static const int value = 1 + Count<L>::value + Count<R>::value; | |
}; | |
int main() { | |
typedef typename Insert<1, 9, void>::result tree; | |
typedef typename Insert<2, 1, tree>::result tree1; | |
typedef typename Insert<2, 4, tree1>::result tree2; | |
typedef typename Insert<3, 9, tree2>::result tree3; | |
typedef typename Insert<2, 16, tree3>::result tree4; | |
std::cout << Count<tree4>::value << std::endl; | |
std::cout << Search<1, tree4>::result::value << std::endl; | |
std::cout << Search<2, tree4>::result::value << std::endl; | |
std::cout << Search<3, tree4>::result::value << std::endl; | |
std::cout << typeid(Search<1329, tree4>::result).name() << std::endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment