Branch data Line data Source code
1 : : /*
2 : : * libpal - Automated Placement of Labels Library
3 : : *
4 : : * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5 : : * University of Applied Sciences, Western Switzerland
6 : : * http://www.hes-so.ch
7 : : *
8 : : * Contact:
9 : : * maxence.laurent <at> heig-vd <dot> ch
10 : : * or
11 : : * eric.taillard <at> heig-vd <dot> ch
12 : : *
13 : : * This file is part of libpal.
14 : : *
15 : : * libpal is free software: you can redistribute it and/or modify
16 : : * it under the terms of the GNU General Public License as published by
17 : : * the Free Software Foundation, either version 3 of the License, or
18 : : * (at your option) any later version.
19 : : *
20 : : * libpal is distributed in the hope that it will be useful,
21 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 : : * GNU General Public License for more details.
24 : : *
25 : : * You should have received a copy of the GNU General Public License
26 : : * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27 : : *
28 : : */
29 : :
30 : : #include "layer.h"
31 : : #include "pal.h"
32 : : #include "costcalculator.h"
33 : : #include "feature.h"
34 : : #include "geomfunction.h"
35 : : #include "labelposition.h"
36 : : #include "qgsgeos.h"
37 : : #include "qgsmessagelog.h"
38 : : #include <cmath>
39 : : #include <cfloat>
40 : :
41 : : using namespace pal;
42 : :
43 : 0 : LabelPosition::LabelPosition( int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed, Quadrant quadrant )
44 : 0 : : id( id )
45 : 0 : , feature( feature )
46 : 0 : , probFeat( 0 )
47 : 0 : , nbOverlap( 0 )
48 : 0 : , alpha( alpha )
49 : 0 : , w( w )
50 : 0 : , h( h )
51 : 0 : , partId( -1 )
52 : 0 : , reversed( isReversed )
53 : 0 : , upsideDown( false )
54 : 0 : , quadrant( quadrant )
55 : 0 : , mCost( cost )
56 : 0 : , mHasObstacleConflict( false )
57 : 0 : , mUpsideDownCharCount( 0 )
58 : 0 : {
59 : 0 : type = GEOS_POLYGON;
60 : 0 : nbPoints = 4;
61 : 0 : x.resize( nbPoints );
62 : 0 : y.resize( nbPoints );
63 : :
64 : : // alpha take his value bw 0 and 2*pi rad
65 : 0 : while ( this->alpha > 2 * M_PI )
66 : 0 : this->alpha -= 2 * M_PI;
67 : :
68 : 0 : while ( this->alpha < 0 )
69 : 0 : this->alpha += 2 * M_PI;
70 : :
71 : 0 : double beta = this->alpha + M_PI_2;
72 : :
73 : : double dx1, dx2, dy1, dy2;
74 : :
75 : 0 : dx1 = std::cos( this->alpha ) * w;
76 : 0 : dy1 = std::sin( this->alpha ) * w;
77 : :
78 : 0 : dx2 = std::cos( beta ) * h;
79 : 0 : dy2 = std::sin( beta ) * h;
80 : :
81 : 0 : x[0] = x1;
82 : 0 : y[0] = y1;
83 : :
84 : 0 : x[1] = x1 + dx1;
85 : 0 : y[1] = y1 + dy1;
86 : :
87 : 0 : x[2] = x1 + dx1 + dx2;
88 : 0 : y[2] = y1 + dy1 + dy2;
89 : :
90 : 0 : x[3] = x1 + dx2;
91 : 0 : y[3] = y1 + dy2;
92 : :
93 : : // upside down ? (curved labels are always correct)
94 : 0 : if ( !feature->layer()->isCurved() &&
95 : 0 : this->alpha > M_PI_2 && this->alpha <= 3 * M_PI_2 )
96 : : {
97 : 0 : if ( feature->showUprightLabels() )
98 : : {
99 : : // Turn label upsidedown by inverting boundary points
100 : : double tx, ty;
101 : :
102 : 0 : tx = x[0];
103 : 0 : ty = y[0];
104 : :
105 : 0 : x[0] = x[2];
106 : 0 : y[0] = y[2];
107 : :
108 : 0 : x[2] = tx;
109 : 0 : y[2] = ty;
110 : :
111 : 0 : tx = x[1];
112 : 0 : ty = y[1];
113 : :
114 : 0 : x[1] = x[3];
115 : 0 : y[1] = y[3];
116 : :
117 : 0 : x[3] = tx;
118 : 0 : y[3] = ty;
119 : :
120 : 0 : if ( this->alpha < M_PI )
121 : 0 : this->alpha += M_PI;
122 : : else
123 : 0 : this->alpha -= M_PI;
124 : :
125 : : // labels with text shown upside down are not classified as upsideDown,
126 : : // only those whose boundary points have been inverted
127 : 0 : upsideDown = true;
128 : 0 : }
129 : 0 : }
130 : :
131 : 0 : for ( int i = 0; i < nbPoints; ++i )
132 : : {
133 : 0 : xmin = std::min( xmin, x[i] );
134 : 0 : xmax = std::max( xmax, x[i] );
135 : 0 : ymin = std::min( ymin, y[i] );
136 : 0 : ymax = std::max( ymax, y[i] );
137 : 0 : }
138 : 0 : }
139 : :
140 : 0 : LabelPosition::LabelPosition( const LabelPosition &other )
141 : 0 : : PointSet( other )
142 : 0 : {
143 : 0 : id = other.id;
144 : 0 : mCost = other.mCost;
145 : 0 : feature = other.feature;
146 : 0 : probFeat = other.probFeat;
147 : 0 : nbOverlap = other.nbOverlap;
148 : :
149 : 0 : alpha = other.alpha;
150 : 0 : w = other.w;
151 : 0 : h = other.h;
152 : :
153 : 0 : if ( other.mNextPart )
154 : 0 : mNextPart = std::make_unique< LabelPosition >( *other.mNextPart );
155 : :
156 : 0 : partId = other.partId;
157 : 0 : upsideDown = other.upsideDown;
158 : 0 : reversed = other.reversed;
159 : 0 : quadrant = other.quadrant;
160 : 0 : mHasObstacleConflict = other.mHasObstacleConflict;
161 : 0 : mUpsideDownCharCount = other.mUpsideDownCharCount;
162 : 0 : }
163 : :
164 : 0 : bool LabelPosition::isIn( double *bbox )
165 : : {
166 : : int i;
167 : :
168 : 0 : for ( i = 0; i < 4; i++ )
169 : : {
170 : 0 : if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
171 : 0 : y[i] >= bbox[1] && y[i] <= bbox[3] )
172 : 0 : return true;
173 : 0 : }
174 : :
175 : 0 : if ( mNextPart )
176 : 0 : return mNextPart->isIn( bbox );
177 : : else
178 : 0 : return false;
179 : 0 : }
180 : :
181 : 0 : bool LabelPosition::isIntersect( double *bbox )
182 : : {
183 : : int i;
184 : :
185 : 0 : for ( i = 0; i < 4; i++ )
186 : : {
187 : 0 : if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
188 : 0 : y[i] >= bbox[1] && y[i] <= bbox[3] )
189 : 0 : return true;
190 : 0 : }
191 : :
192 : 0 : if ( mNextPart )
193 : 0 : return mNextPart->isIntersect( bbox );
194 : : else
195 : 0 : return false;
196 : 0 : }
197 : :
198 : 0 : bool LabelPosition::intersects( const GEOSPreparedGeometry *geometry )
199 : : {
200 : 0 : if ( !mGeos )
201 : 0 : createGeosGeom();
202 : :
203 : : try
204 : : {
205 : 0 : if ( GEOSPreparedIntersects_r( QgsGeos::getGEOSHandler(), geometry, mGeos ) == 1 )
206 : : {
207 : 0 : return true;
208 : : }
209 : 0 : else if ( mNextPart )
210 : : {
211 : 0 : return mNextPart->intersects( geometry );
212 : : }
213 : 0 : }
214 : : catch ( GEOSException &e )
215 : : {
216 : 0 : qWarning( "GEOS exception: %s", e.what() );
217 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
218 : 0 : return false;
219 : 0 : }
220 : :
221 : 0 : return false;
222 : 0 : }
223 : :
224 : 0 : bool LabelPosition::within( const GEOSPreparedGeometry *geometry )
225 : : {
226 : 0 : if ( !mGeos )
227 : 0 : createGeosGeom();
228 : :
229 : : try
230 : : {
231 : 0 : if ( GEOSPreparedContains_r( QgsGeos::getGEOSHandler(), geometry, mGeos ) != 1 )
232 : : {
233 : 0 : return false;
234 : : }
235 : 0 : else if ( mNextPart )
236 : : {
237 : 0 : return mNextPart->within( geometry );
238 : : }
239 : 0 : }
240 : : catch ( GEOSException &e )
241 : : {
242 : 0 : qWarning( "GEOS exception: %s", e.what() );
243 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
244 : 0 : return false;
245 : 0 : }
246 : :
247 : 0 : return true;
248 : 0 : }
249 : :
250 : 0 : bool LabelPosition::isInside( double *bbox )
251 : : {
252 : 0 : for ( int i = 0; i < 4; i++ )
253 : : {
254 : 0 : if ( !( x[i] >= bbox[0] && x[i] <= bbox[2] &&
255 : 0 : y[i] >= bbox[1] && y[i] <= bbox[3] ) )
256 : 0 : return false;
257 : 0 : }
258 : :
259 : 0 : if ( mNextPart )
260 : 0 : return mNextPart->isInside( bbox );
261 : : else
262 : 0 : return true;
263 : 0 : }
264 : :
265 : 0 : bool LabelPosition::isInConflict( const LabelPosition *lp ) const
266 : : {
267 : 0 : if ( this->probFeat == lp->probFeat ) // bugfix #1
268 : 0 : return false; // always overlaping itself !
269 : :
270 : 0 : if ( !nextPart() && !lp->nextPart() )
271 : 0 : return isInConflictSinglePart( lp );
272 : : else
273 : 0 : return isInConflictMultiPart( lp );
274 : 0 : }
275 : :
276 : 0 : bool LabelPosition::isInConflictSinglePart( const LabelPosition *lp ) const
277 : : {
278 : 0 : if ( qgsDoubleNear( alpha, 0 ) && qgsDoubleNear( lp->alpha, 0 ) )
279 : : {
280 : : // simple case -- both candidates are oriented to axis, so shortcut with easy calculation
281 : 0 : return boundingBoxIntersects( lp );
282 : : }
283 : :
284 : 0 : if ( !mGeos )
285 : 0 : createGeosGeom();
286 : :
287 : 0 : if ( !lp->mGeos )
288 : 0 : lp->createGeosGeom();
289 : :
290 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
291 : : try
292 : : {
293 : 0 : bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
294 : 0 : return result;
295 : 0 : }
296 : : catch ( GEOSException &e )
297 : : {
298 : 0 : qWarning( "GEOS exception: %s", e.what() );
299 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
300 : 0 : return false;
301 : 0 : }
302 : 0 : }
303 : :
304 : 0 : bool LabelPosition::isInConflictMultiPart( const LabelPosition *lp ) const
305 : : {
306 : : // check all parts against all parts of other one
307 : 0 : const LabelPosition *tmp1 = this;
308 : 0 : while ( tmp1 )
309 : : {
310 : 0 : // check tmp1 against parts of other label
311 : 0 : const LabelPosition *tmp2 = lp;
312 : 0 : while ( tmp2 )
313 : : {
314 : 0 : if ( tmp1->isInConflictSinglePart( tmp2 ) )
315 : 0 : return true;
316 : 0 : tmp2 = tmp2->nextPart();
317 : : }
318 : :
319 : 0 : tmp1 = tmp1->nextPart();
320 : : }
321 : 0 : return false; // no conflict found
322 : 0 : }
323 : :
324 : 0 : int LabelPosition::partCount() const
325 : : {
326 : 0 : if ( mNextPart )
327 : 0 : return mNextPart->partCount() + 1;
328 : : else
329 : 0 : return 1;
330 : 0 : }
331 : :
332 : 0 : void LabelPosition::offsetPosition( double xOffset, double yOffset )
333 : : {
334 : 0 : for ( int i = 0; i < 4; i++ )
335 : : {
336 : 0 : x[i] += xOffset;
337 : 0 : y[i] += yOffset;
338 : 0 : }
339 : :
340 : 0 : if ( mNextPart )
341 : 0 : mNextPart->offsetPosition( xOffset, yOffset );
342 : :
343 : 0 : invalidateGeos();
344 : 0 : }
345 : :
346 : 0 : int LabelPosition::getId() const
347 : : {
348 : 0 : return id;
349 : : }
350 : :
351 : 0 : double LabelPosition::getX( int i ) const
352 : : {
353 : 0 : return ( i >= 0 && i < 4 ? x[i] : -1 );
354 : : }
355 : :
356 : 0 : double LabelPosition::getY( int i ) const
357 : : {
358 : 0 : return ( i >= 0 && i < 4 ? y[i] : -1 );
359 : : }
360 : :
361 : 0 : double LabelPosition::getAlpha() const
362 : : {
363 : 0 : return alpha;
364 : : }
365 : :
366 : 0 : void LabelPosition::validateCost()
367 : : {
368 : 0 : if ( mCost >= 1 )
369 : : {
370 : 0 : mCost -= int ( mCost ); // label cost up to 1
371 : 0 : }
372 : 0 : }
373 : :
374 : 0 : FeaturePart *LabelPosition::getFeaturePart() const
375 : : {
376 : 0 : return feature;
377 : : }
378 : :
379 : 0 : void LabelPosition::getBoundingBox( double amin[2], double amax[2] ) const
380 : : {
381 : 0 : if ( mNextPart )
382 : : {
383 : 0 : mNextPart->getBoundingBox( amin, amax );
384 : 0 : }
385 : : else
386 : : {
387 : 0 : amin[0] = std::numeric_limits<double>::max();
388 : 0 : amax[0] = std::numeric_limits<double>::lowest();
389 : 0 : amin[1] = std::numeric_limits<double>::max();
390 : 0 : amax[1] = std::numeric_limits<double>::lowest();
391 : : }
392 : 0 : for ( int c = 0; c < 4; c++ )
393 : : {
394 : 0 : if ( x[c] < amin[0] )
395 : 0 : amin[0] = x[c];
396 : 0 : if ( x[c] > amax[0] )
397 : 0 : amax[0] = x[c];
398 : 0 : if ( y[c] < amin[1] )
399 : 0 : amin[1] = y[c];
400 : 0 : if ( y[c] > amax[1] )
401 : 0 : amax[1] = y[c];
402 : 0 : }
403 : 0 : }
404 : :
405 : 0 : void LabelPosition::setConflictsWithObstacle( bool conflicts )
406 : : {
407 : 0 : mHasObstacleConflict = conflicts;
408 : 0 : if ( mNextPart )
409 : 0 : mNextPart->setConflictsWithObstacle( conflicts );
410 : 0 : }
411 : :
412 : 0 : void LabelPosition::setHasHardObstacleConflict( bool conflicts )
413 : : {
414 : 0 : mHasHardConflict = conflicts;
415 : 0 : if ( mNextPart )
416 : 0 : mNextPart->setHasHardObstacleConflict( conflicts );
417 : 0 : }
418 : :
419 : 0 : void LabelPosition::removeFromIndex( PalRtree<LabelPosition> &index )
420 : : {
421 : : double amin[2];
422 : : double amax[2];
423 : 0 : getBoundingBox( amin, amax );
424 : 0 : index.remove( this, QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
425 : 0 : }
426 : :
427 : 0 : void LabelPosition::insertIntoIndex( PalRtree<LabelPosition> &index )
428 : : {
429 : : double amin[2];
430 : : double amax[2];
431 : 0 : getBoundingBox( amin, amax );
432 : 0 : index.insert( this, QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
433 : 0 : }
434 : :
435 : 0 : double LabelPosition::getDistanceToPoint( double xp, double yp ) const
436 : : {
437 : : //first check if inside, if so then distance is -1
438 : 0 : bool contains = false;
439 : 0 : if ( alpha == 0 )
440 : : {
441 : : // easy case -- horizontal label
442 : 0 : contains = x[0] <= xp && x[1] >= xp && y[0] <= yp && y[2] >= yp;
443 : 0 : }
444 : : else
445 : : {
446 : 0 : contains = containsPoint( xp, yp );
447 : : }
448 : :
449 : 0 : double distance = -1;
450 : 0 : if ( !contains )
451 : : {
452 : 0 : if ( alpha == 0 )
453 : : {
454 : 0 : const double dx = std::max( std::max( x[0] - xp, 0.0 ), xp - x[1] );
455 : 0 : const double dy = std::max( std::max( y[0] - yp, 0.0 ), yp - y[2] );
456 : 0 : distance = std::sqrt( dx * dx + dy * dy );
457 : 0 : }
458 : : else
459 : : {
460 : 0 : distance = std::sqrt( minDistanceToPoint( xp, yp ) );
461 : : }
462 : 0 : }
463 : :
464 : 0 : if ( mNextPart && distance > 0 )
465 : 0 : return std::min( distance, mNextPart->getDistanceToPoint( xp, yp ) );
466 : :
467 : 0 : return distance;
468 : 0 : }
469 : :
470 : 0 : bool LabelPosition::crossesLine( PointSet *line ) const
471 : : {
472 : 0 : if ( !mGeos )
473 : 0 : createGeosGeom();
474 : :
475 : 0 : if ( !line->mGeos )
476 : 0 : line->createGeosGeom();
477 : :
478 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
479 : : try
480 : : {
481 : 0 : if ( GEOSPreparedIntersects_r( geosctxt, line->preparedGeom(), mGeos ) == 1 )
482 : : {
483 : 0 : return true;
484 : : }
485 : 0 : else if ( mNextPart )
486 : : {
487 : 0 : return mNextPart->crossesLine( line );
488 : : }
489 : 0 : }
490 : : catch ( GEOSException &e )
491 : : {
492 : 0 : qWarning( "GEOS exception: %s", e.what() );
493 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
494 : 0 : return false;
495 : 0 : }
496 : :
497 : 0 : return false;
498 : 0 : }
499 : :
500 : 0 : bool LabelPosition::crossesBoundary( PointSet *polygon ) const
501 : : {
502 : 0 : if ( !mGeos )
503 : 0 : createGeosGeom();
504 : :
505 : 0 : if ( !polygon->mGeos )
506 : 0 : polygon->createGeosGeom();
507 : :
508 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
509 : : try
510 : : {
511 : 0 : if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1
512 : 0 : && GEOSPreparedContains_r( geosctxt, polygon->preparedGeom(), mGeos ) != 1 )
513 : : {
514 : 0 : return true;
515 : : }
516 : 0 : else if ( mNextPart )
517 : : {
518 : 0 : return mNextPart->crossesBoundary( polygon );
519 : : }
520 : 0 : }
521 : : catch ( GEOSException &e )
522 : : {
523 : 0 : qWarning( "GEOS exception: %s", e.what() );
524 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
525 : 0 : return false;
526 : 0 : }
527 : :
528 : 0 : return false;
529 : 0 : }
530 : :
531 : 0 : int LabelPosition::polygonIntersectionCost( PointSet *polygon ) const
532 : : {
533 : : //effectively take the average polygon intersection cost for all label parts
534 : 0 : double totalCost = polygonIntersectionCostForParts( polygon );
535 : 0 : int n = partCount();
536 : 0 : return std::ceil( totalCost / n );
537 : : }
538 : :
539 : 0 : bool LabelPosition::intersectsWithPolygon( PointSet *polygon ) const
540 : : {
541 : 0 : if ( !mGeos )
542 : 0 : createGeosGeom();
543 : :
544 : 0 : if ( !polygon->mGeos )
545 : 0 : polygon->createGeosGeom();
546 : :
547 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
548 : : try
549 : : {
550 : 0 : if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
551 : : {
552 : 0 : return true;
553 : : }
554 : 0 : }
555 : : catch ( GEOSException &e )
556 : : {
557 : 0 : qWarning( "GEOS exception: %s", e.what() );
558 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
559 : 0 : }
560 : :
561 : 0 : if ( mNextPart )
562 : : {
563 : 0 : return mNextPart->intersectsWithPolygon( polygon );
564 : : }
565 : : else
566 : : {
567 : 0 : return false;
568 : : }
569 : 0 : }
570 : :
571 : 0 : double LabelPosition::polygonIntersectionCostForParts( PointSet *polygon ) const
572 : : {
573 : 0 : if ( !mGeos )
574 : 0 : createGeosGeom();
575 : :
576 : 0 : if ( !polygon->mGeos )
577 : 0 : polygon->createGeosGeom();
578 : :
579 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
580 : 0 : double cost = 0;
581 : : try
582 : : {
583 : 0 : if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
584 : : {
585 : : //at least a partial intersection
586 : 0 : cost += 1;
587 : :
588 : : double px, py;
589 : :
590 : : // check each corner
591 : 0 : for ( int i = 0; i < 4; ++i )
592 : : {
593 : 0 : px = x[i];
594 : 0 : py = y[i];
595 : :
596 : 0 : for ( int a = 0; a < 2; ++a ) // and each middle of segment
597 : : {
598 : 0 : if ( polygon->containsPoint( px, py ) )
599 : 0 : cost++;
600 : 0 : px = ( x[i] + x[( i + 1 ) % 4] ) / 2.0;
601 : 0 : py = ( y[i] + y[( i + 1 ) % 4] ) / 2.0;
602 : 0 : }
603 : 0 : }
604 : :
605 : 0 : px = ( x[0] + x[2] ) / 2.0;
606 : 0 : py = ( y[0] + y[2] ) / 2.0;
607 : :
608 : : //check the label center. if covered by polygon, cost of 4
609 : 0 : if ( polygon->containsPoint( px, py ) )
610 : 0 : cost += 4;
611 : 0 : }
612 : 0 : }
613 : : catch ( GEOSException &e )
614 : : {
615 : 0 : qWarning( "GEOS exception: %s", e.what() );
616 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
617 : 0 : }
618 : :
619 : : //maintain scaling from 0 -> 12
620 : 0 : cost = 12.0 * cost / 13.0;
621 : :
622 : 0 : if ( mNextPart )
623 : : {
624 : 0 : cost += mNextPart->polygonIntersectionCostForParts( polygon );
625 : 0 : }
626 : :
627 : 0 : return cost;
628 : 0 : }
|