qmap.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 QMAP_H
#define QMAP_H

#ifndef QT_H
#include "qglobal.h"
#include "qshared.h"
#include "qdatastream.h"
#include "qpair.h"
#include "qvaluelist.h"
#endif // QT_H

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

//#define QT_CHECK_MAP_RANGE

struct Q_EXPORT QMapNodeBase
{
    enum Color { Red, Black };

    QMapNodeBase* left;
    QMapNodeBase* right;
    QMapNodeBase* parent;

    Color color;

    QMapNodeBase* minimum() {
	QMapNodeBase* x = this;
	while ( x->left )
	    x = x->left;
	return x;
    }

    QMapNodeBase* maximum() {
	QMapNodeBase* x = this;
	while ( x->right )
	    x = x->right;
	return x;
    }
};


template <class K, class T>
struct QMapNode : public QMapNodeBase
{
    QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }
    QMapNode( const K& _key )	   { key = _key; }
    QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }
    QMapNode() { }
    T data;
    K key;
};


template<class K, class T>
class QMapIterator
{
 public:
    /**
     * Typedefs
     */
    typedef QMapNode< K, T >* NodePtr;
#ifndef QT_NO_STL
    typedef std::bidirectional_iterator_tag  iterator_category;
#endif
    typedef T          value_type;
#ifndef QT_NO_STL
    typedef ptrdiff_t  difference_type;
#else
    typedef int difference_type;
#endif
    typedef T*         pointer;
    typedef T&         reference;

    /**
     * Variables
     */
    QMapNode<K,T>* node;

    /**
     * Functions
     */
    QMapIterator() : node( 0 ) {}
    QMapIterator( QMapNode<K,T>* p ) : node( p ) {}
    QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}

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

    const K& key() const { return node->key; }
    T& data() { return node->data; }
    const T& data() const { return node->data; }

private:
    int inc();
    int dec();

public:
    QMapIterator<K,T>& operator++() {
	inc();
	return *this;
    }

    QMapIterator<K,T> operator++(int) {
	QMapIterator<K,T> tmp = *this;
	inc();
	return tmp;
    }

    QMapIterator<K,T>& operator--() {
	dec();
	return *this;
    }

    QMapIterator<K,T> operator--(int) {
	QMapIterator<K,T> tmp = *this;
	dec();
	return tmp;
    }
};

template <class K, class T>
Q_INLINE_TEMPLATES int QMapIterator<K,T>::inc()
{
    QMapNodeBase* tmp = node;
    if ( tmp->right ) {
	tmp = tmp->right;
	while ( tmp->left )
	    tmp = tmp->left;
    } else {
	QMapNodeBase* y = tmp->parent;
	while (tmp == y->right) {
	    tmp = y;
	    y = y->parent;
	}
	if (tmp->right != y)
	    tmp = y;
    }
    node = (NodePtr)tmp;
    return 0;
}

template <class K, class T>
Q_INLINE_TEMPLATES int QMapIterator<K,T>::dec()
{
    QMapNodeBase* tmp = node;
    if (tmp->color == QMapNodeBase::Red &&
	tmp->parent->parent == tmp ) {
	tmp = tmp->right;
    } else if (tmp->left != 0) {
	QMapNodeBase* y = tmp->left;
	while ( y->right )
	    y = y->right;
	tmp = y;
    } else {
	QMapNodeBase* y = tmp->parent;
	while (tmp == y->left) {
	    tmp = y;
	    y = y->parent;
	}
	tmp = y;
    }
    node = (NodePtr)tmp;
    return 0;
}

template<class K, class T>
class QMapConstIterator
{
 public:
    /**
     * Typedefs
     */
    typedef QMapNode< K, T >* NodePtr;
#ifndef QT_NO_STL
    typedef std::bidirectional_iterator_tag  iterator_category;
#endif
    typedef T          value_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
     */
    QMapNode<K,T>* node;

    /**
     * Functions
     */
    QMapConstIterator() : node( 0 ) {}
    QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}
    QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}
    QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}

    bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }
    bool operator!=( const QMapConstIterator<K,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; }

    const K& key() const { return node->key; }
    const T& data() const { return node->data; }

private:
    int inc();
    int dec();

public:
    QMapConstIterator<K,T>& operator++() {
	inc();
	return *this;
    }

    QMapConstIterator<K,T> operator++(int) {
	QMapConstIterator<K,T> tmp = *this;
	inc();
	return tmp;
    }

    QMapConstIterator<K,T>& operator--() {
	dec();
	return *this;
    }

    QMapConstIterator<K,T> operator--(int) {
	QMapConstIterator<K,T> tmp = *this;
	dec();
	return tmp;
    }
};

template <class K, class T>
Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::inc()
{
    QMapNodeBase* tmp = node;
    if ( tmp->right ) {
	tmp = tmp->right;
	while ( tmp->left )
	    tmp = tmp->left;
    } else {
	QMapNodeBase* y = tmp->parent;
	while (tmp == y->right) {
	    tmp = y;
	    y = y->parent;
	}
	if (tmp->right != y)
	    tmp = y;
    }
    node = (NodePtr)tmp;
    return 0;
}

template <class K, class T>
Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::dec()
{
    QMapNodeBase* tmp = node;
    if (tmp->color == QMapNodeBase::Red &&
	tmp->parent->parent == tmp ) {
	tmp = tmp->right;
    } else if (tmp->left != 0) {
	QMapNodeBase* y = tmp->left;
	while ( y->right )
	    y = y->right;
	tmp = y;
    } else {
	QMapNodeBase* y = tmp->parent;
	while (tmp == y->left) {
	    tmp = y;
	    y = y->parent;
	}
	tmp = y;
    }
    node = (NodePtr)tmp;
    return 0;
}

// ### 4.0: rename to something without Private in it. Not really internal.
class Q_EXPORT QMapPrivateBase : public QShared
{
public:
    QMapPrivateBase() {
	node_count = 0;
    }
    QMapPrivateBase( const QMapPrivateBase* _map) {
	node_count = _map->node_count;
    }

    /**
     * Implementations of basic tree algorithms
     */
    void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);
    void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );
    void rebalance( QMapNodeBase* x, QMapNodeBase*& root );
    QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,
				      QMapNodeBase*& leftmost,
				      QMapNodeBase*& rightmost );

    /**
     * Variables
     */
    int node_count;
};


template <class Key, class T>
class QMapPrivate : public QMapPrivateBase
{
public:
    /**
     * Typedefs
     */
    typedef QMapIterator< Key, T > Iterator;
    typedef QMapConstIterator< Key, T > ConstIterator;
    typedef QMapNode< Key, T > Node;
    typedef QMapNode< Key, T >* NodePtr;

    /**
     * Functions
     */
    QMapPrivate();
    QMapPrivate( const QMapPrivate< Key, T >* _map );
    ~QMapPrivate() { clear(); delete header; }

    NodePtr copy( NodePtr p );
    void clear();
    void clear( NodePtr p );

    Iterator begin()	{ return Iterator( (NodePtr)(header->left ) ); }
    Iterator end()	{ return Iterator( header ); }
    ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }
    ConstIterator end() const { return ConstIterator( header ); }

    ConstIterator find(const Key& k) const;

    void remove( Iterator it ) {
	NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );
	delete del;
	--node_count;
    }

#ifdef QT_QMAP_DEBUG
    void inorder( QMapNodeBase* x = 0, int level = 0 ){
	if ( !x )
	    x = header->parent;
	if ( x->left )
	    inorder( x->left, level + 1 );
    //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
	if ( x->right )
	    inorder( x->right, level + 1 );
    }
#endif

#if 0
    Iterator insertMulti(const Key& v){
	QMapNodeBase* y = header;
	QMapNodeBase* x = header->parent;
	while (x != 0){
	    y = x;
	    x = ( v < key(x) ) ? x->left : x->right;
	}
	return insert(x, y, v);
    }
#endif

    Iterator insertSingle( const Key& k );
    Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k );

protected:
    /**
     * Helpers
     */
    const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }

    /**
     * Variables
     */
    NodePtr header;
};


template <class Key, class T>
Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate() {
    header = new Node;
    header->color = QMapNodeBase::Red; // Mark the header
    header->parent = 0;
    header->left = header->right = header;
}
template <class Key, class T>
Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {