Blame qtools/qglist.cpp

Packit 1c1d7e
/****************************************************************************
Packit 1c1d7e
** 
Packit 1c1d7e
**
Packit 1c1d7e
** Implementation of QGList and QGListIterator classes
Packit 1c1d7e
**
Packit 1c1d7e
** Created : 920624
Packit 1c1d7e
**
Packit 1c1d7e
** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
Packit 1c1d7e
**
Packit 1c1d7e
** This file is part of the tools module of the Qt GUI Toolkit.
Packit 1c1d7e
**
Packit 1c1d7e
** This file may be distributed under the terms of the Q Public License
Packit 1c1d7e
** as defined by Trolltech AS of Norway and appearing in the file
Packit 1c1d7e
** LICENSE.QPL included in the packaging of this file.
Packit 1c1d7e
**
Packit 1c1d7e
** This file may be distributed and/or modified under the terms of the
Packit 1c1d7e
** GNU General Public License version 2 as published by the Free Software
Packit 1c1d7e
** Foundation and appearing in the file LICENSE.GPL included in the
Packit 1c1d7e
** packaging of this file.
Packit 1c1d7e
**
Packit 1c1d7e
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
Packit 1c1d7e
** licenses may use this file in accordance with the Qt Commercial License
Packit 1c1d7e
** Agreement provided with the Software.
Packit 1c1d7e
**
Packit 1c1d7e
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
Packit 1c1d7e
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
Packit 1c1d7e
**
Packit 1c1d7e
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
Packit 1c1d7e
**   information about Qt Commercial License Agreements.
Packit 1c1d7e
** See http://www.trolltech.com/qpl/ for QPL licensing information.
Packit 1c1d7e
** See http://www.trolltech.com/gpl/ for GPL licensing information.
Packit 1c1d7e
**
Packit 1c1d7e
** Contact info@trolltech.com if any conditions of this licensing are
Packit 1c1d7e
** not clear to you.
Packit 1c1d7e
**
Packit 1c1d7e
**********************************************************************/
Packit 1c1d7e
Packit 1c1d7e
#include "qglist.h"
Packit 1c1d7e
#include "qgvector.h"
Packit 1c1d7e
#include "qdatastream.h"
Packit 1c1d7e
Packit 1c1d7e
Packit 1c1d7e
// NOT REVISED
Packit 1c1d7e
/*!
Packit 1c1d7e
  \class QLNode qglist.h
Packit 1c1d7e
  \brief The QLNode class is an internal class for the QList template collection.
Packit 1c1d7e
Packit 1c1d7e
  QLNode is a doubly linked list node; it has three pointers:
Packit 1c1d7e
  
    Packit 1c1d7e
      
  1. Pointer to the previous node.
  2. Packit 1c1d7e
      
  3. Pointer to the next node.
  4. Packit 1c1d7e
      
  5. Pointer to the actual data.
  6. Packit 1c1d7e
      
    Packit 1c1d7e
    Packit 1c1d7e
      Sometimes it might be practical to have direct access to the list nodes
    Packit 1c1d7e
      in a QList, but it is seldom required.
    Packit 1c1d7e
    Packit 1c1d7e
      \warning Be very careful if you want to access the list nodes. The heap
    Packit 1c1d7e
      can easily get corrupted if you make a mistake.
    Packit 1c1d7e
    Packit 1c1d7e
      \sa QList::currentNode(), QList::removeNode(), QList::takeNode()
    Packit 1c1d7e
    */
    Packit 1c1d7e
    Packit 1c1d7e
    /*!
    Packit 1c1d7e
      \fn QCollection::Item QLNode::getData()
    Packit 1c1d7e
      Returns a pointer (\c void*) to the actual data in the list node.
    Packit 1c1d7e
    */
    Packit 1c1d7e
    Packit 1c1d7e
    Packit 1c1d7e
    /*!
    Packit 1c1d7e
      \class QGList qglist.h
    Packit 1c1d7e
      \brief The QGList class is an internal class for implementing Qt collection classes.
    Packit 1c1d7e
    Packit 1c1d7e
      QGList is a strictly internal class that acts as a base class for several
    Packit 1c1d7e
      \link collection.html collection classes\endlink; QList, QQueue and
    Packit 1c1d7e
      QStack.
    Packit 1c1d7e
    Packit 1c1d7e
      QGList has some virtual functions that can be reimplemented to customize
    Packit 1c1d7e
      the subclasses.
    Packit 1c1d7e
      
      Packit 1c1d7e
        
    • compareItems() compares two collection/list items.
    • Packit 1c1d7e
        
    • read() reads a collection/list item from a QDataStream.
    • Packit 1c1d7e
        
    • write() writes a collection/list item to a QDataStream.
    • Packit 1c1d7e
        
      Packit 1c1d7e
        Normally, you do not have to reimplement any of these functions.
      Packit 1c1d7e
        If you still want to reimplement them, see the QStrList class (qstrlist.h),
      Packit 1c1d7e
        which is a good example.
      Packit 1c1d7e
      */
      Packit 1c1d7e
      Packit 1c1d7e
      Packit 1c1d7e
      /*****************************************************************************
      Packit 1c1d7e
        Default implementation of virtual functions
      Packit 1c1d7e
       *****************************************************************************/
      Packit 1c1d7e
      Packit 1c1d7e
      /*!
      Packit 1c1d7e
        This virtual function compares two list items.
      Packit 1c1d7e
      Packit 1c1d7e
        Returns:
      Packit 1c1d7e
        
        Packit 1c1d7e
          
      • 0 if \e item1 == \e item2
      • Packit 1c1d7e
          
      • non-zero if \e item1 != \e item2
      • Packit 1c1d7e
          
        Packit 1c1d7e
        Packit 1c1d7e
          This function returns \e int rather than \e bool so that
        Packit 1c1d7e
          reimplementations can return three values and use it to sort by:
        Packit 1c1d7e
        Packit 1c1d7e
          
          Packit 1c1d7e
            
        • 0 if \e item1 == \e item2
        • Packit 1c1d7e
            
        • \> 0 (positive integer) if \e item1 \> \e item2
        • Packit 1c1d7e
            
        • \< 0 (negative integer) if \e item1 \< \e item2
        • Packit 1c1d7e
            
          Packit 1c1d7e
          Packit 1c1d7e
            The QList::inSort() function requires that compareItems() is implemented
          Packit 1c1d7e
            as described here.
          Packit 1c1d7e
          Packit 1c1d7e
            This function should not modify the list because some const functions
          Packit 1c1d7e
            call compareItems().
          Packit 1c1d7e
          Packit 1c1d7e
            The default implementation compares the pointers:
          Packit 1c1d7e
            \code
          Packit 1c1d7e
          Packit 1c1d7e
            \endcode
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          int QGList::compareItems( QCollection::Item item1, QCollection::Item item2 )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              return item1 != item2;			// compare pointers
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          #ifndef QT_NO_DATASTREAM
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            Reads a collection/list item from the stream \a s and returns a reference
          Packit 1c1d7e
            to the stream.
          Packit 1c1d7e
          Packit 1c1d7e
            The default implementation sets \a item to 0.
          Packit 1c1d7e
          Packit 1c1d7e
            \sa write()
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QDataStream &QGList::read( QDataStream &s, QCollection::Item &item )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              item = 0;
          Packit 1c1d7e
              return s;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            Writes a collection/list item to the stream \a s and returns a reference
          Packit 1c1d7e
            to the stream.
          Packit 1c1d7e
          Packit 1c1d7e
            The default implementation does nothing.
          Packit 1c1d7e
          Packit 1c1d7e
            \sa read()
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QDataStream &QGList::write( QDataStream &s, QCollection::Item ) const
          Packit 1c1d7e
          {
          Packit 1c1d7e
              return s;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          #endif // QT_NO_DATASTREAM
          Packit 1c1d7e
          Packit 1c1d7e
          /*****************************************************************************
          Packit 1c1d7e
            QGList member functions
          Packit 1c1d7e
           *****************************************************************************/
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Constructs an empty list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGList::QGList()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              firstNode = lastNode = curNode = 0;		// initialize list
          Packit 1c1d7e
              numNodes  = 0;
          Packit 1c1d7e
              curIndex  = -1;
          Packit 1c1d7e
              iterators = 0;				// initialize iterator list
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Constructs a copy of \e list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGList::QGList( const QGList & list )
          Packit 1c1d7e
              : QCollection( list )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              firstNode = lastNode = curNode = 0;		// initialize list
          Packit 1c1d7e
              numNodes  = 0;
          Packit 1c1d7e
              curIndex  = -1;
          Packit 1c1d7e
              iterators = 0;				// initialize iterator list
          Packit 1c1d7e
              QLNode *n = list.firstNode;
          Packit 1c1d7e
              while ( n ) {				// copy all items from list
          Packit 1c1d7e
          	append( n->data );
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
              }
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes all items from the list and destroys the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGList::~QGList()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              clear();
          Packit 1c1d7e
              if ( !iterators )				// no iterators for this list
          Packit 1c1d7e
          	return;
          Packit 1c1d7e
              QGListIterator *i = (QGListIterator*)iterators->first();
          Packit 1c1d7e
              while ( i ) {				// notify all iterators that
          Packit 1c1d7e
          	i->list = 0;				// this list is deleted
          Packit 1c1d7e
          	i->curNode = 0;
          Packit 1c1d7e
          	i = (QGListIterator*)iterators->next();
          Packit 1c1d7e
              }
          Packit 1c1d7e
              delete iterators;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Assigns \e list to this list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGList& QGList::operator=( const QGList &list )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              clear();
          Packit 1c1d7e
              if ( list.count() > 0 ) {
          Packit 1c1d7e
          	QLNode *n = list.firstNode;
          Packit 1c1d7e
          	while ( n ) {				// copy all items from list
          Packit 1c1d7e
          	    append( n->data );
          Packit 1c1d7e
          	    n = n->next;
          Packit 1c1d7e
          	}
          Packit 1c1d7e
          	curNode	 = firstNode;
          Packit 1c1d7e
          	curIndex = 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return *this;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            Compares this list with \a list. Retruns TRUE if the lists
          Packit 1c1d7e
            contain the same data, else FALSE.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          bool QGList::operator==( const QGList &list ) const
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( count() != list.count() )
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              
          Packit 1c1d7e
              if ( count() == 0 )
          Packit 1c1d7e
          	return TRUE;
          Packit 1c1d7e
              
          Packit 1c1d7e
              QLNode *n1 = firstNode;
          Packit 1c1d7e
              QLNode *n2 = list.firstNode;
          Packit 1c1d7e
              while ( n1 && n2 ) {
          Packit 1c1d7e
          	// should be mutable
          Packit 1c1d7e
          	if ( ( (QGList*)this )->compareItems( n1->data, n2->data ) != 0 )
          Packit 1c1d7e
          	    return FALSE;
          Packit 1c1d7e
          	n1 = n1->next;
          Packit 1c1d7e
          	n2 = n2->next;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              
          Packit 1c1d7e
              return TRUE;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn uint QGList::count() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the number of items in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the node at position \e index.  Sets this node to current.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QLNode *QGList::locate( uint index )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( index == (uint)curIndex )		// current node ?
          Packit 1c1d7e
          	return curNode;
          Packit 1c1d7e
              if ( !curNode && firstNode ) {		// set current node
          Packit 1c1d7e
          	curNode	 = firstNode;
          Packit 1c1d7e
          	curIndex = 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              register QLNode *node;
          Packit 1c1d7e
              int	 distance = index - curIndex;		// node distance to cur node
          Packit 1c1d7e
              bool forward;				// direction to traverse
          Packit 1c1d7e
          Packit 1c1d7e
              if ( index >= numNodes ) {
          Packit 1c1d7e
          #if defined(CHECK_RANGE)
          Packit 1c1d7e
          	qWarning( "QGList::locate: Index %d out of range", index );
          Packit 1c1d7e
          #endif
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
          Packit 1c1d7e
              if ( distance < 0 )
          Packit 1c1d7e
          	distance = -distance;
          Packit 1c1d7e
              if ( (uint)distance < index && (uint)distance < numNodes - index ) {
          Packit 1c1d7e
          	node =	curNode;			// start from current node
          Packit 1c1d7e
          	forward = index > (uint)curIndex;
          Packit 1c1d7e
              } else if ( index < numNodes - index ) {	// start from first node
          Packit 1c1d7e
          	node = firstNode;
          Packit 1c1d7e
          	distance = index;
          Packit 1c1d7e
          	forward = TRUE;
          Packit 1c1d7e
              } else {					// start from last node
          Packit 1c1d7e
          	node = lastNode;
          Packit 1c1d7e
          	distance = numNodes - index - 1;
          Packit 1c1d7e
          	if ( distance < 0 )
          Packit 1c1d7e
          	    distance = 0;
          Packit 1c1d7e
          	forward = FALSE;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              if ( forward ) {				// now run through nodes
          Packit 1c1d7e
          	while ( distance-- )
          Packit 1c1d7e
          	    node = node->next;
          Packit 1c1d7e
              } else {
          Packit 1c1d7e
          	while ( distance-- )
          Packit 1c1d7e
          	    node = node->prev;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              curIndex = index;				// must update index
          Packit 1c1d7e
              return curNode = node;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Inserts an item at its sorted position in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::inSort( QCollection::Item d )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              int index = 0;
          Packit 1c1d7e
              register QLNode *n = firstNode;
          Packit 1c1d7e
              while ( n && compareItems(n->data,d) < 0 ){ // find position in list
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
          	index++;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              insertAt( index, d );
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Inserts an item at the start of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::prepend( QCollection::Item d )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n = new QLNode( newItem(d) );
          Packit 1c1d7e
              CHECK_PTR( n );
          Packit 1c1d7e
              n->prev = 0;
          Packit 1c1d7e
              if ( (n->next = firstNode) )		// list is not empty
          Packit 1c1d7e
          	firstNode->prev = n;
          Packit 1c1d7e
              else					// initialize list
          Packit 1c1d7e
          	lastNode = n;
          Packit 1c1d7e
              firstNode = curNode = n;			// curNode affected
          Packit 1c1d7e
              numNodes++;
          Packit 1c1d7e
              curIndex = 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Inserts an item at the end of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::append( QCollection::Item d )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n = new QLNode( newItem(d) );
          Packit 1c1d7e
              CHECK_PTR( n );
          Packit 1c1d7e
              n->next = 0;
          Packit 1c1d7e
              if ( (n->prev = lastNode) )			// list is not empty
          Packit 1c1d7e
          	lastNode->next = n;
          Packit 1c1d7e
              else					// initialize list
          Packit 1c1d7e
          	firstNode = n;
          Packit 1c1d7e
              lastNode = curNode = n;			// curNode affected
          Packit 1c1d7e
              curIndex = numNodes;
          Packit 1c1d7e
              numNodes++;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Inserts an item at position \e index in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          bool QGList::insertAt( uint index, QCollection::Item d )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( index == 0 ) {				// insert at head of list
          Packit 1c1d7e
          	prepend( d );
          Packit 1c1d7e
          	return TRUE;
          Packit 1c1d7e
              } else if ( index == numNodes ) {		// append at tail of list
          Packit 1c1d7e
          	append( d );
          Packit 1c1d7e
          	return TRUE;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              QLNode *nextNode = locate( index );
          Packit 1c1d7e
              if ( !nextNode )				// illegal position
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              QLNode *prevNode = nextNode->prev;
          Packit 1c1d7e
              register QLNode *n = new QLNode( newItem(d) );
          Packit 1c1d7e
              CHECK_PTR( n );
          Packit 1c1d7e
              nextNode->prev = n;
          Packit 1c1d7e
              prevNode->next = n;
          Packit 1c1d7e
              n->prev = prevNode;				// link new node into list
          Packit 1c1d7e
              n->next = nextNode;
          Packit 1c1d7e
              curNode = n;				// curIndex set by locate()
          Packit 1c1d7e
              numNodes++;
          Packit 1c1d7e
              return TRUE;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Relinks node \e n and makes it the first node in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::relinkNode( QLNode *n )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( n == firstNode )			// already first
          Packit 1c1d7e
          	return;
          Packit 1c1d7e
              curNode = n;
          Packit 1c1d7e
              unlink();
          Packit 1c1d7e
              n->prev = 0;
          Packit 1c1d7e
              if ( (n->next = firstNode) )		// list is not empty
          Packit 1c1d7e
          	firstNode->prev = n;
          Packit 1c1d7e
              else					// initialize list
          Packit 1c1d7e
          	lastNode = n;
          Packit 1c1d7e
              firstNode = curNode = n;			// curNode affected
          Packit 1c1d7e
              numNodes++;
          Packit 1c1d7e
              curIndex = 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Unlinks the current list node and returns a pointer to this node.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QLNode *QGList::unlink()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( curNode == 0 )				// null current node
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              register QLNode *n = curNode;		// unlink this node
          Packit 1c1d7e
              if ( n == firstNode ) {			// removing first node ?
          Packit 1c1d7e
          	if ( (firstNode = n->next) ) {
          Packit 1c1d7e
          	    firstNode->prev = 0;
          Packit 1c1d7e
          	} else {
          Packit 1c1d7e
          	    lastNode = curNode = 0;		// list becomes empty
          Packit 1c1d7e
          	    curIndex = -1;
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              } else {
          Packit 1c1d7e
          	if ( n == lastNode ) {			// removing last node ?
          Packit 1c1d7e
          	    lastNode = n->prev;
          Packit 1c1d7e
          	    lastNode->next = 0;
          Packit 1c1d7e
          	} else {				// neither last nor first node
          Packit 1c1d7e
          	    n->prev->next = n->next;
          Packit 1c1d7e
          	    n->next->prev = n->prev;
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              }
          Packit 1c1d7e
              if ( n->next ) {				// change current node
          Packit 1c1d7e
          	curNode = n->next;
          Packit 1c1d7e
              } else if ( n->prev ) {
          Packit 1c1d7e
          	curNode = n->prev;
          Packit 1c1d7e
          	curIndex--;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              if ( iterators && iterators->count() ) {	// update iterators
          Packit 1c1d7e
          	QGListIterator *i = (QGListIterator*)iterators->first();
          Packit 1c1d7e
          	while ( i ) {				// fix all iterators that
          Packit 1c1d7e
          	    if ( i->curNode == n )		// refers to pending node
          Packit 1c1d7e
          		i->curNode = curNode;
          Packit 1c1d7e
          	    i = (QGListIterator*)iterators->next();
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              }
          Packit 1c1d7e
              numNodes--;
          Packit 1c1d7e
              return n;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes the node \e n from the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          bool QGList::removeNode( QLNode *n )
          Packit 1c1d7e
          {
          Packit 1c1d7e
          #if defined(CHECK_NULL)
          Packit 1c1d7e
              if ( n == 0 || (n->prev && n->prev->next != n) ||
          Packit 1c1d7e
          	 (n->next && n->next->prev != n) ) {
          Packit 1c1d7e
          	qWarning( "QGList::removeNode: Corrupted node" );
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              }
          Packit 1c1d7e
          #endif
          Packit 1c1d7e
              curNode = n;
          Packit 1c1d7e
              unlink();					// unlink node
          Packit 1c1d7e
              deleteItem( n->data );			// deallocate this node
          Packit 1c1d7e
              delete n;
          Packit 1c1d7e
              curNode  = firstNode;
          Packit 1c1d7e
              curIndex = curNode ? 0 : -1;
          Packit 1c1d7e
              return TRUE;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes the item \e d from the list.	Uses compareItems() to find the item.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          bool QGList::remove( QCollection::Item d )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( d ) {					// find the item
          Packit 1c1d7e
          	if ( find(d) == -1 )
          Packit 1c1d7e
          	    return FALSE;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              if ( !n )
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              deleteItem( n->data );			// deallocate this node
          Packit 1c1d7e
              delete n;
          Packit 1c1d7e
              return TRUE;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes the item \e d from the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          bool QGList::removeRef( QCollection::Item d )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( d ) {					// find the item
          Packit 1c1d7e
          	if ( findRef(d) == -1 )
          Packit 1c1d7e
          	    return FALSE;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              if ( !n )
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              deleteItem( n->data );			// deallocate this node
          Packit 1c1d7e
              delete n;
          Packit 1c1d7e
              return TRUE;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn bool QGList::removeFirst()
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes the first item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn bool QGList::removeLast()
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes the last item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes the item at position \e index from the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          bool QGList::removeAt( uint index )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !locate(index) )
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              if ( !n )
          Packit 1c1d7e
          	return FALSE;
          Packit 1c1d7e
              deleteItem( n->data );			// deallocate this node
          Packit 1c1d7e
              delete n;
          Packit 1c1d7e
              return TRUE;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Takes the node \e n out of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::takeNode( QLNode *n )
          Packit 1c1d7e
          {
          Packit 1c1d7e
          #if defined(CHECK_NULL)
          Packit 1c1d7e
              if ( n == 0 || (n->prev && n->prev->next != n) ||
          Packit 1c1d7e
          	 (n->next && n->next->prev != n) ) {
          Packit 1c1d7e
          	qWarning( "QGList::takeNode: Corrupted node" );
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
          #endif
          Packit 1c1d7e
              curNode = n;
          Packit 1c1d7e
              unlink();					// unlink node
          Packit 1c1d7e
              Item d = n->data;
          Packit 1c1d7e
              delete n;					// delete the node, not data
          Packit 1c1d7e
              curNode  = firstNode;
          Packit 1c1d7e
              curIndex = curNode ? 0 : -1;
          Packit 1c1d7e
              return d;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Takes the current item out of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::take()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              Item d = n ? n->data : 0;
          Packit 1c1d7e
              delete n;					// delete node, keep contents
          Packit 1c1d7e
              return d;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Takes the item at position \e index out of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::takeAt( uint index )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !locate(index) )
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              Item d = n ? n->data : 0;
          Packit 1c1d7e
              delete n;					// delete node, keep contents
          Packit 1c1d7e
              return d;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Takes the first item out of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::takeFirst()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              first();
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              Item d = n ? n->data : 0;
          Packit 1c1d7e
              delete n;
          Packit 1c1d7e
              return d;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Takes the last item out of the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::takeLast()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              last();
          Packit 1c1d7e
              QLNode *n = unlink();			// unlink node
          Packit 1c1d7e
              Item d = n ? n->data : 0;
          Packit 1c1d7e
              delete n;
          Packit 1c1d7e
              return d;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Removes all items from the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::clear()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n = firstNode;
          Packit 1c1d7e
          Packit 1c1d7e
              firstNode = lastNode = curNode = 0;		// initialize list
          Packit 1c1d7e
              numNodes = 0;
          Packit 1c1d7e
              curIndex = -1;
          Packit 1c1d7e
          Packit 1c1d7e
              if ( iterators && iterators->count() ) {
          Packit 1c1d7e
          	QGListIterator *i = (QGListIterator*)iterators->first();
          Packit 1c1d7e
          	while ( i ) {				// notify all iterators that
          Packit 1c1d7e
          	    i->curNode = 0;			// this list is empty
          Packit 1c1d7e
          	    i = (QGListIterator*)iterators->next();
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              }
          Packit 1c1d7e
          Packit 1c1d7e
              QLNode *prevNode;
          Packit 1c1d7e
              while ( n ) {				// for all nodes ...
          Packit 1c1d7e
          	deleteItem( n->data );			// deallocate data
          Packit 1c1d7e
          	prevNode = n;
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
          	delete prevNode;			// deallocate node
          Packit 1c1d7e
              }
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Finds an item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          int QGList::findRef( QCollection::Item d, bool fromStart )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n;
          Packit 1c1d7e
              int	     index;
          Packit 1c1d7e
              if ( fromStart ) {				// start from first node
          Packit 1c1d7e
          	n = firstNode;
          Packit 1c1d7e
          	index = 0;
          Packit 1c1d7e
              } else {					// start from current node
          Packit 1c1d7e
          	n = curNode;
          Packit 1c1d7e
          	index = curIndex;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              while ( n && n->data != d ) {		// find exact match
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
          	index++;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              curNode = n;
          Packit 1c1d7e
              curIndex = n ? index : -1;
          Packit 1c1d7e
              return curIndex;				// return position of item
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Finds an item in the list.  Uses compareItems().
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          int QGList::find( QCollection::Item d, bool fromStart )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n;
          Packit 1c1d7e
              int	     index;
          Packit 1c1d7e
              if ( fromStart ) {				// start from first node
          Packit 1c1d7e
          	n = firstNode;
          Packit 1c1d7e
          	index = 0;
          Packit 1c1d7e
              } else {					// start from current node
          Packit 1c1d7e
          	n = curNode;
          Packit 1c1d7e
          	index = curIndex;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              while ( n && compareItems(n->data,d) ){	// find equal match
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
          	index++;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              curNode = n;
          Packit 1c1d7e
              curIndex = n ? index : -1;
          Packit 1c1d7e
              return curIndex;				// return position of item
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Counts the number an item occurs in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          uint QGList::containsRef( QCollection::Item d ) const
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n = firstNode;
          Packit 1c1d7e
              uint     count = 0;
          Packit 1c1d7e
              while ( n ) {				// for all nodes...
          Packit 1c1d7e
          	if ( n->data == d )			// count # exact matches
          Packit 1c1d7e
          	    count++;
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return count;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Counts the number an item occurs in the list.	 Uses compareItems().
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          uint QGList::contains( QCollection::Item d ) const
          Packit 1c1d7e
          {
          Packit 1c1d7e
              register QLNode *n = firstNode;
          Packit 1c1d7e
              uint     count = 0;
          Packit 1c1d7e
              QGList  *that = (QGList*)this;		// mutable for compareItems()
          Packit 1c1d7e
              while ( n ) {				// for all nodes...
          Packit 1c1d7e
          	if ( !that->compareItems(n->data,d) )	// count # equal matches
          Packit 1c1d7e
          	    count++;
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return count;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn QCollection::Item QGList::at( uint index )
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Sets the item at position \e index to the current item.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn int QGList::at() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the current index.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn QLNode *QGList::currentNode() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the current node.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn QCollection::Item QGList::get() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the current item.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn QCollection::Item QGList::cfirst() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the first item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn QCollection::Item QGList::clast() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the last item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the first list item.	Sets this to current.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::first()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( firstNode ) {
          Packit 1c1d7e
          	curIndex = 0;
          Packit 1c1d7e
          	return (curNode=firstNode)->data;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the last list item.  Sets this to current.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::last()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( lastNode ) {
          Packit 1c1d7e
          	curIndex = numNodes-1;
          Packit 1c1d7e
          	return (curNode=lastNode)->data;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the next list item (after current).  Sets this to current.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::next()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( curNode ) {
          Packit 1c1d7e
          	if ( curNode->next ) {
          Packit 1c1d7e
          	    curIndex++;
          Packit 1c1d7e
          	    curNode = curNode->next;
          Packit 1c1d7e
          	    return curNode->data;
          Packit 1c1d7e
          	}
          Packit 1c1d7e
          	curIndex = -1;
          Packit 1c1d7e
          	curNode = 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the previous list item (before current).  Sets this to current.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGList::prev()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( curNode ) {
          Packit 1c1d7e
          	if ( curNode->prev ) {
          Packit 1c1d7e
          	    curIndex--;
          Packit 1c1d7e
          	    curNode = curNode->prev;
          Packit 1c1d7e
          	    return curNode->data;
          Packit 1c1d7e
          	}
          Packit 1c1d7e
          	curIndex = -1;
          Packit 1c1d7e
          	curNode = 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Converts the list to a vector.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::toVector( QGVector *vector ) const
          Packit 1c1d7e
          {
          Packit 1c1d7e
              vector->clear();
          Packit 1c1d7e
              if ( !vector->resize( count() ) )
          Packit 1c1d7e
          	return;
          Packit 1c1d7e
              register QLNode *n = firstNode;
          Packit 1c1d7e
              uint i = 0;
          Packit 1c1d7e
              while ( n ) {
          Packit 1c1d7e
          	vector->insert( i, n->data );
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
          	i++;
          Packit 1c1d7e
              }
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::heapSortPushDown( QCollection::Item* heap, int first, int last )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              int r = first;
          Packit 1c1d7e
              while( r <= last/2 ) {
          Packit 1c1d7e
          	// Node r has only one child ?
          Packit 1c1d7e
          	if ( last == 2*r ) {
          Packit 1c1d7e
          	    // Need for swapping ?
          Packit 1c1d7e
          	    if ( compareItems( heap[r], heap[ 2*r ] ) > 0 ) {
          Packit 1c1d7e
          		QCollection::Item tmp = heap[r];
          Packit 1c1d7e
          		heap[ r ] = heap[ 2*r ];
          Packit 1c1d7e
          		heap[ 2*r ] = tmp;
          Packit 1c1d7e
          	    }
          Packit 1c1d7e
          	    // That's it ...
          Packit 1c1d7e
          	    r = last;
          Packit 1c1d7e
          	} else {
          Packit 1c1d7e
          	    // Node has two children
          Packit 1c1d7e
          	    if ( compareItems( heap[r], heap[ 2*r ] ) > 0 &&
          Packit 1c1d7e
          		 compareItems( heap[ 2*r ], heap[ 2*r+1 ] ) <= 0 ) {
          Packit 1c1d7e
          		// Swap with left child
          Packit 1c1d7e
          		QCollection::Item tmp = heap[r];
          Packit 1c1d7e
          		heap[ r ] = heap[ 2*r ];
          Packit 1c1d7e
          		heap[ 2*r ] = tmp;
          Packit 1c1d7e
          		r *= 2;
          Packit 1c1d7e
          	    } else if ( compareItems( heap[r], heap[ 2*r+1 ] ) > 0 &&
          Packit 1c1d7e
          			compareItems( heap[ 2*r+1 ], heap[ 2*r ] ) < 0 ) {
          Packit 1c1d7e
          		// Swap with right child
          Packit 1c1d7e
          		QCollection::Item tmp = heap[r];
          Packit 1c1d7e
          		heap[ r ] = heap[ 2*r+1 ];
          Packit 1c1d7e
          		heap[ 2*r+1 ] = tmp;
          Packit 1c1d7e
          		r = 2*r+1;
          Packit 1c1d7e
          	    } else {
          Packit 1c1d7e
          		// We are done
          Packit 1c1d7e
          		r = last;
          Packit 1c1d7e
          	    }
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              }
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*! Sorts the list by the result of the virtual compareItems() function.
          Packit 1c1d7e
          Packit 1c1d7e
            The Heap-Sort algorithm is used for sorting.  It sorts n items with
          Packit 1c1d7e
            O(n*log n) compares.  This is the asymptotic optimal solution of the
          Packit 1c1d7e
            sorting problem.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          void QGList::sort()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              uint n = count();
          Packit 1c1d7e
              if ( n < 2 )
          Packit 1c1d7e
          	return;
          Packit 1c1d7e
          Packit 1c1d7e
              // Create the heap
          Packit 1c1d7e
              QCollection::Item* realheap = new QCollection::Item[ n ];
          Packit 1c1d7e
              // Wow, what a fake. But I want the heap to be indexed as 1...n
          Packit 1c1d7e
              QCollection::Item* heap = realheap - 1;
          Packit 1c1d7e
              int size = 0;
          Packit 1c1d7e
              QLNode* insert = firstNode;
          Packit 1c1d7e
              for( ; insert != 0; insert = insert->next ) {
          Packit 1c1d7e
          	heap[++size] = insert->data;
          Packit 1c1d7e
          	int i = size;
          Packit 1c1d7e
          	while( i > 1 && compareItems( heap[i], heap[ i / 2 ] ) < 0 ) {
          Packit 1c1d7e
          	    QCollection::Item tmp = heap[ i ];
          Packit 1c1d7e
          	    heap[ i ] = heap[ i/2 ];
          Packit 1c1d7e
          	    heap[ i/2 ] = tmp;
          Packit 1c1d7e
          	    i /= 2;
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              }
          Packit 1c1d7e
          Packit 1c1d7e
              insert = firstNode;
          Packit 1c1d7e
              // Now do the sorting
          Packit 1c1d7e
              for ( int i = n; i > 0; i-- ) {
          Packit 1c1d7e
          	insert->data = heap[1];
          Packit 1c1d7e
          	insert = insert->next;
          Packit 1c1d7e
          	if ( i > 1 ) {
          Packit 1c1d7e
          	    heap[1] = heap[i];
          Packit 1c1d7e
          	    heapSortPushDown( heap, 1, i - 1 );
          Packit 1c1d7e
          	}
          Packit 1c1d7e
              }
          Packit 1c1d7e
          Packit 1c1d7e
              delete [] realheap;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*****************************************************************************
          Packit 1c1d7e
            QGList stream functions
          Packit 1c1d7e
           *****************************************************************************/
          Packit 1c1d7e
          Packit 1c1d7e
          #ifndef QT_NO_DATASTREAM
          Packit 1c1d7e
          QDataStream &operator>>( QDataStream &s, QGList &list )
          Packit 1c1d7e
          {						// read list
          Packit 1c1d7e
              return list.read( s );
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          QDataStream &operator<<( QDataStream &s, const QGList &list )
          Packit 1c1d7e
          {						// write list
          Packit 1c1d7e
              return list.write( s );
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Reads a list from the stream \e s.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QDataStream &QGList::read( QDataStream &s )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              uint num;
          Packit 1c1d7e
              s >> num;					// read number of items
          Packit 1c1d7e
              clear();					// clear list
          Packit 1c1d7e
              while ( num-- ) {				// read all items
          Packit 1c1d7e
          	Item d;
          Packit 1c1d7e
          	read( s, d );
          Packit 1c1d7e
          	CHECK_PTR( d );
          Packit 1c1d7e
          	if ( !d )				// no memory
          Packit 1c1d7e
          	    break;
          Packit 1c1d7e
          	QLNode *n = new QLNode( d );
          Packit 1c1d7e
          	CHECK_PTR( n );
          Packit 1c1d7e
          	if ( !n )				// no memory
          Packit 1c1d7e
          	    break;
          Packit 1c1d7e
          	n->next = 0;
          Packit 1c1d7e
          	if ( (n->prev = lastNode) )		// list is not empty
          Packit 1c1d7e
          	    lastNode->next = n;
          Packit 1c1d7e
          	else					// initialize list
          Packit 1c1d7e
          	    firstNode = n;
          Packit 1c1d7e
          	lastNode = n;
          Packit 1c1d7e
          	numNodes++;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              curNode  = firstNode;
          Packit 1c1d7e
              curIndex = curNode ? 0 : -1;
          Packit 1c1d7e
              return s;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Writes the list to the stream \e s.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QDataStream &QGList::write( QDataStream &s ) const
          Packit 1c1d7e
          {
          Packit 1c1d7e
              s << count();				// write number of items
          Packit 1c1d7e
              QLNode *n = firstNode;
          Packit 1c1d7e
              while ( n ) {				// write all items
          Packit 1c1d7e
          	write( s, n->data );
          Packit 1c1d7e
          	n = n->next;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return s;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          #endif // QT_NO_DATASTREAM
          Packit 1c1d7e
          Packit 1c1d7e
          /*****************************************************************************
          Packit 1c1d7e
            QGListIterator member functions
          Packit 1c1d7e
           *****************************************************************************/
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \class QGListIterator qglist.h
          Packit 1c1d7e
            \brief The QGListIterator class is an internal class for implementing QListIterator.
          Packit 1c1d7e
          Packit 1c1d7e
            QGListIterator is a strictly internal class that does the heavy work for
          Packit 1c1d7e
            QListIterator.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Constructs an iterator that operates on the list \e l.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGListIterator::QGListIterator( const QGList &l )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              list = (QGList *)&l;			// get reference to list
          Packit 1c1d7e
              curNode = list->firstNode;			// set to first node
          Packit 1c1d7e
              if ( !list->iterators ) {
          Packit 1c1d7e
          	list->iterators = new QGList;		// create iterator list
          Packit 1c1d7e
          	CHECK_PTR( list->iterators );
          Packit 1c1d7e
              }
          Packit 1c1d7e
              list->iterators->append( this );		// attach iterator to list
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Constructs a copy of the iterator \e it.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGListIterator::QGListIterator( const QGListIterator &it )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              list = it.list;
          Packit 1c1d7e
              curNode = it.curNode;
          Packit 1c1d7e
              if ( list )
          Packit 1c1d7e
          	list->iterators->append( this );	// attach iterator to list
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Assigns a copy of the iterator \e it and returns a reference to this
          Packit 1c1d7e
            iterator.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGListIterator &QGListIterator::operator=( const QGListIterator &it )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( list )					// detach from old list
          Packit 1c1d7e
          	list->iterators->removeRef( this );
          Packit 1c1d7e
              list = it.list;
          Packit 1c1d7e
              curNode = it.curNode;
          Packit 1c1d7e
              if ( list )
          Packit 1c1d7e
          	list->iterators->append( this );	// attach to new list
          Packit 1c1d7e
              return *this;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Destroys the iterator.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QGListIterator::~QGListIterator()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( list )					// detach iterator from list
          Packit 1c1d7e
          	list->iterators->removeRef(this);
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn bool QGListIterator::atFirst() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns TRUE if the iterator points to the first item, otherwise FALSE.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn bool QGListIterator::atLast() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns TRUE if the iterator points to the last item, otherwise FALSE.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Sets the list iterator to point to the first item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::toFirst()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !list ) {
          Packit 1c1d7e
          #if defined(CHECK_NULL)
          Packit 1c1d7e
          	qWarning( "QGListIterator::toFirst: List has been deleted" );
          Packit 1c1d7e
          #endif
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return list->firstNode ? (curNode = list->firstNode)->getData() : 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Sets the list iterator to point to the last item in the list.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::toLast()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !list ) {
          Packit 1c1d7e
          #if defined(CHECK_NULL)
          Packit 1c1d7e
          	qWarning( "QGListIterator::toLast: List has been deleted" );
          Packit 1c1d7e
          #endif
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              }
          Packit 1c1d7e
              return list->lastNode ? (curNode = list->lastNode)->getData() : 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \fn QCollection::Item QGListIterator::get() const
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Returns the iterator item.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Moves to the next item (postfix).
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::operator()()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !curNode )
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              QCollection::Item d = curNode->getData();
          Packit 1c1d7e
              curNode = curNode->next;
          Packit 1c1d7e
              return  d;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Moves to the next item (prefix).
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::operator++()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !curNode )
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              curNode = curNode->next;
          Packit 1c1d7e
              return curNode ? curNode->getData() : 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Moves \e jumps positions forward.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::operator+=( uint jumps )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              while ( curNode && jumps-- )
          Packit 1c1d7e
          	curNode = curNode->next;
          Packit 1c1d7e
              return curNode ? curNode->getData() : 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Moves to the previous item (prefix).
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::operator--()
          Packit 1c1d7e
          {
          Packit 1c1d7e
              if ( !curNode )
          Packit 1c1d7e
          	return 0;
          Packit 1c1d7e
              curNode = curNode->prev;
          Packit 1c1d7e
              return curNode ? curNode->getData() : 0;
          Packit 1c1d7e
          }
          Packit 1c1d7e
          Packit 1c1d7e
          /*!
          Packit 1c1d7e
            \internal
          Packit 1c1d7e
            Moves \e jumps positions backward.
          Packit 1c1d7e
          */
          Packit 1c1d7e
          Packit 1c1d7e
          QCollection::Item QGListIterator::operator-=( uint jumps )
          Packit 1c1d7e
          {
          Packit 1c1d7e
              while ( curNode && jumps-- )
          Packit 1c1d7e
          	curNode = curNode->prev;
          Packit 1c1d7e
              return curNode ? curNode->getData() : 0;
          Packit 1c1d7e
          }