BijectiveMap.hpp

Go to the documentation of this file.

/*
 * Copyright 2023 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_UTIL_BIJECTIVE_MAP_HPP
#define JLM_UTIL_BIJECTIVE_MAP_HPP
 
#include <jlm/util/common.hpp>
 
#include <unordered_map>
 
namespace jlm::util
{
template<typename K, typename V>
class BijectiveMap
{
  using ForwardMapType = std::unordered_map<K, V>;
  using ReverseMapType = std::unordered_map<V, K>;
 
public:
  using ItemType = std::pair<const K, V>;
 
  class ConstIterator final
  {
  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = ItemType;
    using difference_type = std::ptrdiff_t;
    using pointer = ItemType *;
    using reference = ItemType &;
 
    friend BijectiveMap;
 
    ConstIterator() = default;
 
    explicit ConstIterator(const typename ForwardMapType::const_iterator & it)
        : It_(it)
    {}
 
    const ItemType &
    operator*() const
    {
      return It_.operator*();
    }
 
    const ItemType *
    operator->() const
    {
      return It_.operator->();
    }
 
    ConstIterator &
    operator++()
    {
      ++It_;
      return *this;
    }
 
    ConstIterator
    operator++(int)
    {
      ConstIterator tmp = *this;
      ++*this;
      return tmp;
    }
 
    bool
    operator==(const ConstIterator & other) const
    {
      return It_ == other.It_;
    }
 
    bool
    operator!=(const ConstIterator & other) const
    {
      return !operator==(other);
    }
 
  private:
    typename ForwardMapType::const_iterator It_;
  };
 
  ~BijectiveMap() noexcept = default;
 
  BijectiveMap() = default;
 
  BijectiveMap(const BijectiveMap & other) = default;
 
  BijectiveMap(BijectiveMap && other) noexcept = default;
 
  template<class InputIt>
  explicit BijectiveMap(InputIt first, InputIt last)
      : ForwardMap_(),
        ReverseMap_()
  {
    for (auto it = first; it != last; ++it)
      InsertOrThrow(it->first, it->second);
  }
 
  BijectiveMap(std::initializer_list<ItemType> init)
      : BijectiveMap(init.begin(), init.end())
  {}
 
  BijectiveMap &
  operator=(const BijectiveMap & other) = default;
 
  BijectiveMap &
  operator=(BijectiveMap && other) = default;
 
  void
  Clear() noexcept
  {
    ForwardMap_.clear();
    ReverseMap_.clear();
  }
 
  [[nodiscard]] std::size_t
  Size() const noexcept
  {
    JLM_ASSERT(ForwardMap_.size() == ReverseMap_.size());
    return ForwardMap_.size();
  }
 
  bool
  Insert(const K & key, const V & value)
  {
    if (HasKey(key) || HasValue(value))
      return false;
 
    ForwardMap_.insert({ key, value });
    ReverseMap_.insert({ value, key });
    return true;
  }
 
  template<typename IteratorType>
  size_t
  InsertPairs(IteratorType begin, IteratorType end)
  {
    static_assert(
        std::is_base_of_v<std::forward_iterator_tag, typename IteratorType::iterator_category>);
 
    size_t inserted = 0;
    while (begin != end)
    {
      if (Insert(begin->first, begin->second))
        inserted++;
      ++begin;
    }
 
    return inserted;
  }
 
  void
  InsertOrThrow(const K & key, const V & value)
  {
    if (!Insert(key, value))
      throw Error("Key or value were already present in the BijectiveMap");
  }
 
  [[nodiscard]] bool
  HasKey(const K & key) const noexcept
  {
    return ForwardMap_.count(key);
  }
 
  [[nodiscard]] bool
  HasValue(const V & value) const noexcept
  {
    return ReverseMap_.count(value);
  }
 
  [[nodiscard]] const V &
  LookupKey(const K & key) const
  {
    auto it = ForwardMap_.find(key);
    if (it == ForwardMap_.end())
      throw Error("Key not found in BijectiveMap");
    return it->second;
  }
 
  [[nodiscard]] const K &
  LookupValue(const V & value) const
  {
    auto it = ReverseMap_.find(value);
    if (it == ReverseMap_.end())
      throw Error("Value not found in BijectiveMap");
    return it->second;
  }
 
  [[nodiscard]] ConstIterator
  begin() const noexcept
  {
    return ConstIterator(ForwardMap_.cbegin());
  }
 
  [[nodiscard]] ConstIterator
  end() const noexcept
  {
    return ConstIterator(ForwardMap_.cend());
  }
 
  ConstIterator
  Erase(ConstIterator it)
  {
    const size_t removed = ReverseMap_.erase(it->second);
    JLM_ASSERT(removed == 1);
    const auto nextForwardIt = ForwardMap_.erase(it.It_);
    return ConstIterator(nextForwardIt);
  }
 
  bool
  RemoveKey(const K & key)
  {
    auto it = ForwardMap_.find(key);
    if (it == ForwardMap_.end())
      return false;
 
    Erase(ConstIterator(it));
    return true;
  }
 
  bool
  RemoveValue(const V & value)
  {
    auto it = ReverseMap_.find(value);
    if (it == ReverseMap_.end())
      return false;
 
    auto removed = ForwardMap_.erase(it->second);
    JLM_ASSERT(removed == 1);
 
    ReverseMap_.erase(it);
    return true;
  }
 
  template<typename F>
  size_t
  RemoveWhere(const F & match)
  {
    size_t removed = 0;
    auto it = begin();
    while (it != end())
    {
      if (match(it->first, it->second))
      {
        it = Erase(it);
        removed++;
      }
      else
      {
        ++it;
      }
    }
    return removed;
  }
 
  template<typename F>
  size_t
  RemoveKeysWhere(const F & match)
  {
    return RemoveWhere(
        [&](const K & key, const V &)
        {
          return match(key);
        });
  }
 
  template<typename F>
  size_t
  RemoveValuesWhere(const F & match)
  {
    return RemoveWhere(
        [&](const K &, const V & value)
        {
          return match(value);
        });
  }
 
  [[nodiscard]] bool
  operator==(const BijectiveMap & other) const noexcept
  {
    // We only need to compare forward maps, as reverse maps are uniquely defined by the forward map
    return ForwardMap_ == other.ForwardMap_;
  }
 
  [[nodiscard]] bool
  operator!=(const BijectiveMap & other) const noexcept
  {
    return !operator==(other);
  }
 
private:
  ForwardMapType ForwardMap_;
  ReverseMapType ReverseMap_;
};
 
}
 
#endif // JLM_UTIL_BIJECTIVE_MAP_HPP