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