okular/core/textpage.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2005 by Piotr Szymanski <niedakh@gmail.com>             *
   3  *                                                                         *
   4  *   This program is free software; you can redistribute it and/or modify  *
   5  *   it under the terms of the GNU General Public License as published by  *
   6  *   the Free Software Foundation; either version 2 of the License, or     *
   7  *   (at your option) any later version.                                   *
   8  ***************************************************************************/
   9
  10 #include "textpage.h"
  11 #include "textpage_p.h"
  12
  13 #include <kdebug.h>
  14
  15 #include "area.h"
  16 #include "debug_p.h"
  17 #include "misc.h"
  18 #include "page.h"
  19 #include "page_p.h"
  20
  21 #include <cstring>
  22
  23 using namespace Okular;
  24
  25 class SearchPoint
  26 {
  27     public:
  28         SearchPoint()
  29             : offset_begin( -1 ), offset_end( -1 )
  30         {
  31         }
  32
  33         TextList::ConstIterator it_begin;
  34         TextList::ConstIterator it_end;
  35         int offset_begin;
  36         int offset_end;
  37 };
  38
  39
  40 /*
  41   Rationale behind TinyTextEntity:
  42
  43   instead of storing directly a QString for the text of an entity,
  44   we store the UTF-16 data and their length. This way, we save about
  45   4 int's wrt a QString, and we can create a new string from that
  46   raw data (that's the only penalty of that).
  47  */
  48 class TinyTextEntity
  49 {
  50     public:
  51         TinyTextEntity( const QString &text, const NormalizedRect &rect )
  52             : area( rect )
  53         {
  54             Q_ASSERT_X( !text.isEmpty(), "TinyTextEntity", "empty string" );
  55             length = text.length();
  56             data = new QChar[ length ];
  57             std::memcpy( data, text.constData(), length * sizeof( QChar ) );
  58         }
  59
  60         ~TinyTextEntity()
  61         {
  62             delete [] data;
  63         }
  64
  65         inline QString text() const
  66         {
  67             return QString::fromRawData( data, length );
  68         }
  69
  70         inline NormalizedRect transformedArea( const QMatrix &matrix ) const
  71         {
  72             NormalizedRect transformed_area = area;
  73             transformed_area.transform( matrix );
  74             return transformed_area;
  75         }
  76
  77         NormalizedRect area;
  78
  79     private:
  80         Q_DISABLE_COPY( TinyTextEntity )
  81
  82         QChar *data;
  83         int length;
  84 };
  85
  86
  87 TextEntity::TextEntity( const QString &text, NormalizedRect *area )
  88     : m_text( text ), m_area( area ), d( 0 )
  89 {
  90 }
  91
  92 TextEntity::~TextEntity()
  93 {
  94     delete m_area;
  95 }
  96
  97 QString TextEntity::text() const
  98 {
  99     return m_text;
 100 }
 101
 102 NormalizedRect* TextEntity::area() const
 103 {
 104     return m_area;
 105 }
 106
 107 NormalizedRect TextEntity::transformedArea(const QMatrix &matrix) const
 108 {
 109     NormalizedRect transformed_area = *m_area;
 110     transformed_area.transform( matrix );
 111     return transformed_area;
 112 }
 113
 114
 115 TextPagePrivate::TextPagePrivate()
 116     : m_page( 0 )
 117 {
 118 }
 119
 120 TextPagePrivate::~TextPagePrivate()
 121 {
 122     qDeleteAll( m_searchPoints );
 123     qDeleteAll( m_words );
 124 }
 125
 126
 127 TextPage::TextPage()
 128     : d( new TextPagePrivate() )
 129 {
 130 }
 131
 132 TextPage::TextPage( const TextEntity::List &words )
 133     : d( new TextPagePrivate() )
 134 {
 135     TextEntity::List::ConstIterator it = words.constBegin(), itEnd = words.constEnd();
 136     for ( ; it != itEnd; ++it )
 137     {
 138         TextEntity *e = *it;
 139         if ( !e->text().isEmpty() )
 140             d->m_words.append( new TinyTextEntity( e->text(), *e->area() ) );
 141         delete e;
 142     }
 143 }
 144
 145 TextPage::~TextPage()
 146 {
 147     delete d;
 148 }
 149
 150 void TextPage::append( const QString &text, NormalizedRect *area )
 151 {
 152     if ( !text.isEmpty() )
 153         d->m_words.append( new TinyTextEntity( text, *area ) );
 154     delete area;
 155 }
 156
 157 RegularAreaRect * TextPage::textArea ( TextSelection * sel) const
 158 {
 159     if ( d->m_words.isEmpty() )
 160         return new RegularAreaRect();
 161
 162 /**
 163     It works like this:
 164     There are two cursors, we need to select all the text between them. The coordinates are normalised, leftTop is (0,0)
 165     rightBottom is (1,1), so for cursors start (sx,sy) and end (ex,ey) we start with finding text rectangles under those
 166     points, if not we search for the first that is to the right to it in the same baseline, if none found, then we search
 167     for the first rectangle with a baseline under the cursor, having two points that are the best rectangles to both
 168     of the cursors: (rx,ry)x(tx,ty) for start and (ux,uy)x(vx,vy) for end, we do a
 169     1. (rx,ry)x(1,ty)
 170     2. (0,ty)x(1,uy)
 171     3. (0,uy)x(vx,vy)
 172
 173     To find the closest rectangle to cursor (cx,cy) we search for a rectangle that either contains the cursor
 174     or that has a left border >= cx and bottom border >= cy.
 175 */
 176     RegularAreaRect * ret= new RegularAreaRect;
 177
 178     QMatrix matrix = d->m_page ? d->m_page->rotationMatrix() : QMatrix();
 179 #if 0
 180     int it = -1;
 181     int itB = -1;
 182     int itE = -1;
 183
 184     // ending cursor is higher than start cursor, we need to find positions in reverse
 185     NormalizedRect tmp;
 186     NormalizedRect start;
 187     NormalizedRect end;
 188
 189     NormalizedPoint startC = sel->start();
 190     double startCx = startC.x;
 191     double startCy = startC.y;
 192
 193     NormalizedPoint endC = sel->end();
 194     double endCx = endC.x;
 195     double endCy = endC.y;
 196
 197     if ( sel->direction() == 1 || ( sel->itB() == -1 && sel->direction() == 0 ) )
 198     {
 199 #ifdef DEBUG_TEXTPAGE
 200         kWarning() << "running first loop";
 201 #endif
 202         const int count = d->m_words.count();
 203         for ( it = 0; it < count; it++ )
 204         {
 205             tmp = *d->m_words[ it ]->area();
 206             if ( tmp.contains( startCx, startCy )
 207                  || ( tmp.top <= startCy && tmp.bottom >= startCy && tmp.left >= startCx )
 208                  || ( tmp.top >= startCy))
 209             {
 210                 /// we have found the (rx,ry)x(tx,ty)
 211                 itB = it;
 212 #ifdef DEBUG_TEXTPAGE
 213                 kWarning() << "start is" << itB << "count is" << d->m_words.count();
 214 #endif
 215                 break;
 216             }
 217         }
 218         sel->itB( itB );
 219     }
 220     itB = sel->itB();
 221 #ifdef DEBUG_TEXTPAGE
 222     kWarning() << "direction is" << sel->direction();
 223     kWarning() << "reloaded start is" << itB << "against" << sel->itB();
 224 #endif
 225     if ( sel->direction() == 0 || ( sel->itE() == -1 && sel->direction() == 1 ) )
 226     {
 227 #ifdef DEBUG_TEXTPAGE
 228         kWarning() << "running second loop";
 229 #endif
 230         for ( it = d->m_words.count() - 1; it >= itB; it-- )
 231         {
 232             tmp = *d->m_words[ it ]->area();
 233             if ( tmp.contains( endCx, endCy )
 234                  || ( tmp.top <= endCy && tmp.bottom >= endCy && tmp.right <= endCx )
 235                  || ( tmp.bottom <= endCy ) )
 236             {
 237                 /// we have found the (ux,uy)x(vx,vy)
 238                 itE = it;
 239 #ifdef DEBUG_TEXTPAGE
 240                 kWarning() << "ending is" << itE << "count is" << d->m_words.count();
 241                 kWarning() << "conditions" << tmp.contains( endCx, endCy ) << " "
 242                   << ( tmp.top <= endCy && tmp.bottom >= endCy && tmp.right <= endCx ) << " " <<
 243                   ( tmp.top >= endCy);
 244 #endif
 245                 break;
 246             }
 247         }
 248         sel->itE( itE );
 249     }
 250 #ifdef DEBUG_TEXTPAGE
 251     kWarning() << "reloaded ending is" << itE << "against" << sel->itE();
 252 #endif
 253
 254     if ( sel->itB() != -1 && sel->itE() != -1 )
 255     {
 256         start = *d->m_words[ sel->itB() ]->area();
 257         end = *d->m_words[ sel->itE() ]->area();
 258
 259         NormalizedRect first, second, third;
 260         /// finding out if there is more than one baseline between them is a hard and discussable task
 261         /// we will create a rectangle (rx,0)x(tx,1) and will check how many times does it intersect the
 262         /// areas, if more than one -> we have a three or over line selection
 263         first = start;
 264         second.top = start.bottom;
 265         first.right = second.right = 1;
 266         third = end;
 267         third.left = second.left = 0;
 268         second.bottom = end.top;
 269         int selMax = qMax( sel->itB(), sel->itE() );
 270         for ( it = qMin( sel->itB(), sel->itE() ); it <= selMax; ++it )
 271         {
 272             tmp = *d->m_words[ it ]->area();
 273             if ( tmp.intersects( &first ) || tmp.intersects( &second ) || tmp.intersects( &third ) )
 274                 ret->appendShape( d->m_words.at( it )->transformedArea( matrix ) );
 275         }
 276     }
 277 #else
 278     NormalizedRect tmp;
 279
 280     NormalizedPoint startC = sel->start();
 281     double startCx = startC.x;
 282     double startCy = startC.y;
 283
 284     NormalizedPoint endC = sel->end();
 285     double endCx = endC.x;
 286     double endCy = endC.y;
 287
 288     TextList::ConstIterator it = d->m_words.constBegin(), itEnd = d->m_words.constEnd();
 289     MergeSide side = d->m_page ? (MergeSide)d->m_page->m_page->totalOrientation() : MergeRight;
 290     for ( ; it != itEnd; ++it )
 291     {
 292         tmp = (*it)->area;
 293         if ( ( tmp.top > startCy || ( tmp.bottom > startCy && tmp.right > startCx ) )
 294              && ( tmp.bottom < endCy || ( tmp.top < endCy && tmp.left < endCx ) ) )
 295         {
 296             ret->appendShape( (*it)->transformedArea( matrix ), side );
 297         }
 298     }
 299 #endif
 300
 301     return ret;
 302 }
 303
 304
 305 RegularAreaRect* TextPage::findText( int searchID, const QString &query, SearchDirection direct,
 306                                      Qt::CaseSensitivity caseSensitivity, const RegularAreaRect *area )
 307 {
 308     SearchDirection dir=direct;
 309     // invalid search request
 310     if ( d->m_words.isEmpty() || query.isEmpty() || ( area && area->isNull() ) )
 311         return 0;
 312     TextList::ConstIterator start;
 313     TextList::ConstIterator end;
 314     QMap< int, SearchPoint* >::const_iterator sIt = d->m_searchPoints.constFind( searchID );
 315     if ( sIt == d->m_searchPoints.constEnd() )
 316     {
 317         // if no previous run of this search is found, then set it to start
 318         // from the beginning (respecting the search direction)
 319         if ( dir == NextResult )
 320             dir = FromTop;
 321         else if ( dir == PreviousResult )
 322             dir = FromBottom;
 323     }
 324     bool forward = true;
 325     switch ( dir )
 326     {
 327         case FromTop:
 328             start = d->m_words.constBegin();
 329             end = d->m_words.constEnd();
 330             break;
 331         case FromBottom:
 332             start = d->m_words.constEnd();
 333             end = d->m_words.constBegin();
 334             Q_ASSERT( start != end );
 335             // we can safely go one step back, as we already checked
 336             // that the list is not empty
 337             --start;
 338             forward = false;
 339             break;
 340         case NextResult:
 341             start = (*sIt)->it_end;
 342             end = d->m_words.constEnd();
 343             if ( ( start + 1 ) != end )
 344                 ++start;
 345             break;
 346         case PreviousResult:
 347             start = (*sIt)->it_begin;
 348             end = d->m_words.constBegin();
 349             if ( start != end )
 350                 --start;
 351             forward = false;
 352             break;
 353     };
 354     RegularAreaRect* ret = 0;
 355     if ( forward )
 356     {
 357         ret = d->findTextInternalForward( searchID, query, caseSensitivity, start, end );
 358     }
 359     else
 360     {
 361         ret = d->findTextInternalBackward( searchID, query, caseSensitivity, start, end );
 362     }
 363     return ret;
 364 }
 365
 366
 367 RegularAreaRect* TextPagePrivate::findTextInternalForward( int searchID, const QString &_query,
 368                                                              Qt::CaseSensitivity caseSensitivity,
 369                                                              const TextList::ConstIterator &start,
 370                                                              const TextList::ConstIterator &end )
 371 {
 372     QMatrix matrix = m_page ? m_page->rotationMatrix() : QMatrix();
 373
 374     RegularAreaRect* ret=new RegularAreaRect;
 375     QString query = (caseSensitivity == Qt::CaseSensitive) ? _query : _query.toLower();
 376
 377     // j is the current position in our query
 378     // len is the length of the string in TextEntity
 379     // queryLeft is the length of the query we have left
 380     const TinyTextEntity* curEntity = 0;
 381     int j=0, len=0, queryLeft=query.length();
 382     int offset = 0;
 383     bool haveMatch=false;
 384     bool offsetMoved = false;
 385     TextList::ConstIterator it = start;
 386     TextList::ConstIterator it_begin;
 387     for ( ; it != end; ++it )
 388     {
 389         curEntity = *it;
 390         const QString &str = curEntity->text();
 391         if ( !offsetMoved && ( it == start ) )
 392         {
 393             if ( m_searchPoints.contains( searchID ) )
 394             {
 395                 offset = qMax( m_searchPoints[ searchID ]->offset_end, 0 );
 396             }
 397             offsetMoved = true;
 398         }
 399         {
 400             len=str.length();
 401             int min=qMin(queryLeft,len);
 402 #ifdef DEBUG_TEXTPAGE
 403             kDebug(OkularDebug) << str.mid(offset,min) << ":" << _query.mid(j,min);
 404 #endif
 405             // we have equal (or less than) area of the query left as the length of the current
 406             // entity
 407
 408             if ((caseSensitivity == Qt::CaseSensitive)
 409                 ? (str.mid(offset,min) != query.mid(j,min))
 410                 : (str.mid(offset,min).toLower() != query.mid(j,min))
 411                 )
 412             {
 413                     // we not have matched
 414                     // this means we do not have a complete match
 415                     // we need to get back to query start
 416                     // and continue the search from this place
 417                     haveMatch=false;
 418                     ret->clear();
 419 #ifdef DEBUG_TEXTPAGE
 420             kDebug(OkularDebug) << "\tnot matched";
 421 #endif
 422                     j=0;
 423                     offset = 0;
 424                     queryLeft=query.length();
 425                     it_begin = TextList::ConstIterator();
 426             }
 427             else
 428             {
 429                     // we have a match
 430                     // move the current position in the query
 431                     // to the position after the length of this string
 432                     // we matched
 433                     // substract the length of the current entity from
 434                     // the left length of the query
 435 #ifdef DEBUG_TEXTPAGE
 436             kDebug(OkularDebug) << "\tmatched";
 437 #endif
 438                     haveMatch=true;
 439                     ret->append( curEntity->transformedArea( matrix ) );
 440                     j+=min;
 441                     queryLeft-=min;
 442                     if ( it_begin == TextList::ConstIterator() )
 443                     {
 444                         it_begin = it;
 445                     }
 446             }
 447         }
 448
 449         if (haveMatch && queryLeft==0 && j==query.length())
 450         {
 451             // save or update the search point for the current searchID
 452             if ( !m_searchPoints.contains( searchID ) )
 453             {
 454                 SearchPoint* newsp = new SearchPoint;
 455                 m_searchPoints.insert( searchID, newsp );
 456             }
 457             SearchPoint* sp = m_searchPoints[ searchID ];
 458             sp->it_begin = it_begin;
 459             sp->it_end = it;
 460             sp->offset_begin = j;
 461             sp->offset_end = j + qMin( queryLeft, len );
 462             ret->simplify();
 463             return ret;
 464         }
 465     }
 466     // end of loop - it means that we've ended the textentities
 467     if ( m_searchPoints.contains( searchID ) )
 468     {
 469         SearchPoint* sp = m_searchPoints[ searchID ];
 470         m_searchPoints.remove( searchID );
 471         delete sp;
 472     }
 473     delete ret;
 474     return 0;
 475 }
 476
 477 RegularAreaRect* TextPagePrivate::findTextInternalBackward( int searchID, const QString &_query,
 478                                                             Qt::CaseSensitivity caseSensitivity,
 479                                                             const TextList::ConstIterator &start,
 480                                                             const TextList::ConstIterator &end )
 481 {
 482     QMatrix matrix = m_page ? m_page->rotationMatrix() : QMatrix();
 483
 484     RegularAreaRect* ret=new RegularAreaRect;
 485     const QString query = (caseSensitivity == Qt::CaseSensitive) ? _query : _query.toLower();
 486
 487     // j is the current position in our query
 488     // len is the length of the string in TextEntity
 489     // queryLeft is the length of the query we have left
 490     const TinyTextEntity* curEntity = 0;
 491     int j=query.length() - 1, len=0, queryLeft=query.length();
 492     int offset = 0;
 493     bool haveMatch=false;
 494     bool dontIncrement=false;
 495     bool offsetMoved = false;
 496     TextList::ConstIterator it = start;
 497     TextList::ConstIterator it_begin;
 498     while ( true )
 499     {
 500         curEntity = *it;
 501         const QString &str = curEntity->text();
 502         if ( !offsetMoved && ( it == start ) )
 503         {
 504             if ( m_searchPoints.contains( searchID ) )
 505             {
 506                 offset = qMax( m_searchPoints[ searchID ]->offset_begin, 0 );
 507             }
 508             offsetMoved = true;
 509         }
 510         if ( query.at(j).isSpace() )
 511         {
 512             // lets match newline as a space
 513 #ifdef DEBUG_TEXTPAGE
 514             kDebug(OkularDebug) << "newline or space";
 515 #endif
 516             j--;
 517             queryLeft--;
 518             // since we do not really need to increment this after this
 519             // run of the loop finishes because we are not comparing it
 520             // to any entity, rather we are deducing a situation in a document
 521             dontIncrement=true;
 522         }
 523         else
 524         {
 525             dontIncrement=false;
 526             len=str.length();
 527             int min=qMin(queryLeft,len);
 528 #ifdef DEBUG_TEXTPAGE
 529             kDebug(OkularDebug) << str.right(min) << " : " << _query.mid(j-min+1,min);
 530 #endif
 531             // we have equal (or less than) area of the query left as the length of the current
 532             // entity
 533
 534             if ((caseSensitivity == Qt::CaseSensitive)
 535                 ? (str.right(min) != query.mid(j-min+1,min))
 536                 : (str.right(min).toLower() != query.mid(j-min+1,min))
 537                 )
 538             {
 539                     // we not have matched
 540                     // this means we do not have a complete match
 541                     // we need to get back to query start
 542                     // and continue the search from this place
 543                     haveMatch=false;
 544                     ret->clear();
 545 #ifdef DEBUG_TEXTPAGE
 546                     kDebug(OkularDebug) << "\tnot matched";
 547 #endif
 548                     j=query.length() - 1;
 549                     offset = 0;
 550                     queryLeft=query.length();
 551                     it_begin = TextList::ConstIterator();
 552             }
 553             else
 554             {
 555                     // we have a match
 556                     // move the current position in the query
 557                     // to the position after the length of this string
 558                     // we matched
 559                     // substract the length of the current entity from
 560                     // the left length of the query
 561 #ifdef DEBUG_TEXTPAGE
 562                     kDebug(OkularDebug) << "\tmatched";
 563 #endif
 564                     haveMatch=true;
 565                     ret->append( curEntity->transformedArea( matrix ) );
 566                     j-=min;
 567                     queryLeft-=min;
 568                     if ( it_begin == TextList::ConstIterator() )
 569                     {
 570                         it_begin = it;
 571                     }
 572             }
 573         }
 574
 575         if (haveMatch && queryLeft==0 && j<0)
 576         {
 577             // save or update the search point for the current searchID
 578             QMap< int, SearchPoint* >::iterator sIt = m_searchPoints.find( searchID );
 579             if ( sIt == m_searchPoints.end() )
 580             {
 581                 sIt = m_searchPoints.insert( searchID, new SearchPoint );
 582             }
 583             SearchPoint* sp = *sIt;
 584             sp->it_begin = it;
 585             sp->it_end = it_begin;
 586             sp->offset_begin = j;
 587             sp->offset_end = j + qMin( queryLeft, len );
 588             ret->simplify();
 589             return ret;
 590         }
 591         if ( it == end )
 592             break;
 593         else
 594             --it;
 595     }
 596     // end of loop - it means that we've ended the textentities
 597     QMap< int, SearchPoint* >::iterator sIt = m_searchPoints.find( searchID );
 598     if ( sIt != m_searchPoints.end() )
 599     {
 600         SearchPoint* sp = *sIt;
 601         m_searchPoints.erase( sIt );
 602         delete sp;
 603     }
 604     delete ret;
 605     return 0;
 606 }
 607
 608 QString TextPage::text(const RegularAreaRect *area) const
 609 {
 610     if ( area && area->isNull() )
 611         return QString();
 612
 613     TextList::ConstIterator it = d->m_words.constBegin(), itEnd = d->m_words.constEnd();
 614     QString ret;
 615     if ( area )
 616     {
 617         for ( ; it != itEnd; ++it )
 618         {
 619             if ( area->intersects( (*it)->area ) )
 620             {
 621                 ret += (*it)->text();
 622             }
 623         }
 624     }
 625     else
 626     {
 627         for ( ; it != itEnd; ++it )
 628             ret += (*it)->text();
 629     }
 630     return ret;
 631 }