Debian Codegraph @

Source/Utilities/Container/CQtManagedRestrictedModificationMap.cpp

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 * This file incorporates work covered by the following copyright and
20 * permission notice (to be compatible with LGPLv2.1,
21 * this code is available/released under GPLv3,
22 * see https://www.gnu.org/licenses/gpl-faq.html#AllCompatibility):
23 *
24 *
25 * Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
26 * Contact: http://www.qt-project.org/legal
27 *
28 * This file is part of the QtCore module of the Qt Toolkit.
29 *
30 * $QT_BEGIN_LICENSE:LGPL$
31 * Commercial License Usage
32 * Licensees holding valid commercial Qt licenses may use this file in
33 * accordance with the commercial license agreement provided with the
34 * Software or, alternatively, in accordance with the terms contained in
35 * a written agreement between you and Digia. For licensing terms and
36 * conditions see http://qt.digia.com/licensing. For further information
37 * use the contact form at http://qt.digia.com/contact-us.
38 *
39 * GNU Lesser General Public License Usage
40 * Alternatively, this file may be used under the terms of the GNU Lesser
41 * General Public License version 2.1 as published by the Free Software
42 * Foundation and appearing in the file LICENSE.LGPL included in the
43 * packaging of this file. Please review the following information to
44 * ensure the GNU Lesser General Public License version 2.1 requirements
45 * will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
46 *
47 * In addition, as a special exception, Digia gives you certain additional
48 * rights. These rights are described in the Digia Qt LGPL Exception
49 * version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
50 *
51 * GNU General Public License Usage
52 * Alternatively, this file may be used under the terms of the GNU
53 * General Public License version 3.0 as published by the Free Software
54 * Foundation and appearing in the file LICENSE.GPL included in the
55 * packaging of this file. Please review the following information to
56 * ensure the GNU General Public License version 3.0 requirements will be
57 * met: http://www.gnu.org/copyleft/gpl.html.
58 *
59 *
60 * $QT_END_LICENSE$
61 *
62 *
63 */
64
65 #ifndef KONCLUDE_UTILITIES_CONTAINER_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_CPP
66 #define KONCLUDE_UTILITIES_CONTAINER_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_CPP
67
68
69 #include "CQtManagedRestrictedModificationMap.h"
70
71
72 namespace Konclude {
73
74 namespace Utilities {
75
76 namespace Container {
77
78
79 #ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_MAP_CONTAINER
80
81
82 template <class Key, class T>
83 Q_INLINE_TEMPLATE CQtManagedRestrictedModificationMap<Key, T> &CQtManagedRestrictedModificationMap<Key, T>::operator=(const CQtManagedRestrictedModificationMap<Key, T> &other)
84 {
85 if (d != other.d) {
86 //other.d->ref.ref();
87 //if (!d->ref.deref())
88 if (d->refMap == this)
89 freeData(d);
90 d = other.d;
91 if (!d->sharable)
92 detach_helper();
93 }
94 return *this;
95 }
96
97
98 template <class Key, class T>
99 Q_INLINE_TEMPLATE CQtManagedRestrictedModificationMap<Key, T>* CQtManagedRestrictedModificationMap<Key, T>::init(const CQtManagedRestrictedModificationMap<Key, T> &other, CContext* context)
100 {
101 if (d != other.d) {
102 //other.d->ref.ref();
103 //if (!d->ref.deref())
104 if (d->refMap == this)
105 freeData(d);
106 d = other.d;
107 if (!d->sharable)
108 detach_helper();
109 }
110 mContext = context;
111 mMemMan = CContext::getMemoryAllocationManager(mContext);
112 return this;
113 }
114
115 template <class Key, class T>
116 Q_INLINE_TEMPLATE CQtManagedRestrictedModificationMap<Key, T>* CQtManagedRestrictedModificationMap<Key, T>::init(const CQtManagedRestrictedModificationMap<Key, T>* other, CContext* context)
117 {
118 if (other) {
119 if (d != other->d) {
120 //other.d->ref.ref();
121 //if (!d->ref.deref())
122 if (d->refMap == this)
123 freeData(d);
124 d = other->d;
125 if (!d->sharable)
126 detach_helper();
127 }
128 } else {
129 clear();
130 }
131 mContext = context;
132 mMemMan = CContext::getMemoryAllocationManager(mContext);
133 return this;
134 }
135
136
137 template <class Key, class T>
138 Q_INLINE_TEMPLATE bool CQtManagedRestrictedModificationMap<Key, T>::isKeySubSetOf(const CQtManagedRestrictedModificationMap<Key, T>* other, cint64 testDirectSubSetFactorCount) {
139 if (count() > other->count()) {
140 return false;
141 }
142 if (count() * testDirectSubSetFactorCount < other->count()) {
143 for (const_iterator it = constBegin(),itEnd = constEnd(); it != itEnd; ++it) {
144 const Key& key = it.key();
145 if (!other->contains(key)) {
146 return false;
147 }
148 }
149 } else {
150 const_iterator itSub = constBegin(),itSubEnd = constEnd();
151 const_iterator itSuper = other->constBegin(),itSuperEnd = other->constEnd();
152 while (itSub != itSubEnd) {
153 const Key& subKey = itSub.key();
154 if (itSuper == itSuperEnd) {
155 return false;
156 }
157 const Key& superKey = itSuper.key();
158 if (superKey < subKey) {
159 ++itSuper;
160 } else if (subKey < superKey) {
161 return false;
162 } else {
163 ++itSub;
164 ++itSuper;
165 }
166 }
167 }
168 return true;
169 }
170
171
172 template <class Key, class T>
173 Q_INLINE_TEMPLATE CQtManagedRestrictedModificationMap<Key, T>* CQtManagedRestrictedModificationMap<Key, T>::init(CContext* context)
174 {
175 clear();
176 mContext = context;
177 mMemMan = CContext::getMemoryAllocationManager(mContext);
178 return this;
179 }
180
181
182 template <class Key, class T>
183 Q_INLINE_TEMPLATE void CQtManagedRestrictedModificationMap<Key, T>::clear()
184 {
185 *this = CQtManagedRestrictedModificationMap<Key, T>(mContext);
186 }
187
188 template <class Key, class T>
189 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMapData::Node *
190 CQtManagedRestrictedModificationMap<Key, T>::node_create(CQtManagedRestrictedModificationMapData *adt, CQtManagedRestrictedModificationMapData::Node *aupdate[], const Key &akey, const T &avalue)
191 {
192 CQtManagedRestrictedModificationMapData::Node *abstractNode = adt->node_create(aupdate, payload(), alignment(), mMemMan);
193 QT_TRY {
194 Node *concreteNode = concrete(abstractNode);
195 new (&concreteNode->key) Key(akey);
196 QT_TRY {
197 new (&concreteNode->value) T(avalue);
198 } QT_CATCH(...) {
199 concreteNode->key.~Key();
200 QT_RETHROW;
201 }
202 } QT_CATCH(...) {
203 adt->node_delete(aupdate, payload(), abstractNode, mMemMan);
204 QT_RETHROW;
205 }
206
207 // clean up the update array for further insertions
208 /*
209 for (int i = 0; i <= d->topLevel; ++i) {
210 if ( aupdate[i]==reinterpret_cast<CQtManagedRestrictedModificationMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)
211 break;
212 aupdate[i] = abstractNode;
213 }
214 */
215
216 return abstractNode;
217 }
218
219 template <class Key, class T>
220 Q_INLINE_TEMPLATE CQtManagedRestrictedModificationMapData::Node *CQtManagedRestrictedModificationMap<Key, T>::findNode(const Key &akey) const
221 {
222 CQtManagedRestrictedModificationMapData::Node *cur = e;
223 CQtManagedRestrictedModificationMapData::Node *next = e;
224
225 for (int i = d->topLevel; i >= 0; i--) {
226 while ((next = cur->forward[i]) != e && cMapLessThanKey<Key>(concrete(next)->key, akey))
227 cur = next;
228 }
229
230 if (next != e && !cMapLessThanKey<Key>(akey, concrete(next)->key)) {
231 return next;
232 } else {
233 return e;
234 }
235 }
236
237 template <class Key, class T>
238 Q_INLINE_TEMPLATE const T CQtManagedRestrictedModificationMap<Key, T>::value(const Key &akey) const
239 {
240 CQtManagedRestrictedModificationMapData::Node *node;
241 if (d->size == 0 || (node = findNode(akey)) == e) {
242 return T();
243 } else {
244 return concrete(node)->value;
245 }
246 }
247
248 template <class Key, class T>
249 Q_INLINE_TEMPLATE const T CQtManagedRestrictedModificationMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
250 {
251 CQtManagedRestrictedModificationMapData::Node *node;
252 if (d->size == 0 || (node = findNode(akey)) == e) {
253 return adefaultValue;
254 } else {
255 return concrete(node)->value;
256 }
257 }
258
259
260 template <class Key, class T>
261 Q_INLINE_TEMPLATE bool CQtManagedRestrictedModificationMap<Key, T>::tryGetValue(const Key &akey, T* value) const {
262 CQtManagedRestrictedModificationMapData::Node *node;
263 if (d->size == 0 || (node = findNode(akey)) == e) {
264 return false;
265 } else {
266 *value = concrete(node)->value;
267 return true;
268 }
269 }
270
271 template <class Key, class T>
272 Q_INLINE_TEMPLATE bool CQtManagedRestrictedModificationMap<Key, T>::tryGetValuePointer(const Key &akey, T*& valuePointer) const {
273 CQtManagedRestrictedModificationMapData::Node *node;
274 if (d->size == 0 || (node = findNode(akey)) == e) {
275 return false;
276 } else {
277 valuePointer = &(concrete(node)->value);
278 return true;
279 }
280 }
281
282
283 template <class Key, class T>
284 Q_INLINE_TEMPLATE const T CQtManagedRestrictedModificationMap<Key, T>::operator[](const Key &akey) const
285 {
286 return value(akey);
287 }
288
289 template <class Key, class T>
290 Q_INLINE_TEMPLATE T &CQtManagedRestrictedModificationMap<Key, T>::operator[](const Key &akey)
291 {
292 detach();
293
294 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
295 CQtManagedRestrictedModificationMapData::Node *node = mutableFindNode(update, akey);
296 if (node == e)
297 node = node_create(d, update, akey, T());
298 return concrete(node)->value;
299 }
300
301 template <class Key, class T>
302 Q_INLINE_TEMPLATE int CQtManagedRestrictedModificationMap<Key, T>::count(const Key &akey) const
303 {
304 int cnt = 0;
305 CQtManagedRestrictedModificationMapData::Node *node = findNode(akey);
306 if (node != e) {
307 do {
308 ++cnt;
309 node = node->forward[0];
310 } while (node != e && !cMapLessThanKey<Key>(akey, concrete(node)->key));
311 }
312 return cnt;
313 }
314
315 template <class Key, class T>
316 Q_INLINE_TEMPLATE bool CQtManagedRestrictedModificationMap<Key, T>::contains(const Key &akey) const
317 {
318 return findNode(akey) != e;
319 }
320
321 template <class Key, class T>
322 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::insert(const Key &akey,
323 const T &avalue)
324 {
325 detach();
326
327 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
328 CQtManagedRestrictedModificationMapData::Node *node = mutableFindNode(update, akey);
329 if (node == e) {
330 node = node_create(d, update, akey, avalue);
331 } else {
332 concrete(node)->value = avalue;
333 }
334 return iterator(node);
335 }
336
337
338 template <class Key, class T>
339 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::tryInsert(const Key &akey,
340 const T &avalue, bool* containsAlready)
341 {
342 detach();
343
344 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
345 CQtManagedRestrictedModificationMapData::Node *node = mutableFindNode(update, akey);
346 if (node == e) {
347 node = node_create(d, update, akey, avalue);
348 if (containsAlready) {
349 *containsAlready = false;
350 }
351 } else {
352 if (containsAlready) {
353 *containsAlready = true;
354 }
355 //concrete(node)->value = avalue;
356 }
357 return iterator(node);
358 }
359
360
361 template <class Key, class T>
362 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::tryInsert(const Key &akey,
363 const T &avalue, bool* containsAlready, T** containedValue)
364 {
365 detach();
366
367 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
368 CQtManagedRestrictedModificationMapData::Node *node = mutableFindNode(update, akey);
369 if (node == e) {
370 node = node_create(d, update, akey, avalue);
371 if (containsAlready) {
372 *containsAlready = false;
373 }
374 } else {
375 if (containsAlready) {
376 *containsAlready = true;
377 }
378 //concrete(node)->value = avalue;
379 }
380 if (containedValue) {
381 *containedValue = &concrete(node)->value;
382 }
383 return iterator(node);
384 }
385
386
387 template <class Key, class T>
388 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::insertMulti(const Key &akey,
389 const T &avalue)
390 {
391 detach();
392
393 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
394 mutableFindNode(update, akey);
395 return iterator(node_create(d, update, akey, avalue));
396 }
397
398 template <class Key, class T>
399 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::const_iterator CQtManagedRestrictedModificationMap<Key, T>::find(const Key &akey) const
400 {
401 return const_iterator(findNode(akey));
402 }
403
404 template <class Key, class T>
405 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::const_iterator CQtManagedRestrictedModificationMap<Key, T>::constFind(const Key &akey) const
406 {
407 return const_iterator(findNode(akey));
408 }
409
410 template <class Key, class T>
411 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::find(const Key &akey)
412 {
413 detach();
414 return iterator(findNode(akey));
415 }
416
417 template <class Key, class T>
418 Q_INLINE_TEMPLATE CQtManagedRestrictedModificationMap<Key, T> &CQtManagedRestrictedModificationMap<Key, T>::unite(const CQtManagedRestrictedModificationMap<Key, T> &other)
419 {
420 CQtManagedRestrictedModificationMap<Key, T> copy(other);
421 const_iterator it = copy.constEnd();
422 const const_iterator b = copy.constBegin();
423 while (it != b) {
424 --it;
425 insertMulti(it.key(), it.value());
426 }
427 return *this;
428 }
429
430 template <class Key, class T>
431 Q_OUTOFLINE_TEMPLATE void CQtManagedRestrictedModificationMap<Key, T>::freeData(CQtManagedRestrictedModificationMapData *x)
432 {
433 if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
434 CQtManagedRestrictedModificationMapData *cur = x;
435 CQtManagedRestrictedModificationMapData *next = cur->forward[0];
436 while (next != x) {
437 cur = next;
438 next = cur->forward[0];
439 #if defined(_MSC_VER) && (_MSC_VER >= 1300)
440 #pragma warning(disable:4189)
441 #endif
442 Node *concreteNode = concrete(reinterpret_cast<CQtManagedRestrictedModificationMapData::Node *>(cur));
443 concreteNode->key.~Key();
444 concreteNode->value.~T();
445 #if defined(_MSC_VER) && (_MSC_VER >= 1300)
446 #pragma warning(default:4189)
447 #endif
448 }
449 }
450 x->continueFreeData(payload(), mMemMan);
451 }
452
453 template <class Key, class T>
454 Q_OUTOFLINE_TEMPLATE int CQtManagedRestrictedModificationMap<Key, T>::remove(const Key &akey)
455 {
456 detach();
457
458 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
459 CQtManagedRestrictedModificationMapData::Node *cur = e;
460 CQtManagedRestrictedModificationMapData::Node *next = e;
461 int oldSize = d->size;
462
463 for (int i = d->topLevel; i >= 0; i--) {
464 while ((next = cur->forward[i]) != e && cMapLessThanKey<Key>(concrete(next)->key, akey))
465 cur = next;
466 update[i] = cur;
467 }
468
469 if (next != e && !cMapLessThanKey<Key>(akey, concrete(next)->key)) {
470 bool deleteNext = true;
471 do {
472 cur = next;
473 next = cur->forward[0];
474 deleteNext = (next != e && !cMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
475 concrete(cur)->key.~Key();
476 concrete(cur)->value.~T();
477 d->node_delete(update, payload(), cur, mMemMan);
478 } while (deleteNext);
479 }
480 return oldSize - d->size;
481 }
482
483 template <class Key, class T>
484 Q_OUTOFLINE_TEMPLATE T CQtManagedRestrictedModificationMap<Key, T>::take(const Key &akey)
485 {
486 detach();
487
488 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
489 CQtManagedRestrictedModificationMapData::Node *cur = e;
490 CQtManagedRestrictedModificationMapData::Node *next = e;
491
492 for (int i = d->topLevel; i >= 0; i--) {
493 while ((next = cur->forward[i]) != e && cMapLessThanKey<Key>(concrete(next)->key, akey))
494 cur = next;
495 update[i] = cur;
496 }
497
498 if (next != e && !cMapLessThanKey<Key>(akey, concrete(next)->key)) {
499 T t = concrete(next)->value;
500 concrete(next)->key.~Key();
501 concrete(next)->value.~T();
502 d->node_delete(update, payload(), next, mMemMan);
503 return t;
504 }
505 return T();
506 }
507
508 template <class Key, class T>
509 Q_OUTOFLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::erase(iterator it)
510 {
511 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
512 CQtManagedRestrictedModificationMapData::Node *cur = e;
513 CQtManagedRestrictedModificationMapData::Node *next = e;
514
515 if (it == iterator(e))
516 return it;
517
518 for (int i = d->topLevel; i >= 0; i--) {
519 while ((next = cur->forward[i]) != e && cMapLessThanKey<Key>(concrete(next)->key, it.key()))
520 cur = next;
521 update[i] = cur;
522 }
523
524 while (next != e) {
525 cur = next;
526 next = cur->forward[0];
527 if (cur == it) {
528 concrete(cur)->key.~Key();
529 concrete(cur)->value.~T();
530 d->node_delete(update, payload(), cur, mMemMan);
531 return iterator(next);
532 }
533
534 for (int i = 0; i <= d->topLevel; ++i) {
535 if (update[i]->forward[i] != cur)
536 break;
537 update[i] = cur;
538 }
539 }
540 return end();
541 }
542
543 template <class Key, class T>
544 Q_OUTOFLINE_TEMPLATE void CQtManagedRestrictedModificationMap<Key, T>::detach_helper()
545 {
546 union { CQtManagedRestrictedModificationMapData *d; CQtManagedRestrictedModificationMapData::Node *e; } x;
547 x.d = CQtManagedRestrictedModificationMapData::createData(alignment(), this, mMemMan);
548 if (d->size) {
549 x.d->insertInOrder = true;
550 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
551 CQtManagedRestrictedModificationMapData::Node *cur = e->forward[0];
552 update[0] = x.e;
553 while (cur != e) {
554 QT_TRY {
555 Node *concreteNode = concrete(cur);
556 node_create(x.d, update, concreteNode->key, concreteNode->value);
557 } QT_CATCH(...) {
558 freeData(x.d);
559 QT_RETHROW;
560 }
561 cur = cur->forward[0];
562 }
563 x.d->insertInOrder = false;
564 }
565 if (/*!d->ref.deref()*/ d->refMap == this)
566 freeData(d);
567 d = x.d;
568 }
569
570 template <class Key, class T>
571 Q_OUTOFLINE_TEMPLATE CQtManagedRestrictedModificationMapData::Node *CQtManagedRestrictedModificationMap<Key, T>::mutableFindNode(CQtManagedRestrictedModificationMapData::Node *aupdate[],
572 const Key &akey) const
573 {
574 CQtManagedRestrictedModificationMapData::Node *cur = e;
575 CQtManagedRestrictedModificationMapData::Node *next = e;
576
577 for (int i = d->topLevel; i >= 0; i--) {
578 while ((next = cur->forward[i]) != e && cMapLessThanKey<Key>(concrete(next)->key, akey))
579 cur = next;
580 aupdate[i] = cur;
581 }
582 if (next != e && !cMapLessThanKey<Key>(akey, concrete(next)->key)) {
583 return next;
584 } else {
585 return e;
586 }
587 }
588
589 template <class Key, class T>
590 Q_OUTOFLINE_TEMPLATE QList<Key> CQtManagedRestrictedModificationMap<Key, T>::uniqueKeys() const
591 {
592 QList<Key> res;
593 res.reserve(size()); // May be too much, but assume short lifetime
594 const_iterator i = begin();
595 if (i != end()) {
596 for (;;) {
597 const Key &aKey = i.key();
598 res.append(aKey);
599 do {
600 if (++i == end())
601 goto break_out_of_outer_loop;
602 } while (!(aKey < i.key())); // loop while (key == i.key())
603 }
604 }
605 break_out_of_outer_loop:
606 return res;
607 }
608
609 template <class Key, class T>
610 Q_OUTOFLINE_TEMPLATE QList<Key> CQtManagedRestrictedModificationMap<Key, T>::keys() const
611 {
612 QList<Key> res;
613 res.reserve(size());
614 const_iterator i = begin();
615 while (i != end()) {
616 res.append(i.key());
617 ++i;
618 }
619 return res;
620 }
621
622 template <class Key, class T>
623 Q_OUTOFLINE_TEMPLATE QList<Key> CQtManagedRestrictedModificationMap<Key, T>::keys(const T &avalue) const
624 {
625 QList<Key> res;
626 const_iterator i = begin();
627 while (i != end()) {
628 if (i.value() == avalue)
629 res.append(i.key());
630 ++i;
631 }
632 return res;
633 }
634
635 template <class Key, class T>
636 Q_OUTOFLINE_TEMPLATE const Key CQtManagedRestrictedModificationMap<Key, T>::key(const T &avalue) const
637 {
638 return key(avalue, Key());
639 }
640
641 template <class Key, class T>
642 Q_OUTOFLINE_TEMPLATE const Key CQtManagedRestrictedModificationMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
643 {
644 const_iterator i = begin();
645 while (i != end()) {
646 if (i.value() == avalue)
647 return i.key();
648 ++i;
649 }
650
651 return defaultKey;
652 }
653
654 template <class Key, class T>
655 Q_OUTOFLINE_TEMPLATE QList<T> CQtManagedRestrictedModificationMap<Key, T>::values() const
656 {
657 QList<T> res;
658 res.reserve(size());
659 const_iterator i = begin();
660 while (i != end()) {
661 res.append(i.value());
662 ++i;
663 }
664 return res;
665 }
666
667 template <class Key, class T>
668 Q_OUTOFLINE_TEMPLATE QList<T> CQtManagedRestrictedModificationMap<Key, T>::values(const Key &akey) const
669 {
670 QList<T> res;
671 CQtManagedRestrictedModificationMapData::Node *node = findNode(akey);
672 if (node != e) {
673 do {
674 res.append(concrete(node)->value);
675 node = node->forward[0];
676 } while (node != e && !cMapLessThanKey<Key>(akey, concrete(node)->key));
677 }
678 return res;
679 }
680
681 template <class Key, class T>
682 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::const_iterator
683 CQtManagedRestrictedModificationMap<Key, T>::lowerBound(const Key &akey) const
684 {
685 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
686 mutableFindNode(update, akey);
687 return const_iterator(update[0]->forward[0]);
688 }
689
690 template <class Key, class T>
691 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::lowerBound(const Key &akey)
692 {
693 detach();
694 return static_cast<CQtManagedRestrictedModificationMapData::Node *>(const_cast<const CQtManagedRestrictedModificationMap *>(this)->lowerBound(akey));
695 }
696
697 template <class Key, class T>
698 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::const_iterator
699 CQtManagedRestrictedModificationMap<Key, T>::upperBound(const Key &akey) const
700 {
701 CQtManagedRestrictedModificationMapData::Node *update[CQtManagedRestrictedModificationMapData::LastLevel + 1];
702 mutableFindNode(update, akey);
703 CQtManagedRestrictedModificationMapData::Node *node = update[0]->forward[0];
704 while (node != e && !cMapLessThanKey<Key>(akey, concrete(node)->key))
705 node = node->forward[0];
706 return const_iterator(node);
707 }
708
709 template <class Key, class T>
710 Q_INLINE_TEMPLATE typename CQtManagedRestrictedModificationMap<Key, T>::iterator CQtManagedRestrictedModificationMap<Key, T>::upperBound(const Key &akey)
711 {
712 detach();
713 return static_cast<CQtManagedRestrictedModificationMapData::Node *>(const_cast<const CQtManagedRestrictedModificationMap *>(this)->upperBound(akey));
714 }
715
716 template <class Key, class T>
717 Q_OUTOFLINE_TEMPLATE bool CQtManagedRestrictedModificationMap<Key, T>::operator==(const CQtManagedRestrictedModificationMap<Key, T> &other) const
718 {
719 if (size() != other.size())
720 return false;
721 if (d == other.d)
722 return true;
723
724 const_iterator it1 = begin();
725 const_iterator it2 = other.begin();
726
727 while (it1 != end()) {
728 if (!(it1.value() == it2.value()) || cMapLessThanKey(it1.key(), it2.key()) || cMapLessThanKey(it2.key(), it1.key()))
729 return false;
730 ++it2;
731 ++it1;
732 }
733 return true;
734 }
735
736 #ifndef QT_NO_STL
737 template <class Key, class T>
738 Q_OUTOFLINE_TEMPLATE CQtManagedRestrictedModificationMap<Key, T>::CQtManagedRestrictedModificationMap(const std::map<Key, T> &other)
739 {
740 d = CQtManagedRestrictedModificationMapData::createData(alignment(), this, mMemMan);
741 d->insertInOrder = true;
742 typename std::map<Key,T>::const_iterator it = other.end();
743 while (it != other.begin()) {
744 --it;
745 insert((*it).first, (*it).second);
746 }
747 d->insertInOrder = false;
748 }
749
750 template <class Key, class T>
751 Q_OUTOFLINE_TEMPLATE std::map<Key, T> CQtManagedRestrictedModificationMap<Key, T>::toStdMap() const
752 {
753 std::map<Key, T> map;
754 const_iterator it = end();
755 while (it != begin()) {
756 --it;
757 map.insert(std::pair<Key, T>(it.key(), it.value()));
758 }
759 return map;
760 }
761
762 #endif // QT_NO_STL
763
764
765 #endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_MAP_CONTAINER
766
767
768 }; // end namespace Container
769
770 }; // end namespace Utilities
771
772 }; // end namespace Konclude
773
774 #endif // KONCLUDE_UTILITIES_CONTAINER_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_CPP
775