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