qtools/qgvector.cpp

   1 /****************************************************************************
   2 **
   3 **
   4 ** Implementation of QGVector class
   5 **
   6 ** Created : 930907
   7 **
   8 ** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
   9 **
  10 ** This file is part of the tools module of the Qt GUI Toolkit.
  11 **
  12 ** This file may be distributed under the terms of the Q Public License
  13 ** as defined by Trolltech AS of Norway and appearing in the file
  14 ** LICENSE.QPL included in the packaging of this file.
  15 **
  16 ** This file may be distributed and/or modified under the terms of the
  17 ** GNU General Public License version 2 as published by the Free Software
  18 ** Foundation and appearing in the file LICENSE.GPL included in the
  19 ** packaging of this file.
  20 **
  21 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
  22 ** licenses may use this file in accordance with the Qt Commercial License
  23 ** Agreement provided with the Software.
  24 **
  25 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  26 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27 **
  28 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
  29 **   information about Qt Commercial License Agreements.
  30 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
  31 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
  32 **
  33 ** Contact info@trolltech.com if any conditions of this licensing are
  34 ** not clear to you.
  35 **
  36 **********************************************************************/
  37
  38 #define  QGVECTOR_CPP
  39 #include "qgvector.h"
  40 #include "qglist.h"
  41 #include "qstring.h"
  42 #include "qdatastream.h"
  43 #include <stdlib.h>
  44
  45 #define USE_MALLOC                              // comment to use new/delete
  46
  47 #undef NEW
  48 #undef DELETE
  49
  50 #if defined(USE_MALLOC)
  51 #define NEW(type,size)  ((type*)malloc(size*sizeof(type)))
  52 #define DELETE(array)   (free((char*)array))
  53 #else
  54 #define NEW(type,size)  (new type[size])
  55 #define DELETE(array)   (delete[] array)
  56 #define DONT_USE_REALLOC                        // comment to use realloc()
  57 #endif
  58
  59 // NOT REVISED
  60
  61 /*!
  62   \class QGVector qgvector.h
  63
  64   \brief The QGVector class is an internal class for implementing Qt
  65   collection classes.
  66
  67   QGVector is a strictly internal class that acts as a base class for
  68   the QVector collection class.
  69
  70   QGVector has some virtual functions that may be reimplemented in
  71   subclasses to to customize behavior.
  72
  73   <ul>
  74   <li> compareItems() compares two collection/vector items.
  75   <li> read() reads a collection/vector item from a QDataStream.
  76   <li> write() writes a collection/vector item to a QDataStream.
  77   </ul>
  78 */
  79
  80 /*****************************************************************************
  81   Default implementation of virtual functions
  82  *****************************************************************************/
  83
  84 /*!
  85   This virtual function compares two list items.
  86
  87   Returns:
  88   <ul>
  89   <li> 0 if \a item1 == \a item2
  90   <li> non-zero if \a item1 != \a item2
  91   </ul>
  92
  93   This function returns \e int rather than \e bool so that
  94   reimplementations can return one of three values and use it to sort
  95   by:
  96
  97   <ul>
  98   <li> 0 if \e item1 == \e item2
  99   <li> \> 0 (positive integer) if \a item1 \> \a item2
 100   <li> \< 0 (negative integer) if \a item1 \< \a item2
 101   </ul>
 102
 103   The QVector::sort() and QVector::bsearch() functions require that
 104   compareItems() is implemented as described here.
 105
 106   This function should not modify the vector because some const
 107   functions call compareItems().
 108 */
 109
 110 int QGVector::compareItems( Item d1, Item d2 )
 111 {
 112     return d1 != d2;                            // compare pointers
 113 }
 114
 115 #ifndef QT_NO_DATASTREAM
 116 /*!
 117   Reads a collection/vector item from the stream \a s and returns a reference
 118   to the stream.
 119
 120   The default implementation sets \e item to 0.
 121
 122   \sa write()
 123 */
 124
 125 QDataStream &QGVector::read( QDataStream &s, Item &d )
 126 {                                               // read item from stream
 127     d = 0;
 128     return s;
 129 }
 130
 131 /*!
 132   Writes a collection/vector item to the stream \a s and returns a reference
 133   to the stream.
 134
 135   The default implementation does nothing.
 136
 137   \sa read()
 138 */
 139
 140 QDataStream &QGVector::write( QDataStream &s, Item ) const
 141 {                                               // write item to stream
 142     return s;
 143 }
 144 #endif // QT_NO_DATASTREAM
 145
 146 /*****************************************************************************
 147   QGVector member functions
 148  *****************************************************************************/
 149
 150 /*!
 151   \internal
 152 */
 153
 154 QGVector::QGVector()                            // create empty vector
 155 {
 156     vec = 0;
 157     len = numItems = 0;
 158 }
 159
 160 /*!
 161   \internal
 162 */
 163 QGVector::QGVector( uint size )                 // create vectors with nullptrs
 164 {
 165     len = size;
 166     numItems = 0;
 167     if ( len == 0 ) {                           // zero length
 168         vec = 0;
 169         return;
 170     }
 171     vec = NEW(Item,len);
 172     CHECK_PTR( vec );
 173     memset( (void*)vec, 0, len*sizeof(Item) );  // fill with nulls
 174 }
 175
 176 /*!
 177   \internal
 178 */
 179
 180 QGVector::QGVector( const QGVector &a )         // make copy of other vector
 181     : QCollection( a )
 182 {
 183     len = a.len;
 184     numItems = a.numItems;
 185     vec = NEW(Item,len);
 186     CHECK_PTR( vec );
 187     for ( uint i=0; i<len; i++ ) {
 188         vec[i] = a.vec[i] ? newItem( a.vec[i] ) : 0;
 189         CHECK_PTR( vec[i] );
 190     }
 191 }
 192
 193 /*!
 194   \internal
 195 */
 196
 197 QGVector::~QGVector()
 198 {
 199     clear();
 200 }
 201
 202
 203 /*!
 204   \internal
 205 */
 206
 207 QGVector& QGVector::operator=( const QGVector &v )
 208 {                                               // assign from other vector
 209     clear();                                    // first delete old vector
 210     len = v.len;
 211     numItems = v.numItems;
 212     vec = NEW(Item,len);                                // create new vector
 213     CHECK_PTR( vec );
 214     for ( uint i=0; i<len; i++ ) {              // copy elements
 215         vec[i] = v.vec[i] ? newItem( v.vec[i] ) : 0;
 216         CHECK_PTR( vec[i] );
 217     }
 218     return *this;
 219 }
 220
 221
 222 /*!
 223   \fn Item *QGVector::data() const
 224   \internal
 225 */
 226
 227 /*!
 228   \fn uint QGVector::size() const
 229   \internal
 230 */
 231
 232 /*!
 233   \fn uint QGVector::count() const
 234   \internal
 235 */
 236
 237 /*!
 238   \fn Item QGVector::at( uint index ) const
 239   \internal
 240 */
 241
 242 /*!
 243   \internal
 244 */
 245
 246 bool QGVector::insert( uint index, Item d )     // insert item at index
 247 {
 248 #if defined(CHECK_RANGE)
 249     if ( index >= len ) {                       // range error
 250         qWarning( "QGVector::insert: Index %d out of range", index );
 251         return FALSE;
 252     }
 253 #endif
 254     if ( vec[index] ) {                         // remove old item
 255         deleteItem( vec[index] );
 256         numItems--;
 257     }
 258     if ( d ) {
 259         vec[index] = newItem( d );
 260         CHECK_PTR( vec[index] );
 261         numItems++;
 262         return vec[index] != 0;
 263     } else {
 264         vec[index] = 0;                         // reset item
 265     }
 266     return TRUE;
 267 }
 268
 269 /*!
 270   \internal
 271 */
 272
 273 bool QGVector::remove( uint index )             // remove item at index
 274 {
 275 #if defined(CHECK_RANGE)
 276     if ( index >= len ) {                       // range error
 277         qWarning( "QGVector::remove: Index %d out of range", index );
 278         return FALSE;
 279     }
 280 #endif
 281     if ( vec[index] ) {                         // valid item
 282         deleteItem( vec[index] );               // delete it
 283         vec[index] = 0;                         // reset pointer
 284         numItems--;
 285     }
 286     return TRUE;
 287 }
 288
 289 /*!
 290   \internal
 291 */
 292
 293 QCollection::Item QGVector::take( uint index )          // take out item
 294 {
 295 #if defined(CHECK_RANGE)
 296     if ( index >= len ) {                       // range error
 297         qWarning( "QGVector::take: Index %d out of range", index );
 298         return 0;
 299     }
 300 #endif
 301     Item d = vec[index];                                // don't delete item
 302     if ( d )
 303         numItems--;
 304     vec[index] = 0;
 305     return d;
 306 }
 307
 308
 309 /*!
 310   \internal
 311 */
 312
 313 void QGVector::clear()                          // clear vector
 314 {
 315     if ( vec ) {
 316         for ( uint i=0; i<len; i++ ) {          // delete each item
 317             if ( vec[i] )
 318                 deleteItem( vec[i] );
 319         }
 320         DELETE(vec);
 321         vec = 0;
 322         len = numItems = 0;
 323     }
 324 }
 325
 326 /*!
 327   \internal
 328 */
 329
 330 bool QGVector::resize( uint newsize )           // resize array
 331 {
 332     if ( newsize == len )                       // nothing to do
 333         return TRUE;
 334     if ( vec ) {                                // existing data
 335         if ( newsize < len ) {                  // shrink vector
 336             uint i = newsize;
 337             while ( i < len ) {                 // delete lost items
 338                 if ( vec[i] ) {
 339                     deleteItem( vec[i] );
 340                     numItems--;
 341                 }
 342                 i++;
 343             }
 344         }
 345         if ( newsize == 0 ) {                   // vector becomes empty
 346             DELETE(vec);
 347             vec = 0;
 348             len = numItems = 0;
 349             return TRUE;
 350         }
 351 #if defined(DONT_USE_REALLOC)
 352         Item *newvec = NEW(Item,newsize);               // manual realloc
 353         memcpy( newvec, vec, (len < newsize ? len : newsize)*sizeof(Item) );
 354         DELETE(vec);
 355         vec = newvec;
 356 #else
 357         vec = (Item*)realloc( (char *)vec, newsize*sizeof(Item) );
 358 #endif
 359     } else {                                    // create new vector
 360         vec = NEW(Item,newsize);
 361         len = numItems = 0;
 362     }
 363     CHECK_PTR( vec );
 364     if ( !vec )                                 // no memory
 365         return FALSE;
 366     if ( newsize > len )                        // init extra space added
 367         memset( (void*)&vec[len], 0, (newsize-len)*sizeof(Item) );
 368     len = newsize;
 369     return TRUE;
 370 }
 371
 372
 373 /*!
 374   \internal
 375 */
 376
 377 bool QGVector::fill( Item d, int flen )         // resize and fill vector
 378 {
 379     if ( flen < 0 )
 380         flen = len;                             // default: use vector length
 381     else if ( !resize( flen ) )
 382         return FALSE;
 383     for ( uint i=0; i<(uint)flen; i++ )         // insert d at every index
 384         insert( i, d );
 385     return TRUE;
 386 }
 387
 388
 389 static QGVector *sort_vec=0;                    // current sort vector
 390
 391
 392 #if defined(Q_C_CALLBACKS)
 393 extern "C" {
 394 #endif
 395
 396 static int cmp_vec( const void *n1, const void *n2 )
 397 {
 398     return sort_vec->compareItems( *((QCollection::Item*)n1), *((QCollection::Item*)n2) );
 399 }
 400
 401 #if defined(Q_C_CALLBACKS)
 402 }
 403 #endif
 404
 405
 406 /*!
 407   \internal
 408 */
 409
 410 void QGVector::sort()                           // sort vector
 411 {
 412     if ( count() == 0 )                         // no elements
 413         return;
 414     register Item *start = &vec[0];
 415     register Item *end  = &vec[len-1];
 416     Item tmp;
 417     while ( TRUE ) {                            // put all zero elements behind
 418         while ( start < end && *start != 0 )
 419             start++;
 420         while ( end > start && *end == 0 )
 421             end--;
 422         if ( start < end ) {
 423             tmp = *start;
 424             *start = *end;
 425             *end = tmp;
 426         } else {
 427             break;
 428         }
 429     }
 430     sort_vec = (QGVector*)this;
 431     qsort( vec, count(), sizeof(Item), cmp_vec );
 432     sort_vec = 0;
 433 }
 434
 435 /*!
 436   \internal
 437 */
 438
 439 int QGVector::bsearch( Item d ) const           // binary search; when sorted
 440 {
 441     if ( !len )
 442         return -1;
 443     if ( !d ) {
 444 #if defined(CHECK_NULL)
 445         qWarning( "QGVector::bsearch: Cannot search for null object" );
 446 #endif
 447         return -1;
 448     }
 449     int n1 = 0;
 450     int n2 = len - 1;
 451     int mid = 0;
 452     bool found = FALSE;
 453     while ( n1 <= n2 ) {
 454         int  res;
 455         mid = (n1 + n2)/2;
 456         if ( vec[mid] == 0 )                    // null item greater
 457             res = -1;
 458         else
 459             res = ((QGVector*)this)->compareItems( d, vec[mid] );
 460         if ( res < 0 )
 461             n2 = mid - 1;
 462         else if ( res > 0 )
 463             n1 = mid + 1;
 464         else {                                  // found it
 465             found = TRUE;
 466             break;
 467         }
 468     }
 469     if ( !found )
 470         return -1;
 471     // search to first of equal items
 472     while ( (mid - 1 >= 0) && !((QGVector*)this)->compareItems(d, vec[mid-1]) )
 473         mid--;
 474     return mid;
 475 }
 476
 477
 478 /*!
 479   \internal
 480 */
 481
 482 int QGVector::findRef( Item d, uint index) const // find exact item in vector
 483 {
 484 #if defined(CHECK_RANGE)
 485     if ( index >= len ) {                       // range error
 486         qWarning( "QGVector::findRef: Index %d out of range", index );
 487         return -1;
 488     }
 489 #endif
 490     for ( uint i=index; i<len; i++ ) {
 491         if ( vec[i] == d )
 492             return i;
 493     }
 494     return -1;
 495 }
 496
 497 /*!
 498   \internal
 499 */
 500
 501 int QGVector::find( Item d, uint index ) const  // find equal item in vector
 502 {
 503 #if defined(CHECK_RANGE)
 504     if ( index >= len ) {                       // range error
 505         qWarning( "QGVector::find: Index %d out of range", index );
 506         return -1;
 507     }
 508 #endif
 509     for ( uint i=index; i<len; i++ ) {
 510         if ( vec[i] == 0 && d == 0 )            // found null item
 511             return i;
 512         if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 )
 513             return i;
 514     }
 515     return -1;
 516 }
 517
 518 /*!
 519   \internal
 520 */
 521
 522 uint QGVector::containsRef( Item d ) const      // get number of exact matches
 523 {
 524     uint count = 0;
 525     for ( uint i=0; i<len; i++ ) {
 526         if ( vec[i] == d )
 527             count++;
 528     }
 529     return count;
 530 }
 531
 532 /*!
 533   \internal
 534 */
 535
 536 uint QGVector::contains( Item d ) const         // get number of equal matches
 537 {
 538     uint count = 0;
 539     for ( uint i=0; i<len; i++ ) {
 540         if ( vec[i] == 0 && d == 0 )            // count null items
 541             count++;
 542         if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 )
 543             count++;
 544     }
 545     return count;
 546 }
 547
 548
 549 /*!
 550   \internal
 551 */
 552
 553 bool QGVector::insertExpand( uint index, Item d )// insert and grow if necessary
 554 {
 555     if ( index >= len ) {
 556         if ( !resize( index+1 ) )               // no memory
 557             return FALSE;
 558     }
 559     insert( index, d );
 560     return TRUE;
 561 }
 562
 563
 564 /*!
 565   \internal
 566 */
 567
 568 void QGVector::toList( QGList *list ) const     // store items in list
 569 {
 570     list->clear();
 571     for ( uint i=0; i<len; i++ ) {
 572         if ( vec[i] )
 573             list->append( vec[i] );
 574     }
 575 }
 576
 577
 578 void QGVector::warningIndexRange( uint i )
 579 {
 580 #if defined(CHECK_RANGE)
 581     qWarning( "QGVector::operator[]: Index %d out of range", i );
 582 #else
 583     Q_UNUSED( i )
 584 #endif
 585 }
 586
 587
 588 /*****************************************************************************
 589   QGVector stream functions
 590  *****************************************************************************/
 591 #ifndef QT_NO_DATASTREAM
 592 QDataStream &operator>>( QDataStream &s, QGVector &vec )
 593 {                                               // read vector
 594     return vec.read( s );
 595 }
 596
 597 QDataStream &operator<<( QDataStream &s, const QGVector &vec )
 598 {                                               // write vector
 599     return vec.write( s );
 600 }
 601
 602 /*!
 603   \internal
 604 */
 605
 606 QDataStream &QGVector::read( QDataStream &s )   // read vector from stream
 607 {
 608     uint num;
 609     s >> num;                                   // read number of items
 610     clear();                                    // clear vector
 611     resize( num );
 612     for (uint i=0; i<num; i++) {                // read all items
 613         Item d;
 614         read( s, d );
 615         CHECK_PTR( d );
 616         if ( !d )                               // no memory
 617             break;
 618         vec[i] = d;
 619     }
 620     return s;
 621 }
 622
 623 /*!
 624   \internal
 625 */
 626
 627 QDataStream &QGVector::write( QDataStream &s ) const
 628 {                                               // write vector to stream
 629     uint num = count();
 630     s << num;                                   // number of items to write
 631     num = size();
 632     for (uint i=0; i<num; i++) {                // write non-null items
 633         if ( vec[i] )
 634             write( s, vec[i] );
 635     }
 636     return s;
 637 }
 638 #endif // QT_NO_DATASTREAM