include/flat_map.h

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