← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/qt3support/tools/q3glist.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

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