LSSTApplications  18.1.0
LSSTDataManagementBasePackage
GenericMap.h
Go to the documentation of this file.
1 // -*- LSST-C++ -*-
2 /*
3  * This file is part of afw.
4  *
5  * Developed for the LSST Data Management System.
6  * This product includes software developed by the LSST Project
7  * (https://www.lsst.org).
8  * See the COPYRIGHT file at the top-level directory of this distribution
9  * for details of code ownership.
10  *
11  * This program is free software: you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation, either version 3 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program. If not, see <https://www.gnu.org/licenses/>.
23  */
24 
25 #ifndef LSST_AFW_TYPEHANDLING_GENERICMAP_H
26 #define LSST_AFW_TYPEHANDLING_GENERICMAP_H
27 
28 #include <algorithm>
29 #include <cstdint>
30 #include <functional>
31 #include <ostream>
32 #include <memory>
33 #include <sstream>
34 #include <typeinfo>
35 #include <type_traits>
36 #include <unordered_set>
37 #include <vector>
38 
39 #include "boost/core/demangle.hpp"
40 #include "boost/variant.hpp"
41 
42 #include "lsst/pex/exceptions.h"
45 
46 namespace lsst {
47 namespace afw {
48 namespace typehandling {
49 
62 template <typename K, typename V>
63 class Key final {
64 public:
65  using KeyType = K;
66  using ValueType = V;
67 
79  constexpr Key(K id) : id(id) {}
80 
81  Key(Key const&) = default;
82  Key(Key&&) = default;
83  Key& operator=(Key const&) = delete;
84  Key& operator=(Key&&) = delete;
85 
94  constexpr K const& getId() const noexcept { return id; }
95 
104  constexpr bool operator==(Key<K, V> const& other) const noexcept { return this->id == other.id; }
105 
106  template <typename U>
107  constexpr std::enable_if_t<!std::is_same<U, V>::value, bool> operator==(Key<K, U> const&) const noexcept {
108  return false;
109  }
110 
111  template <typename U>
112  constexpr bool operator!=(Key<K, U> const& other) const noexcept {
113  return !(*this == other);
114  }
115 
131  template <typename U>
132  constexpr bool operator<(Key<K, U> const& other) const noexcept {
133  const std::less<K> comparator;
134  return comparator(this->getId(), other.getId());
135  }
136 
138  std::size_t hash_value() const noexcept { return std::hash<K>()(id); }
139 
140 private:
142  K const id;
143 };
144 
160 // template parameters must be reversed for inference to work correctly
161 template <typename V, typename K>
162 constexpr Key<K, V> makeKey(K const& id) {
163  return Key<K, V>(id);
164 }
165 
184 template <typename K, typename V>
185 std::ostream& operator<<(std::ostream& os, Key<K, V> const& key) {
186  static const std::string typeStr = boost::core::demangle(typeid(V).name());
187  static const std::string constStr = std::is_const<V>::value ? " const" : "";
188  static const std::string volatileStr = std::is_volatile<V>::value ? " volatile" : "";
189  os << key.getId() << "<" << typeStr << constStr << volatileStr << ">";
190  return os;
191 }
192 
193 // Test for smart pointers as "any type with an element_type member"
194 // Second template parameter is a dummy to let us do some metaprogramming
195 template <typename, typename = void>
196 constexpr bool IS_SMART_PTR = false;
197 template <typename T>
198 constexpr bool IS_SMART_PTR<T, std::enable_if_t<std::is_object<typename T::element_type>::value>> = true;
199 
228 // TODO: const keys should be possible in C++17 with std::variant
229 template <typename K>
230 class GenericMap {
231 public:
232  using key_type = K;
235 
236  virtual ~GenericMap() noexcept = default;
237 
255  template <typename T, typename std::enable_if_t<!IS_SMART_PTR<T>, int> = 0>
256  T& at(Key<K, T> const& key) {
257  // Both casts are safe; see Effective C++, Item 3
258  return const_cast<T&>(static_cast<const GenericMap&>(*this).at(key));
259  }
260 
261  template <typename T, typename std::enable_if_t<!IS_SMART_PTR<T>, int> = 0>
262  T const& at(Key<K, T> const& key) const {
263  // Delegate to private methods to hide further special-casing of T
264  return _at(key);
265  }
266 
267  template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
269  // Delegate to private methods to hide further special-casing of T
270  return _at(key);
271  }
272 
275  virtual size_type size() const noexcept = 0;
277 
279  virtual bool empty() const noexcept = 0;
280 
288  virtual size_type max_size() const noexcept = 0;
289 
303  template <typename T>
304  size_type count(Key<K, T> const& key) const {
305  return contains(key) ? 1 : 0;
306  }
307 
320  virtual bool contains(K const& key) const = 0;
321 
340  template <typename T>
341  bool contains(Key<K, T> const& key) const {
342  // Delegate to private methods to hide special-casing of T
343  return _contains(key);
344  }
345 
360  virtual std::vector<K> const& keys() const noexcept = 0;
361 
376  virtual bool operator==(GenericMap const& other) const noexcept {
377  auto keys1 = this->keys();
378  auto keys2 = other.keys();
379  if (!std::is_permutation(keys1.begin(), keys1.end(), keys2.begin(), keys2.end())) {
380  return false;
381  }
382  for (K const& key : keys1) {
383  if (this->unsafeLookup(key) != other.unsafeLookup(key)) {
384  return false;
385  }
386  }
387  return true;
388  }
389 
390  bool operator!=(GenericMap const& other) const { return !(*this == other); }
391 
452  template <class Visitor>
453  auto apply(Visitor&& visitor) const {
454  // Delegate to private methods to hide special-casing of Visitor
455  return _apply(visitor);
456  }
457 
474  template <class Visitor>
475  auto apply(Visitor&& visitor) {
476  // Delegate to private methods to hide special-casing of Visitor
477  return _apply(visitor);
478  }
479 
480 private:
481  // Transformations between value/reference/ref-to-const versions of internal variant type, to let
482  // the set of value types supported by GenericMap be defined only once
483  // Icky TMP, but I can't find another way to get at the template arguments for variant :(
484  // Methods have no definition but can't be deleted without breaking type definitions below
485 
487  // may need to use std::reference_wrapper when migrating to std::variant, but it confuses Boost
488  template <typename... Types>
489  static boost::variant<std::add_lvalue_reference_t<Types>...> _typeToRef(
490  boost::variant<Types...> const&) noexcept;
491  template <typename... Types>
492  static boost::variant<std::add_lvalue_reference_t<std::add_const_t<Types>>...> _typeToConstRef(
493  boost::variant<Types...> const&) noexcept;
495 
496 protected:
502  using StorableType = boost::variant<bool, std::int32_t, std::int64_t, float, double, std::string,
504 
511  // this mouthful is shorter than the equivalent expression with result_of
512  using ConstValueReference = decltype(_typeToConstRef(std::declval<StorableType>()));
513  using ValueReference = decltype(_typeToRef(std::declval<StorableType>()));
514 
532  virtual ConstValueReference unsafeLookup(K key) const = 0;
533 
535  ConstValueReference constRef = static_cast<const GenericMap&>(*this).unsafeLookup(key);
536  auto removeConst = [](auto const& value) -> ValueReference {
537  using NonConstRef = std::add_lvalue_reference_t<
538  std::remove_const_t<std::remove_reference_t<decltype(value)>>>;
539  // This cast is safe; see Effective C++, Item 3
540  return const_cast<NonConstRef>(value);
541  };
542  return boost::apply_visitor(removeConst, constRef);
543  }
544 
547 private:
548  // Neither Storable nor shared_ptr<Storable>
549  template <typename T,
550  typename std::enable_if_t<
552  T const& _at(Key<K, T> const& key) const {
553  static_assert(!std::is_const<T>::value,
554  "Due to implementation constraints, const keys are not supported.");
555  try {
556  auto foo = unsafeLookup(key.getId());
557  return boost::get<T const&>(foo);
558  } catch (boost::bad_get const&) {
559  std::stringstream message;
560  message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
562  }
563  }
564 
565  // Storable and its subclasses
566  template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
567  T const& _at(Key<K, T> const& key) const {
568  static_assert(!std::is_const<T>::value,
569  "Due to implementation constraints, const keys are not supported.");
570  try {
571  auto foo = unsafeLookup(key.getId());
572  // Don't use pointer-based get, because it won't work after migrating to std::variant
573  Storable const& value = boost::get<PolymorphicValue const&>(foo);
574  T const* typedPointer = dynamic_cast<T const*>(&value);
575  if (typedPointer != nullptr) {
576  return *typedPointer;
577  } else {
578  std::stringstream message;
579  message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
581  }
582  } catch (boost::bad_get const&) {
583  std::stringstream message;
584  message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
586  }
587  }
588 
589  // shared_ptr<Storable>
590  template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
591  std::shared_ptr<T> _at(Key<K, std::shared_ptr<T>> const& key) const {
592  static_assert(!std::is_const<T>::value,
593  "Due to implementation constraints, const keys are not supported.");
594  try {
595  auto foo = unsafeLookup(key.getId());
596  auto pointer = boost::get<std::shared_ptr<Storable> const&>(foo);
597  std::shared_ptr<T> typedPointer = std::dynamic_pointer_cast<T>(pointer);
598  // shared_ptr can be empty without being null. dynamic_pointer_cast
599  // only promises result of failed cast is empty, so test for that
600  if (typedPointer.use_count() > 0) {
601  return typedPointer;
602  } else {
603  std::stringstream message;
604  message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
606  }
607  } catch (boost::bad_get const&) {
608  std::stringstream message;
609  message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
611  }
612  }
613 
614  // Neither Storable nor shared_ptr<Storable>
615  template <typename T,
616  typename std::enable_if_t<
618  bool _contains(Key<K, T> const& key) const {
619  // Avoid actually getting and casting an object, if at all possible
620  if (!contains(key.getId())) {
621  return false;
622  }
623 
624  auto foo = unsafeLookup(key.getId());
625  // boost::variant has no equivalent to std::holds_alternative
626  try {
627  boost::get<T const&>(foo);
628  return true;
629  } catch (boost::bad_get const&) {
630  return false;
631  }
632  }
633 
634  // Storable and its subclasses
635  template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
636  bool _contains(Key<K, T> const& key) const {
637  // Avoid actually getting and casting an object, if at all possible
638  if (!contains(key.getId())) {
639  return false;
640  }
641 
642  auto foo = unsafeLookup(key.getId());
643  try {
644  // Don't use pointer-based get, because it won't work after migrating to std::variant
645  Storable const& value = boost::get<PolymorphicValue const&>(foo);
646  auto asT = dynamic_cast<T const*>(&value);
647  return asT != nullptr;
648  } catch (boost::bad_get const&) {
649  return false;
650  }
651  }
652 
653  // shared_ptr<Storable>
654  template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
655  bool _contains(Key<K, std::shared_ptr<T>> const& key) const {
656  // Avoid actually getting and casting an object, if at all possible
657  if (!contains(key.getId())) {
658  return false;
659  }
660 
661  auto foo = unsafeLookup(key.getId());
662  try {
663  auto pointer = boost::get<std::shared_ptr<Storable> const&>(foo);
664  std::shared_ptr<T> typedPointer = std::dynamic_pointer_cast<T>(pointer);
665  // shared_ptr can be empty without being null. dynamic_pointer_cast
666  // only promises result of failed cast is empty, so test for that
667  return typedPointer.use_count() > 0;
668  } catch (boost::bad_get const&) {
669  return false;
670  }
671  }
672 
673  // Type alias to properly handle Visitor output
674  // Assume that each operator() has the same return type; variant will enforce it
676  template <class Visitor>
677  using _VisitorResult = std::result_of_t<Visitor && (K&&, bool&)>;
679 
680  // No return value, const GenericMap
681  template <class Visitor, typename std::enable_if_t<std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
682  void _apply(Visitor&& visitor) const {
683  for (K const& key : keys()) {
684  boost::variant<K> varKey = key;
685  boost::apply_visitor(visitor, varKey, unsafeLookup(key));
686  }
687  }
688 
689  // Return value, const GenericMap
690  template <class Visitor,
691  typename std::enable_if_t<!std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
692  auto _apply(Visitor&& visitor) const {
694  results.reserve(size());
695 
696  for (K const& key : keys()) {
697  boost::variant<K> varKey = key;
698  results.emplace_back(boost::apply_visitor(visitor, varKey, unsafeLookup(key)));
699  }
700  return results;
701  }
702 
703  // No return value, non-const GenericMap
704  template <class Visitor, typename std::enable_if_t<std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
705  void _apply(Visitor&& visitor) {
706  for (K const& key : keys()) {
707  boost::variant<K> varKey = key;
708  // Boost gets confused if we pass it a temporary variant
709  ValueReference ref = unsafeLookup(key);
710  boost::apply_visitor(visitor, varKey, ref);
711  }
712  }
713 
714  // Return value, non-const GenericMap
715  template <class Visitor,
716  typename std::enable_if_t<!std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
717  auto _apply(Visitor&& visitor) {
719  results.reserve(size());
720 
721  for (K const& key : keys()) {
722  boost::variant<K> varKey = key;
723  // Boost gets confused if we pass it a temporary variant
724  ValueReference ref = unsafeLookup(key);
725  results.emplace_back(boost::apply_visitor(visitor, varKey, ref));
726  }
727  return results;
728  }
729 };
730 
741 template <typename K>
742 class MutableGenericMap : public GenericMap<K> {
743 protected:
744  using typename GenericMap<K>::StorableType;
745 
746 public:
747  virtual ~MutableGenericMap() noexcept = default;
748 
754  virtual void clear() noexcept = 0;
755 
774  template <typename T>
775  bool insert(Key<K, T> const& key, T const& value) {
776  if (this->contains(key.getId())) {
777  return false;
778  }
779 
780  return unsafeInsert(key.getId(), StorableType(value));
781  }
782 
798  template <typename T>
799  std::pair<Key<K, T>, bool> insert(K const& key, T const& value) {
800  auto strongKey = makeKey<T>(key);
801  // Construct return value in advance, so that exception from copying/moving Key is atomic
802  auto result = make_pair(strongKey, false);
803  result.second = insert(strongKey, value);
804  return result;
805  }
806 
820  template <typename T>
821  bool erase(Key<K, T> const& key) {
822  if (this->contains(key)) {
823  return unsafeErase(key.getId());
824  } else {
825  return false;
826  }
827  }
828 
829 protected:
842  virtual bool unsafeInsert(K key, StorableType&& value) = 0;
843 
853  virtual bool unsafeErase(K key) = 0;
854 };
855 
856 } // namespace typehandling
857 } // namespace afw
858 } // namespace lsst
859 
860 namespace std {
861 template <typename K, typename V>
862 struct hash<typename lsst::afw::typehandling::Key<K, V>> {
865  size_t operator()(argument_type const& obj) const noexcept { return obj.hash_value(); }
866 };
867 } // namespace std
868 
869 #endif
T is_permutation(T... args)
auto apply(Visitor &&visitor)
Apply a modifying operation to each key-value pair in the map.
Definition: GenericMap.h:475
size_type count(Key< K, T > const &key) const
Return the number of elements mapped to the specified key.
Definition: GenericMap.h:304
bool operator!=(GenericMap const &other) const
Test for map equality.
Definition: GenericMap.h:390
bool erase(Key< K, T > const &key)
Remove the mapping for a key from this map, if it exists.
Definition: GenericMap.h:821
bool contains(VertexIterator const begin, VertexIterator const end, UnitVector3d const &v)
Container that passes Storable objects by value while preserving type.
std::shared_ptr< T > at(Key< K, std::shared_ptr< T >> const &key) const
Return a reference to the mapped value of the element with key equal to key.
Definition: GenericMap.h:268
T & at(Key< K, T > const &key)
Return a reference to the mapped value of the element with key equal to key.
Definition: GenericMap.h:256
Interface supporting iteration over heterogenous containers.
Definition: Storable.h:56
constexpr Key< K, V > makeKey(K const &id)
Factory function for Key, to enable type parameter inference.
Definition: GenericMap.h:162
py::object result
Definition: schema.cc:418
size_t operator()(argument_type const &obj) const noexcept
Definition: GenericMap.h:865
decltype(_typeToConstRef(std::declval< StorableType >())) ConstValueReference
A type-agnostic reference to the value stored inside the map.
Definition: GenericMap.h:512
STL namespace.
constexpr bool operator==(Key< K, V > const &other) const noexcept
Test for key equality.
Definition: GenericMap.h:104
bool contains(Key< K, T > const &key) const
Return true if this map contains a mapping for the specified key.
Definition: GenericMap.h:341
T const & at(Key< K, T > const &key) const
Return a reference to the mapped value of the element with key equal to key.
Definition: GenericMap.h:262
boost::variant< bool, std::int32_t, std::int64_t, float, double, std::string, PolymorphicValue, std::shared_ptr< Storable > > StorableType
The types that can be stored in a map.
Definition: GenericMap.h:503
STL class.
Key for type-safe lookup in a GenericMap.
Definition: GenericMap.h:63
virtual ConstValueReference unsafeLookup(K key) const =0
Return a reference to the mapped value of the element with key equal to key.
A base class for image defects.
auto apply(Visitor &&visitor) const
Apply an operation to each key-value pair in the map.
Definition: GenericMap.h:453
T str(T... args)
constexpr Key(K id)
Construct a new key.
Definition: GenericMap.h:79
ValueReference unsafeLookup(K key)
Return a reference to the mapped value of the element with key equal to key.
Definition: GenericMap.h:534
typename lsst::afw::typehandling::Key< K, V > argument_type
Definition: GenericMap.h:863
T dynamic_pointer_cast(T... args)
constexpr bool operator!=(Key< K, U > const &other) const noexcept
Test for key equality.
Definition: GenericMap.h:112
std::size_t hash_value() const noexcept
Return a hash of this object.
Definition: GenericMap.h:138
#define LSST_EXCEPT(type,...)
Create an exception with a given type.
Definition: Exception.h:48
Reports attempts to access elements outside a valid range of indices.
Definition: Runtime.h:89
virtual bool operator==(GenericMap const &other) const noexcept
Test for map equality.
Definition: GenericMap.h:376
Key< U > key
Definition: Schema.cc:281
decltype(_typeToRef(std::declval< StorableType >())) ValueReference
A type-agnostic reference to the value stored inside the map.
Definition: GenericMap.h:513
std::pair< Key< K, T >, bool > insert(K const &key, T const &value)
Insert an element into the map, if the map doesn&#39;t already contain a mapping with a conflicting key...
Definition: GenericMap.h:799
constexpr bool IS_SMART_PTR
Definition: GenericMap.h:196
ItemVariant const * other
Definition: Schema.cc:56
bool insert(Key< K, T > const &key, T const &value)
Insert an element into the map, if the map doesn&#39;t already contain a mapping with the same or a confl...
Definition: GenericMap.h:775
Interface for a GenericMap that allows element addition and removal.
Definition: GenericMap.h:742
constexpr K const & getId() const noexcept
Return the identifier of this field.
Definition: GenericMap.h:94
STL class.
Interface for a heterogeneous map.
Definition: GenericMap.h:230
Key & operator=(Key const &)=delete
std::ostream * os
Definition: Schema.cc:746
T reserve(T... args)
T emplace_back(T... args)