Get the path "difference" between two directories

Question

The situation:

I got one or more absolute paths, e.g.:

1. /home/benjamin/test/
2. /home/benjamin/test/a/1
3. /home/benjamin/test/b/1

How can I get the difference between two paths? Let's say I want to know how I can get from path 1 to path 2. Expected result would be

/home/benjamin/test/a/1 - /home/benjamin/test/ = /a/1

Is there a more elegant way than subtracting the strings from each other?

Answer 1

I don't know a call xxxx(...) way but since the file paths are trees, I would have thought a tree traversal algorithm would be as elegant as it gets...

There is stuff here in this question.

Answer 2

You can insert all paths into a Trie, and see what suffixes remain.

A bit more general is using an edit distance, and retracing the steps for the minimal edit distance.

Both seem more elegant to me. However, what's wrong with subtracting the strings in the first place?

Answer 3

Assuming you're not worried about things like /home/benjamin/test/c/.., then this becomes a simple substring matching exercise.

The laziest way would be to use something like std::string::find. Alternatively, a little while loop that iterates over both strings until it reaches the end of one, or finds a character difference.

Answer 4

I would try to use std::mismatch (documentation)

template <class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2 );

Return first position where two ranges differ

Compares the elements in the range [first1,last1) against those in the range beginning at first2 sequentially, and returns where the first mismatch happens.

Some code:

string
mismatch_string( string const & a, string const & b ) {

    string::const_iterator longBegin, longEnd, shortBegin;

    if( a.length() >= b.length() ) {
        longBegin = a.begin();
        longEnd = a.end();
        shortBegin = b.begin();
    }
    else {
        longBegin = b.begin();
        longEnd = b.end();
        shortBegin = a.begin();
    }

    pair< string::const_iterator, string::const_iterator > mismatch_pair = 
        mismatch( longBegin, longEnd, shortBegin );

    return string(  mismatch_pair.first, longEnd );
}

A full example with output is uploaded at codepad.

Answer 5

You can do it with a simple regular expression:

return($1) if longer =~ /^#{shorter}(.*)$/

Here is a complete example in Ruby. You can test it out in command-line and start using it or this code can give you an idea how to write the regexp in C++.