include/flat_map.h

   1 /*
   2  * InspIRCd -- Internet Relay Chat Daemon
   3  *
   4  *   Copyright (C) 2014 Attila Molnar <attilamolnar@hush.com>
   5  *
   6  * This file is part of InspIRCd.  InspIRCd is free software: you can
   7  * redistribute it and/or modify it under the terms of the GNU General Public
   8  * License as published by the Free Software Foundation, version 2.
   9  *
  10  * This program is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  12  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  13  * details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19
  20 #pragma once
  21
  22 #include <vector>
  23
  24 namespace insp
  25 {
  26
  27 namespace detail
  28 {
  29
  30 template <typename T, typename Comp>
  31 class map_pair_compare : public Comp
  32 {
  33         typedef T value_type;
  34         typedef typename value_type::first_type key_type;
  35
  36  public:
  37         bool operator()(const value_type& x, const value_type& y) const
  38         {
  39                 return Comp::operator()(x.first, y.first);
  40         }
  41
  42         bool operator()(const value_type& x, const key_type& y) const
  43         {
  44                 return Comp::operator()(x.first, y);
  45         }
  46
  47         bool operator()(const key_type& x, const value_type& y) const
  48         {
  49                 return Comp::operator()(x, y.first);
  50         }
  51 };
  52
  53 template <typename Val, typename Comp>
  54 class map_value_compare : public std::binary_function<Val, Val, bool>
  55 {
  56  public:
  57         // Constructor should be private
  58
  59         bool operator()(const Val& x, const Val& y) const
  60         {
  61                 Comp c;
  62                 return c(x.first, y.first);
  63         }
  64 };
  65
  66 template <typename T, typename Comp, typename Key = T, typename ElementComp = Comp>
  67 class flat_map_base
  68 {
  69  protected:
  70         typedef std::vector<T> storage_type;
  71         storage_type vect;
  72
  73  public:
  74         typedef typename storage_type::iterator iterator;
  75         typedef typename storage_type::const_iterator const_iterator;
  76         typedef typename storage_type::reverse_iterator reverse_iterator;
  77         typedef typename storage_type::const_reverse_iterator const_reverse_iterator;
  78
  79         typedef typename storage_type::size_type size_type;
  80         typedef typename storage_type::difference_type difference_type;
  81         typedef Key key_type;
  82         typedef T value_type;
  83
  84         typedef Comp key_compare;
  85         typedef ElementComp value_compare;
  86
  87         flat_map_base() { }
  88
  89         flat_map_base(const flat_map_base& other)
  90                 : vect(other.vect)
  91         {
  92         }
  93
  94         size_type size() const { return vect.size(); }
  95         bool empty() const { return vect.empty(); }
  96         size_type capacity() const { return vect.capacity(); }
  97         size_type max_size() const { return vect.max_size(); }
  98
  99         void clear() { vect.clear(); }
 100         void reserve(size_type n) { vect.reserve(n); }
 101
 102         iterator begin() { return vect.begin(); }
 103         iterator end() { return vect.end(); }
 104         reverse_iterator rbegin() { return vect.rbegin(); }
 105         reverse_iterator rend() { return vect.rend(); }
 106
 107         const_iterator begin() const { return vect.begin(); }
 108         const_iterator end() const { return vect.end(); }
 109         const_reverse_iterator rbegin() const { return vect.rbegin(); }
 110         const_reverse_iterator rend() const { return vect.rend(); }
 111
 112         key_compare key_comp() const { return Comp(); }
 113
 114         iterator erase(iterator it) { return vect.erase(it); }
 115         iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
 116         size_type erase(const key_type& x)
 117         {
 118                 size_type n = vect.size();
 119                 std::pair<iterator, iterator> itpair = equal_range(x);
 120                 vect.erase(itpair.first, itpair.second);
 121                 return n - vect.size();
 122         }
 123
 124         iterator find(const key_type& x)
 125         {
 126                 value_compare c;
 127                 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
 128                 if ((it != vect.end()) && (!c(x, *it)))
 129                         return it;
 130                 return vect.end();
 131         }
 132
 133         const_iterator find(const key_type& x) const
 134         {
 135                 // Same as above but this time we return a const_iterator
 136                 value_compare c;
 137                 const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
 138                 if ((it != vect.end()) && (!c(x, *it)))
 139                         return it;
 140                 return vect.end();
 141         }
 142
 143         std::pair<iterator, iterator> equal_range(const key_type& x)
 144         {
 145                 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
 146         }
 147
 148         std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
 149         {
 150                 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
 151         }
 152
 153         iterator lower_bound(const key_type& x)
 154         {
 155                 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
 156         }
 157
 158         const_iterator lower_bound(const key_type& x) const
 159         {
 160                 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
 161         }
 162
 163         iterator upper_bound(const key_type& x)
 164         {
 165                 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
 166         }
 167
 168         const_iterator upper_bound(const key_type& x) const
 169         {
 170                 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
 171         }
 172
 173         size_type count(const key_type& x) const
 174         {
 175                 std::pair<const_iterator, const_iterator> itpair = equal_range(x);
 176                 return std::distance(itpair.first, itpair.second);
 177         }
 178
 179  protected:
 180         std::pair<iterator, bool> insert_single(const value_type& x)
 181         {
 182                 bool inserted = false;
 183
 184                 value_compare c;
 185                 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
 186                 if ((it == vect.end()) || (c(x, *it)))
 187                 {
 188                         inserted = true;
 189                         it = vect.insert(it, x);
 190                 }
 191                 return std::make_pair(it, inserted);
 192         }
 193
 194         iterator insert_multi(const value_type& x)
 195         {
 196                 iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
 197                 return vect.insert(it, x);
 198         }
 199 };
 200
 201 } // namespace detail
 202
 203 template <typename T, typename Comp = std::less<T> >
 204 class flat_set : public detail::flat_map_base<T, Comp>
 205 {
 206         typedef detail::flat_map_base<T, Comp> base_t;
 207
 208  public:
 209         typedef typename base_t::iterator iterator;
 210         typedef typename base_t::value_type value_type;
 211
 212         flat_set() { }
 213
 214         template <typename InputIterator>
 215         flat_set(InputIterator first, InputIterator last)
 216         {
 217                 this->insert(first, last);
 218         }
 219
 220         flat_set(const flat_set& other)
 221                 : base_t(other)
 222         {
 223         }
 224
 225         std::pair<iterator, bool> insert(const value_type& x)
 226         {
 227                 return this->insert_single(x);
 228         }
 229
 230         template <typename InputIterator>
 231         void insert(InputIterator first, InputIterator last)
 232         {
 233                 for (; first != last; ++first)
 234                         this->insert_single(*first);
 235         }
 236
 237         void swap(flat_set& other)
 238         {
 239                 base_t::vect.swap(other.vect);
 240         }
 241 };
 242
 243 template <typename T, typename Comp = std::less<T> >
 244 class flat_multiset : public detail::flat_map_base<T, Comp>
 245 {
 246         typedef detail::flat_map_base<T, Comp> base_t;
 247
 248  public:
 249         typedef typename base_t::iterator iterator;
 250         typedef typename base_t::value_type value_type;
 251
 252         flat_multiset() { }
 253
 254         template <typename InputIterator>
 255         flat_multiset(InputIterator first, InputIterator last)
 256         {
 257                 this->insert(first, last);
 258         }
 259
 260         flat_multiset(const flat_multiset& other)
 261                 : base_t(other)
 262         {
 263         }
 264
 265         iterator insert(const value_type& x)
 266         {
 267                 return this->insert_multi(x);
 268         }
 269
 270         template <typename InputIterator>
 271         void insert(InputIterator first, InputIterator last)
 272         {
 273                 for (; first != last; ++first)
 274                         insert_multi(*first);
 275         }
 276
 277         void swap(flat_multiset& other)
 278         {
 279                 base_t::vect.swap(other.vect);
 280         }
 281 };
 282
 283 template <typename T, typename U, typename Comp = std::less<T> >
 284 class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> >
 285 {
 286         typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> > base_t;
 287
 288  public:
 289         typedef typename base_t::iterator iterator;
 290         typedef typename base_t::key_type key_type;
 291         typedef typename base_t::value_type value_type;
 292         typedef U mapped_type;
 293         typedef typename base_t::value_compare value_compare;
 294
 295         flat_map() { }
 296
 297         template <typename InputIterator>
 298         flat_map(InputIterator first, InputIterator last)
 299         {
 300                 insert(first, last);
 301         }
 302
 303         flat_map(const flat_map& other)
 304                 : base_t(other)
 305         {
 306         }
 307
 308         std::pair<iterator, bool> insert(const value_type& x)
 309         {
 310                 return this->insert_single(x);
 311         }
 312
 313         template <typename InputIterator>
 314         void insert(InputIterator first, InputIterator last)
 315         {
 316                 for (; first != last; ++first)
 317                         this->insert_single(*first);
 318         }
 319
 320         void swap(flat_map& other)
 321         {
 322                 base_t::vect.swap(other.vect);
 323         }
 324
 325         mapped_type& operator[](const key_type& x)
 326         {
 327                 return insert(std::make_pair(x, mapped_type())).first->second;
 328         }
 329
 330         value_compare value_comp() const
 331         {
 332                 return value_compare();
 333         }
 334 };
 335
 336 template <typename T, typename U, typename Comp = std::less<T> >
 337 class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> >
 338 {
 339         typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> > base_t;
 340
 341  public:
 342         typedef typename base_t::iterator iterator;
 343         typedef typename base_t::value_type value_type;
 344         typedef U mapped_type;
 345         typedef typename base_t::value_compare value_compare;
 346
 347         flat_multimap() { }
 348
 349         template <typename InputIterator>
 350         flat_multimap(InputIterator first, InputIterator last)
 351         {
 352                 this->insert(first, last);
 353         }
 354
 355         flat_multimap(const flat_multimap& other)
 356                 : base_t(other)
 357         {
 358         }
 359
 360         iterator insert(const value_type& x)
 361         {
 362                 return this->insert_multi(x);
 363         }
 364
 365         template <typename InputIterator>
 366         void insert(InputIterator first, InputIterator last)
 367         {
 368                 for (; first != last; ++first)
 369                         this->insert_multi(*first);
 370         }
 371
 372         void swap(flat_multimap& other)
 373         {
 374                 base_t::vect.swap(other.vect);
 375         }
 376
 377         value_compare value_comp() const
 378         {
 379                 return value_compare();
 380         }
 381 };
 382
 383 } // namespace insp