/* 
 * © 2008 MySQL AB, 2008-2009 Sun Microsystems, Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#ifndef _STDEXT_LCS_H
#define _STDEXT_LCS_H

// TODO move to utlities project

//#ifndef _WIN32
#include <assert.h>
//#endif

#include <deque>
#include <iostream>

namespace stdext {

// code below was taken from 'vos' project which is under LGPL
// http://unix.freshmeat.net/redir/vos/20456/url_tgz/vos-0.23.0.tar.gz/vos-0.23.0/libs/vos/extensions/revcontrol/list3waymerge.cc
// MODIFICATIONS:
// 19-Jul-2007 namespace set to stdext
// 19-Jul-2007 Change and Entry now are template arguments
// 19-Jul-2007 functions accept iterators instead of std::deque
// 25-Jul-2007 two output iterators for elements in both input colletions
// 27-Jul-2007 added set_lcs_to_vectors method


#define LCS_LEFT  1
#define LCS_UP    2
#define LCS_DIAG  3


#define B(_i, _j) b[(_j)*m + (_i)]
#define C(_i, _j) c[(_j)*m + (_i)]


template<class _InIt1, class _InIt2, class _OutIt1, class _OutIt2> 
void printLCS(int* b, _InIt1 _First1, _InIt2 _First2, _OutIt1& _Dest1, _OutIt2& _Dest2, int i, int j, int m, int n)
{
    //std::cout << i << " " << j << std::endl;
    if(i == 0 || j == 0) return;
    if(B(i, j) == LCS_DIAG) {
        printLCS(b, _First1, _First2, _Dest1, _Dest2, i-1, j-1, m, n);
        //std::cout << X[i-1].pos << " " << X[i-1].name << " " << X[i-1].child << std::endl;
        *_Dest1++ = _First1 + i-1;
        *_Dest2++ = _First2 + j-1;
    } else if(B(i, j) == LCS_UP) {
        printLCS(b, _First1, _First2, _Dest1, _Dest2, i-1, j, m, n);
    } else {
        printLCS(b, _First1, _First2, _Dest1, _Dest2, i, j-1, m, n);
    }
}


static void printTable(int* b, int m, int n)
{
    std::cout << "  ";
    for(int j = 0; j <= n; j++) {
        std::cout << j << " ";
    }
    std::cout << std::endl;
    for(int i = 0; i <= m; i++) {
        std::cout << i << " ";
        for(int j = 0; j <= n; j++) {
            switch(B(i, j)) {
            case LCS_UP:
                std::cout << "| ";
                break;
            case LCS_LEFT:
                std::cout << "- ";
                break;
            case LCS_DIAG:
                std::cout << "\\ ";
                break;
            default:
                std::cout << "  ";
            }
        }
        std::cout << std::endl;
    }
}

template<
  class _InIt1, class _InIt2, 
  class _OutIt1, class _OutIt2,
  class _EqOp
> 
_OutIt1 LCS(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt1 _Dest1, _OutIt2 _Dest2, _EqOp _Eq)
{
    int m = _Last1 - _First1;
    int n = _Last2 - _First2;
    int* b = new int[(m+1)*(n+1)];
    int* c = new int[(m+1)*(n+1)];

    assert(b && c);
    if (!b || !c)
      exit(1); // TODO!!

    for(int i = 0; i <= m; i++) C(i, 0) = 0;
    for(int j = 0; j <= n; j++) C(0, j) = 0;

    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            //std::cout << (i-1) << " " << (j-1) << " ?= \"" << X[i-1].name << "\" \""
            //<< Y[j-1].child << "\"" << std::endl;

            if (_Eq(*(_First1 + i-1), *(_First2 + j-1))) { // *(_First1 + i-1) == *(_First2 + j-1)
                //std::cout << (i-1) << " " << (j-1) << " match \"" << X[i-1].name << "\" \""
                //<< Y[j-1].child << "\"" << std::endl;
                C(i, j) = C(i-1, j-1) + 1;
                B(i, j) = LCS_DIAG;
            } else if(C(i-1, j) > C(i, j-1)) {
                C(i, j) = C(i-1, j);
                B(i, j) = LCS_UP;
            } else {
                C(i, j) = C(i, j-1);
                B(i, j) = LCS_LEFT;
            }
        }
    }

    //std::cout << "Longest Common Subsequence:\n";
    printLCS(b, _First1, _First2, _Dest1, _Dest2, m, n, m, n);

    //printTable(b, m, n);

    delete[] b;
    delete[] c;
    return _Dest1;
}

#undef B
#undef C

template<class Entry, class Change>
void diffEntries(std::deque<Entry>& entries, std::deque<Entry>& base_entries,
                 std::deque<Change>& delete_list, std::deque<Change>& insert_list)
{
    std::deque<Entry> lcs;
    LCS(entries, base_entries, lcs);

    int bac = 0;
    int lcsc = 0;
    while(bac < base_entries.size() || lcsc < lcs.size()) {
        //std::cout << bac << " " << lcsc << " " << base_entries[bac].name << " " << lcs[lcsc].name << std::endl;
        if(lcsc < lcs.size() && base_entries[bac] == lcs[lcsc]) {
            bac++;
            lcsc++;
        } else {
            Change ch;
            ch.type = Change::DELETE;
            ch.pos = base_entries[bac].pos;
            ch.name = base_entries[bac].name;
            ch.child = base_entries[bac].child;
            ch.oldname = base_entries[bac].name;
            ch.oldchild = base_entries[bac].child;
            delete_list.push_front(ch);
            bac++;
        }
    }

    int nac = 0;
    lcsc = 0;
    while(nac < entries.size() || lcsc < lcs.size()) {
        if(lcsc < lcs.size() && entries[nac] == lcs[lcsc]) {
            nac++;
            lcsc++;
        } else {
            Change ch;
            ch.type = Change::INSERT;
            ch.pos = entries[nac].pos;
            ch.name = entries[nac].name;
            ch.child = entries[nac].child;
            insert_list.push_back(ch);
            nac++;
        }
    }
}

template<class Change>
void printChangelist(std::deque<Change>& clist)
{
    for(int i = 0; i < clist.size(); i++) {
        switch(clist[i].type) {
        case Change::INSERT:
            std::cout << "INSERT " << clist[i].pos << " " << clist[i].name
                      << " " << clist[i].child << std::endl;
            break;
        case Change::DELETE:
            std::cout << "DELETE " << clist[i].pos << " " << clist[i].oldname
                      << " " << clist[i].oldchild << std::endl;
            break;
        case Change::SET:
            break;
        }
    }
}

template<typename T> bool memberOf(T& item, std::deque<T>& thelist)
{
    bool both = false;
    for(int n = 0; n < thelist.size(); n++) {
        if(item == thelist[n]) return true;
    }
    return false;
}


template<class _InIt1,
  class _InIt2, class T, class _EqOp> inline
void set_lcs_to_vectors(_InIt1 _First1, _InIt1 _Last1,
                       _InIt2 _First2, _InIt2 _Last2,
                       std::vector<T> &vec1, 
                       std::vector<T> &vec2, 
                       _EqOp _Eq)
{
#undef min
  vec1.insert(vec1.begin(), std::min(_Last1 - _First1, _Last2 - _First2), typename std::vector<T>::value_type());
  vec2.insert(vec2.begin(), vec1.size(), typename std::vector<T>::value_type());
  vec1.erase(LCS(_First1, _Last1, _First2, _Last2, vec1.begin(), vec2.begin(), _Eq), vec1.end());
  vec2.erase(vec2.begin() + vec1.size(), vec2.end() );
}


}

#endif
