OpenTTD
smallmap_type.hpp
Go to the documentation of this file.
1 /* $Id$ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #ifndef SMALLMAP_TYPE_HPP
13 #define SMALLMAP_TYPE_HPP
14 
15 #include "smallvec_type.hpp"
16 
22 template <typename T, typename U>
23 struct SmallPair {
24  T first;
25  U second;
26 
28  inline SmallPair(const T &first, const U &second) : first(first), second(second) { }
29  SmallPair() = default;
30 };
31 
41 template <typename T, typename U>
42 struct SmallMap : std::vector<SmallPair<T, U> > {
43  typedef ::SmallPair<T, U> Pair;
44  typedef Pair *iterator;
45  typedef const Pair *const_iterator;
46 
48  inline SmallMap() { }
50  inline ~SmallMap() { }
51 
57  inline typename std::vector<Pair>::const_iterator Find(const T &key) const
58  {
59  typename std::vector<Pair>::const_iterator it;
60  for (it = std::vector<Pair>::begin(); it != std::vector<Pair>::end(); it++) {
61  if (key == it->first) return it;
62  }
63  return it;
64  }
65 
71  inline Pair *Find(const T &key)
72  {
73  for (uint i = 0; i < std::vector<Pair>::size(); i++) {
74  if (key == std::vector<Pair>::operator[](i).first) return &std::vector<Pair>::operator[](i);
75  }
76  return this->End();
77  }
78 
79  inline const Pair *End() const
80  {
81  return std::vector<Pair>::data() + std::vector<Pair>::size();
82  }
83 
84  inline Pair *End()
85  {
86  return std::vector<Pair>::data() + std::vector<Pair>::size();
87  }
88 
89 
95  inline bool Contains(const T &key) const
96  {
97  return this->Find(key) != std::vector<Pair>::end();
98  }
99 
105  inline bool Contains(const T &key)
106  {
107  return this->Find(key) != this->End();
108  }
109 
115  inline void Erase(Pair *pair)
116  {
117  assert(pair >= std::vector<Pair>::data() && pair < this->End());
118  auto distance = pair - std::vector<Pair>::data();
119  std::vector<Pair>::erase(std::vector<Pair>::begin() + distance);
120  }
121 
128  inline bool Erase(const T &key)
129  {
130  auto *pair = this->Find(key);
131  if (pair == this->End()) return false;
132 
133  this->Erase(pair);
134  return true;
135  }
136 
143  inline bool Insert(const T &key, const U &data)
144  {
145  if (this->Contains(key)) return false;
146  std::vector<Pair>::emplace_back(key, data);
147  return true;
148  }
149 
156  inline U &operator[](const T &key)
157  {
158  for (uint i = 0; i < std::vector<Pair>::size(); i++) {
159  if (key == std::vector<Pair>::operator[](i).first) return std::vector<Pair>::operator[](i).second;
160  }
161  /*C++17: Pair &n = */ std::vector<Pair>::emplace_back();
162  Pair &n = std::vector<Pair>::back();
163  n.first = key;
164  return n.second;
165  }
166 };
167 
168 #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.