author | kergoth <kergoth> | 2002-11-01 00:10:42 (UTC) |
---|---|---|
committer | kergoth <kergoth> | 2002-11-01 00:10:42 (UTC) |
commit | 5042e3cf0d3514552769e441f5aad590c8eaf967 (patch) (unidiff) | |
tree | 4a5ea45f3519d981a172ab5275bf38c6fa778dec /qmake/include/qmap.h | |
parent | 108c1c753e74e989cc13923086996791428c9af4 (diff) | |
download | opie-5042e3cf0d3514552769e441f5aad590c8eaf967.zip opie-5042e3cf0d3514552769e441f5aad590c8eaf967.tar.gz opie-5042e3cf0d3514552769e441f5aad590c8eaf967.tar.bz2 |
Adding qmake in preperation for new build system
-rw-r--r-- | qmake/include/qmap.h | 883 |
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 | |||
56 | struct 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 | |||
82 | template <class K, class T> | ||
83 | struct 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 | |||
94 | template<class K, class T> | ||
95 | class 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 | |||
137 | private: | ||
138 | int inc(); | ||
139 | int dec(); | ||
140 | |||
141 | public: | ||
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 | |||
165 | template <class K, class T> | ||
166 | Q_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 | |||
186 | template <class K, class T> | ||
187 | Q_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 | |||
210 | template<class K, class T> | ||
211 | class 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 | |||
253 | private: | ||
254 | int inc(); | ||
255 | int dec(); | ||
256 | |||
257 | public: | ||
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 | |||
281 | template <class K, class T> | ||
282 | Q_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 | |||
302 | template <class K, class T> | ||
303 | Q_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 | class Q_EXPORT QMapPrivateBase : public QShared | ||
327 | { | ||
328 | public: | ||
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 | |||
353 | template <class Key, class T> | ||
354 | class QMapPrivate : public QMapPrivateBase | ||
355 | { | ||
356 | public: | ||
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 | |||
416 | protected: | ||
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 | |||
429 | template <class Key, class T> | ||
430 | Q_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 | } | ||
436 | template <class Key, class T> | ||
437 | Q_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 | |||
451 | template <class Key, class T> | ||
452 | Q_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 | |||
473 | template <class Key, class T> | ||
474 | Q_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 | |||
483 | template <class Key, class T> | ||
484 | Q_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 | |||
494 | template <class Key, class T> | ||
495 | Q_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 | |||
517 | template <class Key, class T> | ||
518 | Q_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 | |||
548 | template <class Key, class T> | ||
549 | Q_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 | |||
586 | template <class T> class QDeepCopy; | ||
587 | |||
588 | template<class Key, class T> | ||
589 | class QMap | ||
590 | { | ||
591 | public: | ||
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 | |||
747 | protected: | ||
748 | /** | ||
749 | * Helpers | ||
750 | */ | ||
751 | void detach() { if ( sh->count > 1 ) detachInternal(); } | ||
752 | |||
753 | Priv* sh; | ||
754 | private: | ||
755 | void detachInternal(); | ||
756 | |||
757 | friend class QDeepCopy< QMap<Key,T> >; | ||
758 | }; | ||
759 | |||
760 | template<class Key, class T> | ||
761 | Q_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 | |||
770 | template<class Key, class T> | ||
771 | Q_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 | |||
784 | template<class Key, class T> | ||
785 | Q_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 | |||
793 | template<class Key, class T> | ||
794 | Q_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 | |||
808 | template<class Key, class T> | ||
809 | Q_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 | |||
818 | template<class Key, class T> | ||
819 | Q_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 | |||
829 | template<class Key, class T> | ||
830 | Q_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 | |||
840 | template<class Key, class T> | ||
841 | Q_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 | |||
849 | template<class Key, class T> | ||
850 | Q_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 | ||
857 | template<class Key, class T> | ||
858 | Q_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 | |||
873 | template<class Key, class T> | ||
874 | Q_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 | ||