CODEWITHSUNDEEP
c++qt
ldr
ldr

Reputation: 211

Sort relative paths

My problem is pretty simple, but i can't think of an elegant solution.
In my application a bunch of relative paths are collected from user input (they don't really exist in the filesystem).
As an example:

Those are gathered in a QList (which contains pointers to instances of a class that have the paths as a QString member), but the container doesn't really matter to me.
The desired result is having the list in an ordered form, directories over files (as we are used from most file managers), basically like you would tree a real filesystem.

Obviously a normal string based sorting would not work, but what is the most elegant / easiest way to sort a list like this?

Upvotes: 2

Views: 497

Answers (2)

mateuszlewko
mateuszlewko

Reputation: 1129

I would write a custom comparator function for a builtin sort. Something like this may work:

auto cmp = [](const string& lhs, const string& rhs) {
    int len = min(lhs.size(), rhs.size());
    for (int i = 0; i < len; i++) {
        if (lhs[i] = rhs[i]) continue;

        // check if there is a '/' starting from position i in both paths
        // put directory first (if only one is a directory)
        // or return lhs[i] < rhs[i]
};

It should be fairly easy to finish this code, and then

sort(begin(paths), end(paths), cmp);

Note that I'm using c++11

Upvotes: 1

Sam Varshavchik
Sam Varshavchik

Reputation: 118350

Take a step back, and take a moment to summarize your desired sorting criteria, in plain English:

  1. Directories come first, files come second.

  2. Directories are sorted alphabetically, and files are sorted alphabetically.

Now, once your logical is reduced to this kind of simplistic, straightforward definition, simply translate this logic directly into C++ code.

First, translate each string into a single value, 0 or 1, that represents whether the string has a pathname component, or not.

Sort on that. Then if both strings' values are equivalent, sort on the strings themselves, as usual. Simple:

std::sort(container.begin(),
          container.end(),
          []
          (const QString &a,
           const QString &b)
          {
             // Compute whether a or b is a subdirectory, representing
             // each as:
             //
             // 0: directory
             // 1: file

             int a_hier=a.contains('/') ? 0:1;
             int b_hier=b.contains('/') ? 0:1;

             if (a_hier != b_hier)
                  return a_hier < b_hier;

             return a < b;
         });

This is you basic, initial approach. If necessary, this can be tweaked to sort the pathnames with directories slightly differently (since the / component in the pathname participates in the relative sorting order, which you may or may not want, this was unclear in your question).

Upvotes: 1

Related Questions