#ifndef __BINMEMOISE_H__
#define __BINMEMOISE_H__
#include "delegate.h"
#include "bintree.h"

template<typename T>
BinTree<T> code(Fun1<T, Int> fun)
{
	return mkLazy(mkFun([] (Fun1<T, Int> fun) {
		auto val = mkLazy(mkFun([] (Fun1<T, Int> fun) { return fun.invoke (Ref::mk (0L)); }));
		auto lFun = mkFun1([] (Fun1<T, Int> fun, R<Int> n) { return fun.invoke (Ref::mk (*n * 2L + 1L)); });
		auto rFun = mkFun1([] (Fun1<T, Int> fun, R<Int> n) { return fun.invoke (Ref::mk (*n * 2L + 2L)); });
		return Ref::mk <BinTree<T>> (code(lFun), val, code(rFun));
	}, fun));
}

template<typename T>
Fun1<T, Int> decode(BinTree<T> tree)
{
	return mkFun1([] (BinTree<T> tree, R<Int> n)
	{
		if (*n == 0L)
		{
			return tree->get();
		}
		else if (*n % 2L == 1L)
		{
			return (decode (tree->getLeft())).invoke (Ref::mk ((*n - 1L) / 2L));
		}
		else
		{
			return (decode (tree->getRight())).invoke (Ref::mk ((*n - 2L) / 2L));
		}
	});
}

#endif