1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the Qt3Support module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "q3glist.h"

    43 #include "q3gvector.h"

    44 #include "qdatastream.h"

    45 #include "q3valuelist.h"

    46 

    47 QT_BEGIN_NAMESPACE

    48 

    49 /*!

    50   \class Q3LNode

    51   \reentrant

    52   \brief The Q3LNode class is an internal class for the Q3PtrList template collection.

    53 

    54   \internal

    55 

    56   Q3LNode is a doubly-linked list node. It has three pointers:

    57   \list 1

    58   \i Pointer to the previous node.

    59   \i Pointer to the next node.

    60   \i Pointer to the actual data.

    61   \endlist

    62 

    63   It might sometimes be practical to have direct access to the list nodes

    64   in a Q3PtrList, but it is seldom required.

    65 

    66   Be very careful if you want to access the list nodes. The heap can

    67   easily get corrupted if you make a mistake.

    68 

    69   \sa Q3PtrList::currentNode(), Q3PtrList::removeNode(), Q3PtrList::takeNode()

    70 */

    71 

    72 /*!

    73   \fn Q3PtrCollection::Item Q3LNode::getData()

    74   Returns a pointer (\c void*) to the actual data in the list node.

    75 */

    76 

    77 

    78 /*!

    79   \class Q3GList

    80   \reentrant

    81   \brief The Q3GList class is an internal class for implementing Qt collection classes.

    82 

    83   \internal

    84 

    85   Q3GList is a strictly internal class that acts as a base class for

    86   several collection classes; Q3PtrList, Q3PtrQueue and Q3PtrStack.

    87 

    88   Q3GList has some virtual functions that can be reimplemented to

    89   customize the subclasses, namely compareItems(), read() and

    90   write. Normally, you do not have to reimplement any of these

    91   functions.  If you still want to reimplement them, see the QStrList

    92   class (qstrlist.h) for an example.

    93 */

    94 

    95 

    96 /* Internal helper class for Q3GList. Contains some optimization for

    97    the typically case where only one iterators is activre on the list.

    98  */

    99 class Q3GListIteratorList

   100 {

   101 public:

   102     Q3GListIteratorList()

   103 	: list(0), iterator(0) {

   104     }

   105     ~Q3GListIteratorList() {

   106 	notifyClear( true );

   107 	delete list;

   108     }

   109 

   110     void add( Q3GListIterator* i ) {

   111 	if ( !iterator ) {

   112 	    iterator = i;

   113 	} else if ( list ) {

   114 	    list->push_front( i );

   115 	} else {

   116 	    list = new Q3ValueList<Q3GListIterator*>;

   117 	    list->push_front( i );

   118 	}

   119     }

   120 

   121     void remove( Q3GListIterator* i ) {

   122 	if ( iterator == i ) {

   123 	    iterator = 0;

   124 	} else if ( list ) {

   125 	    list->remove( i );

   126 	    if ( list->isEmpty() ) {

   127 		delete list;

   128 		list = 0;

   129 	    }

   130 	}

   131     }

   132 

   133     void notifyClear( bool zeroList ) {

   134 	if ( iterator ) {

   135 	    if ( zeroList )

   136 		iterator->list = 0;

   137 	    iterator->curNode = 0;

   138 	}

   139 	if ( list ) {

   140 	    for ( Q3ValueList<Q3GListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) {

   141 		if ( zeroList )

   142 		    (*i)->list = 0;

   143 		(*i)->curNode = 0;

   144 	    }

   145 	}

   146     }

   147 

   148     void notifyRemove( Q3LNode* n, Q3LNode* curNode ) {

   149 	if ( iterator ) {

   150 	    if ( iterator->curNode == n )

   151 		iterator->curNode = curNode;

   152 	}

   153 	if ( list ) {

   154 	    for ( Q3ValueList<Q3GListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) {

   155 		if ( (*i)->curNode == n )

   156 		    (*i)->curNode = curNode;

   157 	    }

   158 	}

   159     }

   160 

   161 private:

   162     Q3ValueList<Q3GListIterator*>* list;

   163     Q3GListIterator* iterator;

   164 };

   165 

   166 

   167 

   168 /*****************************************************************************

   169   Default implementation of virtual functions

   170  *****************************************************************************/

   171 

   172 /*!

   173   Documented as Q3PtrList::compareItems().

   174 

   175   Compares \a item1 with \a item2.

   176 */

   177 int Q3GList::compareItems( Q3PtrCollection::Item item1, Q3PtrCollection::Item item2 )

   178 {

   179     return item1 != item2;			// compare pointers

   180 }

   181 

   182 #ifndef QT_NO_DATASTREAM

   183 /*!

   184     \overload

   185   Reads a collection/list item from the stream \a s and returns a reference

   186   to the stream.

   187 

   188   The default implementation sets \a item to 0.

   189 

   190   \sa write()

   191 */

   192 

   193 QDataStream &Q3GList::read( QDataStream &s, Q3PtrCollection::Item &item )

   194 {

   195     item = 0;

   196     return s;

   197 }

   198 

   199 /*!

   200     \overload

   201   Writes a collection/list item to the stream \a s and

   202   returns a reference to the stream.

   203 

   204   The default implementation does nothing.

   205 

   206   \sa read()

   207 */

   208 

   209 QDataStream &Q3GList::write( QDataStream &s, Q3PtrCollection::Item ) const

   210 {

   211     return s;

   212 }

   213 #endif // QT_NO_DATASTREAM

   214 

   215 /*****************************************************************************

   216   Q3GList member functions

   217  *****************************************************************************/

   218 

   219 /*!

   220   Constructs an empty list.

   221 */

   222 

   223 Q3GList::Q3GList()

   224 {

   225     firstNode = lastNode = curNode = 0;		// initialize list

   226     numNodes  = 0;

   227     curIndex  = -1;

   228     iterators = 0;				// initialize iterator list

   229 }

   230 

   231 /*!

   232   Constructs a copy of \a list.

   233 */

   234 

   235 Q3GList::Q3GList( const Q3GList & list )

   236     : Q3PtrCollection( list )

   237 {

   238     firstNode = lastNode = curNode = 0;		// initialize list

   239     numNodes  = 0;

   240     curIndex  = -1;

   241     iterators = 0;				// initialize iterator list

   242     Q3LNode *n = list.firstNode;

   243     while ( n ) {				// copy all items from list

   244 	append( n->data );

   245 	n = n->next;

   246     }

   247 }

   248 

   249 /*!

   250   Removes all items from the list and destroys the list.

   251 */

   252 

   253 Q3GList::~Q3GList()

   254 {

   255     clear();

   256     delete iterators;

   257     // Workaround for GCC 2.7.* bug. Compiler constructs 'static' Q3GList

   258     // instances twice on the same address and therefore tries to destruct

   259     // twice on the same address! This is insane but let's try not to crash

   260     // here.

   261     iterators = 0;

   262 }

   263 

   264 

   265 /*!

   266   Assigns \a list to this list.

   267 */

   268 

   269 Q3GList& Q3GList::operator=( const Q3GList &list )

   270 {

   271     if ( &list == this )

   272 	return *this;

   273 

   274     clear();

   275     if ( list.count() > 0 ) {

   276 	Q3LNode *n = list.firstNode;

   277 	while ( n ) {				// copy all items from list

   278 	    append( n->data );

   279 	    n = n->next;

   280 	}

   281 	curNode	 = firstNode;

   282 	curIndex = 0;

   283     }

   284     return *this;

   285 }

   286 

   287 /*!

   288   Compares this list with \a list. Returns true if the lists

   289   contain the same data, otherwise false.

   290 */

   291 

   292 bool Q3GList::operator==( const Q3GList &list ) const

   293 {

   294     if ( count() != list.count() )

   295 	return false;

   296 

   297     if ( count() == 0 )

   298 	return true;

   299 

   300     Q3LNode *n1 = firstNode;

   301     Q3LNode *n2 = list.firstNode;

   302     while ( n1 && n2 ) {

   303 	// should be mutable

   304 	if ( ( (Q3GList*)this )->compareItems( n1->data, n2->data ) != 0 )

   305 	    return false;

   306 	n1 = n1->next;

   307 	n2 = n2->next;

   308     }

   309 

   310     return true;

   311 }

   312 

   313 /*!

   314   \fn uint Q3GList::count() const

   315 

   316   Returns the number of items in the list.

   317 */

   318 

   319 

   320 /*!

   321   Returns the node at position \a index.  Sets this node to current.

   322 */

   323 

   324 Q3LNode *Q3GList::locate( uint index )

   325 {

   326     if ( index == (uint)curIndex )		// current node ?

   327 	return curNode;

   328     if ( !curNode && firstNode ) {		// set current node

   329 	curNode	 = firstNode;

   330 	curIndex = 0;

   331     }

   332     register Q3LNode *node;

   333     int	 distance = index - curIndex;		// node distance to cur node

   334     bool forward;				// direction to traverse

   335 

   336     if ( index >= numNodes )

   337 	return 0;

   338 

   339     if ( distance < 0 )

   340 	distance = -distance;

   341     if ( (uint)distance < index && (uint)distance < numNodes - index ) {

   342 	node =	curNode;			// start from current node

   343 	forward = index > (uint)curIndex;

   344     } else if ( index < numNodes - index ) {	// start from first node

   345 	node = firstNode;

   346 	distance = index;

   347 	forward = true;

   348     } else {					// start from last node

   349 	node = lastNode;

   350 	distance = numNodes - index - 1;

   351 	if ( distance < 0 )

   352 	    distance = 0;

   353 	forward = false;

   354     }

   355     if ( forward ) {				// now run through nodes

   356 	while ( distance-- )

   357 	    node = node->next;

   358     } else {

   359 	while ( distance-- )

   360 	    node = node->prev;

   361     }

   362     curIndex = index;				// must update index

   363     return curNode = node;

   364 }

   365 

   366 

   367 /*!

   368   Inserts item \a d at its sorted position in the list.

   369 */

   370 

   371 void Q3GList::inSort( Q3PtrCollection::Item d )

   372 {

   373     int index = 0;

   374     register Q3LNode *n = firstNode;

   375     while ( n && compareItems(n->data,d) < 0 ){ // find position in list

   376 	n = n->next;

   377 	index++;

   378     }

   379     insertAt( index, d );

   380 }

   381 

   382 

   383 /*!

   384   Inserts item \a d at the start of the list.

   385 */

   386 

   387 void Q3GList::prepend( Q3PtrCollection::Item d )

   388 {

   389     register Q3LNode *n = new Q3LNode( newItem(d) );

   390     Q_CHECK_PTR( n );

   391     n->prev = 0;

   392     if ( (n->next = firstNode) )		// list is not empty

   393 	firstNode->prev = n;

   394     else					// initialize list

   395 	lastNode = n;

   396     firstNode = curNode = n;			// curNode affected

   397     numNodes++;

   398     curIndex = 0;

   399 }

   400 

   401 

   402 /*!

   403   Inserts item \a d at the end of the list.

   404 */

   405 

   406 void Q3GList::append( Q3PtrCollection::Item d )

   407 {

   408     register Q3LNode *n = new Q3LNode( newItem(d) );

   409     Q_CHECK_PTR( n );

   410     n->next = 0;

   411     if ( (n->prev = lastNode) )			// list is not empty

   412 	lastNode->next = n;

   413     else					// initialize list

   414 	firstNode = n;

   415     lastNode = curNode = n;			// curNode affected

   416     curIndex = numNodes;

   417     numNodes++;

   418 }

   419 

   420 

   421 /*!

   422   Inserts item \a d at position \a index in the list.

   423 */

   424 

   425 bool Q3GList::insertAt( uint index, Q3PtrCollection::Item d )

   426 {

   427     if ( index == 0 ) {

   428 	prepend( d );

   429 	return true;

   430     } else if ( index == numNodes ) {

   431 	append( d );

   432 	return true;

   433     }

   434     Q3LNode *nextNode = locate( index );

   435     if ( !nextNode )

   436 	return false;

   437     Q3LNode *prevNode = nextNode->prev;

   438     register Q3LNode *n = new Q3LNode( newItem(d) );

   439     Q_CHECK_PTR( n );

   440     nextNode->prev = n;

   441     prevNode->next = n;

   442     n->prev = prevNode;				// link new node into list

   443     n->next = nextNode;

   444     curNode = n;				// curIndex set by locate()

   445     numNodes++;

   446     return true;

   447 }

   448 

   449 

   450 /*!

   451   Relinks node \a n and makes it the first node in the list.

   452 */

   453 

   454 void Q3GList::relinkNode( Q3LNode *n )

   455 {

   456     if ( n == firstNode )			// already first

   457 	return;

   458     curNode = n;

   459     unlink();

   460     n->prev = 0;

   461     if ( (n->next = firstNode) )		// list is not empty

   462 	firstNode->prev = n;

   463     else					// initialize list

   464 	lastNode = n;

   465     firstNode = curNode = n;			// curNode affected

   466     numNodes++;

   467     curIndex = 0;

   468 }

   469 

   470 

   471 /*!

   472   Unlinks the current list node and returns a pointer to this node.

   473 */

   474 

   475 Q3LNode *Q3GList::unlink()

   476 {

   477     if ( curNode == 0 )				// null current node

   478 	return 0;

   479     register Q3LNode *n = curNode;		// unlink this node

   480     if ( n == firstNode ) {			// removing first node ?

   481 	if ( (firstNode = n->next) ) {

   482 	    firstNode->prev = 0;

   483 	} else {

   484 	    lastNode = curNode = 0;		// list becomes empty

   485 	    curIndex = -1;

   486 	}

   487     } else {

   488 	if ( n == lastNode ) {			// removing last node ?

   489 	    lastNode = n->prev;

   490 	    lastNode->next = 0;

   491 	} else {				// neither last nor first node

   492 	    n->prev->next = n->next;

   493 	    n->next->prev = n->prev;

   494 	}

   495     }

   496 

   497     if ( n->next ) {                            // change current node

   498         curNode = n->next;

   499     } else if ( n->prev ) {

   500         curNode = n->prev;

   501         curIndex--;

   502     }

   503 

   504     if ( iterators )

   505 	iterators->notifyRemove( n, curNode );

   506     numNodes--;

   507     return n;

   508 }

   509 

   510 

   511 /*!

   512   Removes the node \a n from the list.

   513 */

   514 

   515 bool Q3GList::removeNode( Q3LNode *n )

   516 {

   517 #if defined(QT_CHECK_NULL)

   518     if ( n == 0 || (n->prev && n->prev->next != n) ||

   519 	 (n->next && n->next->prev != n) ) {

   520 	qWarning( "Q3GList::removeNode: Corrupted node" );

   521 	return false;

   522     }

   523 #endif

   524     curNode = n;

   525     unlink();					// unlink node

   526     deleteItem( n->data );			// deallocate this node

   527     delete n;

   528     curNode  = firstNode;

   529     curIndex = curNode ? 0 : -1;

   530     return true;

   531 }

   532 

   533 /*!

   534   Removes the item \a d from the list.	Uses compareItems() to find the item.

   535 

   536   If \a d is 0, removes the current item.

   537 */

   538 

   539 bool Q3GList::remove( Q3PtrCollection::Item d )

   540 {

   541     if ( d && find(d) == -1 )

   542 	return false;

   543     Q3LNode *n = unlink();

   544     if ( !n )

   545 	return false;

   546     deleteItem( n->data );

   547     delete n;

   548     return true;

   549 }

   550 

   551 /*!

   552   Removes the item \a d from the list.

   553 */

   554 

   555 bool Q3GList::removeRef( Q3PtrCollection::Item d )

   556 {

   557     if ( findRef(d) == -1 )

   558 	return false;

   559     Q3LNode *n = unlink();

   560     if ( !n )

   561 	return false;

   562     deleteItem( n->data );

   563     delete n;

   564     return true;

   565 }

   566 

   567 /*!

   568   \fn bool Q3GList::removeFirst()

   569 

   570   Removes the first item in the list.

   571 */

   572 

   573 /*!

   574   \fn bool Q3GList::removeLast()

   575 

   576   Removes the last item in the list.

   577 */

   578 

   579 /*!

   580   Removes the item at position \a index from the list.

   581 */

   582 

   583 bool Q3GList::removeAt( uint index )

   584 {

   585     if ( !locate(index) )

   586 	return false;

   587     Q3LNode *n = unlink();

   588     if ( !n )

   589 	return false;

   590     deleteItem( n->data );

   591     delete n;

   592     return true;

   593 }

   594 

   595 

   596 /*!

   597   Replaces the item at index \a index with \a d.

   598 */

   599 bool Q3GList::replaceAt( uint index, Q3PtrCollection::Item d )

   600 {

   601     Q3LNode *n = locate( index );

   602     if ( !n )

   603 	return false;

   604     if ( n->data != d ) {

   605 	deleteItem( n->data );

   606 	n->data = newItem( d );

   607     }

   608     return true;

   609 }

   610 

   611 

   612 

   613 /*!

   614   Takes the node \a n out of the list.

   615 */

   616 

   617 Q3PtrCollection::Item Q3GList::takeNode( Q3LNode *n )

   618 {

   619 #if defined(QT_CHECK_NULL)

   620     if ( n == 0 || (n->prev && n->prev->next != n) ||

   621 	 (n->next && n->next->prev != n) ) {

   622 	qWarning( "Q3GList::takeNode: Corrupted node" );

   623 	return 0;

   624     }

   625 #endif

   626     curNode = n;

   627     unlink();					// unlink node

   628     Item d = n->data;

   629     delete n;					// delete the node, not data

   630     curNode  = firstNode;

   631     curIndex = curNode ? 0 : -1;

   632     return d;

   633 }

   634 

   635 /*!

   636   Takes the current item out of the list.

   637 */

   638 

   639 Q3PtrCollection::Item Q3GList::take()

   640 {

   641     Q3LNode *n = unlink();			// unlink node

   642     Item d = n ? n->data : 0;

   643     delete n;					// delete node, keep contents

   644     return d;

   645 }

   646 

   647 /*!

   648   Takes the item at position \a index out of the list.

   649 */

   650 

   651 Q3PtrCollection::Item Q3GList::takeAt( uint index )

   652 {

   653     if ( !locate(index) )

   654 	return 0;

   655     Q3LNode *n = unlink();			// unlink node

   656     Item d = n ? n->data : 0;

   657     delete n;					// delete node, keep contents

   658     return d;

   659 }

   660 

   661 /*!

   662   Takes the first item out of the list.

   663 */

   664 

   665 Q3PtrCollection::Item Q3GList::takeFirst()

   666 {

   667     first();

   668     Q3LNode *n = unlink();			// unlink node

   669     Item d = n ? n->data : 0;

   670     delete n;

   671     return d;

   672 }

   673 

   674 /*!

   675   Takes the last item out of the list.

   676 */

   677 

   678 Q3PtrCollection::Item Q3GList::takeLast()

   679 {

   680     last();

   681     Q3LNode *n = unlink();			// unlink node

   682     Item d = n ? n->data : 0;

   683     delete n;

   684     return d;

   685 }

   686 

   687 

   688 /*!

   689   Removes all items from the list.

   690 */

   691 

   692 void Q3GList::clear()

   693 {

   694     register Q3LNode *n = firstNode;

   695 

   696     firstNode = lastNode = curNode = 0;		// initialize list

   697     numNodes = 0;

   698     curIndex = -1;

   699 

   700     if ( iterators )

   701 	iterators->notifyClear( false );

   702 

   703     Q3LNode *prevNode;

   704     while ( n ) {				// for all nodes ...

   705 	deleteItem( n->data );			// deallocate data

   706 	prevNode = n;

   707 	n = n->next;

   708 	delete prevNode;			// deallocate node

   709     }

   710 }

   711 

   712 

   713 /*!

   714   Finds item \a d in the list. If \a fromStart is true the search

   715   begins at the first node; otherwise it begins at the current node.

   716 */

   717 

   718 int Q3GList::findRef( Q3PtrCollection::Item d, bool fromStart )

   719 {

   720     register Q3LNode *n;

   721     int	     index;

   722     if ( fromStart ) {				// start from first node

   723 	n = firstNode;

   724 	index = 0;

   725     } else {					// start from current node

   726 	n = curNode;

   727 	index = curIndex;

   728     }

   729     while ( n && n->data != d ) {		// find exact match

   730 	n = n->next;

   731 	index++;

   732     }

   733     curNode = n;

   734     curIndex = n ? index : -1;

   735     return curIndex;				// return position of item

   736 }

   737 

   738 /*!

   739   Finds item \a d in the list using compareItems(). If \a fromStart is

   740   true the search begins at the first node; otherwise it begins at the

   741   current node.

   742 */

   743 

   744 int Q3GList::find( Q3PtrCollection::Item d, bool fromStart )

   745 {

   746     register Q3LNode *n;

   747     int	     index;

   748     if ( fromStart ) {				// start from first node

   749 	n = firstNode;

   750 	index = 0;

   751     } else {					// start from current node

   752 	n = curNode;

   753 	index = curIndex;

   754     }

   755     while ( n && compareItems(n->data,d) ){	// find equal match

   756 	n = n->next;

   757 	index++;

   758     }

   759     curNode = n;

   760     curIndex = n ? index : -1;

   761     return curIndex;				// return position of item

   762 }

   763 

   764 

   765 /*!

   766   Counts the number item \a d occurs in the list.

   767 */

   768 

   769 uint Q3GList::containsRef( Q3PtrCollection::Item d ) const

   770 {

   771     register Q3LNode *n = firstNode;

   772     uint     count = 0;

   773     while ( n ) {				// for all nodes...

   774 	if ( n->data == d )			// count # exact matches

   775 	    count++;

   776 	n = n->next;

   777     }

   778     return count;

   779 }

   780 

   781 /*!

   782   Counts the number of times item \a d occurs in the list. Uses

   783   compareItems().

   784 */

   785 

   786 uint Q3GList::contains( Q3PtrCollection::Item d ) const

   787 {

   788     register Q3LNode *n = firstNode;

   789     uint     count = 0;

   790     Q3GList  *that = (Q3GList*)this;		// mutable for compareItems()

   791     while ( n ) {				// for all nodes...

   792 	if ( !that->compareItems(n->data,d) )	// count # equal matches

   793 	    count++;

   794 	n = n->next;

   795     }

   796     return count;

   797 }

   798 

   799 

   800 /*!

   801   \fn Q3PtrCollection::Item Q3GList::at( uint index )

   802   \overload

   803 

   804   Sets the item at position \a index to the current item.

   805 */

   806 

   807 /*!

   808   \fn int Q3GList::at() const

   809 

   810   Returns the current index.

   811 */

   812 

   813 /*!

   814   \fn Q3LNode *Q3GList::currentNode() const

   815 

   816   Returns the current node.

   817 */

   818 

   819 /*!

   820   \fn Q3PtrCollection::Item Q3GList::get() const

   821 

   822   Returns the current item.

   823 */

   824 

   825 /*!

   826   \fn Q3PtrCollection::Item Q3GList::cfirst() const

   827 

   828   Returns the first item in the list.

   829 */

   830 

   831 /*!

   832   \fn Q3PtrCollection::Item Q3GList::clast() const

   833 

   834   Returns the last item in the list.

   835 */

   836 

   837 

   838 /*!

   839   Returns the first list item.	Sets this to current.

   840 */

   841 

   842 Q3PtrCollection::Item Q3GList::first()

   843 {

   844     if ( firstNode ) {

   845 	curIndex = 0;

   846 	return (curNode=firstNode)->data;

   847     }

   848     return 0;

   849 }

   850 

   851 /*!

   852   Returns the last list item.  Sets this to current.

   853 */

   854 

   855 Q3PtrCollection::Item Q3GList::last()

   856 {

   857     if ( lastNode ) {

   858 	curIndex = numNodes-1;

   859 	return (curNode=lastNode)->data;

   860     }

   861     return 0;

   862 }

   863 

   864 /*!

   865   Returns the next list item (after current).  Sets this to current.

   866 */

   867 

   868 Q3PtrCollection::Item Q3GList::next()

   869 {

   870     if ( curNode ) {

   871 	if ( curNode->next ) {

   872 	    curIndex++;

   873 	    curNode = curNode->next;

   874 	    return curNode->data;

   875 	}

   876 	curIndex = -1;

   877 	curNode = 0;

   878     }

   879     return 0;

   880 }

   881 

   882 /*!

   883   Returns the previous list item (before current).  Sets this to current.

   884 */

   885 

   886 Q3PtrCollection::Item Q3GList::prev()

   887 {

   888     if ( curNode ) {

   889 	if ( curNode->prev ) {

   890 	    curIndex--;

   891 	    curNode = curNode->prev;

   892 	    return curNode->data;

   893 	}

   894 	curIndex = -1;

   895 	curNode = 0;

   896     }

   897     return 0;

   898 }

   899 

   900 

   901 /*!

   902   Converts the list to a vector, \a vector.

   903 */

   904 

   905 void Q3GList::toVector( Q3GVector *vector ) const

   906 {

   907     vector->clear();

   908     if ( !vector->resize( count() ) )

   909 	return;

   910     register Q3LNode *n = firstNode;

   911     uint i = 0;

   912     while ( n ) {

   913 	vector->insert( i, n->data );

   914 	n = n->next;

   915 	i++;

   916     }

   917 }

   918 

   919 void Q3GList::heapSortPushDown( Q3PtrCollection::Item* heap, int first, int last )

   920 {

   921     int r = first;

   922     while( r <= last/2 ) {

   923 	// Node r has only one child ?

   924 	if ( last == 2*r ) {

   925 	    // Need for swapping ?

   926 	    if ( compareItems( heap[r], heap[ 2*r ] ) > 0 ) {

   927 		Q3PtrCollection::Item tmp = heap[r];

   928 		heap[ r ] = heap[ 2*r ];

   929 		heap[ 2*r ] = tmp;

   930 	    }

   931 	    // That's it ...

   932 	    r = last;

   933 	} else {

   934 	    // Node has two children

   935 	    if ( compareItems( heap[r], heap[ 2*r ] ) > 0 &&

   936 		 compareItems( heap[ 2*r ], heap[ 2*r+1 ] ) <= 0 ) {

   937 		// Swap with left child

   938 		Q3PtrCollection::Item tmp = heap[r];

   939 		heap[ r ] = heap[ 2*r ];

   940 		heap[ 2*r ] = tmp;

   941 		r *= 2;

   942 	    } else if ( compareItems( heap[r], heap[ 2*r+1 ] ) > 0 &&

   943 			compareItems( heap[ 2*r+1 ], heap[ 2*r ] ) < 0 ) {

   944 		// Swap with right child

   945 		Q3PtrCollection::Item tmp = heap[r];

   946 		heap[ r ] = heap[ 2*r+1 ];

   947 		heap[ 2*r+1 ] = tmp;

   948 		r = 2*r+1;

   949 	    } else {

   950 		// We are done

   951 		r = last;

   952 	    }

   953 	}

   954     }

   955 }

   956 

   957 

   958 /*! Sorts the list by the result of the virtual compareItems() function.

   959 

   960   The Heap-Sort algorithm is used for sorting.  It sorts n items with

   961   O(n*log n) compares.  This is the asymptotic optimal solution of the

   962   sorting problem.

   963 */

   964 

   965 void Q3GList::sort()

   966 {

   967     uint n = count();

   968     if ( n < 2 )

   969 	return;

   970 

   971     // Create the heap

   972     Q3PtrCollection::Item* realheap = new Q3PtrCollection::Item[ n ];

   973     // Wow, what a fake. But I want the heap to be indexed as 1...n

   974     Q3PtrCollection::Item* heap = realheap - 1;

   975     int size = 0;

   976     Q3LNode* insert = firstNode;

   977     for( ; insert != 0; insert = insert->next ) {

   978 	heap[++size] = insert->data;

   979 	int i = size;

   980 	while( i > 1 && compareItems( heap[i], heap[ i / 2 ] ) < 0 ) {

   981 	    Q3PtrCollection::Item tmp = heap[ i ];

   982 	    heap[ i ] = heap[ i/2 ];

   983 	    heap[ i/2 ] = tmp;

   984 	    i /= 2;

   985 	}

   986     }

   987 

   988     insert = firstNode;

   989     // Now do the sorting

   990     for ( int i = n; i > 0; i-- ) {

   991 	insert->data = heap[1];

   992 	insert = insert->next;

   993 	if ( i > 1 ) {

   994 	    heap[1] = heap[i];

   995 	    heapSortPushDown( heap, 1, i - 1 );

   996 	}

   997     }

   998 

   999     delete [] realheap;

  1000 }

  1001 

  1002 

  1003 /*****************************************************************************

  1004   Q3GList stream functions

  1005  *****************************************************************************/

  1006 

  1007 #ifndef QT_NO_DATASTREAM

  1008 QDataStream &operator>>( QDataStream &s, Q3GList &list )

  1009 {						// read list

  1010     return list.read( s );

  1011 }

  1012 

  1013 QDataStream &operator<<( QDataStream &s, const Q3GList &list )

  1014 {						// write list

  1015     return list.write( s );

  1016 }

  1017 

  1018 /*!

  1019   Reads a list from the stream \a s.

  1020 */

  1021 

  1022 QDataStream &Q3GList::read( QDataStream &s )

  1023 {

  1024     uint num;

  1025     s >> num;					// read number of items

  1026     clear();					// clear list

  1027     while ( num-- ) {				// read all items

  1028 	Item d;

  1029 	read( s, d );

  1030 	Q_CHECK_PTR( d );

  1031 	if ( !d )				// no memory

  1032 	    break;

  1033 	Q3LNode *n = new Q3LNode( d );

  1034 	Q_CHECK_PTR( n );

  1035 	if ( !n )				// no memory

  1036 	    break;

  1037 	n->next = 0;

  1038 	if ( (n->prev = lastNode) )		// list is not empty

  1039 	    lastNode->next = n;

  1040 	else					// initialize list

  1041 	    firstNode = n;

  1042 	lastNode = n;

  1043 	numNodes++;

  1044     }

  1045     curNode  = firstNode;

  1046     curIndex = curNode ? 0 : -1;

  1047     return s;

  1048 }

  1049 

  1050 /*!

  1051   Writes the list to the stream \a s.

  1052 */

  1053 

  1054 QDataStream &Q3GList::write( QDataStream &s ) const

  1055 {

  1056     s << count();				// write number of items

  1057     Q3LNode *n = firstNode;

  1058     while ( n ) {				// write all items

  1059 	write( s, n->data );

  1060 	n = n->next;

  1061     }

  1062     return s;

  1063 }

  1064 

  1065 #endif // QT_NO_DATASTREAM

  1066 

  1067 

  1068 

  1069 /*! \internal

  1070  */

  1071 Q3LNode* Q3GList::erase( Q3LNode* it )

  1072 {

  1073     Q3LNode* n = it;

  1074     it = it->next;

  1075     removeNode( n );

  1076     return it;

  1077 }

  1078 

  1079 

  1080 /*****************************************************************************

  1081   Q3GListIterator member functions

  1082  *****************************************************************************/

  1083 

  1084 /*!

  1085   \class Q3GListIterator

  1086   \reentrant

  1087   \brief The Q3GListIterator class is an internal class for implementing Q3PtrListIterator.

  1088 

  1089   \internal

  1090 

  1091   Q3GListIterator is a strictly internal class that does the heavy work for

  1092   Q3PtrListIterator.

  1093 */

  1094 

  1095 /*!

  1096   \internal

  1097   Constructs an iterator that operates on the list \a l.

  1098 */

  1099 

  1100 Q3GListIterator::Q3GListIterator( const Q3GList &l )

  1101 {

  1102     list = (Q3GList *)&l;			// get reference to list

  1103     curNode = list->firstNode;			// set to first node

  1104     if ( !list->iterators ) {

  1105 	list->iterators = new Q3GListIteratorList;		// create iterator list

  1106 	Q_CHECK_PTR( list->iterators );

  1107     }

  1108     list->iterators->add( this );		// attach iterator to list

  1109 }

  1110 

  1111 /*!

  1112   \internal

  1113   Constructs a copy of the iterator \a it.

  1114 */

  1115 

  1116 Q3GListIterator::Q3GListIterator( const Q3GListIterator &it )

  1117 {

  1118     list = it.list;

  1119     curNode = it.curNode;

  1120     if ( list )

  1121 	list->iterators->add( this );	// attach iterator to list

  1122 }

  1123 

  1124 /*!

  1125   \internal

  1126   Assigns a copy of the iterator \a it and returns a reference to this

  1127   iterator.

  1128 */

  1129 

  1130 Q3GListIterator &Q3GListIterator::operator=( const Q3GListIterator &it )

  1131 {

  1132     if ( list )					// detach from old list

  1133 	list->iterators->remove( this );

  1134     list = it.list;