Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 12 years 8 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␊
192␉append( n->data );␊
193␉n = 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␊
206␉return;␊
207 QGListIterator *i = (QGListIterator*)iterators->first();␊
208 while ( i ) {␉␉␉␉// notify all iterators that␊
209␉i->list = 0;␉␉␉␉// this list is deleted␊
210␉i->curNode = 0;␊
211␉i = (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 ) {␊
226␉QLNode *n = list.firstNode;␊
227␉while ( n ) {␉␉␉␉// copy all items from list␊
228␉ append( n->data );␊
229␉ n = n->next;␊
230␉}␊
231␉curNode␉ = firstNode;␊
232␉curIndex = 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() )␊
245␉return FALSE;␊
246 ␊
247 if ( count() == 0 )␊
248␉return TRUE;␊
249 ␊
250 QLNode *n1 = firstNode;␊
251 QLNode *n2 = list.firstNode;␊
252 while ( n1 && n2 ) {␊
253␉// should be mutable␊
254␉if ( ( (QGList*)this )->compareItems( n1->data, n2->data ) != 0 )␊
255␉ return FALSE;␊
256␉n1 = n1->next;␊
257␉n2 = 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 ?␊
278␉return curNode;␊
279 if ( !curNode && firstNode ) {␉␉// set current node␊
280␉curNode␉ = firstNode;␊
281␉curIndex = 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)␊
289␉qWarning( "QGList::locate: Index %d out of range", index );␊
290#endif␊
291␉return 0;␊
292 }␊
293␊
294 if ( distance < 0 )␊
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␊
300␉node = firstNode;␊
301␉distance = index;␊
302␉forward = TRUE;␊
303 } else {␉␉␉␉␉// start from last node␊
304␉node = lastNode;␊
305␉distance = numNodes - index - 1;␊
306␉if ( distance < 0 )␊
307␉ distance = 0;␊
308␉forward = FALSE;␊
309 }␊
310 if ( forward ) {␉␉␉␉// now run through nodes␊
311␉while ( distance-- )␊
312␉ node = node->next;␊
313 } else {␊
314␉while ( 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␊
332␉n = n->next;␊
333␉index++;␊
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␊
350␉firstNode->prev = n;␊
351 else␉␉␉␉␉// initialize list␊
352␉lastNode = 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␊
370␉lastNode->next = n;␊
371 else␉␉␉␉␉// initialize list␊
372␉firstNode = 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␊
387␉prepend( d );␊
388␉return TRUE;␊
389 } else if ( index == numNodes ) {␉␉// append at tail of list␊
390␉append( d );␊
391␉return TRUE;␊
392 }␊
393 QLNode *nextNode = locate( index );␊
394 if ( !nextNode )␉␉␉␉// illegal position␊
395␉return 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␊
417␉return;␊
418 curNode = n;␊
419 unlink();␊
420 n->prev = 0;␊
421 if ( (n->next = firstNode) )␉␉// list is not empty␊
422␉firstNode->prev = n;␊
423 else␉␉␉␉␉// initialize list␊
424␉lastNode = 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␊
439␉return 0;␊
440 register QLNode *n = curNode;␉␉// unlink this node␊
441 if ( n == firstNode ) {␉␉␉// removing first node ?␊
442␉if ( (firstNode = n->next) ) {␊
443␉ firstNode->prev = 0;␊
444␉} else {␊
445␉ lastNode = curNode = 0;␉␉// list becomes empty␊
446␉ curIndex = -1;␊
447␉}␊
448 } else {␊
449␉if ( 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␊
458␉curNode = n->next;␊
459 } else if ( n->prev ) {␊
460␉curNode = n->prev;␊
461␉curIndex--;␊
462 }␊
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();␊
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) ) {␊
486␉qWarning( "QGList::removeNode: Corrupted node" );␊
487␉return 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␊
507␉if ( find(d) == -1 )␊
508␉ return FALSE;␊
509 }␊
510 QLNode *n = unlink();␉␉␉// unlink node␊
511 if ( !n )␊
512␉return 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␊
526␉if ( findRef(d) == -1 )␊
527␉ return FALSE;␊
528 }␊
529 QLNode *n = unlink();␉␉␉// unlink node␊
530 if ( !n )␊
531␉return 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) )␊
557␉return FALSE;␊
558 QLNode *n = unlink();␉␉␉// unlink node␊
559 if ( !n )␊
560␉return 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) ) {␊
577␉qWarning( "QGList::takeNode: Corrupted node" );␊
578␉return 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) )␊
611␉return 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() ) {␊
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();␊
665␉}␊
666 }␊
667␊
668 QLNode *prevNode;␊
669 while ( n ) {␉␉␉␉// for all nodes ...␊
670␉deleteItem( n->data );␉␉␉// deallocate data␊
671␉prevNode = n;␊
672␉n = n->next;␊
673␉delete 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␊
688␉n = firstNode;␊
689␉index = 0;␊
690 } else {␉␉␉␉␉// start from current node␊
691␉n = curNode;␊
692␉index = curIndex;␊
693 }␊
694 while ( n && n->data != d ) {␉␉// find exact match␊
695␉n = n->next;␊
696␉index++;␊
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␊
713␉n = firstNode;␊
714␉index = 0;␊
715 } else {␉␉␉␉␉// start from current node␊
716␉n = curNode;␊
717␉index = curIndex;␊
718 }␊
719 while ( n && compareItems(n->data,d) ){␉// find equal match␊
720␉n = n->next;␊
721␉index++;␊
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...␊
739␉if ( n->data == d )␉␉␉// count # exact matches␊
740␉ count++;␊
741␉n = 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...␊
757␉if ( !that->compareItems(n->data,d) )␉// count # equal matches␊
758␉ count++;␊
759␉n = 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 ) {␊
810␉curIndex = 0;␊
811␉return (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 ) {␊
824␉curIndex = numNodes-1;␊
825␉return (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 ) {␊
838␉if ( curNode->next ) {␊
839␉ curIndex++;␊
840␉ curNode = curNode->next;␊
841␉ return curNode->data;␊
842␉}␊
843␉curIndex = -1;␊
844␉curNode = 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 ) {␊
857␉if ( curNode->prev ) {␊
858␉ curIndex--;␊
859␉ curNode = curNode->prev;␊
860␉ return curNode->data;␊
861␉}␊
862␉curIndex = -1;␊
863␉curNode = 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() ) )␊
878␉return;␊
879 register QLNode *n = firstNode;␊
880 uint i = 0;␊
881 while ( n ) {␊
882␉vector->insert( i, n->data );␊
883␉n = n->next;␊
884␉i++;␊
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 ?␊
893␉if ( last == 2*r ) {␊
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 ];␊
898␉␉heap[ 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␊
907␉␉QCollection::Item tmp = heap[r];␊
908␉␉heap[ r ] = heap[ 2*r ];␊
909␉␉heap[ 2*r ] = tmp;␊
910␉␉r *= 2;␊
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 ];␊
916␉␉heap[ 2*r+1 ] = tmp;␊
917␉␉r = 2*r+1;␊
918␉ } else {␊
919␉␉// We are done␊
920␉␉r = 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 )␊
938␉return;␊
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 ) {␊
947␉heap[++size] = insert->data;␊
948␉int i = size;␊
949␉while( 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-- ) {␊
960␉insert->data = heap[1];␊
961␉insert = insert->next;␊
962␉if ( 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␊
998␉Item d;␊
999␉read( s, d );␊
1000␉CHECK_PTR( d );␊
1001␉if ( !d )␉␉␉␉// no memory␊
1002␉ break;␊
1003␉QLNode *n = new QLNode( d );␊
1004␉CHECK_PTR( n );␊
1005␉if ( !n )␉␉␉␉// no memory␊
1006␉ break;␊
1007␉n->next = 0;␊
1008␉if ( (n->prev = lastNode) )␉␉// list is not empty␊
1009␉ lastNode->next = n;␊
1010␉else␉␉␉␉␉// initialize list␊
1011␉ firstNode = n;␊
1012␉lastNode = n;␊
1013␉numNodes++;␊
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␊
1030␉write( s, n->data );␊
1031␉n = 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 ) {␊
1060␉list->iterators = new QGList;␉␉// create iterator list␊
1061␉CHECK_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 )␊
1076␉list->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␊
1088␉list->iterators->removeRef( this );␊
1089 list = it.list;␊
1090 curNode = it.curNode;␊
1091 if ( list )␊
1092␉list->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␊
1104␉list->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)␊
1130␉qWarning( "QGListIterator::toFirst: List has been deleted" );␊
1131#endif␊
1132␉return 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)␊
1146␉qWarning( "QGListIterator::toLast: List has been deleted" );␊
1147#endif␊
1148␉return 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 )␊
1169␉return 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 )␊
1183␉return 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-- )␊
1196␉curNode = 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 )␊
1208␉return 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-- )␊
1221␉curNode = curNode->prev;␊
1222 return curNode ? curNode->getData() : 0;␊
1223}␊
1224

Archive Download this file

Revision: 1322