summaryrefslogtreecommitdiff
path: root/qmake/include/qmap.h
Unidiff
Diffstat (limited to 'qmake/include/qmap.h') (more/less context) (ignore whitespace changes)
-rw-r--r--qmake/include/qmap.h883
1 files changed, 883 insertions, 0 deletions
diff --git a/qmake/include/qmap.h b/qmake/include/qmap.h
new file mode 100644
index 0000000..269bd6b
--- a/dev/null
+++ b/qmake/include/qmap.h
@@ -0,0 +1,883 @@
1/****************************************************************************
2** $Id$
3**
4** Definition of QMap class
5**
6** Created : 990406
7**
8** Copyright (C) 1992-2002 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
326class Q_EXPORT QMapPrivateBase : public QShared
327{
328public:
329 QMapPrivateBase() {
330 node_count = 0;
331 }
332 QMapPrivateBase( const QMapPrivateBase* _map) {
333 node_count = _map->node_count;
334 }
335
336 /**
337 * Implementations of basic tree algorithms
338 */
339 void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);
340 void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );
341 void rebalance( QMapNodeBase* x, QMapNodeBase*& root );
342 QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,
343 QMapNodeBase*& leftmost,
344 QMapNodeBase*& rightmost );
345
346 /**
347 * Variables
348 */
349 int node_count;
350};
351
352
353template <class Key, class T>
354class QMapPrivate : public QMapPrivateBase
355{
356public:
357 /**
358 * Typedefs
359 */
360 typedef QMapIterator< Key, T > Iterator;
361 typedef QMapConstIterator< Key, T > ConstIterator;
362 typedef QMapNode< Key, T > Node;
363 typedef QMapNode< Key, T >* NodePtr;
364
365 /**
366 * Functions
367 */
368 QMapPrivate();
369 QMapPrivate( const QMapPrivate< Key, T >* _map );
370 ~QMapPrivate() { clear(); delete header; }
371
372 NodePtr copy( NodePtr p );
373 void clear();
374 void clear( NodePtr p );
375
376 Iterator begin(){ return Iterator( (NodePtr)(header->left ) ); }
377 Iterator end(){ return Iterator( header ); }
378 ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }
379 ConstIterator end() const { return ConstIterator( header ); }
380
381 ConstIterator find(const Key& k) const;
382
383 void remove( Iterator it ) {
384 NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );
385 delete del;
386 --node_count;
387 }
388
389#ifdef QT_QMAP_DEBUG
390 void inorder( QMapNodeBase* x = 0, int level = 0 ){
391 if ( !x )
392 x = header->parent;
393 if ( x->left )
394 inorder( x->left, level + 1 );
395 //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
396 if ( x->right )
397 inorder( x->right, level + 1 );
398 }
399#endif
400
401#if 0
402 Iterator insertMulti(const Key& v){
403 QMapNodeBase* y = header;
404 QMapNodeBase* x = header->parent;
405 while (x != 0){
406 y = x;
407 x = ( v < key(x) ) ? x->left : x->right;
408 }
409 return insert(x, y, v);
410 }
411#endif
412
413 Iterator insertSingle( const Key& k );
414 Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k );
415
416protected:
417 /**
418 * Helpers
419 */
420 const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }
421
422 /**
423 * Variables
424 */
425 NodePtr header;
426};
427
428
429template <class Key, class T>
430Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate() {
431 header = new Node;
432 header->color = QMapNodeBase::Red; // Mark the header
433 header->parent = 0;
434 header->left = header->right = header;
435}
436template <class Key, class T>
437Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {
438 header = new Node;
439 header->color = QMapNodeBase::Red; // Mark the header
440 if ( _map->header->parent == 0 ) {
441 header->parent = 0;
442 header->left = header->right = header;
443 } else {
444 header->parent = copy( (NodePtr)(_map->header->parent) );
445 header->parent->parent = header;
446 header->left = header->parent->minimum();
447 header->right = header->parent->maximum();
448 }
449}
450
451template <class Key, class T>
452Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::NodePtr QMapPrivate<Key,T>::copy( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
453{
454 if ( !p )
455 return 0;
456 NodePtr n = new Node( *p );
457 n->color = p->color;
458 if ( p->left ) {
459 n->left = copy( (NodePtr)(p->left) );
460 n->left->parent = n;
461 } else {
462 n->left = 0;
463 }
464 if ( p->right ) {
465 n->right = copy( (NodePtr)(p->right) );
466 n->right->parent = n;
467 } else {
468 n->right = 0;
469 }
470 return n;
471}
472
473template <class Key, class T>
474Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear()
475{
476 clear( (NodePtr)(header->parent) );
477 header->color = QMapNodeBase::Red;
478 header->parent = 0;
479 header->left = header->right = header;
480 node_count = 0;
481}
482
483template <class Key, class T>
484Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
485{
486 while ( p != 0 ) {
487 clear( (NodePtr)p->right );
488 NodePtr y = (NodePtr)p->left;
489 delete p;
490 p = y;
491 }
492}
493
494template <class Key, class T>
495Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::ConstIterator QMapPrivate<Key,T>::find(const Key& k) const
496{
497 QMapNodeBase* y = header; // Last node
498 QMapNodeBase* x = header->parent; // Root node.
499
500 while ( x != 0 ) {
501 // If as k <= key(x) go left
502 if ( !( key(x) < k ) ) {
503 y = x;
504 x = x->left;
505 } else {
506 x = x->right;
507 }
508 }
509
510 // Was k bigger/smaller then the biggest/smallest
511 // element of the tree ? Return end()
512 if ( y == header || k < key(y) )
513 return ConstIterator( header );
514 return ConstIterator( (NodePtr)y );
515}
516
517template <class Key, class T>
518Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insertSingle( const Key& k )
519{
520 // Search correct position in the tree
521 QMapNodeBase* y = header;
522 QMapNodeBase* x = header->parent;
523 bool result = TRUE;
524 while ( x != 0 ) {
525 result = ( k < key(x) );
526 y = x;
527 x = result ? x->left : x->right;
528 }
529 // Get iterator on the last not empty one
530 Iterator j( (NodePtr)y );
531 if ( result ) {
532 // Smaller then the leftmost one ?
533 if ( j == begin() ) {
534 return insert(x, y, k );
535 } else {
536 // Perhaps daddy is the right one ?
537 --j;
538 }
539 }
540 // Really bigger ?
541 if ( (j.node->key) < k )
542 return insert(x, y, k );
543 // We are going to replace a node
544 return j;
545}
546
547
548template <class Key, class T>
549Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k )
550{
551 NodePtr z = new Node( k );
552 if (y == header || x != 0 || k < key(y) ) {
553 y->left = z; // also makes leftmost = z when y == header
554 if ( y == header ) {
555 header->parent = z;
556 header->right = z;
557 } else if ( y == header->left )
558 header->left = z; // maintain leftmost pointing to min node
559 } else {
560 y->right = z;
561 if ( y == header->right )
562 header->right = z; // maintain rightmost pointing to max node
563 }
564 z->parent = y;
565 z->left = 0;
566 z->right = 0;
567 rebalance( z, header->parent );
568 ++node_count;
569 return Iterator(z);
570}
571
572
573#ifdef QT_CHECK_RANGE
574# if !defined( QT_NO_DEBUG ) && defined( QT_CHECK_MAP_RANGE )
575# define QT_CHECK_INVALID_MAP_ELEMENT if ( empty() ) qWarning( "QMap: Warning invalid element" )
576# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL Q_ASSERT( !empty() );
577# else
578# define QT_CHECK_INVALID_MAP_ELEMENT
579# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
580# endif
581#else
582# define QT_CHECK_INVALID_MAP_ELEMENT
583# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
584#endif
585
586template <class T> class QDeepCopy;
587
588template<class Key, class T>
589class QMap
590{
591public:
592 /**
593 * Typedefs
594 */
595 typedef Key key_type;
596 typedef T mapped_type;
597 typedef QPair<const key_type, mapped_type> value_type;
598 typedef value_type* pointer;
599 typedef const value_type* const_pointer;
600 typedef value_type& reference;
601 typedef const value_type& const_reference;
602#ifndef QT_NO_STL
603 typedef ptrdiff_t difference_type;
604#else
605 typedef int difference_type;
606#endif
607 typedef size_t size_type;
608 typedef QMapIterator<Key,T> iterator;
609 typedef QMapConstIterator<Key,T> const_iterator;
610 typedef QPair<iterator,bool> insert_pair;
611
612 typedef QMapIterator< Key, T > Iterator;
613 typedef QMapConstIterator< Key, T > ConstIterator;
614 typedef T ValueType;
615 typedef QMapPrivate< Key, T > Priv;
616
617 /**
618 * API
619 */
620 QMap()
621 {
622 sh = new QMapPrivate< Key, T >;
623 }
624 QMap( const QMap<Key,T>& m )
625 {
626 sh = m.sh; sh->ref();
627 }
628
629#ifndef QT_NO_STL
630# ifdef Q_CC_HPACC // HP-UX aCC does require typename in some place
631# undef Q_TYPENAME // but not accept them at others.
632# define Q_TYPENAME // also doesn't like re-defines ...
633# endif
634 QMap( const Q_TYPENAME std::map<Key,T>& m )
635 {
636 sh = new QMapPrivate<Key,T>;
637#if defined(Q_OS_WIN32)
638 std::map<Key,T>::const_iterator it = m.begin();
639#else
640 QMapConstIterator<Key,T> it = m.begin();
641#endif
642 for ( ; it != m.end(); ++it ) {
643 value_type p( (*it).first, (*it).second );
644 insert( p );
645 }
646 }
647#endif
648 ~QMap()
649 {
650 if ( sh->deref() )
651 delete sh;
652 }
653 QMap<Key,T>& operator= ( const QMap<Key,T>& m );
654#ifndef QT_NO_STL
655 QMap<Key,T>& operator= ( const Q_TYPENAME std::map<Key,T>& m )
656 {
657 clear();
658#if defined(Q_OS_WIN32)
659 std::map<Key,T>::const_iterator it = m.begin();
660#else
661 QMapConstIterator<Key,T> it = m.begin();
662#endif
663 for ( ; it != m.end(); ++it ) {
664 value_type p( (*it).first, (*it).second );
665 insert( p );
666 }
667 return *this;
668 }
669# ifdef Q_CC_HPACC // undo the HP-UX aCC hackery done above
670# undef Q_TYPENAME
671# define Q_TYPENAME typename
672# endif
673#endif
674
675 iterator begin() { detach(); return sh->begin(); }
676 iterator end() { detach(); return sh->end(); }
677 const_iterator begin() const { return ((const Priv*)sh)->begin(); }
678 const_iterator end() const { return ((const Priv*)sh)->end(); }
679 iterator replace( const Key& k, const T& v )
680 {
681 remove( k );
682 return insert( k, v );
683 }
684
685 size_type size() const
686 {
687 return sh->node_count;
688 }
689 bool empty() const
690 {
691 return sh->node_count == 0;
692 }
693 QPair<iterator,bool> insert( const value_type& x );
694
695 void erase( iterator it )
696 {
697 detach();
698 sh->remove( it );
699 }
700 void erase( const key_type& k );
701 size_type count( const key_type& k ) const;
702 T& operator[] ( const Key& k );
703 void clear();
704
705 iterator find ( const Key& k )
706 {
707 detach();
708 return iterator( sh->find( k ).node );
709 }
710 const_iterator find ( const Key& k ) const {return sh->find( k ); }
711
712 const T& operator[] ( const Key& k ) const
713 { QT_CHECK_INVALID_MAP_ELEMENT; return sh->find( k ).data(); }
714 bool contains ( const Key& k ) const
715 { return find( k ) != end(); }
716 //{ return sh->find( k ) != ((const Priv*)sh)->end(); }
717
718 size_type count() const { return sh->node_count; }
719
720 QValueList<Key> keys() const {
721 QValueList<Key> r;
722 for (const_iterator i=begin(); i!=end(); ++i)
723 r.append(i.key());
724 return r;
725 }
726
727 QValueList<T> values() const {
728 QValueList<T> r;
729 for (const_iterator i=begin(); i!=end(); ++i)
730 r.append(*i);
731 return r;
732 }
733
734 bool isEmpty() const { return sh->node_count == 0; }
735
736 iterator insert( const Key& key, const T& value, bool overwrite = TRUE );
737 void remove( iterator it ) { detach(); sh->remove( it ); }
738 void remove( const Key& k );
739
740#if defined(Q_FULL_TEMPLATE_INSTANTIATION)
741 bool operator==( const QMap<Key,T>& ) const { return FALSE; }
742#ifndef QT_NO_STL
743 bool operator==( const Q_TYPENAME std::map<Key,T>& ) const { return FALSE; }
744#endif
745#endif
746
747protected:
748 /**
749 * Helpers
750 */
751 void detach() { if ( sh->count > 1 ) detachInternal(); }
752
753 Priv* sh;
754private:
755 void detachInternal();
756
757 friend class QDeepCopy< QMap<Key,T> >;
758};
759
760template<class Key, class T>
761Q_INLINE_TEMPLATES QMap<Key,T>& QMap<Key,T>::operator= ( const QMap<Key,T>& m )
762{
763 m.sh->ref();
764 if ( sh->deref() )
765 delete sh;
766 sh = m.sh;
767 return *this;
768}
769
770template<class Key, class T>
771Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::insert_pair QMap<Key,T>::insert( const Q_TYPENAME QMap<Key,T>::value_type& x )
772{
773 detach();
774 size_type n = size();
775 iterator it = sh->insertSingle( x.first );
776 bool inserted = FALSE;
777 if ( n < size() ) {
778 inserted = TRUE;
779 it.data() = x.second;
780 }
781 return QPair<iterator,bool>( it, inserted );
782}
783
784template<class Key, class T>
785Q_INLINE_TEMPLATES void QMap<Key,T>::erase( const Key& k )
786{
787 detach();
788 iterator it( sh->find( k ).node );
789 if ( it != end() )
790 sh->remove( it );
791}
792
793template<class Key, class T>
794Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::size_type QMap<Key,T>::count( const Key& k ) const
795{
796 const_iterator it( sh->find( k ).node );
797 if ( it != end() ) {
798 size_type c = 0;
799 while ( it != end() ) {
800 ++it;
801 ++c;
802 }
803 return c;
804 }
805 return 0;
806}
807
808template<class Key, class T>
809Q_INLINE_TEMPLATES T& QMap<Key,T>::operator[] ( const Key& k )
810{
811 detach();
812 QMapNode<Key,T>* p = sh->find( k ).node;
813 if ( p != sh->end().node )
814 return p->data;
815 return insert( k, T() ).data();
816}
817
818template<class Key, class T>
819Q_INLINE_TEMPLATES void QMap<Key,T>::clear()
820{
821 if ( sh->count == 1 )
822 sh->clear();
823 else {
824 sh->deref();
825 sh = new QMapPrivate<Key,T>;
826 }
827}
828
829template<class Key, class T>
830Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::iterator QMap<Key,T>::insert( const Key& key, const T& value, bool overwrite )
831{
832 detach();
833 size_type n = size();
834 iterator it = sh->insertSingle( key );
835 if ( overwrite || n < size() )
836 it.data() = value;
837 return it;
838}
839
840template<class Key, class T>
841Q_INLINE_TEMPLATES void QMap<Key,T>::remove( const Key& k )
842{
843 detach();
844 iterator it( sh->find( k ).node );
845 if ( it != end() )
846 sh->remove( it );
847}
848
849template<class Key, class T>
850Q_INLINE_TEMPLATES void QMap<Key,T>::detachInternal()
851{
852 sh->deref(); sh = new QMapPrivate<Key,T>( sh );
853}
854
855
856#ifndef QT_NO_DATASTREAM
857template<class Key, class T>
858Q_INLINE_TEMPLATES QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {
859 m.clear();
860 Q_UINT32 c;
861 s >> c;
862 for( Q_UINT32 i = 0; i < c; ++i ) {
863 Key k; T t;
864 s >> k >> t;
865 m.insert( k, t );
866 if ( s.atEnd() )
867 break;
868 }
869 return s;
870}
871
872
873template<class Key, class T>
874Q_INLINE_TEMPLATES QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {
875 s << (Q_UINT32)m.size();
876 QMapConstIterator<Key,T> it = m.begin();
877 for( ; it != m.end(); ++it )
878 s << it.key() << it.data();
879 return s;
880}
881#endif
882
883#endif // QMAP_H