void StackedTileLoader::updateTile( TileId const &tileId, QImage const &tileImage )
{
    Q_ASSERT( !tileImage.isNull() );

    d->detectMaxTileLevel();

    const TileId stackedTileId( 0, tileId.zoomLevel(), tileId.x(), tileId.y() );

    StackedTile * displayedTile = d->m_tilesOnDisplay.take( stackedTileId );
    if ( displayedTile ) {
        Q_ASSERT( !d->m_tileCache.contains( stackedTileId ) );

        QVector<QSharedPointer<TextureTile> > tiles = displayedTile->tiles();
        delete displayedTile;
        displayedTile = 0;

        for ( int i = 0; i < tiles.count(); ++ i) {
            if ( tiles[i]->id() == tileId ) {
                const Blending *blending = tiles[i]->blending();
                tiles[i] = QSharedPointer<TextureTile>( new TextureTile( tileId, tileImage, blending ) );
            }
        }

        const QImage resultImage = d->m_layerDecorator.merge( stackedTileId, tiles );
        displayedTile = new StackedTile( stackedTileId, resultImage, tiles );
        d->m_tilesOnDisplay.insert( stackedTileId, displayedTile );

        emit tileUpdateAvailable( stackedTileId );
    } else {
        d->m_tileCache.remove( stackedTileId );
    }
}

void GeoGraphicsScene::removeItem( GeoGraphicsItem* item )
{
    int zoomLevel;
    qreal north, south, east, west;
    item->latLonAltBox().boundaries( north, south, east, west );
    for(zoomLevel = s_tileZoomLevel; zoomLevel >= 0; zoomLevel--)
    {
        if( d->coordToTileId( GeoDataCoordinates(west, north, 0), zoomLevel ) == 
            d->coordToTileId( GeoDataCoordinates(east, south, 0), zoomLevel ) )
            break;
    }
    int tnorth, tsouth, teast, twest;
    TileId key;
    
    key = d->coordToTileId( GeoDataCoordinates(west, north, 0), zoomLevel );
    twest = key.x();
    tnorth = key.y();

    key = d->coordToTileId( GeoDataCoordinates(east, south, 0), zoomLevel );
    teast = key.x();
    tsouth = key.y();
        
    for( int i = twest; i <= teast; i++ )
    {
        for( int j = tsouth; j <= tnorth; j++ )
        {
            QList< GeoGraphicsItem* >& tileList = d->m_items[TileId( "", zoomLevel, i, j )]; 
            tileList.removeOne( item );
        }
    }
}

void StackedTileLoader::downloadTile( TileId const & stackedTileId )
{
    QVector<GeoSceneTexture const *> const textureLayers = d->findRelevantTextureLayers( stackedTileId );
    QVector<GeoSceneTexture const *>::const_iterator pos = textureLayers.constBegin();
    QVector<GeoSceneTexture const *>::const_iterator const end = textureLayers.constEnd();
    for (; pos != end; ++pos ) {
        GeoSceneTexture const * const textureLayer = *pos;
        TileId const tileId( textureLayer->sourceDir(), stackedTileId.zoomLevel(),
                             stackedTileId.x(), stackedTileId.y() );
        d->m_tileLoader->downloadTile( tileId );
    }
}

void TileLoader::triggerDownload( GeoSceneTileDataset const *tileData, TileId const &id, DownloadUsage const usage )
{
    if (id.zoomLevel() > 0 && id.zoomLevel() != qBound(tileData->minimumTileLevel(), id.zoomLevel(), tileData->maximumTileLevel())) {
        // Download only level 0 tiles and tiles between minimum and maximum tile level
        return;
    }

    QUrl const sourceUrl = tileData->downloadUrl( id );
    QString const destFileName = tileData->relativeTileFileName( id );
    QString const idStr = QString( "%1:%2:%3:%4:%5" ).arg( tileData->nodeType()).arg( tileData->sourceDir() ).arg( id.zoomLevel() ).arg( id.x() ).arg( id.y() );
    emit downloadTile( sourceUrl, destFileName, idStr, usage );
}

QUrl OsmServerLayout::downloadUrl( const QUrl &prototypeUrl, const TileId &id ) const
{
    const QString suffix = m_textureLayer->fileFormat().toLower();
    const QString path = QString( "%1/%2/%3.%4" ).arg( id.zoomLevel() )
                                                 .arg( id.x() )
                                                 .arg( id.y() )
                                                 .arg( suffix );

    QUrl url = prototypeUrl;
    url.setPath( url.path() + path );

    return url;
}

void TileIdTest::testFromCoordinates()
{
    QFETCH( qreal, lon );
    QFETCH( qreal, lat );
    QFETCH( int, zoom);
    QFETCH( int, x);
    QFETCH( int, y);

    const TileId tile = TileId::fromCoordinates(GeoDataCoordinates( lon , lat, 0, GeoDataCoordinates::Degree), zoom );

    QCOMPARE( tile.x(), x );
    QCOMPARE( tile.y(), y );
}

QSet<TileId> PlacemarkLayout::visibleTiles( const ViewportParams *viewport )
{
    int zoomLevel = qLn( viewport->radius() *4 / 256 ) / qLn( 2.0 );

    /*
     * rely on m_placemarkCache to find the placemarks for the tiles which
     * matter. The top level tiles have the more popular placemarks,
     * the bottom level tiles have the smaller ones, and we only get the ones
     * matching our latLonAltBox.
     */

    qreal north, south, east, west;
    viewport->viewLatLonAltBox().boundaries(north, south, east, west);
    QSet<TileId> tileIdSet;
    QVector<QRectF> geoRects;
    if( west <= east ) {
        geoRects << QRectF(west, north, east - west, south - north);
    } else {
        geoRects << QRectF(west, north, M_PI - west, south - north);
        geoRects << QRectF(-M_PI, north, east + M_PI, south - north);
    }
    foreach( const QRectF &geoRect, geoRects ) {
        TileId key;
        QRect rect;

        key = TileId::fromCoordinates( GeoDataCoordinates(geoRect.left(), north, 0), zoomLevel);
        rect.setLeft( key.x() );
        rect.setTop( key.y() );

        key = TileId::fromCoordinates( GeoDataCoordinates(geoRect.right(), south, 0), zoomLevel);
        rect.setRight( key.x() );
        rect.setBottom( key.y() );

        TileCoordsPyramid pyramid(0, zoomLevel );
        pyramid.setBottomLevelCoords( rect );

        for ( int level = pyramid.topLevel(); level <= pyramid.bottomLevel(); ++level ) {
        QRect const coords = pyramid.coords( level );
        int x1, y1, x2, y2;
        coords.getCoords( &x1, &y1, &x2, &y2 );
            for ( int x = x1; x <= x2; ++x ) {
                for ( int y = y1; y <= y2; ++y ) {
                    TileId const tileId( 0, level, x, y );
                    tileIdSet.insert(tileId);
                }
            }
        }
    }

QImage TileLoader::scaledLowerLevelTile( const GeoSceneTextureTile * textureLayer, TileId const & id )
{
    mDebug() << Q_FUNC_INFO << id;

    for ( int level = qMax<int>( 0, id.zoomLevel() - 1 ); level >= 0; --level ) {
        int const deltaLevel = id.zoomLevel() - level;

        TileId const replacementTileId( id.mapThemeIdHash(), level,
                                        id.x() >> deltaLevel, id.y() >> deltaLevel );
        QString const fileName = tileFileName( textureLayer, replacementTileId );
        mDebug() << "TileLoader::scaledLowerLevelTile" << "trying" << fileName;
        QImage toScale = QFile::exists(fileName) ? QImage(fileName) : QImage();

        if ( level == 0 && toScale.isNull() ) {
            mDebug() << "No level zero tile installed in map theme dir. Falling back to a transparent image for now.";
            QSize tileSize = textureLayer->tileSize();
            Q_ASSERT( !tileSize.isEmpty() ); // assured by textureLayer
            toScale = QImage( tileSize, QImage::Format_ARGB32_Premultiplied );
            toScale.fill( qRgba( 0, 0, 0, 0 ) );
        }

        if ( !toScale.isNull() ) {
            // which rect to scale?
            int const restTileX = id.x() % ( 1 << deltaLevel );
            int const restTileY = id.y() % ( 1 << deltaLevel );
            int const partWidth = qMax(1, toScale.width() >> deltaLevel);
            int const partHeight = qMax(1, toScale.height() >> deltaLevel);
            int const startX = restTileX * partWidth;
            int const startY = restTileY * partHeight;
            mDebug() << "QImage::copy:" << startX << startY << partWidth << partHeight;
            QImage const part = toScale.copy( startX, startY, partWidth, partHeight );
            mDebug() << "QImage::scaled:" << toScale.size();
            return part.scaled( toScale.size() );
        }
    }

void StackedTileLoader::updateTile( TileId const &tileId, QImage const &tileImage )
{
    const TileId stackedTileId( 0, tileId.zoomLevel(), tileId.x(), tileId.y() );

    StackedTile * displayedTile = d->m_tilesOnDisplay.take( stackedTileId );
    if ( displayedTile ) {
        Q_ASSERT( !d->m_tileCache.contains( stackedTileId ) );

        StackedTile *const stackedTile = d->m_layerDecorator->updateTile( *displayedTile, tileId, tileImage );
        stackedTile->setUsed( true );
        d->m_tilesOnDisplay.insert( stackedTileId, stackedTile );

        delete displayedTile;
        displayedTile = 0;

        emit tileLoaded( stackedTileId );
    } else {
        d->m_tileCache.remove( stackedTileId );
    }
}

QString GeoSceneTileDataset::relativeTileFileName( const TileId &id ) const
{
    const QString suffix = fileFormat().toLower();

    QString relFileName;

    switch ( m_storageLayoutMode ) {
    default:
        mDebug() << Q_FUNC_INFO << "Invalid storage layout mode! Falling back to default.";
    case GeoSceneTileDataset::Marble:
        relFileName = QString( "%1/%2/%3/%3_%4.%5" )
            .arg( themeStr() )
            .arg( id.zoomLevel() )
            .arg( id.y(), tileDigits, 10, QChar('0') )
            .arg( id.x(), tileDigits, 10, QChar('0') )
            .arg( suffix );
        break;
    case GeoSceneTileDataset::OpenStreetMap:
        relFileName = QString( "%1/%2/%3/%4.%5" )
            .arg( themeStr() )
            .arg( id.zoomLevel() )
            .arg( id.x() )
            .arg( id.y() )
            .arg( suffix );
        break;
    case GeoSceneTileDataset::TileMapService:
        relFileName = QString( "%1/%2/%3/%4.%5" )
            .arg( themeStr() )
            .arg( id.zoomLevel() )
            .arg( id.x() )
            .arg( ( 1<<id.zoomLevel() ) - id.y() - 1 )  //Y coord in TMS runs from bottom to top
            .arg( suffix );
        break;
    }

    return relFileName;
}

QVector<GeoSceneTexture const *>
StackedTileLoaderPrivate::findRelevantTextureLayers( TileId const & stackedTileId ) const
{
    QVector<GeoSceneTexture const *> result;
    QVector<GeoSceneTexture const *>::const_iterator pos = m_textureLayers.constBegin();
    QVector<GeoSceneTexture const *>::const_iterator const end = m_textureLayers.constEnd();
    for (; pos != end; ++pos ) {
        GeoSceneTexture const * const candidate = dynamic_cast<GeoSceneTexture const *>( *pos );
        // check if layer is enabled. A layer is considered to be enabled if one of the
        // following conditions is true:
        // 1) it is the first layer
        // 2) there are no settings available (group "Texture Layers" not defined in DGML)
        // 3) the layer is configured and enabled in the settings
        // also check, if layer provides tiles for the current level
        if ( candidate
             && ( !candidate->hasMaximumTileLevel()
                  || stackedTileId.zoomLevel() <= candidate->maximumTileLevel() ))
            result.append( candidate );
    }
    return result;
}

void TileLoader::triggerDownload( GeoSceneTiled const *textureLayer, TileId const &id, DownloadUsage const usage )
{
    QUrl const sourceUrl = textureLayer->downloadUrl( id );
    QString const destFileName = textureLayer->relativeTileFileName( id );
    QString const idStr = QString( "%1:%2:%3:%4" ).arg( textureLayer->sourceDir() ).arg( id.zoomLevel() ).arg( id.x() ).arg( id.y() );
    emit downloadTile( sourceUrl, destFileName, idStr, usage );
}

void MergedLayerDecorator::paintTileId( QImage *tileImage, const TileId &id ) const
{
    QString filename = QString( "%1_%2.jpg" )
        .arg( id.x(), tileDigits, 10, QChar('0') )
        .arg( id.y(), tileDigits, 10, QChar('0') );

    QPainter painter( tileImage );

    QColor foreground;
    QColor background;

    if ( ( (qreal)(id.x())/2 == id.x()/2 && (qreal)(id.y())/2 == id.y()/2 ) 
         || ( (qreal)(id.x())/2 != id.x()/2 && (qreal)(id.y())/2 != id.y()/2 ) 
       )
    {
        foreground.setNamedColor( "#FFFFFF" );
        background.setNamedColor( "#000000" );
    }
    else {
        foreground.setNamedColor( "#000000" );
        background.setNamedColor( "#FFFFFF" );
    }

    int   strokeWidth = 10;
    QPen  testPen( foreground );
    testPen.setWidth( strokeWidth );
    testPen.setJoinStyle( Qt::MiterJoin );

    painter.setPen( testPen );
    painter.drawRect( strokeWidth / 2, strokeWidth / 2, 
                      tileImage->width()  - strokeWidth,
                      tileImage->height() - strokeWidth );
    QFont testFont( "Sans", 12 );
    QFontMetrics testFm( testFont );
    painter.setFont( testFont );

    QPen outlinepen( foreground );
    outlinepen.setWidthF( 6 );

    painter.setPen( outlinepen );
    painter.setBrush( background );

    QPainterPath   outlinepath;

    QPointF  baseline1( ( tileImage->width() - testFm.boundingRect(filename).width() ) / 2,
                        ( tileImage->height() * 0.25) );
    outlinepath.addText( baseline1, testFont, QString( "level: %1" ).arg(id.zoomLevel()) );

    QPointF  baseline2( ( tileImage->width() - testFm.boundingRect(filename).width() ) / 2,
                        tileImage->height() * 0.50 );
    outlinepath.addText( baseline2, testFont, filename );

    QPointF  baseline3( ( tileImage->width() - testFm.boundingRect(filename).width() ) / 2,
                        tileImage->height() * 0.75 );
    outlinepath.addText( baseline3, testFont, m_themeId );

    painter.drawPath( outlinepath );

    painter.setPen( Qt::NoPen );
    painter.drawPath( outlinepath );
}

const StackedTile* StackedTileLoader::loadTile( TileId const & stackedTileId )
{
    // check if the tile is in the hash
    d->m_cacheLock.lockForRead();
    StackedTile * stackedTile = d->m_tilesOnDisplay.value( stackedTileId, 0 );
    d->m_cacheLock.unlock();
    if ( stackedTile ) {
        stackedTile->setUsed( true );
        return stackedTile;
    }
    // here ends the performance critical section of this method

    d->m_cacheLock.lockForWrite();

    // has another thread loaded our tile due to a race condition?
    stackedTile = d->m_tilesOnDisplay.value( stackedTileId, 0 );
    if ( stackedTile ) {
        stackedTile->setUsed( true );
        d->m_cacheLock.unlock();
        return stackedTile;
    }

    mDebug() << "StackedTileLoader::loadTile" << stackedTileId.toString();

    // the tile was not in the hash so check if it is in the cache
    stackedTile = d->m_tileCache.take( stackedTileId );
    if ( stackedTile ) {
        stackedTile->setUsed( true );
        d->m_tilesOnDisplay[ stackedTileId ] = stackedTile;
        d->m_cacheLock.unlock();
        return stackedTile;
    }

    // tile (valid) has not been found in hash or cache, so load it from disk
    // and place it in the hash from where it will get transferred to the cache

    // mDebug() << "load Tile from Disk: " << stackedTileId.toString();

    QVector<QSharedPointer<TextureTile> > tiles;
    QVector<GeoSceneTexture const *> const textureLayers = d->findRelevantTextureLayers( stackedTileId );
    QVector<GeoSceneTexture const *>::const_iterator pos = textureLayers.constBegin();
    QVector<GeoSceneTexture const *>::const_iterator const end = textureLayers.constEnd();
    for (; pos != end; ++pos ) {
        GeoSceneTexture const * const textureLayer = *pos;
        TileId const tileId( textureLayer->sourceDir(), stackedTileId.zoomLevel(),
                             stackedTileId.x(), stackedTileId.y() );
        mDebug() << "StackedTileLoader::loadTile: tile" << textureLayer->sourceDir()
                 << tileId.toString() << textureLayer->tileSize();
        const QImage tileImage = d->m_tileLoader->loadTile( tileId, DownloadBrowse );
        const Blending *blending = d->m_blendingFactory.findBlending( textureLayer->blending() );
        if ( blending == 0 && !textureLayer->blending().isEmpty() ) {
            mDebug() << Q_FUNC_INFO << "could not find blending" << textureLayer->blending();
        }
        QSharedPointer<TextureTile> tile( new TextureTile( tileId, tileImage, blending ) );
        tiles.append( tile );
    }
    Q_ASSERT( !tiles.isEmpty() );

    const QImage resultImage = d->m_layerDecorator.merge( stackedTileId, tiles );
    stackedTile = new StackedTile( stackedTileId, resultImage, tiles );
    stackedTile->setUsed( true );

    d->m_tilesOnDisplay[ stackedTileId ] = stackedTile;
    d->m_cacheLock.unlock();
    return stackedTile;
}

void SunLightBlending::blend( QImage * const tileImage, Tile const * const top ) const
{
    if ( tileImage->depth() != 32 )
        return;

    // TODO add support for 8-bit maps?
    // add sun shading
    const TileId id = top->id();
    const qreal  global_width  = tileImage->width()
        * TileLoaderHelper::levelToColumn( m_levelZeroColumns, id.zoomLevel() );
    const qreal  global_height = tileImage->height()
        * TileLoaderHelper::levelToRow( m_levelZeroRows, id.zoomLevel() );
    const qreal lon_scale = 2*M_PI / global_width;
    const qreal lat_scale = -M_PI / global_height;
    const int tileHeight = tileImage->height();
    const int tileWidth = tileImage->width();

    // First we determine the supporting point interval for the interpolation.
    const int n = maxDivisor( 30, tileWidth );
    const int ipRight = n * (int)( tileWidth / n );

    const QImage *nighttile = top->image();

    for ( int cur_y = 0; cur_y < tileHeight; ++cur_y ) {
        const qreal lat = lat_scale * ( id.y() * tileHeight + cur_y ) - 0.5*M_PI;
        const qreal a = sin( ( lat+DEG2RAD * m_sunLocator->getLat() )/2.0 );
        const qreal c = cos(lat)*cos( -DEG2RAD * m_sunLocator->getLat() );

        QRgb* scanline  = (QRgb*)tileImage->scanLine( cur_y );
        const QRgb* nscanline = (QRgb*)nighttile->scanLine( cur_y );

        qreal lastShade = -10.0;

        int cur_x = 0;

        while ( cur_x < tileWidth ) {

            const bool interpolate = ( cur_x != 0 && cur_x < ipRight && cur_x + n < tileWidth );

            qreal shade = 0;

            if ( interpolate ) {
                const int check = cur_x + n;
                const qreal checklon   = lon_scale * ( id.x() * tileWidth + check );
                shade = m_sunLocator->shading( checklon, a, c );

                // if the shading didn't change across the interpolation
                // interval move on and don't change anything.
                if ( shade == lastShade && shade == 1.0 ) {
                    scanline += n;
                    nscanline += n;
                    cur_x += n;
                    continue;
                }
                if ( shade == lastShade && shade == 0.0 ) {
                    for ( int t = 0; t < n; ++t ) {
                        m_sunLocator->shadePixelComposite( *scanline, *nscanline, shade );
                        ++scanline;
                        ++nscanline;
                    }
                    cur_x += n;
                    continue;
                }
                for ( int t = 0; t < n ; ++t ) {
                    qreal lon   = lon_scale * ( id.x() * tileWidth + cur_x );
                    shade = m_sunLocator->shading( lon, a, c );
                    m_sunLocator->shadePixelComposite( *scanline, *nscanline, shade );
                    ++scanline;
                    ++nscanline;
                    ++cur_x;
                }
            }

            else {
                // Make sure we don't exceed the image memory
                if ( cur_x < tileWidth ) {
                    qreal lon   = lon_scale * ( id.x() * tileWidth + cur_x );
                    shade = m_sunLocator->shading( lon, a, c );
                    m_sunLocator->shadePixelComposite( *scanline, *nscanline, shade );
                    ++scanline;
                    ++nscanline;
                    ++cur_x;
                }
            }
            lastShade = shade;
        }
    }
}