[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-commits
Subject:    Re: KDE/kdebase/apps/lib/konq
From:       David Faure <faure () kde ! org>
Date:       2008-08-13 7:50:33
Message-ID: 200808130950.36042.faure () kde ! org
[Download RAW message or body]

On Wednesday 13 August 2008, Rafael Fernández López wrote:
> +     * For example, for a list of "/home/foo/a", "/home/foo/a/a.txt", \
> "/home/foo/a/a/a.txt", "/home/foo/a/b/b.txt", +     * "home/foo/b/b.txt", this \
> method will return the list "/home/foo/a", "/home/foo/b/b.txt". +KUrl::List \
> KonqMimeData::simplifiedUrlList( const KUrl::List &urls ) +{
> +    KUrl::List ret( urls );
> +    KUrl::List::const_iterator it = urls.begin();
> +    while ( it != urls.end() ) {
> +        KUrl::List::const_iterator it2 = urls.begin();
> +        while ( it2 != urls.end() ) {
> +            if ( it != it2 && it->isParentOf( *it2 ) ) {
> +                ret.removeAll( *it2 );
> +            }
> +            ++it2;
> +        }
> +        ++it;
> +    }
> +    return ret;
> +}

This is O(n^2) though, I'm wondering if we couldn't do it faster.
We know that a parent will always be before its children, right?
So we could start the inner loop at the index of the outer loop plus one,
(good thing QList allows us to use indexes for iterating too).
Then it'll be like 4+3+2+1 instead of 5*5 (number of times the inner code is run).

In fact we could even do that better; once we reach a url that is
NOT a child of (*it), we can stop, right? In your example it wouldn't
change much, but in general it would help too.
This would simply mean " } else { break; } " I think.

-- 
David Faure, faure@kde.org, sponsored by Trolltech to work on KDE,
Konqueror (http://www.konqueror.org), and KOffice (http://www.koffice.org).


[prev in list] [next in list] [prev in thread] [next in thread]