Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qmap.h

Source at commit 1322 created 12 years 8 months ago.
By meklort, Add doxygen to utils folder
1/****************************************************************************␊
2** ␊
3**␊
4** Definition of QMap 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 QMAP_H␊
39#define QMAP_H␊
40␊
41#ifndef QT_H␊
42#include "qshared.h"␊
43#include "qdatastream.h"␊
44#endif // QT_H␊
45␊
46␊
47struct QMapNodeBase␊
48{␊
49 enum Color { Red, Black };␊
50␊
51 QMapNodeBase* left;␊
52 QMapNodeBase* right;␊
53 QMapNodeBase* parent;␊
54␊
55 Color color;␊
56␊
57 QMapNodeBase* minimum() {␊
58␉QMapNodeBase* x = this;␊
59␉while ( x->left )␊
60␉ x = x->left;␊
61␉return x;␊
62 }␊
63␊
64 QMapNodeBase* maximum() {␊
65␉QMapNodeBase* x = this;␊
66␉while ( x->right )␊
67␉ x = x->right;␊
68␉return x;␊
69 }␊
70};␊
71␊
72␊
73template <class K, class T>␊
74struct QMapNode : public QMapNodeBase␊
75{␊
76 QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }␊
77 QMapNode( const K& _key )␉ { key = _key; }␊
78 QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }␊
79 QMapNode() { }␊
80 T data;␊
81 K key;␊
82};␊
83␊
84␊
85template<class K, class T>␊
86class Q_EXPORT QMapIterator␊
87{␊
88 public:␊
89 /**␊
90 * Typedefs␊
91 */␊
92 typedef QMapNode< K, T >* NodePtr;␊
93␊
94 /**␊
95 * Variables␊
96 */␊
97 QMapNode<K,T>* node;␊
98␊
99 /**␊
100 * Functions␊
101 */␊
102 QMapIterator() : node( 0 ) {}␊
103 QMapIterator( QMapNode<K,T>* p ) : node( p ) {}␊
104 QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}␊
105␊
106 bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }␊
107 bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }␊
108 T& operator*() { return node->data; }␊
109 const T& operator*() const { return node->data; }␊
110␊
111 // Cannot have this - some compilers are too stupid␊
112 //T* operator->() const { return &(node->data); }␊
113␊
114 const K& key() const { return node->key; }␊
115 T& data() { return node->data; }␊
116 const T& data() const { return node->data; }␊
117␊
118private:␊
119 int inc() {␊
120␉QMapNodeBase* tmp = node;␊
121␉if ( tmp->right ) {␊
122␉ tmp = tmp->right;␊
123␉ while ( tmp->left )␊
124␉␉tmp = tmp->left;␊
125␉} else {␊
126␉ QMapNodeBase* y = tmp->parent;␊
127␉ while (tmp == y->right) {␊
128␉␉tmp = y;␊
129␉␉y = y->parent;␊
130␉ }␊
131␉ if (tmp->right != y)␊
132␉␉tmp = y;␊
133␉}␊
134␉node = (NodePtr)tmp;␊
135␉return 0;␊
136 }␊
137␊
138 int dec() {␊
139␉QMapNodeBase* tmp = node;␊
140␉if (tmp->color == QMapNodeBase::Red &&␊
141␉ tmp->parent->parent == tmp ) {␊
142␉ tmp = tmp->right;␊
143␉} else if (tmp->left != 0) {␊
144␉ QMapNodeBase* y = tmp->left;␊
145␉ while ( y->right )␊
146␉␉y = y->right;␊
147␉ tmp = y;␊
148␉} else {␊
149␉ QMapNodeBase* y = tmp->parent;␊
150␉ while (tmp == y->left) {␊
151␉␉tmp = y;␊
152␉␉y = y->parent;␊
153␉ }␊
154␉ tmp = y;␊
155␉}␊
156␉node = (NodePtr)tmp;␊
157␉return 0;␊
158 }␊
159␊
160public:␊
161 QMapIterator<K,T>& operator++() {␊
162␉inc();␊
163␉return *this;␊
164 }␊
165␊
166 QMapIterator<K,T> operator++(int) {␊
167␉QMapIterator<K,T> tmp = *this;␊
168␉inc();␊
169␉return tmp;␊
170 }␊
171␊
172 QMapIterator<K,T>& operator--() {␊
173␉dec();␊
174␉return *this;␊
175 }␊
176␊
177 QMapIterator<K,T> operator--(int) {␊
178␉QMapIterator<K,T> tmp = *this;␊
179␉dec();␊
180␉return tmp;␊
181 }␊
182};␊
183␊
184template<class K, class T>␊
185class Q_EXPORT QMapConstIterator␊
186{␊
187 public:␊
188 /**␊
189 * Typedefs␊
190 */␊
191 typedef QMapNode< K, T >* NodePtr;␊
192␊
193 /**␊
194 * Variables␊
195 */␊
196 QMapNode<K,T>* node;␊
197␊
198 /**␊
199 * Functions␊
200 */␊
201 QMapConstIterator() : node( 0 ) {}␊
202 QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}␊
203 QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}␊
204 QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}␊
205␊
206 bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }␊
207 bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }␊
208 const T& operator*() const { return node->data; }␊
209␊
210 // Cannot have this - some compilers are too stupid␊
211 //const T* operator->() const { return &(node->data); }␊
212␊
213 const K& key() const { return node->key; }␊
214 const T& data() const { return node->data; }␊
215␊
216private:␊
217 int inc() {␊
218 QMapNodeBase* tmp = node;␊
219␉if ( tmp->right ) {␊
220␉ tmp = tmp->right;␊
221␉ while ( tmp->left )␊
222␉␉tmp = tmp->left;␊
223␉} else {␊
224␉ QMapNodeBase* y = tmp->parent;␊
225␉ while (tmp == y->right) {␊
226␉␉tmp = y;␊
227␉␉y = y->parent;␊
228␉ }␊
229␉ if (tmp->right != y)␊
230␉␉tmp = y;␊
231␉}␊
232␉node = (NodePtr)tmp;␊
233␉return 0;␊
234 }␊
235␊
236 int dec() {␊
237␉QMapNodeBase* tmp = node;␊
238␉if (tmp->color == QMapNodeBase::Red &&␊
239␉ tmp->parent->parent == tmp ) {␊
240␉ tmp = tmp->right;␊
241␉} else if (tmp->left != 0) {␊
242␉ QMapNodeBase* y = tmp->left;␊
243␉ while ( y->right )␊
244␉␉y = y->right;␊
245␉ tmp = y;␊
246␉} else {␊
247␉ QMapNodeBase* y = tmp->parent;␊
248␉ while (tmp == y->left) {␊
249␉␉tmp = y;␊
250␉␉y = y->parent;␊
251␉ }␊
252␉ tmp = y;␊
253␉}␊
254␉node = (NodePtr)tmp;␊
255␉return 0;␊
256 }␊
257␊
258public:␊
259 QMapConstIterator<K,T>& operator++() {␊
260␉inc();␊
261␉return *this;␊
262 }␊
263␊
264 QMapConstIterator<K,T> operator++(int) {␊
265␉QMapConstIterator<K,T> tmp = *this;␊
266␉inc();␊
267␉return tmp;␊
268 }␊
269␊
270 QMapConstIterator<K,T>& operator--() {␊
271␉dec();␊
272␉return *this;␊
273 }␊
274␊
275 QMapConstIterator<K,T> operator--(int) {␊
276␉QMapConstIterator<K,T> tmp = *this;␊
277␉dec();␊
278␉return tmp;␊
279 }␊
280};␊
281␊
282␊
283class Q_EXPORT QMapPrivateBase : public QShared␊
284{␊
285public:␊
286 QMapPrivateBase() {␊
287␉node_count = 0;␊
288 }␊
289 QMapPrivateBase( const QMapPrivateBase* _map) {␊
290␉node_count = _map->node_count;␊
291 }␊
292␊
293 /**␊
294 * Implementations of basic tree algorithms␊
295 */␊
296 void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);␊
297 void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );␊
298 void rebalance( QMapNodeBase* x, QMapNodeBase*& root );␊
299 QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,␊
300␉␉␉␉ QMapNodeBase*& leftmost,␊
301␉␉␉␉ QMapNodeBase*& rightmost );␊
302␊
303 /**␊
304 * Variables␊
305 */␊
306 int node_count;␊
307};␊
308␊
309␊
310template <class Key, class T>␊
311class QMapPrivate : public QMapPrivateBase␊
312{␊
313public:␊
314 /**␊
315 * Typedefs␊
316 */␊
317 typedef QMapIterator< Key, T > Iterator;␊
318 typedef QMapConstIterator< Key, T > ConstIterator;␊
319 typedef QMapNode< Key, T > Node;␊
320 typedef QMapNode< Key, T >* NodePtr;␊
321␊
322 /**␊
323 * Functions␊
324 */␊
325 QMapPrivate() {␊
326␉header = new Node;␊
327␉header->color = QMapNodeBase::Red; // Mark the header␊
328␉header->parent = 0;␊
329␉header->left = header->right = header;␊
330 }␊
331 QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {␊
332␉header = new Node;␊
333␉header->color = QMapNodeBase::Red; // Mark the header␊
334␉if ( _map->header->parent == 0 ) {␊
335␉ header->parent = 0;␊
336␉ header->left = header->right = header;␊
337␉} else {␊
338␉ header->parent = copy( (NodePtr)(_map->header->parent) );␊
339␉ header->parent->parent = header;␊
340␉ header->left = header->parent->minimum();␊
341␉ header->right = header->parent->maximum();␊
342␉}␊
343 }␊
344 ~QMapPrivate() { clear(); delete header; }␊
345␊
346 NodePtr copy( NodePtr p ) {␊
347␉if ( !p )␊
348␉ return 0;␊
349␉NodePtr n = new Node( *p );␊
350␉n->color = p->color;␊
351␉if ( p->left ) {␊
352␉ n->left = copy( (NodePtr)(p->left) );␊
353␉ n->left->parent = n;␊
354␉} else {␊
355␉ n->left = 0;␊
356␉}␊
357␉if ( p->right ) {␊
358␉ n->right = copy( (NodePtr)(p->right) );␊
359␉ n->right->parent = n;␊
360␉} else {␊
361␉ n->right = 0;␊
362␉}␊
363␉return n;␊
364 }␊
365␊
366 void clear() {␊
367␉clear( (NodePtr)(header->parent) );␊
368␉header->color = QMapNodeBase::Red;␊
369␉header->parent = 0;␊
370␉header->left = header->right = header;␊
371␉node_count = 0;␊
372 }␊
373␊
374 void clear( NodePtr p ) {␊
375␉while ( p != 0 ) {␊
376␉ clear( (NodePtr)p->right );␊
377␉ NodePtr y = (NodePtr)p->left;␊
378␉ delete p;␊
379␉ p = y;␊
380␉}␊
381 }␊
382␊
383 Iterator begin()␉{ return Iterator( (NodePtr)(header->left ) ); }␊
384 Iterator end()␉{ return Iterator( header ); }␊
385 ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }␊
386 ConstIterator end() const { return ConstIterator( header ); }␊
387␊
388 ConstIterator find(const Key& k) const {␊
389␉QMapNodeBase* y = header; // Last node␊
390␉QMapNodeBase* x = header->parent; // Root node.␊
391␊
392␉while ( x != 0 ) {␊
393␉ // If as k <= key(x) go left␊
394␉ if ( !( key(x) < k ) ) {␊
395␉␉y = x;␊
396␉␉x = x->left;␊
397␉ } else {␊
398␉␉x = x->right;␊
399␉ }␊
400␉}␊
401␊
402␉// Was k bigger/smaller then the biggest/smallest␊
403␉// element of the tree ? Return end()␊
404␉if ( y == header || k < key(y) )␊
405␉ return ConstIterator( header );␊
406␉return ConstIterator( (NodePtr)y );␊
407 }␊
408␊
409 void remove( Iterator it ) {␊
410␉NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );␊
411␉delete del;␊
412␉--node_count;␊
413 }␊
414␊
415#ifdef QT_QMAP_DEBUG␊
416 void inorder( QMapNodeBase* x = 0, int level = 0 ){␊
417␉if ( !x )␊
418␉ x = header->parent;␊
419␉if ( x->left )␊
420␉ inorder( x->left, level + 1 );␊
421 //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;␊
422␉if ( x->right )␊
423␉ inorder( x->right, level + 1 );␊
424 }␊
425#endif␊
426␊
427 Iterator insertMulti(const Key& v){␊
428␉QMapNodeBase* y = header;␊
429␉QMapNodeBase* x = header->parent;␊
430␉while (x != 0){␊
431␉ y = x;␊
432␉ x = ( v < key(x) ) ? x->left : x->right;␊
433␉}␊
434␉return insert(x, y, v);␊
435 }␊
436␊
437 Iterator insertSingle( const Key& k ) {␊
438␉// Search correct position in the tree␊
439␉QMapNodeBase* y = header;␊
440␉QMapNodeBase* x = header->parent;␊
441␉bool result = TRUE;␊
442␉while ( x != 0 ) {␊
443␉ result = ( k < key(x) );␊
444␉ y = x;␊
445␉ x = result ? x->left : x->right;␊
446␉}␊
447␉// Get iterator on the last not empty one␊
448␉Iterator j( (NodePtr)y );␊
449␉if ( result ) {␊
450␉ // Smaller then the leftmost one ?␊
451␉ if ( j == begin() ) {␊
452␉␉return insert(x, y, k );␊
453␉ } else {␊
454␉␉// Perhaps daddy is the right one ?␊
455␉␉--j;␊
456␉ }␊
457␉}␊
458␉// Really bigger ?␊
459␉if ( (j.node->key) < k )␊
460␉ return insert(x, y, k );␊
461␉// We are going to replace a node␊
462␉return j;␊
463 }␊
464␊
465 Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k ) {␊
466␉NodePtr z = new Node( k );␊
467␉if (y == header || x != 0 || k < key(y) ) {␊
468␉ y->left = z; // also makes leftmost = z when y == header␊
469␉ if ( y == header ) {␊
470␉␉header->parent = z;␊
471␉␉header->right = z;␊
472␉ } else if ( y == header->left )␊
473␉␉header->left = z; // maintain leftmost pointing to min node␊
474␉} else {␊
475␉ y->right = z;␊
476␉ if ( y == header->right )␊
477␉␉header->right = z; // maintain rightmost pointing to max node␊
478␉}␊
479␉z->parent = y;␊
480␉z->left = 0;␊
481␉z->right = 0;␊
482␉rebalance( z, header->parent );␊
483␉++node_count;␊
484␉return Iterator(z);␊
485 }␊
486␊
487protected:␊
488 /**␊
489 * Helpers␊
490 */␊
491 const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }␊
492␊
493 /**␊
494 * Variables␊
495 */␊
496 NodePtr header;␊
497};␊
498␊
499␊
500template<class Key, class T>␊
501class Q_EXPORT QMap␊
502{␊
503public:␊
504 /**␊
505 * Typedefs␊
506 */␊
507 typedef QMapIterator< Key, T > Iterator;␊
508 typedef QMapConstIterator< Key, T > ConstIterator;␊
509 typedef T ValueType;␊
510 typedef QMapPrivate< Key, T > Priv;␊
511␊
512 /**␊
513 * API␊
514 */␊
515 QMap() { sh = new QMapPrivate< Key, T >; }␊
516 QMap( const QMap<Key,T>& m ) { sh = m.sh; sh->ref(); }␊
517 ~QMap() { if ( sh->deref() ) delete sh; }␊
518␊
519 QMap<Key,T>& operator= ( const QMap<Key,T>& m )␊
520 { m.sh->ref(); if ( sh->deref() ) delete sh; sh = m.sh; return *this; }␊
521␊
522 Iterator begin() { detach(); return sh->begin(); }␊
523 Iterator end() { detach(); return sh->end(); }␊
524 ConstIterator begin() const { return ((const Priv*)sh)->begin(); }␊
525 ConstIterator end() const { return ((const Priv*)sh)->end(); }␊
526␊
527 Iterator find ( const Key& k )␊
528␉{ detach(); return Iterator( sh->find( k ).node ); }␊
529 ConstIterator find ( const Key& k ) const␊
530␉{ return sh->find( k ); }␊
531 T& operator[] ( const Key& k ) {␊
532␉detach(); QMapNode<Key,T>* p = sh->find( k ).node;␊
533␉if ( p != sh->end().node ) return p->data;␊
534␉return insert( k, T() ).data(); }␊
535 const T& operator[] ( const Key& k ) const␊
536␉{ return sh->find( k ).data(); }␊
537 bool contains ( const Key& k ) const␊
538␉{ return find( k ) != end(); }␊
539␉//{ return sh->find( k ) != ((const Priv*)sh)->end(); }␊
540␊
541 uint count() const { return sh->node_count; }␊
542␊
543 bool isEmpty() const { return sh->node_count == 0; }␊
544␊
545 Iterator insert( const Key& key, const T& value ) {␊
546 detach();␊
547 Iterator it = sh->insertSingle( key );␊
548 it.data() = value;␊
549 return it;␊
550 }␊
551␊
552 void remove( Iterator it ) { detach(); sh->remove( it ); }␊
553 void remove( const Key& k ) {␊
554 detach();␊
555 Iterator it( sh->find( k ).node );␊
556 if ( it != end() )␊
557 sh->remove( it );␊
558 }␊
559␊
560 Iterator replace( const Key& k, const T& v ) {␊
561␉remove( k );␊
562␉return insert( k, v );␊
563 }␊
564␊
565 void clear() { if ( sh->count == 1 ) sh->clear(); else { sh->deref(); sh = new QMapPrivate<Key,T>; } }␊
566␊
567#if defined(Q_FULL_TEMPLATE_INSTANTIATION)␊
568 bool operator==( const QMap<Key,T>& ) const { return FALSE; }␊
569#endif␊
570␊
571protected:␊
572 /**␊
573 * Helpers␊
574 */␊
575 void detach() { if ( sh->count > 1 ) { sh->deref(); sh = new QMapPrivate<Key,T>( sh ); } }␊
576␊
577 Priv* sh;␊
578};␊
579␊
580␊
581#ifndef QT_NO_DATASTREAM␊
582template<class Key, class T>␊
583inline QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {␊
584 m.clear();␊
585 Q_UINT32 c;␊
586 s >> c;␊
587 for( Q_UINT32 i = 0; i < c; ++i ) {␊
588␉Key k; T t;␊
589␉s >> k >> t;␊
590␉m.insert( k, t );␊
591 }␊
592 return s;␊
593}␊
594␊
595␊
596template<class Key, class T>␊
597inline QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {␊
598 s << (Q_UINT32)m.count();␊
599 QMapConstIterator<Key,T> it = m.begin();␊
600 for( ; it != m.end(); ++it )␊
601␉s << it.key() << it.data();␊
602 return s;␊
603}␊
604#endif␊
605␊
606#endif // QMAP_H␊
607

Archive Download this file

Revision: 1322