File indexing completed on 2024-05-05 03:56:40

 /*
 
     SPDX-FileCopyrightText: 2010 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.net>
     SPDX-FileContributor: Stephen Kelly <stephen@kdab.com>
 
     SPDX-License-Identifier: LGPL-2.0-or-later
 */
 
 #ifndef KBIHASH_P_H
 #define KBIHASH_P_H
 
 #include <QHash>
 #include <QMap>
 
 #include <QDebug>
 
 template<typename LeftContainer, typename RightContainer>
 class KBiAssociativeContainer;
 
 template<typename LeftContainer, typename RightContainer>
 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container);
 
 template<typename LeftContainer, typename RightContainer>
 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container);
 
 template<typename LeftContainer, typename RightContainer>
 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container);
 
 template<typename LeftContainer, typename RightContainer>
 class KBiAssociativeContainer
 {
     // We need to convert from a QHash::iterator or QMap::iterator
     // to a KBiAssociativeContainer::iterator (left or right)
     // Do do that we use this implicit ctor. We partially specialize
     // it for QHash and QMap types.
     // Our iterator inherits from this struct to get the implicit ctor,
     // and this struct must inherit from the QHash or QMap iterator.
     template<typename Container, typename T, typename U>
     struct _iterator_impl_ctor : public Container::iterator {
         _iterator_impl_ctor(typename Container::iterator it);
     };
 
     template<typename T, typename U>
     struct _iterator_impl_ctor<QHash<T, U>, T, U> : public QHash<T, U>::iterator {
         /* implicit */ _iterator_impl_ctor(const typename QHash<T, U>::iterator it)
             : QHash<T, U>::iterator(it)
         {
         }
     };
 
     template<typename T, typename U>
     struct _iterator_impl_ctor<QMap<T, U>, T, U> : public QMap<T, U>::iterator {
         /* implicit */ _iterator_impl_ctor(const typename QMap<T, U>::iterator it)
             : QMap<T, U>::iterator(it)
         {
         }
     };
 
 public:
     typedef typename RightContainer::mapped_type left_type;
     typedef typename LeftContainer::mapped_type right_type;
 
     template<typename Container>
     class _iterator : public _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>
     {
     public:
         explicit inline _iterator(void *data)
             : Container::iterator(data)
         {
         }
 
         /* implicit */ _iterator(const typename Container::iterator it)
             : _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>(it)
         {
         }
 
         inline const typename Container::mapped_type &value() const
         {
             return Container::iterator::value();
         }
         inline const typename Container::mapped_type &operator*() const
         {
             return Container::iterator::operator*();
         }
         inline const typename Container::mapped_type *operator->() const
         {
             return Container::iterator::operator->();
         }
 
     private:
 #ifndef Q_CC_MSVC
         using Container::iterator::operator*;
         using Container::iterator::operator->;
         using Container::iterator::value;
 #endif
     };
 
     typedef _iterator<LeftContainer> left_iterator;
     typedef typename LeftContainer::const_iterator left_const_iterator;
     typedef _iterator<RightContainer> right_iterator;
     typedef typename RightContainer::const_iterator right_const_iterator;
 
     inline KBiAssociativeContainer()
     {
     }
     inline KBiAssociativeContainer(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         *this = other;
     }
 
     const KBiAssociativeContainer<LeftContainer, RightContainer> &operator=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         _leftToRight = other._leftToRight;
         _rightToLeft = other._rightToLeft;
         return *this;
     }
 
     inline bool removeLeft(left_type t)
     {
         const right_type u = _leftToRight.take(t);
         return _rightToLeft.remove(u) != 0;
     }
 
     inline bool removeRight(right_type u)
     {
         const left_type t = _rightToLeft.take(u);
         return _leftToRight.remove(t) != 0;
     }
 
     inline right_type takeLeft(left_type t)
     {
         const right_type u = _leftToRight.take(t);
         _rightToLeft.remove(u);
         return u;
     }
 
     inline left_type takeRight(right_type u)
     {
         const left_type t = _rightToLeft.take(u);
         _leftToRight.remove(t);
         return t;
     }
 
     inline left_type rightToLeft(right_type u) const
     {
         return _rightToLeft.value(u);
     }
 
     inline right_type leftToRight(left_type t) const
     {
         return _leftToRight.value(t);
     }
 
     inline bool leftContains(left_type t) const
     {
         return _leftToRight.contains(t);
     }
 
     inline bool rightContains(right_type u) const
     {
         return _rightToLeft.contains(u);
     }
 
     inline int size() const
     {
         return _leftToRight.size();
     }
 
     inline int count() const
     {
         return _leftToRight.count();
     }
 
     inline int capacity() const
     {
         return _leftToRight.capacity();
     }
 
     void reserve(int size)
     {
         _leftToRight.reserve(size);
         _rightToLeft.reserve(size);
     }
 
     inline void squeeze()
     {
         _leftToRight.squeeze();
         _rightToLeft.squeeze();
     }
 
     inline void detach()
     {
         _leftToRight.detach();
         _rightToLeft.detach();
     }
 
     inline bool isDetached() const
     {
         return _leftToRight.isDetached();
     }
 
     inline void setSharable(bool sharable)
     {
         _leftToRight.setSharable(sharable);
         _rightToLeft.setSharable(sharable);
     }
 
     inline bool isSharedWith(const KBiAssociativeContainer<RightContainer, LeftContainer> &other) const
     {
         return _leftToRight.isSharedWith(other._leftToRight) && _rightToLeft.isSharedWith(other._leftToRight);
     }
 
     void clear()
     {
         _leftToRight.clear();
         _rightToLeft.clear();
     }
 
     QList<left_type> leftValues() const
     {
         return _leftToRight.keys();
     }
 
     QList<right_type> rightValues() const
     {
         return _rightToLeft.keys();
     }
 
     right_iterator eraseRight(right_iterator it)
     {
         Q_ASSERT(it != rightEnd());
         _leftToRight.remove(it.value());
         return _rightToLeft.erase(it);
     }
 
     left_iterator eraseLeft(left_iterator it)
     {
         Q_ASSERT(it != leftEnd());
         _rightToLeft.remove(it.value());
         return _leftToRight.erase(it);
     }
 
     left_iterator findLeft(left_type t)
     {
         return _leftToRight.find(t);
     }
 
     left_const_iterator findLeft(left_type t) const
     {
         return _leftToRight.find(t);
     }
 
     left_const_iterator constFindLeft(left_type t) const
     {
         return _leftToRight.constFind(t);
     }
 
     right_iterator findRight(right_type u)
     {
         return _rightToLeft.find(u);
     }
 
     right_const_iterator findRight(right_type u) const
     {
         return _rightToLeft.find(u);
     }
 
     right_const_iterator constFindRight(right_type u) const
     {
         return _rightToLeft.find(u);
     }
 
     left_iterator insert(left_type t, right_type u)
     {
         // biHash.insert(5, 7); // creates 5->7 in _leftToRight and 7->5 in _rightToLeft
         // biHash.insert(5, 9); // replaces 5->7 with 5->9 in _leftToRight and inserts 9->5 in _rightToLeft.
         // The 7->5 in _rightToLeft would be dangling, so we remove it before insertion.
 
         // This means we need to hash u and t up to twice each. Could probably be done better using QHashNode.
 
         if (_leftToRight.contains(t)) {
             _rightToLeft.remove(_leftToRight.take(t));
         }
         if (_rightToLeft.contains(u)) {
             _leftToRight.remove(_rightToLeft.take(u));
         }
 
         _rightToLeft.insert(u, t);
         return _leftToRight.insert(t, u);
     }
 
     KBiAssociativeContainer<LeftContainer, RightContainer> &intersect(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin();
         while (it != leftEnd()) {
             if (!other.leftContains(it.key())) {
                 it = eraseLeft(it);
             } else {
                 ++it;
             }
         }
         return *this;
     }
 
     KBiAssociativeContainer<LeftContainer, RightContainer> &subtract(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin();
         while (it != leftEnd()) {
             if (other._leftToRight.contains(it.key())) {
                 it = eraseLeft(it);
             } else {
                 ++it;
             }
         }
         return *this;
     }
 
     KBiAssociativeContainer<LeftContainer, RightContainer> &unite(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         typename LeftContainer::const_iterator it = other._leftToRight.constBegin();
         const typename LeftContainer::const_iterator end = other._leftToRight.constEnd();
         while (it != end) {
             const left_type key = it.key();
             if (!_leftToRight.contains(key)) {
                 insert(key, it.value());
             }
             ++it;
         }
         return *this;
     }
 
     void updateRight(left_iterator it, right_type u)
     {
         Q_ASSERT(it != leftEnd());
         const left_type key = it.key();
         _rightToLeft.remove(_leftToRight.value(key));
         _leftToRight[key] = u;
         _rightToLeft[u] = key;
     }
 
     void updateLeft(right_iterator it, left_type t)
     {
         Q_ASSERT(it != rightEnd());
         const right_type key = it.key();
         _leftToRight.remove(_rightToLeft.value(key));
         _rightToLeft[key] = t;
         _leftToRight[t] = key;
     }
 
     inline bool isEmpty() const
     {
         return _leftToRight.isEmpty();
     }
 
     const right_type operator[](const left_type &t) const
     {
         return _leftToRight.operator[](t);
     }
 
     bool operator==(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         return _leftToRight.operator==(other._leftToRight);
     }
 
     bool operator!=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other)
     {
         return _leftToRight.operator!=(other._leftToRight);
     }
 
     left_iterator toLeftIterator(right_iterator it) const
     {
         Q_ASSERT(it != rightEnd());
         return _leftToRight.find(it.value());
     }
 
     right_iterator toRightIterator(left_iterator it) const
     {
         Q_ASSERT(it != leftEnd());
         return _rightToLeft.find(it.value());
     }
 
     inline left_iterator leftBegin()
     {
         return _leftToRight.begin();
     }
 
     inline left_iterator leftEnd()
     {
         return _leftToRight.end();
     }
 
     inline left_const_iterator leftBegin() const
     {
         return _leftToRight.begin();
     }
 
     inline left_const_iterator leftEnd() const
     {
         return _leftToRight.end();
     }
 
     inline left_const_iterator leftConstBegin() const
     {
         return _leftToRight.constBegin();
     }
 
     inline left_const_iterator leftConstEnd() const
     {
         return _leftToRight.constEnd();
     }
 
     inline right_iterator rightBegin()
     {
         return _rightToLeft.begin();
     }
 
     inline right_iterator rightEnd()
     {
         return _rightToLeft.end();
     }
 
     inline right_const_iterator rightBegin() const
     {
         return _rightToLeft.begin();
     }
 
     inline right_const_iterator rightEnd() const
     {
         return _rightToLeft.end();
     }
     inline right_const_iterator rightConstBegin() const
     {
         return _rightToLeft.constBegin();
     }
 
     inline right_const_iterator rightConstEnd() const
     {
         return _rightToLeft.constEnd();
     }
 
     static KBiAssociativeContainer<LeftContainer, RightContainer> fromHash(const QHash<left_type, right_type> &hash)
     {
         KBiAssociativeContainer<LeftContainer, RightContainer> container;
         typename QHash<left_type, right_type>::const_iterator it = hash.constBegin();
         const typename QHash<left_type, right_type>::const_iterator end = hash.constEnd();
         for (; it != end; ++it) {
             container.insert(it.key(), it.value());
         }
         return container;
     }
 
     static KBiAssociativeContainer<LeftContainer, RightContainer> fromMap(const QMap<left_type, right_type> &hash)
     {
         KBiAssociativeContainer<LeftContainer, RightContainer> container;
         typename QMap<left_type, right_type>::const_iterator it = hash.constBegin();
         const typename QMap<left_type, right_type>::const_iterator end = hash.constEnd();
         for (; it != end; ++it) {
             container.insert(it.key(), it.value());
         }
         return container;
     }
 
     friend QDataStream &operator<<<LeftContainer, RightContainer>(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &bihash);
     friend QDataStream &operator>><LeftContainer, RightContainer>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &biHash);
     friend QDebug operator<<<LeftContainer, RightContainer>(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &biHash);
 
 protected:
     LeftContainer _leftToRight;
     RightContainer _rightToLeft;
 };
 
 template<typename LeftContainer, typename RightContainer>
 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container)
 {
     return out << container._leftToRight;
 }
 
 template<typename LeftContainer, typename RightContainer>
 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container)
 {
     LeftContainer leftToRight;
     in >> leftToRight;
     typename LeftContainer::const_iterator it = leftToRight.constBegin();
     const typename LeftContainer::const_iterator end = leftToRight.constEnd();
     for (; it != end; ++it) {
         container.insert(it.key(), it.value());
     }
 
     return in;
 }
 
 template<typename Container, typename T, typename U>
 struct _containerType {
     operator const char *();
 };
 
 template<typename T, typename U>
 struct _containerType<QHash<T, U>, T, U> {
     operator const char *()
     {
         return "QHash";
     }
 };
 
 template<typename T, typename U>
 struct _containerType<QMap<T, U>, T, U> {
     operator const char *()
     {
         return "QMap";
     }
 };
 
 template<typename Container>
 static const char *containerType()
 {
     return _containerType<Container, typename Container::key_type, typename Container::mapped_type>();
 }
 
 template<typename LeftContainer, typename RightContainer>
 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container)
 {
     typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator it = container.leftConstBegin();
 
     const typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator end = container.leftConstEnd();
     out.nospace() << "KBiAssociativeContainer<" << containerType<LeftContainer>() << ", " << containerType<RightContainer>() << ">"
                   << "(";
     for (; it != end; ++it) {
         out << "(" << it.key() << " <=> " << it.value() << ") ";
     }
 
     out << ")";
     return out;
 }
 
 /**
  * @brief KBiHash provides a bi-directional hash container
  *
  * @note This class is designed to make mapping easier in proxy model implementations.
  *
  * @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.
  */
 template<typename T, typename U>
 struct KBiHash : public KBiAssociativeContainer<QHash<T, U>, QHash<U, T>> {
     KBiHash()
         : KBiAssociativeContainer<QHash<T, U>, QHash<U, T>>()
     {
     }
 
     KBiHash(const KBiAssociativeContainer<QHash<T, U>, QHash<U, T>> &container)
         : KBiAssociativeContainer<QHash<T, U>, QHash<U, T>>(container)
     {
     }
 };
 
 template<typename T, typename U>
 QDebug operator<<(QDebug out, const KBiHash<T, U> &biHash)
 {
     typename KBiHash<T, U>::left_const_iterator it = biHash.leftConstBegin();
 
     const typename KBiHash<T, U>::left_const_iterator end = biHash.leftConstEnd();
     out.nospace() << "KBiHash(";
     for (; it != end; ++it) {
         out << "(" << it.key() << " <=> " << it.value() << ") ";
     }
 
     out << ")";
     return out;
 }
 
 template<typename T, typename U>
 struct KHash2Map : public KBiAssociativeContainer<QHash<T, U>, QMap<U, T>> {
     KHash2Map()
         : KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>()
     {
     }
 
     KHash2Map(const KBiAssociativeContainer<QHash<T, U>, QMap<U, T>> &container)
         : KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>(container)
     {
     }
 
     typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_iterator rightLowerBound(const U &key)
     {
         return this->_rightToLeft.lowerBound(key);
     }
 
     typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_const_iterator rightLowerBound(const U &key) const
     {
         return this->_rightToLeft.lowerBound(key);
     }
 
     typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_iterator rightUpperBound(const U &key)
     {
         return this->_rightToLeft.upperBound(key);
     }
 
     typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T>>::right_const_iterator rightUpperBound(const U &key) const
     {
         return this->_rightToLeft.upperBound(key);
     }
 };
 
 template<typename T, typename U>
 QDebug operator<<(QDebug out, const KHash2Map<T, U> &container)
 {
     typename KHash2Map<T, U>::left_const_iterator it = container.leftConstBegin();
 
     const typename KHash2Map<T, U>::left_const_iterator end = container.leftConstEnd();
     out.nospace() << "KHash2Map(";
     for (; it != end; ++it) {
         out << "(" << it.key() << " <=> " << it.value() << ") ";
     }
 
     out << ")";
     return out;
 }
 
 #endif