File indexing completed on 2024-07-21 06:38:21

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