1 /****************************************************************************
2 ** $Id: qt/qvaluelist.h 3.3.8 edited Jan 11 14:38 $
3 **
4 ** Definition of QValueList class
5 **
6 ** Created : 990406
7 **
8 ** Copyright (C) 1992-2007 Trolltech ASA. 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 ASA 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 #ifndef QVALUELIST_H
39 #define QVALUELIST_H
40
41 #ifndef QT_H
42 #include "qtl.h"
43 #include "qshared.h"
44 #include "qdatastream.h"
45 #endif // QT_H
46
47 #ifndef QT_NO_STL
48 #include <iterator>
49 #include <list>
50 #endif
51
52 //#define QT_CHECK_VALUELIST_RANGE
53
54 #if defined(Q_CC_MSVC)
55 #pragma warning(disable:4284) // "return type for operator -> is not a UDT"
56 #endif
57
58 template <class T>
59 class QValueListNode
60 {
61 public:
QValueListNode(const T & t)62 QValueListNode( const T& t ) : data( t ) { }
QValueListNode()63 QValueListNode() { }
64 #if defined(Q_TEMPLATEDLL)
65 // Workaround MS bug in memory de/allocation in DLL vs. EXE
~QValueListNode()66 virtual ~QValueListNode() { }
67 #endif
68
69 QValueListNode<T>* next;
70 QValueListNode<T>* prev;
71 T data;
72 };
73
74 template<class T>
75 class QValueListIterator
76 {
77 public:
78 /**
79 * Typedefs
80 */
81 typedef QValueListNode<T>* NodePtr;
82 #ifndef QT_NO_STL
83 typedef std::bidirectional_iterator_tag iterator_category;
84 #endif
85 typedef T value_type;
86 typedef size_t size_type;
87 #ifndef QT_NO_STL
88 typedef ptrdiff_t difference_type;
89 #else
90 typedef int difference_type;
91 #endif
92 typedef T* pointer;
93 typedef T& reference;
94
95 /**
96 * Variables
97 */
98 NodePtr node;
99
100 /**
101 * Functions
102 */
QValueListIterator()103 QValueListIterator() : node( 0 ) {}
QValueListIterator(NodePtr p)104 QValueListIterator( NodePtr p ) : node( p ) {}
QValueListIterator(const QValueListIterator<T> & it)105 QValueListIterator( const QValueListIterator<T>& it ) : node( it.node ) {}
106
107 bool operator==( const QValueListIterator<T>& it ) const { return node == it.node; }
108 bool operator!=( const QValueListIterator<T>& it ) const { return node != it.node; }
109 const T& operator*() const { return node->data; }
110 T& operator*() { return node->data; }
111 // UDT for T = x*
112 // T* operator->() const { return &node->data; }
113
114 QValueListIterator<T>& operator++() {
115 node = node->next;
116 return *this;
117 }
118
119 QValueListIterator<T> operator++(int) {
120 QValueListIterator<T> tmp = *this;
121 node = node->next;
122 return tmp;
123 }
124
125 QValueListIterator<T>& operator--() {
126 node = node->prev;
127 return *this;
128 }
129
130 QValueListIterator<T> operator--(int) {
131 QValueListIterator<T> tmp = *this;
132 node = node->prev;
133 return tmp;
134 }
135
136 QValueListIterator<T>& operator+=( int j ) {
137 while ( j-- )
138 node = node->next;
139 return *this;
140 }
141
142 QValueListIterator<T>& operator-=( int j ) {
143 while ( j-- )
144 node = node->prev;
145 return *this;
146 }
147
148 };
149
150 template<class T>
151 class QValueListConstIterator
152 {
153 public:
154 /**
155 * Typedefs
156 */
157 typedef QValueListNode<T>* NodePtr;
158 #ifndef QT_NO_STL
159 typedef std::bidirectional_iterator_tag iterator_category;
160 #endif
161 typedef T value_type;
162 typedef size_t size_type;
163 #ifndef QT_NO_STL
164 typedef ptrdiff_t difference_type;
165 #else
166 typedef int difference_type;
167 #endif
168 typedef const T* pointer;
169 typedef const T& reference;
170
171 /**
172 * Variables
173 */
174 NodePtr node;
175
176 /**
177 * Functions
178 */
QValueListConstIterator()179 QValueListConstIterator() : node( 0 ) {}
QValueListConstIterator(NodePtr p)180 QValueListConstIterator( NodePtr p ) : node( p ) {}
QValueListConstIterator(const QValueListConstIterator<T> & it)181 QValueListConstIterator( const QValueListConstIterator<T>& it ) : node( it.node ) {}
QValueListConstIterator(const QValueListIterator<T> & it)182 QValueListConstIterator( const QValueListIterator<T>& it ) : node( it.node ) {}
183
184 bool operator==( const QValueListConstIterator<T>& it ) const { return node == it.node; }
185 bool operator!=( const QValueListConstIterator<T>& it ) const { return node != it.node; }
186 const T& operator*() const { return node->data; }
187 // UDT for T = x*
188 // const T* operator->() const { return &node->data; }
189
190 QValueListConstIterator<T>& operator++() {
191 node = node->next;
192 return *this;
193 }
194
195 QValueListConstIterator<T> operator++(int) {
196 QValueListConstIterator<T> tmp = *this;
197 node = node->next;
198 return tmp;
199 }
200
201 QValueListConstIterator<T>& operator--() {
202 node = node->prev;
203 return *this;
204 }
205
206 QValueListConstIterator<T> operator--(int) {
207 QValueListConstIterator<T> tmp = *this;
208 node = node->prev;
209 return tmp;
210 }
211 };
212
213 template <class T>
214 class QValueListPrivate : public QShared
215 {
216 public:
217 /**
218 * Typedefs
219 */
220 typedef QValueListIterator<T> Iterator;
221 typedef QValueListConstIterator<T> ConstIterator;
222 typedef QValueListNode<T> Node;
223 typedef QValueListNode<T>* NodePtr;
224 typedef size_t size_type;
225
226 /**
227 * Functions
228 */
229 QValueListPrivate();
230 QValueListPrivate( const QValueListPrivate<T>& _p );
231
derefAndDelete()232 void derefAndDelete() // ### hack to get around hp-cc brain damage
233 {
234 if ( deref() )
235 delete this;
236 }
237
238 #if defined(Q_TEMPLATEDLL)
239 // Workaround MS bug in memory de/allocation in DLL vs. EXE
240 virtual
241 #endif
242 ~QValueListPrivate();
243
244 Iterator insert( Iterator it, const T& x );
245 Iterator remove( Iterator it );
246 NodePtr find( NodePtr start, const T& x ) const;
247 int findIndex( NodePtr start, const T& x ) const;
248 uint contains( const T& x ) const;
249 uint remove( const T& x );
250 NodePtr at( size_type i ) const;
251 void clear();
252
253 NodePtr node;
254 size_type nodes;
255 };
256
257 template <class T>
QValueListPrivate()258 Q_INLINE_TEMPLATES QValueListPrivate<T>::QValueListPrivate()
259 {
260 node = new Node; node->next = node->prev = node; nodes = 0;
261 }
262
263 template <class T>
QValueListPrivate(const QValueListPrivate<T> & _p)264 Q_INLINE_TEMPLATES QValueListPrivate<T>::QValueListPrivate( const QValueListPrivate<T>& _p )
265 : QShared()
266 {
267 node = new Node; node->next = node->prev = node; nodes = 0;
268 Iterator b( _p.node->next );
269 Iterator e( _p.node );
270 Iterator i( node );
271 while( b != e )
272 insert( i, *b++ );
273 }
274
275 template <class T>
~QValueListPrivate()276 Q_INLINE_TEMPLATES QValueListPrivate<T>::~QValueListPrivate() {
277 NodePtr p = node->next;
278 while( p != node ) {
279 NodePtr x = p->next;
280 delete p;
281 p = x;
282 }
283 delete node;
284 }
285
286 template <class T>
insert(Q_TYPENAME QValueListPrivate<T>::Iterator it,const T & x)287 Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::Iterator QValueListPrivate<T>::insert( Q_TYPENAME QValueListPrivate<T>::Iterator it, const T& x )
288 {
289 NodePtr p = new Node( x );
290 p->next = it.node;
291 p->prev = it.node->prev;
292 it.node->prev->next = p;
293 it.node->prev = p;
294 nodes++;
295 return p;
296 }
297
298 template <class T>
remove(Q_TYPENAME QValueListPrivate<T>::Iterator it)299 Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::Iterator QValueListPrivate<T>::remove( Q_TYPENAME QValueListPrivate<T>::Iterator it )
300 {
301 Q_ASSERT ( it.node != node );
302 NodePtr next = it.node->next;
303 NodePtr prev = it.node->prev;
304 prev->next = next;
305 next->prev = prev;
306 delete it.node;
307 nodes--;
308 return Iterator( next );
309 }
310
311 template <class T>
find(Q_TYPENAME QValueListPrivate<T>::NodePtr start,const T & x)312 Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::NodePtr QValueListPrivate<T>::find( Q_TYPENAME QValueListPrivate<T>::NodePtr start, const T& x ) const
313 {
314 ConstIterator first( start );
315 ConstIterator last( node );
316 while( first != last) {
317 if ( *first == x )
318 return first.node;
319 ++first;
320 }
321 return last.node;
322 }
323
324 template <class T>
findIndex(Q_TYPENAME QValueListPrivate<T>::NodePtr start,const T & x)325 Q_INLINE_TEMPLATES int QValueListPrivate<T>::findIndex( Q_TYPENAME QValueListPrivate<T>::NodePtr start, const T& x ) const
326 {
327 ConstIterator first( start );
328 ConstIterator last( node );
329 int pos = 0;
330 while( first != last) {
331 if ( *first == x )
332 return pos;
333 ++first;
334 ++pos;
335 }
336 return -1;
337 }
338
339 template <class T>
contains(const T & x)340 Q_INLINE_TEMPLATES uint QValueListPrivate<T>::contains( const T& x ) const
341 {
342 uint result = 0;
343 Iterator first = Iterator( node->next );
344 Iterator last = Iterator( node );
345 while( first != last) {
346 if ( *first == x )
347 ++result;
348 ++first;
349 }
350 return result;
351 }
352
353 template <class T>
remove(const T & _x)354 Q_INLINE_TEMPLATES uint QValueListPrivate<T>::remove( const T& _x )
355 {
356 const T x = _x;
357 uint result = 0;
358 Iterator first = Iterator( node->next );
359 Iterator last = Iterator( node );
360 while( first != last) {
361 if ( *first == x ) {
362 first = remove( first );
363 ++result;
364 } else
365 ++first;
366 }
367 return result;
368 }
369
370 template <class T>
at(size_type i)371 Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::NodePtr QValueListPrivate<T>::at( size_type i ) const
372 {
373 Q_ASSERT( i <= nodes );
374 NodePtr p = node->next;
375 for( size_type x = 0; x < i; ++x )
376 p = p->next;
377 return p;
378 }
379
380 template <class T>
clear()381 Q_INLINE_TEMPLATES void QValueListPrivate<T>::clear()
382 {
383 nodes = 0;
384 NodePtr p = node->next;
385 while( p != node ) {
386 NodePtr next = p->next;
387 delete p;
388 p = next;
389 }
390 node->next = node->prev = node;
391 }
392
393 #ifdef QT_CHECK_RANGE
394 # if !defined( QT_NO_DEBUG ) && defined( QT_CHECK_VALUELIST_RANGE )
395 # define QT_CHECK_INVALID_LIST_ELEMENT if ( empty() ) qWarning( "QValueList: Warning invalid element" )
396 # define QT_CHECK_INVALID_LIST_ELEMENT_FATAL Q_ASSERT( !empty() );
397 # else
398 # define QT_CHECK_INVALID_LIST_ELEMENT
399 # define QT_CHECK_INVALID_LIST_ELEMENT_FATAL
400 # endif
401 #else
402 # define QT_CHECK_INVALID_LIST_ELEMENT
403 # define QT_CHECK_INVALID_LIST_ELEMENT_FATAL
404 #endif
405
406 template <class T> class QDeepCopy;
407
408 template <class T>
409 class QValueList
410 {
411 public:
412 /**
413 * Typedefs
414 */
415 typedef QValueListIterator<T> iterator;
416 typedef QValueListConstIterator<T> const_iterator;
417 typedef T value_type;
418 typedef value_type* pointer;
419 typedef const value_type* const_pointer;
420 typedef value_type& reference;
421 typedef const value_type& const_reference;
422 typedef size_t size_type;
423 #ifndef QT_NO_STL
424 typedef ptrdiff_t difference_type;
425 #else
426 typedef int difference_type;
427 #endif
428
429 /**
430 * API
431 */
QValueList()432 QValueList() { sh = new QValueListPrivate<T>; }
QValueList(const QValueList<T> & l)433 QValueList( const QValueList<T>& l ) { sh = l.sh; sh->ref(); }
434 #ifndef QT_NO_STL
QValueList(const std::list<T> & l)435 QValueList( const std::list<T>& l )
436 {
437 sh = new QValueListPrivate<T>;
438 qCopy( l.begin(), l.end(), std::back_inserter( *this ) );
439 }
440 #endif
~QValueList()441 ~QValueList() { sh->derefAndDelete(); }
442
443 QValueList<T>& operator= ( const QValueList<T>& l )
444 {
445 l.sh->ref();
446 sh->derefAndDelete();
447 sh = l.sh;
448 return *this;
449 }
450 #ifndef QT_NO_STL
451 QValueList<T>& operator= ( const std::list<T>& l )
452 {
453 detach();
454 qCopy( l.begin(), l.end(), std::back_inserter( *this ) );
455 return *this;
456 }
457 bool operator== ( const std::list<T>& l ) const
458 {
459 if ( size() != l.size() )
460 return FALSE;
461 const_iterator it2 = begin();
462 #if !defined(Q_CC_MIPS)
463 typename
464 #endif
465 std::list<T>::const_iterator it = l.begin();
466 for ( ; it2 != end(); ++it2, ++it )
467 if ( !((*it2) == (*it)) )
468 return FALSE;
469 return TRUE;
470 }
471 #endif
472 bool operator== ( const QValueList<T>& l ) const;
473 bool operator!= ( const QValueList<T>& l ) const { return !( *this == l ); }
begin()474 iterator begin() { detach(); return iterator( sh->node->next ); }
begin()475 const_iterator begin() const { return const_iterator( sh->node->next ); }
constBegin()476 const_iterator constBegin() const { return const_iterator( sh->node->next ); }
end()477 iterator end() { detach(); return iterator( sh->node ); }
end()478 const_iterator end() const { return const_iterator( sh->node ); }
constEnd()479 const_iterator constEnd() const { return const_iterator( sh->node ); }
insert(iterator it,const T & x)480 iterator insert( iterator it, const T& x ) { detach(); return sh->insert( it, x ); }
remove(const T & x)481 uint remove( const T& x ) { detach(); return sh->remove( x ); }
482 void clear();
483
484 // ### 4.0: move out of class
485 QValueList<T>& operator<< ( const T& x )
486 {
487 append( x );
488 return *this;
489 }
490
size()491 size_type size() const { return sh->nodes; }
empty()492 bool empty() const { return sh->nodes == 0; }
push_front(const T & x)493 void push_front( const T& x ) { detach(); sh->insert( begin(), x ); }
push_back(const T & x)494 void push_back( const T& x ) { detach(); sh->insert( end(), x ); }
erase(iterator pos)495 iterator erase( iterator pos ) { detach(); return sh->remove( pos ); }
496 iterator erase( iterator first, iterator last );
front()497 reference front() { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *begin(); }
front()498 const_reference front() const { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *begin(); }
back()499 reference back() { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *(--end()); }
back()500 const_reference back() const { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *(--end()); }
pop_front()501 void pop_front() { QT_CHECK_INVALID_LIST_ELEMENT; erase( begin() ); }
pop_back()502 void pop_back() {
503 QT_CHECK_INVALID_LIST_ELEMENT;
504 iterator tmp = end();
505 erase( --tmp );
506 }
507 void insert( iterator pos, size_type n, const T& x );
508 // Some compilers (incl. vc++) would instantiate this function even if
509 // it is not used; this would constrain QValueList to classes that provide
510 // an operator<
511 /*
512 void sort()
513 {
514 qHeapSort( *this );
515 }
516 */
517
518 QValueList<T> operator+ ( const QValueList<T>& l ) const;
519 QValueList<T>& operator+= ( const QValueList<T>& l );
520
fromLast()521 iterator fromLast() { detach(); return iterator( sh->node->prev ); }
fromLast()522 const_iterator fromLast() const { return const_iterator( sh->node->prev ); }
523
isEmpty()524 bool isEmpty() const { return ( sh->nodes == 0 ); }
525
append(const T & x)526 iterator append( const T& x ) { detach(); return sh->insert( end(), x ); }
prepend(const T & x)527 iterator prepend( const T& x ) { detach(); return sh->insert( begin(), x ); }
528
remove(iterator it)529 iterator remove( iterator it ) { detach(); return sh->remove( it ); }
530
first()531 T& first() { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return sh->node->next->data; }
first()532 const T& first() const { QT_CHECK_INVALID_LIST_ELEMENT; return sh->node->next->data; }
last()533 T& last() { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return sh->node->prev->data; }
last()534 const T& last() const { QT_CHECK_INVALID_LIST_ELEMENT; return sh->node->prev->data; }
535
536 T& operator[] ( size_type i ) { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return sh->at(i)->data; }
537 const T& operator[] ( size_type i ) const { QT_CHECK_INVALID_LIST_ELEMENT; return sh->at(i)->data; }
at(size_type i)538 iterator at( size_type i ) { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return iterator( sh->at(i) ); }
at(size_type i)539 const_iterator at( size_type i ) const { QT_CHECK_INVALID_LIST_ELEMENT; return const_iterator( sh->at(i) ); }
find(const T & x)540 iterator find ( const T& x ) { detach(); return iterator( sh->find( sh->node->next, x) ); }
find(const T & x)541 const_iterator find ( const T& x ) const { return const_iterator( sh->find( sh->node->next, x) ); }
find(iterator it,const T & x)542 iterator find ( iterator it, const T& x ) { detach(); return iterator( sh->find( it.node, x ) ); }
find(const_iterator it,const T & x)543 const_iterator find ( const_iterator it, const T& x ) const { return const_iterator( sh->find( it.node, x ) ); }
findIndex(const T & x)544 int findIndex( const T& x ) const { return sh->findIndex( sh->node->next, x) ; }
contains(const T & x)545 size_type contains( const T& x ) const { return sh->contains( x ); }
546
count()547 size_type count() const { return sh->nodes; }
548
549 QValueList<T>& operator+= ( const T& x )
550 {
551 append( x );
552 return *this;
553 }
554 typedef QValueListIterator<T> Iterator;
555 typedef QValueListConstIterator<T> ConstIterator;
556 typedef T ValueType;
557
558 protected:
559 /**
560 * Helpers
561 */
detach()562 void detach() { if ( sh->count > 1 ) detachInternal(); }
563
564 /**
565 * Variables
566 */
567 QValueListPrivate<T>* sh;
568
569 private:
570 void detachInternal();
571
572 friend class QDeepCopy< QValueList<T> >;
573 };
574
575 template <class T>
576 Q_INLINE_TEMPLATES bool QValueList<T>::operator== ( const QValueList<T>& l ) const
577 {
578 if ( size() != l.size() )
579 return FALSE;
580 const_iterator it2 = begin();
581 const_iterator it = l.begin();
582 for( ; it != l.end(); ++it, ++it2 )
583 if ( !( *it == *it2 ) )
584 return FALSE;
585 return TRUE;
586 }
587
588 template <class T>
clear()589 Q_INLINE_TEMPLATES void QValueList<T>::clear()
590 {
591 if ( sh->count == 1 ) sh->clear(); else { sh->deref(); sh = new QValueListPrivate<T>; }
592 }
593
594 template <class T>
erase(Q_TYPENAME QValueList<T>::iterator first,Q_TYPENAME QValueList<T>::iterator last)595 Q_INLINE_TEMPLATES Q_TYPENAME QValueList<T>::iterator QValueList<T>::erase( Q_TYPENAME QValueList<T>::iterator first, Q_TYPENAME QValueList<T>::iterator last )
596 {
597 while ( first != last )
598 erase( first++ );
599 return last;
600 }
601
602
603 template <class T>
insert(Q_TYPENAME QValueList<T>::iterator pos,size_type n,const T & x)604 Q_INLINE_TEMPLATES void QValueList<T>::insert( Q_TYPENAME QValueList<T>::iterator pos, size_type n, const T& x )
605 {
606 for ( ; n > 0; --n )
607 insert( pos, x );
608 }
609
610 template <class T>
611 Q_INLINE_TEMPLATES QValueList<T> QValueList<T>::operator+ ( const QValueList<T>& l ) const
612 {
613 QValueList<T> l2( *this );
614 for( const_iterator it = l.begin(); it != l.end(); ++it )
615 l2.append( *it );
616 return l2;
617 }
618
619 template <class T>
620 Q_INLINE_TEMPLATES QValueList<T>& QValueList<T>::operator+= ( const QValueList<T>& l )
621 {
622 QValueList<T> copy = l;
623 for( const_iterator it = copy.begin(); it != copy.end(); ++it )
624 append( *it );
625 return *this;
626 }
627
628 template <class T>
detachInternal()629 Q_INLINE_TEMPLATES void QValueList<T>::detachInternal()
630 {
631 sh->deref(); sh = new QValueListPrivate<T>( *sh );
632 }
633
634 #ifndef QT_NO_DATASTREAM
635 template <class T>
636 Q_INLINE_TEMPLATES QDataStream& operator>>( QDataStream& s, QValueList<T>& l )
637 {
638 l.clear();
639 Q_UINT32 c;
640 s >> c;
641 for( Q_UINT32 i = 0; i < c; ++i )
642 {
643 T t;
644 s >> t;
645 l.append( t );
646 if ( s.atEnd() )
647 break;
648 }
649 return s;
650 }
651
652 template <class T>
653 Q_INLINE_TEMPLATES QDataStream& operator<<( QDataStream& s, const QValueList<T>& l )
654 {
655 s << (Q_UINT32)l.size();
656 QValueListConstIterator<T> it = l.begin();
657 for( ; it != l.end(); ++it )
658 s << *it;
659 return s;
660 }
661 #endif // QT_NO_DATASTREAM
662
663 #define Q_DEFINED_QVALUELIST
664 #define Q_DEFINED_QVALUELIST
665 #include "qwinexport.h"
666 #endif // QVALUELIST_H
667