Diff algorithm C++

Question

I'm trying to create a program in C++ that could be able to diff two .txt files.

struct line
{
    string text;
    size_t num;
    int status;
};

void compareFiles(vector<line> &buffer_1, vector<line> &buffer_2, size_t index_1, size_t index_2)
{
    while(index_1 < buffer_1.size())
    {
         while(index_2 < buffer_2.size())
         {  
             X = buffer_1[index_1].text;
             Y = buffer_2[index_2].text;
             if(X == Y)
             {
                 ++index_1;
                 ++index_2;
             }
             else
             {
                 LCS();
                 string lcs = printLCS(X.length(), Y.length());

                 /*
                 * Here's my problem
                 */

             }
         }
     }
 }

As you can see, I have two buffers (vectors of lines) previously loaded with files contents . I also have the LCS algorithm fully functional (tested). LCS works on strings X and Y globally defined.

So, what I really need to do is compare buffers line by line with LCS, but I didn't manage a way to do it.

Could you please help me?

I suggest un-nesting your two while() loops -- what happens when you run out of lines in buffer_2? index_1 will never be incremented, and the outermost while loop will never terminate. while (index_1 < buffer_1.size() || index_2 < buffer_2.size()) { ... } would allow you to run over both inputs entirely. (Maybe one input differs from the other by only one new line appended at the end...) — sarnold
– sarnold, Commented May 27, 2011 at 23:25

statox · Accepted Answer · 2016-05-31 12:59:49Z

When in doubt, I usually defer to someone who's done it before. The venerable diff program has been around forever, and does what you want to do. Furthermore, it is open source, so head over to ftp://mirrors.kernel.org/gnu/diffutils/diffutils-3.0.tar.gz and check it out.

Once you unzip the archive, open up src/analyze.c. The diff_2_files function begins on line 472. The code that does the actual comparison runs from lines 512 - 537. They are reproduced below:

for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
{
    /* Read a buffer's worth from both files.  */
    for (f = 0; f < 2; f++)
        if (0 <= cmp->file[f].desc)
            file_block_read (&cmp->file[f],
                buffer_size - cmp->file[f].buffered);

    /* If the buffers differ, the files differ.  */
    if (cmp->file[0].buffered != cmp->file[1].buffered
            || memcmp (cmp->file[0].buffer,
                    cmp->file[1].buffer,
                    cmp->file[0].buffered))
    {
        changes = 1;
        break;
    }

    /* If we reach end of file, the files are the same.  */
    if (cmp->file[0].buffered != buffer_size)
    {
        changes = 0;
        break;
    }
}

The idea there is to load two buffers of identical size, then load each file into a buffer. Compare the two files one buffer at a time using memcmp, and see if any buffer differs from the other. If any buffer comparison does not return equal, then the two files are different. It's also important to note that you never have to read more than two buffers worth of data at a time, so this approach works on huge files too.

The source code is here git.savannah.gnu.org/cgit/diffutils.git/tree/src/analyze.c
The gnu diff source is absolute terrible and leaking like hell, doesn't matter because it's a command line tool but can't be just moved into a library.

Chris Frederick · Accepted Answer · 2011-05-27 23:59:17Z

First of all, I would rewrite LCS() to take two lines as parameters and return the longest common sequence—I imagine a function signature like std::string LCS(const line& lhs, const line& rhs). Then I would modify your while loops as follows.

for(int i = 0; i < buffer_1.size(); ++i)
{
    for(int j = 0; j < buffer_2.size(); ++j)
    {  
        std::string lcs = LCS(buffer_1[i].text, buffer_2[j].text);
        std::cout << "LCS[" << i << "][" << j << "]: " << lcs << std::endl;
    }
}

This will find and print the longest common sequence for each combination of lines in buffer_1 and buffer_2. Is this want you want to do? Did I understand your question correctly?

Collectives™ on Stack Overflow

Diff algorithm C++

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related