akonadi
kbihash_p.h
00001 /* 00002 00003 Copyright (C) 2010 Klarälvdalens Datakonsult AB, 00004 a KDAB Group company, info@kdab.net, 00005 author Stephen Kelly <stephen@kdab.com> 00006 00007 This library is free software; you can redistribute it and/or modify it 00008 under the terms of the GNU Library General Public License as published by 00009 the Free Software Foundation; either version 2 of the License, or (at your 00010 option) any later version. 00011 00012 This library is distributed in the hope that it will be useful, but WITHOUT 00013 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00014 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public 00015 License for more details. 00016 00017 You should have received a copy of the GNU Library General Public License 00018 along with this library; see the file COPYING.LIB. If not, write to the 00019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 00020 02110-1301, USA. 00021 */ 00022 00023 #ifndef KBIHASH_P_H 00024 #define KBIHASH_P_H 00025 00026 #include <QtCore/QHash> 00027 #include <QtCore/QMap> 00028 00029 #include <QtCore/QDebug> 00030 00031 template<typename LeftContainer, typename RightContainer> 00032 class KBiAssociativeContainer; 00033 00034 template<typename LeftContainer, typename RightContainer> 00035 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container); 00036 00037 template<typename LeftContainer, typename RightContainer> 00038 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container); 00039 00040 template<typename LeftContainer, typename RightContainer> 00041 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container); 00042 00043 00044 template<typename LeftContainer, typename RightContainer> 00045 class KBiAssociativeContainer 00046 { 00047 // We need to convert from a QHash::iterator or QMap::iterator 00048 // to a KBiAssociativeContainer::iterator (left or right) 00049 // Do do that we use this implicit ctor. We partially specialize 00050 // it for QHash and QMap types. 00051 // Our iterator inherits from this struct to get the implicit ctor, 00052 // and this struct must inherit from the QHash or QMap iterator. 00053 template<typename Container, typename T, typename U> 00054 struct _iterator_impl_ctor : public Container::iterator 00055 { 00056 _iterator_impl_ctor(typename Container::iterator it); 00057 }; 00058 00059 template<typename T, typename U> 00060 struct _iterator_impl_ctor<QHash<T, U>, T, U> : public QHash<T, U>::iterator 00061 { 00062 /* implicit */ _iterator_impl_ctor(const typename QHash<T, U>::iterator it) 00063 // Using internals here because I was too lazy to write my own iterator. 00064 : QHash<T, U>::iterator(reinterpret_cast<void *>(static_cast<QHashNode<T, U> *>(it))) 00065 { 00066 00067 } 00068 }; 00069 00070 template<typename T, typename U> 00071 struct _iterator_impl_ctor<QMap<T, U>, T, U> : public QMap<T, U>::iterator 00072 { 00073 /* implicit */ _iterator_impl_ctor(const typename QMap<T, U>::iterator it) 00074 // Using internals here because I was too lazy to write my own iterator. 00075 : QMap<T, U>::iterator(static_cast<QMapData::Node*>(it)) 00076 { 00077 00078 } 00079 }; 00080 public: 00081 typedef typename RightContainer::mapped_type left_type; 00082 typedef typename LeftContainer::mapped_type right_type; 00083 00084 template <typename Container> 00085 class _iterator : public _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type> 00086 { 00087 public: 00088 explicit inline _iterator(void *data) : Container::iterator(data) {} 00089 00090 /* implicit */ _iterator(const typename Container::iterator it) 00091 : _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>(it) 00092 { 00093 00094 } 00095 00096 inline const typename Container::mapped_type &value() const { 00097 return Container::iterator::value(); 00098 } 00099 inline const typename Container::mapped_type &operator*() const { 00100 return Container::iterator::operator*(); 00101 } 00102 inline const typename Container::mapped_type *operator->() const { 00103 return Container::iterator::operator->(); 00104 } 00105 00106 private: 00107 #ifndef Q_CC_MSVC 00108 using Container::iterator::operator*; 00109 using Container::iterator::operator->; 00110 using Container::iterator::value; 00111 #endif 00112 }; 00113 00114 typedef _iterator<LeftContainer> left_iterator; 00115 typedef typename LeftContainer::const_iterator left_const_iterator; 00116 typedef _iterator<RightContainer> right_iterator; 00117 typedef typename RightContainer::const_iterator right_const_iterator; 00118 00119 inline KBiAssociativeContainer() {} 00120 inline KBiAssociativeContainer(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00121 *this = other; 00122 } 00123 00124 const KBiAssociativeContainer<LeftContainer, RightContainer> &operator=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00125 _leftToRight = other._leftToRight; _rightToLeft = other._rightToLeft; return *this; 00126 } 00127 00128 inline bool removeLeft(left_type t) { 00129 const right_type u = _leftToRight.take(t); 00130 return _rightToLeft.remove(u) != 0; 00131 } 00132 00133 inline bool removeRight(right_type u) { 00134 const left_type t = _rightToLeft.take(u); 00135 return _leftToRight.remove(t) != 0; 00136 } 00137 00138 inline right_type takeLeft(left_type t) { 00139 const right_type u = _leftToRight.take(t); 00140 _rightToLeft.remove(u); 00141 return u; 00142 } 00143 00144 inline left_type takeRight(right_type u) { 00145 const left_type t = _rightToLeft.take(u); 00146 _leftToRight.remove(t); 00147 return t; 00148 } 00149 00150 inline left_type rightToLeft(right_type u) const { 00151 return _rightToLeft.value(u); 00152 } 00153 00154 inline right_type leftToRight(left_type t) const { 00155 return _leftToRight.value(t); 00156 } 00157 00158 inline bool leftContains(left_type t) const { 00159 return _leftToRight.contains(t); 00160 } 00161 00162 inline bool rightContains(right_type u) const { 00163 return _rightToLeft.contains(u); 00164 } 00165 00166 inline int size() const { 00167 return _leftToRight.size(); 00168 } 00169 00170 inline int count() const { 00171 return _leftToRight.count(); 00172 } 00173 00174 inline int capacity() const { 00175 return _leftToRight.capacity(); 00176 } 00177 00178 void reserve(int size) { 00179 _leftToRight.reserve(size); _rightToLeft.reserve(size); 00180 } 00181 00182 inline void squeeze() { 00183 _leftToRight.squeeze(); _rightToLeft.squeeze(); 00184 } 00185 00186 inline void detach() { 00187 _leftToRight.detach(); _rightToLeft.detach(); 00188 } 00189 00190 inline bool isDetached() const { 00191 return _leftToRight.isDetached(); 00192 } 00193 00194 inline void setSharable(bool sharable) { 00195 _leftToRight.setSharable(sharable); _rightToLeft.setSharable(sharable); 00196 } 00197 00198 inline bool isSharedWith(const KBiAssociativeContainer<RightContainer, LeftContainer> &other) const { 00199 return _leftToRight.isSharedWith(other._leftToRight) && _rightToLeft.isSharedWith(other._leftToRight); 00200 } 00201 00202 void clear() { 00203 _leftToRight.clear(); _rightToLeft.clear(); 00204 } 00205 00206 QList<left_type> leftValues() const { 00207 return _leftToRight.keys(); 00208 } 00209 00210 QList<right_type> rightValues() const { 00211 return _rightToLeft.keys(); 00212 } 00213 00214 right_iterator eraseRight(right_iterator it) { 00215 Q_ASSERT(it != rightEnd()); 00216 _leftToRight.remove(it.value()); 00217 return _rightToLeft.erase(it); 00218 } 00219 00220 left_iterator eraseLeft(left_iterator it) { 00221 Q_ASSERT(it != leftEnd()); 00222 _rightToLeft.remove(it.value()); 00223 return _leftToRight.erase(it); 00224 } 00225 00226 left_iterator findLeft(left_type t) { 00227 return _leftToRight.find(t); 00228 } 00229 00230 left_const_iterator findLeft(left_type t) const { 00231 return _leftToRight.find(t); 00232 } 00233 00234 left_const_iterator constFindLeft(left_type t) const { 00235 return _leftToRight.constFind(t); 00236 } 00237 00238 right_iterator findRight(right_type u) { 00239 return _rightToLeft.find(u); 00240 } 00241 00242 right_const_iterator findRight(right_type u) const { 00243 return _rightToLeft.find(u); 00244 } 00245 00246 right_const_iterator constFindRight(right_type u) const { 00247 return _rightToLeft.find(u); 00248 } 00249 00250 left_iterator insert(left_type t, right_type u) { 00251 // biHash.insert(5, 7); // creates 5->7 in _leftToRight and 7->5 in _rightToLeft 00252 // biHash.insert(5, 9); // replaces 5->7 with 5->9 in _leftToRight and inserts 9->5 in _rightToLeft. 00253 // The 7->5 in _rightToLeft would be dangling, so we remove it before insertion. 00254 00255 // This means we need to hash u and t up to twice each. Could probably be done better using QHashNode. 00256 00257 if (_leftToRight.contains(t)) 00258 _rightToLeft.remove(_leftToRight.take(t)); 00259 if (_rightToLeft.contains(u)) 00260 _leftToRight.remove(_rightToLeft.take(u)); 00261 00262 _rightToLeft.insert(u, t); 00263 return _leftToRight.insert(t, u); 00264 } 00265 00266 00267 KBiAssociativeContainer<LeftContainer, RightContainer> &intersect(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00268 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin(); 00269 while (it != leftEnd()) { 00270 if (!other.leftContains(it.key())) 00271 it = eraseLeft(it); 00272 else 00273 ++it; 00274 } 00275 return *this; 00276 } 00277 00278 KBiAssociativeContainer<LeftContainer, RightContainer> &subtract(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00279 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin(); 00280 while (it != leftEnd()) { 00281 if (other._leftToRight.contains(it.key())) 00282 it = eraseLeft(it); 00283 else 00284 ++it; 00285 } 00286 return *this; 00287 } 00288 00289 KBiAssociativeContainer<LeftContainer, RightContainer> &unite(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00290 typename LeftContainer::const_iterator it = other._leftToRight.constBegin(); 00291 const typename LeftContainer::const_iterator end = other._leftToRight.constEnd(); 00292 while (it != end) { 00293 const left_type key = it.key(); 00294 if (!_leftToRight.contains(key)) 00295 insert(key, it.value()); 00296 ++it; 00297 } 00298 return *this; 00299 } 00300 00301 void updateRight(left_iterator it, right_type u) { 00302 Q_ASSERT(it != leftEnd()); 00303 const left_type key = it.key(); 00304 _rightToLeft.remove(_leftToRight.value(key)); 00305 _leftToRight[key] = u; 00306 _rightToLeft[u] = key; 00307 } 00308 00309 void updateLeft(right_iterator it, left_type t) { 00310 Q_ASSERT(it != rightEnd()); 00311 const right_type key = it.key(); 00312 _leftToRight.remove(_rightToLeft.value(key)); 00313 _rightToLeft[key] = t; 00314 _leftToRight[t] = key; 00315 } 00316 00317 inline bool isEmpty() const { 00318 return _leftToRight.isEmpty(); 00319 } 00320 00321 const right_type operator[](const left_type &t) const { 00322 return _leftToRight.operator[](t); 00323 } 00324 00325 bool operator==(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00326 return _leftToRight.operator == (other._leftToRight); 00327 } 00328 00329 bool operator!=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) { 00330 return _leftToRight.operator != (other._leftToRight); 00331 } 00332 00333 left_iterator toLeftIterator(right_iterator it) const { 00334 Q_ASSERT(it != rightEnd()); 00335 return _leftToRight.find(it.value()); 00336 } 00337 00338 right_iterator toRightIterator(left_iterator it) const { 00339 Q_ASSERT(it != leftEnd()); 00340 return _rightToLeft.find(it.value()); 00341 } 00342 00343 inline left_iterator leftBegin() { 00344 return _leftToRight.begin(); 00345 } 00346 00347 inline left_iterator leftEnd() { 00348 return _leftToRight.end(); 00349 } 00350 00351 inline left_const_iterator leftBegin() const { 00352 return _leftToRight.begin(); 00353 } 00354 00355 inline left_const_iterator leftEnd() const { 00356 return _leftToRight.end(); 00357 } 00358 00359 inline left_const_iterator leftConstBegin() const { 00360 return _leftToRight.constBegin(); 00361 } 00362 00363 inline left_const_iterator leftConstEnd() const { 00364 return _leftToRight.constEnd(); 00365 } 00366 00367 inline right_iterator rightBegin() { 00368 return _rightToLeft.begin(); 00369 } 00370 00371 inline right_iterator rightEnd() { 00372 return _rightToLeft.end(); 00373 } 00374 00375 inline right_const_iterator rightBegin() const { 00376 return _rightToLeft.begin(); 00377 } 00378 00379 inline right_const_iterator rightEnd() const { 00380 return _rightToLeft.end(); 00381 } 00382 inline right_const_iterator rightConstBegin() const { 00383 return _rightToLeft.constBegin(); 00384 } 00385 00386 inline right_const_iterator rightConstEnd() const { 00387 return _rightToLeft.constEnd(); 00388 } 00389 00390 static KBiAssociativeContainer<LeftContainer, RightContainer> fromHash(const QHash<left_type, right_type> &hash) { 00391 KBiAssociativeContainer<LeftContainer, RightContainer> container; 00392 typename QHash<left_type, right_type>::const_iterator it = hash.constBegin(); 00393 const typename QHash<left_type, right_type>::const_iterator end = hash.constEnd(); 00394 for ( ; it != end; ++it) 00395 container.insert(it.key(), it.value()); 00396 return container; 00397 } 00398 00399 static KBiAssociativeContainer<LeftContainer, RightContainer> fromMap(const QMap<left_type, right_type> &hash) { 00400 KBiAssociativeContainer<LeftContainer, RightContainer> container; 00401 typename QMap<left_type, right_type>::const_iterator it = hash.constBegin(); 00402 const typename QMap<left_type, right_type>::const_iterator end = hash.constEnd(); 00403 for ( ; it != end; ++it) 00404 container.insert(it.key(), it.value()); 00405 return container; 00406 } 00407 00408 friend QDataStream &operator<< <LeftContainer, RightContainer>(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &bihash); 00409 friend QDataStream &operator>> <LeftContainer, RightContainer>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &biHash); 00410 friend QDebug operator<< <LeftContainer, RightContainer>(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &biHash); 00411 protected: 00412 LeftContainer _leftToRight; 00413 RightContainer _rightToLeft; 00414 }; 00415 00416 template<typename LeftContainer, typename RightContainer> 00417 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container) 00418 { 00419 return out << container._leftToRight; 00420 } 00421 00422 template<typename LeftContainer, typename RightContainer> 00423 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container) 00424 { 00425 LeftContainer leftToRight; 00426 in >> leftToRight; 00427 typename LeftContainer::const_iterator it = leftToRight.constBegin(); 00428 const typename LeftContainer::const_iterator end = leftToRight.constEnd(); 00429 for (; it != end; ++it) 00430 container.insert(it.key(), it.value()); 00431 00432 return in; 00433 } 00434 00435 template<typename Container, typename T, typename U> 00436 struct _containerType 00437 { 00438 operator const char *(); 00439 }; 00440 00441 template<typename T, typename U> 00442 struct _containerType<QHash<T, U>, T, U> 00443 { 00444 operator const char *() 00445 { 00446 return "QHash"; 00447 } 00448 }; 00449 00450 template<typename T, typename U> 00451 struct _containerType<QMap<T, U>, T, U> 00452 { 00453 operator const char *() 00454 { 00455 return "QMap"; 00456 } 00457 }; 00458 00459 00460 template<typename Container> 00461 static const char * containerType() 00462 { 00463 return _containerType<Container, typename Container::key_type, typename Container::mapped_type>(); 00464 } 00465 00466 template<typename LeftContainer, typename RightContainer> 00467 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container) 00468 { 00469 typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator it = container.leftConstBegin(); 00470 00471 const typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator end = container.leftConstEnd(); 00472 out.nospace() << "KBiAssociativeContainer<" << containerType<LeftContainer>() << ", " << containerType<RightContainer>() << ">" << "("; 00473 for (; it != end; ++it) 00474 out << "(" << it.key() << " <=> " << it.value() << ") "; 00475 00476 out << ")"; 00477 return out; 00478 } 00479 00487 template <typename T, typename U> 00488 struct KBiHash : public KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > 00489 { 00490 KBiHash() 00491 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > () 00492 { 00493 00494 } 00495 00496 KBiHash(const KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > &container) 00497 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > (container) 00498 { 00499 00500 } 00501 }; 00502 00503 template<typename T, typename U> 00504 QDebug operator<<(QDebug out, const KBiHash<T, U> &biHash) 00505 { 00506 typename KBiHash<T, U>::left_const_iterator it = biHash.leftConstBegin(); 00507 00508 const typename KBiHash<T, U>::left_const_iterator end = biHash.leftConstEnd(); 00509 out.nospace() << "KBiHash("; 00510 for (; it != end; ++it) 00511 out << "(" << it.key() << " <=> " << it.value() << ") "; 00512 00513 out << ")"; 00514 return out; 00515 } 00516 00517 template <typename T, typename U> 00518 struct KHash2Map : public KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > 00519 { 00520 KHash2Map() 00521 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > () 00522 { 00523 00524 } 00525 00526 KHash2Map(const KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > &container) 00527 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > (container) 00528 { 00529 00530 } 00531 00532 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_iterator rightLowerBound(const U &key) 00533 { 00534 return this->_rightToLeft.lowerBound(key); 00535 } 00536 00537 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_const_iterator rightLowerBound(const U &key) const 00538 { 00539 return this->_rightToLeft.lowerBound(key); 00540 } 00541 00542 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_iterator rightUpperBound(const U &key) 00543 { 00544 return this->_rightToLeft.upperBound(key); 00545 } 00546 00547 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_const_iterator rightUpperBound(const U &key) const 00548 { 00549 return this->_rightToLeft.upperBound(key); 00550 } 00551 }; 00552 00553 template<typename T, typename U> 00554 QDebug operator<<(QDebug out, const KHash2Map<T, U> &container) 00555 { 00556 typename KHash2Map<T, U>::left_const_iterator it = container.leftConstBegin(); 00557 00558 const typename KHash2Map<T, U>::left_const_iterator end = container.leftConstEnd(); 00559 out.nospace() << "KHash2Map("; 00560 for (; it != end; ++it) 00561 out << "(" << it.key() << " <=> " << it.value() << ") "; 00562 00563 out << ")"; 00564 return out; 00565 } 00566 00567 #endif