sw/source/core/doc/doccomp.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: doccomp.cxx,v $
  10  * $Revision: 1.24 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_sw.hxx"
  33
  34
  35 #include <hintids.hxx>
  36 #include <tools/list.hxx>
  37 #include <vcl/vclenum.hxx>
  38 #include <svx/crsditem.hxx>
  39 #include <svx/colritem.hxx>
  40 #include <svx/boxitem.hxx>
  41 #include <svx/udlnitem.hxx>
  42 #include <doc.hxx>
  43 #include <docary.hxx>
  44 #include <pam.hxx>
  45 #include <ndtxt.hxx>
  46 #include <redline.hxx>
  47 #include <undobj.hxx>
  48 #include <section.hxx>
  49 #include <tox.hxx>
  50 #include <docsh.hxx>
  51
  52 #include <com/sun/star/document/XDocumentPropertiesSupplier.hpp>
  53 #include <com/sun/star/document/XDocumentProperties.hpp>
  54
  55 using namespace ::com::sun::star;
  56
  57
  58 class CompareLine
  59 {
  60 public:
  61     CompareLine() {}
  62     virtual ~CompareLine();
  63
  64     virtual ULONG GetHashValue() const = 0;
  65     virtual BOOL Compare( const CompareLine& rLine ) const = 0;
  66 };
  67
  68 DECLARE_LIST( CompareList, CompareLine* )
  69
  70 class CompareData
  71 {
  72     ULONG* pIndex;
  73     BOOL* pChangedFlag;
  74
  75 protected:
  76     CompareList aLines;
  77     ULONG nSttLineNum;
  78
  79     // Anfang und Ende beschneiden und alle anderen in das
  80     // LinesArray setzen
  81     virtual void CheckRanges( CompareData& ) = 0;
  82
  83 public:
  84     CompareData();
  85     virtual ~CompareData();
  86
  87     // gibt es unterschiede?
  88     BOOL HasDiffs( const CompareData& rData ) const;
  89
  90     // startet das Vergleichen und Erzeugen der Unterschiede zweier
  91     // Dokumente
  92     void CompareLines( CompareData& rData );
  93     // lasse die Unterschiede anzeigen - ruft die beiden Methoden
  94     // ShowInsert / ShowDelete. Diese bekommen die Start und EndLine-Nummer
  95     // uebergeben. Die Abbildung auf den tatsaechline Inhalt muss die
  96     // Ableitung uebernehmen!
  97     ULONG ShowDiffs( const CompareData& rData );
  98
  99     virtual void ShowInsert( ULONG nStt, ULONG nEnd );
 100     virtual void ShowDelete( const CompareData& rData, ULONG nStt,
 101                                 ULONG nEnd, ULONG nInsPos );
 102     virtual void CheckForChangesInLine( const CompareData& rData,
 103                                     ULONG& nStt, ULONG& nEnd,
 104                                     ULONG& nThisStt, ULONG& nThisEnd );
 105
 106     // Eindeutigen Index fuer eine Line setzen. Gleiche Lines haben den
 107     // selben Index; auch in den anderen CompareData!
 108     void SetIndex( ULONG nLine, ULONG nIndex );
 109     ULONG GetIndex( ULONG nLine ) const
 110         { return nLine < aLines.Count() ? pIndex[ nLine ] : 0; }
 111
 112     // setze/erfrage ob eine Zeile veraendert ist
 113     void SetChanged( ULONG nLine, BOOL bFlag = TRUE );
 114     BOOL GetChanged( ULONG nLine ) const
 115         {
 116             return (pChangedFlag && nLine < aLines.Count())
 117                 ? pChangedFlag[ nLine ]
 118                 : 0;
 119         }
 120
 121     ULONG GetLineCount() const          { return aLines.Count(); }
 122     ULONG GetLineOffset() const         { return nSttLineNum; }
 123     const CompareLine* GetLine( ULONG nLine ) const
 124             { return aLines.GetObject( nLine ); }
 125     void InsertLine( CompareLine* pLine )
 126         { aLines.Insert( pLine, LIST_APPEND ); }
 127 };
 128
 129 class Hash
 130 {
 131     struct _HashData
 132     {
 133         ULONG nNext, nHash;
 134         const CompareLine* pLine;
 135
 136         _HashData()
 137             : nNext( 0 ), nHash( 0 ), pLine(0) {}
 138     };
 139
 140     ULONG* pHashArr;
 141     _HashData* pDataArr;
 142     ULONG nCount, nPrime;
 143
 144 public:
 145     Hash( ULONG nSize );
 146     ~Hash();
 147
 148     void CalcHashValue( CompareData& rData );
 149
 150     ULONG GetCount() const { return nCount; }
 151 };
 152
 153 class Compare
 154 {
 155 public:
 156     class MovedData
 157     {
 158         ULONG* pIndex;
 159         ULONG* pLineNum;
 160         ULONG nCount;
 161
 162     public:
 163         MovedData( CompareData& rData, sal_Char* pDiscard );
 164         ~MovedData();
 165
 166         ULONG GetIndex( ULONG n ) const { return pIndex[ n ]; }
 167         ULONG GetLineNum( ULONG n ) const { return pLineNum[ n ]; }
 168         ULONG GetCount() const { return nCount; }
 169     };
 170
 171 private:
 172     // Suche die verschobenen Lines
 173     class CompareSequence
 174     {
 175         CompareData &rData1, &rData2;
 176         const MovedData &rMoved1, &rMoved2;
 177         long *pMemory, *pFDiag, *pBDiag;
 178
 179         void Compare( ULONG nStt1, ULONG nEnd1, ULONG nStt2, ULONG nEnd2 );
 180         ULONG CheckDiag( ULONG nStt1, ULONG nEnd1,
 181                         ULONG nStt2, ULONG nEnd2, ULONG* pCost );
 182     public:
 183         CompareSequence( CompareData& rData1, CompareData& rData2,
 184                         const MovedData& rD1, const MovedData& rD2 );
 185         ~CompareSequence();
 186     };
 187
 188
 189     static void CountDifference( const CompareData& rData, ULONG* pCounts );
 190     static void SetDiscard( const CompareData& rData,
 191                             sal_Char* pDiscard, ULONG* pCounts );
 192     static void CheckDiscard( ULONG nLen, sal_Char* pDiscard );
 193     static ULONG SetChangedFlag( CompareData& rData, sal_Char* pDiscard, int bFirst );
 194     static void ShiftBoundaries( CompareData& rData1, CompareData& rData2 );
 195
 196 public:
 197     Compare( ULONG nDiff, CompareData& rData1, CompareData& rData2 );
 198 };
 199
 200 // ====================================================================
 201
 202 CompareLine::~CompareLine() {}
 203
 204 // ----------------------------------------------------------------------
 205
 206 CompareData::CompareData()
 207     : pIndex( 0 ), pChangedFlag( 0 ), nSttLineNum( 0 )
 208 {
 209 }
 210
 211 CompareData::~CompareData()
 212 {
 213     delete[] pIndex;
 214     delete[] pChangedFlag;
 215 }
 216
 217 void CompareData::SetIndex( ULONG nLine, ULONG nIndex )
 218 {
 219     if( !pIndex )
 220     {
 221         pIndex = new ULONG[ aLines.Count() ];
 222         memset( pIndex, 0, aLines.Count() * sizeof( ULONG ) );
 223     }
 224     if( nLine < aLines.Count() )
 225         pIndex[ nLine ] = nIndex;
 226 }
 227
 228 void CompareData::SetChanged( ULONG nLine, BOOL bFlag )
 229 {
 230     if( !pChangedFlag )
 231     {
 232         pChangedFlag = new BOOL[ aLines.Count() +1 ];
 233         memset( pChangedFlag, 0, aLines.Count() +1 * sizeof( BOOL ) );
 234     }
 235     if( nLine < aLines.Count() )
 236         pChangedFlag[ nLine ] = bFlag;
 237 }
 238
 239 void CompareData::CompareLines( CompareData& rData )
 240 {
 241     CheckRanges( rData );
 242
 243     ULONG nDifferent;
 244     {
 245         Hash aH( GetLineCount() + rData.GetLineCount() + 1 );
 246         aH.CalcHashValue( *this );
 247         aH.CalcHashValue( rData );
 248         nDifferent = aH.GetCount();
 249     }
 250     {
 251         Compare aComp( nDifferent, *this, rData );
 252     }
 253 }
 254
 255 ULONG CompareData::ShowDiffs( const CompareData& rData )
 256 {
 257     ULONG nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
 258     ULONG nStt1 = 0, nStt2 = 0;
 259     ULONG nCnt = 0;
 260
 261     while( nStt1 < nLen1 || nStt2 < nLen2 )
 262     {
 263         if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
 264         {
 265             ULONG nSav1 = nStt1, nSav2 = nStt2;
 266             while( nStt1 < nLen1 && rData.GetChanged( nStt1 )) ++nStt1;
 267             while( nStt2 < nLen2 && GetChanged( nStt2 )) ++nStt2;
 268
 269             // rData ist das Original,
 270             // this ist das, in das die Veraenderungen sollen
 271             if( nSav2 != nStt2 && nSav1 != nStt1 )
 272                 CheckForChangesInLine( rData, nSav1, nStt1, nSav2, nStt2 );
 273
 274             if( nSav2 != nStt2 )
 275                 ShowInsert( nSav2, nStt2 );
 276
 277             if( nSav1 != nStt1 )
 278                 ShowDelete( rData, nSav1, nStt1, nStt2 );
 279             ++nCnt;
 280         }
 281         ++nStt1, ++nStt2;
 282     }
 283     return nCnt;
 284 }
 285
 286 BOOL CompareData::HasDiffs( const CompareData& rData ) const
 287 {
 288     BOOL bRet = FALSE;
 289     ULONG nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
 290     ULONG nStt1 = 0, nStt2 = 0;
 291
 292     while( nStt1 < nLen1 || nStt2 < nLen2 )
 293     {
 294         if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
 295         {
 296             bRet = TRUE;
 297             break;
 298         }
 299         ++nStt1, ++nStt2;
 300     }
 301     return bRet;
 302 }
 303
 304 void CompareData::ShowInsert( ULONG, ULONG )
 305 {
 306 }
 307
 308 void CompareData::ShowDelete( const CompareData&, ULONG, ULONG, ULONG )
 309 {
 310 }
 311
 312 void CompareData::CheckForChangesInLine( const CompareData& ,
 313                                     ULONG&, ULONG&, ULONG&, ULONG& )
 314 {
 315 }
 316
 317 // ----------------------------------------------------------------------
 318
 319 Hash::Hash( ULONG nSize )
 320     : nCount( 1 )
 321 {
 322
 323 static const ULONG primes[] =
 324 {
 325   509,
 326   1021,
 327   2039,
 328   4093,
 329   8191,
 330   16381,
 331   32749,
 332   65521,
 333   131071,
 334   262139,
 335   524287,
 336   1048573,
 337   2097143,
 338   4194301,
 339   8388593,
 340   16777213,
 341   33554393,
 342   67108859,                     /* Preposterously large . . . */
 343   134217689,
 344   268435399,
 345   536870909,
 346   1073741789,
 347   2147483647,
 348   0
 349 };
 350     int i;
 351
 352     pDataArr = new _HashData[ nSize ];
 353     pDataArr[0].nNext = 0;
 354     pDataArr[0].nHash = 0,
 355     pDataArr[0].pLine = 0;
 356
 357     for( i = 0; primes[i] < nSize / 3;  i++)
 358         if( !primes[i] )
 359         {
 360             pHashArr = 0;
 361             return;
 362         }
 363     nPrime = primes[ i ];
 364     pHashArr = new ULONG[ nPrime ];
 365     memset( pHashArr, 0, nPrime * sizeof( ULONG ) );
 366 }
 367
 368 Hash::~Hash()
 369 {
 370     delete[] pHashArr;
 371     delete[] pDataArr;
 372 }
 373
 374 void Hash::CalcHashValue( CompareData& rData )
 375 {
 376     if( pHashArr )
 377     {
 378         for( ULONG n = 0; n < rData.GetLineCount(); ++n )
 379         {
 380             const CompareLine* pLine = rData.GetLine( n );
 381             ASSERT( pLine, "wo ist die Line?" );
 382             ULONG nH = pLine->GetHashValue();
 383
 384             ULONG* pFound = &pHashArr[ nH % nPrime ];
 385             ULONG i;
 386             for( i = *pFound;  ;  i = pDataArr[i].nNext )
 387                 if( !i )
 388                 {
 389                     i = nCount++;
 390                     pDataArr[i].nNext = *pFound;
 391                     pDataArr[i].nHash = nH;
 392                     pDataArr[i].pLine = pLine;
 393                     *pFound = i;
 394                     break;
 395                 }
 396                 else if( pDataArr[i].nHash == nH &&
 397                         pDataArr[i].pLine->Compare( *pLine ))
 398                     break;
 399
 400             rData.SetIndex( n, i );
 401         }
 402     }
 403 }
 404
 405 // ----------------------------------------------------------------------
 406
 407 Compare::Compare( ULONG nDiff, CompareData& rData1, CompareData& rData2 )
 408 {
 409     MovedData *pMD1, *pMD2;
 410     // Suche die unterschiedlichen Lines
 411     {
 412         sal_Char* pDiscard1 = new sal_Char[ rData1.GetLineCount() ];
 413         sal_Char* pDiscard2 = new sal_Char[ rData2.GetLineCount() ];
 414
 415         ULONG* pCount1 = new ULONG[ nDiff ];
 416         ULONG* pCount2 = new ULONG[ nDiff ];
 417         memset( pCount1, 0, nDiff * sizeof( ULONG ));
 418         memset( pCount2, 0, nDiff * sizeof( ULONG ));
 419
 420         // stelle fest, welche Indizies in den CompareData mehrfach vergeben wurden
 421         CountDifference( rData1, pCount1 );
 422         CountDifference( rData2, pCount2 );
 423
 424         // alle die jetzt nur einmal vorhanden sind, sind eingefuegt oder
 425         // geloescht worden. Alle die im anderen auch vorhanden sind, sind
 426         // verschoben worden
 427         SetDiscard( rData1, pDiscard1, pCount2 );
 428         SetDiscard( rData2, pDiscard2, pCount1 );
 429
 430         // die Arrays koennen wir wieder vergessen
 431         delete pCount1; delete pCount2;
 432
 433         CheckDiscard( rData1.GetLineCount(), pDiscard1 );
 434         CheckDiscard( rData2.GetLineCount(), pDiscard2 );
 435
 436         pMD1 = new MovedData( rData1, pDiscard1 );
 437         pMD2 = new MovedData( rData2, pDiscard2 );
 438
 439         // die Arrays koennen wir wieder vergessen
 440         delete pDiscard1; delete pDiscard2;
 441     }
 442
 443     {
 444         CompareSequence aTmp( rData1, rData2, *pMD1, *pMD2 );
 445     }
 446
 447     ShiftBoundaries( rData1, rData2 );
 448
 449     delete pMD1;
 450     delete pMD2;
 451 }
 452
 453
 454
 455 void Compare::CountDifference( const CompareData& rData, ULONG* pCounts )
 456 {
 457     ULONG nLen = rData.GetLineCount();
 458     for( ULONG n = 0; n < nLen; ++n )
 459     {
 460         ULONG nIdx = rData.GetIndex( n );
 461         ++pCounts[ nIdx ];
 462     }
 463 }
 464
 465 void Compare::SetDiscard( const CompareData& rData,
 466                             sal_Char* pDiscard, ULONG* pCounts )
 467 {
 468     ULONG nLen = rData.GetLineCount();
 469
 470     // berechne Max in Abhanegigkeit zur LineAnzahl
 471     USHORT nMax = 5;
 472     ULONG n;
 473
 474     for( n = nLen / 64; ( n = n >> 2 ) > 0; )
 475         nMax <<= 1;
 476
 477     for( n = 0; n < nLen; ++n )
 478     {
 479         ULONG nIdx = rData.GetIndex( n );
 480         if( nIdx )
 481         {
 482             nIdx = pCounts[ nIdx ];
 483             pDiscard[ n ] = !nIdx ? 1 : nIdx > nMax ? 2 : 0;
 484         }
 485         else
 486             pDiscard[ n ] = 0;
 487     }
 488 }
 489
 490 void Compare::CheckDiscard( ULONG nLen, sal_Char* pDiscard )
 491 {
 492     for( ULONG n = 0; n < nLen; ++n )
 493     {
 494         if( 2 == pDiscard[ n ] )
 495             pDiscard[n] = 0;
 496         else if( pDiscard[ n ] )
 497         {
 498             ULONG j;
 499             ULONG length;
 500             ULONG provisional = 0;
 501
 502             /* Find end of this run of discardable lines.
 503                 Count how many are provisionally discardable.  */
 504             for (j = n; j < nLen; j++)
 505             {
 506                 if( !pDiscard[j] )
 507                     break;
 508                 if( 2 == pDiscard[j] )
 509                     ++provisional;
 510             }
 511
 512             /* Cancel provisional discards at end, and shrink the run.  */
 513             while( j > n && 2 == pDiscard[j - 1] )
 514                 pDiscard[ --j ] = 0, --provisional;
 515
 516             /* Now we have the length of a run of discardable lines
 517                whose first and last are not provisional.  */
 518             length = j - n;
 519
 520             /* If 1/4 of the lines in the run are provisional,
 521                cancel discarding of all provisional lines in the run.  */
 522             if (provisional * 4 > length)
 523             {
 524                 while (j > n)
 525                     if (pDiscard[--j] == 2)
 526                         pDiscard[j] = 0;
 527             }
 528             else
 529             {
 530                 ULONG consec;
 531                 ULONG minimum = 1;
 532                 ULONG tem = length / 4;
 533
 534                 /* MINIMUM is approximate square root of LENGTH/4.
 535                    A subrun of two or more provisionals can stand
 536                    when LENGTH is at least 16.
 537                    A subrun of 4 or more can stand when LENGTH >= 64.  */
 538                 while ((tem = tem >> 2) > 0)
 539                     minimum *= 2;
 540                 minimum++;
 541
 542                 /* Cancel any subrun of MINIMUM or more provisionals
 543                    within the larger run.  */
 544                 for (j = 0, consec = 0; j < length; j++)
 545                     if (pDiscard[n + j] != 2)
 546                         consec = 0;
 547                     else if (minimum == ++consec)
 548                         /* Back up to start of subrun, to cancel it all.  */
 549                         j -= consec;
 550                     else if (minimum < consec)
 551                         pDiscard[n + j] = 0;
 552
 553                 /* Scan from beginning of run
 554                    until we find 3 or more nonprovisionals in a row
 555                    or until the first nonprovisional at least 8 lines in.
 556                    Until that point, cancel any provisionals.  */
 557                 for (j = 0, consec = 0; j < length; j++)
 558                 {
 559                     if (j >= 8 && pDiscard[n + j] == 1)
 560                         break;
 561                     if (pDiscard[n + j] == 2)
 562                         consec = 0, pDiscard[n + j] = 0;
 563                     else if (pDiscard[n + j] == 0)
 564                         consec = 0;
 565                     else
 566                         consec++;
 567                     if (consec == 3)
 568                         break;
 569                 }
 570
 571                 /* I advances to the last line of the run.  */
 572                 n += length - 1;
 573
 574                 /* Same thing, from end.  */
 575                 for (j = 0, consec = 0; j < length; j++)
 576                 {
 577                     if (j >= 8 && pDiscard[n - j] == 1)
 578                         break;
 579                     if (pDiscard[n - j] == 2)
 580                         consec = 0, pDiscard[n - j] = 0;
 581                     else if (pDiscard[n - j] == 0)
 582                         consec = 0;
 583                     else
 584                         consec++;
 585                     if (consec == 3)
 586                         break;
 587                 }
 588             }
 589         }
 590     }
 591 }
 592
 593 // ----------------------------------------------------------------------
 594
 595 Compare::MovedData::MovedData( CompareData& rData, sal_Char* pDiscard )
 596     : pIndex( 0 ), pLineNum( 0 ), nCount( 0 )
 597 {
 598     ULONG nLen = rData.GetLineCount();
 599     ULONG n;
 600
 601     for( n = 0; n < nLen; ++n )
 602         if( pDiscard[ n ] )
 603             rData.SetChanged( n );
 604         else
 605             ++nCount;
 606
 607     if( nCount )
 608     {
 609         pIndex = new ULONG[ nCount ];
 610         pLineNum = new ULONG[ nCount ];
 611
 612         for( n = 0, nCount = 0; n < nLen; ++n )
 613             if( !pDiscard[ n ] )
 614             {
 615                 pIndex[ nCount ] = rData.GetIndex( n );
 616                 pLineNum[ nCount++ ] = n;
 617             }
 618     }
 619 }
 620
 621 Compare::MovedData::~MovedData()
 622 {
 623     delete pIndex;
 624     delete pLineNum;
 625 }
 626
 627 // ----------------------------------------------------------------------
 628
 629     // Suche die verschobenen Lines
 630 Compare::CompareSequence::CompareSequence(
 631                             CompareData& rD1, CompareData& rD2,
 632                             const MovedData& rMD1, const MovedData& rMD2 )
 633     : rData1( rD1 ), rData2( rD2 ), rMoved1( rMD1 ), rMoved2( rMD2 )
 634 {
 635     ULONG nSize = rMD1.GetCount() + rMD2.GetCount() + 3;
 636     pMemory = new long[ nSize * 2 ];
 637     pFDiag = pMemory + ( rMD2.GetCount() + 1 );
 638     pBDiag = pMemory + ( nSize + rMD2.GetCount() + 1 );
 639
 640     Compare( 0, rMD1.GetCount(), 0, rMD2.GetCount() );
 641 }
 642
 643 Compare::CompareSequence::~CompareSequence()
 644 {
 645     delete pMemory;
 646 }
 647
 648 void Compare::CompareSequence::Compare( ULONG nStt1, ULONG nEnd1,
 649                                         ULONG nStt2, ULONG nEnd2 )
 650 {
 651     /* Slide down the bottom initial diagonal. */
 652     while( nStt1 < nEnd1 && nStt2 < nEnd2 &&
 653         rMoved1.GetIndex( nStt1 ) == rMoved2.GetIndex( nStt2 ))
 654         ++nStt1, ++nStt2;
 655
 656     /* Slide up the top initial diagonal. */
 657     while( nEnd1 > nStt1 && nEnd2 > nStt2 &&
 658         rMoved1.GetIndex( nEnd1 - 1 ) == rMoved2.GetIndex( nEnd2 - 1 ))
 659         --nEnd1, --nEnd2;
 660
 661     /* Handle simple cases. */
 662     if( nStt1 == nEnd1 )
 663         while( nStt2 < nEnd2 )
 664             rData2.SetChanged( rMoved2.GetLineNum( nStt2++ ));
 665
 666     else if (nStt2 == nEnd2)
 667         while (nStt1 < nEnd1)
 668             rData1.SetChanged( rMoved1.GetLineNum( nStt1++ ));
 669
 670     else
 671     {
 672         ULONG c, d, b;
 673
 674         /* Find a point of correspondence in the middle of the files.  */
 675
 676         d = CheckDiag( nStt1, nEnd1, nStt2, nEnd2, &c );
 677         b = pBDiag[ d ];
 678
 679         if( 1 != c )
 680         {
 681             /* Use that point to split this problem into two subproblems.  */
 682             Compare( nStt1, b, nStt2, b - d );
 683             /* This used to use f instead of b,
 684                but that is incorrect!
 685                It is not necessarily the case that diagonal d
 686                has a snake from b to f.  */
 687             Compare( b, nEnd1, b - d, nEnd2 );
 688         }
 689     }
 690 }
 691
 692 ULONG Compare::CompareSequence::CheckDiag( ULONG nStt1, ULONG nEnd1,
 693                                     ULONG nStt2, ULONG nEnd2, ULONG* pCost )
 694 {
 695     const long dmin = nStt1 - nEnd2;    /* Minimum valid diagonal. */
 696     const long dmax = nEnd1 - nStt2;    /* Maximum valid diagonal. */
 697     const long fmid = nStt1 - nStt2;    /* Center diagonal of top-down search. */
 698     const long bmid = nEnd1 - nEnd2;    /* Center diagonal of bottom-up search. */
 699
 700     long fmin = fmid, fmax = fmid;      /* Limits of top-down search. */
 701     long bmin = bmid, bmax = bmid;      /* Limits of bottom-up search. */
 702
 703     long c;                     /* Cost. */
 704     long odd = (fmid - bmid) & 1;       /* True if southeast corner is on an odd
 705                      diagonal with respect to the northwest. */
 706
 707     pFDiag[fmid] = nStt1;
 708     pBDiag[bmid] = nEnd1;
 709
 710     for (c = 1;; ++c)
 711     {
 712         long d;                 /* Active diagonal. */
 713         long big_snake = 0;
 714
 715         /* Extend the top-down search by an edit step in each diagonal. */
 716         fmin > dmin ? pFDiag[--fmin - 1] = -1 : ++fmin;
 717         fmax < dmax ? pFDiag[++fmax + 1] = -1 : --fmax;
 718         for (d = fmax; d >= fmin; d -= 2)
 719         {
 720             long x, y, oldx, tlo = pFDiag[d - 1], thi = pFDiag[d + 1];
 721
 722             if (tlo >= thi)
 723                 x = tlo + 1;
 724             else
 725                 x = thi;
 726             oldx = x;
 727             y = x - d;
 728             while( ULONG(x) < nEnd1 && ULONG(y) < nEnd2 &&
 729                 rMoved1.GetIndex( x ) == rMoved2.GetIndex( y ))
 730                 ++x, ++y;
 731             if (x - oldx > 20)
 732                 big_snake = 1;
 733             pFDiag[d] = x;
 734             if( odd && bmin <= d && d <= bmax && pBDiag[d] <= pFDiag[d] )
 735             {
 736                 *pCost = 2 * c - 1;
 737                 return d;
 738             }
 739         }
 740
 741         /* Similar extend the bottom-up search. */
 742         bmin > dmin ? pBDiag[--bmin - 1] = INT_MAX : ++bmin;
 743         bmax < dmax ? pBDiag[++bmax + 1] = INT_MAX : --bmax;
 744         for (d = bmax; d >= bmin; d -= 2)
 745         {
 746             long x, y, oldx, tlo = pBDiag[d - 1], thi = pBDiag[d + 1];
 747
 748             if (tlo < thi)
 749                 x = tlo;
 750             else
 751                 x = thi - 1;
 752             oldx = x;
 753             y = x - d;
 754             while( ULONG(x) > nStt1 && ULONG(y) > nStt2 &&
 755                 rMoved1.GetIndex( x - 1 ) == rMoved2.GetIndex( y - 1 ))
 756                 --x, --y;
 757             if (oldx - x > 20)
 758                 big_snake = 1;
 759             pBDiag[d] = x;
 760             if (!odd && fmin <= d && d <= fmax && pBDiag[d] <= pFDiag[d])
 761             {
 762                 *pCost = 2 * c;
 763                 return d;
 764             }
 765         }
 766     }
 767 }
 768
 769 void Compare::ShiftBoundaries( CompareData& rData1, CompareData& rData2 )
 770 {
 771     for( int iz = 0; iz < 2; ++iz )
 772     {
 773         CompareData* pData = &rData1;
 774         CompareData* pOtherData = &rData2;
 775
 776         ULONG i = 0;
 777         ULONG j = 0;
 778         ULONG i_end = pData->GetLineCount();
 779         ULONG preceding = ULONG_MAX;
 780         ULONG other_preceding = ULONG_MAX;
 781
 782         while (1)
 783         {
 784             ULONG start, other_start;
 785
 786             /* Scan forwards to find beginning of another run of changes.
 787                Also keep track of the corresponding point in the other file.  */
 788
 789             while( i < i_end && !pData->GetChanged( i ) )
 790             {
 791                 while( pOtherData->GetChanged( j++ ))
 792                     /* Non-corresponding lines in the other file
 793                        will count as the preceding batch of changes.  */
 794                     other_preceding = j;
 795                 i++;
 796             }
 797
 798             if (i == i_end)
 799                 break;
 800
 801             start = i;
 802             other_start = j;
 803
 804             while (1)
 805             {
 806                 /* Now find the end of this run of changes.  */
 807
 808                 while( pData->GetChanged( ++i ))
 809                     ;
 810
 811                 /* If the first changed line matches the following unchanged one,
 812                    and this run does not follow right after a previous run,
 813                    and there are no lines deleted from the other file here,
 814                    then classify the first changed line as unchanged
 815                    and the following line as changed in its place.  */
 816
 817                 /* You might ask, how could this run follow right after another?
 818                    Only because the previous run was shifted here.  */
 819
 820                 if( i != i_end &&
 821                     pData->GetIndex( start ) == pData->GetIndex( i ) &&
 822                     !pOtherData->GetChanged( j ) &&
 823                     !( start == preceding || other_start == other_preceding ))
 824                 {
 825                     pData->SetChanged( start++, 0 );
 826                     pData->SetChanged(  i );
 827                     /* Since one line-that-matches is now before this run
 828                        instead of after, we must advance in the other file
 829                        to keep in synch.  */
 830                     ++j;
 831                 }
 832                 else
 833                     break;
 834             }
 835
 836             preceding = i;
 837             other_preceding = j;
 838         }
 839
 840         pData = &rData2;
 841         pOtherData = &rData1;
 842     }
 843 }
 844
 845 /* \f */
 846
 847 class SwCompareLine : public CompareLine
 848 {
 849     const SwNode& rNode;
 850 public:
 851     SwCompareLine( const SwNode& rNd );
 852     virtual ~SwCompareLine();
 853
 854     virtual ULONG GetHashValue() const;
 855     virtual BOOL Compare( const CompareLine& rLine ) const;
 856
 857     static ULONG GetTxtNodeHashValue( const SwTxtNode& rNd, ULONG nVal );
 858     static BOOL CompareNode( const SwNode& rDstNd, const SwNode& rSrcNd );
 859     static BOOL CompareTxtNd( const SwTxtNode& rDstNd,
 860                               const SwTxtNode& rSrcNd );
 861
 862     BOOL ChangesInLine( const SwCompareLine& rLine,
 863                             SwPaM *& rpInsRing, SwPaM*& rpDelRing ) const;
 864
 865     const SwNode& GetNode() const { return rNode; }
 866
 867     const SwNode& GetEndNode() const;
 868
 869     // fuers Debugging!
 870     String GetText() const;
 871 };
 872
 873 class SwCompareData : public CompareData
 874 {
 875     SwDoc& rDoc;
 876     SwPaM *pInsRing, *pDelRing;
 877
 878     ULONG PrevIdx( const SwNode* pNd );
 879     ULONG NextIdx( const SwNode* pNd );
 880
 881     virtual void CheckRanges( CompareData& );
 882     virtual void ShowInsert( ULONG nStt, ULONG nEnd );
 883     virtual void ShowDelete( const CompareData& rData, ULONG nStt,
 884                                 ULONG nEnd, ULONG nInsPos );
 885
 886     virtual void CheckForChangesInLine( const CompareData& rData,
 887                                     ULONG& nStt, ULONG& nEnd,
 888                                     ULONG& nThisStt, ULONG& nThisEnd );
 889
 890 public:
 891     SwCompareData( SwDoc& rD ) : rDoc( rD ), pInsRing(0), pDelRing(0) {}
 892     virtual ~SwCompareData();
 893
 894     void SetRedlinesToDoc( BOOL bUseDocInfo );
 895 };
 896
 897 // ----------------------------------------------------------------
 898
 899 SwCompareLine::SwCompareLine( const SwNode& rNd )
 900     : rNode( rNd )
 901 {
 902 }
 903
 904 SwCompareLine::~SwCompareLine()
 905 {
 906 }
 907
 908 ULONG SwCompareLine::GetHashValue() const
 909 {
 910     ULONG nRet = 0;
 911     switch( rNode.GetNodeType() )
 912     {
 913     case ND_TEXTNODE:
 914         nRet = GetTxtNodeHashValue( (SwTxtNode&)rNode, nRet );
 915         break;
 916
 917     case ND_TABLENODE:
 918         {
 919             const SwNode* pEndNd = rNode.EndOfSectionNode();
 920             SwNodeIndex aIdx( rNode );
 921             while( &aIdx.GetNode() != pEndNd )
 922             {
 923                 if( aIdx.GetNode().IsTxtNode() )
 924                     nRet = GetTxtNodeHashValue( (SwTxtNode&)aIdx.GetNode(), nRet );
 925                 aIdx++;
 926             }
 927         }
 928         break;
 929
 930     case ND_SECTIONNODE:
 931         {
 932             String sStr( GetText() );
 933             for( xub_StrLen n = 0; n < sStr.Len(); ++n )
 934                 ( nRet <<= 1 ) += sStr.GetChar( n );
 935         }
 936         break;
 937
 938     case ND_GRFNODE:
 939     case ND_OLENODE:
 940         // feste Id ? sollte aber nie auftauchen
 941         break;
 942     }
 943     return nRet;
 944 }
 945
 946 const SwNode& SwCompareLine::GetEndNode() const
 947 {
 948     const SwNode* pNd = &rNode;
 949     switch( rNode.GetNodeType() )
 950     {
 951     case ND_TABLENODE:
 952         pNd = rNode.EndOfSectionNode();
 953         break;
 954
 955     case ND_SECTIONNODE:
 956         {
 957             const SwSectionNode& rSNd = (SwSectionNode&)rNode;
 958             const SwSection& rSect = rSNd.GetSection();
 959             if( CONTENT_SECTION != rSect.GetType() || rSect.IsProtect() )
 960                 pNd = rNode.EndOfSectionNode();
 961         }
 962         break;
 963     }
 964     return *pNd;
 965 }
 966
 967 BOOL SwCompareLine::Compare( const CompareLine& rLine ) const
 968 {
 969     return CompareNode( rNode, ((SwCompareLine&)rLine).rNode );
 970 }
 971
 972 BOOL SwCompareLine::CompareNode( const SwNode& rDstNd, const SwNode& rSrcNd )
 973 {
 974     if( rSrcNd.GetNodeType() != rDstNd.GetNodeType() )
 975         return FALSE;
 976
 977     BOOL bRet = FALSE;
 978
 979     switch( rDstNd.GetNodeType() )
 980     {
 981     case ND_TEXTNODE:
 982         bRet = CompareTxtNd( (SwTxtNode&)rDstNd, (SwTxtNode&)rSrcNd );
 983         break;
 984
 985     case ND_TABLENODE:
 986         {
 987             const SwTableNode& rTSrcNd = (SwTableNode&)rSrcNd;
 988             const SwTableNode& rTDstNd = (SwTableNode&)rDstNd;
 989
 990             bRet = ( rTSrcNd.EndOfSectionIndex() - rTSrcNd.GetIndex() ) ==
 991                    ( rTDstNd.EndOfSectionIndex() - rTDstNd.GetIndex() );
 992         }
 993         break;
 994
 995     case ND_SECTIONNODE:
 996         {
 997             const SwSectionNode& rSSrcNd = (SwSectionNode&)rSrcNd,
 998                                & rSDstNd = (SwSectionNode&)rDstNd;
 999             const SwSection& rSrcSect = rSSrcNd.GetSection(),
1000                            & rDstSect = rSDstNd.GetSection();
1001             SectionType eSrcSectType = rSrcSect.GetType(),
1002                         eDstSectType = rDstSect.GetType();
1003             switch( eSrcSectType )
1004             {
1005             case CONTENT_SECTION:
1006                 bRet = CONTENT_SECTION == eDstSectType &&
1007                         rSrcSect.IsProtect() == rDstSect.IsProtect();
1008                 if( bRet && rSrcSect.IsProtect() )
1009                 {
1010                     // the only have they both the same size
1011                     bRet = ( rSSrcNd.EndOfSectionIndex() - rSSrcNd.GetIndex() ) ==
1012                               ( rSDstNd.EndOfSectionIndex() - rSDstNd.GetIndex() );
1013                 }
1014                 break;
1015
1016             case TOX_HEADER_SECTION:
1017             case TOX_CONTENT_SECTION:
1018                 if( TOX_HEADER_SECTION == eDstSectType ||
1019                     TOX_CONTENT_SECTION == eDstSectType )
1020                 {
1021                     // the same type of TOX?
1022                     const SwTOXBase* pSrcTOX = rSrcSect.GetTOXBase();
1023                     const SwTOXBase* pDstTOX = rDstSect.GetTOXBase();
1024                     bRet =      pSrcTOX && pDstTOX
1025                             && pSrcTOX->GetType() == pDstTOX->GetType()
1026                             && pSrcTOX->GetTitle() == pDstTOX->GetTitle()
1027                             && pSrcTOX->GetTypeName() == pDstTOX->GetTypeName()
1028 //                                                      && pSrcTOX->GetTOXName() == pDstTOX->GetTOXName()
1029                             ;
1030                 }
1031                 break;
1032
1033             case DDE_LINK_SECTION:
1034             case FILE_LINK_SECTION:
1035                 bRet = eSrcSectType == eDstSectType &&
1036                         rSrcSect.GetLinkFileName() ==
1037                         rDstSect.GetLinkFileName();
1038                 break;
1039             }
1040         }
1041         break;
1042
1043     case ND_ENDNODE:
1044         bRet = rSrcNd.StartOfSectionNode()->GetNodeType() ==
1045                rDstNd.StartOfSectionNode()->GetNodeType();
1046         break;
1047     }
1048     return bRet;
1049 }
1050
1051 String SwCompareLine::GetText() const
1052 {
1053     String sRet;
1054     switch( rNode.GetNodeType() )
1055     {
1056     case ND_TEXTNODE:
1057         sRet = ((SwTxtNode&)rNode).GetExpandTxt();
1058         break;
1059
1060     case ND_TABLENODE:
1061         {
1062             const SwNode* pEndNd = rNode.EndOfSectionNode();
1063             SwNodeIndex aIdx( rNode );
1064             while( &aIdx.GetNode() != pEndNd )
1065             {
1066                 if( aIdx.GetNode().IsTxtNode() )
1067                 {
1068                     if( sRet.Len() )
1069                         sRet.Append( '\n' );
1070                     sRet.Append( ((SwTxtNode&)rNode).GetExpandTxt() );
1071                 }
1072                 aIdx++;
1073             }
1074             sRet.InsertAscii( "Tabelle: ", 0 );
1075         }
1076         break;
1077
1078     case ND_SECTIONNODE:
1079         {
1080             sRet.AssignAscii( RTL_CONSTASCII_STRINGPARAM( "Section - Node:" ));
1081
1082             const SwSectionNode& rSNd = (SwSectionNode&)rNode;
1083             const SwSection& rSect = rSNd.GetSection();
1084             switch( rSect.GetType() )
1085             {
1086             case CONTENT_SECTION:
1087                 if( rSect.IsProtect() )
1088                     sRet.Append( String::CreateFromInt32(
1089                             rSNd.EndOfSectionIndex() - rSNd.GetIndex() ));
1090                 break;
1091
1092             case TOX_HEADER_SECTION:
1093             case TOX_CONTENT_SECTION:
1094                 {
1095                     const SwTOXBase* pTOX = rSect.GetTOXBase();
1096                     if( pTOX )
1097                         sRet.Append( pTOX->GetTitle() )
1098                             .Append( pTOX->GetTypeName() )
1099 //                                                      .Append( pTOX->GetTOXName() )
1100                             .Append( String::CreateFromInt32( pTOX->GetType() ));
1101                 }
1102                 break;
1103
1104             case DDE_LINK_SECTION:
1105             case FILE_LINK_SECTION:
1106                 sRet += rSect.GetLinkFileName();
1107                 break;
1108             }
1109         }
1110         break;
1111
1112     case ND_GRFNODE:
1113         sRet.AssignAscii( RTL_CONSTASCII_STRINGPARAM( "Grafik - Node:" ));
1114         break;
1115     case ND_OLENODE:
1116         sRet.AssignAscii( RTL_CONSTASCII_STRINGPARAM( "OLE - Node:" ));
1117         break;
1118     }
1119     return sRet;
1120 }
1121
1122 ULONG SwCompareLine::GetTxtNodeHashValue( const SwTxtNode& rNd, ULONG nVal )
1123 {
1124     String sStr( rNd.GetExpandTxt() );
1125     for( xub_StrLen n = 0; n < sStr.Len(); ++n )
1126         ( nVal <<= 1 ) += sStr.GetChar( n );
1127     return nVal;
1128 }
1129
1130 BOOL SwCompareLine::CompareTxtNd( const SwTxtNode& rDstNd,
1131                                   const SwTxtNode& rSrcNd )
1132 {
1133     BOOL bRet = FALSE;
1134     // erstmal ganz einfach!
1135     if( rDstNd.GetTxt() == rSrcNd.GetTxt() )
1136     {
1137         // der Text ist gleich, aber sind die "Sonderattribute" (0xFF) auch
1138         // dieselben??
1139         bRet = TRUE;
1140     }
1141     return bRet;
1142 }
1143
1144 BOOL SwCompareLine::ChangesInLine( const SwCompareLine& rLine,
1145                             SwPaM *& rpInsRing, SwPaM*& rpDelRing ) const
1146 {
1147     BOOL bRet = FALSE;
1148     if( ND_TEXTNODE == rNode.GetNodeType() &&
1149         ND_TEXTNODE == rLine.GetNode().GetNodeType() )
1150     {
1151         SwTxtNode& rDestNd = *(SwTxtNode*)rNode.GetTxtNode();
1152         const SwTxtNode& rSrcNd = *rLine.GetNode().GetTxtNode();
1153
1154         xub_StrLen nDEnd = rDestNd.GetTxt().Len(), nSEnd = rSrcNd.GetTxt().Len();
1155         xub_StrLen nStt;
1156         xub_StrLen nEnd;
1157
1158         for( nStt = 0, nEnd = Min( nDEnd, nSEnd ); nStt < nEnd; ++nStt )
1159             if( rDestNd.GetTxt().GetChar( nStt ) !=
1160                 rSrcNd.GetTxt().GetChar( nStt ) )
1161                 break;
1162
1163         while( nStt < nDEnd && nStt < nSEnd )
1164         {
1165             --nDEnd, --nSEnd;
1166             if( rDestNd.GetTxt().GetChar( nDEnd ) !=
1167                 rSrcNd.GetTxt().GetChar( nSEnd ) )
1168             {
1169                 ++nDEnd, ++nSEnd;
1170                 break;
1171             }
1172         }
1173
1174         if( nStt || !nDEnd || !nSEnd || nDEnd < rDestNd.GetTxt().Len() ||
1175             nSEnd < rSrcNd.GetTxt().Len() )
1176         {
1177             // jetzt ist zwischen nStt bis nDEnd das neu eingefuegte
1178             // und zwischen nStt und nSEnd das geloeschte
1179             SwDoc* pDoc = rDestNd.GetDoc();
1180             SwPaM aPam( rDestNd, nDEnd );
1181             if( nStt != nDEnd )
1182             {
1183                 SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpInsRing );
1184                 if( !rpInsRing )
1185                     rpInsRing = pTmp;
1186
1187                 pTmp->SetMark();
1188                 pTmp->GetMark()->nContent = nStt;
1189             }
1190
1191             if( nStt != nSEnd )
1192             {
1193                 {
1194                     BOOL bUndo = pDoc->DoesUndo();
1195                     pDoc->DoUndo( FALSE );
1196                     SwPaM aCpyPam( rSrcNd, nStt );
1197                     aCpyPam.SetMark();
1198                     aCpyPam.GetPoint()->nContent = nSEnd;
1199                     aCpyPam.GetDoc()->CopyRange( aCpyPam, *aPam.GetPoint(),
1200                             false );
1201                     pDoc->DoUndo( bUndo );
1202                 }
1203
1204                 SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpDelRing );
1205                 if( !rpDelRing )
1206                     rpDelRing = pTmp;
1207
1208                 pTmp->SetMark();
1209                 pTmp->GetMark()->nContent = nDEnd;
1210
1211                 if( rpInsRing )
1212                 {
1213                     SwPaM* pCorr = (SwPaM*)rpInsRing->GetPrev();
1214                     if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1215                         *pCorr->GetPoint() = *pTmp->GetMark();
1216                 }
1217             }
1218             bRet = TRUE;
1219         }
1220     }
1221     return bRet;
1222 }
1223
1224 // ----------------------------------------------------------------
1225
1226 SwCompareData::~SwCompareData()
1227 {
1228     if( pDelRing )
1229     {
1230         while( pDelRing->GetNext() != pDelRing )
1231             delete pDelRing->GetNext();
1232         delete pDelRing;
1233     }
1234     if( pInsRing )
1235     {
1236         while( pInsRing->GetNext() != pInsRing )
1237             delete pInsRing->GetNext();
1238         delete pInsRing;
1239     }
1240 }
1241
1242 ULONG SwCompareData::NextIdx( const SwNode* pNd )
1243 {
1244     if( pNd->IsStartNode() )
1245     {
1246         const SwSectionNode* pSNd;
1247         if( pNd->IsTableNode() ||
1248             ( 0 != (pSNd = pNd->GetSectionNode() ) &&
1249                 ( CONTENT_SECTION != pSNd->GetSection().GetType() ||
1250                     pSNd->GetSection().IsProtect() ) ) )
1251             pNd = pNd->EndOfSectionNode();
1252     }
1253     return pNd->GetIndex() + 1;
1254 }
1255
1256 ULONG SwCompareData::PrevIdx( const SwNode* pNd )
1257 {
1258     if( pNd->IsEndNode() )
1259     {
1260         const SwSectionNode* pSNd;
1261         if( pNd->StartOfSectionNode()->IsTableNode() ||
1262             ( 0 != (pSNd = pNd->StartOfSectionNode()->GetSectionNode() ) &&
1263                 ( CONTENT_SECTION != pSNd->GetSection().GetType() ||
1264                     pSNd->GetSection().IsProtect() ) ) )
1265             pNd = pNd->StartOfSectionNode();
1266     }
1267     return pNd->GetIndex() - 1;
1268 }
1269
1270
1271 void SwCompareData::CheckRanges( CompareData& rData )
1272 {
1273     const SwNodes& rSrcNds = ((SwCompareData&)rData).rDoc.GetNodes();
1274     const SwNodes& rDstNds = rDoc.GetNodes();
1275
1276     const SwNode& rSrcEndNd = rSrcNds.GetEndOfContent();
1277     const SwNode& rDstEndNd = rDstNds.GetEndOfContent();
1278
1279     ULONG nSrcSttIdx = NextIdx( rSrcEndNd.StartOfSectionNode() );
1280     ULONG nSrcEndIdx = rSrcEndNd.GetIndex();
1281
1282     ULONG nDstSttIdx = NextIdx( rDstEndNd.StartOfSectionNode() );
1283     ULONG nDstEndIdx = rDstEndNd.GetIndex();
1284
1285     while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1286     {
1287         const SwNode* pSrcNd = rSrcNds[ nSrcSttIdx ];
1288         const SwNode* pDstNd = rDstNds[ nDstSttIdx ];
1289         if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1290             break;
1291
1292         nSrcSttIdx = NextIdx( pSrcNd );
1293         nDstSttIdx = NextIdx( pDstNd );
1294     }
1295
1296     nSrcEndIdx = PrevIdx( &rSrcEndNd );
1297     nDstEndIdx = PrevIdx( &rDstEndNd );
1298     while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1299     {
1300         const SwNode* pSrcNd = rSrcNds[ nSrcEndIdx ];
1301         const SwNode* pDstNd = rDstNds[ nDstEndIdx ];
1302         if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1303             break;
1304
1305         nSrcEndIdx = PrevIdx( pSrcNd );
1306         nDstEndIdx = PrevIdx( pDstNd );
1307     }
1308
1309     while( nSrcSttIdx <= nSrcEndIdx )
1310     {
1311         const SwNode* pNd = rSrcNds[ nSrcSttIdx ];
1312         rData.InsertLine( new SwCompareLine( *pNd ) );
1313         nSrcSttIdx = NextIdx( pNd );
1314     }
1315
1316     while( nDstSttIdx <= nDstEndIdx )
1317     {
1318         const SwNode* pNd = rDstNds[ nDstSttIdx ];
1319         InsertLine( new SwCompareLine( *pNd ) );
1320         nDstSttIdx = NextIdx( pNd );
1321     }
1322 }
1323
1324
1325 void SwCompareData::ShowInsert( ULONG nStt, ULONG nEnd )
1326 {
1327     SwPaM* pTmp = new SwPaM( ((SwCompareLine*)GetLine( nStt ))->GetNode(), 0,
1328                             ((SwCompareLine*)GetLine( nEnd-1 ))->GetEndNode(), 0,
1329                              pInsRing );
1330     if( !pInsRing )
1331         pInsRing = pTmp;
1332
1333     // #i65201#: These SwPaMs are calculated smaller than needed, see comment below
1334
1335 }
1336
1337 void SwCompareData::ShowDelete( const CompareData& rData, ULONG nStt,
1338                                 ULONG nEnd, ULONG nInsPos )
1339 {
1340     SwNodeRange aRg(
1341         ((SwCompareLine*)rData.GetLine( nStt ))->GetNode(), 0,
1342         ((SwCompareLine*)rData.GetLine( nEnd-1 ))->GetEndNode(), 1 );
1343
1344     USHORT nOffset = 0;
1345     const CompareLine* pLine;
1346     if( GetLineCount() == nInsPos )
1347     {
1348         pLine = GetLine( nInsPos-1 );
1349         nOffset = 1;
1350     }
1351     else
1352         pLine = GetLine( nInsPos );
1353
1354     const SwNode* pLineNd;
1355     if( pLine )
1356     {
1357         if( nOffset )
1358             pLineNd = &((SwCompareLine*)pLine)->GetEndNode();
1359         else
1360             pLineNd = &((SwCompareLine*)pLine)->GetNode();
1361     }
1362     else
1363     {
1364         pLineNd = &rDoc.GetNodes().GetEndOfContent();
1365         nOffset = 0;
1366     }
1367
1368     SwNodeIndex aInsPos( *pLineNd, nOffset );
1369     SwNodeIndex aSavePos( aInsPos, -1 );
1370
1371     ((SwCompareData&)rData).rDoc.CopyWithFlyInFly( aRg, 0, aInsPos );
1372     rDoc.SetModified();
1373     aSavePos++;
1374
1375     // #i65201#: These SwPaMs are calculated when the (old) delete-redlines are hidden,
1376     // they will be inserted when the delete-redlines are shown again.
1377     // To avoid unwanted insertions of delete-redlines into these new redlines, what happens
1378     // especially at the end of the document, I reduce the SwPaM by one node.
1379     // Before the new redlines are inserted, they have to expand again.
1380     SwPaM* pTmp = new SwPaM( aSavePos.GetNode(), aInsPos.GetNode(), 0, -1, pDelRing );
1381     if( !pDelRing )
1382         pDelRing = pTmp;
1383
1384     if( pInsRing )
1385     {
1386         SwPaM* pCorr = (SwPaM*)pInsRing->GetPrev();
1387         if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1388         {
1389             SwNodeIndex aTmpPos( pTmp->GetMark()->nNode, -1 );
1390             *pCorr->GetPoint() = SwPosition( aTmpPos, 0 );
1391         }
1392     }
1393 }
1394
1395 void SwCompareData::CheckForChangesInLine( const CompareData& rData,
1396                                     ULONG& rStt, ULONG& rEnd,
1397                                     ULONG& rThisStt, ULONG& rThisEnd )
1398 {
1399     while( rStt < rEnd && rThisStt < rThisEnd )
1400     {
1401         SwCompareLine* pDstLn = (SwCompareLine*)GetLine( rThisStt );
1402         SwCompareLine* pSrcLn = (SwCompareLine*)rData.GetLine( rStt );
1403         if( !pDstLn->ChangesInLine( *pSrcLn, pInsRing, pDelRing ) )
1404             break;
1405
1406         ++rStt;
1407         ++rThisStt;
1408     }
1409 }
1410
1411 void SwCompareData::SetRedlinesToDoc( BOOL bUseDocInfo )
1412 {
1413     SwPaM* pTmp = pDelRing;
1414
1415     // Bug #83296#: get the Author / TimeStamp from the "other"
1416     //                          document info
1417     USHORT nAuthor = rDoc.GetRedlineAuthor();
1418     DateTime aTimeStamp;
1419     SwDocShell *pDocShell(rDoc.GetDocShell());
1420     DBG_ASSERT(pDocShell, "no SwDocShell");
1421     if (pDocShell) {
1422         uno::Reference<document::XDocumentPropertiesSupplier> xDPS(
1423             pDocShell->GetModel(), uno::UNO_QUERY_THROW);
1424         uno::Reference<document::XDocumentProperties> xDocProps(
1425             xDPS->getDocumentProperties());
1426         DBG_ASSERT(xDocProps.is(), "Doc has no DocumentProperties");
1427
1428         if( bUseDocInfo && xDocProps.is() ) {
1429             String aTmp( 1 == xDocProps->getEditingCycles()
1430                                 ? xDocProps->getAuthor()
1431                                 : xDocProps->getModifiedBy() );
1432             util::DateTime uDT( 1 == xDocProps->getEditingCycles()
1433                                 ? xDocProps->getCreationDate()
1434                                 : xDocProps->getModificationDate() );
1435             Date d(uDT.Day, uDT.Month, uDT.Year);
1436             Time t(uDT.Hours, uDT.Minutes, uDT.Seconds, uDT.HundredthSeconds);
1437             DateTime aDT(d,t);
1438
1439             if( aTmp.Len() )
1440             {
1441                 nAuthor = rDoc.InsertRedlineAuthor( aTmp );
1442                 aTimeStamp = aDT;
1443             }
1444         }
1445     }
1446
1447     if( pTmp )
1448     {
1449         SwRedlineData aRedlnData( nsRedlineType_t::REDLINE_DELETE, nAuthor, aTimeStamp,
1450                                     aEmptyStr, 0, 0 );
1451         do {
1452             // #i65201#: Expand again, see comment above.
1453             if( pTmp->GetPoint()->nContent == 0 )
1454             {
1455                 pTmp->GetPoint()->nNode++;
1456                 pTmp->GetPoint()->nContent.Assign( pTmp->GetCntntNode(), 0 );
1457             }
1458
1459             rDoc.DeleteRedline( *pTmp, false, USHRT_MAX );
1460
1461             if( rDoc.DoesUndo() )
1462                 rDoc.AppendUndo( new SwUndoCompDoc( *pTmp, FALSE ));
1463             rDoc.AppendRedline( new SwRedline( aRedlnData, *pTmp ), true );
1464
1465         } while( pDelRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1466     }
1467
1468     pTmp = pInsRing;
1469     if( pTmp )
1470     {
1471         do {
1472             if( pTmp->GetPoint()->nContent == 0 )
1473             {
1474                 pTmp->GetPoint()->nNode++;
1475                 pTmp->GetPoint()->nContent.Assign( pTmp->GetCntntNode(), 0 );
1476             }
1477         } while( pInsRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1478         SwRedlineData aRedlnData( nsRedlineType_t::REDLINE_INSERT, nAuthor, aTimeStamp,
1479                                     aEmptyStr, 0, 0 );
1480
1481         // zusammenhaengende zusammenfassen
1482         if( pTmp->GetNext() != pInsRing )
1483         {
1484             const SwCntntNode* pCNd;
1485             do {
1486                 SwPosition& rSttEnd = *pTmp->End(),
1487                           & rEndStt = *((SwPaM*)pTmp->GetNext())->Start();
1488                 if( rSttEnd == rEndStt ||
1489                     (!rEndStt.nContent.GetIndex() &&
1490                     rEndStt.nNode.GetIndex() - 1 == rSttEnd.nNode.GetIndex() &&
1491                     0 != ( pCNd = rSttEnd.nNode.GetNode().GetCntntNode() )
1492                         ? rSttEnd.nContent.GetIndex() == pCNd->Len()
1493                         : 0 ))
1494                 {
1495                     if( pTmp->GetNext() == pInsRing )
1496                     {
1497                         // liegen hintereinander also zusammen fassen
1498                         rEndStt = *pTmp->Start();
1499                         delete pTmp;
1500                         pTmp = pInsRing;
1501                     }
1502                     else
1503                     {
1504                         // liegen hintereinander also zusammen fassen
1505                         rSttEnd = *((SwPaM*)pTmp->GetNext())->End();
1506                         delete pTmp->GetNext();
1507                     }
1508                 }
1509                 else
1510                     pTmp = (SwPaM*)pTmp->GetNext();
1511             } while( pInsRing != pTmp );
1512         }
1513
1514         do {
1515             if( rDoc.AppendRedline( new SwRedline( aRedlnData, *pTmp ), true) &&
1516                 rDoc.DoesUndo() )
1517                 rDoc.AppendUndo( new SwUndoCompDoc( *pTmp, TRUE ));
1518         } while( pInsRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1519     }
1520 }
1521
1522 /* \f */
1523
1524
1525
1526     // returnt (?die Anzahl der Unterschiede?) ob etwas unterschiedlich ist
1527 long SwDoc::CompareDoc( const SwDoc& rDoc )
1528 {
1529     if( &rDoc == this )
1530         return 0;
1531
1532     long nRet = 0;
1533
1534     StartUndo(UNDO_EMPTY, NULL);
1535     BOOL bDocWasModified = IsModified();
1536     SwDoc& rSrcDoc = (SwDoc&)rDoc;
1537     BOOL bSrcModified = rSrcDoc.IsModified();
1538
1539     RedlineMode_t eSrcRedlMode = rSrcDoc.GetRedlineMode();
1540     rSrcDoc.SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_INSERT );
1541     SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_ON | nsRedlineMode_t::REDLINE_SHOW_INSERT));
1542
1543     SwCompareData aD0( rSrcDoc );
1544     SwCompareData aD1( *this );
1545
1546     aD1.CompareLines( aD0 );
1547
1548     nRet = aD1.ShowDiffs( aD0 );
1549
1550     if( nRet )
1551     {
1552       SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_ON |
1553                        nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1554
1555         aD1.SetRedlinesToDoc( !bDocWasModified );
1556         SetModified();
1557     }
1558
1559     rSrcDoc.SetRedlineMode( eSrcRedlMode );
1560     SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1561
1562     if( !bSrcModified )
1563         rSrcDoc.ResetModified();
1564
1565     EndUndo(UNDO_EMPTY, NULL);
1566
1567     return nRet;
1568 }
1569
1570
1571 typedef void (SwDoc::*FNInsUndo)( SwUndo* );
1572
1573 class _SaveMergeRedlines : public Ring
1574 {
1575     const SwRedline* pSrcRedl;
1576     SwRedline* pDestRedl;
1577 public:
1578     _SaveMergeRedlines( const SwNode& rDstNd,
1579                         const SwRedline& rSrcRedl, Ring* pRing );
1580     USHORT InsertRedline( FNInsUndo pFn );
1581
1582     SwRedline* GetDestRedline() { return pDestRedl; }
1583 };
1584
1585 _SaveMergeRedlines::_SaveMergeRedlines( const SwNode& rDstNd,
1586                         const SwRedline& rSrcRedl, Ring* pRing )
1587     : Ring( pRing ), pSrcRedl( &rSrcRedl )
1588 {
1589     SwPosition aPos( rDstNd );
1590
1591     const SwPosition* pStt = rSrcRedl.Start();
1592     if( rDstNd.IsCntntNode() )
1593         aPos.nContent.Assign( ((SwCntntNode*)&rDstNd), pStt->nContent.GetIndex() );
1594     pDestRedl = new SwRedline( rSrcRedl.GetRedlineData(), aPos );
1595
1596     if( nsRedlineType_t::REDLINE_DELETE == pDestRedl->GetType() )
1597     {
1598         // den Bereich als geloescht kennzeichnen
1599         const SwPosition* pEnd = pStt == rSrcRedl.GetPoint()
1600                                             ? rSrcRedl.GetMark()
1601                                             : rSrcRedl.GetPoint();
1602
1603         pDestRedl->SetMark();
1604         pDestRedl->GetPoint()->nNode += pEnd->nNode.GetIndex() -
1605                                         pStt->nNode.GetIndex();
1606         pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetCntntNode(),
1607                                                 pEnd->nContent.GetIndex() );
1608     }
1609 }
1610
1611 USHORT _SaveMergeRedlines::InsertRedline( FNInsUndo pFn )
1612 {
1613     USHORT nIns = 0;
1614     SwDoc* pDoc = pDestRedl->GetDoc();
1615
1616     if( nsRedlineType_t::REDLINE_INSERT == pDestRedl->GetType() )
1617     {
1618         // der Teil wurde eingefuegt, also kopiere ihn aus dem SourceDoc
1619         BOOL bUndo = pDoc->DoesUndo();
1620         pDoc->DoUndo( FALSE );
1621
1622         SwNodeIndex aSaveNd( pDestRedl->GetPoint()->nNode, -1 );
1623         xub_StrLen nSaveCnt = pDestRedl->GetPoint()->nContent.GetIndex();
1624
1625         RedlineMode_t eOld = pDoc->GetRedlineMode();
1626         pDoc->SetRedlineMode_intern((RedlineMode_t)(eOld | nsRedlineMode_t::REDLINE_IGNORE));
1627
1628         pSrcRedl->GetDoc()->CopyRange(
1629                 *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1630                 *pDestRedl->GetPoint(), false );
1631
1632         pDoc->SetRedlineMode_intern( eOld );
1633         pDoc->DoUndo( bUndo );
1634
1635         pDestRedl->SetMark();
1636         aSaveNd++;
1637         pDestRedl->GetMark()->nNode = aSaveNd;
1638         pDestRedl->GetMark()->nContent.Assign( aSaveNd.GetNode().GetCntntNode(),
1639                                                 nSaveCnt );
1640
1641         if( GetPrev() != this )
1642         {
1643             SwPaM* pTmpPrev = ((_SaveMergeRedlines*)GetPrev())->pDestRedl;
1644             if( pTmpPrev && *pTmpPrev->GetPoint() == *pDestRedl->GetPoint() )
1645                 *pTmpPrev->GetPoint() = *pDestRedl->GetMark();
1646         }
1647     }
1648     else
1649     {
1650         //JP 21.09.98: Bug 55909
1651         // falls im Doc auf gleicher Pos aber schon ein geloeschter oder
1652         // eingefuegter ist, dann muss dieser gesplittet werden!
1653         SwPosition* pDStt = pDestRedl->GetMark(),
1654                   * pDEnd = pDestRedl->GetPoint();
1655         USHORT n = 0;
1656
1657             // zur StartPos das erste Redline suchen
1658         if( !pDoc->GetRedline( *pDStt, &n ) && n )
1659             --n;
1660
1661         const SwRedlineTbl& rRedlineTbl = pDoc->GetRedlineTbl();
1662         for( ; n < rRedlineTbl.Count(); ++n )
1663         {
1664             SwRedline* pRedl = rRedlineTbl[ n ];
1665             SwPosition* pRStt = pRedl->Start(),
1666                       * pREnd = pRStt == pRedl->GetPoint() ? pRedl->GetMark()
1667                                                            : pRedl->GetPoint();
1668             if( nsRedlineType_t::REDLINE_DELETE == pRedl->GetType() ||
1669                 nsRedlineType_t::REDLINE_INSERT == pRedl->GetType() )
1670             {
1671                 SwComparePosition eCmpPos = ComparePosition( *pDStt, *pDEnd, *pRStt, *pREnd );
1672                 switch( eCmpPos )
1673                 {
1674                 case POS_COLLIDE_START:
1675                 case POS_BEHIND:
1676                     break;
1677
1678                 case POS_INSIDE:
1679                 case POS_EQUAL:
1680                     delete pDestRedl, pDestRedl = 0;
1681                     // break; -> kein break !!!!
1682
1683                 case POS_COLLIDE_END:
1684                 case POS_BEFORE:
1685                     n = rRedlineTbl.Count();
1686                     break;
1687
1688                 case POS_OUTSIDE:
1689                     {
1690                         SwRedline* pCpyRedl = new SwRedline(
1691                             pDestRedl->GetRedlineData(), *pDStt );
1692                         pCpyRedl->SetMark();
1693                         *pCpyRedl->GetPoint() = *pRStt;
1694
1695                         SwUndoCompDoc* pUndo = pDoc->DoesUndo()
1696                                     ? new SwUndoCompDoc( *pCpyRedl ) : 0;
1697
1698                         // now modify doc: append redline, undo (and count)
1699                         pDoc->AppendRedline( pCpyRedl, true );
1700                         if( pUndo )
1701                             (pDoc->*pFn)( pUndo );
1702                         ++nIns;
1703
1704                         *pDStt = *pREnd;
1705
1706                         // dann solle man neu anfangen
1707                         n = USHRT_MAX;
1708                     }
1709                     break;
1710
1711                 case POS_OVERLAP_BEFORE:
1712                     *pDEnd = *pRStt;
1713                     break;
1714
1715                 case POS_OVERLAP_BEHIND:
1716                     *pDStt = *pREnd;
1717                     break;
1718                 }
1719             }
1720             else if( *pDEnd <= *pRStt )
1721                 break;
1722         }
1723
1724     }
1725
1726     if( pDestRedl )
1727     {
1728         SwUndoCompDoc* pUndo = pDoc->DoesUndo() ? new SwUndoCompDoc( *pDestRedl ) : 0;
1729
1730         // now modify doc: append redline, undo (and count)
1731         bool bRedlineAccepted = pDoc->AppendRedline( pDestRedl, true );
1732         if( pUndo )
1733             (pDoc->*pFn)( pUndo );
1734         ++nIns;
1735
1736         // if AppendRedline has deleted our redline, we may not keep a
1737         // reference to it
1738         if( ! bRedlineAccepted )
1739             pDestRedl = NULL;
1740     }
1741     return nIns;
1742 }
1743
1744 // merge zweier Dokumente
1745 long SwDoc::MergeDoc( const SwDoc& rDoc )
1746 {
1747     if( &rDoc == this )
1748         return 0;
1749
1750     long nRet = 0;
1751
1752     StartUndo(UNDO_EMPTY, NULL);
1753
1754     SwDoc& rSrcDoc = (SwDoc&)rDoc;
1755     BOOL bSrcModified = rSrcDoc.IsModified();
1756
1757     RedlineMode_t eSrcRedlMode = rSrcDoc.GetRedlineMode();
1758     rSrcDoc.SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_DELETE );
1759     SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_DELETE );
1760
1761     SwCompareData aD0( rSrcDoc );
1762     SwCompareData aD1( *this );
1763
1764     aD1.CompareLines( aD0 );
1765
1766     if( !aD1.HasDiffs( aD0 ) )
1767     {
1768         // jetzt wollen wir alle Redlines aus dem SourceDoc zu uns bekommen
1769
1770         // suche alle Insert - Redlines aus dem SourceDoc und bestimme
1771         // deren Position im DestDoc
1772         _SaveMergeRedlines* pRing = 0;
1773         const SwRedlineTbl& rSrcRedlTbl = rSrcDoc.GetRedlineTbl();
1774         ULONG nEndOfExtra = rSrcDoc.GetNodes().GetEndOfExtras().GetIndex();
1775         ULONG nMyEndOfExtra = GetNodes().GetEndOfExtras().GetIndex();
1776         for( USHORT n = 0; n < rSrcRedlTbl.Count(); ++n )
1777         {
1778             const SwRedline* pRedl = rSrcRedlTbl[ n ];
1779             ULONG nNd = pRedl->GetPoint()->nNode.GetIndex();
1780             RedlineType_t eType = pRedl->GetType();
1781             if( nEndOfExtra < nNd &&
1782                 ( nsRedlineType_t::REDLINE_INSERT == eType || nsRedlineType_t::REDLINE_DELETE == eType ))
1783             {
1784                 const SwNode* pDstNd = GetNodes()[
1785                                         nMyEndOfExtra + nNd - nEndOfExtra ];
1786
1787                 // Position gefunden. Dann muss im DestDoc auch
1788                 // in der Line das Redline eingefuegt werden
1789                 _SaveMergeRedlines* pTmp = new _SaveMergeRedlines(
1790                                                     *pDstNd, *pRedl, pRing );
1791                 if( !pRing )
1792                     pRing = pTmp;
1793             }
1794         }
1795
1796         if( pRing )
1797         {
1798             // dann alle ins DestDoc ueber nehmen
1799           rSrcDoc.SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1800
1801           SetRedlineMode((RedlineMode_t)(
1802                                       nsRedlineMode_t::REDLINE_ON |
1803                                       nsRedlineMode_t::REDLINE_SHOW_INSERT |
1804                                       nsRedlineMode_t::REDLINE_SHOW_DELETE));
1805
1806             _SaveMergeRedlines* pTmp = pRing;
1807
1808             do {
1809                 nRet += pTmp->InsertRedline( &SwDoc::AppendUndo );
1810             } while( pRing != ( pTmp = (_SaveMergeRedlines*)pTmp->GetNext() ));
1811
1812             while( pRing != pRing->GetNext() )
1813                 delete pRing->GetNext();
1814             delete pRing;
1815         }
1816     }
1817
1818     rSrcDoc.SetRedlineMode( eSrcRedlMode );
1819     if( !bSrcModified )
1820         rSrcDoc.ResetModified();
1821
1822     SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1823
1824     EndUndo(UNDO_EMPTY, NULL);
1825
1826     return nRet;
1827 }
1828
1829