-rw-r--r-- | qmake/tools/qglist.cpp | 1255 |
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 | */ | ||
95 | class QGListIteratorList | ||
96 | { | ||
97 | public: | ||
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 | |||
157 | private: | ||
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 | */ | ||
173 | int 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 | |||
189 | QDataStream &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 | |||
205 | QDataStream &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 | |||
219 | QGList::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 | |||
231 | QGList::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 | |||
249 | QGList::~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 | |||
265 | QGList& 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 | |||
288 | bool 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 | |||
320 | QLNode *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 | |||
371 | void 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 | |||
387 | void 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 | |||
406 | void 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 | |||
425 | bool 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 | |||
454 | void 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 | |||
475 | QLNode *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 | |||
515 | bool 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 | |||
539 | bool 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 | |||
555 | bool 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 | |||
583 | bool 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 | */ | ||
599 | bool 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 | |||
617 | QPtrCollection::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 | |||
639 | QPtrCollection::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 | |||
651 | QPtrCollection::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 | |||
665 | QPtrCollection::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 | |||
678 | QPtrCollection::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 | |||
692 | void 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 | |||
718 | int 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 | |||
744 | int 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 | |||
769 | uint 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 | |||
786 | uint 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 | |||
841 | QPtrCollection::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 | |||
854 | QPtrCollection::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 | |||
867 | QPtrCollection::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 | |||
885 | QPtrCollection::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 | |||
904 | void 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 | |||
918 | void 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 | |||
964 | void 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 | ||
1007 | QDataStream &operator>>( QDataStream &s, QGList &list ) | ||
1008 | { // read list | ||
1009 | return list.read( s ); | ||
1010 | } | ||
1011 | |||
1012 | QDataStream &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 | |||
1021 | QDataStream &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 | |||
1053 | QDataStream &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 | |||
1087 | QGListIterator::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 | |||
1103 | QGListIterator::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 | |||
1117 | QGListIterator &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 | |||
1133 | QGListIterator::~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 | |||
1158 | QPtrCollection::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 | |||
1174 | QPtrCollection::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 | |||
1198 | QPtrCollection::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 | |||
1212 | QPtrCollection::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 | |||
1225 | QPtrCollection::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 | |||
1237 | QPtrCollection::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 | |||
1250 | QPtrCollection::Item QGListIterator::operator-=( uint jumps ) | ||
1251 | { | ||
1252 | while ( curNode && jumps-- ) | ||
1253 | curNode = curNode->prev; | ||
1254 | return curNode ? curNode->getData() : 0; | ||
1255 | } | ||