1 /****************************************************************************

     2 ** 

     3 **

     4 ** Definition of QValueList class

     5 **

     6 ** Created : 990406

     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 #ifndef QVALUELIST_H

    39 #define QVALUELIST_H

    40 

    41 #ifndef QT_H

    42 #include "qshared.h"

    43 #include "qdatastream.h"

    44 #endif // QT_H

    45 

    46 #if defined(_CC_MSVC_)

    47 #pragma warning(disable:4284) // "return type for operator -> is not a UDT"

    48 #endif

    49 

    50 template <class T>

    51 class Q_EXPORT QValueListNode

    52 {

    53 public:

    54     QValueListNode( const T& t ) : data( t ) { }

    55     QValueListNode() { }

    56 #if defined(Q_TEMPLATEDLL)

    57     // Workaround MS bug in memory de/allocation in DLL vs. EXE 

    58     virtual ~QValueListNode() { }

    59 #endif

    60 

    61     QValueListNode<T>* next;

    62     QValueListNode<T>* prev;

    63     T data;

    64 };

    65 

    66 template<class T>

    67 class Q_EXPORT QValueListIterator

    68 {

    69  public:

    70     /**

    71      * Typedefs

    72      */

    73     typedef QValueListNode<T>* NodePtr;

    74 

    75     /**

    76      * Variables

    77      */

    78     NodePtr node;

    79 

    80     /**

    81      * Functions

    82      */

    83     QValueListIterator() : node( 0 ) {}

    84     QValueListIterator( NodePtr p ) : node( p ) {}

    85     QValueListIterator( const QValueListIterator<T>& it ) : node( it.node ) {}

    86 

    87     bool operator==( const QValueListIterator<T>& it ) const { return node == it.node; }

    88     bool operator!=( const QValueListIterator<T>& it ) const { return node != it.node; }

    89     const T& operator*() const { return node->data; }

    90     T& operator*() { return node->data; }

    91 

    92     // Compilers are too dumb to understand this for QValueList<int>

    93     //T* operator->() const { return &(node->data); }

    94 

    95     QValueListIterator<T>& operator++() {

    96 	node = node->next;

    97 	return *this;

    98     }

    99 

   100     QValueListIterator<T> operator++(int) {

   101 	QValueListIterator<T> tmp = *this;

   102 	node = node->next;

   103 	return tmp;

   104     }

   105 

   106     QValueListIterator<T>& operator--() {

   107 	node = node->prev;

   108 	return *this;

   109     }

   110 

   111     QValueListIterator<T> operator--(int) {

   112 	QValueListIterator<T> tmp = *this;

   113 	node = node->prev;

   114 	return tmp;

   115     }

   116 };

   117 

   118 template<class T>

   119 class Q_EXPORT QValueListConstIterator

   120 {

   121  public:

   122     /**

   123      * Typedefs

   124      */

   125     typedef QValueListNode<T>* NodePtr;

   126 

   127     /**

   128      * Variables

   129      */

   130     NodePtr node;

   131 

   132     /**

   133      * Functions

   134      */

   135     QValueListConstIterator() : node( 0 ) {}

   136     QValueListConstIterator( NodePtr p ) : node( p ) {}

   137     QValueListConstIterator( const QValueListConstIterator<T>& it ) : node( it.node ) {}

   138     QValueListConstIterator( const QValueListIterator<T>& it ) : node( it.node ) {}

   139 

   140     bool operator==( const QValueListConstIterator<T>& it ) const { return node == it.node; }

   141     bool operator!=( const QValueListConstIterator<T>& it ) const { return node != it.node; }

   142     const T& operator*() const { return node->data; }

   143 

   144     // Compilers are too dumb to understand this for QValueList<int>

   145     //const T* operator->() const { return &(node->data); }

   146 

   147     QValueListConstIterator<T>& operator++() {

   148 	node = node->next;

   149 	return *this;

   150     }

   151 

   152     QValueListConstIterator<T> operator++(int) {

   153 	QValueListConstIterator<T> tmp = *this;

   154 	node = node->next;

   155 	return tmp;

   156     }

   157 

   158     QValueListConstIterator<T>& operator--() {

   159 	node = node->prev;

   160 	return *this;

   161     }

   162 

   163     QValueListConstIterator<T> operator--(int) {

   164 	QValueListConstIterator<T> tmp = *this;

   165 	node = node->prev;

   166 	return tmp;

   167     }

   168 };

   169 

   170 template <class T>

   171 class Q_EXPORT QValueListPrivate : public QShared

   172 {

   173 public:

   174     /**

   175      * Typedefs

   176      */

   177     typedef QValueListIterator<T> Iterator;

   178     typedef QValueListConstIterator<T> ConstIterator;

   179     typedef QValueListNode<T> Node;

   180     typedef QValueListNode<T>* NodePtr;

   181 

   182     /**

   183      * Functions

   184      */

   185     QValueListPrivate() { node = new Node; node->next = node->prev = node; nodes = 0; }

   186     QValueListPrivate( const QValueListPrivate<T>& _p ) : QShared() {

   187 	node = new Node; node->next = node->prev = node; nodes = 0;

   188 	Iterator b( _p.node->next );

   189 	Iterator e( _p.node );

   190 	Iterator i( node );

   191 	while( b != e )

   192 	    insert( i, *b++ );

   193     }

   194 

   195     void derefAndDelete() // ### hack to get around hp-cc brain damage

   196     {

   197 	if ( deref() )

   198 	    delete this;

   199     }

   200 

   201 #if defined(Q_TEMPLATEDLL)

   202     // Workaround MS bug in memory de/allocation in DLL vs. EXE 

   203     virtual

   204 #endif

   205     ~QValueListPrivate() {

   206 	NodePtr p = node->next;

   207 	while( p != node ) {

   208 	    NodePtr x = p->next;

   209 	    delete p;

   210 	    p = x;

   211 	}

   212 	delete node;

   213     }

   214 

   215     Iterator insert( Iterator it, const T& x ) {

   216 	NodePtr p = new Node( x );

   217 	p->next = it.node;

   218 	p->prev = it.node->prev;

   219 	it.node->prev->next = p;

   220 	it.node->prev = p;

   221 	nodes++;

   222 	return p;

   223     }

   224 

   225     Iterator remove( Iterator it ) {

   226 	ASSERT ( it.node != node );

   227 	NodePtr next = it.node->next;

   228 	NodePtr prev = it.node->prev;

   229 	prev->next = next;

   230 	next->prev = prev;

   231 	delete it.node;

   232 	nodes--;

   233 	return Iterator( next );

   234     }

   235 

   236     NodePtr find( NodePtr start, const T& x ) const {

   237 	ConstIterator first( start );

   238 	ConstIterator last( node );

   239 	while( first != last) {

   240 	    if ( *first == x )

   241 		return first.node;

   242 	    ++first;

   243 	}

   244 	return last.node;

   245     }

   246 

   247     int findIndex( NodePtr start, const T& x ) const {

   248 	ConstIterator first( start );

   249 	ConstIterator last( node );

   250 	int pos = 0;

   251 	while( first != last) {

   252 	    if ( *first == x )

   253 		return pos;

   254 	    ++first;

   255 	    ++pos;

   256 	}

   257 	return -1;

   258     }

   259 

   260     uint contains( const T& x ) const {

   261 	uint result = 0;

   262 	Iterator first = Iterator( node->next );

   263 	Iterator last = Iterator( node );

   264 	while( first != last) {

   265 	    if ( *first == x )

   266 		++result;

   267 	    ++first;

   268 	}

   269 	return result;

   270     }

   271 

   272     void remove( const T& x ) {

   273 	Iterator first = Iterator( node->next );

   274 	Iterator last = Iterator( node );

   275 	while( first != last) {

   276 	    if ( *first == x )

   277 		first = remove( first );

   278 	    else

   279 		++first;

   280 	}

   281     }

   282 

   283     NodePtr at( uint i ) const {

   284 	ASSERT( i <= nodes );

   285 	NodePtr p = node->next;

   286 	for( uint x = 0; x < i; ++x )

   287 	    p = p->next;

   288 	return p;

   289     }

   290 

   291     void clear() {

   292 	nodes = 0;

   293 	NodePtr p = node->next;

   294 	while( p != node ) {

   295 	    NodePtr next = p->next;

   296 	    delete p;

   297 	    p = next;

   298 	}

   299 	node->next = node->prev = node;

   300     }

   301 

   302     NodePtr node;

   303     uint nodes;

   304 };

   305 

   306 template <class T>

   307 class Q_EXPORT QValueList

   308 {

   309 public:

   310     /**

   311      * Typedefs

   312      */

   313     typedef QValueListIterator<T> Iterator;

   314     typedef QValueListConstIterator<T> ConstIterator;

   315     typedef T ValueType;

   316 

   317     /**

   318      * API

   319      */

   320     QValueList() { sh = new QValueListPrivate<T>; }

   321     QValueList( const QValueList<T>& l ) { sh = l.sh; sh->ref(); }

   322     ~QValueList() { sh->derefAndDelete(); }

   323 

   324     QValueList<T>& operator= ( const QValueList<T>& l )

   325     {

   326 	l.sh->ref();

   327 	sh->derefAndDelete();

   328 	sh = l.sh;

   329 	return *this;

   330     }

   331 

   332     QValueList<T> operator+ ( const QValueList<T>& l ) const

   333     {

   334 	QValueList<T> l2( *this );

   335 	for( ConstIterator it = l.begin(); it != l.end(); ++it )

   336 	    l2.append( *it );

   337 	return l2;

   338     }

   339 

   340     QValueList<T>& operator+= ( const QValueList<T>& l )

   341     {

   342 	for( ConstIterator it = l.begin(); it != l.end(); ++it )

   343 	    append( *it );

   344 	return *this;

   345     }

   346 

   347     bool operator== ( const QValueList<T>& l ) const

   348     {

   349 	if ( count() != l.count() )

   350 	    return FALSE;

   351 	ConstIterator it2 = begin();

   352 	ConstIterator it = l.begin();

   353 	for( ; it != l.end(); ++it, ++it2 )

   354 	    if ( !( *it == *it2 ) )

   355 		return FALSE;

   356 	return TRUE;

   357     }

   358 

   359     bool operator!= ( const QValueList<T>& l ) const { return !( *this == l ); }

   360 

   361     Iterator begin() { detach(); return Iterator( sh->node->next ); }

   362     ConstIterator begin() const { return ConstIterator( sh->node->next ); }

   363     Iterator end() { detach(); return Iterator( sh->node ); }

   364     ConstIterator end() const { return ConstIterator( sh->node ); }

   365     Iterator fromLast() { detach(); return Iterator( sh->node->prev ); }

   366     ConstIterator fromLast() const { return ConstIterator( sh->node->prev ); }

   367 

   368     bool isEmpty() const { return ( sh->nodes == 0 ); }

   369 

   370     Iterator insert( Iterator it, const T& x ) { detach(); return sh->insert( it, x ); }

   371 

   372     Iterator append( const T& x ) { detach(); return sh->insert( end(), x ); }

   373     Iterator prepend( const T& x ) { detach(); return sh->insert( begin(), x ); }

   374 

   375     Iterator remove( Iterator it ) { detach(); return sh->remove( it ); }

   376     void remove( const T& x ) { detach(); sh->remove( x ); }

   377 

   378     T& first() { detach(); return sh->node->next->data; }

   379     const T& first() const { return sh->node->next->data; }

   380     T& last() { detach(); return sh->node->prev->data; }

   381     const T& last() const { return sh->node->prev->data; }

   382 

   383     T& operator[] ( uint i ) { detach(); return sh->at(i)->data; }

   384     const T& operator[] ( uint i ) const { return sh->at(i)->data; }

   385     Iterator at( uint i ) { detach(); return Iterator( sh->at(i) ); }

   386     ConstIterator at( uint i ) const { return ConstIterator( sh->at(i) ); }

   387     Iterator find ( const T& x ) { detach(); return Iterator( sh->find( sh->node->next, x) ); }

   388     ConstIterator find ( const T& x ) const { return ConstIterator( sh->find( sh->node->next, x) ); }

   389     Iterator find ( Iterator it, const T& x ) { detach(); return Iterator( sh->find( it.node, x ) ); }

   390     ConstIterator find ( ConstIterator it, const T& x ) const { return ConstIterator( sh->find( it.node, x ) ); }

   391     int findIndex( const T& x ) const { return sh->findIndex( sh->node->next, x) ; }

   392     uint contains( const T& x ) const { return sh->contains( x ); }

   393 

   394     uint count() const { return sh->nodes; }

   395 

   396     void clear() { if ( sh->count == 1 ) sh->clear(); else { sh->deref(); sh = new QValueListPrivate<T>; } }

   397 

   398 

   399     QValueList<T>& operator+= ( const T& x )

   400     {

   401 	append( x );

   402 	return *this;

   403     }

   404     QValueList<T>& operator<< ( const T& x )

   405     {

   406 	append( x );

   407 	return *this;

   408     }

   409 

   410 

   411 protected:

   412     /**

   413      * Helpers

   414      */

   415     void detach() { if ( sh->count > 1 ) { sh->deref(); sh = new QValueListPrivate<T>( *sh ); } }

   416 

   417     /**

   418      * Variables

   419      */

   420     QValueListPrivate<T>* sh;

   421 };

   422 

   423 #ifndef QT_NO_DATASTREAM

   424 template<class T>

   425 inline QDataStream& operator>>( QDataStream& s, QValueList<T>& l )

   426 {

   427     l.clear();

   428     Q_UINT32 c;

   429     s >> c;

   430     for( Q_UINT32 i = 0; i < c; ++i )

   431     {

   432 	T t;

   433 	s >> t;

   434 	l.append( t );

   435     }

   436     return s;

   437 }

   438 

   439 template<class T>

   440 inline QDataStream& operator<<( QDataStream& s, const QValueList<T>& l )

   441 {

   442     s << (Q_UINT32)l.count();

   443     QValueListConstIterator<T> it = l.begin();

   444     for( ; it != l.end(); ++it )

   445 	s << *it;

   446     return s;

   447 }

   448 #endif // QT_NO_DATASTREAM

   449 #endif // QVALUELIST_H