Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qglist.cpp

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/****************************************************************************
2**
3**
4** Implementation of QGList and QGListIterator classes
5**
6** Created : 920624
7**
8** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
9**
10** This file is part of the tools module of the Qt GUI Toolkit.
11**
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.
15**
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.
20**
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.
24**
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.
27**
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.
32**
33** Contact info@trolltech.com if any conditions of this licensing are
34** not clear to you.
35**
36**********************************************************************/
37
38#include "qglist.h"
39#include "qgvector.h"
40#include "qdatastream.h"
41
42
43// NOT REVISED
44/*!
45 \class QLNode qglist.h
46 \brief The QLNode class is an internal class for the QList template collection.
47
48 QLNode is a doubly linked list node; it has three pointers:
49 <ol>
50 <li> Pointer to the previous node.
51 <li> Pointer to the next node.
52 <li> Pointer to the actual data.
53 </ol>
54
55 Sometimes it might be practical to have direct access to the list nodes
56 in a QList, but it is seldom required.
57
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.
60
61 \sa QList::currentNode(), QList::removeNode(), QList::takeNode()
62*/
63
64/*!
65 \fn QCollection::Item QLNode::getData()
66 Returns a pointer (\c void*) to the actual data in the list node.
67*/
68
69
70/*!
71 \class QGList qglist.h
72 \brief The QGList class is an internal class for implementing Qt collection classes.
73
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
76 QStack.
77
78 QGList has some virtual functions that can be reimplemented to customize
79 the subclasses.
80 <ul>
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.
84 </ul>
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.
88*/
89
90
91/*****************************************************************************
92 Default implementation of virtual functions
93 *****************************************************************************/
94
95/*!
96 This virtual function compares two list items.
97
98 Returns:
99 <ul>
100 <li> 0 if \e item1 == \e item2
101 <li> non-zero if \e item1 != \e item2
102 </ul>
103
104 This function returns \e int rather than \e bool so that
105 reimplementations can return three values and use it to sort by:
106
107 <ul>
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
111 </ul>
112
113 The QList::inSort() function requires that compareItems() is implemented
114 as described here.
115
116 This function should not modify the list because some const functions
117 call compareItems().
118
119 The default implementation compares the pointers:
120 \code
121
122 \endcode
123*/
124
125int QGList::compareItems( QCollection::Item item1, QCollection::Item item2 )
126{
127 return item1 != item2;// compare pointers
128}
129
130#ifndef QT_NO_DATASTREAM
131/*!
132 Reads a collection/list item from the stream \a s and returns a reference
133 to the stream.
134
135 The default implementation sets \a item to 0.
136
137 \sa write()
138*/
139
140QDataStream &QGList::read( QDataStream &s, QCollection::Item &item )
141{
142 item = 0;
143 return s;
144}
145
146/*!
147 Writes a collection/list item to the stream \a s and returns a reference
148 to the stream.
149
150 The default implementation does nothing.
151
152 \sa read()
153*/
154
155QDataStream &QGList::write( QDataStream &s, QCollection::Item ) const
156{
157 return s;
158}
159#endif // QT_NO_DATASTREAM
160
161/*****************************************************************************
162 QGList member functions
163 *****************************************************************************/
164
165/*!
166 \internal
167 Constructs an empty list.
168*/
169
170QGList::QGList()
171{
172 firstNode = lastNode = curNode = 0;// initialize list
173 numNodes = 0;
174 curIndex = -1;
175 iterators = 0;// initialize iterator list
176}
177
178/*!
179 \internal
180 Constructs a copy of \e list.
181*/
182
183QGList::QGList( const QGList & list )
184 : QCollection( list )
185{
186 firstNode = lastNode = curNode = 0;// initialize list
187 numNodes = 0;
188 curIndex = -1;
189 iterators = 0;// initialize iterator list
190 QLNode *n = list.firstNode;
191 while ( n ) {// copy all items from list
192append( n->data );
193n = n->next;
194 }
195}
196
197/*!
198 \internal
199 Removes all items from the list and destroys the list.
200*/
201
202QGList::~QGList()
203{
204 clear();
205 if ( !iterators )// no iterators for this list
206return;
207 QGListIterator *i = (QGListIterator*)iterators->first();
208 while ( i ) {// notify all iterators that
209i->list = 0;// this list is deleted
210i->curNode = 0;
211i = (QGListIterator*)iterators->next();
212 }
213 delete iterators;
214}
215
216
217/*!
218 \internal
219 Assigns \e list to this list.
220*/
221
222QGList& QGList::operator=( const QGList &list )
223{
224 clear();
225 if ( list.count() > 0 ) {
226QLNode *n = list.firstNode;
227while ( n ) {// copy all items from list
228 append( n->data );
229 n = n->next;
230}
231curNode = firstNode;
232curIndex = 0;
233 }
234 return *this;
235}
236
237/*!
238 Compares this list with \a list. Retruns TRUE if the lists
239 contain the same data, else FALSE.
240*/
241
242bool QGList::operator==( const QGList &list ) const
243{
244 if ( count() != list.count() )
245return FALSE;
246
247 if ( count() == 0 )
248return TRUE;
249
250 QLNode *n1 = firstNode;
251 QLNode *n2 = list.firstNode;
252 while ( n1 && n2 ) {
253// should be mutable
254if ( ( (QGList*)this )->compareItems( n1->data, n2->data ) != 0 )
255 return FALSE;
256n1 = n1->next;
257n2 = n2->next;
258 }
259
260 return TRUE;
261}
262
263/*!
264 \fn uint QGList::count() const
265 \internal
266 Returns the number of items in the list.
267*/
268
269
270/*!
271 \internal
272 Returns the node at position \e index. Sets this node to current.
273*/
274
275QLNode *QGList::locate( uint index )
276{
277 if ( index == (uint)curIndex )// current node ?
278return curNode;
279 if ( !curNode && firstNode ) {// set current node
280curNode = firstNode;
281curIndex = 0;
282 }
283 register QLNode *node;
284 int distance = index - curIndex;// node distance to cur node
285 bool forward;// direction to traverse
286
287 if ( index >= numNodes ) {
288#if defined(CHECK_RANGE)
289qWarning( "QGList::locate: Index %d out of range", index );
290#endif
291return 0;
292 }
293
294 if ( distance < 0 )
295distance = -distance;
296 if ( (uint)distance < index && (uint)distance < numNodes - index ) {
297node =curNode;// start from current node
298forward = index > (uint)curIndex;
299 } else if ( index < numNodes - index ) {// start from first node
300node = firstNode;
301distance = index;
302forward = TRUE;
303 } else {// start from last node
304node = lastNode;
305distance = numNodes - index - 1;
306if ( distance < 0 )
307 distance = 0;
308forward = FALSE;
309 }
310 if ( forward ) {// now run through nodes
311while ( distance-- )
312 node = node->next;
313 } else {
314while ( distance-- )
315 node = node->prev;
316 }
317 curIndex = index;// must update index
318 return curNode = node;
319}
320
321
322/*!
323 \internal
324 Inserts an item at its sorted position in the list.
325*/
326
327void QGList::inSort( QCollection::Item d )
328{
329 int index = 0;
330 register QLNode *n = firstNode;
331 while ( n && compareItems(n->data,d) < 0 ){ // find position in list
332n = n->next;
333index++;
334 }
335 insertAt( index, d );
336}
337
338
339/*!
340 \internal
341 Inserts an item at the start of the list.
342*/
343
344void QGList::prepend( QCollection::Item d )
345{
346 register QLNode *n = new QLNode( newItem(d) );
347 CHECK_PTR( n );
348 n->prev = 0;
349 if ( (n->next = firstNode) )// list is not empty
350firstNode->prev = n;
351 else// initialize list
352lastNode = n;
353 firstNode = curNode = n;// curNode affected
354 numNodes++;
355 curIndex = 0;
356}
357
358
359/*!
360 \internal
361 Inserts an item at the end of the list.
362*/
363
364void QGList::append( QCollection::Item d )
365{
366 register QLNode *n = new QLNode( newItem(d) );
367 CHECK_PTR( n );
368 n->next = 0;
369 if ( (n->prev = lastNode) )// list is not empty
370lastNode->next = n;
371 else// initialize list
372firstNode = n;
373 lastNode = curNode = n;// curNode affected
374 curIndex = numNodes;
375 numNodes++;
376}
377
378
379/*!
380 \internal
381 Inserts an item at position \e index in the list.
382*/
383
384bool QGList::insertAt( uint index, QCollection::Item d )
385{
386 if ( index == 0 ) {// insert at head of list
387prepend( d );
388return TRUE;
389 } else if ( index == numNodes ) {// append at tail of list
390append( d );
391return TRUE;
392 }
393 QLNode *nextNode = locate( index );
394 if ( !nextNode )// illegal position
395return FALSE;
396 QLNode *prevNode = nextNode->prev;
397 register QLNode *n = new QLNode( newItem(d) );
398 CHECK_PTR( n );
399 nextNode->prev = n;
400 prevNode->next = n;
401 n->prev = prevNode;// link new node into list
402 n->next = nextNode;
403 curNode = n;// curIndex set by locate()
404 numNodes++;
405 return TRUE;
406}
407
408
409/*!
410 \internal
411 Relinks node \e n and makes it the first node in the list.
412*/
413
414void QGList::relinkNode( QLNode *n )
415{
416 if ( n == firstNode )// already first
417return;
418 curNode = n;
419 unlink();
420 n->prev = 0;
421 if ( (n->next = firstNode) )// list is not empty
422firstNode->prev = n;
423 else// initialize list
424lastNode = n;
425 firstNode = curNode = n;// curNode affected
426 numNodes++;
427 curIndex = 0;
428}
429
430
431/*!
432 \internal
433 Unlinks the current list node and returns a pointer to this node.
434*/
435
436QLNode *QGList::unlink()
437{
438 if ( curNode == 0 )// null current node
439return 0;
440 register QLNode *n = curNode;// unlink this node
441 if ( n == firstNode ) {// removing first node ?
442if ( (firstNode = n->next) ) {
443 firstNode->prev = 0;
444} else {
445 lastNode = curNode = 0;// list becomes empty
446 curIndex = -1;
447}
448 } else {
449if ( n == lastNode ) {// removing last node ?
450 lastNode = n->prev;
451 lastNode->next = 0;
452} else {// neither last nor first node
453 n->prev->next = n->next;
454 n->next->prev = n->prev;
455}
456 }
457 if ( n->next ) {// change current node
458curNode = n->next;
459 } else if ( n->prev ) {
460curNode = n->prev;
461curIndex--;
462 }
463 if ( iterators && iterators->count() ) {// update iterators
464QGListIterator *i = (QGListIterator*)iterators->first();
465while ( i ) {// fix all iterators that
466 if ( i->curNode == n )// refers to pending node
467i->curNode = curNode;
468 i = (QGListIterator*)iterators->next();
469}
470 }
471 numNodes--;
472 return n;
473}
474
475
476/*!
477 \internal
478 Removes the node \e n from the list.
479*/
480
481bool QGList::removeNode( QLNode *n )
482{
483#if defined(CHECK_NULL)
484 if ( n == 0 || (n->prev && n->prev->next != n) ||
485 (n->next && n->next->prev != n) ) {
486qWarning( "QGList::removeNode: Corrupted node" );
487return FALSE;
488 }
489#endif
490 curNode = n;
491 unlink();// unlink node
492 deleteItem( n->data );// deallocate this node
493 delete n;
494 curNode = firstNode;
495 curIndex = curNode ? 0 : -1;
496 return TRUE;
497}
498
499/*!
500 \internal
501 Removes the item \e d from the list.Uses compareItems() to find the item.
502*/
503
504bool QGList::remove( QCollection::Item d )
505{
506 if ( d ) {// find the item
507if ( find(d) == -1 )
508 return FALSE;
509 }
510 QLNode *n = unlink();// unlink node
511 if ( !n )
512return FALSE;
513 deleteItem( n->data );// deallocate this node
514 delete n;
515 return TRUE;
516}
517
518/*!
519 \internal
520 Removes the item \e d from the list.
521*/
522
523bool QGList::removeRef( QCollection::Item d )
524{
525 if ( d ) {// find the item
526if ( findRef(d) == -1 )
527 return FALSE;
528 }
529 QLNode *n = unlink();// unlink node
530 if ( !n )
531return FALSE;
532 deleteItem( n->data );// deallocate this node
533 delete n;
534 return TRUE;
535}
536
537/*!
538 \fn bool QGList::removeFirst()
539 \internal
540 Removes the first item in the list.
541*/
542
543/*!
544 \fn bool QGList::removeLast()
545 \internal
546 Removes the last item in the list.
547*/
548
549/*!
550 \internal
551 Removes the item at position \e index from the list.
552*/
553
554bool QGList::removeAt( uint index )
555{
556 if ( !locate(index) )
557return FALSE;
558 QLNode *n = unlink();// unlink node
559 if ( !n )
560return FALSE;
561 deleteItem( n->data );// deallocate this node
562 delete n;
563 return TRUE;
564}
565
566
567/*!
568 \internal
569 Takes the node \e n out of the list.
570*/
571
572QCollection::Item QGList::takeNode( QLNode *n )
573{
574#if defined(CHECK_NULL)
575 if ( n == 0 || (n->prev && n->prev->next != n) ||
576 (n->next && n->next->prev != n) ) {
577qWarning( "QGList::takeNode: Corrupted node" );
578return 0;
579 }
580#endif
581 curNode = n;
582 unlink();// unlink node
583 Item d = n->data;
584 delete n;// delete the node, not data
585 curNode = firstNode;
586 curIndex = curNode ? 0 : -1;
587 return d;
588}
589
590/*!
591 \internal
592 Takes the current item out of the list.
593*/
594
595QCollection::Item QGList::take()
596{
597 QLNode *n = unlink();// unlink node
598 Item d = n ? n->data : 0;
599 delete n;// delete node, keep contents
600 return d;
601}
602
603/*!
604 \internal
605 Takes the item at position \e index out of the list.
606*/
607
608QCollection::Item QGList::takeAt( uint index )
609{
610 if ( !locate(index) )
611return 0;
612 QLNode *n = unlink();// unlink node
613 Item d = n ? n->data : 0;
614 delete n;// delete node, keep contents
615 return d;
616}
617
618/*!
619 \internal
620 Takes the first item out of the list.
621*/
622
623QCollection::Item QGList::takeFirst()
624{
625 first();
626 QLNode *n = unlink();// unlink node
627 Item d = n ? n->data : 0;
628 delete n;
629 return d;
630}
631
632/*!
633 \internal
634 Takes the last item out of the list.
635*/
636
637QCollection::Item QGList::takeLast()
638{
639 last();
640 QLNode *n = unlink();// unlink node
641 Item d = n ? n->data : 0;
642 delete n;
643 return d;
644}
645
646
647/*!
648 \internal
649 Removes all items from the list.
650*/
651
652void QGList::clear()
653{
654 register QLNode *n = firstNode;
655
656 firstNode = lastNode = curNode = 0;// initialize list
657 numNodes = 0;
658 curIndex = -1;
659
660 if ( iterators && iterators->count() ) {
661QGListIterator *i = (QGListIterator*)iterators->first();
662while ( i ) {// notify all iterators that
663 i->curNode = 0;// this list is empty
664 i = (QGListIterator*)iterators->next();
665}
666 }
667
668 QLNode *prevNode;
669 while ( n ) {// for all nodes ...
670deleteItem( n->data );// deallocate data
671prevNode = n;
672n = n->next;
673delete prevNode;// deallocate node
674 }
675}
676
677
678/*!
679 \internal
680 Finds an item in the list.
681*/
682
683int QGList::findRef( QCollection::Item d, bool fromStart )
684{
685 register QLNode *n;
686 int index;
687 if ( fromStart ) {// start from first node
688n = firstNode;
689index = 0;
690 } else {// start from current node
691n = curNode;
692index = curIndex;
693 }
694 while ( n && n->data != d ) {// find exact match
695n = n->next;
696index++;
697 }
698 curNode = n;
699 curIndex = n ? index : -1;
700 return curIndex;// return position of item
701}
702
703/*!
704 \internal
705 Finds an item in the list. Uses compareItems().
706*/
707
708int QGList::find( QCollection::Item d, bool fromStart )
709{
710 register QLNode *n;
711 int index;
712 if ( fromStart ) {// start from first node
713n = firstNode;
714index = 0;
715 } else {// start from current node
716n = curNode;
717index = curIndex;
718 }
719 while ( n && compareItems(n->data,d) ){// find equal match
720n = n->next;
721index++;
722 }
723 curNode = n;
724 curIndex = n ? index : -1;
725 return curIndex;// return position of item
726}
727
728
729/*!
730 \internal
731 Counts the number an item occurs in the list.
732*/
733
734uint QGList::containsRef( QCollection::Item d ) const
735{
736 register QLNode *n = firstNode;
737 uint count = 0;
738 while ( n ) {// for all nodes...
739if ( n->data == d )// count # exact matches
740 count++;
741n = n->next;
742 }
743 return count;
744}
745
746/*!
747 \internal
748 Counts the number an item occurs in the list. Uses compareItems().
749*/
750
751uint QGList::contains( QCollection::Item d ) const
752{
753 register QLNode *n = firstNode;
754 uint count = 0;
755 QGList *that = (QGList*)this;// mutable for compareItems()
756 while ( n ) {// for all nodes...
757if ( !that->compareItems(n->data,d) )// count # equal matches
758 count++;
759n = n->next;
760 }
761 return count;
762}
763
764
765/*!
766 \fn QCollection::Item QGList::at( uint index )
767 \internal
768 Sets the item at position \e index to the current item.
769*/
770
771/*!
772 \fn int QGList::at() const
773 \internal
774 Returns the current index.
775*/
776
777/*!
778 \fn QLNode *QGList::currentNode() const
779 \internal
780 Returns the current node.
781*/
782
783/*!
784 \fn QCollection::Item QGList::get() const
785 \internal
786 Returns the current item.
787*/
788
789/*!
790 \fn QCollection::Item QGList::cfirst() const
791 \internal
792 Returns the first item in the list.
793*/
794
795/*!
796 \fn QCollection::Item QGList::clast() const
797 \internal
798 Returns the last item in the list.
799*/
800
801
802/*!
803 \internal
804 Returns the first list item.Sets this to current.
805*/
806
807QCollection::Item QGList::first()
808{
809 if ( firstNode ) {
810curIndex = 0;
811return (curNode=firstNode)->data;
812 }
813 return 0;
814}
815
816/*!
817 \internal
818 Returns the last list item. Sets this to current.
819*/
820
821QCollection::Item QGList::last()
822{
823 if ( lastNode ) {
824curIndex = numNodes-1;
825return (curNode=lastNode)->data;
826 }
827 return 0;
828}
829
830/*!
831 \internal
832 Returns the next list item (after current). Sets this to current.
833*/
834
835QCollection::Item QGList::next()
836{
837 if ( curNode ) {
838if ( curNode->next ) {
839 curIndex++;
840 curNode = curNode->next;
841 return curNode->data;
842}
843curIndex = -1;
844curNode = 0;
845 }
846 return 0;
847}
848
849/*!
850 \internal
851 Returns the previous list item (before current). Sets this to current.
852*/
853
854QCollection::Item QGList::prev()
855{
856 if ( curNode ) {
857if ( curNode->prev ) {
858 curIndex--;
859 curNode = curNode->prev;
860 return curNode->data;
861}
862curIndex = -1;
863curNode = 0;
864 }
865 return 0;
866}
867
868
869/*!
870 \internal
871 Converts the list to a vector.
872*/
873
874void QGList::toVector( QGVector *vector ) const
875{
876 vector->clear();
877 if ( !vector->resize( count() ) )
878return;
879 register QLNode *n = firstNode;
880 uint i = 0;
881 while ( n ) {
882vector->insert( i, n->data );
883n = n->next;
884i++;
885 }
886}
887
888void QGList::heapSortPushDown( QCollection::Item* heap, int first, int last )
889{
890 int r = first;
891 while( r <= last/2 ) {
892// Node r has only one child ?
893if ( last == 2*r ) {
894 // Need for swapping ?
895 if ( compareItems( heap[r], heap[ 2*r ] ) > 0 ) {
896QCollection::Item tmp = heap[r];
897heap[ r ] = heap[ 2*r ];
898heap[ 2*r ] = tmp;
899 }
900 // That's it ...
901 r = last;
902} else {
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
907QCollection::Item tmp = heap[r];
908heap[ r ] = heap[ 2*r ];
909heap[ 2*r ] = tmp;
910r *= 2;
911 } else if ( compareItems( heap[r], heap[ 2*r+1 ] ) > 0 &&
912compareItems( heap[ 2*r+1 ], heap[ 2*r ] ) < 0 ) {
913// Swap with right child
914QCollection::Item tmp = heap[r];
915heap[ r ] = heap[ 2*r+1 ];
916heap[ 2*r+1 ] = tmp;
917r = 2*r+1;
918 } else {
919// We are done
920r = last;
921 }
922}
923 }
924}
925
926
927/*! Sorts the list by the result of the virtual compareItems() function.
928
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
931 sorting problem.
932*/
933
934void QGList::sort()
935{
936 uint n = count();
937 if ( n < 2 )
938return;
939
940 // Create the heap
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;
944 int size = 0;
945 QLNode* insert = firstNode;
946 for( ; insert != 0; insert = insert->next ) {
947heap[++size] = insert->data;
948int i = size;
949while( i > 1 && compareItems( heap[i], heap[ i / 2 ] ) < 0 ) {
950 QCollection::Item tmp = heap[ i ];
951 heap[ i ] = heap[ i/2 ];
952 heap[ i/2 ] = tmp;
953 i /= 2;
954}
955 }
956
957 insert = firstNode;
958 // Now do the sorting
959 for ( int i = n; i > 0; i-- ) {
960insert->data = heap[1];
961insert = insert->next;
962if ( i > 1 ) {
963 heap[1] = heap[i];
964 heapSortPushDown( heap, 1, i - 1 );
965}
966 }
967
968 delete [] realheap;
969}
970
971
972/*****************************************************************************
973 QGList stream functions
974 *****************************************************************************/
975
976#ifndef QT_NO_DATASTREAM
977QDataStream &operator>>( QDataStream &s, QGList &list )
978{// read list
979 return list.read( s );
980}
981
982QDataStream &operator<<( QDataStream &s, const QGList &list )
983{// write list
984 return list.write( s );
985}
986
987/*!
988 \internal
989 Reads a list from the stream \e s.
990*/
991
992QDataStream &QGList::read( QDataStream &s )
993{
994 uint num;
995 s >> num;// read number of items
996 clear();// clear list
997 while ( num-- ) {// read all items
998Item d;
999read( s, d );
1000CHECK_PTR( d );
1001if ( !d )// no memory
1002 break;
1003QLNode *n = new QLNode( d );
1004CHECK_PTR( n );
1005if ( !n )// no memory
1006 break;
1007n->next = 0;
1008if ( (n->prev = lastNode) )// list is not empty
1009 lastNode->next = n;
1010else// initialize list
1011 firstNode = n;
1012lastNode = n;
1013numNodes++;
1014 }
1015 curNode = firstNode;
1016 curIndex = curNode ? 0 : -1;
1017 return s;
1018}
1019
1020/*!
1021 \internal
1022 Writes the list to the stream \e s.
1023*/
1024
1025QDataStream &QGList::write( QDataStream &s ) const
1026{
1027 s << count();// write number of items
1028 QLNode *n = firstNode;
1029 while ( n ) {// write all items
1030write( s, n->data );
1031n = n->next;
1032 }
1033 return s;
1034}
1035
1036#endif // QT_NO_DATASTREAM
1037
1038/*****************************************************************************
1039 QGListIterator member functions
1040 *****************************************************************************/
1041
1042/*!
1043 \class QGListIterator qglist.h
1044 \brief The QGListIterator class is an internal class for implementing QListIterator.
1045
1046 QGListIterator is a strictly internal class that does the heavy work for
1047 QListIterator.
1048*/
1049
1050/*!
1051 \internal
1052 Constructs an iterator that operates on the list \e l.
1053*/
1054
1055QGListIterator::QGListIterator( const QGList &l )
1056{
1057 list = (QGList *)&l;// get reference to list
1058 curNode = list->firstNode;// set to first node
1059 if ( !list->iterators ) {
1060list->iterators = new QGList;// create iterator list
1061CHECK_PTR( list->iterators );
1062 }
1063 list->iterators->append( this );// attach iterator to list
1064}
1065
1066/*!
1067 \internal
1068 Constructs a copy of the iterator \e it.
1069*/
1070
1071QGListIterator::QGListIterator( const QGListIterator &it )
1072{
1073 list = it.list;
1074 curNode = it.curNode;
1075 if ( list )
1076list->iterators->append( this );// attach iterator to list
1077}
1078
1079/*!
1080 \internal
1081 Assigns a copy of the iterator \e it and returns a reference to this
1082 iterator.
1083*/
1084
1085QGListIterator &QGListIterator::operator=( const QGListIterator &it )
1086{
1087 if ( list )// detach from old list
1088list->iterators->removeRef( this );
1089 list = it.list;
1090 curNode = it.curNode;
1091 if ( list )
1092list->iterators->append( this );// attach to new list
1093 return *this;
1094}
1095
1096/*!
1097 \internal
1098 Destroys the iterator.
1099*/
1100
1101QGListIterator::~QGListIterator()
1102{
1103 if ( list )// detach iterator from list
1104list->iterators->removeRef(this);
1105}
1106
1107
1108/*!
1109 \fn bool QGListIterator::atFirst() const
1110 \internal
1111 Returns TRUE if the iterator points to the first item, otherwise FALSE.
1112*/
1113
1114/*!
1115 \fn bool QGListIterator::atLast() const
1116 \internal
1117 Returns TRUE if the iterator points to the last item, otherwise FALSE.
1118*/
1119
1120
1121/*!
1122 \internal
1123 Sets the list iterator to point to the first item in the list.
1124*/
1125
1126QCollection::Item QGListIterator::toFirst()
1127{
1128 if ( !list ) {
1129#if defined(CHECK_NULL)
1130qWarning( "QGListIterator::toFirst: List has been deleted" );
1131#endif
1132return 0;
1133 }
1134 return list->firstNode ? (curNode = list->firstNode)->getData() : 0;
1135}
1136
1137/*!
1138 \internal
1139 Sets the list iterator to point to the last item in the list.
1140*/
1141
1142QCollection::Item QGListIterator::toLast()
1143{
1144 if ( !list ) {
1145#if defined(CHECK_NULL)
1146qWarning( "QGListIterator::toLast: List has been deleted" );
1147#endif
1148return 0;
1149 }
1150 return list->lastNode ? (curNode = list->lastNode)->getData() : 0;
1151}
1152
1153
1154/*!
1155 \fn QCollection::Item QGListIterator::get() const
1156 \internal
1157 Returns the iterator item.
1158*/
1159
1160
1161/*!
1162 \internal
1163 Moves to the next item (postfix).
1164*/
1165
1166QCollection::Item QGListIterator::operator()()
1167{
1168 if ( !curNode )
1169return 0;
1170 QCollection::Item d = curNode->getData();
1171 curNode = curNode->next;
1172 return d;
1173}
1174
1175/*!
1176 \internal
1177 Moves to the next item (prefix).
1178*/
1179
1180QCollection::Item QGListIterator::operator++()
1181{
1182 if ( !curNode )
1183return 0;
1184 curNode = curNode->next;
1185 return curNode ? curNode->getData() : 0;
1186}
1187
1188/*!
1189 \internal
1190 Moves \e jumps positions forward.
1191*/
1192
1193QCollection::Item QGListIterator::operator+=( uint jumps )
1194{
1195 while ( curNode && jumps-- )
1196curNode = curNode->next;
1197 return curNode ? curNode->getData() : 0;
1198}
1199
1200/*!
1201 \internal
1202 Moves to the previous item (prefix).
1203*/
1204
1205QCollection::Item QGListIterator::operator--()
1206{
1207 if ( !curNode )
1208return 0;
1209 curNode = curNode->prev;
1210 return curNode ? curNode->getData() : 0;
1211}
1212
1213/*!
1214 \internal
1215 Moves \e jumps positions backward.
1216*/
1217
1218QCollection::Item QGListIterator::operator-=( uint jumps )
1219{
1220 while ( curNode && jumps-- )
1221curNode = curNode->prev;
1222 return curNode ? curNode->getData() : 0;
1223}
1224

Archive Download this file

Revision: 1322