Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 9 years 5 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() {
58QMapNodeBase* x = this;
59while ( x->left )
60 x = x->left;
61return x;
62 }
63
64 QMapNodeBase* maximum() {
65QMapNodeBase* x = this;
66while ( x->right )
67 x = x->right;
68return 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() {
120QMapNodeBase* tmp = node;
121if ( tmp->right ) {
122 tmp = tmp->right;
123 while ( tmp->left )
124tmp = tmp->left;
125} else {
126 QMapNodeBase* y = tmp->parent;
127 while (tmp == y->right) {
128tmp = y;
129y = y->parent;
130 }
131 if (tmp->right != y)
132tmp = y;
133}
134node = (NodePtr)tmp;
135return 0;
136 }
137
138 int dec() {
139QMapNodeBase* tmp = node;
140if (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 )
146y = y->right;
147 tmp = y;
148} else {
149 QMapNodeBase* y = tmp->parent;
150 while (tmp == y->left) {
151tmp = y;
152y = y->parent;
153 }
154 tmp = y;
155}
156node = (NodePtr)tmp;
157return 0;
158 }
159
160public:
161 QMapIterator<K,T>& operator++() {
162inc();
163return *this;
164 }
165
166 QMapIterator<K,T> operator++(int) {
167QMapIterator<K,T> tmp = *this;
168inc();
169return tmp;
170 }
171
172 QMapIterator<K,T>& operator--() {
173dec();
174return *this;
175 }
176
177 QMapIterator<K,T> operator--(int) {
178QMapIterator<K,T> tmp = *this;
179dec();
180return 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;
219if ( tmp->right ) {
220 tmp = tmp->right;
221 while ( tmp->left )
222tmp = tmp->left;
223} else {
224 QMapNodeBase* y = tmp->parent;
225 while (tmp == y->right) {
226tmp = y;
227y = y->parent;
228 }
229 if (tmp->right != y)
230tmp = y;
231}
232node = (NodePtr)tmp;
233return 0;
234 }
235
236 int dec() {
237QMapNodeBase* tmp = node;
238if (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 )
244y = y->right;
245 tmp = y;
246} else {
247 QMapNodeBase* y = tmp->parent;
248 while (tmp == y->left) {
249tmp = y;
250y = y->parent;
251 }
252 tmp = y;
253}
254node = (NodePtr)tmp;
255return 0;
256 }
257
258public:
259 QMapConstIterator<K,T>& operator++() {
260inc();
261return *this;
262 }
263
264 QMapConstIterator<K,T> operator++(int) {
265QMapConstIterator<K,T> tmp = *this;
266inc();
267return tmp;
268 }
269
270 QMapConstIterator<K,T>& operator--() {
271dec();
272return *this;
273 }
274
275 QMapConstIterator<K,T> operator--(int) {
276QMapConstIterator<K,T> tmp = *this;
277dec();
278return tmp;
279 }
280};
281
282
283class Q_EXPORT QMapPrivateBase : public QShared
284{
285public:
286 QMapPrivateBase() {
287node_count = 0;
288 }
289 QMapPrivateBase( const QMapPrivateBase* _map) {
290node_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() {
326header = new Node;
327header->color = QMapNodeBase::Red; // Mark the header
328header->parent = 0;
329header->left = header->right = header;
330 }
331 QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {
332header = new Node;
333header->color = QMapNodeBase::Red; // Mark the header
334if ( _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 ) {
347if ( !p )
348 return 0;
349NodePtr n = new Node( *p );
350n->color = p->color;
351if ( p->left ) {
352 n->left = copy( (NodePtr)(p->left) );
353 n->left->parent = n;
354} else {
355 n->left = 0;
356}
357if ( p->right ) {
358 n->right = copy( (NodePtr)(p->right) );
359 n->right->parent = n;
360} else {
361 n->right = 0;
362}
363return n;
364 }
365
366 void clear() {
367clear( (NodePtr)(header->parent) );
368header->color = QMapNodeBase::Red;
369header->parent = 0;
370header->left = header->right = header;
371node_count = 0;
372 }
373
374 void clear( NodePtr p ) {
375while ( 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 {
389QMapNodeBase* y = header; // Last node
390QMapNodeBase* x = header->parent; // Root node.
391
392while ( x != 0 ) {
393 // If as k <= key(x) go left
394 if ( !( key(x) < k ) ) {
395y = x;
396x = x->left;
397 } else {
398x = x->right;
399 }
400}
401
402// Was k bigger/smaller then the biggest/smallest
403// element of the tree ? Return end()
404if ( y == header || k < key(y) )
405 return ConstIterator( header );
406return ConstIterator( (NodePtr)y );
407 }
408
409 void remove( Iterator it ) {
410NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );
411delete del;
412--node_count;
413 }
414
415#ifdef QT_QMAP_DEBUG
416 void inorder( QMapNodeBase* x = 0, int level = 0 ){
417if ( !x )
418 x = header->parent;
419if ( x->left )
420 inorder( x->left, level + 1 );
421 //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
422if ( x->right )
423 inorder( x->right, level + 1 );
424 }
425#endif
426
427 Iterator insertMulti(const Key& v){
428QMapNodeBase* y = header;
429QMapNodeBase* x = header->parent;
430while (x != 0){
431 y = x;
432 x = ( v < key(x) ) ? x->left : x->right;
433}
434return insert(x, y, v);
435 }
436
437 Iterator insertSingle( const Key& k ) {
438// Search correct position in the tree
439QMapNodeBase* y = header;
440QMapNodeBase* x = header->parent;
441bool result = TRUE;
442while ( 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
448Iterator j( (NodePtr)y );
449if ( result ) {
450 // Smaller then the leftmost one ?
451 if ( j == begin() ) {
452return insert(x, y, k );
453 } else {
454// Perhaps daddy is the right one ?
455--j;
456 }
457}
458// Really bigger ?
459if ( (j.node->key) < k )
460 return insert(x, y, k );
461// We are going to replace a node
462return j;
463 }
464
465 Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k ) {
466NodePtr z = new Node( k );
467if (y == header || x != 0 || k < key(y) ) {
468 y->left = z; // also makes leftmost = z when y == header
469 if ( y == header ) {
470header->parent = z;
471header->right = z;
472 } else if ( y == header->left )
473header->left = z; // maintain leftmost pointing to min node
474} else {
475 y->right = z;
476 if ( y == header->right )
477header->right = z; // maintain rightmost pointing to max node
478}
479z->parent = y;
480z->left = 0;
481z->right = 0;
482rebalance( z, header->parent );
483++node_count;
484return 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 ) {
532detach(); QMapNode<Key,T>* p = sh->find( k ).node;
533if ( p != sh->end().node ) return p->data;
534return 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 ) {
561remove( k );
562return 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 ) {
588Key k; T t;
589s >> k >> t;
590m.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 )
601s << it.key() << it.data();
602 return s;
603}
604#endif
605
606#endif // QMAP_H
607

Archive Download this file

Revision: 1322