Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Much faster QgsTemporalRange::mergeRanges
  • Loading branch information
nyalldawson committed Mar 26, 2021
1 parent c262794 commit 15420f2
Showing 1 changed file with 20 additions and 22 deletions.
42 changes: 20 additions & 22 deletions src/core/qgsrange.h
Expand Up @@ -616,32 +616,30 @@ class QgsTemporalRange
*/
static QList< QgsTemporalRange<T> > mergeRanges( const QList< QgsTemporalRange<T> > &ranges )
{
QList< QgsTemporalRange<T > > res;

QList< QgsTemporalRange<T> > queue = ranges;
while ( !queue.empty() )
if ( ranges.empty() )
return {};

QList< QgsTemporalRange<T > > sortedRanges = ranges;
std::sort( sortedRanges.begin(), sortedRanges.end(), []( const QgsTemporalRange< T > &a, const QgsTemporalRange< T > &b ) -> bool { return a.begin() < b.begin(); } );
QList< QgsTemporalRange<T>> res;
res.reserve( sortedRanges.size() );

QgsTemporalRange<T> prevRange;
auto it = sortedRanges.constBegin();
prevRange = *it++;
for ( ; it != sortedRanges.constEnd(); ++it )
{
QgsTemporalRange<T> range = queue.back();
queue.pop_back();

bool extended = false;
for ( int i = 0; i < res.count(); ++i )
if ( prevRange.overlaps( *it ) )
{
if ( res[i].overlaps( range ) )
{
QgsTemporalRange< T > other = res.takeAt( i );
other.extend( range );
queue.push_back( other );
extended = true;
break;
}
prevRange.extend( *it );
}
else
{
res << prevRange;
prevRange = *it;
}

if ( !extended )
res.push_back( range );
}

std::sort( res.begin(), res.end(), []( const QgsTemporalRange< T > &a, const QgsTemporalRange< T > &b ) -> bool { return a.begin() < b.begin(); } );
res << prevRange;
return res;
}
#endif
Expand Down

0 comments on commit 15420f2

Please sign in to comment.