1/*
2
3 SPDX-FileCopyrightText: 2010 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.net>
4 SPDX-FileContributor: Stephen Kelly <stephen@kdab.com>
5
6 SPDX-License-Identifier: LGPL-2.0-or-later
7*/
8
9#ifndef KBIHASH_P_H
10#define KBIHASH_P_H
11
12#include <QHash>
13#include <QMap>
14
15#include <QDebug>
16
17template<typename LeftContainer, typename RightContainer>
18class KBiAssociativeContainer;
19
20template<typename LeftContainer, typename RightContainer>
21QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container);
22
23template<typename LeftContainer, typename RightContainer>
24QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container);
25
26template<typename LeftContainer, typename RightContainer>
27QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container);
28
29template<typename LeftContainer, typename RightContainer>
30class KBiAssociativeContainer
31{
32 // We need to convert from a QHash::iterator or QMap::iterator
33 // to a KBiAssociativeContainer::iterator (left or right)
34 // Do do that we use this implicit ctor. We partially specialize
35 // it for QHash and QMap types.
36 // Our iterator inherits from this struct to get the implicit ctor,
37 // and this struct must inherit from the QHash or QMap iterator.
38 template<typename Container, typename T, typename U>
39 struct _iterator_impl_ctor : public Container::iterator {
40 _iterator_impl_ctor(typename Container::iterator it);
41 };
42
43 template<typename T, typename U>
44 struct _iterator_impl_ctor<QHash<T, U>, T, U> : public QHash<T, U>::iterator {
45 /* implicit */ _iterator_impl_ctor(const typename QHash<T, U>::iterator it)
46 : QHash<T, U>::iterator(it)
47 {
48 }
49 };
50
51 template<typename T, typename U>
52 struct _iterator_impl_ctor<QMap<T, U>, T, U> : public QMap<T, U>::iterator {
53 /* implicit */ _iterator_impl_ctor(const typename QMap<T, U>::iterator it)
54 : QMap<T, U>::iterator(it)
55 {
56 }
57 };
58
59public:
60 typedef typename RightContainer::mapped_type left_type;
61 typedef typename LeftContainer::mapped_type right_type;
62
63 template<typename Container>
64 class _iterator : public _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>
65 {
66 public:
67 explicit inline _iterator(void *data)
68 : Container::iterator(data)
69 {
70 }
71
72 /* implicit */ _iterator(const typename Container::iterator it)
73 : _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>(it)
74 {
75 }
76
77 inline const typename Container::mapped_type &value() const
78 {
79 return Container::iterator::value();
80 }
81 inline const typename Container::mapped_type &operator*() const
82 {
83 return Container::iterator::operator*();
84 }
85 inline const typename Container::mapped_type *operator->() const
86 {
87 return Container::iterator::operator->();
88 }
89
90 private:
91#ifndef Q_CC_MSVC
92 using Container::iterator::operator*;
93 using Container::iterator::operator->;
94 using Container::iterator::value;
95#endif
96 };
97
98 typedef _iterator<LeftContainer> left_iterator;
99 typedef typename LeftContainer::const_iterator left_const_iterator;
100 typedef _iterator<RightContainer> right_iterator;
101 typedef typename RightContainer::const_iterator right_const_iterator;
102
103 inline KBiAssociativeContainer()
104 {
105 }
106 inline KBiAssociativeContainer(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
107 {
108 *this = other;
109 }
110
111 const KBiAssociativeContainer<LeftContainer, RightContainer> &operator=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
112 {
113 _leftToRight = other._leftToRight;
114 _rightToLeft = other._rightToLeft;
115 return *this;
116 }
117
118 inline bool removeLeft(left_type t)
119 {
120 const right_type u = _leftToRight.take(t);
121 return _rightToLeft.remove(u) != 0;
122 }
123
124 inline bool removeRight(right_type u)
125 {
126 const left_type t = _rightToLeft.take(u);
127 return _leftToRight.remove(t) != 0;
128 }
129
130 inline right_type takeLeft(left_type t)
131 {
132 const right_type u = _leftToRight.take(t);
133 _rightToLeft.remove(u);
134 return u;
135 }
136
137 inline left_type takeRight(right_type u)
138 {
139 const left_type t = _rightToLeft.take(u);
140 _leftToRight.remove(t);
141 return t;
142 }
143
144 inline left_type rightToLeft(right_type u) const
145 {
146 return _rightToLeft.value(u);
147 }
148
149 inline right_type leftToRight(left_type t) const
150 {
151 return _leftToRight.value(t);
152 }
153
154 inline bool leftContains(left_type t) const
155 {
156 return _leftToRight.contains(t);
157 }
158
159 inline bool rightContains(right_type u) const
160 {
161 return _rightToLeft.contains(u);
162 }
163
164 inline int size() const
165 {
166 return _leftToRight.size();
167 }
168
169 inline int count() const
170 {
171 return _leftToRight.count();
172 }
173
174 inline int capacity() const
175 {
176 return _leftToRight.capacity();
177 }
178
179 void reserve(int size)
180 {
181 _leftToRight.reserve(size);
182 _rightToLeft.reserve(size);
183 }
184
185 inline void squeeze()
186 {
187 _leftToRight.squeeze();
188 _rightToLeft.squeeze();
189 }
190
191 inline void detach()
192 {
193 _leftToRight.detach();
194 _rightToLeft.detach();
195 }
196
197 inline bool isDetached() const
198 {
199 return _leftToRight.isDetached();
200 }
201
202 inline void setSharable(bool sharable)
203 {
204 _leftToRight.setSharable(sharable);
205 _rightToLeft.setSharable(sharable);
206 }
207
208 inline bool isSharedWith(const KBiAssociativeContainer<RightContainer, LeftContainer> &other) const
209 {
210 return _leftToRight.isSharedWith(other._leftToRight) && _rightToLeft.isSharedWith(other._leftToRight);
211 }
212
213 void clear()
214 {
215 _leftToRight.clear();
216 _rightToLeft.clear();
217 }
218
219 QList<left_type> leftValues() const
220 {
221 return _leftToRight.keys();
222 }
223
224 QList<right_type> rightValues() const
225 {
226 return _rightToLeft.keys();
227 }
228
229 right_iterator eraseRight(right_iterator it)
230 {
231 Q_ASSERT(it != rightEnd());
232 _leftToRight.remove(it.value());
233 return _rightToLeft.erase(it);
234 }
235
236 left_iterator eraseLeft(left_iterator it)
237 {
238 Q_ASSERT(it != leftEnd());
239 _rightToLeft.remove(it.value());
240 return _leftToRight.erase(it);
241 }
242
243 left_iterator findLeft(left_type t)
244 {
245 return _leftToRight.find(t);
246 }
247
248 left_const_iterator findLeft(left_type t) const
249 {
250 return _leftToRight.find(t);
251 }
252
253 left_const_iterator constFindLeft(left_type t) const
254 {
255 return _leftToRight.constFind(t);
256 }
257
258 right_iterator findRight(right_type u)
259 {
260 return _rightToLeft.find(u);
261 }
262
263 right_const_iterator findRight(right_type u) const
264 {
265 return _rightToLeft.find(u);
266 }
267
268 right_const_iterator constFindRight(right_type u) const
269 {
270 return _rightToLeft.find(u);
271 }
272
273 left_iterator insert(left_type t, right_type u)
274 {
275 // biHash.insert(5, 7); // creates 5->7 in _leftToRight and 7->5 in _rightToLeft
276 // biHash.insert(5, 9); // replaces 5->7 with 5->9 in _leftToRight and inserts 9->5 in _rightToLeft.
277 // The 7->5 in _rightToLeft would be dangling, so we remove it before insertion.
278
279 // This means we need to hash u and t up to twice each. Could probably be done better using QHashNode.
280
281 if (_leftToRight.contains(t)) {
282 _rightToLeft.remove(_leftToRight.take(t));
283 }
284 if (_rightToLeft.contains(u)) {
285 _leftToRight.remove(_rightToLeft.take(u));
286 }
287
288 _rightToLeft.insert(u, t);
289 return _leftToRight.insert(t, u);
290 }
291
292 KBiAssociativeContainer<LeftContainer, RightContainer> &intersect(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
293 {
294 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin();
295 while (it != leftEnd()) {
296 if (!other.leftContains(it.key())) {
297 it = eraseLeft(it);
298 } else {
299 ++it;
300 }
301 }
302 return *this;
303 }
304
305 KBiAssociativeContainer<LeftContainer, RightContainer> &subtract(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
306 {
307 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin();
308 while (it != leftEnd()) {
309 if (other._leftToRight.contains(it.key())) {
310 it = eraseLeft(it);
311 } else {
312 ++it;
313 }
314 }
315 return *this;
316 }
317
318 KBiAssociativeContainer<LeftContainer, RightContainer> &unite(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
319 {
320 typename LeftContainer::const_iterator it = other._leftToRight.constBegin();
321 const typename LeftContainer::const_iterator end = other._leftToRight.constEnd();
322 while (it != end) {
323 const left_type key = it.key();
324 if (!_leftToRight.contains(key)) {
325 insert(t: key, u: it.value());
326 }
327 ++it;
328 }
329 return *this;
330 }
331
332 void updateRight(left_iterator it, right_type u)
333 {
334 Q_ASSERT(it != leftEnd());
335 const left_type key = it.key();
336 _rightToLeft.remove(_leftToRight.value(key));
337 _leftToRight[key] = u;
338 _rightToLeft[u] = key;
339 }
340
341 void updateLeft(right_iterator it, left_type t)
342 {
343 Q_ASSERT(it != rightEnd());
344 const right_type key = it.key();
345 _leftToRight.remove(_rightToLeft.value(key));
346 _rightToLeft[key] = t;
347 _leftToRight[t] = key;
348 }
349
350 inline bool isEmpty() const
351 {
352 return _leftToRight.isEmpty();
353 }
354
355 const right_type operator[](const left_type &t) const
356 {
357 return _leftToRight.operator[](t);
358 }
359
360 bool operator==(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
361 {
362 return _leftToRight == other._leftToRight;
363 }
364
365 bool operator!=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
366 {
367 return _leftToRight != other._leftToRight;
368 }
369
370 left_iterator toLeftIterator(right_iterator it) const
371 {
372 Q_ASSERT(it != rightEnd());
373 return _leftToRight.find(it.value());
374 }
375
376 right_iterator toRightIterator(left_iterator it) const
377 {
378 Q_ASSERT(it != leftEnd());
379 return _rightToLeft.find(it.value());
380 }
381
382 inline left_iterator leftBegin()
383 {
384 return _leftToRight.begin();
385 }
386
387 inline left_iterator leftEnd()
388 {
389 return _leftToRight.end();
390 }
391
392 inline left_const_iterator leftBegin() const
393 {
394 return _leftToRight.begin();
395 }
396
397 inline left_const_iterator leftEnd() const
398 {
399 return _leftToRight.end();
400 }
401
402 inline left_const_iterator leftConstBegin() const
403 {
404 return _leftToRight.constBegin();
405 }
406
407 inline left_const_iterator leftConstEnd() const
408 {
409 return _leftToRight.constEnd();
410 }
411
412 inline right_iterator rightBegin()
413 {
414 return _rightToLeft.begin();
415 }
416
417 inline right_iterator rightEnd()
418 {
419 return _rightToLeft.end();
420 }
421
422 inline right_const_iterator rightBegin() const
423 {
424 return _rightToLeft.begin();
425 }
426
427 inline right_const_iterator rightEnd() const
428 {
429 return _rightToLeft.end();
430 }
431 inline right_const_iterator rightConstBegin() const
432 {
433 return _rightToLeft.constBegin();
434 }
435
436 inline right_const_iterator rightConstEnd() const
437 {
438 return _rightToLeft.constEnd();
439 }
440
441 static KBiAssociativeContainer<LeftContainer, RightContainer> fromHash(const QHash<left_type, right_type> &hash)
442 {
443 KBiAssociativeContainer<LeftContainer, RightContainer> container;
444 typename QHash<left_type, right_type>::const_iterator it = hash.constBegin();
445 const typename QHash<left_type, right_type>::const_iterator end = hash.constEnd();
446 for (; it != end; ++it) {
447 container.insert(it.key(), it.value());
448 }
449 return container;
450 }
451
452 static KBiAssociativeContainer<LeftContainer, RightContainer> fromMap(const QMap<left_type, right_type> &hash)
453 {
454 KBiAssociativeContainer<LeftContainer, RightContainer> container;
455 typename QMap<left_type, right_type>::const_iterator it = hash.constBegin();
456 const typename QMap<left_type, right_type>::const_iterator end = hash.constEnd();
457 for (; it != end; ++it) {
458 container.insert(it.key(), it.value());
459 }
460 return container;
461 }
462
463 friend QDataStream &operator<<<LeftContainer, RightContainer>(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &bihash);
464 friend QDataStream &operator>><LeftContainer, RightContainer>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &biHash);
465 friend QDebug operator<<<LeftContainer, RightContainer>(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &biHash);
466
467protected:
468 LeftContainer _leftToRight;
469 RightContainer _rightToLeft;
470};
471
472template<typename LeftContainer, typename RightContainer>
473QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container)
474{
475 return out << container._leftToRight;
476}
477
478template<typename LeftContainer, typename RightContainer>
479QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container)
480{
481 LeftContainer leftToRight;
482 in >> leftToRight;
483 typename LeftContainer::const_iterator it = leftToRight.constBegin();
484 const typename LeftContainer::const_iterator end = leftToRight.constEnd();
485 for (; it != end; ++it) {
486 container.insert(it.key(), it.value());
487 }
488
489 return in;
490}
491
492template<typename Container, typename T, typename U>
493struct _containerType {
494 operator const char *();
495};
496
497template<typename T, typename U>
498struct _containerType<QHash<T, U>, T, U> {
499 operator const char *()
500 {
501 return "QHash";
502 }
503};
504
505template<typename T, typename U>
506struct _containerType<QMap<T, U>, T, U> {
507 operator const char *()
508 {
509 return "QMap";
510 }
511};
512
513template<typename Container>
514static const char *containerType()
515{
516 return _containerType<Container, typename Container::key_type, typename Container::mapped_type>();
517}
518
519template<typename LeftContainer, typename RightContainer>
520QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container)
521{
522 typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator it = container.leftConstBegin();
523
524 const typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator end = container.leftConstEnd();
525 out.nospace() << "KBiAssociativeContainer<" << containerType<LeftContainer>() << ", " << containerType<RightContainer>() << ">"
526 << "(";
527 for (; it != end; ++it) {
528 out << "(" << it.key() << " <=> " << it.value() << ") ";
529 }
530
531 out << ")";
532 return out;
533}
534
535/*
536 * KBiHash provides a bi-directional hash container
537 *
538 * Note: This class is designed to make mapping easier in proxy model implementations.
539 *
540 * TODO: Figure out whether to discard this and use boost::bimap instead, submit it Qt or keep it here and make more direct use of QHashNode.
541 */
542template<typename T, typename U>
543struct KBiHash : public KBiAssociativeContainer<QHash<T, U>, QHash<U, T>> {
544 KBiHash()
545 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T>>()
546 {
547 }
548
549 KBiHash(const KBiAssociativeContainer<QHash<T, U>, QHash<U, T>> &container)
550 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T>>(container)
551 {
552 }
553};
554
555template<typename T, typename U>
556QDebug operator<<(QDebug out, const KBiHash<T, U> &biHash)
557{
558 typename KBiHash<T, U>::left_const_iterator it = biHash.leftConstBegin();
559
560 const typename KBiHash<T, U>::left_const_iterator end = biHash.leftConstEnd();
561 out.nospace() << "KBiHash(";
562 for (; it != end; ++it) {
563 out << "(" << it.key() << " <=> " << it.value() << ") ";
564 }
565
566 out << ")";
567 return out;
568}
569
570template<typename T, typename U>
571struct KHash2Map : public KBiAssociativeContainer<QHash<T, U>, QMap<U, T>> {
572 KHash2Map()
573 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>()
574 {
575 }
576
577 KHash2Map(const KBiAssociativeContainer<QHash<T, U>, QMap<U, T>> &container)
578 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>(container)
579 {
580 }
581
582 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_iterator rightLowerBound(const U &key)
583 {
584 return this->_rightToLeft.lowerBound(key);
585 }
586
587 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_const_iterator rightLowerBound(const U &key) const
588 {
589 return this->_rightToLeft.lowerBound(key);
590 }
591
592 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_iterator rightUpperBound(const U &key)
593 {
594 return this->_rightToLeft.upperBound(key);
595 }
596
597 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_const_iterator rightUpperBound(const U &key) const
598 {
599 return this->_rightToLeft.upperBound(key);
600 }
601};
602
603template<typename T, typename U>
604QDebug operator<<(QDebug out, const KHash2Map<T, U> &container)
605{
606 typename KHash2Map<T, U>::left_const_iterator it = container.leftConstBegin();
607
608 const typename KHash2Map<T, U>::left_const_iterator end = container.leftConstEnd();
609 out.nospace() << "KHash2Map(";
610 for (; it != end; ++it) {
611 out << "(" << it.key() << " <=> " << it.value() << ") ";
612 }
613
614 out << ")";
615 return out;
616}
617
618#endif
619

source code of kitemmodels/src/core/kbihash_p.h