|
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 |
|
110 int 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 |
|
125 QDataStream &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 |
|
140 QDataStream &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 |
|
154 QGVector::QGVector() // create empty vector |
|
155 { |
|
156 vec = 0; |
|
157 len = numItems = 0; |
|
158 } |
|
159 |
|
160 /*! |
|
161 \internal |
|
162 */ |
|
163 QGVector::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 |
|
180 QGVector::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 |
|
197 QGVector::~QGVector() |
|
198 { |
|
199 clear(); |
|
200 } |
|
201 |
|
202 |
|
203 /*! |
|
204 \internal |
|
205 */ |
|
206 |
|
207 QGVector& 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 |
|
246 bool 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 |
|
273 bool 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 |
|
293 QCollection::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 |
|
313 void 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 |
|
330 bool 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 |
|
377 bool 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 |
|
389 static QGVector *sort_vec=0; // current sort vector |
|
390 |
|
391 |
|
392 #if defined(Q_C_CALLBACKS) |
|
393 extern "C" { |
|
394 #endif |
|
395 |
|
396 static 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 |
|
410 void 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 |
|
439 int 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 |
|
482 int 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 |
|
501 int 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 |
|
522 uint 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 |
|
536 uint 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 |
|
553 bool 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 |
|
568 void 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 |
|
578 void 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 |
|
592 QDataStream &operator>>( QDataStream &s, QGVector &vec ) |
|
593 { // read vector |
|
594 return vec.read( s ); |
|
595 } |
|
596 |
|
597 QDataStream &operator<<( QDataStream &s, const QGVector &vec ) |
|
598 { // write vector |
|
599 return vec.write( s ); |
|
600 } |
|
601 |
|
602 /*! |
|
603 \internal |
|
604 */ |
|
605 |
|
606 QDataStream &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 |
|
627 QDataStream &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 |