diffをつくる(3) -中編

経路を記憶するしくみを追加し、実際に文字列を比較してみます。
コードの様子が変わったように見えるかもしれませんが、やっていることの実質はおなじです。
メンバのtree_に編集の操作(delete/common/add)がツリーとして記録されます。diffの最後で見つかった経路の終端を覚えておきます。getSESで終端から逆順に経路をたどり、最後に順序を逆にしています。

#include <string>
#include <vector>
#include <algorithm>
#include <exception>

class Diff
{
public:
    class Exception : public std::exception
    {
    public:
        explicit Exception(const char* what) : std::exception(), what_(what) {}
        ~Exception() throw() {}
        const char* what() const throw() { return what_.c_str(); }

    private:
        std::string what_;
    };

    enum EditType
    {
        DELETE,
        COMMON,
        ADD
    };

    typedef std::vector<EditType> EditSequence;

    struct TreeNode
    {
        TreeNode(EditType editType, int prev) : editType(editType), prev(prev) {}

        EditType editType;
        int      prev;
    };

    struct VItem
    {
        VItem() : y(0), tail(-1) {}
        VItem(int y, int tail) : y(y), tail(tail) {}

        int y;
        int tail;
    };

    Diff() : tree_(), tail_(-1)
    {
    }

    int ond(const std::string& sequenceA, const std::string& sequenceB)
    {
        const int sizeA = sequenceA.size();
        const int sizeB = sequenceB.size();

        const int& offset = sizeA;

        VItem* v = new VItem[sizeA + sizeB + 1];

        tree_.clear();
        tail_ = -1;

        for(int d = 0; d <= sizeA + sizeB; ++d)
        {
            for(int k = -d; k <= d; k += 2)
            {
                if((k < -sizeA) || (sizeB < k))
                {
                    continue;
                }

                VItem* v_k   = v + k + offset;
                VItem* v_kp1 = v_k + 1;
                VItem* v_km1 = v_k - 1;

                if(d != 0)
                {
                    if(((k == -d) || (k == -sizeA)) || (((k != d) && (k != sizeB)) && ((v_km1->y + 1) < v_kp1->y)))
                    {
                        v_k->y    = v_kp1->y;
                        v_k->tail = tree_.size();
                        tree_.push_back(TreeNode(DELETE, v_kp1->tail));
                    }
                    else
                    {
                        v_k->y    = v_km1->y + 1;
                        v_k->tail = tree_.size();
                        tree_.push_back(TreeNode(ADD, v_km1->tail));
                    }
                }

                while(((v_k->y - k) < sizeA) && (v_k->y < sizeB) && (sequenceA[v_k->y - k] == sequenceB[v_k->y]))
                {
                    TreeNode node(COMMON, v_k->tail);
                    v_k->tail = tree_.size();
                    tree_.push_back(node);
                    ++v_k->y;
                }

                if(((v_k->y - k) >= sizeA) && (v_k->y >= sizeB))
                {
                    tail_ = v_k->tail;
                    delete[] v;
                    return d;
                }
            }
        }
        delete[] v;
        throw Exception("not found");
    }

    void getSES(EditSequence& ses) const
    {
        ses.clear();
        for(int i = tail_; i >= 0; i = tree_[i].prev)
        {
            ses.push_back(tree_[i].editType);
        }
        std::reverse(ses.begin(), ses.end());
    }

private:
    std::vector<TreeNode> tree_;
    int                   tail_;
};

#include <iostream>

std::ostream& operator << (std::ostream& out, Diff::EditType editType)
{
    switch(editType)
    {
    case Diff::DELETE: out << '-'; break;
    case Diff::COMMON: out << ' '; break;
    case Diff::ADD:    out << '+'; break;
    default:           out << '?'; break;
    }
    return out;
}

int main(int argc, char* argv[])
{
    if(argc != 3)
    {
        std::cout << argv[0] << " <str_a> <str_b>\n";
        return 0;
    }

    try
    {
        std::string str_a(argv[1]);
        std::string str_b(argv[2]);

        Diff diff;
		std::cout << diff.ond(str_a, str_b) << "\n";

        std::string::iterator a = str_a.begin();
        std::string::iterator b = str_b.begin();

        Diff::EditSequence ses;
        diff.getSES(ses);
        for(std::vector<Diff::EditType>::iterator i = ses.begin(); i != ses.end(); ++i)
        {
            std::cout << *i << " ";
            switch(*i)
            {
            case Diff::DELETE:
                std::cout << *a;
                ++a;
                break;

            case Diff::COMMON:
                std::cout << *a;
                ++a;
                ++b;
                break;

            case Diff::ADD:
                std::cout << *b;
                ++b;
                break;

            default:
                break;
            }
            std::cout << "\n";
        }
    }
    catch(const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }

    return 0;
}

実行例。

$ ./my_diff3 string streingth
 3
   s
   t
   r
 + e
   i
   n
   g
 + t
 + h

ondの中身がイマイチきれいな感じがしません。精進します。