doxygen
linkedmap.h
1 /******************************************************************************
2  *
3  * Copyright (C) 1997-2020 by Dimitri van Heesch.
4  *
5  * Permission to use, copy, modify, and distribute this software and its
6  * documentation under the terms of the GNU General Public License is hereby
7  * granted. No representations are made about the suitability of this software
8  * for any purpose. It is provided "as is" without express or implied warranty.
9  * See the GNU General Public License for more details.
10  *
11  * Documents produced by Doxygen are derivative works derived from the
12  * input used in their production; they are not affected by this license.
13  *
14  */
15 
16 #ifndef LINKEDMAP_H
17 #define LINKEDMAP_H
18 
19 #include <unordered_map>
20 #include <vector>
21 #include <memory>
22 #include <string>
23 #include <algorithm>
24 #include <cctype>
25 
26 #include "qcstring.h"
27 
32 template<class T, class Hash = std::hash<std::string>,
33  class KeyEqual = std::equal_to<std::string>,
34  class Map = std::unordered_map<std::string,T*,Hash,KeyEqual > >
35 class LinkedMap
36 {
37  public:
38  using Ptr = std::unique_ptr<T>;
39  using Vec = std::vector<Ptr>;
40  using iterator = typename Vec::iterator;
41  using const_iterator = typename Vec::const_iterator;
42  using reverse_iterator = typename Vec::reverse_iterator;
43  using const_reverse_iterator = typename Vec::const_reverse_iterator;
44 
47  const T *find(const std::string &key) const
48  {
49  auto it = m_lookup.find(key);
50  return it!=m_lookup.end() ? it->second : nullptr;
51  }
52 
55  const T *find(const QCString &key) const
56  {
57  auto it = m_lookup.find(key.str());
58  return it!=m_lookup.end() ? it->second : nullptr;
59  }
60 
63  const T *find(const char *key) const
64  {
65  return find(std::string(key ? key : ""));
66  }
67 
69  T* find(const char *key)
70  {
71  return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key));
72  }
73 
75  T* find(const QCString &key)
76  {
77  return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key));
78  }
79 
81  T* find(const std::string &key)
82  {
83  return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key));
84  }
85 
89  template<class...Args>
90  T *add(const char *k, Args&&... args)
91  {
92  T *result = find(k);
93  if (result==nullptr)
94  {
95  std::string key(k ? k : "");
96  Ptr ptr = std::make_unique<T>(QCString(k),std::forward<Args>(args)...);
97  result = ptr.get();
98  m_lookup.insert({key,result});
99  m_entries.push_back(std::move(ptr));
100  }
101  return result;
102  }
103 
104  template<class...Args>
105  T *add(const QCString &k, Args&&... args)
106  {
107  std::string key = k.str();
108  T *result = find(key);
109  if (result==nullptr)
110  {
111  Ptr ptr = std::make_unique<T>(k,std::forward<Args>(args)...);
112  result = ptr.get();
113  m_lookup.insert({key,result});
114  m_entries.push_back(std::move(ptr));
115  }
116  return result;
117  }
118 
123  T *add(const char *k, Ptr &&ptr)
124  {
125  T *result = find(k);
126  if (result==nullptr)
127  {
128  std::string key(k ? k : "");
129  result = ptr.get();
130  m_lookup.insert({key,result});
131  m_entries.push_back(std::move(ptr));
132  }
133  return result;
134  }
135 
136  T *add(const QCString &k, Ptr &&ptr)
137  {
138  std::string key = k.str();
139  T *result = find(key);
140  if (result==nullptr)
141  {
142  result = ptr.get();
143  m_lookup.insert({key,result});
144  m_entries.push_back(std::move(ptr));
145  }
146  return result;
147  }
148 
152  template<class...Args>
153  T *prepend(const char *k, Args&&... args)
154  {
155  T *result = find(k);
156  if (result==nullptr)
157  {
158  std::string key(k ? k : "");
159  Ptr ptr = std::make_unique<T>(key.c_str(),std::forward<Args>(args)...);
160  result = ptr.get();
161  m_lookup.insert({key,result});
162  m_entries.push_front(std::move(ptr));
163  }
164  return result;
165  }
166 
167  template<class...Args>
168  T *prepend(const QCString &key, Args&&... args)
169  {
170  T *result = find(key);
171  if (result==nullptr)
172  {
173  Ptr ptr = std::make_unique<T>(key,std::forward<Args>(args)...);
174  result = ptr.get();
175  m_lookup.insert({key.str(),result});
176  m_entries.push_front(std::move(ptr));
177  }
178  return result;
179  }
180 
183  bool del(const QCString &key)
184  {
185  auto it = m_lookup.find(key.str());
186  if (it!=m_lookup.end())
187  {
188  auto vecit = std::find_if(m_entries.begin(),m_entries.end(),[obj=it->second](auto &el) { return el.get()==obj; });
189  if (vecit!=m_entries.end()) // should always be true
190  {
191  m_entries.erase(vecit);
192  m_lookup.erase(it);
193  return true;
194  }
195  }
196  return false;
197  }
198 
199  Ptr &operator[](size_t pos) { return m_entries[pos]; }
200  const Ptr &operator[](size_t pos) const { return m_entries[pos]; }
201  iterator begin() { return m_entries.begin(); }
202  iterator end() { return m_entries.end(); }
203  const_iterator begin() const { return m_entries.cbegin(); }
204  const_iterator end() const { return m_entries.cend(); }
205  reverse_iterator rbegin() { return m_entries.rbegin(); }
206  reverse_iterator rend() { return m_entries.rend(); }
207  const_reverse_iterator rbegin() const { return m_entries.crbegin(); }
208  const_reverse_iterator rend() const { return m_entries.crend(); }
209  bool empty() const { return m_entries.empty(); }
210  size_t size() const { return m_entries.size(); }
211 
212  void clear()
213  {
214  m_entries.clear();
215  m_lookup.clear();
216  }
217 
218  private:
219 
220  Map m_lookup;
221  Vec m_entries;
222 };
223 
228 template<class T, class Hash = std::hash<std::string>,
229  class KeyEqual = std::equal_to<std::string>,
230  class Map = std::unordered_map<std::string,T*,Hash,KeyEqual > >
232 {
233  public:
234  using Ptr = T*;
235  using Vec = std::vector<Ptr>;
236  using iterator = typename Vec::iterator;
237  using const_iterator = typename Vec::const_iterator;
238  using reverse_iterator = typename Vec::reverse_iterator;
239  using const_reverse_iterator = typename Vec::const_reverse_iterator;
240 
243  const T *find(const std::string &key) const
244  {
245  auto it = m_lookup.find(key);
246  return it!=m_lookup.end() ? it->second : nullptr;
247  }
248 
251  const T *find(const QCString &key) const
252  {
253  auto it = m_lookup.find(key.str());
254  return it!=m_lookup.end() ? it->second : nullptr;
255  }
256 
259  const T *find(const char *key) const
260  {
261  return find(std::string(key ? key : ""));
262  }
263 
265  T* find(const char *key)
266  {
267  return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key));
268  }
269 
270  T* find(const QCString &key)
271  {
272  return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key));
273  }
274 
276  T* find(const std::string &key)
277  {
278  return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key));
279  }
280 
284  bool add(const char *k, T* obj)
285  {
286  if (find(k)==nullptr) // new element
287  {
288  std::string key(k ? k : "");
289  m_lookup.insert({key,obj});
290  m_entries.push_back(obj);
291  return true;
292  }
293  else // already existing, don't add
294  {
295  return false;
296  }
297  }
298 
299  bool add(const QCString &k, T* obj)
300  {
301  std::string key = k.str();
302  if (find(key)==nullptr) // new element
303  {
304  m_lookup.insert({key,obj});
305  m_entries.push_back(obj);
306  return true;
307  }
308  else // already existing, don't add
309  {
310  return false;
311  }
312  }
313 
317  bool prepend(const char *k, T* obj)
318  {
319  if (find(k)==nullptr) // new element
320  {
321  std::string key(k ? k : "");
322  m_lookup.insert({key,obj});
323  m_entries.insert(m_entries.begin(),obj);
324  return true;
325  }
326  else // already existing, don't add
327  {
328  return false;
329  }
330  }
331 
332  bool prepend(const QCString &key, T* obj)
333  {
334  if (find(key)==nullptr) // new element
335  {
336  m_lookup.insert({key.str(),obj});
337  m_entries.insert(m_entries.begin(),obj);
338  return true;
339  }
340  else // already existing, don't add
341  {
342  return false;
343  }
344  }
345 
348  bool del(const QCString &key)
349  {
350  auto it = m_lookup.find(key.str());
351  if (it!=m_lookup.end())
352  {
353  auto vecit = std::find_if(m_entries.begin(),m_entries.end(),[obj=it->second](auto &el) { return el.get()==obj; });
354  if (vecit!=m_entries.end()) // should always be true
355  {
356  m_entries.erase(vecit);
357  m_lookup.erase(it);
358  return true;
359  }
360  }
361  return false;
362  }
363 
364  Ptr &operator[](size_t pos) { return m_entries[pos]; }
365  const Ptr &operator[](size_t pos) const { return m_entries[pos]; }
366  iterator begin() { return m_entries.begin(); }
367  iterator end() { return m_entries.end(); }
368  const_iterator begin() const { return m_entries.cbegin(); }
369  const_iterator end() const { return m_entries.cend(); }
370  reverse_iterator rbegin() { return m_entries.rbegin(); }
371  reverse_iterator rend() { return m_entries.rend(); }
372  const_reverse_iterator rbegin() const { return m_entries.crbegin(); }
373  const_reverse_iterator rend() const { return m_entries.crend(); }
374  bool empty() const { return m_entries.empty(); }
375  size_t size() const { return m_entries.size(); }
376 
377  void clear()
378  {
379  m_entries.clear();
380  m_lookup.clear();
381  }
382 
383  private:
384  Map m_lookup;
385  Vec m_entries;
386 };
387 
388 
389 #endif
T * find(const char *key)
non-const wrapper for find() const
Definition: linkedmap.h:265
const T * find(const std::string &key) const
Find an object given the key.
Definition: linkedmap.h:47
T * find(const std::string &key)
non-const wrapper for find() const
Definition: linkedmap.h:276
bool prepend(const char *k, T *obj)
Prepends an object reference to the ordered vector if it was not added already.
Definition: linkedmap.h:317
T * add(const char *k, Ptr &&ptr)
Adds an existing object to the ordered vector (unless another object was already added under the same...
Definition: linkedmap.h:123
const T * find(const std::string &key) const
find an object given the key.
Definition: linkedmap.h:243
T * find(const char *key)
A non-const wrapper for find() const.
Definition: linkedmap.h:69
const T * find(const char *key) const
find an object given the key.
Definition: linkedmap.h:259
T * add(const char *k, Args &&... args)
Adds a new object to the ordered vector if it was not added already.
Definition: linkedmap.h:90
Definition: conceptdef.h:22
T * prepend(const char *k, Args &&... args)
Prepends a new object to the ordered vector if it was not added already.
Definition: linkedmap.h:153
Container class representing a vector of objects with keys.
Definition: linkedmap.h:35
const T * find(const char *key) const
Find an object given the key.
Definition: linkedmap.h:63
bool add(const char *k, T *obj)
Adds an object reference to the ordered vector if it was not added already.
Definition: linkedmap.h:284
Container class representing a vector of objects with keys.
Definition: linkedmap.h:231
bool del(const QCString &key)
Removes an object from the container and deletes it.
Definition: linkedmap.h:183
const T * find(const QCString &key) const
find an object given the key.
Definition: linkedmap.h:251
T * find(const std::string &key)
A non-const wrapper for find() const.
Definition: linkedmap.h:81
bool del(const QCString &key)
Removes an object from the container and deletes it.
Definition: linkedmap.h:348
This is an alternative implementation of QCString.
Definition: qcstring.h:108
const T * find(const QCString &key) const
Find an object given the key.
Definition: linkedmap.h:55
T * find(const QCString &key)
A non-const wrapper for find() const.
Definition: linkedmap.h:75