karbon

vpath.cc

00001 /* This file is part of the KDE project
00002    Copyright (C) 2002, The Karbon Developers
00003 
00004    This library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Library General Public
00006    License as published by the Free Software Foundation; either
00007    version 2 of the License, or (at your option) any later version.
00008 
00009    This library is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY; without even the implied warranty of
00011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012    Library General Public License for more details.
00013 
00014    You should have received a copy of the GNU Library General Public License
00015    along with this library; see the file COPYING.LIB.  If not, write to
00016    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00017  * Boston, MA 02110-1301, USA.
00018 */
00019 
00020 
00021 #include <math.h>
00022 
00023 #include <qdom.h>
00024 #include <qvaluelist.h>
00025 #include <qwmatrix.h>
00026 
00027 #include "vpath.h"
00028 #include "vsegment.h"
00029 #include "vvisitor.h"
00030 
00031 #include <kdebug.h>
00032 
00033 
00034 class VSubpathIteratorList
00035 {
00036 public:
00037     VSubpathIteratorList()
00038             : m_list( 0L ), m_iterator( 0L )
00039     {}
00040 
00041     ~VSubpathIteratorList()
00042     {
00043         notifyClear( true );
00044         delete m_list;
00045     }
00046 
00047     void add( VSubpathIterator* itr )
00048     {
00049         if( !m_iterator )
00050             m_iterator = itr;
00051         else if( m_list )
00052             m_list->push_front( itr );
00053         else
00054         {
00055             m_list = new QValueList<VSubpathIterator*>;
00056             m_list->push_front( itr );
00057         }
00058     }
00059 
00060     void remove( VSubpathIterator* itr )
00061     {
00062         if( m_iterator == itr )
00063             m_iterator = 0L;
00064         else if( m_list )
00065         {
00066             m_list->remove( itr );
00067 
00068             if( m_list->isEmpty() )
00069             {
00070                 delete m_list;
00071                 m_list = 0L;
00072             }
00073         }
00074     }
00075 
00076     void notifyClear( bool zeroList )
00077     {
00078         if( m_iterator )
00079         {
00080             if( zeroList )
00081                 m_iterator->m_list = 0L;
00082 
00083             m_iterator->m_current = 0L;
00084         }
00085 
00086         if( m_list )
00087         {
00088             for(
00089                 QValueList<VSubpathIterator*>::Iterator itr = m_list->begin();
00090                 itr != m_list->end();
00091                 ++itr )
00092             {
00093                 if( zeroList )
00094                     ( *itr )->m_list = 0L;
00095 
00096                 ( *itr )->m_current = 0L;
00097             }
00098         }
00099     }
00100 
00101     void notifyRemove( VSegment* segment, VSegment* current )
00102     {
00103         if( m_iterator )
00104         {
00105             if( m_iterator->m_current == segment )
00106                 m_iterator->m_current = current;
00107         }
00108 
00109         if( m_list )
00110         {
00111             for(
00112                 QValueList<VSubpathIterator*>::Iterator itr = m_list->begin();
00113                 itr != m_list->end();
00114                 ++itr )
00115             {
00116                 if( ( *itr )->m_current == segment )
00117                     ( *itr )->m_current = current;
00118             }
00119         }
00120     }
00121 
00122 private:
00123     QValueList<VSubpathIterator*>* m_list;
00124     VSubpathIterator* m_iterator;
00125 };
00126 
00127 
00128 VSubpath::VSubpath( VObject* parent )
00129         : VObject( parent )
00130 {
00131     m_isClosed = false;
00132 
00133     m_first = m_last = m_current = 0L;
00134     m_number = 0;
00135     m_currentIndex = -1;
00136     m_iteratorList = 0L;
00137 
00138     // Add an initial segment.
00139     append( new VSegment( 1 ) );
00140 }
00141 
00142 VSubpath::VSubpath( const VSubpath& list )
00143         : VObject( list )
00144 {
00145     m_isClosed = list.isClosed();
00146 
00147     m_first = m_last = m_current = 0L;
00148     m_number = 0;
00149     m_currentIndex = -1;
00150     m_iteratorList = 0L;
00151 
00152     VSegment* segment = list.m_first;
00153 
00154     while( segment )
00155     {
00156         append( segment->clone() );
00157         segment = segment->m_next;
00158     }
00159 }
00160 
00161 VSubpath::VSubpath( const VSegment& segment )
00162         : VObject( 0L )
00163 {
00164     m_isClosed = false;
00165 
00166     m_first = m_last = m_current = 0L;
00167     m_number = 0;
00168     m_currentIndex = -1;
00169     m_iteratorList = 0L;
00170 
00171     // The segment is not a "begin" segment.
00172     if( segment.prev() )
00173     {
00174         // Add an initial segment.
00175         append( new VSegment( 1 ) );
00176 
00177         // Move the "begin" segment to the new segment's previous knot.
00178         moveTo( segment.prev()->knot() );
00179     }
00180 
00181     // Append a copy of the segment.
00182     append( segment.clone() );
00183 }
00184 
00185 VSubpath::~VSubpath()
00186 {
00187     clear();
00188     delete m_iteratorList;
00189 }
00190 
00191 const KoPoint&
00192 VSubpath::currentPoint() const
00193 {
00194     return getLast()->knot();
00195 }
00196 
00197 bool
00198 VSubpath::moveTo( const KoPoint& p )
00199 {
00200     // Move "begin" segment if path is still empty.
00201     if( isEmpty() )
00202     {
00203         getLast()->setKnot( p );
00204         return true;
00205     }
00206 
00207     return false;
00208 }
00209 
00210 bool
00211 VSubpath::lineTo( const KoPoint& p )
00212 {
00213     if( isClosed() )
00214         return false;
00215 
00216     VSegment* s = new VSegment( 1 );
00217 
00218     s->setDegree( 1 );
00219     s->setKnot( p );
00220 
00221     append( s );
00222 
00223     return true;
00224 }
00225 
00226 bool
00227 VSubpath::curveTo(
00228     const KoPoint& p1, const KoPoint& p2, const KoPoint& p3 )
00229 {
00230     if( isClosed() )
00231         return false;
00232 
00233     VSegment* s = new VSegment();
00234 
00235     s->setDegree( 3 );
00236     s->setPoint( 0, p1 );
00237     s->setPoint( 1, p2 );
00238     s->setPoint( 2, p3 );
00239 
00240     append( s );
00241 
00242 
00243     return true;
00244 }
00245 
00246 bool
00247 VSubpath::curve1To( const KoPoint& p2, const KoPoint& p3 )
00248 {
00249     if( isClosed() )
00250         return false;
00251 
00252     VSegment* s = new VSegment();
00253 
00254     s->setDegree( 3 );
00255     s->setPoint( 0, currentPoint() );
00256     s->setPoint( 1, p2 );
00257     s->setPoint( 2, p3 );
00258 
00259     append( s );
00260 
00261 
00262     return true;
00263 }
00264 
00265 bool
00266 VSubpath::curve2To( const KoPoint& p1, const KoPoint& p3 )
00267 {
00268     if( isClosed() )
00269         return false;
00270 
00271     VSegment* s = new VSegment();
00272 
00273     s->setDegree( 3 );
00274     s->setPoint( 0, p1 );
00275     s->setPoint( 1, p3 );
00276     s->setPoint( 2, p3 );
00277 
00278     append( s );
00279 
00280 
00281     return true;
00282 }
00283 
00284 bool
00285 VSubpath::arcTo(
00286     const KoPoint& p1, const KoPoint& p2, const double r )
00287 {
00288     /* This routine is inspired by code in GNU ghostscript.
00289      *
00290      *           |- P1B3 -|
00291      *
00292      *          |- - - T12- - -|
00293      *
00294      *  -   - P1 x....__--o.....x P2
00295      *  |   |    :  _/    B3
00296      * P1B0      : /
00297      *      |    :/
00298      *  |        |
00299      *  -  T10   o B0
00300      *           |
00301      *      |    |
00302      *           |
00303      *      |    |
00304      *      -    x P0
00305      */
00306 
00307     if( isClosed() || r < 0.0 )
00308         return false;
00309 
00310 
00311     // We need to calculate the tangent points. Therefore calculate tangents
00312     // T10=P1P0 and T12=P1P2 first.
00313     double dx0 = currentPoint().x() - p1.x();
00314     double dy0 = currentPoint().y() - p1.y();
00315     double dx2 = p2.x() - p1.x();
00316     double dy2 = p2.y() - p1.y();
00317 
00318     // Calculate distance squares.
00319     double dsqT10 = dx0 * dx0 + dy0 * dy0;
00320     double dsqT12 = dx2 * dx2 + dy2 * dy2;
00321 
00322     // We now calculate tan(a/2) where a is the angle between T10 and T12.
00323     // We benefit from the facts T10*T12 = |T10|*|T12|*cos(a),
00324     // |T10xT12| = |T10|*|T12|*sin(a) (cross product) and tan(a/2) = sin(a)/[1-cos(a)].
00325     double num = dy0 * dx2 - dy2 * dx0;
00326 
00327     double denom = sqrt( dsqT10 * dsqT12 ) - ( dx0 * dx2 + dy0 * dy2 );
00328 
00329     // The points are colinear.
00330     if( 1.0 + denom == 1.0 )
00331     {
00332         // Just add a line.
00333         lineTo( p1 );
00334     }
00335     else
00336     {
00337         // |P1B0| = |P1B3| = r * tan(a/2).
00338         double dP1B0 = fabs( r * num / denom );
00339 
00340         // B0 = P1 + |P1B0| * T10/|T10|.
00341         KoPoint b0 = p1 + KoPoint( dx0, dy0 ) * ( dP1B0 / sqrt( dsqT10 ) );
00342 
00343         // If B0 deviates from current point P0, add a line to it.
00344         if( !b0.isNear( currentPoint(), VGlobal::isNearRange ) )
00345             lineTo( b0 );
00346 
00347         // B3 = P1 + |P1B3| * T12/|T12|.
00348         KoPoint b3 = p1 + KoPoint( dx2, dy2 ) * ( dP1B0 / sqrt( dsqT12 ) );
00349 
00350 
00351         // The two bezier-control points are located on the tangents at a fraction
00352         // of the distance[ tangent points <-> tangent intersection ].
00353         const KoPoint d = p1 - b0;
00354 
00355         double distsq = d * d;
00356 
00357         double rsq = r * r;
00358 
00359         double fract;
00360 
00361         // r is very small.
00362         if( distsq >= rsq * VGlobal::veryBigNumber )
00363         {
00364             // Assume dist = r = 0.
00365             fract = 0.0;
00366         }
00367         else
00368         {
00369             fract = ( 4.0 / 3.0 ) / ( 1.0 + sqrt( 1.0 + distsq / rsq ) );
00370         }
00371 
00372         KoPoint b1 = b0 + ( p1 - b0 ) * fract;
00373         KoPoint b2 = b3 + ( p1 - b3 ) * fract;
00374 
00375         // Finally add the bezier-segment.
00376         curveTo( b1, b2, b3 );
00377     }
00378 
00379     return true;
00380 }
00381 
00382 void
00383 VSubpath::close()
00384 {
00385     // In the case the list is 100% empty (which should actually never happen),
00386     // append a "begin" first, to avoid a crash.
00387     if( count() == 0 )
00388         append( new VSegment( 1 ) );
00389 
00390     // Move last segment if we are already closed.
00391     if( isClosed() )
00392     {
00393         getLast()->setKnot( getFirst()->knot() );
00394     }
00395     // Append a line, if necessary.
00396     else
00397     {
00398         if(
00399             getLast()->knot().isNear(
00400                 getFirst()->knot(), VGlobal::isNearRange ) )
00401         {
00402             // Move last knot.
00403             getLast()->setKnot( getFirst()->knot() );
00404         }
00405         else
00406         {
00407             // Add a line.
00408             lineTo( getFirst()->knot() );
00409         }
00410 
00411         m_isClosed = true;
00412     }
00413 }
00414 
00415 bool
00416 VSubpath::pointIsInside( const KoPoint& p ) const
00417 {
00418     // If the point is not inside the boundingbox, it cannot be inside the path either.
00419     if( !boundingBox().contains( p ) )
00420         return false;
00421 
00422     // First check if the point is inside the knot polygon (beziers are treated
00423     // as lines).
00424 
00425     /* This algorithm is taken from "Fast Winding Number Inclusion of a Point
00426      * in a Polygon" by Dan Sunday, geometryalgorithms.com.
00427      */
00428 
00429     /*
00430     int windingNumber = 0;
00431 
00432     // Ommit first segment.
00433     VSegment* segment = getFirst()->next();
00434 
00435     while( segment )
00436     {
00437         if( segment->prev()->knot().y() <= p.y() )
00438         {
00439             // Upward crossing.
00440             if( segment->knot().y() > p.y() )
00441             {
00442                 // Point is left.
00443                 if( segment->pointIsLeft( p ) > 0 )
00444                 {
00445                     // Valid up intersection.
00446                     ++windingNumber;
00447                 }
00448             }
00449         }
00450         else
00451         {
00452             // Downward crossing.
00453             if( segment->knot().y() <= p.y() )
00454             {
00455                 // Point is right.
00456                 if( segment->pointIsLeft( p ) < 0 )
00457                 {
00458                     // Valid down intersection.
00459                     --windingNumber;
00460                 }
00461             }
00462         }
00463 
00464         segment = segment->next();
00465     }
00466 
00467     if( static_cast<bool>( windingNumber ) )
00468         return true;
00469     */
00470     
00471     // Then check if the point is located in between the knot polygon
00472     // and the bezier curves.
00473 
00474     /* We rotate each segment in order to make their chord (the line between
00475      * the previous knot and the knot ) parallel to the x-axis. Then we
00476      * calculate y(xp) on the segment for the rotated input point (xp,yp)
00477      * and compare y(xp) with yp.
00478      */
00479 // TODO
00480     
00481     // cache the closed evaluation
00482     bool closed = isClosed() || getLast()->knot() == getFirst()->knot();
00483 
00484     QValueList<double> rparams;
00485 
00486     VSegment* segment = getFirst()->next();
00487 
00488     // move all segements so that p is the origin 
00489     // and compute their intersections with the x-axis
00490     while( segment )
00491     {
00492         VSubpath tmpCurve( 0L );
00493         tmpCurve.append( new VSegment( segment->degree() ) );
00494     
00495         for( int i = 0; i <= segment->degree(); ++i )
00496             tmpCurve.current()->setP(i, segment->p(i)-p );
00497         
00498         tmpCurve.current()->rootParams( rparams );
00499 
00500         segment = segment->next();
00501     }
00502     
00503     // if the path is not closed, compute the intersection of
00504     // the line through the first and last knot and the x-axis too
00505     if( ! closed )
00506     {
00507         KoPoint prevKnot = getLast()->knot() - p;
00508         KoPoint nextKnot = getFirst()->knot() - p;
00509 
00510         double dx = nextKnot.x() - prevKnot.x();
00511         double dy = nextKnot.y() - prevKnot.y();
00512         if( dx == 0.0 )
00513         {
00514             rparams.append( nextKnot.x() );
00515         }
00516         else if( dy != 0.0 )
00517         {
00518             if( ( prevKnot.y() < 0.0 && nextKnot.y() > 0.0 ) || ( prevKnot.y() > 0.0 && nextKnot.y() < 0.0 ) )
00519             {
00520                 double n = prevKnot.y() - dy / dx * prevKnot.x();
00521                 rparams.append( -n * dx / dy );
00522             }
00523         }
00524     }
00525     
00526     kdDebug(38000) << "intersection count: " << rparams.count() << endl;
00527 
00528     // sort all intersections
00529     qHeapSort( rparams );
00530 
00531     QValueList<double>::iterator itr, etr = rparams.end();
00532     
00533     for( itr = rparams.begin(); itr != etr; ++itr )
00534         kdDebug(38000) << "intersection: " << *itr << endl;
00535 
00536     if( closed )
00537     {
00538         // pair the intersections and check if the origin is within a pair
00539         for( itr = rparams.begin(); itr != etr; ++itr )
00540         {
00541             if( *itr > 0.0 ) 
00542                 return false;
00543     
00544             if( ++itr == etr )
00545                 return false;
00546             
00547             if( *itr > 0.0 )
00548                 return true;
00549         }
00550     }
00551     else
00552     {
00553         // only check if point is between first and last intersection if we have an open path
00554         if ( rparams.front() < 0.0 && rparams.back() > 0.0 )
00555             return true;
00556     }
00557 
00558     return false;
00559 }
00560 
00561 bool
00562 VSubpath::intersects( const VSegment& s ) const
00563 {
00564     // Check if path is empty and if boundingboxes intersect.
00565     if(
00566         isEmpty() ||
00567         !boundingBox().intersects( s.boundingBox() ) )
00568     {
00569         return false;
00570     }
00571 
00572 
00573     // Ommit first segment.
00574     VSegment* segment = getFirst()->next();
00575 
00576     while( segment )
00577     {
00578         if( segment->intersects( s ) )
00579         {
00580             return true;
00581         }
00582 
00583         segment = segment->next();
00584     }
00585 
00586     return false;
00587 }
00588 
00589 bool
00590 VSubpath::counterClockwise() const
00591 {
00592     /* This algorithm is taken from the FAQ of comp.graphics.algorithms:
00593      * "Find the lowest vertex (or, if there is more than one vertex with the
00594      * same lowest coordinate, the rightmost of those vertices) and then take
00595      * the cross product of the edges fore and aft of it."
00596      */
00597 
00598     // A non closed path does not have a winding.
00599     if( !isClosed() )
00600     {
00601         return false;
00602     }
00603 
00604 
00605     VSegment* segment = getFirst();
00606 
00607     // We save the segment not the knot itself. Initialize it with the
00608     // first segment:
00609     const VSegment* bottomRight = getFirst();
00610 
00611     while( segment )
00612     {
00613         if( segment->knot().y() < bottomRight->knot().y() )
00614             bottomRight = segment;
00615         else if( segment->knot().y() - bottomRight->knot().y()
00616                   < VGlobal::isNearRange )
00617         {
00618             if( segment->knot().x() > bottomRight->knot().x() )
00619                 bottomRight = segment;
00620         }
00621 
00622         segment = segment->next();
00623     }
00624 
00625 
00626     // Catch boundary case (bottomRight is first or last segment):
00627     const VSegment* current;
00628     const VSegment* next;
00629 
00630     if( bottomRight == getFirst() )
00631         current = getLast();
00632     else
00633         current = bottomRight;
00634 
00635     if( bottomRight == getLast() )
00636         next = getFirst()->next();
00637     else
00638         next = bottomRight->next();
00639 
00640     // Check "z-component" of cross product:
00641     return
00642         ( next->knot().x() - next->prev()->knot().x() ) *
00643         ( current->knot().y() - current->prev()->knot().y() )
00644         -
00645         ( next->knot().y() - next->prev()->knot().y() ) *
00646         ( current->knot().x() - current->prev()->knot().x() ) < 0.0;
00647 }
00648 
00649 void
00650 VSubpath::revert()
00651 {
00652     // Catch case where the list is "empty".
00653     if( isEmpty() )
00654         return;
00655 
00656 
00657     VSubpath list( parent() );
00658     list.moveTo( getLast()->knot() );
00659 
00660     VSegment* segment = getLast();
00661 
00662     while( segment->prev() )
00663     {
00664         list.append( segment->revert() );
00665         segment = segment->prev();
00666     }
00667 
00668     list.m_isClosed = isClosed();
00669 
00670     *this = list;
00671 }
00672 
00673 const KoRect&
00674 VSubpath::boundingBox() const
00675 {
00676     if( m_boundingBoxIsInvalid )
00677     {
00678         // Reset the boundingbox.
00679         m_boundingBox = KoRect();
00680 
00681         VSegment* segment = m_first;
00682 
00683         while( segment )
00684         {
00685             if( segment->state() != VSegment::deleted )
00686                 m_boundingBox |= segment->boundingBox();
00687 
00688             segment = segment->m_next;
00689         }
00690 
00691         m_boundingBoxIsInvalid = false;
00692     }
00693 
00694     return m_boundingBox;
00695 }
00696 
00697 VSubpath*
00698 VSubpath::clone() const
00699 {
00700     return new VSubpath( *this );
00701 }
00702 
00703 void
00704 VSubpath::saveSvgPath( QString &d ) const
00705 {
00706     // Save segments.
00707     VSegment* segment = getFirst();
00708 
00709     while( segment )
00710     {
00711         if( segment->state() == VSegment::normal )
00712         {
00713             if( segment->degree() <= 2 )
00714             {
00715                 // Line.
00716                 if( segment->prev() )
00717                 {
00718                     d += QString( "L%1 %2" ).
00719                             arg( segment->knot().x() ).arg( segment->knot().y() );
00720                 }
00721                 // Moveto.
00722                 else
00723                 {
00724                     d += QString( "M%1 %2" ).
00725                             arg( segment->knot().x() ).arg( segment->knot().y() );
00726                 }
00727             }
00728             // Bezier ( degree >= 3 ).
00729             else
00730             {
00731                 // We currently treat all beziers as cubic beziers.
00732                 d += QString( "C%1 %2 %3 %4 %5 %6" ).
00733                             arg( segment->point( segment->degree() - 3 ).x() ).
00734                             arg( segment->point( segment->degree() - 3 ).y() ).
00735                             arg( segment->point( segment->degree() - 2 ).x() ).
00736                             arg( segment->point( segment->degree() - 2 ).y() ).
00737                             arg( segment->knot().x() ).
00738                             arg( segment->knot().y() );
00739             }
00740         }
00741 
00742         segment = segment->m_next;
00743     }
00744 
00745     if( isClosed() )
00746         d += "Z";
00747 }
00748 
00749 // TODO: remove this backward compatibility function after koffice 1.3.x
00750 void
00751 VSubpath::load( const QDomElement& element )
00752 {
00753     // We might have a "begin" segment.
00754     clear();
00755 
00756     QDomNodeList list = element.childNodes();
00757 
00758     for( uint i = 0; i < list.count(); ++i )
00759     {
00760         if( list.item( i ).isElement() )
00761         {
00762             QDomElement segment = list.item( i ).toElement();
00763 
00764             VSegment* s = new VSegment();
00765             s->load( segment );
00766             append( s );
00767         }
00768     }
00769 
00770     if( element.attribute( "isClosed" ) == 0 ? false : true )
00771         close();
00772 }
00773 
00774 void
00775 VSubpath::accept( VVisitor& visitor )
00776 {
00777     visitor.visitVSubpath( *this );
00778 }
00779 
00780 
00781 VSubpath&
00782 VSubpath::operator=( const VSubpath& list )
00783 {
00784     if( this == &list )
00785         return *this;
00786 
00787     m_isClosed = list.isClosed();
00788 
00789     clear();
00790 
00791     VSegment* segment = list.m_first;
00792 
00793     while( segment )
00794     {
00795         append( segment->clone() );
00796         segment = segment->m_next;
00797     }
00798 
00799     m_current = m_first;
00800     m_currentIndex = 0;
00801 
00802     return *this;
00803 }
00804 
00805 bool
00806 VSubpath::insert( const VSegment* segment )
00807 {
00808     if( m_currentIndex == -1 )
00809         return false;
00810 
00811     VSegment* s = const_cast<VSegment*>( segment );
00812 
00813     VSegment* prev = m_current->m_prev;
00814 
00815     m_current->m_prev = s;
00816     prev->m_next = s;
00817     s->m_prev = prev;
00818     s->m_next = m_current;
00819 
00820     m_current = s;
00821     ++m_number;
00822 
00823     invalidateBoundingBox();
00824 
00825     return true;
00826 }
00827 
00828 bool
00829 VSubpath::insert( uint index, const VSegment* segment )
00830 {
00831     VSegment* s = const_cast<VSegment*>( segment );
00832 
00833     if( index == 0 )
00834     {
00835         prepend( s );
00836         return true;
00837     }
00838     else if( index == m_number )
00839     {
00840         append( s );
00841         return true;
00842     }
00843 
00844     VSegment* next = locate( index );
00845 
00846     if( !next )
00847         return false;
00848 
00849     VSegment* prev = next->m_prev;
00850 
00851     next->m_prev = s;
00852     prev->m_next = s;
00853     s->m_prev = prev;
00854     s->m_next = next;
00855 
00856     m_current = s;
00857     ++m_number;
00858 
00859     invalidateBoundingBox();
00860 
00861     return true;
00862 }
00863 
00864 void
00865 VSubpath::prepend( const VSegment* segment )
00866 {
00867     VSegment* s = const_cast<VSegment*>( segment );
00868 
00869     s->m_prev = 0L;
00870 
00871     if( ( s->m_next = m_first ) )
00872         m_first->m_prev = s;
00873     else
00874         m_last = s;
00875 
00876     m_first = m_current = s;
00877 
00878     ++m_number;
00879     m_currentIndex = 0;
00880 
00881     invalidateBoundingBox();
00882 }
00883 
00884 void
00885 VSubpath::append( const VSegment* segment )
00886 {
00887     VSegment* s = const_cast<VSegment*>( segment );
00888 
00889     s->m_next = 0L;
00890 
00891     if( ( s->m_prev = m_last ) )
00892         m_last->m_next = s;
00893     else
00894         m_first = s;
00895 
00896     m_last = m_current = s;
00897 
00898     m_currentIndex = m_number;
00899     ++m_number;
00900 
00901     invalidateBoundingBox();
00902 }
00903 
00904 void
00905 VSubpath::clear()
00906 {
00907     VSegment* segment = m_first;
00908 
00909     m_first = m_last = m_current = 0L;
00910     m_number = 0;
00911     m_currentIndex = -1;
00912 
00913     if( m_iteratorList )
00914         m_iteratorList->notifyClear( false );
00915 
00916     VSegment* prev;
00917 
00918     while( segment )
00919     {
00920         prev = segment;
00921         segment = segment->m_next;
00922         delete prev;
00923     }
00924 
00925     m_isClosed = false;
00926 
00927     invalidateBoundingBox();
00928 }
00929 
00930 VSegment*
00931 VSubpath::first()
00932 {
00933     if( m_first )
00934     {
00935         m_currentIndex = 0;
00936         return m_current = m_first;
00937     }
00938 
00939     return 0L;
00940 }
00941 
00942 VSegment*
00943 VSubpath::last()
00944 {
00945     if( m_last )
00946     {
00947         m_currentIndex = m_number - 1;
00948         return m_current = m_last;
00949     }
00950 
00951     return 0L;
00952 }
00953 
00954 VSegment*
00955 VSubpath::prev()
00956 {
00957     if( m_current )
00958     {
00959         if( m_current->m_prev )
00960         {
00961             --m_currentIndex;
00962             return m_current = m_current->m_prev;
00963         }
00964 
00965         m_currentIndex = -1;
00966         m_current = 0L;
00967     }
00968 
00969     return 0L;
00970 }
00971 
00972 VSegment*
00973 VSubpath::next()
00974 {
00975     if( m_current )
00976     {
00977         if( m_current->m_next )
00978         {
00979             ++m_currentIndex;
00980             return m_current = m_current->m_next;
00981         }
00982 
00983         m_currentIndex = -1;
00984         m_current = 0L;
00985     }
00986 
00987     return 0L;
00988 }
00989 
00990 VSegment*
00991 VSubpath::locate( uint index )
00992 {
00993     if( index == static_cast<uint>( m_currentIndex ) )
00994         return m_current;
00995 
00996     if( !m_current && m_first )
00997     {
00998         m_current = m_first;
00999         m_currentIndex = 0;
01000     }
01001 
01002     VSegment* segment;
01003     int distance = index - m_currentIndex;
01004     bool forward;
01005 
01006     if( index >= m_number )
01007         return 0L;
01008 
01009     if( distance < 0 )
01010         distance = -distance;
01011 
01012     if(
01013         static_cast<uint>( distance ) < index &&
01014         static_cast<uint>( distance ) < m_number - index )
01015     {
01016         segment = m_current;
01017         forward = index > static_cast<uint>( m_currentIndex );
01018     }
01019     else if( index < m_number - index )
01020     {
01021         segment = m_first;
01022         distance = index;
01023         forward = true;
01024     }
01025     else
01026     {
01027         segment = m_last;
01028         distance = m_number - index - 1;
01029         if( distance < 0 )
01030             distance = 0;
01031         forward = false;
01032     }
01033 
01034     if( forward )
01035     {
01036         while( distance-- )
01037             segment = segment->m_next;
01038     }
01039     else
01040     {
01041         while( distance-- )
01042             segment = segment->m_prev;
01043     }
01044 
01045     m_currentIndex = index;
01046     return m_current = segment;
01047 }
01048 
01049 
01050 VSubpathIterator::VSubpathIterator( const VSubpath& list )
01051 {
01052     m_list = const_cast<VSubpath*>( &list );
01053     m_current = m_list->m_first;
01054 
01055     if( !m_list->m_iteratorList )
01056         m_list->m_iteratorList = new VSubpathIteratorList();
01057 
01058     m_list->m_iteratorList->add( this );
01059 }
01060 
01061 VSubpathIterator::VSubpathIterator( const VSubpathIterator& itr )
01062 {
01063     m_list = itr.m_list;
01064     m_current = itr.m_current;
01065 
01066     if( m_list )
01067         m_list->m_iteratorList->add( this );
01068 }
01069 
01070 VSubpathIterator::~VSubpathIterator()
01071 {
01072     if( m_list )
01073         m_list->m_iteratorList->remove( this );
01074 }
01075 
01076 VSubpathIterator&
01077 VSubpathIterator::operator=( const VSubpathIterator& itr )
01078 {
01079     if( m_list )
01080         m_list->m_iteratorList->remove( this );
01081 
01082     m_list = itr.m_list;
01083     m_current = itr.m_current;
01084 
01085     if( m_list )
01086         m_list->m_iteratorList->add( this );
01087 
01088     return *this;
01089 }
01090 
01091 VSegment*
01092 VSubpathIterator::current() const
01093 {
01094     // If m_current points to a deleted segment, find the next not
01095     // deleted segment.
01096     if(
01097         m_current &&
01098         m_current->state() == VSegment::deleted )
01099     {
01100         return m_current->next();
01101     }
01102 
01103     return m_current;
01104 }
01105 
01106 VSegment*
01107 VSubpathIterator::operator()()
01108 {
01109     if( VSegment* const old = current() )
01110     {
01111         m_current = current()->next();
01112         return old;
01113     }
01114 
01115     return 0L;
01116 }
01117 
01118 VSegment*
01119 VSubpathIterator::operator++()
01120 {
01121     if( current() )
01122         return m_current = current()->next();
01123 
01124     return 0L;
01125 }
01126 
01127 VSegment*
01128 VSubpathIterator::operator+=( uint i )
01129 {
01130     while( current() && i-- )
01131         m_current = current()->next();
01132 
01133     return current();
01134 }
01135 
01136 VSegment*
01137 VSubpathIterator::operator--()
01138 {
01139     if( current() )
01140         return m_current = current()->prev();
01141 
01142     return 0L;
01143 }
01144 
01145 VSegment*
01146 VSubpathIterator::operator-=( uint i )
01147 {
01148     while( current() && i-- )
01149         m_current = current()->prev();
01150 
01151     return current();
01152 }
01153 
KDE Home | KDE Accessibility Home | Description of Access Keys