qtools/qglist.cpp

   1 /****************************************************************************
   2 **
   3 **
   4 ** Implementation of QGList and QGListIterator classes
   5 **
   6 ** Created : 920624
   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 #include "qglist.h"
  39 #include "qgvector.h"
  40 #include "qdatastream.h"
  41
  42
  43 // NOT REVISED
  44 /*!
  45   \class QLNode qglist.h
  46   \brief The QLNode class is an internal class for the QList template collection.
  47
  48   QLNode is a doubly linked list node; it has three pointers:
  49   <ol>
  50   <li> Pointer to the previous node.
  51   <li> Pointer to the next node.
  52   <li> Pointer to the actual data.
  53   </ol>
  54
  55   Sometimes it might be practical to have direct access to the list nodes
  56   in a QList, but it is seldom required.
  57
  58   \warning Be very careful if you want to access the list nodes. The heap
  59   can easily get corrupted if you make a mistake.
  60
  61   \sa QList::currentNode(), QList::removeNode(), QList::takeNode()
  62 */
  63
  64 /*!
  65   \fn QCollection::Item QLNode::getData()
  66   Returns a pointer (\c void*) to the actual data in the list node.
  67 */
  68
  69
  70 /*!
  71   \class QGList qglist.h
  72   \brief The QGList class is an internal class for implementing Qt collection classes.
  73
  74   QGList is a strictly internal class that acts as a base class for several
  75   \link collection.html collection classes\endlink; QList, QQueue and
  76   QStack.
  77
  78   QGList has some virtual functions that can be reimplemented to customize
  79   the subclasses.
  80   <ul>
  81   <li> compareItems() compares two collection/list items.
  82   <li> read() reads a collection/list item from a QDataStream.
  83   <li> write() writes a collection/list item to a QDataStream.
  84   </ul>
  85   Normally, you do not have to reimplement any of these functions.
  86   If you still want to reimplement them, see the QStrList class (qstrlist.h),
  87   which is a good example.
  88 */
  89
  90
  91 /*****************************************************************************
  92   Default implementation of virtual functions
  93  *****************************************************************************/
  94
  95 /*!
  96   This virtual function compares two list items.
  97
  98   Returns:
  99   <ul>
 100   <li> 0 if \e item1 == \e item2
 101   <li> non-zero if \e item1 != \e item2
 102   </ul>
 103
 104   This function returns \e int rather than \e bool so that
 105   reimplementations can return three values and use it to sort by:
 106
 107   <ul>
 108   <li> 0 if \e item1 == \e item2
 109   <li> \> 0 (positive integer) if \e item1 \> \e item2
 110   <li> \< 0 (negative integer) if \e item1 \< \e item2
 111   </ul>
 112
 113   The QList::inSort() function requires that compareItems() is implemented
 114   as described here.
 115
 116   This function should not modify the list because some const functions
 117   call compareItems().
 118
 119   The default implementation compares the pointers:
 120   \code
 121
 122   \endcode
 123 */
 124
 125 int QGList::compareItems( QCollection::Item item1, QCollection::Item item2 )
 126 {
 127     return item1 != item2;                      // compare pointers
 128 }
 129
 130 #ifndef QT_NO_DATASTREAM
 131 /*!
 132   Reads a collection/list item from the stream \a s and returns a reference
 133   to the stream.
 134
 135   The default implementation sets \a item to 0.
 136
 137   \sa write()
 138 */
 139
 140 QDataStream &QGList::read( QDataStream &s, QCollection::Item &item )
 141 {
 142     item = 0;
 143     return s;
 144 }
 145
 146 /*!
 147   Writes a collection/list item to the stream \a s and returns a reference
 148   to the stream.
 149
 150   The default implementation does nothing.
 151
 152   \sa read()
 153 */
 154
 155 QDataStream &QGList::write( QDataStream &s, QCollection::Item ) const
 156 {
 157     return s;
 158 }
 159 #endif // QT_NO_DATASTREAM
 160
 161 /*****************************************************************************
 162   QGList member functions
 163  *****************************************************************************/
 164
 165 /*!
 166   \internal
 167   Constructs an empty list.
 168 */
 169
 170 QGList::QGList()
 171 {
 172     firstNode = lastNode = curNode = 0;         // initialize list
 173     numNodes  = 0;
 174     curIndex  = -1;
 175     iterators = 0;                              // initialize iterator list
 176 }
 177
 178 /*!
 179   \internal
 180   Constructs a copy of \e list.
 181 */
 182
 183 QGList::QGList( const QGList & list )
 184     : QCollection( list )
 185 {
 186     firstNode = lastNode = curNode = 0;         // initialize list
 187     numNodes  = 0;
 188     curIndex  = -1;
 189     iterators = 0;                              // initialize iterator list
 190     QLNode *n = list.firstNode;
 191     while ( n ) {                               // copy all items from list
 192         append( n->data );
 193         n = n->next;
 194     }
 195 }
 196
 197 /*!
 198   \internal
 199   Removes all items from the list and destroys the list.
 200 */
 201
 202 QGList::~QGList()
 203 {
 204     clear();
 205     if ( !iterators )                           // no iterators for this list
 206         return;
 207     QGListIterator *i = (QGListIterator*)iterators->first();
 208     while ( i ) {                               // notify all iterators that
 209         i->list = 0;                            // this list is deleted
 210         i->curNode = 0;
 211         i = (QGListIterator*)iterators->next();
 212     }
 213     delete iterators;
 214 }
 215
 216
 217 /*!
 218   \internal
 219   Assigns \e list to this list.
 220 */
 221
 222 QGList& QGList::operator=( const QGList &list )
 223 {
 224     clear();
 225     if ( list.count() > 0 ) {
 226         QLNode *n = list.firstNode;
 227         while ( n ) {                           // copy all items from list
 228             append( n->data );
 229             n = n->next;
 230         }
 231         curNode  = firstNode;
 232         curIndex = 0;
 233     }
 234     return *this;
 235 }
 236
 237 /*!
 238   Compares this list with \a list. Retruns TRUE if the lists
 239   contain the same data, else FALSE.
 240 */
 241
 242 bool QGList::operator==( const QGList &list ) const
 243 {
 244     if ( count() != list.count() )
 245         return FALSE;
 246
 247     if ( count() == 0 )
 248         return TRUE;
 249
 250     QLNode *n1 = firstNode;
 251     QLNode *n2 = list.firstNode;
 252     while ( n1 && n2 ) {
 253         // should be mutable
 254         if ( ( (QGList*)this )->compareItems( n1->data, n2->data ) != 0 )
 255             return FALSE;
 256         n1 = n1->next;
 257         n2 = n2->next;
 258     }
 259
 260     return TRUE;
 261 }
 262
 263 /*!
 264   \fn uint QGList::count() const
 265   \internal
 266   Returns the number of items in the list.
 267 */
 268
 269
 270 /*!
 271   \internal
 272   Returns the node at position \e index.  Sets this node to current.
 273 */
 274
 275 QLNode *QGList::locate( uint index )
 276 {
 277     if ( index == (uint)curIndex )              // current node ?
 278         return curNode;
 279     if ( !curNode && firstNode ) {              // set current node
 280         curNode  = firstNode;
 281         curIndex = 0;
 282     }
 283     register QLNode *node;
 284     int  distance = index - curIndex;           // node distance to cur node
 285     bool forward;                               // direction to traverse
 286
 287     if ( index >= numNodes ) {
 288 #if defined(CHECK_RANGE)
 289         qWarning( "QGList::locate: Index %d out of range", index );
 290 #endif
 291         return 0;
 292     }
 293
 294     if ( distance < 0 )
 295         distance = -distance;
 296     if ( (uint)distance < index && (uint)distance < numNodes - index ) {
 297         node =  curNode;                        // start from current node
 298         forward = index > (uint)curIndex;
 299     } else if ( index < numNodes - index ) {    // start from first node
 300         node = firstNode;
 301         distance = index;
 302         forward = TRUE;
 303     } else {                                    // start from last node
 304         node = lastNode;
 305         distance = numNodes - index - 1;
 306         if ( distance < 0 )
 307             distance = 0;
 308         forward = FALSE;
 309     }
 310     if ( forward ) {                            // now run through nodes
 311         while ( distance-- )
 312             node = node->next;
 313     } else {
 314         while ( distance-- )
 315             node = node->prev;
 316     }
 317     curIndex = index;                           // must update index
 318     return curNode = node;
 319 }
 320
 321
 322 /*!
 323   \internal
 324   Inserts an item at its sorted position in the list.
 325 */
 326
 327 void QGList::inSort( QCollection::Item d )
 328 {
 329     int index = 0;
 330     register QLNode *n = firstNode;
 331     while ( n && compareItems(n->data,d) < 0 ){ // find position in list
 332         n = n->next;
 333         index++;
 334     }
 335     insertAt( index, d );
 336 }
 337
 338
 339 /*!
 340   \internal
 341   Inserts an item at the start of the list.
 342 */
 343
 344 void QGList::prepend( QCollection::Item d )
 345 {
 346     register QLNode *n = new QLNode( newItem(d) );
 347     CHECK_PTR( n );
 348     n->prev = 0;
 349     if ( (n->next = firstNode) )                // list is not empty
 350         firstNode->prev = n;
 351     else                                        // initialize list
 352         lastNode = n;
 353     firstNode = curNode = n;                    // curNode affected
 354     numNodes++;
 355     curIndex = 0;
 356 }
 357
 358
 359 /*!
 360   \internal
 361   Inserts an item at the end of the list.
 362 */
 363
 364 void QGList::append( QCollection::Item d )
 365 {
 366     register QLNode *n = new QLNode( newItem(d) );
 367     CHECK_PTR( n );
 368     n->next = 0;
 369     if ( (n->prev = lastNode) )                 // list is not empty
 370         lastNode->next = n;
 371     else                                        // initialize list
 372         firstNode = n;
 373     lastNode = curNode = n;                     // curNode affected
 374     curIndex = numNodes;
 375     numNodes++;
 376 }
 377
 378
 379 /*!
 380   \internal
 381   Inserts an item at position \e index in the list.
 382 */
 383
 384 bool QGList::insertAt( uint index, QCollection::Item d )
 385 {
 386     if ( index == 0 ) {                         // insert at head of list
 387         prepend( d );
 388         return TRUE;
 389     } else if ( index == numNodes ) {           // append at tail of list
 390         append( d );
 391         return TRUE;
 392     }
 393     QLNode *nextNode = locate( index );
 394     if ( !nextNode )                            // illegal position
 395         return FALSE;
 396     QLNode *prevNode = nextNode->prev;
 397     register QLNode *n = new QLNode( newItem(d) );
 398     CHECK_PTR( n );
 399     nextNode->prev = n;
 400     prevNode->next = n;
 401     n->prev = prevNode;                         // link new node into list
 402     n->next = nextNode;
 403     curNode = n;                                // curIndex set by locate()
 404     numNodes++;
 405     return TRUE;
 406 }
 407
 408
 409 /*!
 410   \internal
 411   Relinks node \e n and makes it the first node in the list.
 412 */
 413
 414 void QGList::relinkNode( QLNode *n )
 415 {
 416     if ( n == firstNode )                       // already first
 417         return;
 418     curNode = n;
 419     unlink();
 420     n->prev = 0;
 421     if ( (n->next = firstNode) )                // list is not empty
 422         firstNode->prev = n;
 423     else                                        // initialize list
 424         lastNode = n;
 425     firstNode = curNode = n;                    // curNode affected
 426     numNodes++;
 427     curIndex = 0;
 428 }
 429
 430
 431 /*!
 432   \internal
 433   Unlinks the current list node and returns a pointer to this node.
 434 */
 435
 436 QLNode *QGList::unlink()
 437 {
 438     if ( curNode == 0 )                         // null current node
 439         return 0;
 440     register QLNode *n = curNode;               // unlink this node
 441     if ( n == firstNode ) {                     // removing first node ?
 442         if ( (firstNode = n->next) ) {
 443             firstNode->prev = 0;
 444         } else {
 445             lastNode = curNode = 0;             // list becomes empty
 446             curIndex = -1;
 447         }
 448     } else {
 449         if ( n == lastNode ) {                  // removing last node ?
 450             lastNode = n->prev;
 451             lastNode->next = 0;
 452         } else {                                // neither last nor first node
 453             n->prev->next = n->next;
 454             n->next->prev = n->prev;
 455         }
 456     }
 457     if ( n->next ) {                            // change current node
 458         curNode = n->next;
 459     } else if ( n->prev ) {
 460         curNode = n->prev;
 461         curIndex--;
 462     }
 463     if ( iterators && iterators->count() ) {    // update iterators
 464         QGListIterator *i = (QGListIterator*)iterators->first();
 465         while ( i ) {                           // fix all iterators that
 466             if ( i->curNode == n )              // refers to pending node
 467                 i->curNode = curNode;
 468             i = (QGListIterator*)iterators->next();
 469         }
 470     }
 471     numNodes--;
 472     return n;
 473 }
 474
 475
 476 /*!
 477   \internal
 478   Removes the node \e n from the list.
 479 */
 480
 481 bool QGList::removeNode( QLNode *n )
 482 {
 483 #if defined(CHECK_NULL)
 484     if ( n == 0 || (n->prev && n->prev->next != n) ||
 485          (n->next && n->next->prev != n) ) {
 486         qWarning( "QGList::removeNode: Corrupted node" );
 487         return FALSE;
 488     }
 489 #endif
 490     curNode = n;
 491     unlink();                                   // unlink node
 492     deleteItem( n->data );                      // deallocate this node
 493     delete n;
 494     curNode  = firstNode;
 495     curIndex = curNode ? 0 : -1;
 496     return TRUE;
 497 }
 498
 499 /*!
 500   \internal
 501   Removes the item \e d from the list.  Uses compareItems() to find the item.
 502 */
 503
 504 bool QGList::remove( QCollection::Item d )
 505 {
 506     if ( d ) {                                  // find the item
 507         if ( find(d) == -1 )
 508             return FALSE;
 509     }
 510     QLNode *n = unlink();                       // unlink node
 511     if ( !n )
 512         return FALSE;
 513     deleteItem( n->data );                      // deallocate this node
 514     delete n;
 515     return TRUE;
 516 }
 517
 518 /*!
 519   \internal
 520   Removes the item \e d from the list.
 521 */
 522
 523 bool QGList::removeRef( QCollection::Item d )
 524 {
 525     if ( d ) {                                  // find the item
 526         if ( findRef(d) == -1 )
 527             return FALSE;
 528     }
 529     QLNode *n = unlink();                       // unlink node
 530     if ( !n )
 531         return FALSE;
 532     deleteItem( n->data );                      // deallocate this node
 533     delete n;
 534     return TRUE;
 535 }
 536
 537 /*!
 538   \fn bool QGList::removeFirst()
 539   \internal
 540   Removes the first item in the list.
 541 */
 542
 543 /*!
 544   \fn bool QGList::removeLast()
 545   \internal
 546   Removes the last item in the list.
 547 */
 548
 549 /*!
 550   \internal
 551   Removes the item at position \e index from the list.
 552 */
 553
 554 bool QGList::removeAt( uint index )
 555 {
 556     if ( !locate(index) )
 557         return FALSE;
 558     QLNode *n = unlink();                       // unlink node
 559     if ( !n )
 560         return FALSE;
 561     deleteItem( n->data );                      // deallocate this node
 562     delete n;
 563     return TRUE;
 564 }
 565
 566
 567 /*!
 568   \internal
 569   Takes the node \e n out of the list.
 570 */
 571
 572 QCollection::Item QGList::takeNode( QLNode *n )
 573 {
 574 #if defined(CHECK_NULL)
 575     if ( n == 0 || (n->prev && n->prev->next != n) ||
 576          (n->next && n->next->prev != n) ) {
 577         qWarning( "QGList::takeNode: Corrupted node" );
 578         return 0;
 579     }
 580 #endif
 581     curNode = n;
 582     unlink();                                   // unlink node
 583     Item d = n->data;
 584     delete n;                                   // delete the node, not data
 585     curNode  = firstNode;
 586     curIndex = curNode ? 0 : -1;
 587     return d;
 588 }
 589
 590 /*!
 591   \internal
 592   Takes the current item out of the list.
 593 */
 594
 595 QCollection::Item QGList::take()
 596 {
 597     QLNode *n = unlink();                       // unlink node
 598     Item d = n ? n->data : 0;
 599     delete n;                                   // delete node, keep contents
 600     return d;
 601 }
 602
 603 /*!
 604   \internal
 605   Takes the item at position \e index out of the list.
 606 */
 607
 608 QCollection::Item QGList::takeAt( uint index )
 609 {
 610     if ( !locate(index) )
 611         return 0;
 612     QLNode *n = unlink();                       // unlink node
 613     Item d = n ? n->data : 0;
 614     delete n;                                   // delete node, keep contents
 615     return d;
 616 }
 617
 618 /*!
 619   \internal
 620   Takes the first item out of the list.
 621 */
 622
 623 QCollection::Item QGList::takeFirst()
 624 {
 625     first();
 626     QLNode *n = unlink();                       // unlink node
 627     Item d = n ? n->data : 0;
 628     delete n;
 629     return d;
 630 }
 631
 632 /*!
 633   \internal
 634   Takes the last item out of the list.
 635 */
 636
 637 QCollection::Item QGList::takeLast()
 638 {
 639     last();
 640     QLNode *n = unlink();                       // unlink node
 641     Item d = n ? n->data : 0;
 642     delete n;
 643     return d;
 644 }
 645
 646
 647 /*!
 648   \internal
 649   Removes all items from the list.
 650 */
 651
 652 void QGList::clear()
 653 {
 654     register QLNode *n = firstNode;
 655
 656     firstNode = lastNode = curNode = 0;         // initialize list
 657     numNodes = 0;
 658     curIndex = -1;
 659
 660     if ( iterators && iterators->count() ) {
 661         QGListIterator *i = (QGListIterator*)iterators->first();
 662         while ( i ) {                           // notify all iterators that
 663             i->curNode = 0;                     // this list is empty
 664             i = (QGListIterator*)iterators->next();
 665         }
 666     }
 667
 668     QLNode *prevNode;
 669     while ( n ) {                               // for all nodes ...
 670         deleteItem( n->data );                  // deallocate data
 671         prevNode = n;
 672         n = n->next;
 673         delete prevNode;                        // deallocate node
 674     }
 675 }
 676
 677
 678 /*!
 679   \internal
 680   Finds an item in the list.
 681 */
 682
 683 int QGList::findRef( QCollection::Item d, bool fromStart )
 684 {
 685     register QLNode *n;
 686     int      index;
 687     if ( fromStart ) {                          // start from first node
 688         n = firstNode;
 689         index = 0;
 690     } else {                                    // start from current node
 691         n = curNode;
 692         index = curIndex;
 693     }
 694     while ( n && n->data != d ) {               // find exact match
 695         n = n->next;
 696         index++;
 697     }
 698     curNode = n;
 699     curIndex = n ? index : -1;
 700     return curIndex;                            // return position of item
 701 }
 702
 703 /*!
 704   \internal
 705   Finds an item in the list.  Uses compareItems().
 706 */
 707
 708 int QGList::find( QCollection::Item d, bool fromStart )
 709 {
 710     register QLNode *n;
 711     int      index;
 712     if ( fromStart ) {                          // start from first node
 713         n = firstNode;
 714         index = 0;
 715     } else {                                    // start from current node
 716         n = curNode;
 717         index = curIndex;
 718     }
 719     while ( n && compareItems(n->data,d) ){     // find equal match
 720         n = n->next;
 721         index++;
 722     }
 723     curNode = n;
 724     curIndex = n ? index : -1;
 725     return curIndex;                            // return position of item
 726 }
 727
 728
 729 /*!
 730   \internal
 731   Counts the number an item occurs in the list.
 732 */
 733
 734 uint QGList::containsRef( QCollection::Item d ) const
 735 {
 736     register QLNode *n = firstNode;
 737     uint     count = 0;
 738     while ( n ) {                               // for all nodes...
 739         if ( n->data == d )                     // count # exact matches
 740             count++;
 741         n = n->next;
 742     }
 743     return count;
 744 }
 745
 746 /*!
 747   \internal
 748   Counts the number an item occurs in the list.  Uses compareItems().
 749 */
 750
 751 uint QGList::contains( QCollection::Item d ) const
 752 {
 753     register QLNode *n = firstNode;
 754     uint     count = 0;
 755     QGList  *that = (QGList*)this;              // mutable for compareItems()
 756     while ( n ) {                               // for all nodes...
 757         if ( !that->compareItems(n->data,d) )   // count # equal matches
 758             count++;
 759         n = n->next;
 760     }
 761     return count;
 762 }
 763
 764
 765 /*!
 766   \fn QCollection::Item QGList::at( uint index )
 767   \internal
 768   Sets the item at position \e index to the current item.
 769 */
 770
 771 /*!
 772   \fn int QGList::at() const
 773   \internal
 774   Returns the current index.
 775 */
 776
 777 /*!
 778   \fn QLNode *QGList::currentNode() const
 779   \internal
 780   Returns the current node.
 781 */
 782
 783 /*!
 784   \fn QCollection::Item QGList::get() const
 785   \internal
 786   Returns the current item.
 787 */
 788
 789 /*!
 790   \fn QCollection::Item QGList::cfirst() const
 791   \internal
 792   Returns the first item in the list.
 793 */
 794
 795 /*!
 796   \fn QCollection::Item QGList::clast() const
 797   \internal
 798   Returns the last item in the list.
 799 */
 800
 801
 802 /*!
 803   \internal
 804   Returns the first list item.  Sets this to current.
 805 */
 806
 807 QCollection::Item QGList::first()
 808 {
 809     if ( firstNode ) {
 810         curIndex = 0;
 811         return (curNode=firstNode)->data;
 812     }
 813     return 0;
 814 }
 815
 816 /*!
 817   \internal
 818   Returns the last list item.  Sets this to current.
 819 */
 820
 821 QCollection::Item QGList::last()
 822 {
 823     if ( lastNode ) {
 824         curIndex = numNodes-1;
 825         return (curNode=lastNode)->data;
 826     }
 827     return 0;
 828 }
 829
 830 /*!
 831   \internal
 832   Returns the next list item (after current).  Sets this to current.
 833 */
 834
 835 QCollection::Item QGList::next()
 836 {
 837     if ( curNode ) {
 838         if ( curNode->next ) {
 839             curIndex++;
 840             curNode = curNode->next;
 841             return curNode->data;
 842         }
 843         curIndex = -1;
 844         curNode = 0;
 845     }
 846     return 0;
 847 }
 848
 849 /*!
 850   \internal
 851   Returns the previous list item (before current).  Sets this to current.
 852 */
 853
 854 QCollection::Item QGList::prev()
 855 {
 856     if ( curNode ) {
 857         if ( curNode->prev ) {
 858             curIndex--;
 859             curNode = curNode->prev;
 860             return curNode->data;
 861         }
 862         curIndex = -1;
 863         curNode = 0;
 864     }
 865     return 0;
 866 }
 867
 868
 869 /*!
 870   \internal
 871   Converts the list to a vector.
 872 */
 873
 874 void QGList::toVector( QGVector *vector ) const
 875 {
 876     vector->clear();
 877     if ( !vector->resize( count() ) )
 878         return;
 879     register QLNode *n = firstNode;
 880     uint i = 0;
 881     while ( n ) {
 882         vector->insert( i, n->data );
 883         n = n->next;
 884         i++;
 885     }
 886 }
 887
 888 void QGList::heapSortPushDown( QCollection::Item* heap, int first, int last )
 889 {
 890     int r = first;
 891     while( r <= last/2 ) {
 892         // Node r has only one child ?
 893         if ( last == 2*r ) {
 894             // Need for swapping ?
 895             if ( compareItems( heap[r], heap[ 2*r ] ) > 0 ) {
 896                 QCollection::Item tmp = heap[r];
 897                 heap[ r ] = heap[ 2*r ];
 898                 heap[ 2*r ] = tmp;
 899             }
 900             // That's it ...
 901             r = last;
 902         } else {
 903             // Node has two children
 904             if ( compareItems( heap[r], heap[ 2*r ] ) > 0 &&
 905                  compareItems( heap[ 2*r ], heap[ 2*r+1 ] ) <= 0 ) {
 906                 // Swap with left child
 907                 QCollection::Item tmp = heap[r];
 908                 heap[ r ] = heap[ 2*r ];
 909                 heap[ 2*r ] = tmp;
 910                 r *= 2;
 911             } else if ( compareItems( heap[r], heap[ 2*r+1 ] ) > 0 &&
 912                         compareItems( heap[ 2*r+1 ], heap[ 2*r ] ) < 0 ) {
 913                 // Swap with right child
 914                 QCollection::Item tmp = heap[r];
 915                 heap[ r ] = heap[ 2*r+1 ];
 916                 heap[ 2*r+1 ] = tmp;
 917                 r = 2*r+1;
 918             } else {
 919                 // We are done
 920                 r = last;
 921             }
 922         }
 923     }
 924 }
 925
 926
 927 /*! Sorts the list by the result of the virtual compareItems() function.
 928
 929   The Heap-Sort algorithm is used for sorting.  It sorts n items with
 930   O(n*log n) compares.  This is the asymptotic optimal solution of the
 931   sorting problem.
 932 */
 933
 934 void QGList::sort()
 935 {
 936     uint n = count();
 937     if ( n < 2 )
 938         return;
 939
 940     // Create the heap
 941     QCollection::Item* realheap = new QCollection::Item[ n ];
 942     // Wow, what a fake. But I want the heap to be indexed as 1...n
 943     QCollection::Item* heap = realheap - 1;
 944     int size = 0;
 945     QLNode* insert = firstNode;
 946     for( ; insert != 0; insert = insert->next ) {
 947         heap[++size] = insert->data;
 948         int i = size;
 949         while( i > 1 && compareItems( heap[i], heap[ i / 2 ] ) < 0 ) {
 950             QCollection::Item tmp = heap[ i ];
 951             heap[ i ] = heap[ i/2 ];
 952             heap[ i/2 ] = tmp;
 953             i /= 2;
 954         }
 955     }
 956
 957     insert = firstNode;
 958     // Now do the sorting
 959     for ( int i = n; i > 0; i-- ) {
 960         insert->data = heap[1];
 961         insert = insert->next;
 962         if ( i > 1 ) {
 963             heap[1] = heap[i];
 964             heapSortPushDown( heap, 1, i - 1 );
 965         }
 966     }
 967
 968     delete [] realheap;
 969 }
 970
 971
 972 /*****************************************************************************
 973   QGList stream functions
 974  *****************************************************************************/
 975
 976 #ifndef QT_NO_DATASTREAM
 977 QDataStream &operator>>( QDataStream &s, QGList &list )
 978 {                                               // read list
 979     return list.read( s );
 980 }
 981
 982 QDataStream &operator<<( QDataStream &s, const QGList &list )
 983 {                                               // write list
 984     return list.write( s );
 985 }
 986
 987 /*!
 988   \internal
 989   Reads a list from the stream \e s.
 990 */
 991
 992 QDataStream &QGList::read( QDataStream &s )
 993 {
 994     uint num;
 995     s >> num;                                   // read number of items
 996     clear();                                    // clear list
 997     while ( num-- ) {                           // read all items
 998         Item d;
 999         read( s, d );
1000         CHECK_PTR( d );
1001         if ( !d )                               // no memory
1002             break;
1003         QLNode *n = new QLNode( d );
1004         CHECK_PTR( n );
1005         if ( !n )                               // no memory
1006             break;
1007         n->next = 0;
1008         if ( (n->prev = lastNode) )             // list is not empty
1009             lastNode->next = n;
1010         else                                    // initialize list
1011             firstNode = n;
1012         lastNode = n;
1013         numNodes++;
1014     }
1015     curNode  = firstNode;
1016     curIndex = curNode ? 0 : -1;
1017     return s;
1018 }
1019
1020 /*!
1021   \internal
1022   Writes the list to the stream \e s.
1023 */
1024
1025 QDataStream &QGList::write( QDataStream &s ) const
1026 {
1027     s << count();                               // write number of items
1028     QLNode *n = firstNode;
1029     while ( n ) {                               // write all items
1030         write( s, n->data );
1031         n = n->next;
1032     }
1033     return s;
1034 }
1035
1036 #endif // QT_NO_DATASTREAM
1037
1038 /*****************************************************************************
1039   QGListIterator member functions
1040  *****************************************************************************/
1041
1042 /*!
1043   \class QGListIterator qglist.h
1044   \brief The QGListIterator class is an internal class for implementing QListIterator.
1045
1046   QGListIterator is a strictly internal class that does the heavy work for
1047   QListIterator.
1048 */
1049
1050 /*!
1051   \internal
1052   Constructs an iterator that operates on the list \e l.
1053 */
1054
1055 QGListIterator::QGListIterator( const QGList &l )
1056 {
1057     list = (QGList *)&l;                        // get reference to list
1058     curNode = list->firstNode;                  // set to first node
1059     if ( !list->iterators ) {
1060         list->iterators = new QGList;           // create iterator list
1061         CHECK_PTR( list->iterators );
1062     }
1063     list->iterators->append( this );            // attach iterator to list
1064 }
1065
1066 /*!
1067   \internal
1068   Constructs a copy of the iterator \e it.
1069 */
1070
1071 QGListIterator::QGListIterator( const QGListIterator &it )
1072 {
1073     list = it.list;
1074     curNode = it.curNode;
1075     if ( list )
1076         list->iterators->append( this );        // attach iterator to list
1077 }
1078
1079 /*!
1080   \internal
1081   Assigns a copy of the iterator \e it and returns a reference to this
1082   iterator.
1083 */
1084
1085 QGListIterator &QGListIterator::operator=( const QGListIterator &it )
1086 {
1087     if ( list )                                 // detach from old list
1088         list->iterators->removeRef( this );
1089     list = it.list;
1090     curNode = it.curNode;
1091     if ( list )
1092         list->iterators->append( this );        // attach to new list
1093     return *this;
1094 }
1095
1096 /*!
1097   \internal
1098   Destroys the iterator.
1099 */
1100
1101 QGListIterator::~QGListIterator()
1102 {
1103     if ( list )                                 // detach iterator from list
1104         list->iterators->removeRef(this);
1105 }
1106
1107
1108 /*!
1109   \fn bool QGListIterator::atFirst() const
1110   \internal
1111   Returns TRUE if the iterator points to the first item, otherwise FALSE.
1112 */
1113
1114 /*!
1115   \fn bool QGListIterator::atLast() const
1116   \internal
1117   Returns TRUE if the iterator points to the last item, otherwise FALSE.
1118 */
1119
1120
1121 /*!
1122   \internal
1123   Sets the list iterator to point to the first item in the list.
1124 */
1125
1126 QCollection::Item QGListIterator::toFirst()
1127 {
1128     if ( !list ) {
1129 #if defined(CHECK_NULL)
1130         qWarning( "QGListIterator::toFirst: List has been deleted" );
1131 #endif
1132         return 0;
1133     }
1134     return list->firstNode ? (curNode = list->firstNode)->getData() : 0;
1135 }
1136
1137 /*!
1138   \internal
1139   Sets the list iterator to point to the last item in the list.
1140 */
1141
1142 QCollection::Item QGListIterator::toLast()
1143 {
1144     if ( !list ) {
1145 #if defined(CHECK_NULL)
1146         qWarning( "QGListIterator::toLast: List has been deleted" );
1147 #endif
1148         return 0;
1149     }
1150     return list->lastNode ? (curNode = list->lastNode)->getData() : 0;
1151 }
1152
1153
1154 /*!
1155   \fn QCollection::Item QGListIterator::get() const
1156   \internal
1157   Returns the iterator item.
1158 */
1159
1160
1161 /*!
1162   \internal
1163   Moves to the next item (postfix).
1164 */
1165
1166 QCollection::Item QGListIterator::operator()()
1167 {
1168     if ( !curNode )
1169         return 0;
1170     QCollection::Item d = curNode->getData();
1171     curNode = curNode->next;
1172     return  d;
1173 }
1174
1175 /*!
1176   \internal
1177   Moves to the next item (prefix).
1178 */
1179
1180 QCollection::Item QGListIterator::operator++()
1181 {
1182     if ( !curNode )
1183         return 0;
1184     curNode = curNode->next;
1185     return curNode ? curNode->getData() : 0;
1186 }
1187
1188 /*!
1189   \internal
1190   Moves \e jumps positions forward.
1191 */
1192
1193 QCollection::Item QGListIterator::operator+=( uint jumps )
1194 {
1195     while ( curNode && jumps-- )
1196         curNode = curNode->next;
1197     return curNode ? curNode->getData() : 0;
1198 }
1199
1200 /*!
1201   \internal
1202   Moves to the previous item (prefix).
1203 */
1204
1205 QCollection::Item QGListIterator::operator--()
1206 {
1207     if ( !curNode )
1208         return 0;
1209     curNode = curNode->prev;
1210     return curNode ? curNode->getData() : 0;
1211 }
1212
1213 /*!
1214   \internal
1215   Moves \e jumps positions backward.
1216 */
1217
1218 QCollection::Item QGListIterator::operator-=( uint jumps )
1219 {
1220     while ( curNode && jumps-- )
1221         curNode = curNode->prev;
1222     return curNode ? curNode->getData() : 0;
1223 }