diffをつくる(2) -補遺

diffをつくる(2)で掲載したコードは文字列を比較するコードですが、std::stringを他のコンテナに替えればそのコンテナどうしのdiffがとれます。
任意のコンテナのdiffをとれるようにテンプレートにしたものを掲載。この例ではstd::stringのdiffとstd::vectorのdiffを取っています。

実行結果。

$ cat hello_c++.txt 
Hello
    C++!

$ cat hello_diff.txt 
Hello
    diff!

$ ./my_diff2_2 hello_c++.txt hello_diff.txt 
 FILE NAME
   h
   e
   l
   l
   o
   _
 - c
 - +
 - +
 + d
 + i
 + f
 + f
   .
   t
   x
   t

 CONTENTS
   Hello
 -     C++!
 +     diff!

以下コード。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>
#include <cstdlib>

enum EditType
{
    DELETE,
    COMMON,
    ADD
};

typedef std::vector<std::vector<int> > Grid;

template<typename container_t>
struct Item : public std::pair<EditType, typename container_t::value_type>
{
    Item(EditType ses, const typename container_t::value_type& value) : std::pair<EditType, typename container_t::value_type>(ses, value) {}
};

template<typename container_t>
std::ostream& operator << (std::ostream& out, const Item<container_t>& item)
{
    switch(item.first)
    {
    case ADD:    out << '+'; break;
    case COMMON: out << ' '; break;
    case DELETE: out << '-'; break;
    default:     out << '?'; break;
    }
    return out << ' ' << item.second;
}

template<typename container_t>
void initializeGrid(Grid& grid, std::size_t rowSize, std::size_t colSize)
{
    grid.resize(rowSize);
    for(std::size_t i = 0; i < grid.size(); ++i)
    {
        grid[i].resize(colSize);
    }
}

template<typename container_t>
void makeGraph(Grid& grid, const container_t& str_a, const container_t& str_b)
{
    for(std::size_t row = 0; row < grid.size(); ++row)
    {
        grid[row][0] = row;
    }

    for(std::size_t col = 0; col < grid[0].size(); ++col)
    {
        grid[0][col] = col;
    }

    for(std::size_t row = 1; row < grid.size(); ++row)
    {
        for(std::size_t col = 1; col < grid[row].size(); ++col)
        {
            int d = std::min(grid[row - 1][col] + 1, grid[row][col - 1] + 1);
            if(str_a[row - 1] == str_b[col - 1])
            {
                d = std::min(d, grid[row - 1][col - 1]);
            }
            grid[row][col] = d;
        }
    }
}

template<typename container_t>
std::vector<Item<container_t> > findSES(Grid& grid, const container_t& str_a, const container_t& str_b)
{
    std::vector<Item<container_t> > ses;
    int                             row = str_a.size();
    int                             col = str_b.size();

    while((row > 0) && (col > 0))
    {
        int a = grid[row][col - 1];
        int d = grid[row - 1][col];
        int c = grid[row - 1][col - 1];
        if(d < a)
        {
            if((str_a[row - 1] == str_b[col - 1]) && (c < d))
            {
                ses.push_back(Item<container_t>(COMMON, str_a[row - 1]));
                --row;
                --col;
            }
            else
            {
                ses.push_back(Item<container_t>(DELETE, str_a[row - 1]));
                --row;
            }
        }
        else
        {
            if((str_a[row - 1] == str_b[col - 1]) && (c < a))
            {
                ses.push_back(Item<container_t>(COMMON, str_a[row - 1]));
                --row;
                --col;
            }
            else
            {
                ses.push_back(Item<container_t>(ADD, str_b[col - 1]));
                --col;
            }
        }
    }

    while(col > 0)
    {
        ses.push_back(Item<container_t>(ADD, str_b[col - 1]));
        --col;
    }

    while(row > 0)
    {
        ses.push_back(Item<container_t>(DELETE, str_a[row - 1]));
        --row;
    }

    return std::vector<Item<container_t> >(ses.rbegin(), ses.rend());
}

template<typename container_t>
void diff(const container_t& str_a, const container_t& str_b)
{
    Grid grid;

    initializeGrid<container_t>(grid, str_a.size() + 1, str_b.size() + 1);

    makeGraph<container_t>(grid, str_a, str_b);

    std::vector<Item<container_t> > ses = findSES<container_t>(grid, str_a, str_b);

    std::copy(ses.begin(), ses.end(), std::ostream_iterator<Item<container_t> >(std::cout, "\n"));
}

#include <fstream>

void load(const char* filename, std::vector<std::string>& strings)
{
    strings.clear();
    std::ifstream src(filename);
    std::string   s;
    while(std::getline(src, s).good())
    {
        strings.push_back(s);
    }
}

int main(int argc, char* argv[])
{
    if(argc == 3)
    {
        std::cout << "FILE NAME\n";
        diff(std::string(argv[1]), std::string(argv[2]));

        std::cout << "\nCONTENTS\n";
        std::vector<std::string> strings_a;
        std::vector<std::string> strings_b;
        load(argv[1], strings_a);
        load(argv[2], strings_b);
        diff(strings_a, strings_b);
    }
    else
    {
        std::cout << argv[0] << " <str_a> <str_b>\n";
    }

    return 0;
}