include/flat_map.h

   1 /*
   2  * InspIRCd -- Internet Relay Chat Daemon
   3  *
   4  *   Copyright (C) 2019 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         size_type size() const { return vect.size(); }
  96         bool empty() const { return vect.empty(); }
  97         size_type capacity() const { return vect.capacity(); }
  98         size_type max_size() const { return vect.max_size(); }
  99
 100         void clear() { vect.clear(); }
 101         void reserve(size_type n) { vect.reserve(n); }
 102
 103         iterator begin() { return vect.begin(); }
 104         iterator end() { return vect.end(); }
 105         reverse_iterator rbegin() { return vect.rbegin(); }
 106         reverse_iterator rend() { return vect.rend(); }
 107
 108         const_iterator begin() const { return vect.begin(); }
 109         const_iterator end() const { return vect.end(); }
 110         const_reverse_iterator rbegin() const { return vect.rbegin(); }
 111         const_reverse_iterator rend() const { return vect.rend(); }
 112
 113         key_compare key_comp() const { return Comp(); }
 114
 115         iterator erase(iterator it) { return vect.erase(it); }
 116         iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
 117         size_type erase(const key_type& x)
 118         {
 119                 size_type n = vect.size();
 120                 std::pair<iterator, iterator> itpair = equal_range(x);
 121                 vect.erase(itpair.first, itpair.second);
 122                 return n - vect.size();
 123         }
 124
 125         iterator find(const key_type& x)
 126         {
 127                 value_compare c;
 128                 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
 129                 if ((it != vect.end()) && (!c(x, *it)))
 130                         return it;
 131                 return vect.end();
 132         }
 133
 134         const_iterator find(const key_type& x) const
 135         {
 136                 // Same as above but this time we return a const_iterator
 137                 value_compare c;
 138                 const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
 139                 if ((it != vect.end()) && (!c(x, *it)))
 140                         return it;
 141                 return vect.end();
 142         }
 143
 144         std::pair<iterator, iterator> equal_range(const key_type& x)
 145         {
 146                 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
 147         }
 148
 149         std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
 150         {
 151                 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
 152         }
 153
 154         iterator lower_bound(const key_type& x)
 155         {
 156                 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
 157         }
 158
 159         const_iterator lower_bound(const key_type& x) const
 160         {
 161                 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
 162         }
 163
 164         iterator upper_bound(const key_type& x)
 165         {
 166                 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
 167         }
 168
 169         const_iterator upper_bound(const key_type& x) const
 170         {
 171                 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
 172         }
 173
 174         size_type count(const key_type& x) const
 175         {
 176                 std::pair<const_iterator, const_iterator> itpair = equal_range(x);
 177                 return std::distance(itpair.first, itpair.second);
 178         }
 179
 180  protected:
 181         std::pair<iterator, bool> insert_single(const value_type& x)
 182         {
 183                 bool inserted = false;
 184
 185                 value_compare c;
 186                 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
 187                 if ((it == vect.end()) || (c(x, *it)))
 188                 {
 189                         inserted = true;
 190                         it = vect.insert(it, x);
 191                 }
 192                 return std::make_pair(it, inserted);
 193         }
 194
 195         iterator insert_multi(const value_type& x)
 196         {
 197                 iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
 198                 return vect.insert(it, x);
 199         }
 200 };
 201
 202 } // namespace detail
 203
 204 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
 205 class flat_set : public detail::flat_map_base<T, Comp, T, ElementComp>
 206 {
 207         typedef detail::flat_map_base<T, Comp, T, ElementComp> base_t;
 208
 209  public:
 210         typedef typename base_t::iterator iterator;
 211         typedef typename base_t::value_type value_type;
 212
 213         flat_set() { }
 214
 215         template <typename InputIterator>
 216         flat_set(InputIterator first, InputIterator last)
 217         {
 218                 this->insert(first, last);
 219         }
 220
 221         flat_set(const flat_set& other)
 222                 : base_t(other)
 223         {
 224         }
 225
 226         std::pair<iterator, bool> insert(const value_type& x)
 227         {
 228                 return this->insert_single(x);
 229         }
 230
 231         template <typename InputIterator>
 232         void insert(InputIterator first, InputIterator last)
 233         {
 234                 for (; first != last; ++first)
 235                         this->insert_single(*first);
 236         }
 237
 238         void swap(flat_set& other)
 239         {
 240                 base_t::vect.swap(other.vect);
 241         }
 242 };
 243
 244 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
 245 class flat_multiset : public detail::flat_map_base<T, Comp, T, ElementComp>
 246 {
 247         typedef detail::flat_map_base<T, Comp, T, ElementComp> base_t;
 248
 249  public:
 250         typedef typename base_t::iterator iterator;
 251         typedef typename base_t::value_type value_type;
 252
 253         flat_multiset() { }
 254
 255         template <typename InputIterator>
 256         flat_multiset(InputIterator first, InputIterator last)
 257         {
 258                 this->insert(first, last);
 259         }
 260
 261         flat_multiset(const flat_multiset& other)
 262                 : base_t(other)
 263         {
 264         }
 265
 266         iterator insert(const value_type& x)
 267         {
 268                 return this->insert_multi(x);
 269         }
 270
 271         template <typename InputIterator>
 272         void insert(InputIterator first, InputIterator last)
 273         {
 274                 for (; first != last; ++first)
 275                         insert_multi(*first);
 276         }
 277
 278         void swap(flat_multiset& other)
 279         {
 280                 base_t::vect.swap(other.vect);
 281         }
 282 };
 283
 284 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
 285 class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
 286 {
 287         typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> > base_t;
 288
 289  public:
 290         typedef typename base_t::iterator iterator;
 291         typedef typename base_t::key_type key_type;
 292         typedef typename base_t::value_type value_type;
 293         typedef U mapped_type;
 294         typedef typename base_t::value_compare value_compare;
 295
 296         flat_map() { }
 297
 298         template <typename InputIterator>
 299         flat_map(InputIterator first, InputIterator last)
 300         {
 301                 insert(first, last);
 302         }
 303
 304         flat_map(const flat_map& other)
 305                 : base_t(other)
 306         {
 307         }
 308
 309         std::pair<iterator, bool> insert(const value_type& x)
 310         {
 311                 return this->insert_single(x);
 312         }
 313
 314         template <typename InputIterator>
 315         void insert(InputIterator first, InputIterator last)
 316         {
 317                 for (; first != last; ++first)
 318                         this->insert_single(*first);
 319         }
 320
 321         void swap(flat_map& other)
 322         {
 323                 base_t::vect.swap(other.vect);
 324         }
 325
 326         mapped_type& operator[](const key_type& x)
 327         {
 328                 return insert(std::make_pair(x, mapped_type())).first->second;
 329         }
 330
 331         value_compare value_comp() const
 332         {
 333                 return value_compare();
 334         }
 335 };
 336
 337 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
 338 class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
 339 {
 340         typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> > base_t;
 341
 342  public:
 343         typedef typename base_t::iterator iterator;
 344         typedef typename base_t::value_type value_type;
 345         typedef U mapped_type;
 346         typedef typename base_t::value_compare value_compare;
 347
 348         flat_multimap() { }
 349
 350         template <typename InputIterator>
 351         flat_multimap(InputIterator first, InputIterator last)
 352         {
 353                 this->insert(first, last);
 354         }
 355
 356         flat_multimap(const flat_multimap& other)
 357                 : base_t(other)
 358         {
 359         }
 360
 361         iterator insert(const value_type& x)
 362         {
 363                 return this->insert_multi(x);
 364         }
 365
 366         template <typename InputIterator>
 367         void insert(InputIterator first, InputIterator last)
 368         {
 369                 for (; first != last; ++first)
 370                         this->insert_multi(*first);
 371         }
 372
 373         void swap(flat_multimap& other)
 374         {
 375                 base_t::vect.swap(other.vect);
 376         }
 377
 378         value_compare value_comp() const
 379         {
 380                 return value_compare();
 381         }
 382 };
 383
 384 } // namespace insp