diff options
Diffstat (limited to 'src/linkedmap.h')
| -rw-r--r-- | src/linkedmap.h | 267 |
1 files changed, 267 insertions, 0 deletions
diff --git a/src/linkedmap.h b/src/linkedmap.h new file mode 100644 index 0000000..f09b6d8 --- /dev/null +++ b/src/linkedmap.h @@ -0,0 +1,267 @@ +/****************************************************************************** + * + * Copyright (C) 1997-2020 by Dimitri van Heesch. + * + * Permission to use, copy, modify, and distribute this software and its + * documentation under the terms of the GNU General Public License is hereby + * granted. No representations are made about the suitability of this software + * for any purpose. It is provided "as is" without express or implied warranty. + * See the GNU General Public License for more details. + * + * Documents produced by Doxygen are derivative works derived from the + * input used in their production; they are not affected by this license. + * + */ + +#ifndef LINKEDMAP_H +#define LINKEDMAP_H + +#include <unordered_map> +#include <vector> +#include <memory> +#include <string> +#include <algorithm> +#include <cctype> + +//! @brief Container class representing a vector of objects with keys. +//! @details Objects can efficiently be looked up given the key. +//! Objects are owned by the container. +//! When adding objects the order of addition is kept, and used while iterating. +template<class T, class Hash = std::hash<std::string>, + class KeyEqual = std::equal_to<std::string>, + class Map = std::unordered_map<std::string,T*,Hash,KeyEqual > > +class LinkedMap +{ + public: + using Ptr = std::unique_ptr<T>; + using Vec = std::vector<Ptr>; + using iterator = typename Vec::iterator; + using const_iterator = typename Vec::const_iterator; + using reverse_iterator = typename Vec::reverse_iterator; + using const_reverse_iterator = typename Vec::const_reverse_iterator; + + //! Find an object given the key. + //! Returns a pointer to the element if found or nullptr if it is not found. + const T *find(const char *key_) const + { + std::string key(key_ ? key_ : ""); + auto it = m_lookup.find(key); + return it!=m_lookup.end() ? it->second : nullptr; + } + + //! A non-const wrapper for find() const + T* find(const char *key) + { + return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key)); + } + + //! Adds a new object to the ordered vector if it was not added already. + //! Return a non-owning pointer to the newly added object, or to the existing object if + //! it was already inserted before under the given key. + template<class...Args> + T *add(const char *k, Args&&... args) + { + T *result = find(k); + if (result==nullptr) + { + std::string key(k ? k : ""); + Ptr ptr = std::make_unique<T>(key.c_str(),std::forward<Args>(args)...); + result = ptr.get(); + m_lookup.insert({key,result}); + m_entries.push_back(std::move(ptr)); + } + return result; + } + + //! Adds an existing object to the ordered vector (unless another object was already + //! added under the same key). Ownership is transferred. + //! Return a non-owning pointer to the newly added object, or to the existing object if + //! it was already inserted before under the given key. + T *add(const char *k, Ptr &&ptr) + { + T *result = find(k); + if (result==nullptr) + { + std::string key(k ? k : ""); + result = ptr.get(); + m_lookup.insert({key,result}); + m_entries.push_back(std::move(ptr)); + } + return result; + } + + //! Prepends a new object to the ordered vector if it was not added already. + //! Return a non-owning pointer to the newly added object, or to the existing object if + //! it was already inserted before under the given key. + template<class...Args> + T *prepend(const char *k, Args&&... args) + { + T *result = find(k); + if (result==nullptr) + { + std::string key(k ? k : ""); + Ptr ptr = std::make_unique<T>(key.c_str(),std::forward<Args>(args)...); + result = ptr.get(); + m_lookup.insert({key,result}); + m_entries.push_front(std::move(ptr)); + } + return result; + } + + //! Removes an object from the container and deletes it. + //! Returns true if the object was deleted or false it is was not found. + bool del(const char *key_) + { + std::string key(key_ ? key_ : ""); + auto it = m_lookup.find(key); + if (it!=m_lookup.end()) + { + auto vecit = std::find_if(m_entries.begin(),m_entries.end(),[obj=it->second](auto &el) { return el.get()==obj; }); + if (vecit!=m_entries.end()) // should always be true + { + m_entries.erase(vecit); + m_lookup.erase(it); + return true; + } + } + return false; + } + + Ptr &operator[](size_t pos) { return m_entries[pos]; } + const Ptr &operator[](size_t pos) const { return m_entries[pos]; } + iterator begin() { return m_entries.begin(); } + iterator end() { return m_entries.end(); } + const_iterator begin() const { return m_entries.cbegin(); } + const_iterator end() const { return m_entries.cend(); } + reverse_iterator rbegin() { return m_entries.rbegin(); } + reverse_iterator rend() { return m_entries.rend(); } + const_reverse_iterator rbegin() const { return m_entries.crbegin(); } + const_reverse_iterator rend() const { return m_entries.crend(); } + bool empty() const { return m_entries.empty(); } + size_t size() const { return m_entries.size(); } + + void clear() + { + m_entries.clear(); + m_lookup.clear(); + } + + private: + + Map m_lookup; + Vec m_entries; +}; + +//! @brief Container class representing a vector of objects with keys. +//! @details Objects can be efficiently be looked up given the key. +//! Objects are \e not owned by the container, the container will only hold references. +//! When adding objects the order of addition is kept, and used while iterating. +template<class T, class Hash = std::hash<std::string>, + class KeyEqual = std::equal_to<std::string>, + class Map = std::unordered_map<std::string,T*,Hash,KeyEqual > > +class LinkedRefMap +{ + public: + using Ptr = T*; + using Vec = std::vector<Ptr>; + using iterator = typename Vec::iterator; + using const_iterator = typename Vec::const_iterator; + using reverse_iterator = typename Vec::reverse_iterator; + using const_reverse_iterator = typename Vec::const_reverse_iterator; + + //! find an object given the key. + //! Returns a pointer to the object if found or nullptr if it is not found. + const T *find(const char *key_) const + { + std::string key(key_ ? key_ : ""); + auto it = m_lookup.find(key); + return it!=m_lookup.end() ? it->second : nullptr; + } + + //! non-const wrapper for find() const + T* find(const char *key) + { + return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key)); + } + + //! Adds an object reference to the ordered vector if it was not added already. + //! Return true if the reference was added, and false if an object with the same key + //! was already added before + bool add(const char *k, T* obj) + { + if (find(k)==nullptr) // new element + { + std::string key(k ? k : ""); + m_lookup.insert({key,obj}); + m_entries.push_back(obj); + return true; + } + else // already existing, don't add + { + return false; + } + } + + //! Prepends an object reference to the ordered vector if it was not added already. + //! Return true if the reference was added, and false if an object with the same key + //! was already added before + bool prepend(const char *k, T* obj) + { + if (find(k)==nullptr) // new element + { + std::string key(k ? k : ""); + m_lookup.insert({key,obj}); + m_entries.insert(m_entries.begin(),obj); + return true; + } + else // already existing, don't add + { + return false; + } + } + + //! Removes an object from the container and deletes it. + //! Returns true if the object was deleted or false it is was not found. + bool del(const char *key_) + { + std::string key(key_ ? key_ : ""); + auto it = m_lookup.find(key); + if (it!=m_lookup.end()) + { + auto vecit = std::find_if(m_entries.begin(),m_entries.end(),[obj=it->second](auto &el) { return el.get()==obj; }); + if (vecit!=m_entries.end()) // should always be true + { + m_entries.erase(vecit); + m_lookup.erase(it); + return true; + } + } + return false; + } + + Ptr &operator[](size_t pos) { return m_entries[pos]; } + const Ptr &operator[](size_t pos) const { return m_entries[pos]; } + iterator begin() { return m_entries.begin(); } + iterator end() { return m_entries.end(); } + const_iterator begin() const { return m_entries.cbegin(); } + const_iterator end() const { return m_entries.cend(); } + reverse_iterator rbegin() { return m_entries.rbegin(); } + reverse_iterator rend() { return m_entries.rend(); } + const_reverse_iterator rbegin() const { return m_entries.crbegin(); } + const_reverse_iterator rend() const { return m_entries.crend(); } + bool empty() const { return m_entries.empty(); } + size_t size() const { return m_entries.size(); } + + void clear() + { + m_entries.clear(); + m_lookup.clear(); + } + + private: + Map m_lookup; + Vec m_entries; +}; + + +#endif |