basegfx/source/polygon/b2dpolypolygonrasterconverter.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2000, 2010 Oracle and/or its affiliates.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * This file is part of OpenOffice.org.
  10  *
  11  * OpenOffice.org is free software: you can redistribute it and/or modify
  12  * it under the terms of the GNU Lesser General Public License version 3
  13  * only, as published by the Free Software Foundation.
  14  *
  15  * OpenOffice.org is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU Lesser General Public License version 3 for more details
  19  * (a copy is included in the LICENSE file that accompanied this code).
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * version 3 along with OpenOffice.org.  If not, see
  23  * <http://www.openoffice.org/license.html>
  24  * for a copy of the LGPLv3 License.
  25  *
  26  ************************************************************************/
  27
  28 // MARKER(update_precomp.py): autogen include statement, do not remove
  29 #include "precompiled_basegfx.hxx"
  30
  31 #include <basegfx/polygon/b2dpolypolygonrasterconverter.hxx>
  32
  33 #include <basegfx/numeric/ftools.hxx>
  34 #include <basegfx/polygon/b2dpolygon.hxx>
  35 #include <basegfx/polygon/b2dpolygontools.hxx>
  36 #include <basegfx/polygon/b2dpolypolygontools.hxx>
  37
  38 #include <boost/mem_fn.hpp>
  39
  40 #include <algorithm>
  41
  42 namespace basegfx
  43 {
  44     class radixSort {
  45
  46         //! public interface
  47         public:
  48
  49             //! default constructor
  50             radixSort( void );
  51
  52             //! destructor
  53             ~radixSort( void );
  54
  55             bool sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride );
  56
  57             inline sal_uInt32 *indices( void ) const { return m_indices1; }
  58
  59         //! private attributes
  60         private:
  61
  62             // current size of index list
  63             sal_uInt32 m_current_size;
  64
  65             // last known size of index list
  66             sal_uInt32 m_previous_size;
  67
  68             // index lists
  69             sal_uInt32 *m_indices1;
  70             sal_uInt32 *m_indices2;
  71
  72             sal_uInt32 m_counter[256*4];
  73             sal_uInt32 m_offset[256];
  74
  75         //! private methods
  76         private:
  77
  78             bool resize( sal_uInt32 nNumElements );
  79             inline void reset_indices( void );
  80             bool prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride );
  81     };
  82
  83     inline radixSort::radixSort( void ) {
  84
  85         m_indices1 = NULL;
  86         m_indices2 = NULL;
  87         m_current_size = 0;
  88         m_previous_size = 0;
  89
  90         reset_indices();
  91     }
  92
  93     inline radixSort::~radixSort( void ) {
  94
  95         delete [] m_indices2;
  96         delete [] m_indices1;
  97     }
  98
  99     bool radixSort::resize( sal_uInt32 nNumElements ) {
 100
 101         if(nNumElements==m_previous_size)
 102             return true;
 103
 104         if(nNumElements > m_current_size) {
 105
 106             // release index lists
 107             if(m_indices2)
 108                 delete [] m_indices2;
 109             if(m_indices1)
 110                 delete [] m_indices1;
 111
 112             // allocate new index lists
 113             m_indices1 = new sal_uInt32[nNumElements];
 114             m_indices2 = new sal_uInt32[nNumElements];
 115
 116             // check for out of memory situation
 117             if(!m_indices1 || !m_indices2) {
 118                 delete [] m_indices1;
 119                 delete [] m_indices2;
 120                 m_indices1 = NULL;
 121                 m_indices2 = NULL;
 122                 m_current_size = 0;
 123                 return false;
 124             }
 125
 126             m_current_size = nNumElements;
 127         }
 128
 129         m_previous_size = nNumElements;
 130
 131         // initialize indices
 132         reset_indices();
 133
 134         return true;
 135     }
 136
 137     inline void radixSort::reset_indices( void ) {
 138
 139         for(sal_uInt32 i=0;i<m_current_size;i++)
 140             m_indices1[i] = i;
 141     }
 142
 143     bool radixSort::prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) {
 144
 145         // clear counters
 146         sal_uInt32 *ptr = m_counter;
 147         for(int i=0; i<64; ++i)
 148         {
 149             *ptr++ = 0;
 150             *ptr++ = 0;
 151             *ptr++ = 0;
 152             *ptr++ = 0;
 153             *ptr++ = 0;
 154             *ptr++ = 0;
 155             *ptr++ = 0;
 156             *ptr++ = 0;
 157             *ptr++ = 0;
 158             *ptr++ = 0;
 159             *ptr++ = 0;
 160             *ptr++ = 0;
 161             *ptr++ = 0;
 162             *ptr++ = 0;
 163             *ptr++ = 0;
 164             *ptr++ = 0;
 165         }
 166
 167         // prepare pointers to relevant memory addresses
 168         sal_uInt8 *p = (sal_uInt8*)pInput;
 169         sal_uInt8 *pe = p+(nNumElements*dwStride);
 170         sal_uInt32 *h0= &m_counter[0];
 171         sal_uInt32 *h1= &m_counter[256];
 172         sal_uInt32 *h2= &m_counter[512];
 173         sal_uInt32 *h3= &m_counter[768];
 174
 175         sal_uInt32 *Indices = m_indices1;
 176         float previous_value = *(float *)(((sal_uInt8 *)pInput)+(m_indices1[0]*dwStride));
 177         bool bSorted = true;
 178         while(p!=pe) {
 179             float value = *(float *)(((sal_uInt8 *)pInput)+((*Indices++)*dwStride));
 180             if(value<previous_value)    {
 181                 bSorted = false;
 182                 break;
 183             }
 184             previous_value = value;
 185             h0[*p++]++;
 186             h1[*p++]++;
 187             h2[*p++]++;
 188             h3[*p++]++;
 189             p += dwStride-4;
 190         }
 191         if(bSorted)
 192             return true;
 193         while(p!=pe) {
 194             h0[*p++]++;
 195             h1[*p++]++;
 196             h2[*p++]++;
 197             h3[*p++]++;
 198             p += dwStride-4;
 199         }
 200         return false;
 201     }
 202
 203     bool radixSort::sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) {
 204
 205         if(!(pInput))
 206             return false;
 207         if(!(nNumElements))
 208             return false;
 209         if(!(resize(nNumElements)))
 210             return false;
 211
 212         // prepare radix counters, return if already sorted
 213         if(prepareCounters(pInput,nNumElements,dwStride))
 214             return true;
 215
 216         // count number of negative values
 217         sal_uInt32 num_negatives = 0;
 218         sal_uInt32 *h3= &m_counter[768];
 219         for(sal_uInt32 i=128;i<256;i++)
 220             num_negatives += h3[i];
 221
 222         // perform passes, one for each byte
 223         for(sal_uInt32 j=0;j<4;j++) {
 224
 225             // ignore this pass if all values have the same byte
 226             bool bRun = true;
 227             sal_uInt32 *current_counter = &m_counter[j<<8];
 228             sal_uInt8 unique_value = *(((sal_uInt8*)pInput)+j);
 229             if(current_counter[unique_value]==nNumElements)
 230                 bRun=false;
 231
 232             // does the incoming byte contain the sign bit?
 233             sal_uInt32 i;
 234             if(j!=3) {
 235                 if(bRun) {
 236                     m_offset[0] = 0;
 237                     for(i=1;i<256;i++)
 238                         m_offset[i] = m_offset[i-1] + current_counter[i-1];
 239                     sal_uInt8 *InputBytes = (sal_uInt8 *)pInput;
 240                     sal_uInt32 *Indices = m_indices1;
 241                     sal_uInt32 *IndicesEnd = &m_indices1[nNumElements];
 242                     InputBytes += j;
 243                     while(Indices!=IndicesEnd) {
 244                         sal_uInt32 id = *Indices++;
 245                         m_indices2[m_offset[InputBytes[id*dwStride]]++] = id;
 246                     }
 247                     sal_uInt32 *Tmp = m_indices1;
 248                     m_indices1 = m_indices2;
 249                     m_indices2 = Tmp;
 250                 }
 251             }
 252             else {
 253                 if(bRun) {
 254                     m_offset[0] = num_negatives;
 255                     for(i=1;i<128;i++)
 256                         m_offset[i] = m_offset[i-1] + current_counter[i-1];
 257                     m_offset[255] = 0;
 258                     for(i=0;i<127;i++)
 259                         m_offset[254-i] = m_offset[255-i] + current_counter[255-i];
 260                     for(i=128;i<256;i++)
 261                         m_offset[i] += current_counter[i];
 262                     for(i=0;i<nNumElements;i++) {
 263                         sal_uInt32 Radix = (*(sal_uInt32 *)(((sal_uInt8 *)pInput)+(m_indices1[i]*dwStride)))>>24;
 264                         if(Radix<128) m_indices2[m_offset[Radix]++] = m_indices1[i];
 265                         else m_indices2[--m_offset[Radix]] = m_indices1[i];
 266                     }
 267                     sal_uInt32 *Tmp = m_indices1;
 268                     m_indices1 = m_indices2;
 269                     m_indices2 = Tmp;
 270                 }
 271                 else {
 272                     if(unique_value>=128) {
 273                         for(i=0;i<nNumElements;i++)
 274                             m_indices2[i] = m_indices1[nNumElements-i-1];
 275                         sal_uInt32 *Tmp = m_indices1;
 276                         m_indices1 = m_indices2;
 277                         m_indices2 = Tmp;
 278                     }
 279                 }
 280             }
 281         }
 282
 283         return true;
 284     }
 285
 286     //************************************************************
 287     // Internal vertex storage of B2DPolyPolygonRasterConverter
 288     //************************************************************
 289
 290     inline B2DPolyPolygonRasterConverter::Vertex::Vertex() :
 291         aP1(),
 292         aP2(),
 293         bDownwards( true )
 294     {
 295     }
 296
 297     inline B2DPolyPolygonRasterConverter::Vertex::Vertex( const B2DPoint& rP1, const B2DPoint& rP2, bool bDown ) :
 298         aP1( rP1 ),
 299         aP2( rP2 ),
 300         bDownwards( bDown )
 301     {
 302     }
 303
 304
 305     //************************************************************
 306     // Helper class for holding horizontal line segments during raster
 307     // conversion
 308     //************************************************************
 309
 310     namespace
 311     {
 312         class ImplLineNode
 313         {
 314         public:
 315             sal_Int32   mnYCounter;
 316             float       mfXPos;
 317             float       mfXDelta;
 318             bool        mbDownwards;
 319
 320         public:
 321             /**rP1 and rP2 must not have equal y values, when rounded
 322                to integer!
 323             */
 324             ImplLineNode(const B2DPoint& rP1, const B2DPoint& rP2, bool bDown) :
 325                 mnYCounter( fround(rP2.getY()) - fround(rP1.getY()) ),
 326                 mfXPos( (float)(rP1.getX()) ),
 327                 mfXDelta((float) ((rP2.getX() - rP1.getX()) / mnYCounter) ),
 328                 mbDownwards( bDown )
 329             {
 330             }
 331
 332             /// get current x position
 333             const float& getXPos() const
 334             {
 335                 return mfXPos;
 336             }
 337
 338             /// returns true, if line ends on this Y value
 339             float nextLine()
 340             {
 341                 if(mnYCounter>=0)
 342                 {
 343                     // go one step in Y
 344                     mfXPos += mfXDelta;
 345                     --mnYCounter;
 346                     return mfXDelta;
 347                 }
 348
 349                 return 0.0f;
 350             }
 351
 352             bool isEnded()
 353             {
 354                 return mnYCounter<=0;
 355             }
 356
 357             bool isDownwards()
 358             {
 359                 return mbDownwards;
 360             }
 361         };
 362     }
 363
 364     typedef ::std::vector<ImplLineNode> VectorOfLineNodes;
 365
 366
 367     //************************************************************
 368     //   Base2D PolyPolygon Raster Converter (Rasterizer)
 369     //************************************************************
 370
 371     namespace
 372     {
 373         struct VertexComparator
 374         {
 375             bool operator()( const B2DPolyPolygonRasterConverter::Vertex& rLHS,
 376                              const B2DPolyPolygonRasterConverter::Vertex& rRHS )
 377             {
 378                 return rLHS.aP1.getX() < rRHS.aP1.getX();
 379             }
 380         };
 381     }
 382
 383     void B2DPolyPolygonRasterConverter::init()
 384     {
 385         if(!maPolyPolyRectangle.isEmpty())
 386         {
 387             const sal_Int32 nMinY( fround(maPolyPolyRectangle.getMinY()) );
 388             const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY);
 389
 390             maScanlines.resize( nScanlines+1 );
 391
 392             // add all polygons
 393             for( sal_uInt32 i(0), nCount(maPolyPolygon.count());
 394                  i < nCount;
 395                  ++i )
 396             {
 397                 // add all vertices
 398                 const B2DPolygon& rPoly( maPolyPolygon.getB2DPolygon(i) );
 399                 for( sal_uInt32 k(0), nVertices(rPoly.count());
 400                      k<nVertices;
 401                      ++k )
 402                 {
 403                     const B2DPoint& rP1( rPoly.getB2DPoint(k) );
 404                     const B2DPoint& rP2( rPoly.getB2DPoint( (k + 1) % nVertices ) );
 405
 406                     const sal_Int32 nVertexYP1( fround(rP1.getY()) );
 407                     const sal_Int32 nVertexYP2( fround(rP2.getY()) );
 408
 409                     // insert only vertices which are not strictly
 410                     // horizontal. Note that the ImplLineNode relies on
 411                     // this.
 412                     if(nVertexYP1 != nVertexYP2)
 413                     {
 414                         if( nVertexYP2 < nVertexYP1 )
 415                         {
 416                             const sal_Int32 nStartScanline(nVertexYP2 - nMinY);
 417
 418                             // swap edges
 419                             maScanlines[ nStartScanline ].push_back( Vertex(rP2, rP1, false) );
 420                         }
 421                         else
 422                         {
 423                             const sal_Int32 nStartScanline(nVertexYP1 - nMinY);
 424
 425                             maScanlines[ nStartScanline ].push_back( Vertex(rP1, rP2, true) );
 426                         }
 427                     }
 428                 }
 429             }
 430
 431             // now sort all scanlines, with increasing x coordinates
 432             VectorOfVertexVectors::iterator aIter( maScanlines.begin() );
 433             VectorOfVertexVectors::iterator aEnd( maScanlines.end() );
 434             while( aIter != aEnd )
 435             {
 436                 ::std::sort( aIter->begin(),
 437                              aIter->end(),
 438                              VertexComparator() );
 439                 ++aIter;
 440             }
 441         }
 442     }
 443
 444     B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPoly ) :
 445         maPolyPolygon( rPolyPoly ),
 446         maPolyPolyRectangle( tools::getRange( rPolyPoly ) ),
 447         maScanlines()
 448     {
 449         init();
 450     }
 451
 452     namespace
 453     {
 454         B2DRectangle getCombinedBounds( const B2DPolyPolygon& rPolyPolyRaster,
 455                                         const B2DRectangle&   rRasterArea )
 456         {
 457             B2DRectangle aRect( tools::getRange( rPolyPolyRaster ) );
 458             aRect.expand( rRasterArea );
 459
 460             return aRect;
 461         }
 462     }
 463
 464     B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPolyRaster,
 465                                                                   const B2DRectangle&   rRasterArea ) :
 466         maPolyPolygon( rPolyPolyRaster ),
 467         maPolyPolyRectangle(
 468             getCombinedBounds( rPolyPolyRaster,
 469                                rRasterArea ) ),
 470         maScanlines()
 471     {
 472         init();
 473     }
 474
 475     B2DPolyPolygonRasterConverter::~B2DPolyPolygonRasterConverter()
 476     {
 477     }
 478
 479     namespace
 480     {
 481         class LineNodeGenerator
 482         {
 483         public:
 484             LineNodeGenerator( VectorOfLineNodes& rActiveVertices ) :
 485                 mrActiveVertices( rActiveVertices )
 486             {
 487             }
 488
 489             void operator()( const B2DPolyPolygonRasterConverter::Vertex& rVertex )
 490             {
 491                 mrActiveVertices.push_back( ImplLineNode(rVertex.aP1,
 492                                                          rVertex.aP2,
 493                                                          rVertex.bDownwards) );
 494             }
 495
 496         private:
 497             VectorOfLineNodes& mrActiveVertices;
 498         };
 499
 500         struct LineNodeComparator
 501         {
 502             bool operator()( const ImplLineNode& rLHS, const ImplLineNode& rRHS )
 503             {
 504                 return rLHS.getXPos() < rRHS.getXPos();
 505             }
 506         };
 507     }
 508
 509     void B2DPolyPolygonRasterConverter::rasterConvert( FillRule eFillRule )
 510     {
 511         if( maScanlines.empty() )
 512             return; // no scanlines at all -> bail out
 513
 514         const sal_Int32 nMinY( fround(maPolyPolyRectangle.getMinY()) );
 515         const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY);
 516
 517         // Vector of currently active vertices. A vertex is active, if
 518         // it crosses or touches the current scanline.
 519         VectorOfLineNodes   aActiveVertices;
 520
 521         // mickey's optimized version...
 522         radixSort   rs;
 523         std::size_t nb(0);
 524         std::size_t nb_previous(0);
 525         bool        bSort(false);
 526
 527         // process each scanline
 528         for( sal_Int32 y(0); y <= nScanlines; ++y )
 529         {
 530             // add vertices which start at current scanline into
 531             // active vertex vector
 532             ::std::for_each( maScanlines[y].begin(),
 533                              maScanlines[y].end(),
 534                              LineNodeGenerator( aActiveVertices ) );
 535             nb = aActiveVertices.size();
 536             if(nb != nb_previous)
 537             {
 538                 nb_previous = nb;
 539                 bSort = true;
 540             }
 541
 542             // sort with increasing X
 543             if(bSort)
 544             {
 545                 bSort = false;
 546
 547                 if( nb )
 548                 {
 549                     rs.sort(&aActiveVertices[0].mfXPos,
 550                             nb,
 551                             sizeof(ImplLineNode));
 552                 }
 553             }
 554
 555             const std::size_t nLen( nb );
 556             if( !nLen )
 557             {
 558                 // empty scanline - call derived with an 'off' span
 559                 // for the full width
 560                 span( maPolyPolyRectangle.getMinX(),
 561                       maPolyPolyRectangle.getMaxX(),
 562                       nMinY + y,
 563                       false );
 564             }
 565             else
 566             {
 567                 const sal_Int32 nCurrY( nMinY + y );
 568
 569                 // scanline not empty - forward all scans to derived,
 570                 // according to selected fill rule
 571
 572                 // TODO(P1): Maybe allow these 'off' span calls to be
 573                 // switched off (or all 'on' span calls, depending on
 574                 // use case scenario)
 575
 576                 // sorting didn't change the order of the elements
 577                 // in memory but prepared a list of indices in sorted order.
 578                 // thus we now process the nodes with an additional indirection.
 579                 sal_uInt32 *sorted = rs.indices();
 580
 581                 // call derived with 'off' span for everything left of first active span
 582                 if( aActiveVertices[sorted[0]].getXPos() > maPolyPolyRectangle.getMinX() )
 583                 {
 584                     span( maPolyPolyRectangle.getMinX(),
 585                           aActiveVertices[sorted[0]].getXPos(),
 586                           nCurrY,
 587                           false );
 588                 }
 589
 590                 switch( eFillRule )
 591                 {
 592                     default:
 593                         OSL_ENSURE(false,
 594                                    "B2DPolyPolygonRasterConverter::rasterConvert(): Unexpected fill rule");
 595                         return;
 596
 597                     case FillRule_EVEN_ODD:
 598                         // process each span in current scanline, with
 599                         // even-odd fill rule
 600                         for( ::std::size_t i(0), nLength(aActiveVertices.size());
 601                              i+1 < nLength;
 602                              ++i )
 603                         {
 604                             sal_uInt32 nIndex = sorted[i];
 605                             sal_uInt32 nNextIndex = sorted[i+1];
 606                             span( aActiveVertices[nIndex].getXPos(),
 607                                   aActiveVertices[nNextIndex].getXPos(),
 608                                   nCurrY,
 609                                   i % 2 == 0 );
 610
 611                             float delta = aActiveVertices[nIndex].nextLine();
 612                             if(delta > 0.0f)
 613                             {
 614                                 if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos())
 615                                     bSort = true;
 616                             }
 617                             else if(delta < 0.0f)
 618                             {
 619                                 if(i)
 620                                 {
 621                                     sal_uInt32 nPrevIndex = sorted[i-1];
 622                                     if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos())
 623                                         bSort = true;
 624                                 }
 625                             }
 626                         }
 627                         break;
 628
 629                     case FillRule_NONZERO_WINDING_NUMBER:
 630                         // process each span in current scanline, with
 631                         // non-zero winding numbe fill rule
 632                         sal_Int32 nWindingNumber(0);
 633                         for( ::std::size_t i(0), nLength(aActiveVertices.size());
 634                              i+1 < nLength;
 635                              ++i )
 636                         {
 637                             sal_uInt32 nIndex = sorted[i];
 638                             sal_uInt32 nNextIndex = sorted[i+1];
 639                             nWindingNumber += -1 + 2*aActiveVertices[nIndex].isDownwards();
 640
 641                             span( aActiveVertices[nIndex].getXPos(),
 642                                   aActiveVertices[nNextIndex].getXPos(),
 643                                   nCurrY,
 644                                   nWindingNumber != 0 );
 645
 646                             float delta = aActiveVertices[nIndex].nextLine();
 647                             if(delta > 0.0f)
 648                             {
 649                                 if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos())
 650                                     bSort = true;
 651                             }
 652                             else if(delta < 0.0f)
 653                             {
 654                                 if(i)
 655                                 {
 656                                     sal_uInt32 nPrevIndex = sorted[i-1];
 657                                     if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos())
 658                                         bSort = true;
 659                                 }
 660                             }
 661                         }
 662                         break;
 663                 }
 664
 665                 // call derived with 'off' span for everything right of last active span
 666                 if( aActiveVertices[sorted[nb-1]].getXPos()+1.0 < maPolyPolyRectangle.getMaxX() )
 667                 {
 668                     span( aActiveVertices[sorted[nb-1]].getXPos()+1.0,
 669                           maPolyPolyRectangle.getMaxX(),
 670                           nCurrY,
 671                           false );
 672                 }
 673
 674                 // also call nextLine on very last line node
 675                 sal_uInt32 nIndex = sorted[nb-1];
 676                 float delta = aActiveVertices[nIndex].nextLine();
 677                 if(delta < 0.0f)
 678                 {
 679                     if(nb)
 680                     {
 681                         sal_uInt32 nPrevIndex = sorted[nb-2];
 682                         if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos())
 683                             bSort = true;
 684                     }
 685                 }
 686             }
 687
 688             // remove line nodes which have ended on the current scanline
 689             aActiveVertices.erase( ::std::remove_if( aActiveVertices.begin(),
 690                                                      aActiveVertices.end(),
 691                                                      ::boost::mem_fn( &ImplLineNode::isEnded ) ),
 692                                    aActiveVertices.end() );
 693             nb = aActiveVertices.size();
 694             if(nb != nb_previous)
 695             {
 696                 nb_previous = nb;
 697                 bSort = true;
 698             }
 699         }
 700     }
 701 }
 702 // eof