[boost] Container Difference proposal

From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-09-04 13:20:25

Is there any interest in adding an algorithm to the Boost libraries to
compute the difference between containers of objects?

I have written a template implementation of the Longest Common Subsequence
algorithm as described by David Eppstein at
http://www1.ics.uci.edu/~eppstein/161/960229.html and would like to work on
incorporating it into Boost if there is enough interest.

By way of an example, the following will find the difference between two
numeric arrays.

int main(int, char **)
{
    typedef boost::array<size_t, 8> array_t;

    array_t data1 = { 1, 3, 5, 7, 9, 11, 13, 15 };
    array_t data2 = { 2, 3, 5, 8, 9, 11, 13, 15 };
    array_t::const_iterator it;

    for (it=data1.begin(); it !=data1.end(); ++it)
        std::cout << *it << "  ";
    std::cout << std::endl;
    for (it=data2.begin(); it !=data2.end(); ++it)
        std::cout << *it << "  ";
    std::cout << std::endl;

    // create a typedef first so that we can use a short-handed
    // version later
    typedef cmp::compare< cmp::data_source<size_t> > compare_t;
    compare_t compare(data1.begin(), data1.end(), data2.begin(),
data2.end());

    signed                lcs;
    compare_t::result_set seq;

    // process the data sources
    if ((lcs = compare.compute_lcs(&seq, cmp::REMOVE | cmp::KEEP |
cmp::INSERT)) != -1)
    {
        std::cout << "Comparing numeric array" << std::endl
                  << "Lowest Common Subsequence length is " << lcs <<
std::endl;

        compare_t::result_set::iterator it  = seq.begin();
        compare_t::result_set::iterator ite = seq.end();
        for (; it != ite; ++it)
        {
            compare_t::result_set::value_type res = *it;
            if (res->type() == cmp::REMOVE)
                std::cout << "DEL: " << res->data() << std::endl;
            else if (res->type() == cmp::INSERT)
                std::cout << "INS: " << res->data() << std::endl;
        }
        seq.erase(seq.begin(), seq.end());
    }

    return 0;
}

Expected output:

1  3  5  7  9  11  13  15
2  3  5  8  9  11  13  15
Comparing numeric array
Lowest Common Subsequence length is 6
DEL: 1
INS: 2
DEL: 7
INS: 8