kbihash_p.h (18879B)
1 /* 2 3 Copyright (C) 2010 Klarälvdalens Datakonsult AB, 4 a KDAB Group company, info@kdab.net, 5 author Stephen Kelly <stephen@kdab.com> 6 7 This library is free software; you can redistribute it and/or modify it 8 under the terms of the GNU Library General Public License as published by 9 the Free Software Foundation; either version 2 of the License, or (at your 10 option) any later version. 11 12 This library is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public 15 License for more details. 16 17 You should have received a copy of the GNU Library General Public License 18 along with this library; see the file COPYING.LIB. If not, write to the 19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301, USA. 21 */ 22 23 #ifndef KBIHASH_P_H 24 #define KBIHASH_P_H 25 26 #include <QHash> 27 #include <QMap> 28 29 #include <QDebug> 30 31 template<typename LeftContainer, typename RightContainer> 32 class KBiAssociativeContainer; 33 34 template<typename LeftContainer, typename RightContainer> 35 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container); 36 37 template<typename LeftContainer, typename RightContainer> 38 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container); 39 40 template<typename LeftContainer, typename RightContainer> 41 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container); 42 43 template<typename LeftContainer, typename RightContainer> 44 class KBiAssociativeContainer 45 { 46 // We need to convert from a QHash::iterator or QMap::iterator 47 // to a KBiAssociativeContainer::iterator (left or right) 48 // Do do that we use this implicit ctor. We partially specialize 49 // it for QHash and QMap types. 50 // Our iterator inherits from this struct to get the implicit ctor, 51 // and this struct must inherit from the QHash or QMap iterator. 52 template<typename Container, typename T, typename U> 53 struct _iterator_impl_ctor : public Container::iterator { 54 _iterator_impl_ctor(typename Container::iterator it); 55 }; 56 57 template<typename T, typename U> 58 struct _iterator_impl_ctor<QHash<T, U>, T, U> : public QHash<T, U>::iterator { 59 /* implicit */ _iterator_impl_ctor(const typename QHash<T, U>::iterator it) 60 : QHash<T, U>::iterator(it) 61 { 62 63 } 64 }; 65 66 template<typename T, typename U> 67 struct _iterator_impl_ctor<QMap<T, U>, T, U> : public QMap<T, U>::iterator { 68 /* implicit */ _iterator_impl_ctor(const typename QMap<T, U>::iterator it) 69 : QMap<T, U>::iterator(it) 70 { 71 72 } 73 }; 74 public: 75 typedef typename RightContainer::mapped_type left_type; 76 typedef typename LeftContainer::mapped_type right_type; 77 78 template <typename Container> 79 class _iterator : public _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type> 80 { 81 public: 82 explicit inline _iterator(void *data) : Container::iterator(data) {} 83 84 /* implicit */ _iterator(const typename Container::iterator it) 85 : _iterator_impl_ctor<Container, typename Container::key_type, typename Container::mapped_type>(it) 86 { 87 88 } 89 90 inline const typename Container::mapped_type &value() const 91 { 92 return Container::iterator::value(); 93 } 94 inline const typename Container::mapped_type &operator*() const 95 { 96 return Container::iterator::operator*(); 97 } 98 inline const typename Container::mapped_type *operator->() const 99 { 100 return Container::iterator::operator->(); 101 } 102 103 private: 104 #ifndef Q_CC_MSVC 105 using Container::iterator::operator*; 106 using Container::iterator::operator->; 107 using Container::iterator::value; 108 #endif 109 }; 110 111 typedef _iterator<LeftContainer> left_iterator; 112 typedef typename LeftContainer::const_iterator left_const_iterator; 113 typedef _iterator<RightContainer> right_iterator; 114 typedef typename RightContainer::const_iterator right_const_iterator; 115 116 inline KBiAssociativeContainer() {} 117 inline KBiAssociativeContainer(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 118 { 119 *this = other; 120 } 121 122 const KBiAssociativeContainer<LeftContainer, RightContainer> &operator=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 123 { 124 _leftToRight = other._leftToRight; _rightToLeft = other._rightToLeft; return *this; 125 } 126 127 inline bool removeLeft(left_type t) 128 { 129 const right_type u = _leftToRight.take(t); 130 return _rightToLeft.remove(u) != 0; 131 } 132 133 inline bool removeRight(right_type u) 134 { 135 const left_type t = _rightToLeft.take(u); 136 return _leftToRight.remove(t) != 0; 137 } 138 139 inline right_type takeLeft(left_type t) 140 { 141 const right_type u = _leftToRight.take(t); 142 _rightToLeft.remove(u); 143 return u; 144 } 145 146 inline left_type takeRight(right_type u) 147 { 148 const left_type t = _rightToLeft.take(u); 149 _leftToRight.remove(t); 150 return t; 151 } 152 153 inline left_type rightToLeft(right_type u) const 154 { 155 return _rightToLeft.value(u); 156 } 157 158 inline right_type leftToRight(left_type t) const 159 { 160 return _leftToRight.value(t); 161 } 162 163 inline bool leftContains(left_type t) const 164 { 165 return _leftToRight.contains(t); 166 } 167 168 inline bool rightContains(right_type u) const 169 { 170 return _rightToLeft.contains(u); 171 } 172 173 inline int size() const 174 { 175 return _leftToRight.size(); 176 } 177 178 inline int count() const 179 { 180 return _leftToRight.count(); 181 } 182 183 inline int capacity() const 184 { 185 return _leftToRight.capacity(); 186 } 187 188 void reserve(int size) 189 { 190 _leftToRight.reserve(size); _rightToLeft.reserve(size); 191 } 192 193 inline void squeeze() 194 { 195 _leftToRight.squeeze(); _rightToLeft.squeeze(); 196 } 197 198 inline void detach() 199 { 200 _leftToRight.detach(); _rightToLeft.detach(); 201 } 202 203 inline bool isDetached() const 204 { 205 return _leftToRight.isDetached(); 206 } 207 208 inline void setSharable(bool sharable) 209 { 210 _leftToRight.setSharable(sharable); _rightToLeft.setSharable(sharable); 211 } 212 213 inline bool isSharedWith(const KBiAssociativeContainer<RightContainer, LeftContainer> &other) const 214 { 215 return _leftToRight.isSharedWith(other._leftToRight) && _rightToLeft.isSharedWith(other._leftToRight); 216 } 217 218 void clear() 219 { 220 _leftToRight.clear(); _rightToLeft.clear(); 221 } 222 223 QList<left_type> leftValues() const 224 { 225 return _leftToRight.keys(); 226 } 227 228 QList<right_type> rightValues() const 229 { 230 return _rightToLeft.keys(); 231 } 232 233 right_iterator eraseRight(right_iterator it) 234 { 235 Q_ASSERT(it != rightEnd()); 236 _leftToRight.remove(it.value()); 237 return _rightToLeft.erase(it); 238 } 239 240 left_iterator eraseLeft(left_iterator it) 241 { 242 Q_ASSERT(it != leftEnd()); 243 _rightToLeft.remove(it.value()); 244 return _leftToRight.erase(it); 245 } 246 247 left_iterator findLeft(left_type t) 248 { 249 return _leftToRight.find(t); 250 } 251 252 left_const_iterator findLeft(left_type t) const 253 { 254 return _leftToRight.find(t); 255 } 256 257 left_const_iterator constFindLeft(left_type t) const 258 { 259 return _leftToRight.constFind(t); 260 } 261 262 right_iterator findRight(right_type u) 263 { 264 return _rightToLeft.find(u); 265 } 266 267 right_const_iterator findRight(right_type u) const 268 { 269 return _rightToLeft.find(u); 270 } 271 272 right_const_iterator constFindRight(right_type u) const 273 { 274 return _rightToLeft.find(u); 275 } 276 277 left_iterator insert(left_type t, right_type u) 278 { 279 // biHash.insert(5, 7); // creates 5->7 in _leftToRight and 7->5 in _rightToLeft 280 // biHash.insert(5, 9); // replaces 5->7 with 5->9 in _leftToRight and inserts 9->5 in _rightToLeft. 281 // The 7->5 in _rightToLeft would be dangling, so we remove it before insertion. 282 283 // This means we need to hash u and t up to twice each. Could probably be done better using QHashNode. 284 285 if (_leftToRight.contains(t)) { 286 _rightToLeft.remove(_leftToRight.take(t)); 287 } 288 if (_rightToLeft.contains(u)) { 289 _leftToRight.remove(_rightToLeft.take(u)); 290 } 291 292 _rightToLeft.insert(u, t); 293 return _leftToRight.insert(t, u); 294 } 295 296 KBiAssociativeContainer<LeftContainer, RightContainer> &intersect(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 297 { 298 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin(); 299 while (it != leftEnd()) { 300 if (!other.leftContains(it.key())) { 301 it = eraseLeft(it); 302 } else { 303 ++it; 304 } 305 } 306 return *this; 307 } 308 309 KBiAssociativeContainer<LeftContainer, RightContainer> &subtract(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 310 { 311 typename KBiAssociativeContainer<RightContainer, LeftContainer>::left_iterator it = leftBegin(); 312 while (it != leftEnd()) { 313 if (other._leftToRight.contains(it.key())) { 314 it = eraseLeft(it); 315 } else { 316 ++it; 317 } 318 } 319 return *this; 320 } 321 322 KBiAssociativeContainer<LeftContainer, RightContainer> &unite(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 323 { 324 typename LeftContainer::const_iterator it = other._leftToRight.constBegin(); 325 const typename LeftContainer::const_iterator end = other._leftToRight.constEnd(); 326 while (it != end) { 327 const left_type key = it.key(); 328 if (!_leftToRight.contains(key)) { 329 insert(key, it.value()); 330 } 331 ++it; 332 } 333 return *this; 334 } 335 336 void updateRight(left_iterator it, right_type u) 337 { 338 Q_ASSERT(it != leftEnd()); 339 const left_type key = it.key(); 340 _rightToLeft.remove(_leftToRight.value(key)); 341 _leftToRight[key] = u; 342 _rightToLeft[u] = key; 343 } 344 345 void updateLeft(right_iterator it, left_type t) 346 { 347 Q_ASSERT(it != rightEnd()); 348 const right_type key = it.key(); 349 _leftToRight.remove(_rightToLeft.value(key)); 350 _rightToLeft[key] = t; 351 _leftToRight[t] = key; 352 } 353 354 inline bool isEmpty() const 355 { 356 return _leftToRight.isEmpty(); 357 } 358 359 const right_type operator[](const left_type &t) const 360 { 361 return _leftToRight.operator[](t); 362 } 363 364 bool operator==(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 365 { 366 return _leftToRight.operator == (other._leftToRight); 367 } 368 369 bool operator!=(const KBiAssociativeContainer<LeftContainer, RightContainer> &other) 370 { 371 return _leftToRight.operator != (other._leftToRight); 372 } 373 374 left_iterator toLeftIterator(right_iterator it) const 375 { 376 Q_ASSERT(it != rightEnd()); 377 return _leftToRight.find(it.value()); 378 } 379 380 right_iterator toRightIterator(left_iterator it) const 381 { 382 Q_ASSERT(it != leftEnd()); 383 return _rightToLeft.find(it.value()); 384 } 385 386 inline left_iterator leftBegin() 387 { 388 return _leftToRight.begin(); 389 } 390 391 inline left_iterator leftEnd() 392 { 393 return _leftToRight.end(); 394 } 395 396 inline left_const_iterator leftBegin() const 397 { 398 return _leftToRight.begin(); 399 } 400 401 inline left_const_iterator leftEnd() const 402 { 403 return _leftToRight.end(); 404 } 405 406 inline left_const_iterator leftConstBegin() const 407 { 408 return _leftToRight.constBegin(); 409 } 410 411 inline left_const_iterator leftConstEnd() const 412 { 413 return _leftToRight.constEnd(); 414 } 415 416 inline right_iterator rightBegin() 417 { 418 return _rightToLeft.begin(); 419 } 420 421 inline right_iterator rightEnd() 422 { 423 return _rightToLeft.end(); 424 } 425 426 inline right_const_iterator rightBegin() const 427 { 428 return _rightToLeft.begin(); 429 } 430 431 inline right_const_iterator rightEnd() const 432 { 433 return _rightToLeft.end(); 434 } 435 inline right_const_iterator rightConstBegin() const 436 { 437 return _rightToLeft.constBegin(); 438 } 439 440 inline right_const_iterator rightConstEnd() const 441 { 442 return _rightToLeft.constEnd(); 443 } 444 445 static KBiAssociativeContainer<LeftContainer, RightContainer> fromHash(const QHash<left_type, right_type> &hash) 446 { 447 KBiAssociativeContainer<LeftContainer, RightContainer> container; 448 typename QHash<left_type, right_type>::const_iterator it = hash.constBegin(); 449 const typename QHash<left_type, right_type>::const_iterator end = hash.constEnd(); 450 for (; it != end; ++it) { 451 container.insert(it.key(), it.value()); 452 } 453 return container; 454 } 455 456 static KBiAssociativeContainer<LeftContainer, RightContainer> fromMap(const QMap<left_type, right_type> &hash) 457 { 458 KBiAssociativeContainer<LeftContainer, RightContainer> container; 459 typename QMap<left_type, right_type>::const_iterator it = hash.constBegin(); 460 const typename QMap<left_type, right_type>::const_iterator end = hash.constEnd(); 461 for (; it != end; ++it) { 462 container.insert(it.key(), it.value()); 463 } 464 return container; 465 } 466 467 friend QDataStream &operator<< <LeftContainer, RightContainer>(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &bihash); 468 friend QDataStream &operator>> <LeftContainer, RightContainer>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &biHash); 469 friend QDebug operator<< <LeftContainer, RightContainer>(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &biHash); 470 protected: 471 LeftContainer _leftToRight; 472 RightContainer _rightToLeft; 473 }; 474 475 template<typename LeftContainer, typename RightContainer> 476 QDataStream &operator<<(QDataStream &out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container) 477 { 478 return out << container._leftToRight; 479 } 480 481 template<typename LeftContainer, typename RightContainer> 482 QDataStream &operator>>(QDataStream &in, KBiAssociativeContainer<LeftContainer, RightContainer> &container) 483 { 484 LeftContainer leftToRight; 485 in >> leftToRight; 486 typename LeftContainer::const_iterator it = leftToRight.constBegin(); 487 const typename LeftContainer::const_iterator end = leftToRight.constEnd(); 488 for (; it != end; ++it) { 489 container.insert(it.key(), it.value()); 490 } 491 492 return in; 493 } 494 495 template<typename Container, typename T, typename U> 496 struct _containerType { 497 operator const char *(); 498 }; 499 500 template<typename T, typename U> 501 struct _containerType<QHash<T, U>, T, U> { 502 operator const char *() 503 { 504 return "QHash"; 505 } 506 }; 507 508 template<typename T, typename U> 509 struct _containerType<QMap<T, U>, T, U> { 510 operator const char *() 511 { 512 return "QMap"; 513 } 514 }; 515 516 template<typename Container> 517 static const char *containerType() 518 { 519 return _containerType<Container, typename Container::key_type, typename Container::mapped_type>(); 520 } 521 522 template<typename LeftContainer, typename RightContainer> 523 QDebug operator<<(QDebug out, const KBiAssociativeContainer<LeftContainer, RightContainer> &container) 524 { 525 typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator it = container.leftConstBegin(); 526 527 const typename KBiAssociativeContainer<LeftContainer, RightContainer>::left_const_iterator end = container.leftConstEnd(); 528 out.nospace() << "KBiAssociativeContainer<" << containerType<LeftContainer>() << ", " << containerType<RightContainer>() << ">" << "("; 529 for (; it != end; ++it) { 530 out << "(" << it.key() << " <=> " << it.value() << ") "; 531 } 532 533 out << ")"; 534 return out; 535 } 536 537 /** 538 * @brief KBiHash provides a bi-directional hash container 539 * 540 * @note This class is designed to make mapping easier in proxy model implementations. 541 * 542 * @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. 543 */ 544 template <typename T, typename U> 545 struct KBiHash : public KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > { 546 KBiHash() 547 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > () 548 { 549 550 } 551 552 KBiHash(const KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > &container) 553 : KBiAssociativeContainer<QHash<T, U>, QHash<U, T> > (container) 554 { 555 556 } 557 }; 558 559 template<typename T, typename U> 560 QDebug operator<<(QDebug out, const KBiHash<T, U> &biHash) 561 { 562 typename KBiHash<T, U>::left_const_iterator it = biHash.leftConstBegin(); 563 564 const typename KBiHash<T, U>::left_const_iterator end = biHash.leftConstEnd(); 565 out.nospace() << "KBiHash("; 566 for (; it != end; ++it) { 567 out << "(" << it.key() << " <=> " << it.value() << ") "; 568 } 569 570 out << ")"; 571 return out; 572 } 573 574 template <typename T, typename U> 575 struct KHash2Map : public KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > { 576 KHash2Map() 577 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > () 578 { 579 580 } 581 582 KHash2Map(const KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > &container) 583 : KBiAssociativeContainer<QHash<T, U>, QMap<U, T> > (container) 584 { 585 586 } 587 588 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_iterator rightLowerBound(const U &key) 589 { 590 return this->_rightToLeft.lowerBound(key); 591 } 592 593 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_const_iterator rightLowerBound(const U &key) const 594 { 595 return this->_rightToLeft.lowerBound(key); 596 } 597 598 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_iterator rightUpperBound(const U &key) 599 { 600 return this->_rightToLeft.upperBound(key); 601 } 602 603 typename KBiAssociativeContainer<QHash<T, U>, QMap<U, T> >::right_const_iterator rightUpperBound(const U &key) const 604 { 605 return this->_rightToLeft.upperBound(key); 606 } 607 }; 608 609 template<typename T, typename U> 610 QDebug operator<<(QDebug out, const KHash2Map<T, U> &container) 611 { 612 typename KHash2Map<T, U>::left_const_iterator it = container.leftConstBegin(); 613 614 const typename KHash2Map<T, U>::left_const_iterator end = container.leftConstEnd(); 615 out.nospace() << "KHash2Map("; 616 for (; it != end; ++it) { 617 out << "(" << it.key() << " <=> " << it.value() << ") "; 618 } 619 620 out << ")"; 621 return out; 622 } 623 624 #endif