File indexing completed on 2024-10-20 03:40:06
0001 /* 0002 0003 SPDX-FileCopyrightText: 2010 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.net> 0004 SPDX-FileContributor: Stephen Kelly <stephen@kdab.com> 0005 0006 SPDX-License-Identifier: LGPL-2.0-or-later 0007 */ 0008 0009 #ifndef KBIHASH_P_H 0010 #define KBIHASH_P_H 0011 0012 #include <QHash> 0013 #include <QMap> 0014 0015 #include <QDebug> 0016 0017 template<typename LeftContainer, typename RightContainer> 0018 class KBiAssociativeContainer; 0019 0020 template<typename LeftContainer, typename RightContainer> 0021 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container); 0022 0023 template<typename LeftContainer, typename RightContainer> 0024 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container); 0025 0026 template<typename LeftContainer, typename RightContainer> 0027 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container); 0028 0029 template<typename LeftContainer, typename RightContainer> 0030 class KBiAssociativeContainer 0031 { 0032 // We need to convert from a QHash::iterator or QMap::iterator 0033 // to a KBiAssociativeContainer::iterator (left or right) 0034 // Do do that we use this implicit ctor. We partially specialize 0035 // it for QHash and QMap types. 0036 // Our iterator inherits from this struct to get the implicit ctor, 0037 // and this struct must inherit from the QHash or QMap iterator. 0038 template<typename Container, typename T, typename U> 0039 struct _iterator_impl_ctor : public Container::iterator { 0040 _iterator_impl_ctor(typename Container::iterator it); 0041 }; 0042 0043 template<typename T, typename U> 0044 struct _iterator_impl_ctor<QHash<T, U>, T, U> : public QHash<T, U>::iterator { 0045 /* implicit */ _iterator_impl_ctor(const typename QHash<T, U>::iterator it) 0046 : QHash<T, U>::iterator(it) 0047 { 0048 } 0049 }; 0050 0051 template<typename T, typename U> 0052 struct _iterator_impl_ctor<QMap<T, U>, T, U> : public QMap<T, U>::iterator { 0053 /* implicit */ _iterator_impl_ctor(const typename QMap<T, U>::iterator it) 0054 : QMap<T, U>::iterator(it) 0055 { 0056 } 0057 }; 0058 0059 public: 0060 typedef typename RightContainer::mapped_type left_type; 0061 typedef typename LeftContainer::mapped_type right_type; 0062 0063 template<typename Container> 0064 class _iterator : public _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type> 0065 { 0066 public: 0067 explicit inline _iterator(void *data) 0068 : Container::iterator(data) 0069 { 0070 } 0071 0072 /* implicit */ _iterator(const typename Container::iterator it) 0073 : _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>(it) 0074 { 0075 } 0076 0077 inline const typename Container::mapped_type &value() const 0078 { 0079 return Container::iterator::value(); 0080 } 0081 inline const typename Container::mapped_type &operator*() const 0082 { 0083 return Container::iterator::operator*(); 0084 } 0085 inline const typename Container::mapped_type *operator->() const 0086 { 0087 return Container::iterator::operator->(); 0088 } 0089 0090 private: 0091 #ifndef Q_CC_MSVC 0092 using Container::iterator::operator*; 0093 using Container::iterator::operator->; 0094 using Container::iterator::value; 0095 #endif 0096 }; 0097 0098 typedef _iterator<LeftContainer> left_iterator; 0099 typedef typename LeftContainer::const_iterator left_const_iterator; 0100 typedef _iterator<RightContainer> right_iterator; 0101 typedef typename RightContainer::const_iterator right_const_iterator; 0102 0103 inline KBiAssociativeContainer() 0104 { 0105 } 0106 inline KBiAssociativeContainer(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0107 { 0108 *this = other; 0109 } 0110 0111 const KBiAssociativeContainer<LeftContainer, RightContainer> &operator=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0112 { 0113 _leftToRight = other._leftToRight; 0114 _rightToLeft = other._rightToLeft; 0115 return *this; 0116 } 0117 0118 inline bool removeLeft(left_type t) 0119 { 0120 const right_type u = _leftToRight.take(t); 0121 return _rightToLeft.remove(u) != 0; 0122 } 0123 0124 inline bool removeRight(right_type u) 0125 { 0126 const left_type t = _rightToLeft.take(u); 0127 return _leftToRight.remove(t) != 0; 0128 } 0129 0130 inline right_type takeLeft(left_type t) 0131 { 0132 const right_type u = _leftToRight.take(t); 0133 _rightToLeft.remove(u); 0134 return u; 0135 } 0136 0137 inline left_type takeRight(right_type u) 0138 { 0139 const left_type t = _rightToLeft.take(u); 0140 _leftToRight.remove(t); 0141 return t; 0142 } 0143 0144 inline left_type rightToLeft(right_type u) const 0145 { 0146 return _rightToLeft.value(u); 0147 } 0148 0149 inline right_type leftToRight(left_type t) const 0150 { 0151 return _leftToRight.value(t); 0152 } 0153 0154 inline bool leftContains(left_type t) const 0155 { 0156 return _leftToRight.contains(t); 0157 } 0158 0159 inline bool rightContains(right_type u) const 0160 { 0161 return _rightToLeft.contains(u); 0162 } 0163 0164 inline int size() const 0165 { 0166 return _leftToRight.size(); 0167 } 0168 0169 inline int count() const 0170 { 0171 return _leftToRight.count(); 0172 } 0173 0174 inline int capacity() const 0175 { 0176 return _leftToRight.capacity(); 0177 } 0178 0179 void reserve(int size) 0180 { 0181 _leftToRight.reserve(size); 0182 _rightToLeft.reserve(size); 0183 } 0184 0185 inline void squeeze() 0186 { 0187 _leftToRight.squeeze(); 0188 _rightToLeft.squeeze(); 0189 } 0190 0191 inline void detach() 0192 { 0193 _leftToRight.detach(); 0194 _rightToLeft.detach(); 0195 } 0196 0197 inline bool isDetached() const 0198 { 0199 return _leftToRight.isDetached(); 0200 } 0201 0202 inline void setSharable(bool sharable) 0203 { 0204 _leftToRight.setSharable(sharable); 0205 _rightToLeft.setSharable(sharable); 0206 } 0207 0208 inline bool isSharedWith(const KBiAssociativeContainer<RightContainer, LeftContainer> &other) const 0209 { 0210 return _leftToRight.isSharedWith(other._leftToRight) && _rightToLeft.isSharedWith(other._leftToRight); 0211 } 0212 0213 void clear() 0214 { 0215 _leftToRight.clear(); 0216 _rightToLeft.clear(); 0217 } 0218 0219 QList<left_type> leftValues() const 0220 { 0221 return _leftToRight.keys(); 0222 } 0223 0224 QList<right_type> rightValues() const 0225 { 0226 return _rightToLeft.keys(); 0227 } 0228 0229 right_iterator eraseRight(right_iterator it) 0230 { 0231 Q_ASSERT(it != rightEnd()); 0232 _leftToRight.remove(it.value()); 0233 return _rightToLeft.erase(it); 0234 } 0235 0236 left_iterator eraseLeft(left_iterator it) 0237 { 0238 Q_ASSERT(it != leftEnd()); 0239 _rightToLeft.remove(it.value()); 0240 return _leftToRight.erase(it); 0241 } 0242 0243 left_iterator findLeft(left_type t) 0244 { 0245 return _leftToRight.find(t); 0246 } 0247 0248 left_const_iterator findLeft(left_type t) const 0249 { 0250 return _leftToRight.find(t); 0251 } 0252 0253 left_const_iterator constFindLeft(left_type t) const 0254 { 0255 return _leftToRight.constFind(t); 0256 } 0257 0258 right_iterator findRight(right_type u) 0259 { 0260 return _rightToLeft.find(u); 0261 } 0262 0263 right_const_iterator findRight(right_type u) const 0264 { 0265 return _rightToLeft.find(u); 0266 } 0267 0268 right_const_iterator constFindRight(right_type u) const 0269 { 0270 return _rightToLeft.find(u); 0271 } 0272 0273 left_iterator insert(left_type t, right_type u) 0274 { 0275 // biHash.insert(5, 7); // creates 5->7 in _leftToRight and 7->5 in _rightToLeft 0276 // biHash.insert(5, 9); // replaces 5->7 with 5->9 in _leftToRight and inserts 9->5 in _rightToLeft. 0277 // The 7->5 in _rightToLeft would be dangling, so we remove it before insertion. 0278 0279 // This means we need to hash u and t up to twice each. Could probably be done better using QHashNode. 0280 0281 if (_leftToRight.contains(t)) { 0282 _rightToLeft.remove(_leftToRight.take(t)); 0283 } 0284 if (_rightToLeft.contains(u)) { 0285 _leftToRight.remove(_rightToLeft.take(u)); 0286 } 0287 0288 _rightToLeft.insert(u, t); 0289 return _leftToRight.insert(t, u); 0290 } 0291 0292 KBiAssociativeContainer<LeftContainer, RightContainer> &intersect(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0293 { 0294 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin(); 0295 while (it != leftEnd()) { 0296 if (!other.leftContains(it.key())) { 0297 it = eraseLeft(it); 0298 } else { 0299 ++it; 0300 } 0301 } 0302 return *this; 0303 } 0304 0305 KBiAssociativeContainer<LeftContainer, RightContainer> &subtract(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0306 { 0307 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin(); 0308 while (it != leftEnd()) { 0309 if (other._leftToRight.contains(it.key())) { 0310 it = eraseLeft(it); 0311 } else { 0312 ++it; 0313 } 0314 } 0315 return *this; 0316 } 0317 0318 KBiAssociativeContainer<LeftContainer, RightContainer> &unite(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0319 { 0320 typename LeftContainer::const_iterator it = other._leftToRight.constBegin(); 0321 const typename LeftContainer::const_iterator end = other._leftToRight.constEnd(); 0322 while (it != end) { 0323 const left_type key = it.key(); 0324 if (!_leftToRight.contains(key)) { 0325 insert(key, it.value()); 0326 } 0327 ++it; 0328 } 0329 return *this; 0330 } 0331 0332 void updateRight(left_iterator it, right_type u) 0333 { 0334 Q_ASSERT(it != leftEnd()); 0335 const left_type key = it.key(); 0336 _rightToLeft.remove(_leftToRight.value(key)); 0337 _leftToRight[key] = u; 0338 _rightToLeft[u] = key; 0339 } 0340 0341 void updateLeft(right_iterator it, left_type t) 0342 { 0343 Q_ASSERT(it != rightEnd()); 0344 const right_type key = it.key(); 0345 _leftToRight.remove(_rightToLeft.value(key)); 0346 _rightToLeft[key] = t; 0347 _leftToRight[t] = key; 0348 } 0349 0350 inline bool isEmpty() const 0351 { 0352 return _leftToRight.isEmpty(); 0353 } 0354 0355 const right_type operator[](const left_type &t) const 0356 { 0357 return _leftToRight.operator[](t); 0358 } 0359 0360 bool operator==(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0361 { 0362 return _leftToRight.operator==(other._leftToRight); 0363 } 0364 0365 bool operator!=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 0366 { 0367 return _leftToRight.operator!=(other._leftToRight); 0368 } 0369 0370 left_iterator toLeftIterator(right_iterator it) const 0371 { 0372 Q_ASSERT(it != rightEnd()); 0373 return _leftToRight.find(it.value()); 0374 } 0375 0376 right_iterator toRightIterator(left_iterator it) const 0377 { 0378 Q_ASSERT(it != leftEnd()); 0379 return _rightToLeft.find(it.value()); 0380 } 0381 0382 inline left_iterator leftBegin() 0383 { 0384 return _leftToRight.begin(); 0385 } 0386 0387 inline left_iterator leftEnd() 0388 { 0389 return _leftToRight.end(); 0390 } 0391 0392 inline left_const_iterator leftBegin() const 0393 { 0394 return _leftToRight.begin(); 0395 } 0396 0397 inline left_const_iterator leftEnd() const 0398 { 0399 return _leftToRight.end(); 0400 } 0401 0402 inline left_const_iterator leftConstBegin() const 0403 { 0404 return _leftToRight.constBegin(); 0405 } 0406 0407 inline left_const_iterator leftConstEnd() const 0408 { 0409 return _leftToRight.constEnd(); 0410 } 0411 0412 inline right_iterator rightBegin() 0413 { 0414 return _rightToLeft.begin(); 0415 } 0416 0417 inline right_iterator rightEnd() 0418 { 0419 return _rightToLeft.end(); 0420 } 0421 0422 inline right_const_iterator rightBegin() const 0423 { 0424 return _rightToLeft.begin(); 0425 } 0426 0427 inline right_const_iterator rightEnd() const 0428 { 0429 return _rightToLeft.end(); 0430 } 0431 inline right_const_iterator rightConstBegin() const 0432 { 0433 return _rightToLeft.constBegin(); 0434 } 0435 0436 inline right_const_iterator rightConstEnd() const 0437 { 0438 return _rightToLeft.constEnd(); 0439 } 0440 0441 static KBiAssociativeContainer<LeftContainer, RightContainer> fromHash(const QHash<left_type, right_type> &hash) 0442 { 0443 KBiAssociativeContainer<LeftContainer, RightContainer> container; 0444 typename QHash<left_type, right_type>::const_iterator it = hash.constBegin(); 0445 const typename QHash<left_type, right_type>::const_iterator end = hash.constEnd(); 0446 for (; it != end; ++it) { 0447 container.insert(it.key(), it.value()); 0448 } 0449 return container; 0450 } 0451 0452 static KBiAssociativeContainer<LeftContainer, RightContainer> fromMap(const QMap<left_type, right_type> &hash) 0453 { 0454 KBiAssociativeContainer<LeftContainer, RightContainer> container; 0455 typename QMap<left_type, right_type>::const_iterator it = hash.constBegin(); 0456 const typename QMap<left_type, right_type>::const_iterator end = hash.constEnd(); 0457 for (; it != end; ++it) { 0458 container.insert(it.key(), it.value()); 0459 } 0460 return container; 0461 } 0462 0463 friend QDataStream &operator<<<LeftContainer, RightContainer>(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &bihash); 0464 friend QDataStream &operator>><LeftContainer, RightContainer>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &biHash); 0465 friend QDebug operator<<<LeftContainer, RightContainer>(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &biHash); 0466 0467 protected: 0468 LeftContainer _leftToRight; 0469 RightContainer _rightToLeft; 0470 }; 0471 0472 template<typename LeftContainer, typename RightContainer> 0473 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container) 0474 { 0475 return out << container._leftToRight; 0476 } 0477 0478 template<typename LeftContainer, typename RightContainer> 0479 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container) 0480 { 0481 LeftContainer leftToRight; 0482 in >> leftToRight; 0483 typename LeftContainer::const_iterator it = leftToRight.constBegin(); 0484 const typename LeftContainer::const_iterator end = leftToRight.constEnd(); 0485 for (; it != end; ++it) { 0486 container.insert(it.key(), it.value()); 0487 } 0488 0489 return in; 0490 } 0491 0492 template<typename Container, typename T, typename U> 0493 struct _containerType { 0494 operator const char *(); 0495 }; 0496 0497 template<typename T, typename U> 0498 struct _containerType<QHash<T, U>, T, U> { 0499 operator const char *() 0500 { 0501 return "QHash"; 0502 } 0503 }; 0504 0505 template<typename T, typename U> 0506 struct _containerType<QMap<T, U>, T, U> { 0507 operator const char *() 0508 { 0509 return "QMap"; 0510 } 0511 }; 0512 0513 template<typename Container> 0514 static const char *containerType() 0515 { 0516 return _containerType<Container, typename Container::key_type, typename Container::mapped_type>(); 0517 } 0518 0519 template<typename LeftContainer, typename RightContainer> 0520 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container) 0521 { 0522 typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator it = container.leftConstBegin(); 0523 0524 const typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator end = container.leftConstEnd(); 0525 out.nospace() << "KBiAssociativeContainer<" << containerType<LeftContainer>() << ", " << containerType<RightContainer>() << ">" 0526 << "("; 0527 for (; it != end; ++it) { 0528 out << "(" << it.key() << " <=> " << it.value() << ") "; 0529 } 0530 0531 out << ")"; 0532 return out; 0533 } 0534 0535 /** 0536 * @brief KBiHash provides a bi-directional hash container 0537 * 0538 * @note This class is designed to make mapping easier in proxy model implementations. 0539 * 0540 * @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. 0541 */ 0542 template<typename T, typename U> 0543 struct KBiHash : public KBiAssociativeContainer<QHash<T, U>, QHash<U, T>> { 0544 KBiHash() 0545 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T>>() 0546 { 0547 } 0548 0549 KBiHash(const KBiAssociativeContainer<QHash<T, U>, QHash<U, T>> &container) 0550 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T>>(container) 0551 { 0552 } 0553 }; 0554 0555 template<typename T, typename U> 0556 QDebug operator<<(QDebug out, const KBiHash<T, U> &biHash) 0557 { 0558 typename KBiHash<T, U>::left_const_iterator it = biHash.leftConstBegin(); 0559 0560 const typename KBiHash<T, U>::left_const_iterator end = biHash.leftConstEnd(); 0561 out.nospace() << "KBiHash("; 0562 for (; it != end; ++it) { 0563 out << "(" << it.key() << " <=> " << it.value() << ") "; 0564 } 0565 0566 out << ")"; 0567 return out; 0568 } 0569 0570 template<typename T, typename U> 0571 struct KHash2Map : public KBiAssociativeContainer<QHash<T, U>, QMap<U, T>> { 0572 KHash2Map() 0573 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>() 0574 { 0575 } 0576 0577 KHash2Map(const KBiAssociativeContainer<QHash<T, U>, QMap<U, T>> &container) 0578 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>(container) 0579 { 0580 } 0581 0582 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_iterator rightLowerBound(const U &key) 0583 { 0584 return this->_rightToLeft.lowerBound(key); 0585 } 0586 0587 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_const_iterator rightLowerBound(const U &key) const 0588 { 0589 return this->_rightToLeft.lowerBound(key); 0590 } 0591 0592 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_iterator rightUpperBound(const U &key) 0593 { 0594 return this->_rightToLeft.upperBound(key); 0595 } 0596 0597 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_const_iterator rightUpperBound(const U &key) const 0598 { 0599 return this->_rightToLeft.upperBound(key); 0600 } 0601 }; 0602 0603 template<typename T, typename U> 0604 QDebug operator<<(QDebug out, const KHash2Map<T, U> &container) 0605 { 0606 typename KHash2Map<T, U>::left_const_iterator it = container.leftConstBegin(); 0607 0608 const typename KHash2Map<T, U>::left_const_iterator end = container.leftConstEnd(); 0609 out.nospace() << "KHash2Map("; 0610 for (; it != end; ++it) { 0611 out << "(" << it.key() << " <=> " << it.value() << ") "; 0612 } 0613 0614 out << ")"; 0615 return out; 0616 } 0617 0618 #endif