A "Trapping Rain Water" implementation using C++ template metaprogramming.

trapping_rain_water_tmp.cc

template <int, typename>
struct List;

struct Nil {
    template <int _NValue>
    using Append = List<_NValue, Nil>;
};

template <int _Value, typename _Next>
struct List {
private:
    template <int _NValue, typename _CurNext>
    struct _AppendHelper;
    
    template <int _NValue, int _CurValue, typename _CurNext>
    struct _AppendHelper<_NValue, List<_CurValue, _CurNext>> {
        using Next = List<
            _CurValue,
            typename _AppendHelper<_NValue, _CurNext>::Next
        >;
    };
    
    template <int _NValue>
    struct _AppendHelper<_NValue, Nil> {
        using Next = List<_NValue, Nil>;
    };
    
    template <int _Remain, typename _CurNext>
    struct _NthHelper;
    
    template <int _Remain, int _CurValue, typename _CurNext>
    struct _NthHelper<_Remain, List<_CurValue, _CurNext>> {
        static constexpr int value = _NthHelper<_Remain - 1, _CurNext>::value;
    };
    
    template <int _CurValue, typename _CurNext>
    struct _NthHelper<0, List<_CurValue, _CurNext>> {
        static constexpr int value = _CurValue;
    };
    
public:
    using Next = _Next;
    
    static constexpr int value = _Value;
    
    template <int _NValue>
    using Append = List<_NValue, typename _AppendHelper<_NValue, _Next>::Next>;
    
    template <int _Pos>
    static constexpr int nth = _NthHelper<_Pos, List<_Value, _Next>>::value;
};

template <typename Lst>
struct MakeMaxCache {
private:
    template <int _MaxValue, typename _Cache, typename _CurNext>
    struct _Helper;
    
    template <int _MaxValue, typename _Cache, int _CurValue, typename _CurNext>
    struct _Helper<_MaxValue, _Cache, List<_CurValue, _CurNext>> {
        static constexpr int current_max = _MaxValue > _CurValue
            ? _MaxValue
            : _CurValue;
        using Result = _Helper<
            current_max,
            typename _Cache::template Append<current_max>,
            _CurNext
        >::Result;
    };
    
    template <int _MaxValue, typename _Cache>
    struct _Helper<_MaxValue, _Cache, Nil> {
        using Result = _Cache;
    };
    
public:
    using Result = typename _Helper<0, List<0, Nil>, Lst>::Result::Next;
};

template <typename Input>
struct Trap {
private:
    using LeftMaxHeights = MakeMaxCache<Input>::Result;
    
    template <int _Index, typename _LeftMaxHeights, typename _CurNext>
    struct _Helper;
    
    template <typename _LeftMaxHeights, int _CurValue, typename _CurNext>
    struct _Helper<0, _LeftMaxHeights, List<_CurValue, _CurNext>> {
        using NextState = _Helper<1, _LeftMaxHeights, _CurNext>;
        
        static constexpr int trapped = NextState::trapped;
    };
    
    template <int _Index, typename _LeftMaxHeights, int _CurValue, typename _CurNext>
    struct _Helper<_Index, _LeftMaxHeights, List<_CurValue, _CurNext>> {
        using NextState = _Helper<_Index + 1, _LeftMaxHeights, _CurNext>;
        
        static constexpr int right_max_height = NextState::max_height;
        static constexpr int max_height = _CurValue > right_max_height
            ? _CurValue
            : right_max_height;
        static constexpr int min_wall_height = 
            _LeftMaxHeights::template nth<_Index - 1> > right_max_height
                ? right_max_height
                : _LeftMaxHeights::template nth<_Index - 1>;
        static constexpr int this_trapped = _CurValue < min_wall_height
            ? (min_wall_height - _CurValue)
            : 0;
        static constexpr int trapped = NextState::trapped + this_trapped;
    };
    
    template <int _Index, typename _LeftMaxHeights, int _CurValue>
    struct _Helper<_Index, _LeftMaxHeights, List<_CurValue, Nil>> {
        static constexpr int max_height = _CurValue;
        static constexpr int trapped = 0;
    };
    
public:
    static constexpr int result = _Helper<0, LeftMaxHeights, Input>::trapped;
};

using Input1 = List<0, List<1, List<0, List<2, List<1, List<0, List<1, List<3, List<2, List<1, List<2, List<1, Nil>>>>>>>>>>>>;
using Input2 = List<4, List<2, List<0, List<3, List<2, List<5, Nil>>>>>>;

static_assert(Trap<Input1>::result == 6);
static_assert(Trap<Input2>::result == 9);

// To make the linker happy.
int main(int argc, const char *argv[]) {
    return 0;
}