diff options
Diffstat (limited to 'src/tools/qglist.cpp')
| -rw-r--r-- | src/tools/qglist.cpp | 1267 |
1 files changed, 1267 insertions, 0 deletions
diff --git a/src/tools/qglist.cpp b/src/tools/qglist.cpp new file mode 100644 index 000000000..adfc2a002 --- /dev/null +++ b/src/tools/qglist.cpp @@ -0,0 +1,1267 @@ +/**************************************************************************** +** +** Implementation of TQGList and TQGListIterator classes +** +** Created : 920624 +** +** Copyright (C) 1992-2008 Trolltech ASA. All rights reserved. +** +** This file is part of the tools module of the TQt GUI Toolkit. +** +** This file may be used under the terms of the GNU General +** Public License versions 2.0 or 3.0 as published by the Free +** Software Foundation and appearing in the files LICENSE.GPL2 +** and LICENSE.GPL3 included in the packaging of this file. +** Alternatively you may (at your option) use any later version +** of the GNU General Public License if such license has been +** publicly approved by Trolltech ASA (or its successors, if any) +** and the KDE Free TQt Foundation. +** +** Please review the following information to ensure GNU General +** Public Licensing retquirements will be met: +** http://trolltech.com/products/qt/licenses/licensing/opensource/. +** If you are unsure which license is appropriate for your use, please +** review the following information: +** http://trolltech.com/products/qt/licenses/licensing/licensingoverview +** or contact the sales department at sales@trolltech.com. +** +** This file may be used under the terms of the Q Public License as +** defined by Trolltech ASA and appearing in the file LICENSE.TQPL +** included in the packaging of this file. Licensees holding valid TQt +** Commercial licenses may use this file in accordance with the TQt +** Commercial License Agreement provided with the Software. +** +** This file is provided "AS IS" with NO WARRANTY OF ANY KIND, +** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR +** A PARTICULAR PURPOSE. Trolltech reserves all rights not granted +** herein. +** +**********************************************************************/ + +#include "qglist.h" +#include "qgvector.h" +#include "qdatastream.h" +#include "qvaluelist.h" + +/*! + \class TQLNode qglist.h + \reentrant + \ingroup collection + \brief The TQLNode class is an internal class for the TQPtrList template collection. + + \internal + + TQLNode is a doubly-linked list node. It has three pointers: + \list 1 + \i Pointer to the previous node. + \i Pointer to the next node. + \i Pointer to the actual data. + \endlist + + It might sometimes be practical to have direct access to the list nodes + in a TQPtrList, but it is seldom retquired. + + Be very careful if you want to access the list nodes. The heap can + easily get corrupted if you make a mistake. + + \sa TQPtrList::currentNode(), TQPtrList::removeNode(), TQPtrList::takeNode() +*/ + +/*! + \fn TQPtrCollection::Item TQLNode::getData() + Returns a pointer (\c void*) to the actual data in the list node. +*/ + + +/*! + \class TQGList qglist.h + \reentrant + \ingroup collection + \brief The TQGList class is an internal class for implementing TQt collection classes. + + \internal + + TQGList is a strictly internal class that acts as a base class for + several collection classes; TQPtrList, TQPtrQueue and TQPtrStack. + + TQGList has some virtual functions that can be reimplemented to + customize the subclasses, namely compareItems(), read() and + write. Normally, you do not have to reimplement any of these + functions. If you still want to reimplement them, see the TQStrList + class (qstrlist.h) for an example. +*/ + + +/* Internal helper class for TQGList. Contains some optimization for + the typically case where only one iterators is activre on the list. + */ +class TQGListIteratorList +{ +public: + TQGListIteratorList() + : list(0), iterator(0) { + } + ~TQGListIteratorList() { + notifyClear( TRUE ); + delete list; + } + + void add( TQGListIterator* i ) { + if ( !iterator ) { + iterator = i; + } else if ( list ) { + list->push_front( i ); + } else { + list = new TQValueList<TQGListIterator*>; + list->push_front( i ); + } + } + + void remove( TQGListIterator* i ) { + if ( iterator == i ) { + iterator = 0; + } else if ( list ) { + list->remove( i ); + if ( list->isEmpty() ) { + delete list; + list = 0; + } + } + } + + void notifyClear( bool zeroList ) { + if ( iterator ) { + if ( zeroList ) + iterator->list = 0; + iterator->curNode = 0; + } + if ( list ) { + for ( TQValueList<TQGListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) { + if ( zeroList ) + (*i)->list = 0; + (*i)->curNode = 0; + } + } + } + + void notifyRemove( TQLNode* n, TQLNode* curNode ) { + if ( iterator ) { + if ( iterator->curNode == n ) + iterator->curNode = curNode; + } + if ( list ) { + for ( TQValueList<TQGListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) { + if ( (*i)->curNode == n ) + (*i)->curNode = curNode; + } + } + } + +private: + TQValueList<TQGListIterator*>* list; + TQGListIterator* iterator; +}; + + + +/***************************************************************************** + Default implementation of virtual functions + *****************************************************************************/ + +/*! + Documented as TQPtrList::compareItems(). + + Compares \a item1 with \a item2. +*/ +int TQGList::compareItems( TQPtrCollection::Item item1, TQPtrCollection::Item item2 ) +{ + return item1 != item2; // compare pointers +} + +#ifndef QT_NO_DATASTREAM +/*! + \overload + 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() +*/ + +TQDataStream &TQGList::read( TQDataStream &s, TQPtrCollection::Item &item ) +{ + item = 0; + return s; +} + +/*! + \overload + Writes a collection/list item to the stream \a s and + returns a reference to the stream. + + The default implementation does nothing. + + \sa read() +*/ + +TQDataStream &TQGList::write( TQDataStream &s, TQPtrCollection::Item ) const +{ + return s; +} +#endif // QT_NO_DATASTREAM + +/***************************************************************************** + TQGList member functions + *****************************************************************************/ + +/*! + Constructs an empty list. +*/ + +TQGList::TQGList() +{ + firstNode = lastNode = curNode = 0; // initialize list + numNodes = 0; + curIndex = -1; + iterators = 0; // initialize iterator list +} + +/*! + Constructs a copy of \a list. +*/ + +TQGList::TQGList( const TQGList & list ) + : TQPtrCollection( list ) +{ + firstNode = lastNode = curNode = 0; // initialize list + numNodes = 0; + curIndex = -1; + iterators = 0; // initialize iterator list + TQLNode *n = list.firstNode; + while ( n ) { // copy all items from list + append( n->data ); + n = n->next; + } +} + +/*! + Removes all items from the list and destroys the list. +*/ + +TQGList::~TQGList() +{ + clear(); + delete iterators; + // Workaround for GCC 2.7.* bug. Compiler constructs 'static' TQGList + // instances twice on the same address and therefore tries to destruct + // twice on the same address! This is insane but let's try not to crash + // here. + iterators = 0; +} + + +/*! + Assigns \a list to this list. +*/ + +TQGList& TQGList::operator=( const TQGList &list ) +{ + if ( &list == this ) + return *this; + + clear(); + if ( list.count() > 0 ) { + TQLNode *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. Returns TRUE if the lists + contain the same data, otherwise FALSE. +*/ + +bool TQGList::operator==( const TQGList &list ) const +{ + if ( count() != list.count() ) + return FALSE; + + if ( count() == 0 ) + return TRUE; + + TQLNode *n1 = firstNode; + TQLNode *n2 = list.firstNode; + while ( n1 && n2 ) { + // should be mutable + if ( ( (TQGList*)this )->compareItems( n1->data, n2->data ) != 0 ) + return FALSE; + n1 = n1->next; + n2 = n2->next; + } + + return TRUE; +} + +/*! + \fn uint TQGList::count() const + + Returns the number of items in the list. +*/ + + +/*! + Returns the node at position \a index. Sets this node to current. +*/ + +TQLNode *TQGList::locate( uint index ) +{ + if ( index == (uint)curIndex ) // current node ? + return curNode; + if ( !curNode && firstNode ) { // set current node + curNode = firstNode; + curIndex = 0; + } + register TQLNode *node; + int distance = index - curIndex; // node distance to cur node + bool forward; // direction to traverse + + if ( index >= numNodes ) + 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; +} + + +/*! + Inserts item \a d at its sorted position in the list. +*/ + +void TQGList::inSort( TQPtrCollection::Item d ) +{ + int index = 0; + register TQLNode *n = firstNode; + while ( n && compareItems(n->data,d) < 0 ){ // find position in list + n = n->next; + index++; + } + insertAt( index, d ); +} + + +/*! + Inserts item \a d at the start of the list. +*/ + +void TQGList::prepend( TQPtrCollection::Item d ) +{ + register TQLNode *n = new TQLNode( newItem(d) ); + Q_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; +} + + +/*! + Inserts item \a d at the end of the list. +*/ + +void TQGList::append( TQPtrCollection::Item d ) +{ + register TQLNode *n = new TQLNode( newItem(d) ); + Q_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++; +} + + +/*! + Inserts item \a d at position \a index in the list. +*/ + +bool TQGList::insertAt( uint index, TQPtrCollection::Item d ) +{ + if ( index == 0 ) { + prepend( d ); + return TRUE; + } else if ( index == numNodes ) { + append( d ); + return TRUE; + } + TQLNode *nextNode = locate( index ); + if ( !nextNode ) + return FALSE; + TQLNode *prevNode = nextNode->prev; + register TQLNode *n = new TQLNode( newItem(d) ); + Q_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; +} + + +/*! + Relinks node \a n and makes it the first node in the list. +*/ + +void TQGList::relinkNode( TQLNode *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; +} + + +/*! + Unlinks the current list node and returns a pointer to this node. +*/ + +TQLNode *TQGList::unlink() +{ + if ( curNode == 0 ) // null current node + return 0; + register TQLNode *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->notifyRemove( n, curNode ); + numNodes--; + return n; +} + + +/*! + Removes the node \a n from the list. +*/ + +bool TQGList::removeNode( TQLNode *n ) +{ +#if defined(QT_CHECK_NULL) + if ( n == 0 || (n->prev && n->prev->next != n) || + (n->next && n->next->prev != n) ) { + qWarning( "TQGList::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; +} + +/*! + Removes the item \a d from the list. Uses compareItems() to find the item. + + If \a d is 0, removes the current item. +*/ + +bool TQGList::remove( TQPtrCollection::Item d ) +{ + if ( d && find(d) == -1 ) + return FALSE; + TQLNode *n = unlink(); + if ( !n ) + return FALSE; + deleteItem( n->data ); + delete n; + return TRUE; +} + +/*! + Removes the item \a d from the list. +*/ + +bool TQGList::removeRef( TQPtrCollection::Item d ) +{ + if ( findRef(d) == -1 ) + return FALSE; + TQLNode *n = unlink(); + if ( !n ) + return FALSE; + deleteItem( n->data ); + delete n; + return TRUE; +} + +/*! + \fn bool TQGList::removeFirst() + + Removes the first item in the list. +*/ + +/*! + \fn bool TQGList::removeLast() + + Removes the last item in the list. +*/ + +/*! + Removes the item at position \a index from the list. +*/ + +bool TQGList::removeAt( uint index ) +{ + if ( !locate(index) ) + return FALSE; + TQLNode *n = unlink(); + if ( !n ) + return FALSE; + deleteItem( n->data ); + delete n; + return TRUE; +} + + +/*! + Replaces the item at index \a index with \a d. +*/ +bool TQGList::replaceAt( uint index, TQPtrCollection::Item d ) +{ + TQLNode *n = locate( index ); + if ( !n ) + return FALSE; + if ( n->data != d ) { + deleteItem( n->data ); + n->data = newItem( d ); + } + return TRUE; +} + + + +/*! + Takes the node \a n out of the list. +*/ + +TQPtrCollection::Item TQGList::takeNode( TQLNode *n ) +{ +#if defined(QT_CHECK_NULL) + if ( n == 0 || (n->prev && n->prev->next != n) || + (n->next && n->next->prev != n) ) { + qWarning( "TQGList::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; +} + +/*! + Takes the current item out of the list. +*/ + +TQPtrCollection::Item TQGList::take() +{ + TQLNode *n = unlink(); // unlink node + Item d = n ? n->data : 0; + delete n; // delete node, keep contents + return d; +} + +/*! + Takes the item at position \a index out of the list. +*/ + +TQPtrCollection::Item TQGList::takeAt( uint index ) +{ + if ( !locate(index) ) + return 0; + TQLNode *n = unlink(); // unlink node + Item d = n ? n->data : 0; + delete n; // delete node, keep contents + return d; +} + +/*! + Takes the first item out of the list. +*/ + +TQPtrCollection::Item TQGList::takeFirst() +{ + first(); + TQLNode *n = unlink(); // unlink node + Item d = n ? n->data : 0; + delete n; + return d; +} + +/*! + Takes the last item out of the list. +*/ + +TQPtrCollection::Item TQGList::takeLast() +{ + last(); + TQLNode *n = unlink(); // unlink node + Item d = n ? n->data : 0; + delete n; + return d; +} + + +/*! + Removes all items from the list. +*/ + +void TQGList::clear() +{ + register TQLNode *n = firstNode; + + firstNode = lastNode = curNode = 0; // initialize list + numNodes = 0; + curIndex = -1; + + if ( iterators ) + iterators->notifyClear( FALSE ); + + TQLNode *prevNode; + while ( n ) { // for all nodes ... + deleteItem( n->data ); // deallocate data + prevNode = n; + n = n->next; + delete prevNode; // deallocate node + } +} + + +/*! + Finds item \a d in the list. If \a fromStart is TRUE the search + begins at the first node; otherwise it begins at the current node. +*/ + +int TQGList::findRef( TQPtrCollection::Item d, bool fromStart ) +{ + register TQLNode *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 +} + +/*! + Finds item \a d in the list using compareItems(). If \a fromStart is + TRUE the search begins at the first node; otherwise it begins at the + current node. +*/ + +int TQGList::find( TQPtrCollection::Item d, bool fromStart ) +{ + register TQLNode *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 +} + + +/*! + Counts the number item \a d occurs in the list. +*/ + +uint TQGList::containsRef( TQPtrCollection::Item d ) const +{ + register TQLNode *n = firstNode; + uint count = 0; + while ( n ) { // for all nodes... + if ( n->data == d ) // count # exact matches + count++; + n = n->next; + } + return count; +} + +/*! + Counts the number of times item \a d occurs in the list. Uses + compareItems(). +*/ + +uint TQGList::contains( TQPtrCollection::Item d ) const +{ + register TQLNode *n = firstNode; + uint count = 0; + TQGList *that = (TQGList*)this; // mutable for compareItems() + while ( n ) { // for all nodes... + if ( !that->compareItems(n->data,d) ) // count # equal matches + count++; + n = n->next; + } + return count; +} + + +/*! + \overload TQPtrCollection::Item TQGList::at( uint index ) + + Sets the item at position \a index to the current item. +*/ + +/*! + \fn int TQGList::at() const + + Returns the current index. +*/ + +/*! + \fn TQLNode *TQGList::currentNode() const + + Returns the current node. +*/ + +/*! + \fn TQPtrCollection::Item TQGList::get() const + + Returns the current item. +*/ + +/*! + \fn TQPtrCollection::Item TQGList::cfirst() const + + Returns the first item in the list. +*/ + +/*! + \fn TQPtrCollection::Item TQGList::clast() const + + Returns the last item in the list. +*/ + + +/*! + Returns the first list item. Sets this to current. +*/ + +TQPtrCollection::Item TQGList::first() +{ + if ( firstNode ) { + curIndex = 0; + return (curNode=firstNode)->data; + } + return 0; +} + +/*! + Returns the last list item. Sets this to current. +*/ + +TQPtrCollection::Item TQGList::last() +{ + if ( lastNode ) { + curIndex = numNodes-1; + return (curNode=lastNode)->data; + } + return 0; +} + +/*! + Returns the next list item (after current). Sets this to current. +*/ + +TQPtrCollection::Item TQGList::next() +{ + if ( curNode ) { + if ( curNode->next ) { + curIndex++; + curNode = curNode->next; + return curNode->data; + } + curIndex = -1; + curNode = 0; + } + return 0; +} + +/*! + Returns the previous list item (before current). Sets this to current. +*/ + +TQPtrCollection::Item TQGList::prev() +{ + if ( curNode ) { + if ( curNode->prev ) { + curIndex--; + curNode = curNode->prev; + return curNode->data; + } + curIndex = -1; + curNode = 0; + } + return 0; +} + + +/*! + Converts the list to a vector, \a vector. +*/ + +void TQGList::toVector( TQGVector *vector ) const +{ + vector->clear(); + if ( !vector->resize( count() ) ) + return; + register TQLNode *n = firstNode; + uint i = 0; + while ( n ) { + vector->insert( i, n->data ); + n = n->next; + i++; + } +} + +void TQGList::heapSortPushDown( TQPtrCollection::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 ) { + TQPtrCollection::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 + TQPtrCollection::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 + TQPtrCollection::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 TQGList::sort() +{ + uint n = count(); + if ( n < 2 ) + return; + + // Create the heap + TQPtrCollection::Item* realheap = new TQPtrCollection::Item[ n ]; + // Wow, what a fake. But I want the heap to be indexed as 1...n + TQPtrCollection::Item* heap = realheap - 1; + int size = 0; + TQLNode* 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 ) { + TQPtrCollection::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; +} + + +/***************************************************************************** + TQGList stream functions + *****************************************************************************/ + +#ifndef QT_NO_DATASTREAM +TQDataStream &operator>>( TQDataStream &s, TQGList &list ) +{ // read list + return list.read( s ); +} + +TQDataStream &operator<<( TQDataStream &s, const TQGList &list ) +{ // write list + return list.write( s ); +} + +/*! + Reads a list from the stream \a s. +*/ + +TQDataStream &TQGList::read( TQDataStream &s ) +{ + uint num; + s >> num; // read number of items + clear(); // clear list + while ( num-- ) { // read all items + Item d; + read( s, d ); + Q_CHECK_PTR( d ); + if ( !d ) // no memory + break; + TQLNode *n = new TQLNode( d ); + Q_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; +} + +/*! + Writes the list to the stream \a s. +*/ + +TQDataStream &TQGList::write( TQDataStream &s ) const +{ + s << count(); // write number of items + TQLNode *n = firstNode; + while ( n ) { // write all items + write( s, n->data ); + n = n->next; + } + return s; +} + +#endif // QT_NO_DATASTREAM + + + +/*! \internal + */ +TQLNode* TQGList::erase( TQLNode* it ) +{ + TQLNode* n = it; + it = it->next; + removeNode( n ); + return it; +} + + +/***************************************************************************** + TQGListIterator member functions + *****************************************************************************/ + +/*! + \class TQGListIterator qglist.h + \reentrant + \ingroup collection + \brief The TQGListIterator class is an internal class for implementing TQPtrListIterator. + + \internal + + TQGListIterator is a strictly internal class that does the heavy work for + TQPtrListIterator. +*/ + +/*! + \internal + Constructs an iterator that operates on the list \a l. +*/ + +TQGListIterator::TQGListIterator( const TQGList &l ) +{ + list = (TQGList *)&l; // get reference to list + curNode = list->firstNode; // set to first node + if ( !list->iterators ) { + list->iterators = new TQGListIteratorList; // create iterator list + Q_CHECK_PTR( list->iterators ); + } + list->iterators->add( this ); // attach iterator to list +} + +/*! + \internal + Constructs a copy of the iterator \a it. +*/ + +TQGListIterator::TQGListIterator( const TQGListIterator &it ) +{ + list = it.list; + curNode = it.curNode; + if ( list ) + list->iterators->add( this ); // attach iterator to list +} + +/*! + \internal + Assigns a copy of the iterator \a it and returns a reference to this + iterator. +*/ + +TQGListIterator &TQGListIterator::operator=( const TQGListIterator &it ) +{ + if ( list ) // detach from old list + list->iterators->remove( this ); + list = it.list; + curNode = it.curNode; + if ( list ) + list->iterators->add( this ); // attach to new list + return *this; +} + +/*! + \internal + Destroys the iterator. +*/ + +TQGListIterator::~TQGListIterator() +{ + if ( list ) // detach iterator from list + list->iterators->remove(this); +} + + +/*! + \fn bool TQGListIterator::atFirst() const + \internal + Returns TRUE if the iterator points to the first item, otherwise FALSE. +*/ + +/*! + \fn bool TQGListIterator::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. +*/ + +TQPtrCollection::Item TQGListIterator::toFirst() +{ + if ( !list ) { +#if defined(QT_CHECK_NULL) + qWarning( "TQGListIterator::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. +*/ + +TQPtrCollection::Item TQGListIterator::toLast() +{ + if ( !list ) { +#if defined(QT_CHECK_NULL) + qWarning( "TQGListIterator::toLast: List has been deleted" ); +#endif + return 0; + } + return list->lastNode ? (curNode = list->lastNode)->getData() : 0; +} + + +/*! + \fn TQPtrCollection::Item TQGListIterator::get() const + \internal + Returns the iterator item. +*/ + + +/*! + \internal + Moves to the next item (postfix). +*/ + +TQPtrCollection::Item TQGListIterator::operator()() +{ + if ( !curNode ) + return 0; + TQPtrCollection::Item d = curNode->getData(); + curNode = curNode->next; + return d; +} + +/*! + \internal + Moves to the next item (prefix). +*/ + +TQPtrCollection::Item TQGListIterator::operator++() +{ + if ( !curNode ) + return 0; + curNode = curNode->next; + return curNode ? curNode->getData() : 0; +} + +/*! + \internal + Moves \a jumps positions forward. +*/ + +TQPtrCollection::Item TQGListIterator::operator+=( uint jumps ) +{ + while ( curNode && jumps-- ) + curNode = curNode->next; + return curNode ? curNode->getData() : 0; +} + +/*! + \internal + Moves to the previous item (prefix). +*/ + +TQPtrCollection::Item TQGListIterator::operator--() +{ + if ( !curNode ) + return 0; + curNode = curNode->prev; + return curNode ? curNode->getData() : 0; +} + +/*! + \internal + Moves \a jumps positions backward. +*/ + +TQPtrCollection::Item TQGListIterator::operator-=( uint jumps ) +{ + while ( curNode && jumps-- ) + curNode = curNode->prev; + return curNode ? curNode->getData() : 0; +} |