OpenTTD
smallmap_type.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
10 #ifndef SMALLMAP_TYPE_HPP
11 #define SMALLMAP_TYPE_HPP
12 
13 #include "smallvec_type.hpp"
14 
20 template <typename T, typename U>
21 struct SmallPair {
22  T first;
23  U second;
24 
26  inline SmallPair(const T &first, const U &second) : first(first), second(second) { }
27  SmallPair() = default;
28 };
29 
39 template <typename T, typename U>
40 struct SmallMap : std::vector<SmallPair<T, U> > {
41  typedef ::SmallPair<T, U> Pair;
42  typedef Pair *iterator;
43  typedef const Pair *const_iterator;
44 
46  inline SmallMap() { }
48  inline ~SmallMap() { }
49 
55  inline typename std::vector<Pair>::const_iterator Find(const T &key) const
56  {
57  typename std::vector<Pair>::const_iterator it;
58  for (it = std::vector<Pair>::begin(); it != std::vector<Pair>::end(); it++) {
59  if (key == it->first) return it;
60  }
61  return it;
62  }
63 
69  inline Pair *Find(const T &key)
70  {
71  for (uint i = 0; i < std::vector<Pair>::size(); i++) {
72  if (key == std::vector<Pair>::operator[](i).first) return &std::vector<Pair>::operator[](i);
73  }
74  return this->End();
75  }
76 
77  inline const Pair *End() const
78  {
79  return std::vector<Pair>::data() + std::vector<Pair>::size();
80  }
81 
82  inline Pair *End()
83  {
84  return std::vector<Pair>::data() + std::vector<Pair>::size();
85  }
86 
87 
93  inline bool Contains(const T &key) const
94  {
95  return this->Find(key) != std::vector<Pair>::end();
96  }
97 
103  inline bool Contains(const T &key)
104  {
105  return this->Find(key) != this->End();
106  }
107 
113  inline void Erase(Pair *pair)
114  {
115  assert(pair >= std::vector<Pair>::data() && pair < this->End());
116  auto distance = pair - std::vector<Pair>::data();
117  std::vector<Pair>::erase(std::vector<Pair>::begin() + distance);
118  }
119 
126  inline bool Erase(const T &key)
127  {
128  auto *pair = this->Find(key);
129  if (pair == this->End()) return false;
130 
131  this->Erase(pair);
132  return true;
133  }
134 
141  inline bool Insert(const T &key, const U &data)
142  {
143  if (this->Contains(key)) return false;
144  std::vector<Pair>::emplace_back(key, data);
145  return true;
146  }
147 
154  inline U &operator[](const T &key)
155  {
156  for (uint i = 0; i < std::vector<Pair>::size(); i++) {
157  if (key == std::vector<Pair>::operator[](i).first) return std::vector<Pair>::operator[](i).second;
158  }
159  /*C++17: Pair &n = */ std::vector<Pair>::emplace_back();
160  Pair &n = std::vector<Pair>::back();
161  n.first = key;
162  return n.second;
163  }
164 };
165 
166 #endif /* SMALLMAP_TYPE_HPP */
SmallPair(const T &first, const U &second)
Initializes this Pair with data.
Simple vector class that allows allocating an item without the need to copy this->data needlessly...
Pair * Find(const T &key)
Finds given key in this map.
std::vector< Pair >::const_iterator Find(const T &key) const
Finds given key in this map.
U & operator[](const T &key)
Returns data belonging to this key.
bool Erase(const T &key)
Removes given key from this map.
Implementation of simple mapping class.
bool Contains(const T &key)
Tests whether a key is assigned in this map.
SmallMap()
Creates new SmallMap.
Simple pair of data.
bool Contains(const T &key) const
Tests whether a key is assigned in this map.
~SmallMap()
Data are freed in SmallVector destructor.
bool Insert(const T &key, const U &data)
Adds new item to this map.
void Erase(Pair *pair)
Removes given pair from this map.