QDirIterator internals?

[zaphod.b]

Hi all,

I have a thin wrapper around QDirIterator. This wrapper should be "filterable" by an internal regular expression.

Out-of-the-box QDirIterator supports globbing but not regexes. Also, from the doc

QDirIterator is uni-directional (i.e., you cannot iterate directories in reverse order) and does not allow random access

so I cannot simply set a savepoint, then iterate+skip, and finally revert to the savepoint.
Finally, QDirIterator doesn't provide a copy ctor or clone either.

Question:
Is a QDirIterator's order guaranteed? In other words: Is it safe to simulate a copy ctor by creating a new QDirIterator from the original one's path(), then advance it until its filePath() matches the original one's?

Or is there another solution to my problem? Thx for your consideration.


PS: I'm on 5.1. Mind that the QTCLASS link above links to 4.8, though on first sight there are no differences.

[anda_skoa]

I haven't had a look at the code but my understanding is that it uses the platform's directory traversing API.

So creating a new QDirIterator will call into that API again. If anything has changed the new iterator might have a different iteration result sequence than the first one.

However I don't see why you would need to go back for your use case of filtering using regular expression.
Your iterator will call into the ecapsulated iterator untill your criteria is met and then return this data until it is moved forward, no?

Cheers,
_

[zaphod.b]

Hi and thx,

I haven't had a look at the code but my understanding is that it uses the platform's directory traversing API.

I had a short glimpse but refrained from getting into the code for complexity.

So creating a new QDirIterator will call into that API again. If anything has changed the new iterator might have a different iteration result sequence than the first one.

If your understanding is correct, then these changes would apply to the "original" iterator as well, wouldn't they? In other words: Unbuffered iterators are always invalidated if the underlying collection changes, aren't they?
Edit:
As long as the order of paths QDirIterator returns is invariant, proceeding to the same filePath() should "sync" the iterators. Of course I'd miss changes up to this path, but the same would be true for the original iterator. Or so I think

However I don't see why you would need to go back for your use case of filtering using regular expression.
Your iterator will call into the ecapsulated iterator untill your criteria is met and then return this data until it is moved forward, no?

The encapsulated iterator doesn't support regexes. I'd have to do this myself and query hasNext() multiple times to skip unmatched iterator states. This would require to call next() in turns, thus altering the iterator's state, which hasNext() shouldn't do.

Do I overlook anything?

[anda_skoa]

The encapsulated iterator doesn't support regexes. I'd have to do this myself and query hasNext() multiple times to skip unmatched iterator states. This would require to call next() in turns, thus altering the iterator's state, which hasNext() shouldn't do.

Do I overlook anything?

Maybe I misunderstood what you are trying to do then. My interpretation was that you wanted to iterate over a directory and only get files which match a certain regular expression.
Bascially iterating over a "view" on the directory based on the regex.

Cheers,
_

[zaphod.b]

Maybe I misunderstood what you are trying to do then. My interpretation was that you wanted to iterate over a directory and only get files which match a certain regular expression.
Bascially iterating over a "view" on the directory based on the regex.

You've got me right. I still don't see how this is trivial however...

Could you please elaborate on how you would solve this task? In particular I don't see how to implement hasNext() such that it skips items returned by QDirIterator::hasNext() that are unmatched by the regex? Unless there's a way to restore QDirIterator's state somehow, that is...

Thx for taking the trouble!

[anda_skoa]

Basically you have the next match already retrieved from the QDirIterator at all times
Pseudo code:

class RegExIterator
{
public:
    RegExIterator(Dir, RegEx)
 
    bool hasNext();
    QFileInfo next();
 
private:
    RegEx regex;
    QDirIterator dirIt;
    QFileInfo nextMatch;
 
    void findNext(); 
};

class RegExIterator
{
public:
    RegExIterator(Dir, RegEx)

    bool hasNext();
    QFileInfo next();

private:
    RegEx regex;
    QDirIterator dirIt;
    QFileInfo nextMatch;

    void findNext(); 
};

To copy to clipboard, switch view to plain text mode 

RegExIterator(...)
// store params in members
// init QDirIterator member
{
    findNext():
}
 
bool hasNext()
{
    return nextMatch != QFileInfo();
}
 
QFileInfo next()
{
    QFileInfo result = nextMatch;
 
    findNext();
 
    return result;
}
 
void findNext()
{
    // iterate over dirIt until match found
    // store in nextMatch
}

RegExIterator(...)
// store params in members
// init QDirIterator member
{
    findNext():
}

bool hasNext()
{
    return nextMatch != QFileInfo();
}

QFileInfo next()
{
    QFileInfo result = nextMatch;

    findNext();

    return result;
}

void findNext()
{
    // iterate over dirIt until match found
    // store in nextMatch
}

To copy to clipboard, switch view to plain text mode 

Cheers,
_

[zaphod.b]

Thx, but sorry, I don't think this solves the problem.

Basically you have the next match already retrieved from the QDirIterator at all times

Is that so? I think not.

Edit:
Ah, I think I can follow your train of thoughts at last!
Do you say you are ok with hasNext() altering dirIt's state, and have next() only return this altered state rather than advance dirIt itself?
This will break if next() is called without hasNext(). I'd not want to do this.

Unfortunately your pseudo code spares the relevant part:

void findNext()
{
    // iterate over dirIt until match found
    // store in nextMatch
}

void findNext()
{
    // iterate over dirIt until match found
    // store in nextMatch
}

To copy to clipboard, switch view to plain text mode 

How exactly do you do this?
"Iterate over dirIt" generally implies calling QDirIterator::hasNext() and QDirIterator::next() (for the regex match) in turns, the latter changing the iterator's state.
"Until match found" generally implies to run these cycles more than once unless the very first item returned by QDirIterator matches.

Also in your pseudo code hasNext() would have to call findNext(), too.

Let me try to clarify.
The general pseudo code for the caller using your syntax is

RegExIterator rxIt(dir, rx);
while ( rxIt.hasNext() ) {
    QFileInfo fi = rxIt.next();
    //do something with fi
}

RegExIterator rxIt(dir, rx);
while ( rxIt.hasNext() ) {
    QFileInfo fi = rxIt.next();
    //do something with fi
}

To copy to clipboard, switch view to plain text mode 

Now consider this directory structure

dir/
    a
    x
    aa
    y

dir/
    a
    x
    aa
    y

To copy to clipboard, switch view to plain text mode 

and assume a regex of "a+". The expexted matches are {a, aa}, while {x, y} shall be skipped by the iterator.
Further assume the iterator's position (= state) to be aa. Expected result of hasNext() is false, and next() shall return an invalid result.
The hasNext() algorithm steps would be (loop serialized for clarity)

call dirIt.hasNext()             //true
call dirIt.next()                //necessary to (1)match regex, (2)prepare for 2nd hasNext(). This alters dirIt's position to y!
call dirIt.hasNext() again       //false
revert dirIt position to aa      //hasNext() must not alter state!

call dirIt.hasNext()             //true
call dirIt.next()                //necessary to (1)match regex, (2)prepare for 2nd hasNext(). This alters dirIt's position to y!
call dirIt.hasNext() again       //false
revert dirIt position to aa      //hasNext() must not alter state!

To copy to clipboard, switch view to plain text mode 

Now, given QDirIterator's limitations I listed in this thread's first post, if I could perform the above algorithm on a dirIt copy, it would not change the original dirIt's state and I'd be safe.
In the above example, inside hasNext() I'd create another QDirIterator based on dir/, advance it to aa, then perform the algorithm on the "copy". Obviously this would only work if dirIt and copyDirIt return the items in the same order.

[anda_skoa]

Do you say you are ok with hasNext() altering dirIt's state, and have next() only return this altered state rather than advance dirIt itself?
This will break if next() is called without hasNext(). I'd not want to do this.

No. Only next() alters the state, hasNext() does not. It only returns the value of a comparison, it does not call findNext().

Unfortunately your pseudo code spares the relevant part:

How exactly do you do this?
"Iterate over dirIt" generally implies calling QDirIterator::hasNext() and QDirIterator::next() (for the regex match) in turns, the latter changing the iterator's state.
"Until match found" generally implies to run these cycles more than once unless the very first item returned by QDirIterator matches.

Exactly.

void findNext()
{
    while ( dirIt.hasNext() ) {
        QString file = dirIt.next();
        if ( regexp.match( file ) ) {
            nextMatch = dirIt.fileInfo();
            return;
        }
    }
 
    nextMatch = QFileInfo();
}

void findNext()
{
    while ( dirIt.hasNext() ) {
        QString file = dirIt.next();
        if ( regexp.match( file ) ) {
            nextMatch = dirIt.fileInfo();
            return;
        }
    }

    nextMatch = QFileInfo();
}

To copy to clipboard, switch view to plain text mode 

You could also just keep the string instead of the file info.

Also in your pseudo code hasNext() would have to call findNext(), too.

No, only next() and the constructor do.

Let me try to clarify.
The general pseudo code for the caller using your syntax is

RegExIterator rxIt(dir, rx);
while ( rxIt.hasNext() ) {
    QFileInfo fi = rxIt.next();
    //do something with fi
}

RegExIterator rxIt(dir, rx);
while ( rxIt.hasNext() ) {
    QFileInfo fi = rxIt.next();
    //do something with fi
}

To copy to clipboard, switch view to plain text mode 

Now consider this directory structure

dir/
    a
    x
    aa
    y

dir/
    a
    x
    aa
    y

To copy to clipboard, switch view to plain text mode 

and assume a regex of "a+". The expexted matches are {a, aa}, while {x, y} shall be skipped by the iterator.

The call sequence for that would be like this:

RegExItterator constructor
    QDirIterator constructor
    findNext
        dirIt.hasNext -> true
        dirIt.next -> "a"
        nextMatch -> "a"
 
RegExIterator.hasNext
    nextMatch valid -> true
 
RegExIterator.next
    result = "a"
    findNext
        dirIt.hasNext -> true
        dirIt.next -> "x" (no match, loop continues)
        dirIt.hasNext -> true
        dirIt.next -> "aa"
        nextMatch -> "aa"
    return result
 
RegExIterator.hasNext
    nextMatch valid -> true
 
RegExIterator.next
    result = "aa"
    findNext
        dirIt.hasNext -> true
        dirIt.next -> "y" (no match, loop continues)
        dirIt.hasNext -> false
        nextMatch -> reset/clear
    return result
 
RegExIterator.hasNext
    nextMatch invalid -> false

RegExItterator constructor
    QDirIterator constructor
    findNext
        dirIt.hasNext -> true
        dirIt.next -> "a"
        nextMatch -> "a"

RegExIterator.hasNext
    nextMatch valid -> true

RegExIterator.next
    result = "a"
    findNext
        dirIt.hasNext -> true
        dirIt.next -> "x" (no match, loop continues)
        dirIt.hasNext -> true
        dirIt.next -> "aa"
        nextMatch -> "aa"
    return result

RegExIterator.hasNext
    nextMatch valid -> true

RegExIterator.next
    result = "aa"
    findNext
        dirIt.hasNext -> true
        dirIt.next -> "y" (no match, loop continues)
        dirIt.hasNext -> false
        nextMatch -> reset/clear
    return result

RegExIterator.hasNext
    nextMatch invalid -> false

To copy to clipboard, switch view to plain text mode 

Cheers,
_

[zaphod.b]

Oh my... This is trivial indeed.
Sometimes you just don't see the wood for the trees. I was afraid that was the case here, and it was...

only next() and the constructor do [ed.: look ahead].

Don't know anymore, but to look ahead in the ctor before any hasNext() or next() may have been my blind spot.

Thank you so much for bearing with me.

--
I'd like to change the thread title from "QDirIterator internals?" to "[SOLVED] QDirIterator & regex filter" but can't edit the first post anymore. Admin?