text: #pragma once
  
  #include "fwd.h"
  
  #include <util/generic/utility.h>
  #include <util/generic/vector.h>
  #include <util/generic/mapfindptr.h>
  
  #include <util/str_stl.h>
  #include <util/ysaveload.h>
  
  /*
   * There are 2 classes in this file:
   *   - TDenseHash - analog of THashMap
   *   - TDenseHashSet - analog of THashSet
   */
  
  /*
   * Implements dense-hash, in some circumstances it is a lot (2x) faster than THashMap.
   * We support only adding new elements.
   * TKey value equal to EmptyMarker (by default, it is TKey())
   * can not be inserted into hash - it is used as marker of empty element.
   * TValue type must be default constructible
   */
  
  template <class TKey,
            class TValue,
            class TKeyHash,
            size_t MaxLoadFactor,
            size_t LogInitSize>
  class TDenseHash : public TMapOps<TDenseHash<TKey, TValue, TKeyHash, MaxLoadFactor, LogInitSize>> {
  private:
      template <class THash, class TVal>
      class TIteratorBase {
          friend class TDenseHash;
  
          template <class THash2, class TVal2>
          friend class TIteratorBase;
  
          THash* Hash;
          size_t Idx;
  
          // used only to implement end()
          TIteratorBase(THash* hash, size_t initIdx)
              : Hash(hash)
              , Idx(initIdx)
          {
          }
  
      public:
          TIteratorBase(THash& hash)
              : Hash(&hash)
              , Idx(0)
          {
              if (Hash->EmptyMarker == Hash->Buckets[Idx].first) {
                  Next();
              }
          }
  
          template <class THash2, class TVal2>
          TIteratorBase(const TIteratorBase<THash2, TVal2>& it)
              : Hash(it.Hash)
              , Idx(it.Idx)
          {
          }
  
          static TIteratorBase CreateEmpty() {
              return TIteratorBase(nullptr, 0);
          }
  
          TIteratorBase& operator=(const TIteratorBase& rhs) {
              Hash = rhs.Hash;
              Idx = rhs.Idx;
              return *this;
          }
  
          void Next() {
              ++Idx;
              while (Idx < Hash->Buckets.size() && Hash->EmptyMarker == Hash->Buckets[Idx].first) {
                  ++Idx;
              }
          }
  
          TIteratorBase& operator++() {
              Next();
              return *this;
          }
  
          TVal& operator*() {
              return Hash->Buckets[Idx];
          }
  
          TVal* operator->() {
              return &Hash->Buckets[Idx];
          }
  
          const TVal* operator->() const {
              return &Hash->Buckets[Idx];
          }
  
          THash* GetHash() {
              return Hash;
          }
  
          bool operator==(const TIteratorBase& rhs) const {
              Y_ASSERT(Hash == rhs.Hash);
              return Idx == rhs.Idx;
          }
  
          bool operator!=(const TIteratorBase& rhs) const {
              return !(*this == rhs);
          }
      };
  
  public:
      using key_type = TKey;
      using mapped_type = TValue;
      using value_type = std::pair<const key_type, mapped_type>;
      using size_type = std::size_t;
      using difference_type = std::ptrdiff_t;
      using hasher = TKeyHash;
      using key_equal = std::equal_to<key_type>; // TODO(tender-bum): template argument
      // using allocator_type = ...
      using reference = value_type&;
      using const_reference = const value_type&;
      using pointer = value_type*; // TODO(tender-bum): std::allocator_traits<Alloc>::pointer;
      using const_pointer = const value_type*; // TODO(tender-bum):
                                               // std::allocator_traits<Alloc>::const_pointer;
      using iterator = TIteratorBase<TDenseHash, value_type>;
      using const_iterator = TIteratorBase<const TDenseHash, const value_type>;
  
  public:
      TDenseHash(const key_type& emptyMarker = key_type{}, size_type initSize = 0)
          : EmptyMarker(emptyMarker)
      {
          MakeEmpty(initSize);
      }
  
      TDenseHash(const TDenseHash&) = default;
      TDenseHash(TDenseHash&&) = default;
  
      TDenseHash& operator=(const TDenseHash& rhs) {
          TDenseHash tmp{ rhs };
          return *this = std::move(tmp);
      }
  
      TDenseHash& operator=(TDenseHash&&) = default;
  
      friend bool operator==(const TDenseHash& lhs, const TDenseHash& rhs) {
          return lhs.Size() == rhs.Size() &&
              AllOf(lhs, [&rhs](const auto& v) {
                  auto it = rhs.find(v.first);
                  return it != rhs.end() && *it == v;
              });
      }
  
      void Clear() {
          for (auto& bucket : Buckets) {
              if (bucket.first != EmptyMarker) {
                  SetValue(bucket, EmptyMarker, mapped_type{});
              }
          }
          NumFilled = 0;
      }
  
      void MakeEmpty(size_type initSize = 0) {
          if (!initSize) {
              initSize = 1 << LogInitSize;
          } else {
              initSize = FastClp2(initSize);
          }
          BucketMask = initSize - 1;
          NumFilled = 0;
          TVector<value_type> tmp;
          for (size_type i = 0; i < initSize; ++i) {
              tmp.emplace_back(EmptyMarker, mapped_type{});
          }
          tmp.swap(Buckets);
          GrowThreshold = Max<size_type>(1, initSize * MaxLoadFactor / 100) - 1;
      }
  
      template <class K>
      bool Has(const K& key) const {
          return ProcessKey<bool>(
              key,
              [](size_type) { return true; },
              [](size_type) { return false; });
      }
  
      size_type Capacity() const {
          return Buckets.capacity();
      }
  
      bool Empty() const {
          return Size() == 0;
      }
  
      size_type Size() const {
          return NumFilled;
      }
  
      template <size_type maxFillPercents, size_type logInitSize>
      void Swap(TDenseHash<key_type, mapped_type, hasher, maxFillPercents, logInitSize>& other) {
          Buckets.swap(other.Buckets);
          DoSwap(BucketMask, other.BucketMask);
          DoSwap(NumFilled, other.NumFilled);
          DoSwap(GrowThreshold, other.GrowThreshold);
          DoSwap(EmptyMarker, other.EmptyMarker);
      }
  
      void Save(IOutputStream* s) const {
          // TODO(tender-bum): make SaveLoad great again
          ::SaveMany(s, BucketMask, NumFilled, GrowThreshold);
          // We need to do so because Buckets may be serialized as a pod-array
          // that doesn't correspond to the previous behaviour
          ::SaveSize(s, Buckets.size());
          for (const auto& b : Buckets) {
              ::Save(s, b.first);
              ::Save(s, b.second);
          }
          mapped_type defaultValue{};
          ::SaveMany(s, EmptyMarker, defaultValue);
      }
  
      void Load(IInputStream* s) {
          // TODO(tender-bum): make SaveLoad great again
          ::LoadMany(s, BucketMask, NumFilled, GrowThreshold);
          // We need to do so because we can't load const fields
          struct TPairMimic {
              key_type First;
              mapped_type Second;
              Y_SAVELOAD_DEFINE(First, Second);
          };
          TVector<TPairMimic> tmp;
          ::Load(s, tmp);
          Buckets.clear();
          for (auto& v : tmp) {
              Buckets.emplace_back(std::move(v.First), std::move(v.Second));
          }
          ::Load(s, EmptyMarker);
          mapped_type defaultValue;
          ::Load(s, defaultValue);
      }
  
  public:
      iterator begin() {
          return iterator(*this);
      }
  
      iterator end() {
          return iterator(this, Buckets.size());
      }
  
      const_iterator begin() const {
          return const_iterator(*this);
      }
  
      const_iterator end() const {
          return const_iterator(this, Buckets.size());
      }
  
      template <class K>
      iterator find(const K& key) {
          return ProcessKey<iterator>(
              key,
              [&](size_type idx) { return iterator(this, idx); },
              [&](size_type) { return end(); });
      }
  
      template <class K>
      const_iterator find(const K& key) const {
          return ProcessKey<const_iterator>(
              key,
              [&](size_type idx) { return const_iterator(this, idx); },
              [&](size_type) { return end(); });
      }
  
      template <class K>
      const TValue& at(const K& key) const {
          return ProcessKey<const TValue&>(
              key,
              [&](size_type idx) -> const TValue& { return Buckets[idx].second; },
              [&](size_type) -> const TValue& { throw std::out_of_range("TDenseHash: missing key"); });
      }
  
      template <class K>
      TValue& at(const K& key) {
          return ProcessKey<TValue&>(
              key,
              [&](size_type idx) -> TValue& { return Buckets[idx].second; },
              [&](size_type) -> TValue& { throw std::out_of_range("TDenseHash: missing key"); });
      }
  
      bool Grow(size_type to = 0, bool force = false) {
          if (!to) {
              to = Buckets.size() * 2;
          } else {
              to = FastClp2(to);
              if (to <= Buckets.size() && !force) {
                  return false;
              }
          }
          TVector<value_type> oldBuckets(Reserve(to));
          for (size_type i = 0; i < to; ++i) {
              oldBuckets.emplace_back(EmptyMarker, mapped_type{});
          }
          oldBuckets.swap(Buckets);
  
          BucketMask = Buckets.size() - 1;
          GrowThreshold = Max<size_type>(1, Buckets.size() * (MaxLoadFactor / 100.f)) - 1;
  
          for (auto& item : oldBuckets) {
              if (EmptyMarker != item.first) {
                  SetValue(FindProperBucket(item.first), std::move(item));
              }
          }
          return true;
      }
  
      // We need this overload because we want to optimize insertion when somebody inserts value_type.
      // So we don't need to extract the key.
      // This overload also allows brace enclosed initializer to be inserted.
      std::pair<iterator, bool> insert(const value_type& t) {
          size_type hs = hasher{}(t.first);
          auto p = GetBucketInfo(hs & BucketMask, t.first);
          if (p.second) {
              ++NumFilled;
              if (NumFilled >= GrowThreshold) {
                  Grow();
                  p.first = FindProperBucket(hs & BucketMask, t.first);
              }
              SetValue(p.first, t);
              return { iterator{ this, p.first }, true };
          }
          return { iterator{ this, p.first }, false };
      }
  
      // We need this overload because we want to optimize insertion when somebody inserts value_type.
      // So we don't need to extract the key.
      // This overload also allows brace enclosed initializer to be inserted.
      std::pair<iterator, bool> insert(value_type&& t) {
          size_type hs = hasher{}(t.first);
          auto p = GetBucketInfo(hs & BucketMask, t.first);
          if (p.second) {
              ++NumFilled;
              if (NumFilled >= GrowThreshold) {
                  Grow();
                  p.first = FindProperBucket(hs & BucketMask, t.first);
              }
              SetValue(p.first, std::move(t));
              return { iterator{ this, p.first }, true };
          }
          return { iterator{ this, p.first }, false };
      }
  
      // Standart integration. This overload is equivalent to emplace(std::forward<P>(p)).
      template <class P>
      std::enable_if_t<!std::is_same<std::decay_t<P>, value_type>::value,
      std::pair<iterator, bool>> insert(P&& p) {
          return emplace(std::forward<P>(p));
      }
  
      // Not really emplace because we need to know the key anyway. So we need to construct value_type.
      template <class... Args>
      std::pair<iterator, bool> emplace(Args&&... args) {
          return insert(value_type{ std::forward<Args>(args)... });
      }
  
      template <class K>
      mapped_type& operator[](K&& key) {
          size_type hs = hasher{}(key);
          auto p = GetBucketInfo(hs & BucketMask, key);
          if (p.second) {
              ++NumFilled;
              if (NumFilled >= GrowThreshold) {
                  Grow();
                  p.first = FindProperBucket(hs & BucketMask, key);
              }
              SetValue(p.first, std::forward<K>(key), mapped_type{});
          }
          return Buckets[p.first].second;
      }
  
  private:
      key_type EmptyMarker;
      size_type NumFilled;
      size_type BucketMask;
      size_type GrowThreshold;
      TVector<value_type> Buckets;
  
  private:
      // Tricky way to set value of type with const fields
      template <class... Args>
      void SetValue(value_type& bucket, Args&&... args) {
          bucket.~value_type();
          new (&bucket) value_type(std::forward<Args>(args)...);
      }
  
      template <class... Args>
      void SetValue(size_type idx, Args&&... args) {
          SetValue(Buckets[idx], std::forward<Args>(args)...);
      }
  
      template <class K>
      size_type FindProperBucket(size_type idx, const K& key) const {
          return ProcessIndex<size_type>(
              idx,
              key,
              [](size_type idx) { return idx; },
              [](size_type idx) { return idx; });
      }
  
      template <class K>
      size_type FindProperBucket(const K& key) const {
          return FindProperBucket(hasher{}(key) & BucketMask, key);
      }
  
      // { idx, is_empty }
      template <class K>
      std::pair<size_type, bool> GetBucketInfo(size_type idx, const K& key) const {
          return ProcessIndex<std::pair<size_type, bool>>(
              idx,
              key,
              [](size_type idx) { return std::make_pair(idx, false); },
              [](size_type idx) { return std::make_pair(idx, true); });
      }
  
      template <class R, class K, class OnFound, class OnEmpty>
      R ProcessIndex(size_type idx, const K& key, OnFound f0, OnEmpty f1) const {
          for (size_type numProbes = 1; EmptyMarker != Buckets[idx].first; ++numProbes) {
              if (Buckets[idx].first == key) {
                  return f0(idx);
              }
              idx = (idx + numProbes) & BucketMask;
          }
          return f1(idx);
      }
  
      template <class R, class K, class OnFound, class OnEmpty>
      R ProcessKey(const K& key, OnFound&& f0, OnEmpty&& f1) const {
          return ProcessIndex<R>(
              hasher{}(key) & BucketMask, key, std::forward<OnFound>(f0), std::forward<OnEmpty>(f1));
      }
  };
  
  template <class TKey,
            class TKeyHash,
            size_t MaxLoadFactor,
            size_t LogInitSize>
  class TDenseHashSet {
  public:
      TDenseHashSet(const TKey& emptyMarker = TKey(), size_t initSize = 0)
          : EmptyMarker(emptyMarker)
      {
          MakeEmpty(initSize);
      }
  
      void Clear() {
          size_t currentSize = Buckets.size();
          Buckets.clear();
          Buckets.resize(currentSize, EmptyMarker);
          NumFilled = 0;
      }
  
      void MakeEmpty(size_t initSize = 0) {
          if (!initSize) {
              initSize = 1 << LogInitSize;
          } else {
              initSize = FastClp2(initSize);
          }
          BucketMask = initSize - 1;
          NumFilled = 0;
          TVector<TKey>(initSize, EmptyMarker).swap(Buckets);
          GrowThreshold = Max<size_t>(1, initSize * MaxLoadFactor / 100) - 1;
      }
  
      template <class K>
      bool Has(const K& key) const {
          return Buckets[FindBucket(key)] != EmptyMarker;
      }
  
      // gets existing item or inserts new
      template <class K>
      bool Insert(const K& key) {
          bool inserted = InsertNoGrow(key);
          if (inserted) {
              MaybeGrow();
          }
          return inserted;
      }
  
      size_t Capacity() const {
          return Buckets.capacity();
      }
  
      bool Empty() const {
          return Size() == 0;
      }
  
      size_t Size() const {
          return NumFilled;
      }
  
      template <size_t maxFillPercents, size_t logInitSize>
      void Swap(TDenseHashSet<TKey, TKeyHash, maxFillPercents, logInitSize>& other) {
          Buckets.swap(other.Buckets);
          DoSwap(BucketMask, other.BucketMask);
          DoSwap(NumFilled, other.NumFilled);
          DoSwap(GrowThreshold, other.GrowThreshold);
          DoSwap(EmptyMarker, other.EmptyMarker);
      }
  
      Y_SAVELOAD_DEFINE(BucketMask, NumFilled, GrowThreshold, Buckets, EmptyMarker);
  
  private:
      template <class THash>
      class TIteratorBase {
          friend class TDenseHashSet;
  
          THash* Hash;
          size_t Idx;
  
          // used only to implement end()
          TIteratorBase(THash* hash, size_t initIdx)
              : Hash(hash)
              , Idx(initIdx)
          {
          }
  
      public:
          TIteratorBase(THash& hash)
              : Hash(&hash)
              , Idx(0)
          {
              if (Hash->Buckets[Idx] == Hash->EmptyMarker) {
                  Next();
              }
          }
  
          void Next() {
              ++Idx;
              while (Idx < Hash->Buckets.size() && Hash->Buckets[Idx] == Hash->EmptyMarker) {
                  ++Idx;
              }
          }
  
          TIteratorBase& operator++() {
              Next();
              return *this;
          }
  
          bool Initialized() const {
              return Hash != nullptr;
          }
  
          bool Ok() const {
              return Idx < Hash->Buckets.size();
          }
  
          const TKey& operator*() const {
              return Key();
          }
  
          const TKey& Key() const {
              return Hash->Buckets[Idx];
          }
  
          bool operator==(const TIteratorBase& rhs) const {
              Y_ASSERT(Hash == rhs.Hash);
              return Idx == rhs.Idx;
          }
  
          bool operator!=(const TIteratorBase& rhs) const {
              return !(*this == rhs);
          }
      };
  
  public:
      typedef TIteratorBase<const TDenseHashSet> TConstIterator;
  
      TConstIterator begin() const {
          return TConstIterator(*this);
      }
  
      TConstIterator end() const {
          return TConstIterator(this, Buckets.size());
      }
  
  private:
      size_t BucketMask;
      size_t NumFilled;
      size_t GrowThreshold;
      TVector<TKey> Buckets;
  
      TKey EmptyMarker;
  
      template <class K>
      bool InsertNoGrow(const K& key) {
          size_t idx = FindBucket(key);
          if (Buckets[idx] == EmptyMarker) {
              ++NumFilled;
              Buckets[idx] = key;
              return true;
          }
          return false;
      }
  
      bool MaybeGrow() {
          if (NumFilled < GrowThreshold) {
              return false;
          }
  
          TVector<TKey> oldBuckets(Buckets.size() * 2, EmptyMarker);
          oldBuckets.swap(Buckets);
  
          BucketMask = Buckets.size() - 1;
          GrowThreshold = Max<size_t>(1, Buckets.size() * (MaxLoadFactor / 100.f)) - 1;
  
          NumFilled = 0;
          for (const TKey& key : oldBuckets) {
              if (key != EmptyMarker) {
                  InsertNoGrow(key);
              }
          }
  
          return true;
      }
  
      template <class K>
      size_t FindBucket(const K& key) const {
          size_t idx = TKeyHash()(key) & BucketMask;
          for (size_t numProbes = 1; Buckets[idx] != EmptyMarker; ++numProbes) {
              if (Buckets[idx] == key) {
                  return idx;
              }
              idx = (idx + numProbes) & BucketMask;
          }
          return idx;
      }
  };
  