QMapPrivate< Key, T > Class Template Reference

#include <qmap.h>

Inheritance diagram for QMapPrivate< Key, T >:

Public Types
typedef QMapIterator< Key, T >	Iterator
typedef QMapConstIterator< Key, T >	ConstIterator
typedef QMapNode< Key, T >	Node
typedef QMapNode< Key, T > *	NodePtr

Public Member Functions
	QMapPrivate ()
	QMapPrivate (const QMapPrivate< Key, T > *_map)
	~QMapPrivate ()
NodePtr	copy (NodePtr p)
void	clear ()
void	clear (NodePtr p)
Iterator	begin ()
Iterator	end ()
ConstIterator	begin () const
ConstIterator	end () const
ConstIterator	find (const Key &k) const
void	remove (Iterator it)
Iterator	insertMulti (const Key &v)
Iterator	insertSingle (const Key &k)
Iterator	insert (QMapNodeBase *x, QMapNodeBase *y, const Key &k)
Public Member Functions inherited from QMapPrivateBase
	QMapPrivateBase ()
	QMapPrivateBase (const QMapPrivateBase *_map)
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)
Public Member Functions inherited from QShared
	QShared ()
void	ref ()
bool	deref ()

Protected Member Functions
const Key &	key (QMapNodeBase *b) const

Protected Attributes
NodePtr	header

Additional Inherited Members
Public Attributes inherited from QMapPrivateBase
int	node_count
Public Attributes inherited from QShared
uint	count

Detailed Description

template<class Key, class T>
class QMapPrivate< Key, T >

Definition at line 311 of file qmap.h.

Member Typedef Documentation

template<class Key, class T>

typedef QMapConstIterator< Key, T > QMapPrivate< Key, T >::ConstIterator

Definition at line 318 of file qmap.h.

template<class Key, class T>

typedef QMapIterator< Key, T > QMapPrivate< Key, T >::Iterator

Typedefs

Definition at line 317 of file qmap.h.

template<class Key, class T>

typedef QMapNode< Key, T > QMapPrivate< Key, T >::Node

Definition at line 319 of file qmap.h.

template<class Key, class T>

typedef QMapNode< Key, T >* QMapPrivate< Key, T >::NodePtr

Definition at line 320 of file qmap.h.

Constructor & Destructor Documentation

template<class Key, class T>

QMapPrivate< Key, T >::QMapPrivate ( )

inline

Functions

Definition at line 325 of file qmap.h.

                  {
        header = new Node;
        header->color = QMapNodeBase::Red; // Mark the header
        header->parent = 0;
        header->left = header->right = header;
    }

template<class Key, class T>

QMapPrivate< Key, T >::QMapPrivate ( const QMapPrivate< Key, T > *  _map )

inline

Definition at line 331 of file qmap.h.

                                                     : QMapPrivateBase( _map ) {
        header = new Node;
        header->color = QMapNodeBase::Red; // Mark the header
        if ( _map->header->parent == 0 ) {
            header->parent = 0;
            header->left = header->right = header;
        } else {
            header->parent = copy( (NodePtr)(_map->header->parent) );
            header->parent->parent = header;
            header->left = header->parent->minimum();
            header->right = header->parent->maximum();
        }
    }

template<class Key, class T>

QMapPrivate< Key, T >::~QMapPrivate ( )

inline

Definition at line 344 of file qmap.h.

{ clear(); delete header; }

Member Function Documentation

template<class Key, class T>

Iterator QMapPrivate< Key, T >::begin ( )

inline

Definition at line 383 of file qmap.h.

{ return Iterator( (NodePtr)(header->left ) ); }

template<class Key, class T>

ConstIterator QMapPrivate< Key, T >::begin ( ) const

inline

Definition at line 385 of file qmap.h.

{ return ConstIterator( (NodePtr)(header->left ) ); }

template<class Key, class T>

void QMapPrivate< Key, T >::clear ( )

inline

Definition at line 366 of file qmap.h.

                 {
        clear( (NodePtr)(header->parent) );
        header->color = QMapNodeBase::Red;
        header->parent = 0;
        header->left = header->right = header;
        node_count = 0;
    }

template<class Key, class T>

void QMapPrivate< Key, T >::clear ( NodePtr  p )

inline

Definition at line 374 of file qmap.h.

                            {
        while ( p != 0 ) {
            clear( (NodePtr)p->right );
            NodePtr y = (NodePtr)p->left;
            delete p;
            p = y;
        }
    }

template<class Key, class T>

NodePtr QMapPrivate< Key, T >::copy ( NodePtr  p )

inline

Definition at line 346 of file qmap.h.

                              {
        if ( !p )
            return 0;
        NodePtr n = new Node( *p );
        n->color = p->color;
        if ( p->left ) {
            n->left = copy( (NodePtr)(p->left) );
            n->left->parent = n;
        } else {
            n->left = 0;
        }
        if ( p->right ) {
            n->right = copy( (NodePtr)(p->right) );
            n->right->parent = n;
        } else {
            n->right = 0;
        }
        return n;
    }

template<class Key, class T>

Iterator QMapPrivate< Key, T >::end ( )

inline

Definition at line 384 of file qmap.h.

{ return Iterator( header ); }

template<class Key, class T>

ConstIterator QMapPrivate< Key, T >::end ( ) const

inline

Definition at line 386 of file qmap.h.

{ return ConstIterator( header ); }

template<class Key, class T>

ConstIterator QMapPrivate< Key, T >::find ( const Key &  k ) const

inline

Definition at line 388 of file qmap.h.

                                           {
        QMapNodeBase* y = header;        // Last node
        QMapNodeBase* x = header->parent; // Root node.

        while ( x != 0 ) {
            // If as k <= key(x) go left
            if ( !( key(x) < k ) ) {
                y = x;
                x = x->left;
            } else {
                x = x->right;
            }
        }

        // Was k bigger/smaller then the biggest/smallest
        // element of the tree ? Return end()
        if ( y == header || k < key(y) )
            return ConstIterator( header );
        return ConstIterator( (NodePtr)y );
    }

template<class Key, class T>

Iterator QMapPrivate< Key, T >::insert ( QMapNodeBase *  x, QMapNodeBase *  y, const Key &  k  )

inline

Definition at line 465 of file qmap.h.

                                                                      {
        NodePtr z = new Node( k );
        if (y == header || x != 0 || k < key(y) ) {
            y->left = z;                // also makes leftmost = z when y == header
            if ( y == header ) {
                header->parent = z;
                header->right = z;
            } else if ( y == header->left )
                header->left = z;           // maintain leftmost pointing to min node
        } else {
            y->right = z;
            if ( y == header->right )
                header->right = z;          // maintain rightmost pointing to max node
        }
        z->parent = y;
        z->left = 0;
        z->right = 0;
        rebalance( z, header->parent );
        ++node_count;
        return Iterator(z);
    }

template<class Key, class T>

Iterator QMapPrivate< Key, T >::insertMulti ( const Key &  v )

inline

Definition at line 427 of file qmap.h.

                                      {
        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);
    }

template<class Key, class T>

Iterator QMapPrivate< Key, T >::insertSingle ( const Key &  k )

inline

Definition at line 437 of file qmap.h.

                                          {
        // Search correct position in the tree
        QMapNodeBase* y = header;
        QMapNodeBase* x = header->parent;
        bool result = TRUE;
        while ( x != 0 ) {
            result = ( k < key(x) );
            y = x;
            x = result ? x->left : x->right;
        }
        // Get iterator on the last not empty one
        Iterator j( (NodePtr)y );
        if ( result ) {
            // Smaller then the leftmost one ?
            if ( j == begin() ) {
                return insert(x, y, k );
            } else {
                // Perhaps daddy is the right one ?
                --j;
            }
        }
        // Really bigger ?
        if ( (j.node->key) < k )
            return insert(x, y, k );
        // We are going to replace a node
        return j;
    }

template<class Key, class T>

const Key& QMapPrivate< Key, T >::key ( QMapNodeBase *  b ) const

inlineprotected

Helpers

Definition at line 491 of file qmap.h.

{ return ((NodePtr)b)->key; }

template<class Key, class T>

void QMapPrivate< Key, T >::remove ( Iterator  it )

inline

Definition at line 409 of file qmap.h.

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

Member Data Documentation

template<class Key, class T>

NodePtr QMapPrivate< Key, T >::header

protected

Variables

Definition at line 496 of file qmap.h.

---

The documentation for this class was generated from the following file:

• doxygen-1.8.11/qtools/qmap.h