1 /****************************************************************************
4 ** Implementation of QGList and QGListIterator classes
8 ** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
10 ** This file is part of the tools module of the Qt GUI Toolkit.
12 ** This file may be distributed under the terms of the Q Public License
13 ** as defined by Trolltech AS of Norway and appearing in the file
14 ** LICENSE.QPL included in the packaging of this file.
16 ** This file may be distributed and/or modified under the terms of the
17 ** GNU General Public License version 2 as published by the Free Software
18 ** Foundation and appearing in the file LICENSE.GPL included in the
19 ** packaging of this file.
21 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
22 ** licenses may use this file in accordance with the Qt Commercial License
23 ** Agreement provided with the Software.
25 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
26 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
28 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
29 ** information about Qt Commercial License Agreements.
30 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
31 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
33 ** Contact info@trolltech.com if any conditions of this licensing are
36 **********************************************************************/
40 #include "qdatastream.h"
45 \class QLNode qglist.h
46 \brief The QLNode class is an internal class for the QList template collection.
48 QLNode is a doubly linked list node; it has three pointers:
50 <li> Pointer to the previous node.
51 <li> Pointer to the next node.
52 <li> Pointer to the actual data.
55 Sometimes it might be practical to have direct access to the list nodes
56 in a QList, but it is seldom required.
58 \warning Be very careful if you want to access the list nodes. The heap
59 can easily get corrupted if you make a mistake.
61 \sa QList::currentNode(), QList::removeNode(), QList::takeNode()
65 \fn QCollection::Item QLNode::getData()
66 Returns a pointer (\c void*) to the actual data in the list node.
71 \class QGList qglist.h
72 \brief The QGList class is an internal class for implementing Qt collection classes.
74 QGList is a strictly internal class that acts as a base class for several
75 \link collection.html collection classes\endlink; QList, QQueue and
78 QGList has some virtual functions that can be reimplemented to customize
81 <li> compareItems() compares two collection/list items.
82 <li> read() reads a collection/list item from a QDataStream.
83 <li> write() writes a collection/list item to a QDataStream.
85 Normally, you do not have to reimplement any of these functions.
86 If you still want to reimplement them, see the QStrList class (qstrlist.h),
87 which is a good example.
91 /*****************************************************************************
92 Default implementation of virtual functions
93 *****************************************************************************/
96 This virtual function compares two list items.
100 <li> 0 if \e item1 == \e item2
101 <li> non-zero if \e item1 != \e item2
104 This function returns \e int rather than \e bool so that
105 reimplementations can return three values and use it to sort by:
108 <li> 0 if \e item1 == \e item2
109 <li> \> 0 (positive integer) if \e item1 \> \e item2
110 <li> \< 0 (negative integer) if \e item1 \< \e item2
113 The QList::inSort() function requires that compareItems() is implemented
116 This function should not modify the list because some const functions
119 The default implementation compares the pointers:
125 int QGList::compareItems( QCollection::Item item1, QCollection::Item item2 )
127 return item1 != item2; // compare pointers
130 #ifndef QT_NO_DATASTREAM
132 Reads a collection/list item from the stream \a s and returns a reference
135 The default implementation sets \a item to 0.
140 QDataStream &QGList::read( QDataStream &s, QCollection::Item &item )
147 Writes a collection/list item to the stream \a s and returns a reference
150 The default implementation does nothing.
155 QDataStream &QGList::write( QDataStream &s, QCollection::Item ) const
159 #endif // QT_NO_DATASTREAM
161 /*****************************************************************************
162 QGList member functions
163 *****************************************************************************/
167 Constructs an empty list.
172 firstNode = lastNode = curNode = 0; // initialize list
175 iterators = 0; // initialize iterator list
180 Constructs a copy of \e list.
183 QGList::QGList( const QGList & list )
184 : QCollection( list )
186 firstNode = lastNode = curNode = 0; // initialize list
189 iterators = 0; // initialize iterator list
190 QLNode *n = list.firstNode;
191 while ( n ) { // copy all items from list
199 Removes all items from the list and destroys the list.
205 if ( !iterators ) // no iterators for this list
207 QGListIterator *i = (QGListIterator*)iterators->first();
208 while ( i ) { // notify all iterators that
209 i->list = 0; // this list is deleted
211 i = (QGListIterator*)iterators->next();
219 Assigns \e list to this list.
222 QGList& QGList::operator=( const QGList &list )
225 if ( list.count() > 0 ) {
226 QLNode *n = list.firstNode;
227 while ( n ) { // copy all items from list
238 Compares this list with \a list. Returns TRUE if the lists
239 contain the same data, else FALSE.
242 bool QGList::operator==( const QGList &list ) const
244 if ( count() != list.count() )
250 QLNode *n1 = firstNode;
251 QLNode *n2 = list.firstNode;
254 if ( ( (QGList*)this )->compareItems( n1->data, n2->data ) != 0 )
264 \fn uint QGList::count() const
266 Returns the number of items in the list.
272 Returns the node at position \e index. Sets this node to current.
275 QLNode *QGList::locate( uint index )
277 if ( index == (uint)curIndex ) // current node ?
279 if ( !curNode && firstNode ) { // set current node
284 int distance = index - curIndex; // node distance to cur node
285 bool forward; // direction to traverse
287 if ( index >= numNodes ) {
288 #if defined(CHECK_RANGE)
289 qWarning( "QGList::locate: Index %d out of range", index );
295 distance = -distance;
296 if ( (uint)distance < index && (uint)distance < numNodes - index ) {
297 node = curNode; // start from current node
298 forward = index > (uint)curIndex;
299 } else if ( index < numNodes - index ) { // start from first node
303 } else { // start from last node
305 distance = numNodes - index - 1;
310 if ( forward ) { // now run through nodes
317 curIndex = index; // must update index
318 return curNode = node;
324 Inserts an item at its sorted position in the list.
327 void QGList::inSort( QCollection::Item d )
330 QLNode *n = firstNode;
331 while ( n && compareItems(n->data,d) < 0 ){ // find position in list
335 insertAt( index, d );
341 Inserts an item at the start of the list.
344 void QGList::prepend( QCollection::Item d )
346 QLNode *n = new QLNode( newItem(d) );
349 if ( (n->next = firstNode) ) // list is not empty
351 else // initialize list
353 firstNode = curNode = n; // curNode affected
361 Inserts an item at the end of the list.
364 void QGList::append( QCollection::Item d )
366 QLNode *n = new QLNode( newItem(d) );
369 if ( (n->prev = lastNode) ) // list is not empty
371 else // initialize list
373 lastNode = curNode = n; // curNode affected
381 Inserts an item at position \e index in the list.
384 bool QGList::insertAt( uint index, QCollection::Item d )
386 if ( index == 0 ) { // insert at head of list
389 } else if ( index == numNodes ) { // append at tail of list
393 QLNode *nextNode = locate( index );
394 if ( !nextNode ) // illegal position
396 QLNode *prevNode = nextNode->prev;
397 QLNode *n = new QLNode( newItem(d) );
401 n->prev = prevNode; // link new node into list
403 curNode = n; // curIndex set by locate()
411 Relinks node \e n and makes it the first node in the list.
414 void QGList::relinkNode( QLNode *n )
416 if ( n == firstNode ) // already first
421 if ( (n->next = firstNode) ) // list is not empty
423 else // initialize list
425 firstNode = curNode = n; // curNode affected
433 Unlinks the current list node and returns a pointer to this node.
436 QLNode *QGList::unlink()
438 if ( curNode == 0 ) // null current node
440 QLNode *n = curNode; // unlink this node
441 if ( n == firstNode ) { // removing first node ?
442 if ( (firstNode = n->next) ) {
445 lastNode = curNode = 0; // list becomes empty
449 if ( n == lastNode ) { // removing last node ?
452 } else { // neither last nor first node
453 n->prev->next = n->next;
454 n->next->prev = n->prev;
457 if ( n->next ) { // change current node
459 } else if ( n->prev ) {
463 if ( iterators && iterators->count() ) { // update iterators
464 QGListIterator *i = (QGListIterator*)iterators->first();
465 while ( i ) { // fix all iterators that
466 if ( i->curNode == n ) // refers to pending node
467 i->curNode = curNode;
468 i = (QGListIterator*)iterators->next();
478 Removes the node \e n from the list.
481 bool QGList::removeNode( QLNode *n )
483 #if defined(CHECK_NULL)
484 if ( n == 0 || (n->prev && n->prev->next != n) ||
485 (n->next && n->next->prev != n) ) {
486 qWarning( "QGList::removeNode: Corrupted node" );
491 unlink(); // unlink node
492 deleteItem( n->data ); // deallocate this node
495 curIndex = curNode ? 0 : -1;
501 Removes the item \e d from the list. Uses compareItems() to find the item.
504 bool QGList::remove( QCollection::Item d )
506 if ( d ) { // find the item
510 QLNode *n = unlink(); // unlink node
513 deleteItem( n->data ); // deallocate this node
520 Removes the item \e d from the list.
523 bool QGList::removeRef( QCollection::Item d )
525 if ( d ) { // find the item
526 if ( findRef(d) == -1 )
529 QLNode *n = unlink(); // unlink node
532 deleteItem( n->data ); // deallocate this node
538 \fn bool QGList::removeFirst()
540 Removes the first item in the list.
544 \fn bool QGList::removeLast()
546 Removes the last item in the list.
551 Removes the item at position \e index from the list.
554 bool QGList::removeAt( uint index )
556 if ( !locate(index) )
558 QLNode *n = unlink(); // unlink node
561 deleteItem( n->data ); // deallocate this node
569 Takes the node \e n out of the list.
572 QCollection::Item QGList::takeNode( QLNode *n )
574 #if defined(CHECK_NULL)
575 if ( n == 0 || (n->prev && n->prev->next != n) ||
576 (n->next && n->next->prev != n) ) {
577 qWarning( "QGList::takeNode: Corrupted node" );
582 unlink(); // unlink node
584 delete n; // delete the node, not data
586 curIndex = curNode ? 0 : -1;
592 Takes the current item out of the list.
595 QCollection::Item QGList::take()
597 QLNode *n = unlink(); // unlink node
598 Item d = n ? n->data : 0;
599 delete n; // delete node, keep contents
605 Takes the item at position \e index out of the list.
608 QCollection::Item QGList::takeAt( uint index )
610 if ( !locate(index) )
612 QLNode *n = unlink(); // unlink node
613 Item d = n ? n->data : 0;
614 delete n; // delete node, keep contents
620 Takes the first item out of the list.
623 QCollection::Item QGList::takeFirst()
626 QLNode *n = unlink(); // unlink node
627 Item d = n ? n->data : 0;
634 Takes the last item out of the list.
637 QCollection::Item QGList::takeLast()
640 QLNode *n = unlink(); // unlink node
641 Item d = n ? n->data : 0;
649 Removes all items from the list.
654 QLNode *n = firstNode;
656 firstNode = lastNode = curNode = 0; // initialize list
660 if ( iterators && iterators->count() ) {
661 QGListIterator *i = (QGListIterator*)iterators->first();
662 while ( i ) { // notify all iterators that
663 i->curNode = 0; // this list is empty
664 i = (QGListIterator*)iterators->next();
669 while ( n ) { // for all nodes ...
670 deleteItem( n->data ); // deallocate data
673 delete prevNode; // deallocate node
680 Finds an item in the list.
683 int QGList::findRef( QCollection::Item d, bool fromStart )
687 if ( fromStart ) { // start from first node
690 } else { // start from current node
694 while ( n && n->data != d ) { // find exact match
699 curIndex = n ? index : -1;
700 return curIndex; // return position of item
705 Finds an item in the list. Uses compareItems().
708 int QGList::find( QCollection::Item d, bool fromStart )
712 if ( fromStart ) { // start from first node
715 } else { // start from current node
719 while ( n && compareItems(n->data,d) ){ // find equal match
724 curIndex = n ? index : -1;
725 return curIndex; // return position of item
731 Counts the number an item occurs in the list.
734 uint QGList::containsRef( QCollection::Item d ) const
736 QLNode *n = firstNode;
738 while ( n ) { // for all nodes...
739 if ( n->data == d ) // count # exact matches
748 Counts the number an item occurs in the list. Uses compareItems().
751 uint QGList::contains( QCollection::Item d ) const
753 QLNode *n = firstNode;
755 QGList *that = (QGList*)this; // mutable for compareItems()
756 while ( n ) { // for all nodes...
757 if ( !that->compareItems(n->data,d) ) // count # equal matches
766 \fn QCollection::Item QGList::at( uint index )
768 Sets the item at position \e index to the current item.
772 \fn int QGList::at() const
774 Returns the current index.
778 \fn QLNode *QGList::currentNode() const
780 Returns the current node.
784 \fn QCollection::Item QGList::get() const
786 Returns the current item.
790 \fn QCollection::Item QGList::cfirst() const
792 Returns the first item in the list.
796 \fn QCollection::Item QGList::clast() const
798 Returns the last item in the list.
804 Returns the first list item. Sets this to current.
807 QCollection::Item QGList::first()
811 return (curNode=firstNode)->data;
818 Returns the last list item. Sets this to current.
821 QCollection::Item QGList::last()
824 curIndex = numNodes-1;
825 return (curNode=lastNode)->data;
832 Returns the next list item (after current). Sets this to current.
835 QCollection::Item QGList::next()
838 if ( curNode->next ) {
840 curNode = curNode->next;
841 return curNode->data;
851 Returns the previous list item (before current). Sets this to current.
854 QCollection::Item QGList::prev()
857 if ( curNode->prev ) {
859 curNode = curNode->prev;
860 return curNode->data;
871 Converts the list to a vector.
874 void QGList::toVector( QGVector *vector ) const
877 if ( !vector->resize( count() ) )
879 QLNode *n = firstNode;
882 vector->insert( i, n->data );
888 void QGList::heapSortPushDown( QCollection::Item* heap, int first, int last )
891 while( r <= last/2 ) {
892 // Node r has only one child ?
894 // Need for swapping ?
895 if ( compareItems( heap[r], heap[ 2*r ] ) > 0 ) {
896 QCollection::Item tmp = heap[r];
897 heap[ r ] = heap[ 2*r ];
903 // Node has two children
904 if ( compareItems( heap[r], heap[ 2*r ] ) > 0 &&
905 compareItems( heap[ 2*r ], heap[ 2*r+1 ] ) <= 0 ) {
906 // Swap with left child
907 QCollection::Item tmp = heap[r];
908 heap[ r ] = heap[ 2*r ];
911 } else if ( compareItems( heap[r], heap[ 2*r+1 ] ) > 0 &&
912 compareItems( heap[ 2*r+1 ], heap[ 2*r ] ) < 0 ) {
913 // Swap with right child
914 QCollection::Item tmp = heap[r];
915 heap[ r ] = heap[ 2*r+1 ];
927 /*! Sorts the list by the result of the virtual compareItems() function.
929 The Heap-Sort algorithm is used for sorting. It sorts n items with
930 O(n*log n) compares. This is the asymptotic optimal solution of the
941 QCollection::Item* realheap = new QCollection::Item[ n ];
942 // Wow, what a fake. But I want the heap to be indexed as 1...n
943 QCollection::Item* heap = realheap - 1;
945 QLNode* insert = firstNode;
946 for( ; insert != 0; insert = insert->next ) {
947 heap[++size] = insert->data;
949 while( i > 1 && compareItems( heap[i], heap[ i / 2 ] ) < 0 ) {
950 QCollection::Item tmp = heap[ i ];
951 heap[ i ] = heap[ i/2 ];
958 // Now do the sorting
959 for ( int i = n; i > 0; i-- ) {
960 insert->data = heap[1];
961 insert = insert->next;
964 heapSortPushDown( heap, 1, i - 1 );
972 /*****************************************************************************
973 QGList stream functions
974 *****************************************************************************/
976 #ifndef QT_NO_DATASTREAM
977 QDataStream &operator>>( QDataStream &s, QGList &list )
979 return list.read( s );
982 QDataStream &operator<<( QDataStream &s, const QGList &list )
984 return list.write( s );
989 Reads a list from the stream \e s.
992 QDataStream &QGList::read( QDataStream &s )
995 s >> num; // read number of items
996 clear(); // clear list
997 while ( num-- ) { // read all items
1001 if ( !d ) // no memory
1003 QLNode *n = new QLNode( d );
1005 if ( !n ) // no memory
1008 if ( (n->prev = lastNode) ) // list is not empty
1010 else // initialize list
1015 curNode = firstNode;
1016 curIndex = curNode ? 0 : -1;
1022 Writes the list to the stream \e s.
1025 QDataStream &QGList::write( QDataStream &s ) const
1027 s << count(); // write number of items
1028 QLNode *n = firstNode;
1029 while ( n ) { // write all items
1030 write( s, n->data );
1036 #endif // QT_NO_DATASTREAM
1038 /*****************************************************************************
1039 QGListIterator member functions
1040 *****************************************************************************/
1043 \class QGListIterator qglist.h
1044 \brief The QGListIterator class is an internal class for implementing QListIterator.
1046 QGListIterator is a strictly internal class that does the heavy work for
1052 Constructs an iterator that operates on the list \e l.
1055 QGListIterator::QGListIterator( const QGList &l )
1057 list = (QGList *)&l; // get reference to list
1058 curNode = list->firstNode; // set to first node
1059 if ( !list->iterators ) {
1060 list->iterators = new QGList; // create iterator list
1061 CHECK_PTR( list->iterators );
1063 list->iterators->append( this ); // attach iterator to list
1068 Constructs a copy of the iterator \e it.
1071 QGListIterator::QGListIterator( const QGListIterator &it )
1074 curNode = it.curNode;
1076 list->iterators->append( this ); // attach iterator to list
1081 Assigns a copy of the iterator \e it and returns a reference to this
1085 QGListIterator &QGListIterator::operator=( const QGListIterator &it )
1087 if ( list ) // detach from old list
1088 list->iterators->removeRef( this );
1090 curNode = it.curNode;
1092 list->iterators->append( this ); // attach to new list
1098 Destroys the iterator.
1101 QGListIterator::~QGListIterator()
1103 if ( list ) // detach iterator from list
1104 list->iterators->removeRef(this);
1109 \fn bool QGListIterator::atFirst() const
1111 Returns TRUE if the iterator points to the first item, otherwise FALSE.
1115 \fn bool QGListIterator::atLast() const
1117 Returns TRUE if the iterator points to the last item, otherwise FALSE.
1123 Sets the list iterator to point to the first item in the list.
1126 QCollection::Item QGListIterator::toFirst()
1129 #if defined(CHECK_NULL)
1130 qWarning( "QGListIterator::toFirst: List has been deleted" );
1134 return list->firstNode ? (curNode = list->firstNode)->getData() : 0;
1139 Sets the list iterator to point to the last item in the list.
1142 QCollection::Item QGListIterator::toLast()
1145 #if defined(CHECK_NULL)
1146 qWarning( "QGListIterator::toLast: List has been deleted" );
1150 return list->lastNode ? (curNode = list->lastNode)->getData() : 0;
1155 \fn QCollection::Item QGListIterator::get() const
1157 Returns the iterator item.
1163 Moves to the next item (postfix).
1166 QCollection::Item QGListIterator::operator()()
1170 QCollection::Item d = curNode->getData();
1171 curNode = curNode->next;
1177 Moves to the next item (prefix).
1180 QCollection::Item QGListIterator::operator++()
1184 curNode = curNode->next;
1185 return curNode ? curNode->getData() : 0;
1190 Moves \e jumps positions forward.
1193 QCollection::Item QGListIterator::operator+=( uint jumps )
1195 while ( curNode && jumps-- )
1196 curNode = curNode->next;
1197 return curNode ? curNode->getData() : 0;
1202 Moves to the previous item (prefix).
1205 QCollection::Item QGListIterator::operator--()
1209 curNode = curNode->prev;
1210 return curNode ? curNode->getData() : 0;
1215 Moves \e jumps positions backward.
1218 QCollection::Item QGListIterator::operator-=( uint jumps )
1220 while ( curNode && jumps-- )
1221 curNode = curNode->prev;
1222 return curNode ? curNode->getData() : 0;