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 }