#include "Library.h"

template<class T> struct MemoState {
    Pair<bool,Pair<List<T>*,int> > *table;
    const T *a, *b;
    int alen,blen;
};

template<class T, bool EQ(T,T)>
Pair<List<T>*,int> memo_lcs_internal(MemoState<T> *state, int ap, int bp) {
    Pair<bool,Pair<List<T>*,int> > *memo_ent = &state->table[ap*(state->blen+1)+bp];
    Pair<List<T>*,int> ret,ret2,ret3;
    if(memo_ent->a) return memo_ent->b;
    if(ap == state->alen || bp == state->blen) {
        ret.a = 0;
        ret.b = 0;
    } else if(EQ(state->a[ap],state->b[bp])) {
        ret2 = memo_lcs_internal<T,EQ>(state,ap+1,bp+1);
        ret.a = cons(state->a[ap],ret2.a);
        ret.b = ret2.b + 1;
    } else {
        ret2 = memo_lcs_internal<T,EQ>(state,ap+1,bp);
        ret3 = memo_lcs_internal<T,EQ>(state,ap,bp+1);
        ret = ret2.b > ret3.b ? ret2 : ret3;
    }
    memo_ent->a = true;
    memo_ent->b = ret;
    return ret;
}

template<class T, bool EQ(T,T)>
Pair<List<T>*,int> memo_lcs(const T *a, int alen, const T *b, int blen) {
    MemoState<T> state = {
        new Pair<bool,Pair<List<T>*,int> >[(alen+1)*(blen+1)],
        a, b, alen, blen
    };
    int i;
    for(i=0;i<(alen+1)*(blen+1);i++) state.table[i].a = false;
    Pair<List<T>*,int> ret = memo_lcs_internal<T,EQ>(&state, 0, 0);
    delete state.table;
    return ret;
}