headers/private/kernel/util/VectorMap.h

   1 // VectorMap.h
   2 //
   3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining a
   6 // copy of this software and associated documentation files (the "Software"),
   7 // to deal in the Software without restriction, including without limitation
   8 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9 // and/or sell copies of the Software, and to permit persons to whom the
  10 // Software is furnished to do so, subject to the following conditions:
  11 //
  12 // The above copyright notice and this permission notice shall be included in
  13 // all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21 // DEALINGS IN THE SOFTWARE.
  22 //
  23 // Except as contained in this notice, the name of a copyright holder shall
  24 // not be used in advertising or otherwise to promote the sale, use or other
  25 // dealings in this Software without prior written authorization of the
  26 // copyright holder.
  27
  28 #ifndef _VECTOR_MAP_H
  29 #define _VECTOR_MAP_H
  30
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include <SupportDefs.h>
  35
  36 #include <util/kernel_cpp.h>
  37 #include <KernelUtilsOrder.h>
  38 #include <Vector.h>
  39
  40 namespace VectorMapEntryStrategy {
  41         // Pair
  42         template<typename Key, typename Value,
  43                          typename KeyOrder = KernelUtilsOrder::Ascending<Key> > class Pair;
  44         // ImplicitKey
  45         template<typename Key, typename Value, typename GetKey,
  46                          typename KeyOrder = KernelUtilsOrder::Ascending<Key> >
  47                          class ImplicitKey;
  48 }
  49
  50 template<typename Entry, typename Parent, typename EntryIterator>
  51         class VectorMapIterator;
  52 template<typename _Key, typename _Value, typename Entry, typename Parent>
  53         class VectorMapEntry;
  54
  55 // for convenience
  56 #define _VECTOR_MAP_TEMPLATE_LIST template<typename Key, typename Value, \
  57                                                                                    typename EntryStrategy>
  58 #define _VECTOR_MAP_CLASS_NAME VectorMap<Key, Value, EntryStrategy>
  59 #define _VECTOR_MAP_CLASS_TYPE typename VectorMap<Key, Value, EntryStrategy>
  60
  61 /*!
  62         \class VectorMap
  63         \brief A generic vector-based map implementation.
  64
  65         The map entries are ordered according to the supplied
  66         compare function object. Default is ascending order.
  67
  68         Note that VectorMap::Entry is not the same class as EntryStrategy::Entry.
  69         It is light-weight class, an object of which is returned when a iterator
  70         is dereferenced. It features a Key() and a Value() method returning
  71         references to the entry's key/value. This allows EntryStrategy::Entry
  72         to be an arbitrary class, not needing to implement a certain interface.
  73 */
  74 template<typename Key, typename Value,
  75                  typename EntryStrategy = VectorMapEntryStrategy::Pair<Key, Value> >
  76 class VectorMap {
  77 private:
  78         typedef _VECTOR_MAP_CLASS_NAME                                                  Class;
  79         typedef typename EntryStrategy::Entry                                   _Entry;
  80         typedef typename EntryStrategy::KeyReference                    KeyReference;
  81         typedef Vector<_Entry>                                                                  ElementVector;
  82
  83 public:
  84         typedef VectorMapEntry<KeyReference, Value, _Entry, Class>
  85                                                                                                                         Entry;
  86         typedef VectorMapEntry<KeyReference, const Value, const _Entry,
  87                                                    const Class>                                         ConstEntry;
  88         typedef VectorMapIterator<Entry, Class, typename ElementVector::Iterator>
  89                                                                                                                         Iterator;
  90         typedef VectorMapIterator<ConstEntry, const Class, typename ElementVector::ConstIterator>
  91                                                                                                                         ConstIterator;
  92
  93 private:
  94         static const size_t                             kDefaultChunkSize = 10;
  95         static const size_t                             kMaximalChunkSize = 1024 * 1024;
  96
  97 public:
  98         VectorMap(size_t chunkSize = kDefaultChunkSize);
  99 // TODO: Copy constructor, assignment operator.
 100         ~VectorMap();
 101
 102         status_t Insert(const Key &key, const Value &value);
 103         status_t Put(const Key &key, const Value &value);
 104         Value &Get(const Key &key);
 105         const Value &Get(const Key &key) const;
 106
 107         int32 Remove(const Key &key);
 108         Iterator Erase(const Iterator &iterator);
 109
 110         inline int32 Count() const;
 111         inline bool IsEmpty() const;
 112         void MakeEmpty();
 113
 114         inline Iterator Begin();
 115         inline ConstIterator Begin() const;
 116         inline Iterator End();
 117         inline ConstIterator End() const;
 118         inline Iterator Null();
 119         inline ConstIterator Null() const;
 120
 121         Iterator Find(const Key &key);
 122         ConstIterator Find(const Key &key) const;
 123         Iterator FindClose(const Key &key, bool less);
 124         ConstIterator FindClose(const Key &key, bool less) const;
 125
 126 private:
 127         int32 _FindInsertionIndex(const Key &key, bool &exists) const;
 128
 129 private:
 130 //      friend class Entry;
 131 //      friend class ConstEntry;
 132         friend class VectorMapEntry<KeyReference, Value, _Entry, Class>;
 133         friend class VectorMapEntry<KeyReference, const Value, const _Entry,
 134                 const Class>;
 135
 136         ElementVector   fElements;
 137         EntryStrategy   fEntryStrategy;
 138 };
 139
 140
 141 // VectorMapEntry
 142 template<typename KeyReference, typename _Value, typename Entry,
 143                  typename Parent>
 144 class VectorMapEntry {
 145 private:
 146         typedef VectorMapEntry<KeyReference, _Value, Entry, Parent>     Class;
 147
 148 public:
 149         VectorMapEntry()
 150                 : fParent(NULL), fEntry(NULL) {}
 151
 152         inline KeyReference Key() const
 153         {
 154                 return fParent->fEntryStrategy.GetKey(*fEntry);
 155         }
 156
 157         inline _Value &Value() const
 158         {
 159                 return fParent->fEntryStrategy.GetValue(*fEntry);
 160         }
 161
 162         inline const Class *operator->() const
 163         {
 164                 return this;
 165         }
 166
 167 // private
 168 public:
 169         VectorMapEntry(Parent *parent, Entry *entry)
 170                 : fParent(parent), fEntry(entry) {}
 171
 172 private:
 173         const Parent    *fParent;
 174         Entry                   *fEntry;
 175 };
 176
 177
 178 // VectorMapIterator
 179 template<typename Entry, typename Parent, typename EntryIterator>
 180 class VectorMapIterator {
 181 private:
 182         typedef VectorMapIterator<Entry, Parent, EntryIterator> Iterator;
 183
 184 public:
 185         inline VectorMapIterator()
 186                 : fParent(NULL),
 187                   fIterator()
 188         {
 189         }
 190
 191         inline VectorMapIterator(
 192                 const Iterator &other)
 193                 : fParent(other.fParent),
 194                   fIterator(other.fIterator)
 195         {
 196         }
 197
 198         inline Iterator &operator++()
 199         {
 200                 ++fIterator;
 201                 return *this;
 202         }
 203
 204         inline Iterator operator++(int)
 205         {
 206                 Iterator it(*this);
 207                 ++*this;
 208                 return it;
 209         }
 210
 211         inline Iterator &operator--()
 212         {
 213                 --fIterator;
 214                 return *this;
 215         }
 216
 217         inline Iterator operator--(int)
 218         {
 219                 Iterator it(*this);
 220                 --*this;
 221                 return it;
 222         }
 223
 224         inline Iterator &operator=(const Iterator &other)
 225         {
 226                 fParent = other.fParent;
 227                 fIterator = other.fIterator;
 228                 return *this;
 229         }
 230
 231         inline bool operator==(const Iterator &other) const
 232         {
 233                 return (fParent == other.fParent && fIterator == other.fIterator);
 234         }
 235
 236         inline bool operator!=(const Iterator &other) const
 237         {
 238                 return !(*this == other);
 239         }
 240
 241         inline Entry operator*() const
 242         {
 243                 return Entry(fParent, &*fIterator);
 244         }
 245
 246         inline Entry operator->() const
 247         {
 248                 return Entry(fParent, &*fIterator);
 249         }
 250
 251         inline operator bool() const
 252         {
 253                 return fIterator;
 254         }
 255
 256 // private
 257 public:
 258         inline VectorMapIterator(Parent *parent, const EntryIterator &iterator)
 259                 : fParent(parent),
 260                   fIterator(iterator)
 261         {
 262         }
 263
 264         inline EntryIterator &GetIterator()
 265         {
 266                 return fIterator;
 267         }
 268
 269         inline const EntryIterator &GetIterator() const
 270         {
 271                 return fIterator;
 272         }
 273
 274 protected:
 275         Parent                  *fParent;
 276         EntryIterator   fIterator;
 277 };
 278
 279
 280 // VectorMap
 281
 282 // constructor
 283 /*!     \brief Creates an empty map.
 284         \param chunkSize The granularity for the underlying vector's capacity,
 285                    i.e. the minimal number of elements the capacity grows or shrinks
 286                    when necessary.
 287 */
 288 _VECTOR_MAP_TEMPLATE_LIST
 289 _VECTOR_MAP_CLASS_NAME::VectorMap(size_t chunkSize)
 290         : fElements(chunkSize)
 291 {
 292 }
 293
 294 // destructor
 295 /*!     \brief Frees all resources associated with the object.
 296
 297         The contained keys and values are destroyed. Note, that for pointer
 298         types only the pointer is destroyed, not the object it points to.
 299 */
 300 _VECTOR_MAP_TEMPLATE_LIST
 301 _VECTOR_MAP_CLASS_NAME::~VectorMap()
 302 {
 303 }
 304
 305 // Insert
 306 /*!     \brief Associates a key with a value.
 307
 308         If there is already a value associated with the key, the old entry
 309         is replaced.
 310
 311         \param key The key to which a value shall be associated.
 312         \param value The value to be associated with the key.
 313         \return
 314         - \c B_OK: Everything went fine.
 315         - \c B_NO_MEMORY: Insufficient memory for this operation.
 316         - \c B_BAD_VALUE: The map's EntryStrategy requires some special
 317           relationship between key and value, that \a key and \a value haven't
 318           (doesn't apply to the default strategy).
 319 */
 320 _VECTOR_MAP_TEMPLATE_LIST
 321 status_t
 322 _VECTOR_MAP_CLASS_NAME::Insert(const Key &key, const Value &value)
 323 {
 324         if (!fEntryStrategy.AreCompatible(key, value))
 325                 return B_BAD_VALUE;
 326         bool exists = false;
 327         int32 index = _FindInsertionIndex(key, exists);
 328         if (exists) {
 329                 fElements[index] = fEntryStrategy.MakeEntry(key, value);
 330                 return B_OK;
 331         }
 332         return fElements.Insert(fEntryStrategy.MakeEntry(key, value), index);
 333 }
 334
 335 // Put
 336 /*!     \brief Equivalent to Insert().
 337 */
 338 _VECTOR_MAP_TEMPLATE_LIST
 339 inline
 340 status_t
 341 _VECTOR_MAP_CLASS_NAME::Put(const Key &key, const Value &value)
 342 {
 343         return Insert(key, value);
 344 }
 345
 346 // Get
 347 /*!     \brief Returns the value associated with a given key.
 348
 349         \note Invoking this method for a key not know to the map is dangerous!
 350                   The behavior is unspecified. It may even crash.
 351
 352         \param key The key to be looked up.
 353         \return The value associated with \a key.
 354 */
 355 _VECTOR_MAP_TEMPLATE_LIST
 356 Value &
 357 _VECTOR_MAP_CLASS_NAME::Get(const Key &key)
 358 {
 359         bool exists = false;
 360         int32 index = _FindInsertionIndex(key, exists);
 361         if (!exists)
 362                 return fEntryStrategy.GetValue(fElements[0]);
 363         return fEntryStrategy.GetValue(fElements[index]);
 364 }
 365
 366 // Get
 367 /*!     \brief Returns the value associated with a given key.
 368
 369         \note Invoking this method for a key not know to the map is dangerous!
 370                   The behavior is unspecified. It may even crash.
 371
 372         \param key The key to be looked up.
 373         \return The value associated with \a key.
 374 */
 375 _VECTOR_MAP_TEMPLATE_LIST
 376 const Value &
 377 _VECTOR_MAP_CLASS_NAME::Get(const Key &key) const
 378 {
 379         bool exists = false;
 380         int32 index = _FindInsertionIndex(key, exists);
 381         if (!exists)
 382                 return fEntryStrategy.GetValue(fElements[0]);
 383         return fEntryStrategy.GetValue(fElements[index]);
 384 }
 385
 386 // Remove
 387 /*!     \brief Removes the entry with the supplied key.
 388         \param key The key to be removed.
 389         \return The number of removed occurrences, i.e. \c 1, if the map
 390                         contained an entry with that key, \c 0 otherwise.
 391 */
 392 _VECTOR_MAP_TEMPLATE_LIST
 393 int32
 394 _VECTOR_MAP_CLASS_NAME::Remove(const Key &key)
 395 {
 396         bool exists = false;
 397         int32 index = _FindInsertionIndex(key, exists);
 398         if (!exists)
 399                 return 0;
 400         fElements.Erase(index);
 401         return 1;
 402 }
 403
 404 // Erase
 405 /*!     \brief Removes the entry at the given position.
 406         \param iterator An iterator referring to the entry to be removed.
 407         \return An iterator referring to the entry succeeding the removed
 408                         one (End(), if it was the last element that has been
 409                         removed), or Null(), if \a iterator was an invalid iterator
 410                         (in this case including End()).
 411 */
 412 _VECTOR_MAP_TEMPLATE_LIST
 413 _VECTOR_MAP_CLASS_TYPE::Iterator
 414 _VECTOR_MAP_CLASS_NAME::Erase(const Iterator &iterator)
 415 {
 416         return Iterator(this, fElements.Erase(iterator.GetIterator()));
 417 }
 418
 419 // Count
 420 /*!     \brief Returns the number of entry the map contains.
 421         \return The number of entries the map contains.
 422 */
 423 _VECTOR_MAP_TEMPLATE_LIST
 424 inline
 425 int32
 426 _VECTOR_MAP_CLASS_NAME::Count() const
 427 {
 428         return fElements.Count();
 429 }
 430
 431 // IsEmpty
 432 /*!     \brief Returns whether the map is empty.
 433         \return \c true, if the map is empty, \c false otherwise.
 434 */
 435 _VECTOR_MAP_TEMPLATE_LIST
 436 inline
 437 bool
 438 _VECTOR_MAP_CLASS_NAME::IsEmpty() const
 439 {
 440         return fElements.IsEmpty();
 441 }
 442
 443 // MakeEmpty
 444 /*!     \brief Removes all entries from the map.
 445 */
 446 _VECTOR_MAP_TEMPLATE_LIST
 447 void
 448 _VECTOR_MAP_CLASS_NAME::MakeEmpty()
 449 {
 450         fElements.MakeEmpty();
 451 }
 452
 453 // Begin
 454 /*!     \brief Returns an iterator referring to the beginning of the map.
 455
 456         If the map is not empty, Begin() refers to its first entry,
 457         otherwise it is equal to End() and must not be dereferenced!
 458
 459         \return An iterator referring to the beginning of the map.
 460 */
 461 _VECTOR_MAP_TEMPLATE_LIST
 462 inline
 463 _VECTOR_MAP_CLASS_TYPE::Iterator
 464 _VECTOR_MAP_CLASS_NAME::Begin()
 465 {
 466         return Iterator(this, fElements.Begin());
 467 }
 468
 469 // Begin
 470 /*!     \brief Returns an iterator referring to the beginning of the map.
 471
 472         If the map is not empty, Begin() refers to its first entry,
 473         otherwise it is equal to End() and must not be dereferenced!
 474
 475         \return An iterator referring to the beginning of the map.
 476 */
 477 _VECTOR_MAP_TEMPLATE_LIST
 478 inline
 479 _VECTOR_MAP_CLASS_TYPE::ConstIterator
 480 _VECTOR_MAP_CLASS_NAME::Begin() const
 481 {
 482         return ConstIterator(this, fElements.Begin());
 483 }
 484
 485 // End
 486 /*!     \brief Returns an iterator referring to the end of the map.
 487
 488         The position identified by End() is the one succeeding the last
 489         entry, i.e. it must not be dereferenced!
 490
 491         \return An iterator referring to the end of the map.
 492 */
 493 _VECTOR_MAP_TEMPLATE_LIST
 494 inline
 495 _VECTOR_MAP_CLASS_TYPE::Iterator
 496 _VECTOR_MAP_CLASS_NAME::End()
 497 {
 498         return Iterator(this, fElements.End());
 499 }
 500
 501 // End
 502 /*!     \brief Returns an iterator referring to the end of the map.
 503
 504         The position identified by End() is the one succeeding the last
 505         entry, i.e. it must not be dereferenced!
 506
 507         \return An iterator referring to the end of the map.
 508 */
 509 _VECTOR_MAP_TEMPLATE_LIST
 510 inline
 511 _VECTOR_MAP_CLASS_TYPE::ConstIterator
 512 _VECTOR_MAP_CLASS_NAME::End() const
 513 {
 514         return ConstIterator(this, fElements.End());
 515 }
 516
 517 // Null
 518 /*!     \brief Returns an invalid iterator.
 519
 520         Null() is used as a return value, if something went wrong. It must
 521         neither be incremented or decremented nor dereferenced!
 522
 523         \return An invalid iterator.
 524 */
 525 _VECTOR_MAP_TEMPLATE_LIST
 526 inline
 527 _VECTOR_MAP_CLASS_TYPE::Iterator
 528 _VECTOR_MAP_CLASS_NAME::Null()
 529 {
 530         return Iterator(this, fElements.Null());
 531 }
 532
 533 // Null
 534 /*!     \brief Returns an invalid iterator.
 535
 536         Null() is used as a return value, if something went wrong. It must
 537         neither be incremented or decremented nor dereferenced!
 538
 539         \return An invalid iterator.
 540 */
 541 _VECTOR_MAP_TEMPLATE_LIST
 542 inline
 543 _VECTOR_MAP_CLASS_TYPE::ConstIterator
 544 _VECTOR_MAP_CLASS_NAME::Null() const
 545 {
 546         return ConstIterator(this, fElements.Null());
 547 }
 548
 549 // Find
 550 /*!     \brief Returns an iterator referring to the entry with the
 551                    specified key.
 552         \param key The key of the entry to be found.
 553         \return An iterator referring to the found entry, or End(), if the
 554                         map doesn't contain any entry with the given value.
 555 */
 556 _VECTOR_MAP_TEMPLATE_LIST
 557 _VECTOR_MAP_CLASS_TYPE::Iterator
 558 _VECTOR_MAP_CLASS_NAME::Find(const Key &key)
 559 {
 560         bool exists = false;
 561         int32 index = _FindInsertionIndex(key, exists);
 562         if (!exists)
 563                 return End();
 564         return Iterator(this, fElements.IteratorForIndex(index));
 565 }
 566
 567 // Find
 568 /*!     \brief Returns an iterator referring to the entry with the
 569                    specified key.
 570         \param key The key of the entry to be found.
 571         \return An iterator referring to the found entry, or End(), if the
 572                         map doesn't contain any entry with the given value.
 573 */
 574 _VECTOR_MAP_TEMPLATE_LIST
 575 _VECTOR_MAP_CLASS_TYPE::ConstIterator
 576 _VECTOR_MAP_CLASS_NAME::Find(const Key &key) const
 577 {
 578         bool exists = false;
 579         int32 index = _FindInsertionIndex(key, exists);
 580         if (!exists)
 581                 return End();
 582         return ConstIterator(this, fElements.IteratorForIndex(index));
 583 }
 584
 585 // FindClose
 586 /*!     \brief Returns an iterator referring to the entry with a key closest
 587                    to the specified one.
 588
 589         If the map contains an entry with the specified key, an iterator
 590         to it is returned. Otherwise \a less indicates whether an iterator to
 591         the entry with an directly smaller or greater key shall be returned.
 592
 593         If \a less is \c true and the first entry in the map has a greater
 594         key than the specified one, End() is returned. Similarly, when \a less
 595         is \c false and the last entry's key is smaller. Find() invoked on an
 596         empty map always returns End().
 597
 598         Note, that the key order used for the set is specified as template
 599         argument to the class. Default is ascending order. Descending order
 600         inverts the meaning of \a less, i.e. if \c true, greater values will
 601         be returned, since they are smaller ones according to the order.
 602
 603         \param value The key of the entry to be found.
 604         \return An iterator referring to the found entry, or End(), if the
 605                         map doesn't contain any entry with the given key or a close
 606                         one according to \a less.
 607 */
 608 _VECTOR_MAP_TEMPLATE_LIST
 609 _VECTOR_MAP_CLASS_TYPE::Iterator
 610 _VECTOR_MAP_CLASS_NAME::FindClose(const Key &key, bool less)
 611 {
 612         bool exists = false;
 613         int32 index = _FindInsertionIndex(key, exists);
 614         // If not found, the index _FindInsertionIndex() returns will point to
 615         // an element with a greater value or to End(). So, no special handling
 616         // is needed for !less.
 617         if (exists || !less)
 618                 return Iterator(this, fElements.IteratorForIndex(index));
 619         // An element with a smaller value is desired. The previous one (if any)
 620         // will do.
 621         if (index > 0)
 622                 return Iterator(this, fElements.IteratorForIndex(index - 1));
 623         return End();
 624 }
 625
 626 // FindClose
 627 /*!     \brief Returns an iterator referring to the entry with a key closest
 628                    to the specified one.
 629
 630         If the map contains an entry with the specified key, an iterator
 631         to it is returned. Otherwise \a less indicates whether an iterator to
 632         the entry with an directly smaller or greater key shall be returned.
 633
 634         If \a less is \c true and the first entry in the map has a greater
 635         key than the specified one, End() is returned. Similarly, when \a less
 636         is \c false and the last entry's key is smaller. Find() invoked on an
 637         empty map always returns End().
 638
 639         Note, that the key order used for the set is specified as template
 640         argument to the class. Default is ascending order. Descending order
 641         inverts the meaning of \a less, i.e. if \c true, greater values will
 642         be returned, since they are smaller ones according to the order.
 643
 644         \param value The key of the entry to be found.
 645         \return An iterator referring to the found entry, or End(), if the
 646                         map doesn't contain any entry with the given key or a close
 647                         one according to \a less.
 648 */
 649 _VECTOR_MAP_TEMPLATE_LIST
 650 _VECTOR_MAP_CLASS_TYPE::ConstIterator
 651 _VECTOR_MAP_CLASS_NAME::FindClose(const Key &key, bool less) const
 652 {
 653         bool exists = false;
 654         int32 index = _FindInsertionIndex(key, exists);
 655         // If not found, the index _FindInsertionIndex() returns will point to
 656         // an element with a greater value or to End(). So, no special handling
 657         // is needed for !less.
 658         if (exists || !less)
 659                 return ConstIterator(this, fElements.IteratorForIndex(index));
 660         // An element with a smaller value is desired. The previous one (if any)
 661         // will do.
 662         if (index > 0)
 663                 return ConstIterator(this, fElements.IteratorForIndex(index - 1));
 664         return End();
 665 }
 666
 667 // _FindInsertionIndex
 668 /*!     \brief Finds the index at which the entry with the supplied key is
 669                    located or at which it would need to be inserted.
 670         \param key The key.
 671         \param exists Is set to \c true, if the map does already contain an
 672                    entry with that key, to \c false otherwise.
 673         \return The index at which the entry with the supplied key is
 674                         located or at which it would need to be inserted.
 675 */
 676 _VECTOR_MAP_TEMPLATE_LIST
 677 int32
 678 _VECTOR_MAP_CLASS_NAME::_FindInsertionIndex(const Key &key,
 679                                                                                         bool &exists) const
 680 {
 681         // binary search
 682         int32 lower = 0;
 683         int32 upper = Count();
 684         while (lower < upper) {
 685                 int32 mid = (lower + upper) / 2;
 686                 int cmp = fEntryStrategy.Compare(fEntryStrategy.GetKey(fElements[mid]),
 687                                                                                                                            key);
 688                 if (cmp < 0)
 689                         lower = mid + 1;
 690                 else
 691                         upper = mid;
 692         }
 693         exists = (lower < Count() && fEntryStrategy.Compare(key,
 694                 fEntryStrategy.GetKey(fElements[lower])) == 0);
 695         return lower;
 696 }
 697
 698
 699 // entry strategies
 700
 701 namespace VectorMapEntryStrategy {
 702
 703 // Pair
 704 template<typename Key, typename Value, typename KeyOrder>
 705 class Pair {
 706 public:
 707         typedef const Key       &KeyReference;
 708
 709         class Entry {
 710         public:
 711                 Entry(const Key &key, const Value &value)
 712                         : key(key), value(value) {}
 713
 714                 Key             key;
 715                 Value   value;
 716         };
 717
 718         inline KeyReference GetKey(const Entry &entry) const
 719         {
 720                 return entry.key;
 721         }
 722
 723         inline const Value &GetValue(const Entry &entry) const
 724         {
 725                 return entry.value;
 726         }
 727
 728         inline Value &GetValue(Entry &entry) const
 729         {
 730                 return entry.value;
 731         }
 732
 733         inline Entry MakeEntry(const Key &key, const Value &value) const
 734         {
 735                 return Entry(key, value);
 736         }
 737
 738         inline bool AreCompatible(const Key &, const Value &) const
 739         {
 740                 return true;
 741         }
 742
 743         inline int Compare(const Key &a, const Key &b) const
 744         {
 745                 return fCompare(a, b);
 746         }
 747
 748 private:
 749         KeyOrder        fCompare;
 750 };
 751
 752 // ImplicitKey
 753 template<typename Key, typename Value, typename _GetKey, typename KeyOrder>
 754 class ImplicitKey {
 755 public:
 756         typedef Key                     KeyReference;
 757         typedef Value           Entry;
 758
 759         inline KeyReference GetKey(const Entry &entry) const
 760         {
 761                 return fGetKey(entry);
 762         }
 763
 764         inline const Value &GetValue(const Entry &entry) const
 765         {
 766                 return entry;
 767         }
 768
 769         inline Value &GetValue(Entry &entry) const
 770         {
 771                 return entry;
 772         }
 773
 774         inline Entry MakeEntry(const Key &, const Value &value) const
 775         {
 776                 return value;
 777         }
 778
 779         inline bool AreCompatible(const Key &key, const Value &value) const
 780         {
 781                 return (fGetKey(value) == key);
 782         }
 783
 784         inline int Compare(const Key &a, const Key &b) const
 785         {
 786                 return fCompare(a, b);
 787         }
 788
 789 private:
 790         KeyOrder        fCompare;
 791         _GetKey         fGetKey;
 792 };
 793
 794 }       // VectorMapEntryStrategy
 795
 796 #endif  // _VECTOR_MAP_H