qvaluelist.h

Trolltech公司发布的图形界面操作系统。可在qt-embedded-2.3.10平台上编译为嵌入式图形界面操作系统。

/**********************************************************************
** Copyright (C) 2000-2005 Trolltech AS.  All rights reserved.
**
** This file is part of the Qtopia Environment.
** 
** This program is free software; you can redistribute it and/or modify it
** under the terms of the GNU General Public License as published by the
** Free Software Foundation; either version 2 of the License, or (at your
** option) any later version.
** 
** A copy of the GNU GPL license version 2 is included in this package as 
** LICENSE.GPL.
**
** This program is distributed in the hope that it will be useful, but
** WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
** See the GNU General Public License for more details.
**
** In addition, as a special exception Trolltech gives permission to link
** the code of this program with Qtopia applications copyrighted, developed
** and distributed by Trolltech under the terms of the Qtopia Personal Use
** License Agreement. You must comply with the GNU General Public License
** in all respects for all of the code used other than the applications
** licensed under the Qtopia Personal Use License Agreement. If you modify
** this file, you may extend this exception to your version of the file,
** but you are not obligated to do so. If you do not wish to do so, delete
** this exception statement from your version.
** 
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact [e-mail] if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/

#ifndef QVALUELIST_H
#define QVALUELIST_H

#ifndef QT_H
#include "qtl.h"
#include "qshared.h"
#include "qdatastream.h"
#endif // QT_H

#ifndef QT_NO_STL
#include <iterator>
#include <list>
#endif

//#define QT_CHECK_VALUELIST_RANGE

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

template <class T>
class QValueListNode
{
public:
    QValueListNode( const T& t ) : data( t ) { }
    QValueListNode() { }
#if defined(Q_TEMPLATEDLL)
    // Workaround MS bug in memory de/allocation in DLL vs. EXE
    virtual ~QValueListNode() { }
#endif

    QValueListNode<T>* next;
    QValueListNode<T>* prev;
    T data;
};

template<class T>
class QValueListIterator
{
 public:
    /**
     * Typedefs
     */
    typedef QValueListNode<T>* NodePtr;
#ifndef QT_NO_STL
    typedef std::bidirectional_iterator_tag  iterator_category;
#endif
    typedef T        value_type;
    typedef size_t size_type;
#ifndef QT_NO_STL
    typedef ptrdiff_t  difference_type;
#else
    typedef int difference_type;
#endif
    typedef T*   pointer;
    typedef T& reference;

    /**
     * Variables
     */
    NodePtr node;

    /**
     * Functions
     */
    QValueListIterator() : node( 0 ) {}
    QValueListIterator( NodePtr p ) : node( p ) {}
    QValueListIterator( const QValueListIterator<T>& it ) : node( it.node ) {}

    bool operator==( const QValueListIterator<T>& it ) const { return node == it.node; }
    bool operator!=( const QValueListIterator<T>& it ) const { return node != it.node; }
    const T& operator*() const { return node->data; }
    T& operator*() { return node->data; }
    // UDT for T = x*
    // T* operator->() const { return &node->data; }

    QValueListIterator<T>& operator++() {
	node = node->next;
	return *this;
    }

    QValueListIterator<T> operator++(int) {
	QValueListIterator<T> tmp = *this;
	node = node->next;
	return tmp;
    }

    QValueListIterator<T>& operator--() {
	node = node->prev;
	return *this;
    }

    QValueListIterator<T> operator--(int) {
	QValueListIterator<T> tmp = *this;
	node = node->prev;
	return tmp;
    }

    QValueListIterator<T>& operator+=( int j ) {
	while ( j-- )
	    node = node->next;
	return *this;
    }

    QValueListIterator<T>& operator-=( int j ) {
	while ( j-- )
	    node = node->prev;
	return *this;
    }

};

template<class T>
class QValueListConstIterator
{
 public:
    /**
     * Typedefs
     */
    typedef QValueListNode<T>* NodePtr;
#ifndef QT_NO_STL
    typedef std::bidirectional_iterator_tag  iterator_category;
#endif
    typedef T        value_type;
    typedef size_t size_type;
#ifndef QT_NO_STL
    typedef ptrdiff_t  difference_type;
#else
    typedef int difference_type;
#endif
    typedef const T*   pointer;
    typedef const T& reference;

    /**
     * Variables
     */
    NodePtr node;

    /**
     * Functions
     */
    QValueListConstIterator() : node( 0 ) {}
    QValueListConstIterator( NodePtr p ) : node( p ) {}
    QValueListConstIterator( const QValueListConstIterator<T>& it ) : node( it.node ) {}
    QValueListConstIterator( const QValueListIterator<T>& it ) : node( it.node ) {}

    bool operator==( const QValueListConstIterator<T>& it ) const { return node == it.node; }
    bool operator!=( const QValueListConstIterator<T>& it ) const { return node != it.node; }
    const T& operator*() const { return node->data; }
    // UDT for T = x*
    // const T* operator->() const { return &node->data; }

    QValueListConstIterator<T>& operator++() {
	node = node->next;
	return *this;
    }

    QValueListConstIterator<T> operator++(int) {
	QValueListConstIterator<T> tmp = *this;
	node = node->next;
	return tmp;
    }

    QValueListConstIterator<T>& operator--() {
	node = node->prev;
	return *this;
    }

    QValueListConstIterator<T> operator--(int) {
	QValueListConstIterator<T> tmp = *this;
	node = node->prev;
	return tmp;
    }
};

template <class T>
class QValueListPrivate : public QShared
{
public:
    /**
     * Typedefs
     */
    typedef QValueListIterator<T> Iterator;
    typedef QValueListConstIterator<T> ConstIterator;
    typedef QValueListNode<T> Node;
    typedef QValueListNode<T>* NodePtr;
    typedef size_t size_type;

    /**
     * Functions
     */
    QValueListPrivate();
    QValueListPrivate( const QValueListPrivate<T>& _p );

    void derefAndDelete() // ### hack to get around hp-cc brain damage
    {
	if ( deref() )
	    delete this;
    }

#if defined(Q_TEMPLATEDLL)
    // Workaround MS bug in memory de/allocation in DLL vs. EXE
    virtual
#endif
    ~QValueListPrivate();

    Iterator insert( Iterator it, const T& x );
    Iterator remove( Iterator it );
    NodePtr find( NodePtr start, const T& x ) const;
    int findIndex( NodePtr start, const T& x ) const;
    uint contains( const T& x ) const;
    uint remove( const T& x );
    NodePtr at( size_type i ) const;
    void clear();

    NodePtr node;
    size_type nodes;
};

template <class T>
Q_INLINE_TEMPLATES QValueListPrivate<T>::QValueListPrivate()
{
    node = new Node; node->next = node->prev = node; nodes = 0;
}

template <class T>
Q_INLINE_TEMPLATES QValueListPrivate<T>::QValueListPrivate( const QValueListPrivate<T>& _p )
    : QShared()
{
    node = new Node; node->next = node->prev = node; nodes = 0;
    Iterator b( _p.node->next );
    Iterator e( _p.node );
    Iterator i( node );
    while( b != e )
	insert( i, *b++ );
}

template <class T>
Q_INLINE_TEMPLATES QValueListPrivate<T>::~QValueListPrivate() {
    NodePtr p = node->next;
    while( p != node ) {
	NodePtr x = p->next;
	delete p;
	p = x;
    }
    delete node;
}

template <class T>
Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::Iterator QValueListPrivate<T>::insert( Q_TYPENAME QValueListPrivate<T>::Iterator it, const T& x )
{
    NodePtr p = new Node( x );
    p->next = it.node;
    p->prev = it.node->prev;
    it.node->prev->next = p;
    it.node->prev = p;
    nodes++;
    return p;
}

template <class T>
Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::Iterator QValueListPrivate<T>::remove( Q_TYPENAME QValueListPrivate<T>::Iterator it )
{
    Q_ASSERT ( it.node != node );
    NodePtr next = it.node->next;
    NodePtr prev = it.node->prev;
    prev->next = next;
    next->prev = prev;
    delete it.node;
    nodes--;
    return Iterator( next );
}

template <class T>
Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::NodePtr QValueListPrivate<T>::find( Q_TYPENAME QValueListPrivate<T>::NodePtr start, const T& x ) const
{
    ConstIterator first( start );
    ConstIterator last( node );
    while( first != last) {
	if ( *first == x )
	    return first.node;
	++first;
    }
    return last.node;
}

template <class T>
Q_INLINE_TEMPLATES int QValueListPrivate<T>::findIndex( Q_TYPENAME QValueListPrivate<T>::NodePtr start, const T& x ) const
{
    ConstIterator first( start );
    ConstIterator last( node );
    int pos = 0;
    while( first != last) {
	if ( *first == x )
	    return pos;
	++first;
	++pos;