Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/****************************************************************************
2**
3**
4** Implementation of QGVector class
5**
6** Created : 930907
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#define QGVECTOR_CPP
39#include "qgvector.h"
40#include "qglist.h"
41#include "qstring.h"
42#include "qdatastream.h"
43#include <stdlib.h>
44
45#define USE_MALLOC// comment to use new/delete
46
47#undef NEW
48#undef DELETE
49
50#if defined(USE_MALLOC)
51#define NEW(type,size)((type*)malloc(size*sizeof(type)))
52#define DELETE(array)(free((char*)array))
53#else
54#define NEW(type,size)(new type[size])
55#define DELETE(array)(delete[] array)
56#define DONT_USE_REALLOC// comment to use realloc()
57#endif
58
59// NOT REVISED
60
61/*!
62 \class QGVector qgvector.h
63
64 \brief The QGVector class is an internal class for implementing Qt
65 collection classes.
66
67 QGVector is a strictly internal class that acts as a base class for
68 the QVector collection class.
69
70 QGVector has some virtual functions that may be reimplemented in
71 subclasses to to customize behavior.
72
73 <ul>
74 <li> compareItems() compares two collection/vector items.
75 <li> read() reads a collection/vector item from a QDataStream.
76 <li> write() writes a collection/vector item to a QDataStream.
77 </ul>
78*/
79
80/*****************************************************************************
81 Default implementation of virtual functions
82 *****************************************************************************/
83
84/*!
85 This virtual function compares two list items.
86
87 Returns:
88 <ul>
89 <li> 0 if \a item1 == \a item2
90 <li> non-zero if \a item1 != \a item2
91 </ul>
92
93 This function returns \e int rather than \e bool so that
94 reimplementations can return one of three values and use it to sort
95 by:
96
97 <ul>
98 <li> 0 if \e item1 == \e item2
99 <li> \> 0 (positive integer) if \a item1 \> \a item2
100 <li> \< 0 (negative integer) if \a item1 \< \a item2
101 </ul>
102
103 The QVector::sort() and QVector::bsearch() functions require that
104 compareItems() is implemented as described here.
105
106 This function should not modify the vector because some const
107 functions call compareItems().
108*/
109
110int QGVector::compareItems( Item d1, Item d2 )
111{
112 return d1 != d2;// compare pointers
113}
114
115#ifndef QT_NO_DATASTREAM
116/*!
117 Reads a collection/vector item from the stream \a s and returns a reference
118 to the stream.
119
120 The default implementation sets \e item to 0.
121
122 \sa write()
123*/
124
125QDataStream &QGVector::read( QDataStream &s, Item &d )
126{// read item from stream
127 d = 0;
128 return s;
129}
130
131/*!
132 Writes a collection/vector item to the stream \a s and returns a reference
133 to the stream.
134
135 The default implementation does nothing.
136
137 \sa read()
138*/
139
140QDataStream &QGVector::write( QDataStream &s, Item ) const
141{// write item to stream
142 return s;
143}
144#endif // QT_NO_DATASTREAM
145
146/*****************************************************************************
147 QGVector member functions
148 *****************************************************************************/
149
150/*!
151 \internal
152*/
153
154QGVector::QGVector()// create empty vector
155{
156 vec = 0;
157 len = numItems = 0;
158}
159
160/*!
161 \internal
162*/
163QGVector::QGVector( uint size )// create vectors with nullptrs
164{
165 len = size;
166 numItems = 0;
167 if ( len == 0 ) {// zero length
168vec = 0;
169return;
170 }
171 vec = NEW(Item,len);
172 CHECK_PTR( vec );
173 memset( (void*)vec, 0, len*sizeof(Item) );// fill with nulls
174}
175
176/*!
177 \internal
178*/
179
180QGVector::QGVector( const QGVector &a )// make copy of other vector
181 : QCollection( a )
182{
183 len = a.len;
184 numItems = a.numItems;
185 vec = NEW(Item,len);
186 CHECK_PTR( vec );
187 for ( uint i=0; i<len; i++ ) {
188vec[i] = a.vec[i] ? newItem( a.vec[i] ) : 0;
189CHECK_PTR( vec[i] );
190 }
191}
192
193/*!
194 \internal
195*/
196
197QGVector::~QGVector()
198{
199 clear();
200}
201
202
203/*!
204 \internal
205*/
206
207QGVector& QGVector::operator=( const QGVector &v )
208{// assign from other vector
209 clear();// first delete old vector
210 len = v.len;
211 numItems = v.numItems;
212 vec = NEW(Item,len);// create new vector
213 CHECK_PTR( vec );
214 for ( uint i=0; i<len; i++ ) {// copy elements
215vec[i] = v.vec[i] ? newItem( v.vec[i] ) : 0;
216CHECK_PTR( vec[i] );
217 }
218 return *this;
219}
220
221
222/*!
223 \fn Item *QGVector::data() const
224 \internal
225*/
226
227/*!
228 \fn uint QGVector::size() const
229 \internal
230*/
231
232/*!
233 \fn uint QGVector::count() const
234 \internal
235*/
236
237/*!
238 \fn Item QGVector::at( uint index ) const
239 \internal
240*/
241
242/*!
243 \internal
244*/
245
246bool QGVector::insert( uint index, Item d )// insert item at index
247{
248#if defined(CHECK_RANGE)
249 if ( index >= len ) {// range error
250qWarning( "QGVector::insert: Index %d out of range", index );
251return FALSE;
252 }
253#endif
254 if ( vec[index] ) {// remove old item
255deleteItem( vec[index] );
256numItems--;
257 }
258 if ( d ) {
259vec[index] = newItem( d );
260CHECK_PTR( vec[index] );
261numItems++;
262return vec[index] != 0;
263 } else {
264vec[index] = 0;// reset item
265 }
266 return TRUE;
267}
268
269/*!
270 \internal
271*/
272
273bool QGVector::remove( uint index )// remove item at index
274{
275#if defined(CHECK_RANGE)
276 if ( index >= len ) {// range error
277qWarning( "QGVector::remove: Index %d out of range", index );
278return FALSE;
279 }
280#endif
281 if ( vec[index] ) {// valid item
282deleteItem( vec[index] );// delete it
283vec[index] = 0;// reset pointer
284numItems--;
285 }
286 return TRUE;
287}
288
289/*!
290 \internal
291*/
292
293QCollection::Item QGVector::take( uint index )// take out item
294{
295#if defined(CHECK_RANGE)
296 if ( index >= len ) {// range error
297qWarning( "QGVector::take: Index %d out of range", index );
298return 0;
299 }
300#endif
301 Item d = vec[index];// don't delete item
302 if ( d )
303numItems--;
304 vec[index] = 0;
305 return d;
306}
307
308
309/*!
310 \internal
311*/
312
313void QGVector::clear()// clear vector
314{
315 if ( vec ) {
316for ( uint i=0; i<len; i++ ) {// delete each item
317 if ( vec[i] )
318deleteItem( vec[i] );
319}
320DELETE(vec);
321vec = 0;
322len = numItems = 0;
323 }
324}
325
326/*!
327 \internal
328*/
329
330bool QGVector::resize( uint newsize )// resize array
331{
332 if ( newsize == len )// nothing to do
333return TRUE;
334 if ( vec ) {// existing data
335if ( newsize < len ) {// shrink vector
336 uint i = newsize;
337 while ( i < len ) {// delete lost items
338if ( vec[i] ) {
339 deleteItem( vec[i] );
340 numItems--;
341}
342i++;
343 }
344}
345if ( newsize == 0 ) {// vector becomes empty
346 DELETE(vec);
347 vec = 0;
348 len = numItems = 0;
349 return TRUE;
350}
351#if defined(DONT_USE_REALLOC)
352Item *newvec = NEW(Item,newsize);// manual realloc
353memcpy( newvec, vec, (len < newsize ? len : newsize)*sizeof(Item) );
354DELETE(vec);
355vec = newvec;
356#else
357vec = (Item*)realloc( (char *)vec, newsize*sizeof(Item) );
358#endif
359 } else {// create new vector
360vec = NEW(Item,newsize);
361len = numItems = 0;
362 }
363 CHECK_PTR( vec );
364 if ( !vec )// no memory
365return FALSE;
366 if ( newsize > len )// init extra space added
367memset( (void*)&vec[len], 0, (newsize-len)*sizeof(Item) );
368 len = newsize;
369 return TRUE;
370}
371
372
373/*!
374 \internal
375*/
376
377bool QGVector::fill( Item d, int flen )// resize and fill vector
378{
379 if ( flen < 0 )
380flen = len;// default: use vector length
381 else if ( !resize( flen ) )
382return FALSE;
383 for ( uint i=0; i<(uint)flen; i++ )// insert d at every index
384insert( i, d );
385 return TRUE;
386}
387
388
389static QGVector *sort_vec=0;// current sort vector
390
391
392#if defined(Q_C_CALLBACKS)
393extern "C" {
394#endif
395
396static int cmp_vec( const void *n1, const void *n2 )
397{
398 return sort_vec->compareItems( *((QCollection::Item*)n1), *((QCollection::Item*)n2) );
399}
400
401#if defined(Q_C_CALLBACKS)
402}
403#endif
404
405
406/*!
407 \internal
408*/
409
410void QGVector::sort()// sort vector
411{
412 if ( count() == 0 )// no elements
413return;
414 register Item *start = &vec[0];
415 register Item *end= &vec[len-1];
416 Item tmp;
417 while ( TRUE ) {// put all zero elements behind
418while ( start < end && *start != 0 )
419 start++;
420while ( end > start && *end == 0 )
421 end--;
422if ( start < end ) {
423 tmp = *start;
424 *start = *end;
425 *end = tmp;
426} else {
427 break;
428}
429 }
430 sort_vec = (QGVector*)this;
431 qsort( vec, count(), sizeof(Item), cmp_vec );
432 sort_vec = 0;
433}
434
435/*!
436 \internal
437*/
438
439int QGVector::bsearch( Item d ) const// binary search; when sorted
440{
441 if ( !len )
442return -1;
443 if ( !d ) {
444#if defined(CHECK_NULL)
445qWarning( "QGVector::bsearch: Cannot search for null object" );
446#endif
447return -1;
448 }
449 int n1 = 0;
450 int n2 = len - 1;
451 int mid = 0;
452 bool found = FALSE;
453 while ( n1 <= n2 ) {
454int res;
455mid = (n1 + n2)/2;
456if ( vec[mid] == 0 )// null item greater
457 res = -1;
458else
459 res = ((QGVector*)this)->compareItems( d, vec[mid] );
460if ( res < 0 )
461 n2 = mid - 1;
462else if ( res > 0 )
463 n1 = mid + 1;
464else {// found it
465 found = TRUE;
466 break;
467}
468 }
469 if ( !found )
470return -1;
471 // search to first of equal items
472 while ( (mid - 1 >= 0) && !((QGVector*)this)->compareItems(d, vec[mid-1]) )
473mid--;
474 return mid;
475}
476
477
478/*!
479 \internal
480*/
481
482int QGVector::findRef( Item d, uint index) const // find exact item in vector
483{
484#if defined(CHECK_RANGE)
485 if ( index >= len ) {// range error
486qWarning( "QGVector::findRef: Index %d out of range", index );
487return -1;
488 }
489#endif
490 for ( uint i=index; i<len; i++ ) {
491if ( vec[i] == d )
492 return i;
493 }
494 return -1;
495}
496
497/*!
498 \internal
499*/
500
501int QGVector::find( Item d, uint index ) const// find equal item in vector
502{
503#if defined(CHECK_RANGE)
504 if ( index >= len ) {// range error
505qWarning( "QGVector::find: Index %d out of range", index );
506return -1;
507 }
508#endif
509 for ( uint i=index; i<len; i++ ) {
510if ( vec[i] == 0 && d == 0 )// found null item
511 return i;
512if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 )
513 return i;
514 }
515 return -1;
516}
517
518/*!
519 \internal
520*/
521
522uint QGVector::containsRef( Item d ) const// get number of exact matches
523{
524 uint count = 0;
525 for ( uint i=0; i<len; i++ ) {
526if ( vec[i] == d )
527 count++;
528 }
529 return count;
530}
531
532/*!
533 \internal
534*/
535
536uint QGVector::contains( Item d ) const// get number of equal matches
537{
538 uint count = 0;
539 for ( uint i=0; i<len; i++ ) {
540if ( vec[i] == 0 && d == 0 )// count null items
541 count++;
542if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 )
543 count++;
544 }
545 return count;
546}
547
548
549/*!
550 \internal
551*/
552
553bool QGVector::insertExpand( uint index, Item d )// insert and grow if necessary
554{
555 if ( index >= len ) {
556if ( !resize( index+1 ) )// no memory
557 return FALSE;
558 }
559 insert( index, d );
560 return TRUE;
561}
562
563
564/*!
565 \internal
566*/
567
568void QGVector::toList( QGList *list ) const// store items in list
569{
570 list->clear();
571 for ( uint i=0; i<len; i++ ) {
572if ( vec[i] )
573 list->append( vec[i] );
574 }
575}
576
577
578void QGVector::warningIndexRange( uint i )
579{
580#if defined(CHECK_RANGE)
581 qWarning( "QGVector::operator[]: Index %d out of range", i );
582#else
583 Q_UNUSED( i )
584#endif
585}
586
587
588/*****************************************************************************
589 QGVector stream functions
590 *****************************************************************************/
591#ifndef QT_NO_DATASTREAM
592QDataStream &operator>>( QDataStream &s, QGVector &vec )
593{// read vector
594 return vec.read( s );
595}
596
597QDataStream &operator<<( QDataStream &s, const QGVector &vec )
598{// write vector
599 return vec.write( s );
600}
601
602/*!
603 \internal
604*/
605
606QDataStream &QGVector::read( QDataStream &s )// read vector from stream
607{
608 uint num;
609 s >> num;// read number of items
610 clear();// clear vector
611 resize( num );
612 for (uint i=0; i<num; i++) {// read all items
613Item d;
614read( s, d );
615CHECK_PTR( d );
616if ( !d )// no memory
617 break;
618vec[i] = d;
619 }
620 return s;
621}
622
623/*!
624 \internal
625*/
626
627QDataStream &QGVector::write( QDataStream &s ) const
628{// write vector to stream
629 uint num = count();
630 s << num;// number of items to write
631 num = size();
632 for (uint i=0; i<num; i++) {// write non-null items
633if ( vec[i] )
634 write( s, vec[i] );
635 }
636 return s;
637}
638#endif // QT_NO_DATASTREAM
639

Archive Download this file

Revision: 1322