CPPTM Answers - Exercise 6-3

template<class R = na, class LC = na, class RC = na> struct tree {

	typedef R root;
	typedef LC left;
	typedef RC right;
	typedef tree type;

template<class E> struct is_leaf : true_ {};

template<class R,class LC, class RC> struct is_leaf<tree<R,LC,RC> > : false_ {};

template<class R=na, class LC=na, class RC=na> struct make_tree :

	tree<
		typename R::type,
		typename LC::type,
		typename RC::type
	>

template<class T, class E> struct insert:

	eval_if<
		less<E, typename T::root>,
		make_tree<
			typename T::root,
			eval_if<
				boost::is_same<typename T::left,na>,
				E,
				eval_if<
					is_leaf<typename T::left>,
					insert<tree<typename T::left>, E>,
					insert<typename T::left, E>
				>
			>,
			typename T::right
		>,
		make_tree<
			typename T::root,
			typename T::left,
			eval_if<
				boost::is_same<typename T::right,na>,
				E,
				eval_if<
					is_leaf<typename T::right>,
					insert<tree<typename T::right>, E>,
					insert<typename T::right, E>
				>
			>
		>
	>

template<class E> struct insert<tree<>, E> : tree<E> {};

struct binary_tree_inserter_op {

	template<class Prev, class Ele>
	struct apply : insert<Prev, Ele>
	{
	};

template<class I> struct binary_tree_inserter {

	typedef I state;
	typedef binary_tree_inserter_op operation;

int main(int argc, char** argv) {

    typedef copy<vector_c<int,17,25,10,2,11>, binary_tree_inserter< tree<> > >::type bst;
    BOOST_STATIC_ASSERT(( equal<inorder_view<bst>, vector_c<int,2,10,11,17,25>>::value ));