OpenTTD
smallmap_type.hpp
Go to the documentation of this file.
1 /* $Id: smallmap_type.hpp 24741 2012-11-14 22:50:30Z frosch $ */
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 #include "sort_func.hpp"
17 
23 template <typename T, typename U>
24 struct SmallPair {
25  T first;
26  U second;
27 
29  inline SmallPair(const T &first, const U &second) : first(first), second(second) { }
30 };
31 
41 template <typename T, typename U, uint S = 16>
42 struct SmallMap : SmallVector<SmallPair<T, U>, S> {
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 const Pair *Find(const T &key) const
58  {
59  for (uint i = 0; i < this->items; i++) {
60  if (key == this->data[i].first) return &this->data[i];
61  }
62  return this->End();
63  }
64 
70  inline Pair *Find(const T &key)
71  {
72  for (uint i = 0; i < this->items; i++) {
73  if (key == this->data[i].first) return &this->data[i];
74  }
75  return this->End();
76  }
77 
83  inline bool Contains(const T &key) const
84  {
85  return this->Find(key) != this->End();
86  }
87 
93  inline void Erase(Pair *pair)
94  {
95  assert(pair >= this->Begin() && pair < this->End());
96  *pair = this->data[--this->items];
97  }
98 
105  inline bool Erase(const T &key)
106  {
107  for (uint i = 0; i < this->items; i++) {
108  if (key == this->data[i].first) {
109  this->data[i] = this->data[--this->items];
110  return true;
111  }
112  }
113  return false;
114  }
115 
122  inline bool Insert(const T &key, const U &data)
123  {
124  if (this->Contains(key)) return false;
125  Pair *n = this->Append();
126  n->first = key;
127  n->second = data;
128  return true;
129  }
130 
137  inline U &operator[](const T &key)
138  {
139  for (uint i = 0; i < this->items; i++) {
140  if (key == this->data[i].first) return this->data[i].second;
141  }
142  Pair *n = this->Append();
143  n->first = key;
144  return n->second;
145  }
146 
147  inline void SortByKey()
148  {
149  QSortT(this->Begin(), this->items, KeySorter);
150  }
151 
152  static int CDECL KeySorter(const Pair *a, const Pair *b)
153  {
154  return a->first - b->first;
155  }
156 };
157 
158 #endif /* SMALLMAP_TYPE_HPP */
bool Contains(const T &key) const
Tests whether a key is assigned in this map.
const Pair * Find(const T &key) const
Finds given key in this map.
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...
Implementation of simple mapping class.
Pair * Find(const T &key)
Finds given key in this map.
bool Insert(const T &key, const U &data)
Adds new item to this map.
~SmallMap()
Data are freed in SmallVector destructor.
Simple vector template class.
Simple pair of data.
SmallMap()
Creates new SmallMap.
void Erase(Pair *pair)
Removes given pair from this map.
U & operator[](const T &key)
Returns data belonging to this key.
Functions related to sorting operations.
static void QSortT(T *base, uint num, int(CDECL *comparator)(const T *, const T *), bool desc=false)
Type safe qsort()
Definition: sort_func.hpp:28
bool Erase(const T &key)
Removes given key from this map.