ESPResSo
Extensible Simulation Package for Research on Soft Matter Systems
Loading...
Searching...
No Matches
NumeratedContainer.hpp
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015-2022 The ESPResSo project
3 *
4 * This file is part of ESPResSo.
5 *
6 * ESPResSo is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * ESPResSo is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more 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#ifndef UTILS_ENUMERATED_CONTAINER_HPP
21#define UTILS_ENUMERATED_CONTAINER_HPP
22
23/** @file
24 * Keep an enumerated list of T objects, managed by the class.
25 */
26
27#include <cassert>
28#include <cstddef>
29#include <set>
30#include <unordered_map>
31
32namespace Utils {
33
34/**
35 * @brief Container for objects that are identified by a numeric id.
36 *
37 * This class implements a container that holds T instances and references
38 * them by an integral index. New elements get the lowest free index
39 * and indexes are reused. The Container keeps a copy of the objects added.
40 */
41template <class T, typename index_type = int> class NumeratedContainer {
42public:
43 typedef typename std::unordered_map<index_type, T>::iterator iterator;
44 typedef
45 typename std::unordered_map<index_type, T>::const_iterator const_iterator;
46 typedef typename std::unordered_map<index_type, T>::value_type value_type;
47
49 m_free_indices.insert(0);
50 m_free_indices.insert(1);
51 }
52
53 /**
54 * @brief Construct from list of key-value pairs.
55 * The keys have to be unique.
56 */
57 explicit NumeratedContainer(std::initializer_list<value_type> l)
59 for (auto const &e : l) {
60 m_container[e.first] = e.second;
61 /* Remove the index from the index set if it exists. */
62 if (auto it = m_free_indices.find(e.first); it != m_free_indices.end()) {
63 m_free_indices.erase(it);
64 }
65 }
66
67 /* Refill the index set */
68 for (index_type it(0); m_free_indices.size() < 2; ++it) {
69 if (m_container.find(it) == m_container.end()) {
70 m_free_indices.insert(it);
71 }
72 }
73 }
74
75 /**
76 * @brief Copy c into the container.
77 *
78 * Assign a free id to c and copy it into the container.
79 *
80 * @param c The object to add.
81 */
82 index_type add(const T &c) {
83 const index_type ind = get_index();
84 m_container[ind] = c;
85 return ind;
86 }
87
88 /** @overload */
89 index_type add(T &&c) {
90 const index_type ind = get_index();
91 m_container[ind] = std::move(c);
92 return ind;
93 }
94
95 /**
96 * @brief Remove element from container
97 *
98 * Remove element i and add i to the free
99 * indices.
100 *
101 * @param i The object to remove.
102 */
103 void remove(index_type i) {
104 /* Check that the object actually exists */
105 assert(m_container.find(i) != m_container.end());
106
107 m_container.erase(i);
108 m_free_indices.insert(i);
109 }
110
111 /**
112 * @brief Get element from container
113 *
114 * @param i The object to get.
115 * @return Reference to the object with id i.
116 */
117 T &operator[](index_type i) { return m_container.at(i); }
118
119 /**
120 * @brief Get element from container
121 *
122 * @param i The object to get.
123 * @return Reference to the object with id i.
124 */
125 const T &operator[](index_type i) const { return m_container.at(i); }
126
127 /**
128 * @brief Get iterator to beginning of the container.
129 */
130 iterator begin() { return m_container.begin(); }
131
132 /**
133 * @brief Get a const iterator to beginning of the container.
134 */
135 const_iterator begin() const { return m_container.begin(); }
136
137 /**
138 * @brief Get an iterator to end of the container.
139 */
140 iterator end() { return m_container.end(); }
141
142 /**
143 * @brief Get a const iterator to end of the container.
144 */
145 const_iterator end() const { return m_container.end(); }
146
147 /**
148 * @brief find object by id.
149 *
150 * @param id id of the object to find.
151 * @return Iterator to the object if found or end().
152 */
153 iterator find(int id) { return m_container.find(id); }
154
155 /**
156 * @brief find object by id.
157 *
158 * @param id id of the object to find.
159 * @return Iterator to the object if found or end().
160 */
161 const_iterator find(int id) const { return m_container.find(id); }
162
163 std::size_t size() const { return m_container.size(); }
164
165private:
166 /** Data storage */
167 std::unordered_map<index_type, T> m_container;
168 /** Set for free index bookkeeping */
169 std::set<index_type> m_free_indices;
170
171 /**
172 * @brief Get the next free index.
173 *
174 * This function gets the lowest free index by
175 * popping the first element from the ordered set
176 * of free indices.
177 * If there is only 1 or less elements in the free
178 * index set, we reused all indices that were ever
179 * freed and we add a new one at the end of the set.
180 *
181 * @return Free index.
182 */
183 index_type get_index() {
184 /* Get lowest free index */
185 /* If we don't have a free index, sth went wrong. */
186 assert(!m_free_indices.empty());
187 const index_type index = *m_free_indices.begin();
188 /* and remove it from the list */
189 m_free_indices.erase(index);
190
191 /* If there is only on left, it is the highest ever seen, so we can safely
192 * add +1 */
193 if (m_free_indices.size() == 1) {
194 m_free_indices.insert(*(--m_free_indices.end()) + 1);
195 }
196
197 return index;
198 }
199};
200} // namespace Utils
201
202#endif
Container for objects that are identified by a numeric id.
std::unordered_map< index_type, T >::iterator iterator
const_iterator find(int id) const
find object by id.
const T & operator[](index_type i) const
Get element from container.
std::unordered_map< index_type, T >::const_iterator const_iterator
iterator find(int id)
find object by id.
index_type add(const T &c)
Copy c into the container.
const_iterator begin() const
Get a const iterator to beginning of the container.
void remove(index_type i)
Remove element from container.
iterator end()
Get an iterator to end of the container.
const_iterator end() const
Get a const iterator to end of the container.
std::unordered_map< index_type, T >::value_type value_type
index_type add(T &&c)
This is an overloaded member function, provided for convenience. It differs from the above function o...
iterator begin()
Get iterator to beginning of the container.
NumeratedContainer(std::initializer_list< value_type > l)
Construct from list of key-value pairs.
T & operator[](index_type i)
Get element from container.