IndexMap.hpp

Go to the documentation of this file.

#ifndef AI_TOOLBOX_UTILS_INDEX_MAP_HEADER_FILE
#define AI_TOOLBOX_UTILS_INDEX_MAP_HEADER_FILE
 
#include <AIToolbox/Types.hpp>
 
#include <utility>
#include <type_traits>
 
namespace AIToolbox {
    template <typename IdsIterator, typename Container>
    class IndexMapIterator {
        public:
            using iterator_category = typename IdsIterator::iterator_category;
            using value_type = typename Container::value_type;
            using pointer = value_type *;
            using reference = value_type &;
            using difference_type = typename IdsIterator::difference_type;
 
            IndexMapIterator() : items_(nullptr) {}
 
            IndexMapIterator(IdsIterator id, Container & items) :
                    currentId_(id), items_(&items) {}
 
            auto toContainerId() const { return *currentId_; }
 
            // Input iterator methods
            auto& operator*()  { return (*items_)[toContainerId()]; }
            const auto& operator*() const { return (*items_)[toContainerId()]; }
 
            auto  operator->() { return &(operator*()); }
            auto  operator->() const { return &(operator*()); }
 
            bool operator==(IndexMapIterator other) const {
                // Note that comparing against different containers is undefined.
                return currentId_ == other.currentId_;
            }
            bool operator!=(IndexMapIterator other) const { return !(*this == other); }
 
            auto& operator++() {
                ++currentId_;
                return *this;
            }
 
            auto operator++(int) {
                auto tmp = *this;
                ++currentId_;
                return tmp;
            }
 
            // Bidirectional iterator methods
            template <typename U = iterator_category,
                      typename = std::enable_if_t<std::is_same_v<U, std::bidirectional_iterator_tag> ||
                                                  std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator--() {
                --currentId_;
                return *this;
            }
 
            template <typename U = iterator_category,
                      typename = std::enable_if_t<std::is_same_v<U, std::bidirectional_iterator_tag> ||
                                                  std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator--(int) {
                auto tmp = *this;
                --currentId_;
                return tmp;
            }
 
            // Random access iterator methods
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator+(difference_type diff) const {
                auto retval = IndexMapIterator(currentId_, *items_);
                retval.currentId_ += diff;
                return retval;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator+=(difference_type diff) {
                currentId_ += diff;
                return *this;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator-(difference_type diff) const {
                auto retval = IndexMapIterator(currentId_, *items_);
                retval.currentId_ -= diff;
                return *this;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator-=(difference_type diff) {
                currentId_ -= diff;
                return *this;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            auto operator-(IndexMapIterator other) const {
                return currentId_ - other.currentId_;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            bool operator<(IndexMapIterator other) const {
                return currentId_ < other.currentId_;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            bool operator>(IndexMapIterator other) const {
                return currentId_ > other.currentId_;
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            bool operator<=(IndexMapIterator other) const {
                return !(currentId_ > other.currentId_ );
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            bool operator>=(IndexMapIterator other) const {
                return !(currentId_ < other.currentId_ );
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            auto & operator[](difference_type diff) {
                return (*items_)[*(currentId_ + diff)];
            }
 
            template <typename U = iterator_category, typename = std::enable_if_t<std::is_same_v<U, std::random_access_iterator_tag>>>
            const auto & operator[](difference_type diff) const {
                return (*items_)[*(currentId_ + diff)];
            }
 
        private:
            IdsIterator currentId_;
            Container * items_;
    };
 
    template <typename IdsContainer, typename Container>
    class IndexMap {
        public:
            static constexpr bool OwnsIds = !std::is_pointer_v<IdsContainer>;
            using IdsStorage  = std::conditional_t<OwnsIds,
                                             IdsContainer,
                                             const std::remove_pointer_t<IdsContainer> &
                                >;
 
            using value_type     = typename Container::value_type;
 
            using iterator       = IndexMapIterator<decltype(std::declval<IdsStorage>().begin()),  Container>;
            using const_iterator = IndexMapIterator<decltype(std::declval<IdsStorage>().cbegin()), const Container>;
 
            template <bool Tmp = OwnsIds, std::enable_if_t<Tmp, int> = 0>
            IndexMap(IdsContainer ids, Container & items) : ids_(std::move(ids)), items_(items) {}
 
            template <bool Tmp = OwnsIds, std::enable_if_t<!Tmp, int> = 0>
            IndexMap(IdsContainer ids, Container & items) : ids_(*ids), items_(items) {}
 
            template <bool Tmp = OwnsIds, std::enable_if_t<Tmp, int> = 0>
            void sort() {
                std::sort(std::begin(ids_), std::end(ids_), [this](auto lhs, auto rhs) {
                    return items_[lhs] < items_[rhs];
                });
            }
 
            auto begin() { return iterator(ids_.begin(), items_); }
 
            auto begin() const { return cbegin(); }
 
            auto cbegin() const { return const_iterator(ids_.cbegin(), items_); }
 
            auto end() { return iterator(ids_.end(), items_); };
 
            auto end() const { return cend(); }
 
            auto cend() const { return const_iterator(ids_.cend(), items_); }
 
            auto size() const { return ids_.size(); }
 
        private:
            friend iterator;
            friend const_iterator;
 
            // Const reference if non-owning, const value otherwise.
            IdsStorage ids_;
            Container & items_;
    };
 
    template <class T, class Container>
    IndexMap(std::initializer_list<T> i, Container c) -> IndexMap<std::vector<T>, Container>;
 
    // This is to stop clang++ complaints
    template <typename IdsContainer, typename Container>
    IndexMap(IdsContainer, Container &) -> IndexMap<IdsContainer, Container>;
 
    template <typename IdsContainer, typename Container>
    class IndexSkipMapIterator {
        public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = typename Container::value_type;
            using size_type = typename Container::size_type;
            using pointer = value_type *;
            using reference = value_type &;
            using difference_type = std::ptrdiff_t;
 
            IndexSkipMapIterator(size_type start, const IdsContainer & ids, Container & items) :
                    currentId_(start), currentSkipId_(0), ids_(ids), items_(items)
            {
                // Skip initial unwanted elements
                skip();
            }
 
            auto& operator*()  { return items_[toContainerId()]; }
            const auto& operator*() const { return items_[toContainerId()]; }
 
            auto  operator->() { return &(operator*()); }
            auto  operator->() const { return &(operator*()); }
 
            auto toContainerId() const { return currentId_; }
 
            auto& operator++() {
                ++currentId_;
                skip();
                return *this;
            }
 
            bool operator==(const IndexSkipMapIterator & other) const {
                return (&(items_) == &(other.items_)) &&
                       (&(ids_) == &(other.ids_)) &&
                       (currentId_ == other.currentId_);
            }
            bool operator!=(const IndexSkipMapIterator & other) const { return !(*this == other); }
 
        private:
            void skip() {
                while (currentId_ < items_.size() &&
                       currentSkipId_ < ids_.size() &&
                       currentId_ == ids_[currentSkipId_])
                {
                    ++currentId_;
                    ++currentSkipId_;
                }
            }
 
            size_type currentId_;
            typename IdsContainer::size_type currentSkipId_;
            const IdsContainer & ids_;
            Container & items_;
    };
 
    template <typename IdsContainer, typename Container>
    class IndexSkipMap {
        public:
            static constexpr bool OwnsIds = !std::is_pointer_v<IdsContainer>;
            using IdsStorage  = std::conditional_t<OwnsIds,
                                             const IdsContainer,
                                             const std::remove_pointer_t<IdsContainer> &
                                >;
 
            using value_type     = typename Container::value_type;
 
            using iterator       = IndexSkipMapIterator<std::remove_reference_t<IdsStorage>, Container>;
            using const_iterator = IndexSkipMapIterator<std::remove_reference_t<IdsStorage>, const Container>;
 
            template <bool Tmp = OwnsIds, std::enable_if_t<Tmp, int> = 0>
            IndexSkipMap(IdsContainer ids, Container & items) : ids_(std::move(ids)), items_(items) {}
 
            template <bool Tmp = OwnsIds, std::enable_if_t<!Tmp, int> = 0>
            IndexSkipMap(IdsContainer ids, Container & items) : ids_(*ids), items_(items) {}
 
            auto begin() { return iterator(0, ids_, items_); }
 
            auto begin() const { return cbegin(); }
 
            auto cbegin() const { return const_iterator(0, ids_, items_); }
 
            auto end() { return iterator(items_.size(), ids_, items_); };
 
            auto end() const { return cend(); }
 
            auto cend() const { return const_iterator(items_.size(), ids_, items_); }
 
            auto size() const { return ids_.size(); }
 
        private:
            friend iterator;
            friend const_iterator;
 
            // Const reference if non-owning, const value otherwise.
            IdsStorage ids_;
            Container & items_;
    };
 
    template<class T, class Container>
    IndexSkipMap(std::initializer_list<T> i, Container c) -> IndexSkipMap<std::vector<T>, Container>;
 
    // This is to stop clang++ complaints
    template <typename IdsContainer, typename Container>
    IndexSkipMap(IdsContainer, Container &) -> IndexSkipMap<IdsContainer, Container>;
}
 
#endif