Skip to content

Instantly share code, notes, and snippets.

@unixzii
Last active March 30, 2024 07:28
Show Gist options
  • Save unixzii/281933819c794673833925bebce9c949 to your computer and use it in GitHub Desktop.
Save unixzii/281933819c794673833925bebce9c949 to your computer and use it in GitHub Desktop.
A "Trapping Rain Water" implementation using C++ template metaprogramming.
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment