HashSet.hpp

Go to the documentation of this file.

/*
 * Copyright 2022 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_UTIL_HASHSET_HPP
#define JLM_UTIL_HASHSET_HPP
 
#include <jlm/util/Hash.hpp>
#include <jlm/util/iterator_range.hpp>
 
#include <unordered_set>
 
namespace jlm::util
{
 
template<typename ItemType, typename HashFunctor = Hash<ItemType>>
class HashSet
{
  using InternalSet = std::unordered_set<ItemType, HashFunctor>;
 
public:
  class ItemConstIterator 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 &;
 
  private:
    friend HashSet;
 
    explicit ItemConstIterator(const typename InternalSet::const_iterator & it)
        : It_(it)
    {}
 
  public:
    [[nodiscard]] ItemType *
    Item() const noexcept
    {
      return It_.operator->();
    }
 
    const ItemType &
    operator*() const
    {
      return It_.operator*();
    }
 
    ItemType *
    operator->() const
    {
      return Item();
    }
 
    ItemConstIterator &
    operator++()
    {
      ++It_;
      return *this;
    }
 
    ItemConstIterator
    operator++(int)
    {
      ItemConstIterator tmp = *this;
      ++*this;
      return tmp;
    }
 
    bool
    operator==(const ItemConstIterator & other) const
    {
      return It_ == other.It_;
    }
 
    bool
    operator!=(const ItemConstIterator & other) const
    {
      return !operator==(other);
    }
 
  private:
    typename InternalSet::const_iterator It_;
  };
 
  ~HashSet() noexcept = default;
 
  HashSet() = default;
 
  template<class InputIt>
  HashSet(InputIt begin, InputIt end)
      : Set_(begin, end)
  {}
 
  HashSet(const HashSet & other)
      : Set_(other.Set_)
  {}
 
  HashSet(HashSet && other) noexcept
      : Set_(std::move(other.Set_))
  {}
 
  HashSet(std::initializer_list<ItemType> initializerList)
      : Set_(initializerList)
  {}
 
  template<typename OtherHashFunctor>
  explicit HashSet(const std::unordered_set<ItemType, OtherHashFunctor> & other)
      : Set_(other.begin(), other.end())
  {}
 
  HashSet &
  operator=(const HashSet & other)
  {
    Set_ = other.Set_;
    return *this;
  }
 
  HashSet &
  operator=(HashSet && other) noexcept
  {
    Set_ = std::move(other.Set_);
    return *this;
  }
 
  void
  Clear() noexcept
  {
    Set_.clear();
  }
 
  bool
  Contains(const ItemType & item) const noexcept
  {
    return Set_.find(item) != Set_.end();
  }
 
  bool
  IsSubsetOf(const HashSet<ItemType> & other) const noexcept
  {
    if (Size() > other.Size())
    {
      return false;
    }
 
    for (auto & item : other.Items())
    {
      if (!other.Contains(item))
      {
        return false;
      }
    }
 
    return true;
  }
 
  [[nodiscard]] std::size_t
  Size() const noexcept
  {
    return Set_.size();
  }
 
  [[nodiscard]] bool
  IsEmpty() const noexcept
  {
    return Size() == 0;
  }
 
  bool
  insert(ItemType item)
  {
    auto size = Size();
    Set_.emplace(std::move(item));
    return (size != Size());
  }
 
  [[nodiscard]] IteratorRange<ItemConstIterator>
  Items() const noexcept
  {
    return { ItemConstIterator(Set_.begin()), ItemConstIterator(Set_.end()) };
  }
 
  bool
  UnionWith(const HashSet<ItemType> & other)
  {
    const size_t sizeBefore = Size();
    for (auto & item : other.Items())
      insert(item);
    return sizeBefore != Size();
  }
 
  bool
  UnionWithAndClear(HashSet<ItemType> & other)
  {
    // Make *this the largest of the two sets, to make the union cheaper
    if (Size() < other.Size())
      std::swap(*this, other);
 
    bool result = UnionWith(other);
    other.Clear();
    return result;
  }
 
  void
  IntersectWith(const HashSet<ItemType> & other)
  {
    auto isContained = [&](const ItemType & item)
    {
      return !other.Contains(item);
    };
 
    RemoveWhere(isContained);
  }
 
  void
  IntersectWithAndClear(HashSet<ItemType> & other)
  {
    // Make *this the smallest of the two sets, to make the intersection cheaper
    if (Size() > other.Size())
      std::swap(*this, other);
 
    IntersectWith(other);
    other.Clear();
  }
 
  void
  DifferenceWith(const HashSet<ItemType> & other)
  {
    // If this HashSet is smaller, loop over it and remove elements in other.
    // If other is smaller, loop over it and remove elements from this.
 
    if (Size() <= other.Size())
    {
      // This branch also handles the unlikely case where this and other are the same set.
 
      auto isInOther = [&](const ItemType & item)
      {
        return other.Contains(item);
      };
 
      RemoveWhere(isInOther);
    }
    else
    {
      for (auto & item : other.Set_)
        Remove(item);
    }
  }
 
  bool
  Remove(ItemType item)
  {
    return Set_.erase(item) != 0;
  }
 
  template<typename F>
  size_t
  RemoveWhere(const F & match)
  {
    size_t numRemoved = 0;
    auto it = Set_.begin();
    while (it != Set_.end())
    {
      if (match(*it))
      {
        it = Set_.erase(it);
        numRemoved++;
      }
      else
      {
        it++;
      }
    }
 
    return numRemoved;
  }
 
  ItemConstIterator
  Erase(ItemConstIterator iterator)
  {
    return ItemConstIterator(Set_.erase(iterator.It_));
  }
 
  bool
  operator==(const HashSet<ItemType> & other) const noexcept
  {
    if (Size() != other.Size())
      return false;
 
    for (auto & item : Set_)
      if (!other.Contains(item))
        return false;
 
    return true;
  }
 
  bool
  operator!=(const HashSet<ItemType> & other) const noexcept
  {
    return !operator==(other);
  }
 
private:
  InternalSet Set_;
};
 
}
 
#endif // JLM_UTIL_HASHSET_HPP