source: trunk/include/qmap.h@ 87

Last change on this file since 87 was 2, checked in by dmik, 20 years ago

Imported xplatform parts of the official release 3.3.1 from Trolltech
  • Property svn:keywords set to Id
File size: 21.3 KB
Line 
1/****************************************************************************
2** $Id: qmap.h 2 2005-11-16 15:49:26Z dmik $
3**
4** Definition of QMap class
5**
6** Created : 990406
7**
8** Copyright (C) 1992-2003 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 "qglobal.h"
43#include "qshared.h"
44#include "qdatastream.h"
45#include "qpair.h"
46#include "qvaluelist.h"
47#endif // QT_H
48
49#ifndef QT_NO_STL
50#include <iterator>
51#include <map>
52#endif
53
54//#define QT_CHECK_MAP_RANGE
55
56struct Q_EXPORT QMapNodeBase
57{
58 enum Color { Red, Black };
59
60 QMapNodeBase* left;
61 QMapNodeBase* right;
62 QMapNodeBase* parent;
63
64 Color color;
65
66 QMapNodeBase* minimum() {
67 QMapNodeBase* x = this;
68 while ( x->left )
69 x = x->left;
70 return x;
71 }
72
73 QMapNodeBase* maximum() {
74 QMapNodeBase* x = this;
75 while ( x->right )
76 x = x->right;
77 return x;
78 }
79};
80
81
82template <class K, class T>
83struct QMapNode : public QMapNodeBase
84{
85 QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }
86 QMapNode( const K& _key ) { key = _key; }
87 QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }
88 QMapNode() { }
89 T data;
90 K key;
91};
92
93
94template<class K, class T>
95class QMapIterator
96{
97 public:
98 /**
99 * Typedefs
100 */
101 typedef QMapNode< K, T >* NodePtr;
102#ifndef QT_NO_STL
103 typedef std::bidirectional_iterator_tag iterator_category;
104#endif
105 typedef T value_type;
106#ifndef QT_NO_STL
107 typedef ptrdiff_t difference_type;
108#else
109 typedef int difference_type;
110#endif
111 typedef T* pointer;
112 typedef T& reference;
113
114 /**
115 * Variables
116 */
117 QMapNode<K,T>* node;
118
119 /**
120 * Functions
121 */
122 QMapIterator() : node( 0 ) {}
123 QMapIterator( QMapNode<K,T>* p ) : node( p ) {}
124 QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
125
126 bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }
127 bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }
128 T& operator*() { return node->data; }
129 const T& operator*() const { return node->data; }
130 // UDT for T = x*
131 // T* operator->() const { return &node->data; }
132
133 const K& key() const { return node->key; }
134 T& data() { return node->data; }
135 const T& data() const { return node->data; }
136
137private:
138 int inc();
139 int dec();
140
141public:
142 QMapIterator<K,T>& operator++() {
143 inc();
144 return *this;
145 }
146
147 QMapIterator<K,T> operator++(int) {
148 QMapIterator<K,T> tmp = *this;
149 inc();
150 return tmp;
151 }
152
153 QMapIterator<K,T>& operator--() {
154 dec();
155 return *this;
156 }
157
158 QMapIterator<K,T> operator--(int) {
159 QMapIterator<K,T> tmp = *this;
160 dec();
161 return tmp;
162 }
163};
164
165template <class K, class T>
166Q_INLINE_TEMPLATES int QMapIterator<K,T>::inc()
167{
168 QMapNodeBase* tmp = node;
169 if ( tmp->right ) {
170 tmp = tmp->right;
171 while ( tmp->left )
172 tmp = tmp->left;
173 } else {
174 QMapNodeBase* y = tmp->parent;
175 while (tmp == y->right) {
176 tmp = y;
177 y = y->parent;
178 }
179 if (tmp->right != y)
180 tmp = y;
181 }
182 node = (NodePtr)tmp;
183 return 0;
184}
185
186template <class K, class T>
187Q_INLINE_TEMPLATES int QMapIterator<K,T>::dec()
188{
189 QMapNodeBase* tmp = node;
190 if (tmp->color == QMapNodeBase::Red &&
191 tmp->parent->parent == tmp ) {
192 tmp = tmp->right;
193 } else if (tmp->left != 0) {
194 QMapNodeBase* y = tmp->left;
195 while ( y->right )
196 y = y->right;
197 tmp = y;
198 } else {
199 QMapNodeBase* y = tmp->parent;
200 while (tmp == y->left) {
201 tmp = y;
202 y = y->parent;
203 }
204 tmp = y;
205 }
206 node = (NodePtr)tmp;
207 return 0;
208}
209
210template<class K, class T>
211class QMapConstIterator
212{
213 public:
214 /**
215 * Typedefs
216 */
217 typedef QMapNode< K, T >* NodePtr;
218#ifndef QT_NO_STL
219 typedef std::bidirectional_iterator_tag iterator_category;
220#endif
221 typedef T value_type;
222#ifndef QT_NO_STL
223 typedef ptrdiff_t difference_type;
224#else
225 typedef int difference_type;
226#endif
227 typedef const T* pointer;
228 typedef const T& reference;
229
230
231 /**
232 * Variables
233 */
234 QMapNode<K,T>* node;
235
236 /**
237 * Functions
238 */
239 QMapConstIterator() : node( 0 ) {}
240 QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}
241 QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}
242 QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
243
244 bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }
245 bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }
246 const T& operator*() const { return node->data; }
247 // UDT for T = x*
248 // const T* operator->() const { return &node->data; }
249
250 const K& key() const { return node->key; }
251 const T& data() const { return node->data; }
252
253private:
254 int inc();
255 int dec();
256
257public:
258 QMapConstIterator<K,T>& operator++() {
259 inc();
260 return *this;
261 }
262
263 QMapConstIterator<K,T> operator++(int) {
264 QMapConstIterator<K,T> tmp = *this;
265 inc();
266 return tmp;
267 }
268
269 QMapConstIterator<K,T>& operator--() {
270 dec();
271 return *this;
272 }
273
274 QMapConstIterator<K,T> operator--(int) {
275 QMapConstIterator<K,T> tmp = *this;
276 dec();
277 return tmp;
278 }
279};
280
281template <class K, class T>
282Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::inc()
283{
284 QMapNodeBase* tmp = node;
285 if ( tmp->right ) {
286 tmp = tmp->right;
287 while ( tmp->left )
288 tmp = tmp->left;
289 } else {
290 QMapNodeBase* y = tmp->parent;
291 while (tmp == y->right) {
292 tmp = y;
293 y = y->parent;
294 }
295 if (tmp->right != y)
296 tmp = y;
297 }
298 node = (NodePtr)tmp;
299 return 0;
300}
301
302template <class K, class T>
303Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::dec()
304{
305 QMapNodeBase* tmp = node;
306 if (tmp->color == QMapNodeBase::Red &&
307 tmp->parent->parent == tmp ) {
308 tmp = tmp->right;
309 } else if (tmp->left != 0) {
310 QMapNodeBase* y = tmp->left;
311 while ( y->right )
312 y = y->right;
313 tmp = y;
314 } else {
315 QMapNodeBase* y = tmp->parent;
316 while (tmp == y->left) {
317 tmp = y;
318 y = y->parent;
319 }
320 tmp = y;
321 }
322 node = (NodePtr)tmp;
323 return 0;
324}
325
326// ### 4.0: rename to something without Private in it. Not really internal.
327class Q_EXPORT QMapPrivateBase : public QShared
328{
329public:
330 QMapPrivateBase() {
331 node_count = 0;
332 }
333 QMapPrivateBase( const QMapPrivateBase* _map) {
334 node_count = _map->node_count;
335 }
336
337 /**
338 * Implementations of basic tree algorithms
339 */
340 void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);
341 void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );
342 void rebalance( QMapNodeBase* x, QMapNodeBase*& root );
343 QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,
344 QMapNodeBase*& leftmost,
345 QMapNodeBase*& rightmost );
346
347 /**
348 * Variables
349 */
350 int node_count;
351};
352
353
354template <class Key, class T>
355class QMapPrivate : public QMapPrivateBase
356{
357public:
358 /**
359 * Typedefs
360 */
361 typedef QMapIterator< Key, T > Iterator;
362 typedef QMapConstIterator< Key, T > ConstIterator;
363 typedef QMapNode< Key, T > Node;
364 typedef QMapNode< Key, T >* NodePtr;
365
366 /**
367 * Functions
368 */
369 QMapPrivate();
370 QMapPrivate( const QMapPrivate< Key, T >* _map );
371 ~QMapPrivate() { clear(); delete header; }
372
373 NodePtr copy( NodePtr p );
374 void clear();
375 void clear( NodePtr p );
376
377 Iterator begin() { return Iterator( (NodePtr)(header->left ) ); }
378 Iterator end() { return Iterator( header ); }
379 ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }
380 ConstIterator end() const { return ConstIterator( header ); }
381
382 ConstIterator find(const Key& k) const;
383
384 void remove( Iterator it ) {
385 NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );
386 delete del;
387 --node_count;
388 }
389
390#ifdef QT_QMAP_DEBUG
391 void inorder( QMapNodeBase* x = 0, int level = 0 ){
392 if ( !x )
393 x = header->parent;
394 if ( x->left )
395 inorder( x->left, level + 1 );
396 //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
397 if ( x->right )
398 inorder( x->right, level + 1 );
399 }
400#endif
401
402#if 0
403 Iterator insertMulti(const Key& v){
404 QMapNodeBase* y = header;
405 QMapNodeBase* x = header->parent;
406 while (x != 0){
407 y = x;
408 x = ( v < key(x) ) ? x->left : x->right;
409 }
410 return insert(x, y, v);
411 }
412#endif
413
414 Iterator insertSingle( const Key& k );
415 Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k );
416
417protected:
418 /**
419 * Helpers
420 */
421 const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }
422
423 /**
424 * Variables
425 */
426 NodePtr header;
427};
428
429
430template <class Key, class T>
431Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate() {
432 header = new Node;
433 header->color = QMapNodeBase::Red; // Mark the header
434 header->parent = 0;
435 header->left = header->right = header;
436}
437template <class Key, class T>
438Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {
439 header = new Node;
440 header->color = QMapNodeBase::Red; // Mark the header
441 if ( _map->header->parent == 0 ) {
442 header->parent = 0;
443 header->left = header->right = header;
444 } else {
445 header->parent = copy( (NodePtr)(_map->header->parent) );
446 header->parent->parent = header;
447 header->left = header->parent->minimum();
448 header->right = header->parent->maximum();
449 }
450}
451
452template <class Key, class T>
453Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::NodePtr QMapPrivate<Key,T>::copy( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
454{
455 if ( !p )
456 return 0;
457 NodePtr n = new Node( *p );
458 n->color = p->color;
459 if ( p->left ) {
460 n->left = copy( (NodePtr)(p->left) );
461 n->left->parent = n;
462 } else {
463 n->left = 0;
464 }
465 if ( p->right ) {
466 n->right = copy( (NodePtr)(p->right) );
467 n->right->parent = n;
468 } else {
469 n->right = 0;
470 }
471 return n;
472}
473
474template <class Key, class T>
475Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear()
476{
477 clear( (NodePtr)(header->parent) );
478 header->color = QMapNodeBase::Red;
479 header->parent = 0;
480 header->left = header->right = header;
481 node_count = 0;
482}
483
484template <class Key, class T>
485Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
486{
487 while ( p != 0 ) {
488 clear( (NodePtr)p->right );
489 NodePtr y = (NodePtr)p->left;
490 delete p;
491 p = y;
492 }
493}
494
495template <class Key, class T>
496Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::ConstIterator QMapPrivate<Key,T>::find(const Key& k) const
497{
498 QMapNodeBase* y = header; // Last node
499 QMapNodeBase* x = header->parent; // Root node.
500
501 while ( x != 0 ) {
502 // If as k <= key(x) go left
503 if ( !( key(x) < k ) ) {
504 y = x;
505 x = x->left;
506 } else {
507 x = x->right;
508 }
509 }
510
511 // Was k bigger/smaller then the biggest/smallest
512 // element of the tree ? Return end()
513 if ( y == header || k < key(y) )
514 return ConstIterator( header );
515 return ConstIterator( (NodePtr)y );
516}
517
518template <class Key, class T>
519Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insertSingle( const Key& k )
520{
521 // Search correct position in the tree
522 QMapNodeBase* y = header;
523 QMapNodeBase* x = header->parent;
524 bool result = TRUE;
525 while ( x != 0 ) {
526 result = ( k < key(x) );
527 y = x;
528 x = result ? x->left : x->right;
529 }
530 // Get iterator on the last not empty one
531 Iterator j( (NodePtr)y );
532 if ( result ) {
533 // Smaller then the leftmost one ?
534 if ( j == begin() ) {
535 return insert(x, y, k );
536 } else {
537 // Perhaps daddy is the right one ?
538 --j;
539 }
540 }
541 // Really bigger ?
542 if ( (j.node->key) < k )
543 return insert(x, y, k );
544 // We are going to replace a node
545 return j;
546}
547
548
549template <class Key, class T>
550Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k )
551{
552 NodePtr z = new Node( k );
553 if (y == header || x != 0 || k < key(y) ) {
554 y->left = z; // also makes leftmost = z when y == header
555 if ( y == header ) {
556 header->parent = z;
557 header->right = z;
558 } else if ( y == header->left )
559 header->left = z; // maintain leftmost pointing to min node
560 } else {
561 y->right = z;
562 if ( y == header->right )
563 header->right = z; // maintain rightmost pointing to max node
564 }
565 z->parent = y;
566 z->left = 0;
567 z->right = 0;
568 rebalance( z, header->parent );
569 ++node_count;
570 return Iterator(z);
571}
572
573
574#ifdef QT_CHECK_RANGE
575# if !defined( QT_NO_DEBUG ) && defined( QT_CHECK_MAP_RANGE )
576# define QT_CHECK_INVALID_MAP_ELEMENT if ( empty() ) qWarning( "QMap: Warning invalid element" )
577# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL Q_ASSERT( !empty() );
578# else
579# define QT_CHECK_INVALID_MAP_ELEMENT
580# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
581# endif
582#else
583# define QT_CHECK_INVALID_MAP_ELEMENT
584# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
585#endif
586
587template <class T> class QDeepCopy;
588
589template<class Key, class T>
590class QMap
591{
592public:
593 /**
594 * Typedefs
595 */
596 typedef Key key_type;
597 typedef T mapped_type;
598 typedef QPair<const key_type, mapped_type> value_type;
599 typedef value_type* pointer;
600 typedef const value_type* const_pointer;
601 typedef value_type& reference;
602 typedef const value_type& const_reference;
603#ifndef QT_NO_STL
604 typedef ptrdiff_t difference_type;
605#else
606 typedef int difference_type;
607#endif
608 typedef size_t size_type;
609 typedef QMapIterator<Key,T> iterator;
610 typedef QMapConstIterator<Key,T> const_iterator;
611 typedef QPair<iterator,bool> insert_pair;
612
613 typedef QMapIterator< Key, T > Iterator;
614 typedef QMapConstIterator< Key, T > ConstIterator;
615 typedef T ValueType;
616 typedef QMapPrivate< Key, T > Priv;
617
618 /**
619 * API
620 */
621 QMap()
622 {
623 sh = new QMapPrivate< Key, T >;
624 }
625 QMap( const QMap<Key,T>& m )
626 {
627 sh = m.sh; sh->ref();
628 }
629
630#ifndef QT_NO_STL
631 QMap( const std::map<Key,T>& m )
632 {
633 sh = new QMapPrivate<Key,T>;
634 Q_TYPENAME std::map<Key,T>::const_iterator it = m.begin();
635 for ( ; it != m.end(); ++it ) {
636 value_type p( (*it).first, (*it).second );
637 insert( p );
638 }
639 }
640#endif
641 ~QMap()
642 {
643 if ( sh->deref() )
644 delete sh;
645 }
646 QMap<Key,T>& operator= ( const QMap<Key,T>& m );
647#ifndef QT_NO_STL
648 QMap<Key,T>& operator= ( const std::map<Key,T>& m )
649 {
650 clear();
651 Q_TYPENAME std::map<Key,T>::const_iterator it = m.begin();
652 for ( ; it != m.end(); ++it ) {
653 value_type p( (*it).first, (*it).second );
654 insert( p );
655 }
656 return *this;
657 }
658#endif
659
660 iterator begin() { detach(); return sh->begin(); }
661 iterator end() { detach(); return sh->end(); }
662 const_iterator begin() const { return ((const Priv*)sh)->begin(); }
663 const_iterator end() const { return ((const Priv*)sh)->end(); }
664 const_iterator constBegin() const { return begin(); }
665 const_iterator constEnd() const { return end(); }
666
667 iterator replace( const Key& k, const T& v )
668 {
669 remove( k );
670 return insert( k, v );
671 }
672
673 size_type size() const
674 {
675 return sh->node_count;
676 }
677 bool empty() const
678 {
679 return sh->node_count == 0;
680 }
681 QPair<iterator,bool> insert( const value_type& x );
682
683 void erase( iterator it )
684 {
685 detach();
686 sh->remove( it );
687 }
688 void erase( const key_type& k );
689 size_type count( const key_type& k ) const;
690 T& operator[] ( const Key& k );
691 void clear();
692
693 iterator find ( const Key& k )
694 {
695 detach();
696 return iterator( sh->find( k ).node );
697 }
698 const_iterator find ( const Key& k ) const { return sh->find( k ); }
699
700 const T& operator[] ( const Key& k ) const
701 { QT_CHECK_INVALID_MAP_ELEMENT; return sh->find( k ).data(); }
702 bool contains ( const Key& k ) const
703 { return find( k ) != end(); }
704 //{ return sh->find( k ) != ((const Priv*)sh)->end(); }
705
706 size_type count() const { return sh->node_count; }
707
708 QValueList<Key> keys() const {
709 QValueList<Key> r;
710 for (const_iterator i=begin(); i!=end(); ++i)
711 r.append(i.key());
712 return r;
713 }
714
715 QValueList<T> values() const {
716 QValueList<T> r;
717 for (const_iterator i=begin(); i!=end(); ++i)
718 r.append(*i);
719 return r;
720 }
721
722 bool isEmpty() const { return sh->node_count == 0; }
723
724 iterator insert( const Key& key, const T& value, bool overwrite = TRUE );
725 void remove( iterator it ) { detach(); sh->remove( it ); }
726 void remove( const Key& k );
727
728#if defined(Q_FULL_TEMPLATE_INSTANTIATION)
729 bool operator==( const QMap<Key,T>& ) const { return FALSE; }
730#ifndef QT_NO_STL
731 bool operator==( const std::map<Key,T>& ) const { return FALSE; }
732#endif
733#endif
734
735protected:
736 /**
737 * Helpers
738 */
739 void detach() { if ( sh->count > 1 ) detachInternal(); }
740
741 Priv* sh;
742private:
743 void detachInternal();
744
745 friend class QDeepCopy< QMap<Key,T> >;
746};
747
748template<class Key, class T>
749Q_INLINE_TEMPLATES QMap<Key,T>& QMap<Key,T>::operator= ( const QMap<Key,T>& m )
750{
751 m.sh->ref();
752 if ( sh->deref() )
753 delete sh;
754 sh = m.sh;
755 return *this;
756}
757
758template<class Key, class T>
759Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::insert_pair QMap<Key,T>::insert( const Q_TYPENAME QMap<Key,T>::value_type& x )
760{
761 detach();
762 size_type n = size();
763 iterator it = sh->insertSingle( x.first );
764 bool inserted = FALSE;
765 if ( n < size() ) {
766 inserted = TRUE;
767 it.data() = x.second;
768 }
769 return QPair<iterator,bool>( it, inserted );
770}
771
772template<class Key, class T>
773Q_INLINE_TEMPLATES void QMap<Key,T>::erase( const Key& k )
774{
775 detach();
776 iterator it( sh->find( k ).node );
777 if ( it != end() )
778 sh->remove( it );
779}
780
781template<class Key, class T>
782Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::size_type QMap<Key,T>::count( const Key& k ) const
783{
784 const_iterator it( sh->find( k ).node );
785 if ( it != end() ) {
786 size_type c = 0;
787 while ( it != end() ) {
788 ++it;
789 ++c;
790 }
791 return c;
792 }
793 return 0;
794}
795
796template<class Key, class T>
797Q_INLINE_TEMPLATES T& QMap<Key,T>::operator[] ( const Key& k )
798{
799 detach();
800 QMapNode<Key,T>* p = sh->find( k ).node;
801 if ( p != sh->end().node )
802 return p->data;
803 return insert( k, T() ).data();
804}
805
806template<class Key, class T>
807Q_INLINE_TEMPLATES void QMap<Key,T>::clear()
808{
809 if ( sh->count == 1 )
810 sh->clear();
811 else {
812 sh->deref();
813 sh = new QMapPrivate<Key,T>;
814 }
815}
816
817template<class Key, class T>
818Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::iterator QMap<Key,T>::insert( const Key& key, const T& value, bool overwrite )
819{
820 detach();
821 size_type n = size();
822 iterator it = sh->insertSingle( key );
823 if ( overwrite || n < size() )
824 it.data() = value;
825 return it;
826}
827
828template<class Key, class T>
829Q_INLINE_TEMPLATES void QMap<Key,T>::remove( const Key& k )
830{
831 detach();
832 iterator it( sh->find( k ).node );
833 if ( it != end() )
834 sh->remove( it );
835}
836
837template<class Key, class T>
838Q_INLINE_TEMPLATES void QMap<Key,T>::detachInternal()
839{
840 sh->deref(); sh = new QMapPrivate<Key,T>( sh );
841}
842
843
844#ifndef QT_NO_DATASTREAM
845template<class Key, class T>
846Q_INLINE_TEMPLATES QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {
847 m.clear();
848 Q_UINT32 c;
849 s >> c;
850 for( Q_UINT32 i = 0; i < c; ++i ) {
851 Key k; T t;
852 s >> k >> t;
853 m.insert( k, t );
854 if ( s.atEnd() )
855 break;
856 }
857 return s;
858}
859
860
861template<class Key, class T>
862Q_INLINE_TEMPLATES QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {
863 s << (Q_UINT32)m.size();
864 QMapConstIterator<Key,T> it = m.begin();
865 for( ; it != m.end(); ++it )
866 s << it.key() << it.data();
867 return s;
868}
869#endif
870
871#define Q_DEFINED_QMAP
872#include "qwinexport.h"
873#endif // QMAP_H
Note: See TracBrowser for help on using the repository browser.