Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
[pal] Remove LinkedList and HashTable
This commit replace pal's use of it's own custom linked lists
and hash tables by Qt's QLinkedList and QHash classes. All use
of char arrays have also been replaced by QStrings.

Testing reveals no speed improvements by the changes, but the
changes bring pal more into line with QGIS core and make the
code much more readable.
  • Loading branch information
nyalldawson committed Jul 6, 2015
1 parent 217e9e7 commit a360422
Show file tree
Hide file tree
Showing 21 changed files with 283 additions and 924 deletions.
2 changes: 0 additions & 2 deletions src/core/CMakeLists.txt
Expand Up @@ -249,8 +249,6 @@ SET(QGIS_CORE_SRCS
pal/priorityqueue.cpp
pal/problem.cpp
pal/util.cpp
pal/linkedlist.hpp
pal/hashtable.hpp
pal/rtree.hpp

raster/qgscliptominmaxenhancement.cpp
Expand Down
86 changes: 33 additions & 53 deletions src/core/pal/feature.cpp
Expand Up @@ -34,15 +34,14 @@
#include <iostream>
#endif

#include <qglobal.h>
#include <QLinkedList>

#include <cmath>
#include <cstring>
#include <cfloat>

#include "pal.h"
#include "layer.h"
#include "linkedlist.hpp"
#include "feature.h"
#include "geomfunction.h"
#include "labelposition.h"
Expand All @@ -55,13 +54,14 @@

namespace pal
{
Feature::Feature( Layer* l, const char* geom_id, PalGeometry* userG, double lx, double ly )
Feature::Feature( Layer* l, const QString &geom_id, PalGeometry* userG, double lx, double ly )
: layer( l )
, userGeom( userG )
, label_x( lx )
, label_y( ly )
, distlabel( 0 )
, labelInfo( NULL )
, uid( geom_id )
, fixedPos( false )
, fixedPosX( 0.0 )
, fixedPosY( 0.0 )
Expand All @@ -77,14 +77,11 @@ namespace pal
, alwaysShow( false )
{
assert( finite( lx ) && finite( ly ) );

uid = new char[strlen( geom_id ) +1];
strcpy( uid, geom_id );
}

Feature::~Feature()
{
delete[] uid;

}

////////////
Expand Down Expand Up @@ -260,7 +257,7 @@ namespace pal
}


const char * FeaturePart::getUID()
QString FeaturePart::getUID() const
{
return f->uid;
}
Expand Down Expand Up @@ -573,11 +570,7 @@ namespace pal
if ( flags == 0 )
flags = FLAG_ON_LINE; // default flag

//LinkedList<PointSet*> *shapes_final;

//shapes_final = new LinkedList<PointSet*>(ptrPSetCompare);

LinkedList<LabelPosition*> *positions = new LinkedList<LabelPosition*> ( ptrLPosCompare );
QLinkedList<LabelPosition*> positions;

int nbPoints;
double *x;
Expand Down Expand Up @@ -691,16 +684,15 @@ namespace pal
bool belowLine = ( !reversed && ( flags & FLAG_BELOW_LINE ) ) || ( reversed && ( flags & FLAG_ABOVE_LINE ) );

if ( aboveLine )
positions->push_back( new LabelPosition( i, bx + cos( beta ) *distlabel, by + sin( beta ) *distlabel, xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
positions.append( new LabelPosition( i, bx + cos( beta ) *distlabel, by + sin( beta ) *distlabel, xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
if ( belowLine )
positions->push_back( new LabelPosition( i, bx - cos( beta ) *( distlabel + yrm ), by - sin( beta ) *( distlabel + yrm ), xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
positions.append( new LabelPosition( i, bx - cos( beta ) *( distlabel + yrm ), by - sin( beta ) *( distlabel + yrm ), xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
if ( flags & FLAG_ON_LINE )
positions->push_back( new LabelPosition( i, bx - yrm*cos( beta ) / 2, by - yrm*sin( beta ) / 2, xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
positions.append( new LabelPosition( i, bx - yrm*cos( beta ) / 2, by - yrm*sin( beta ) / 2, xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
}
else if ( f->layer->arrangement == P_HORIZ )
{
positions->push_back( new LabelPosition( i, bx - xrm / 2, by - yrm / 2, xrm, yrm, 0, cost, this ) ); // Line
//positions->push_back( new LabelPosition(i, bx -yrm/2, by - yrm*sin(beta)/2, xrm, yrm, alpha, cost, this, line)); // Line
positions.append( new LabelPosition( i, bx - xrm / 2, by - yrm / 2, xrm, yrm, 0, cost, this ) ); // Line
}
else
{
Expand All @@ -720,17 +712,15 @@ namespace pal
delete[] d;
delete[] ad;

int nbp = positions->size();
int nbp = positions.size();
*lPos = new LabelPosition *[nbp];
i = 0;
while ( positions->size() > 0 )
while ( positions.size() > 0 )
{
( *lPos )[i] = positions->pop_front();
( *lPos )[i] = positions.takeFirst();
i++;
}

delete positions;

return nbp;
}

Expand Down Expand Up @@ -967,7 +957,7 @@ namespace pal
return 0;
}

LinkedList<LabelPosition*> *positions = new LinkedList<LabelPosition*> ( ptrLPosCompare );
QLinkedList<LabelPosition*> positions;
double delta = max( f->labelInfo->label_height, total_distance / 10.0 );

unsigned long flags = f->layer->getArrangementFlags();
Expand Down Expand Up @@ -1017,25 +1007,24 @@ namespace pal
double angle_avg = atan2( sin_avg / f->labelInfo->char_num, cos_avg / f->labelInfo->char_num );
// displacement
if ( flags & FLAG_ABOVE_LINE )
positions->push_back( _createCurvedCandidate( slp, angle_avg, f->distlabel ) );
positions.append( _createCurvedCandidate( slp, angle_avg, f->distlabel ) );
if ( flags & FLAG_ON_LINE )
positions->push_back( _createCurvedCandidate( slp, angle_avg, -f->labelInfo->label_height / 2 ) );
positions.append( _createCurvedCandidate( slp, angle_avg, -f->labelInfo->label_height / 2 ) );
if ( flags & FLAG_BELOW_LINE )
positions->push_back( _createCurvedCandidate( slp, angle_avg, -f->labelInfo->label_height - f->distlabel ) );
positions.append( _createCurvedCandidate( slp, angle_avg, -f->labelInfo->label_height - f->distlabel ) );

// delete original candidate
delete slp;
}
}


int nbp = positions->size();
int nbp = positions.size();
( *lPos ) = new LabelPosition*[nbp];
for ( int i = 0; i < nbp; i++ )
{
( *lPos )[i] = positions->pop_front();
( *lPos )[i] = positions.takeFirst();
}
delete positions;
delete[] path_distances;

return nbp;
Expand Down Expand Up @@ -1081,28 +1070,20 @@ namespace pal

//print();

//LinkedList<PointSet*> *shapes_toCut;
LinkedList<PointSet*> *shapes_toProcess;
LinkedList<PointSet*> *shapes_final;

//shapes_toCut = new LinkedList<PointSet*>(ptrPSetCompare);
shapes_toProcess = new LinkedList<PointSet*> ( ptrPSetCompare );
shapes_final = new LinkedList<PointSet*> ( ptrPSetCompare );
QLinkedList<PointSet*> shapes_toProcess;
QLinkedList<PointSet*> shapes_final;

mapShape->parent = NULL;

shapes_toProcess->push_back( mapShape );
shapes_toProcess.append( mapShape );

splitPolygons( shapes_toProcess, shapes_final, xrm, yrm, f->uid );


delete shapes_toProcess;

int nbp;

if ( shapes_final->size() > 0 )
if ( shapes_final.size() > 0 )
{
LinkedList<LabelPosition*> *positions = new LinkedList<LabelPosition*> ( ptrLPosCompare );
QLinkedList<LabelPosition*> positions;

int id = 0; // ids for candidates
double dlx, dly; // delta from label center and bottom-left corner
Expand All @@ -1114,13 +1095,13 @@ namespace pal
double beta;
double diago = sqrt( xrm * xrm / 4.0 + yrm * yrm / 4 );
double rx, ry;
CHullBox **boxes = new CHullBox*[shapes_final->size()];
CHullBox **boxes = new CHullBox*[shapes_final.size()];
j = 0;

// Compute bounding box foreach finalShape
while ( shapes_final->size() > 0 )
while ( shapes_final.size() > 0 )
{
PointSet *shape = shapes_final->pop_front();
PointSet *shape = shapes_final.takeFirst();
boxes[j] = shape->compute_chull_bbox();

if ( shape->parent )
Expand Down Expand Up @@ -1248,13 +1229,13 @@ namespace pal
if ( isPointInPolygon( mapShape->nbPoints, mapShape->x, mapShape->y, rx, ry ) )
{
// cost is set to minimal value, evaluated later
positions->push_back( new LabelPosition( id++, rx - dlx, ry - dly, xrm, yrm, alpha, 0.0001, this ) ); // Polygon
positions.append( new LabelPosition( id++, rx - dlx, ry - dly, xrm, yrm, alpha, 0.0001, this ) ); // Polygon
}
}
}
} // forall box

nbp = positions->size();
nbp = positions.size();
if ( nbp == 0 )
{
dx /= 2;
Expand All @@ -1264,12 +1245,12 @@ namespace pal
}
while ( nbp == 0 && num_try < max_try );

nbp = positions->size();
nbp = positions.size();

( *lPos ) = new LabelPosition*[nbp];
for ( i = 0; i < nbp; i++ )
{
( *lPos )[i] = positions->pop_front();
( *lPos )[i] = positions.takeFirst();
}

for ( bbid = 0; bbid < j; bbid++ )
Expand All @@ -1278,21 +1259,19 @@ namespace pal
}

delete[] boxes;
delete positions;
}
else
{
nbp = 0;
}

delete shapes_final;

#ifdef _DEBUG_FULL_
std::cout << "NbLabelPosition: " << nbp << std::endl;
#endif
return nbp;
}

#if 0
void FeaturePart::print()
{
int i, j;
Expand All @@ -1315,6 +1294,7 @@ namespace pal

std::cout << std::endl;
}
#endif

int FeaturePart::setPosition( double scale, LabelPosition ***lPos,
double bbox_min[2], double bbox_max[2],
Expand Down
10 changes: 6 additions & 4 deletions src/core/pal/feature.h
Expand Up @@ -33,6 +33,7 @@
#include <iostream>
#include <fstream>
#include <cmath>
#include <QString>

#include <geos_c.h>

Expand Down Expand Up @@ -79,7 +80,7 @@ namespace pal
friend class FeaturePart;

public:
Feature( Layer* l, const char* geom_id, PalGeometry* userG, double lx, double ly );
Feature( Layer* l, const QString& geom_id, PalGeometry* userG, double lx, double ly );
~Feature();

void setLabelInfo( LabelInfo* info ) { labelInfo = info; }
Expand All @@ -103,7 +104,7 @@ namespace pal
double distlabel;
LabelInfo* labelInfo; // optional

char *uid;
QString uid;

bool fixedPos; //true in case of fixed position (only 1 candidate position with cost 0)
double fixedPosX;
Expand Down Expand Up @@ -231,15 +232,16 @@ namespace pal
* \brief get the unique id of the feature
* \return the feature unique identifier
*/
const char *getUID();
QString getUID() const;


#if 0
/**
* \brief Print feature information
* Print feature unique id, geometry type, points, and holes on screen
*/
void print();

#endif

PalGeometry* getUserGeometry() { return f->userGeom; }

Expand Down

0 comments on commit a360422

Please sign in to comment.