Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 12 years 8 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␊
168␉vec = 0;␊
169␉return;␊
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++ ) {␊
188␉vec[i] = a.vec[i] ? newItem( a.vec[i] ) : 0;␊
189␉CHECK_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␊
215␉vec[i] = v.vec[i] ? newItem( v.vec[i] ) : 0;␊
216␉CHECK_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␊
250␉qWarning( "QGVector::insert: Index %d out of range", index );␊
251␉return FALSE;␊
252 }␊
253#endif␊
254 if ( vec[index] ) {␉␉␉␉// remove old item␊
255␉deleteItem( vec[index] );␊
256␉numItems--;␊
257 }␊
258 if ( d ) {␊
259␉vec[index] = newItem( d );␊
260␉CHECK_PTR( vec[index] );␊
261␉numItems++;␊
262␉return vec[index] != 0;␊
263 } else {␊
264␉vec[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␊
277␉qWarning( "QGVector::remove: Index %d out of range", index );␊
278␉return FALSE;␊
279 }␊
280#endif␊
281 if ( vec[index] ) {␉␉␉␉// valid item␊
282␉deleteItem( vec[index] );␉␉// delete it␊
283␉vec[index] = 0;␉␉␉␉// reset pointer␊
284␉numItems--;␊
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␊
297␉qWarning( "QGVector::take: Index %d out of range", index );␊
298␉return 0;␊
299 }␊
300#endif␊
301 Item d = vec[index];␉␉␉␉// don't delete item␊
302 if ( d )␊
303␉numItems--;␊
304 vec[index] = 0;␊
305 return d;␊
306}␊
307␊
308␊
309/*!␊
310 \internal␊
311*/␊
312␊
313void QGVector::clear()␉␉␉␉// clear vector␊
314{␊
315 if ( vec ) {␊
316␉for ( uint i=0; i<len; i++ ) {␉␉// delete each item␊
317␉ if ( vec[i] )␊
318␉␉deleteItem( vec[i] );␊
319␉}␊
320␉DELETE(vec);␊
321␉vec = 0;␊
322␉len = 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␊
333␉return TRUE;␊
334 if ( vec ) {␉␉␉␉// existing data␊
335␉if ( newsize < len ) {␉␉␉// shrink vector␊
336␉ uint i = newsize;␊
337␉ while ( i < len ) {␉␉␉// delete lost items␊
338␉␉if ( vec[i] ) {␊
339␉␉ deleteItem( vec[i] );␊
340␉␉ numItems--;␊
341␉␉}␊
342␉␉i++;␊
343␉ }␊
344␉}␊
345␉if ( 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)␊
352␉Item *newvec = NEW(Item,newsize);␉␉// manual realloc␊
353␉memcpy( newvec, vec, (len < newsize ? len : newsize)*sizeof(Item) );␊
354␉DELETE(vec);␊
355␉vec = newvec;␊
356#else␊
357␉vec = (Item*)realloc( (char *)vec, newsize*sizeof(Item) );␊
358#endif␊
359 } else {␉␉␉␉␉// create new vector␊
360␉vec = NEW(Item,newsize);␊
361␉len = numItems = 0;␊
362 }␊
363 CHECK_PTR( vec );␊
364 if ( !vec )␉␉␉␉␉// no memory␊
365␉return FALSE;␊
366 if ( newsize > len )␉␉␉// init extra space added␊
367␉memset( (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 )␊
380␉flen = len;␉␉␉␉// default: use vector length␊
381 else if ( !resize( flen ) )␊
382␉return FALSE;␊
383 for ( uint i=0; i<(uint)flen; i++ )␉␉// insert d at every index␊
384␉insert( 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␊
413␉return;␊
414 register Item *start = &vec[0];␊
415 register Item *end␉= &vec[len-1];␊
416 Item tmp;␊
417 while ( TRUE ) {␉␉␉␉// put all zero elements behind␊
418␉while ( start < end && *start != 0 )␊
419␉ start++;␊
420␉while ( end > start && *end == 0 )␊
421␉ end--;␊
422␉if ( 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 )␊
442␉return -1;␊
443 if ( !d ) {␊
444#if defined(CHECK_NULL)␊
445␉qWarning( "QGVector::bsearch: Cannot search for null object" );␊
446#endif␊
447␉return -1;␊
448 }␊
449 int n1 = 0;␊
450 int n2 = len - 1;␊
451 int mid = 0;␊
452 bool found = FALSE;␊
453 while ( n1 <= n2 ) {␊
454␉int res;␊
455␉mid = (n1 + n2)/2;␊
456␉if ( vec[mid] == 0 )␉␉␉// null item greater␊
457␉ res = -1;␊
458␉else␊
459␉ res = ((QGVector*)this)->compareItems( d, vec[mid] );␊
460␉if ( res < 0 )␊
461␉ n2 = mid - 1;␊
462␉else if ( res > 0 )␊
463␉ n1 = mid + 1;␊
464␉else {␉␉␉␉␉// found it␊
465␉ found = TRUE;␊
466␉ break;␊
467␉}␊
468 }␊
469 if ( !found )␊
470␉return -1;␊
471 // search to first of equal items␊
472 while ( (mid - 1 >= 0) && !((QGVector*)this)->compareItems(d, vec[mid-1]) )␊
473␉mid--;␊
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␊
486␉qWarning( "QGVector::findRef: Index %d out of range", index );␊
487␉return -1;␊
488 }␊
489#endif␊
490 for ( uint i=index; i<len; i++ ) {␊
491␉if ( 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␊
505␉qWarning( "QGVector::find: Index %d out of range", index );␊
506␉return -1;␊
507 }␊
508#endif␊
509 for ( uint i=index; i<len; i++ ) {␊
510␉if ( vec[i] == 0 && d == 0 )␉␉// found null item␊
511␉ return i;␊
512␉if ( 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++ ) {␊
526␉if ( 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++ ) {␊
540␉if ( vec[i] == 0 && d == 0 )␉␉// count null items␊
541␉ count++;␊
542␉if ( 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 ) {␊
556␉if ( !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++ ) {␊
572␉if ( 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␊
613␉Item d;␊
614␉read( s, d );␊
615␉CHECK_PTR( d );␊
616␉if ( !d )␉␉␉␉// no memory␊
617␉ break;␊
618␉vec[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␊
633␉if ( vec[i] )␊
634␉ write( s, vec[i] );␊
635 }␊
636 return s;␊
637}␊
638#endif // QT_NO_DATASTREAM␊
639

Archive Download this file

Revision: 1322