00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
00048
00049
00050
00051
00052
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 _iterator_impl_ctor(const typename QHash<T, U>::iterator it)
00063
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 _iterator_impl_ctor(const typename QMap<T, U>::iterator it)
00074
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 _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
00252
00253
00254
00255
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