src/3rdparty/cpp-btree/btree_container.h

   1 // Copyright 2013 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef UTIL_BTREE_BTREE_CONTAINER_H__
  16 #define UTIL_BTREE_BTREE_CONTAINER_H__
  17
  18 #include <iosfwd>
  19 #include <utility>
  20
  21 #include "btree.h"
  22
  23 namespace btree {
  24
  25 // A common base class for btree_set, btree_map, btree_multiset and
  26 // btree_multimap.
  27 template <typename Tree>
  28 class btree_container {
  29   typedef btree_container<Tree> self_type;
  30
  31  public:
  32   typedef typename Tree::params_type params_type;
  33   typedef typename Tree::key_type key_type;
  34   typedef typename Tree::value_type value_type;
  35   typedef typename Tree::key_compare key_compare;
  36   typedef typename Tree::allocator_type allocator_type;
  37   typedef typename Tree::pointer pointer;
  38   typedef typename Tree::const_pointer const_pointer;
  39   typedef typename Tree::reference reference;
  40   typedef typename Tree::const_reference const_reference;
  41   typedef typename Tree::size_type size_type;
  42   typedef typename Tree::difference_type difference_type;
  43   typedef typename Tree::iterator iterator;
  44   typedef typename Tree::const_iterator const_iterator;
  45   typedef typename Tree::reverse_iterator reverse_iterator;
  46   typedef typename Tree::const_reverse_iterator const_reverse_iterator;
  47
  48  public:
  49   // Default constructor.
  50   btree_container(const key_compare &comp, const allocator_type &alloc)
  51       : tree_(comp, alloc) {
  52   }
  53
  54   // Copy constructor.
  55   btree_container(const self_type &x)
  56       : tree_(x.tree_) {
  57   }
  58
  59   // Iterator routines.
  60   iterator begin() { return tree_.begin(); }
  61   const_iterator begin() const { return tree_.begin(); }
  62   iterator end() { return tree_.end(); }
  63   const_iterator end() const { return tree_.end(); }
  64   reverse_iterator rbegin() { return tree_.rbegin(); }
  65   const_reverse_iterator rbegin() const { return tree_.rbegin(); }
  66   reverse_iterator rend() { return tree_.rend(); }
  67   const_reverse_iterator rend() const { return tree_.rend(); }
  68
  69   // Const iterator routines.
  70   const_iterator cbegin() const { return begin(); }
  71   const_iterator cend() const { return end(); }
  72   const_reverse_iterator crbegin() const { return rbegin(); }
  73   const_reverse_iterator crend() const { return rend(); }
  74
  75   // Lookup routines.
  76   iterator lower_bound(const key_type &key) {
  77     return tree_.lower_bound(key);
  78   }
  79   const_iterator lower_bound(const key_type &key) const {
  80     return tree_.lower_bound(key);
  81   }
  82   iterator upper_bound(const key_type &key) {
  83     return tree_.upper_bound(key);
  84   }
  85   const_iterator upper_bound(const key_type &key) const {
  86     return tree_.upper_bound(key);
  87   }
  88   std::pair<iterator,iterator> equal_range(const key_type &key) {
  89     return tree_.equal_range(key);
  90   }
  91   std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const {
  92     return tree_.equal_range(key);
  93   }
  94
  95   // Utility routines.
  96   void clear() {
  97     tree_.clear();
  98   }
  99   void swap(self_type &x) {
 100     tree_.swap(x.tree_);
 101   }
 102   void dump(std::ostream &os) const {
 103     tree_.dump(os);
 104   }
 105   void verify() const {
 106     tree_.verify();
 107   }
 108
 109   // Size routines.
 110   size_type size() const { return tree_.size(); }
 111   size_type max_size() const { return tree_.max_size(); }
 112   bool empty() const { return tree_.empty(); }
 113   size_type height() const { return tree_.height(); }
 114   size_type internal_nodes() const { return tree_.internal_nodes(); }
 115   size_type leaf_nodes() const { return tree_.leaf_nodes(); }
 116   size_type nodes() const { return tree_.nodes(); }
 117   size_type bytes_used() const { return tree_.bytes_used(); }
 118   static double average_bytes_per_value() {
 119     return Tree::average_bytes_per_value();
 120   }
 121   double fullness() const { return tree_.fullness(); }
 122   double overhead() const { return tree_.overhead(); }
 123
 124   bool operator==(const self_type& x) const {
 125     if (size() != x.size()) {
 126       return false;
 127     }
 128     for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi) {
 129       if (*i != *xi) {
 130         return false;
 131       }
 132     }
 133     return true;
 134   }
 135
 136   bool operator!=(const self_type& other) const {
 137     return !operator==(other);
 138   }
 139
 140   // Functor retrieval
 141   key_compare key_comp() const { return tree_.key_comp(); }
 142
 143  protected:
 144   Tree tree_;
 145 };
 146
 147 template <typename T>
 148 inline std::ostream& operator<<(std::ostream &os, const btree_container<T> &b) {
 149   b.dump(os);
 150   return os;
 151 }
 152
 153 // A common base class for btree_set and safe_btree_set.
 154 template <typename Tree>
 155 class btree_unique_container : public btree_container<Tree> {
 156   typedef btree_unique_container<Tree> self_type;
 157   typedef btree_container<Tree> super_type;
 158
 159  public:
 160   typedef typename Tree::key_type key_type;
 161   typedef typename Tree::value_type value_type;
 162   typedef typename Tree::size_type size_type;
 163   typedef typename Tree::key_compare key_compare;
 164   typedef typename Tree::allocator_type allocator_type;
 165   typedef typename Tree::iterator iterator;
 166   typedef typename Tree::const_iterator const_iterator;
 167
 168  public:
 169   // Default constructor.
 170   btree_unique_container(const key_compare &comp = key_compare(),
 171                          const allocator_type &alloc = allocator_type())
 172       : super_type(comp, alloc) {
 173   }
 174
 175   // Copy constructor.
 176   btree_unique_container(const self_type &x)
 177       : super_type(x) {
 178   }
 179
 180   // Range constructor.
 181   template <class InputIterator>
 182   btree_unique_container(InputIterator b, InputIterator e,
 183                          const key_compare &comp = key_compare(),
 184                          const allocator_type &alloc = allocator_type())
 185       : super_type(comp, alloc) {
 186     insert(b, e);
 187   }
 188
 189   // Lookup routines.
 190   iterator find(const key_type &key) {
 191     return this->tree_.find_unique(key);
 192   }
 193   const_iterator find(const key_type &key) const {
 194     return this->tree_.find_unique(key);
 195   }
 196   size_type count(const key_type &key) const {
 197     return this->tree_.count_unique(key);
 198   }
 199
 200   // Insertion routines.
 201   std::pair<iterator,bool> insert(const value_type &x) {
 202     return this->tree_.insert_unique(x);
 203   }
 204   iterator insert(iterator position, const value_type &x) {
 205     return this->tree_.insert_unique(position, x);
 206   }
 207   template <typename InputIterator>
 208   void insert(InputIterator b, InputIterator e) {
 209     this->tree_.insert_unique(b, e);
 210   }
 211
 212   // Deletion routines.
 213   int erase(const key_type &key) {
 214     return this->tree_.erase_unique(key);
 215   }
 216   // Erase the specified iterator from the btree. The iterator must be valid
 217   // (i.e. not equal to end()).  Return an iterator pointing to the node after
 218   // the one that was erased (or end() if none exists).
 219   iterator erase(const iterator &iter) {
 220     return this->tree_.erase(iter);
 221   }
 222   void erase(const iterator &first, const iterator &last) {
 223     this->tree_.erase(first, last);
 224   }
 225 };
 226
 227 // A common base class for btree_map and safe_btree_map.
 228 template <typename Tree>
 229 class btree_map_container : public btree_unique_container<Tree> {
 230   typedef btree_map_container<Tree> self_type;
 231   typedef btree_unique_container<Tree> super_type;
 232
 233  public:
 234   typedef typename Tree::key_type key_type;
 235   typedef typename Tree::data_type data_type;
 236   typedef typename Tree::value_type value_type;
 237   typedef typename Tree::mapped_type mapped_type;
 238   typedef typename Tree::key_compare key_compare;
 239   typedef typename Tree::allocator_type allocator_type;
 240
 241  private:
 242   // A pointer-like object which only generates its value when
 243   // dereferenced. Used by operator[] to avoid constructing an empty data_type
 244   // if the key already exists in the map.
 245   struct generate_value {
 246     generate_value(const key_type &k)
 247         : key(k) {
 248     }
 249     value_type operator*() const {
 250       return std::make_pair(key, data_type());
 251     }
 252     const key_type &key;
 253   };
 254
 255  public:
 256   // Default constructor.
 257   btree_map_container(const key_compare &comp = key_compare(),
 258                       const allocator_type &alloc = allocator_type())
 259       : super_type(comp, alloc) {
 260   }
 261
 262   // Copy constructor.
 263   btree_map_container(const self_type &x)
 264       : super_type(x) {
 265   }
 266
 267   // Range constructor.
 268   template <class InputIterator>
 269   btree_map_container(InputIterator b, InputIterator e,
 270                       const key_compare &comp = key_compare(),
 271                       const allocator_type &alloc = allocator_type())
 272       : super_type(b, e, comp, alloc) {
 273   }
 274
 275   // Insertion routines.
 276   data_type& operator[](const key_type &key) {
 277     return this->tree_.insert_unique(key, generate_value(key)).first->second;
 278   }
 279 };
 280
 281 // A common base class for btree_multiset and btree_multimap.
 282 template <typename Tree>
 283 class btree_multi_container : public btree_container<Tree> {
 284   typedef btree_multi_container<Tree> self_type;
 285   typedef btree_container<Tree> super_type;
 286
 287  public:
 288   typedef typename Tree::key_type key_type;
 289   typedef typename Tree::value_type value_type;
 290   typedef typename Tree::size_type size_type;
 291   typedef typename Tree::key_compare key_compare;
 292   typedef typename Tree::allocator_type allocator_type;
 293   typedef typename Tree::iterator iterator;
 294   typedef typename Tree::const_iterator const_iterator;
 295
 296  public:
 297   // Default constructor.
 298   btree_multi_container(const key_compare &comp = key_compare(),
 299                         const allocator_type &alloc = allocator_type())
 300       : super_type(comp, alloc) {
 301   }
 302
 303   // Copy constructor.
 304   btree_multi_container(const self_type &x)
 305       : super_type(x) {
 306   }
 307
 308   // Range constructor.
 309   template <class InputIterator>
 310   btree_multi_container(InputIterator b, InputIterator e,
 311                         const key_compare &comp = key_compare(),
 312                         const allocator_type &alloc = allocator_type())
 313       : super_type(comp, alloc) {
 314     insert(b, e);
 315   }
 316
 317   // Lookup routines.
 318   iterator find(const key_type &key) {
 319     return this->tree_.find_multi(key);
 320   }
 321   const_iterator find(const key_type &key) const {
 322     return this->tree_.find_multi(key);
 323   }
 324   size_type count(const key_type &key) const {
 325     return this->tree_.count_multi(key);
 326   }
 327
 328   // Insertion routines.
 329   iterator insert(const value_type &x) {
 330     return this->tree_.insert_multi(x);
 331   }
 332   iterator insert(iterator position, const value_type &x) {
 333     return this->tree_.insert_multi(position, x);
 334   }
 335   template <typename InputIterator>
 336   void insert(InputIterator b, InputIterator e) {
 337     this->tree_.insert_multi(b, e);
 338   }
 339
 340   // Deletion routines.
 341   int erase(const key_type &key) {
 342     return this->tree_.erase_multi(key);
 343   }
 344   // Erase the specified iterator from the btree. The iterator must be valid
 345   // (i.e. not equal to end()).  Return an iterator pointing to the node after
 346   // the one that was erased (or end() if none exists).
 347   iterator erase(const iterator &iter) {
 348     return this->tree_.erase(iter);
 349   }
 350   void erase(const iterator &first, const iterator &last) {
 351     this->tree_.erase(first, last);
 352   }
 353 };
 354
 355 } // namespace btree
 356
 357 #endif  // UTIL_BTREE_BTREE_CONTAINER_H__