tpl_flat_map.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef TPL_FLAT_MAP_H
#define TPL_FLAT_MAP_H
 
#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <utility>
 
#include <ah-errors.H>
#include <ahFunction.H>
#include <htlist.H>
#include <tpl_memArray.H>
#include <tpl_sort_utils.H>
 
namespace Aleph {
 
template <typename Key, typename T, class Compare = Aleph::less<Key>>
class FlatMap
{
  MemArray<Key> keys_;
  MemArray<T> vals_;
  Compare cmp_;
 
  // Index of the first key not less than k (lower bound position).
  size_t lower_idx(const Key &k) const
  {
    size_t lo = 0, hi = keys_.size();
    while (lo < hi)
      {
        const size_t mid = lo + ((hi - lo) >> 1);
        if (cmp_(keys_(mid), k))
          lo = mid + 1;
        else
          hi = mid;
      }
    return lo;
  }
 
  // Index of the first key greater than k (upper bound position).
  size_t upper_idx(const Key &k) const
  {
    size_t lo = 0, hi = keys_.size();
    while (lo < hi)
      {
        const size_t mid = lo + ((hi - lo) >> 1);
        if (not cmp_(k, keys_(mid)))
          lo = mid + 1;
        else
          hi = mid;
      }
    return lo;
  }
 
  // True if pos holds a key equivalent to k. Assumes pos == lower_idx(k).
  bool match_at(size_t pos, const Key &k) const
  {
    return pos < keys_.size() and not cmp_(k, keys_(pos));
  }
 
  // Opens one slot at pos in both arrays. reserve() is invoked before any
  // logical size change, so allocation failures preserve the map's logical
  // contents even though one backing array may already have grown.
  void make_room(const size_t pos)
  {
    if (keys_.size() == keys_.capacity())
      keys_.reserve(keys_.capacity() << 1);
    if (vals_.size() == vals_.capacity())
      vals_.reserve(vals_.capacity() << 1);
    keys_.putn(1);
    vals_.putn(1);
    Key *kp = keys_.get_ptr();
    T *vp = vals_.get_ptr();
    for (size_t i = keys_.size() - 1; i > pos; --i)
      {
        kp[i] = std::move(kp[i - 1]);
        vp[i] = std::move(vp[i - 1]);
      }
  }
 
  // Removes the slot at pos from both arrays. Failed shrinking
  // reallocations are ignored: the logical removal always succeeds.
  void remove_at(const size_t pos)
  {
    Key *kp = keys_.get_ptr();
    T *vp = vals_.get_ptr();
    const size_t last = keys_.size() - 1;
    for (size_t i = pos; i < last; ++i)
      {
        kp[i] = std::move(kp[i + 1]);
        vp[i] = std::move(vp[i + 1]);
      }
    try
      {
        (void) keys_.get();
      }
    catch (const std::bad_alloc &)
      { /* shrink failed; logical removal already done */
      }
    try
      {
        (void) vals_.get();
      }
    catch (const std::bad_alloc &)
      { /* shrink failed; logical removal already done */
      }
  }
 
  // Sorts freshly loaded parallel arrays by key and drops duplicate keys,
  // keeping the first occurrence of each equivalence class.
  void sort_and_unique()
  {
    const size_t m = keys_.size();
    MemArray<std::pair<Key, T>> tmp(m);
    Key *kp = keys_.get_ptr();
    T *vp = vals_.get_ptr();
    for (size_t i = 0; i < m; ++i)
      tmp.put(std::pair<Key, T>(std::move(kp[i]), std::move(vp[i])));
 
    std::pair<Key, T> *tp = tmp.get_ptr();
    timsort(tp, m, [this](const auto &a, const auto &b)
      {
        return cmp_(a.first, b.first);
      });
 
    size_t out = 0;
    for (size_t i = 0; i < m; ++i)
      if (out == 0 or cmp_(kp[out - 1], tp[i].first))
        {
          kp[out] = std::move(tp[i].first);
          vp[out] = std::move(tp[i].second);
          ++out;
        }
    const size_t excess = m - out;
    if (excess > 0)
      {
        try { (void) keys_.get(excess); } catch (const std::bad_alloc &)
          { /* shrink failed */ }
        try { (void) vals_.get(excess); } catch (const std::bad_alloc &)
          { /* shrink failed */ }
      }
  }
 
public:
  using Item_Type = std::pair<Key, T>;   
  using Key_Type = Key;                  
  using key_type = Key;                  
  using mapped_type = T;                 
  using value_type = std::pair<Key, T>;  
  using key_compare = Compare;           
  using size_type = size_t;              
 
  template <bool IsConst>
  class basic_iterator
  {
    using VPtr = std::conditional_t<IsConst, const T *, T *>;
 
    const Key *k_ = nullptr;
    VPtr v_ = nullptr;
 
  public:
    struct reference
    {
      const Key &first;                                    
      std::conditional_t<IsConst, const T &, T &> second;  
    };
 
    struct pointer
    {
      reference ref;  
      reference *operator ->() noexcept
      {
        return &ref;
      }
    };
 
    using iterator_category = std::random_access_iterator_tag;  
    using value_type = std::pair<Key, T>;                       
    using difference_type = std::ptrdiff_t;                     
 
    basic_iterator() = default;
 
    basic_iterator(const Key *k, VPtr v) noexcept : k_(k), v_(v) {}
 
    template <bool B> requires (IsConst and not B)
    basic_iterator(const basic_iterator<B> &it) noexcept : k_(it.key_ptr()), v_(it.val_ptr())
    {}
 
    const Key *key_ptr() const noexcept
    {
      return k_;
    }
 
    VPtr val_ptr() const noexcept
    {
      return v_;
    }
 
    reference operator * () const noexcept
    {
      return {*k_, *v_};
    }
 
    pointer operator ->() const noexcept
    {
      return {{*k_, *v_}};
    }
 
    reference operator [] (difference_type i) const noexcept
    {
      return {*(k_ + i), *(v_ + i)};
    }
 
    basic_iterator &operator ++ () noexcept
    {
      ++k_;
      ++v_;
      return *this;
    }
 
    basic_iterator operator ++ (int) noexcept
    {
      basic_iterator ret = *this;
      ++*this;
      return ret;
    }
 
    basic_iterator &operator -- () noexcept
    {
      --k_;
      --v_;
      return *this;
    }
 
    basic_iterator operator -- (int) noexcept
    {
      basic_iterator ret = *this;
      --*this;
      return ret;
    }
 
    basic_iterator &operator += (difference_type i) noexcept
    {
      k_ += i;
      v_ += i;
      return *this;
    }
 
    basic_iterator &operator -= (difference_type i) noexcept
    {
      return *this += -i;
    }
 
    basic_iterator operator + (difference_type i) const noexcept
    {
      basic_iterator ret = *this;
      return ret += i;
    }
 
    basic_iterator operator - (difference_type i) const noexcept
    {
      basic_iterator ret = *this;
      return ret -= i;
    }
 
    difference_type operator - (const basic_iterator &it) const noexcept
    {
      return k_ - it.key_ptr();
    }
 
    bool operator == (const basic_iterator &it) const noexcept
    {
      return k_ == it.key_ptr();
    }
 
    bool operator != (const basic_iterator &it) const noexcept
    {
      return k_ != it.key_ptr();
    }
 
    bool operator < (const basic_iterator &it) const noexcept
    {
      return k_ < it.key_ptr();
    }
 
    bool operator <= (const basic_iterator &it) const noexcept
    {
      return k_ <= it.key_ptr();
    }
 
    bool operator > (const basic_iterator &it) const noexcept
    {
      return k_ > it.key_ptr();
    }
 
    bool operator >= (const basic_iterator &it) const noexcept
    {
      return k_ >= it.key_ptr();
    }
  };
 
  using iterator = basic_iterator<false>;       
  using const_iterator = basic_iterator<true>;  
 
  explicit FlatMap(size_t cap = MemArray<Key>::Min_Dim) : keys_(cap), vals_(cap) {}
 
  explicit FlatMap(const Compare &cmp, size_t cap = MemArray<Key>::Min_Dim)
    : keys_(cap), vals_(cap), cmp_(cmp)
  {}
 
  template <class It>
    // Mirrors the loop below instead of std::input_iterator: this map's own
    // iterators yield a proxy with no common reference with std::pair, so
    // they fail std::indirectly_readable while working fine here.
    requires requires(It first, It last, MemArray<Key> & ks, MemArray<T> & vs,
                      const std::remove_reference_t<std::iter_reference_t<It>> & p)
      {
        static_cast<bool>(first != last);
        ++first;
        ks.put(p.first);
        vs.put(p.second);
      }
  FlatMap(It first, It last, const Compare &cmp = Compare())
    : keys_(MemArray<Key>::Min_Dim), vals_(MemArray<T>::Min_Dim), cmp_(cmp)
  {
    for (; first != last; ++first)
      {
        const auto &p = *first;
        keys_.put(p.first);
        vals_.put(p.second);
      }
    sort_and_unique();
  }
 
  FlatMap(std::initializer_list<std::pair<Key, T>> l, const Compare &cmp = Compare())
    : FlatMap(l.begin(), l.end(), cmp)
  {}
 
  FlatMap(const FlatMap &) = default;
 
  FlatMap(FlatMap &&) noexcept = default;
 
  FlatMap &operator = (const FlatMap &) = default;
 
  FlatMap &operator = (FlatMap &&) noexcept = default;
 
  ~FlatMap() = default;
 
  void swap(FlatMap &m) noexcept(std::is_nothrow_swappable_v<Compare>)
  {
    keys_.swap(m.keys_);
    vals_.swap(m.vals_);
    std::swap(cmp_, m.cmp_);
  }
 
  // -- capacity -------------------------------------------------------------
 
  [[nodiscard]] size_t size() const noexcept
  {
    return keys_.size();
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return keys_.is_empty();
  }
 
  [[nodiscard]] size_t capacity() const noexcept
  {
    return keys_.capacity();
  }
 
  void reserve(size_t cap)
  {
    keys_.reserve(cap);
    vals_.reserve(cap);
  }
 
  void empty() noexcept
  {
    keys_.empty();
    vals_.empty();
  }
 
  void clear() noexcept
  {
    empty();
  }
 
  // -- lookup ---------------------------------------------------------------
 
  iterator find(const Key &k)
  {
    const size_t pos = lower_idx(k);
    return match_at(pos, k) ? begin() + pos : end();
  }
 
  const_iterator find(const Key &k) const
  {
    const size_t pos = lower_idx(k);
    return match_at(pos, k) ? begin() + pos : end();
  }
 
  [[nodiscard]] bool contains(const Key &k) const
  {
    return match_at(lower_idx(k), k);
  }
 
  [[nodiscard]] size_t count(const Key &k) const
  {
    return contains(k) ? 1 : 0;
  }
 
  iterator lower_bound(const Key &k)
  {
    return begin() + lower_idx(k);
  }
 
  const_iterator lower_bound(const Key &k) const
  {
    return begin() + lower_idx(k);
  }
 
  iterator upper_bound(const Key &k)
  {
    return begin() + upper_idx(k);
  }
 
  const_iterator upper_bound(const Key &k) const
  {
    return begin() + upper_idx(k);
  }
 
  std::pair<iterator, iterator> equal_range(const Key &k)
  {
    return {lower_bound(k), upper_bound(k)};
  }
 
  std::pair<const_iterator, const_iterator> equal_range(const Key &k) const
  {
    return {lower_bound(k), upper_bound(k)};
  }
 
  T &at(const Key &k)
  {
    const size_t pos = lower_idx(k);
    ah_out_of_range_error_if(not match_at(pos, k)) << "FlatMap::at(): key not found";
    return vals_(pos);
  }
 
  const T &at(const Key &k) const
  {
    const size_t pos = lower_idx(k);
    ah_out_of_range_error_if(not match_at(pos, k)) << "FlatMap::at(): key not found";
    return vals_(pos);
  }
 
  T &operator [] (const Key &k)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      return vals_(pos);
    make_room(pos);
    keys_.get_ptr()[pos] = k;
    vals_.get_ptr()[pos] = T();
    return vals_(pos);
  }
 
  T &operator [] (Key &&k)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      return vals_(pos);
    make_room(pos);
    keys_.get_ptr()[pos] = std::move(k);
    vals_.get_ptr()[pos] = T();
    return vals_(pos);
  }
 
  // -- positional access ----------------------------------------------------
 
  const Key &nth_key(size_t i) const
  {
    return keys_[i];
  }
 
  T &nth_value(size_t i)
  {
    return vals_[i];
  }
 
  const T &nth_value(size_t i) const
  {
    return vals_[i];
  }
 
  // -- modifiers ------------------------------------------------------------
 
  std::pair<iterator, bool> insert(const Key &k, const T &v)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      return {begin() + pos, false};
    make_room(pos);
    keys_.get_ptr()[pos] = k;
    vals_.get_ptr()[pos] = v;
    return {begin() + pos, true};
  }
 
  std::pair<iterator, bool> insert(Key &&k, T &&v)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      return {begin() + pos, false};
    make_room(pos);
    keys_.get_ptr()[pos] = std::move(k);
    vals_.get_ptr()[pos] = std::move(v);
    return {begin() + pos, true};
  }
 
  std::pair<iterator, bool> insert(const std::pair<Key, T> &p)
  {
    return insert(p.first, p.second);
  }
 
  std::pair<iterator, bool> insert(std::pair<Key, T> &&p)
  {
    return insert(std::move(p.first), std::move(p.second));
  }
 
  std::pair<iterator, bool> insert_or_assign(const Key &k, const T &v)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      {
        vals_(pos) = v;
        return {begin() + pos, false};
      }
    make_room(pos);
    keys_.get_ptr()[pos] = k;
    vals_.get_ptr()[pos] = v;
    return {begin() + pos, true};
  }
 
  std::pair<iterator, bool> insert_or_assign(Key &&k, T &&v)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      {
        vals_(pos) = std::move(v);
        return {begin() + pos, false};
      }
    make_room(pos);
    keys_.get_ptr()[pos] = std::move(k);
    vals_.get_ptr()[pos] = std::move(v);
    return {begin() + pos, true};
  }
 
  template <class... KArgs>
  std::pair<iterator, bool> emplace(KArgs &&...kargs)
  {
    return insert(Key(std::forward<KArgs>(kargs)...), T());
  }
 
  size_t erase(const Key &k)
  {
    const size_t pos = lower_idx(k);
    if (not match_at(pos, k))
      return 0;
    remove_at(pos);
    return 1;
  }
 
  iterator erase(const_iterator it)
  {
    const size_t pos = it.key_ptr() - keys_.get_ptr();
    ah_out_of_range_error_if(pos >= size()) << "FlatMap::erase(): iterator out of range";
    remove_at(pos);
    return begin() + pos;
  }
 
  // -- iteration ------------------------------------------------------------
 
  iterator begin() noexcept
  {
    return iterator(keys_.get_ptr(), vals_.get_ptr());
  }
 
  iterator end() noexcept
  {
    return iterator(keys_.get_ptr() + size(), vals_.get_ptr() + size());
  }
 
  const_iterator begin() const noexcept
  {
    return const_iterator(keys_.get_ptr(), vals_.get_ptr());
  }
 
  const_iterator end() const noexcept
  {
    return const_iterator(keys_.get_ptr() + size(), vals_.get_ptr() + size());
  }
 
  const_iterator cbegin() const noexcept
  {
    return begin();
  }
 
  const_iterator cend() const noexcept
  {
    return end();
  }
 
  const Key *keys_data() const noexcept
  {
    return keys_.get_ptr();
  }
 
  T *values_data() noexcept
  {
    return vals_.get_ptr();
  }
 
  const T *values_data() const noexcept
  {
    return vals_.get_ptr();
  }
 
  DynList<Key> keys() const
  {
    DynList<Key> ret;
    const Key *p = keys_.get_ptr();
    for (size_t i = 0; i < size(); ++i)
      ret.append(p[i]);
    return ret;
  }
 
  DynList<T> values() const
  {
    DynList<T> ret;
    const T *p = vals_.get_ptr();
    for (size_t i = 0; i < size(); ++i)
      ret.append(p[i]);
    return ret;
  }
 
  template <class Operation>
  bool traverse(Operation operation)
  {
    const Key *kp = keys_.get_ptr();
    T *vp = vals_.get_ptr();
    const size_t m = size();
    for (size_t i = 0; i < m; ++i)
      if (not operation(kp[i], vp[i]))
        return false;
    return true;
  }
 
  template <class Operation>
  bool traverse(Operation operation) const
  {
    const Key *kp = keys_.get_ptr();
    const T *vp = vals_.get_ptr();
    const size_t m = size();
    for (size_t i = 0; i < m; ++i)
      if (not operation(kp[i], vp[i]))
        return false;
    return true;
  }
 
  // -- comparison -----------------------------------------------------------
 
  bool operator == (const FlatMap &m) const
  {
    return size() == m.size() and
      std::equal(keys_.get_ptr(), keys_.get_ptr() + size(), m.keys_.get_ptr()) and
      std::equal(vals_.get_ptr(), vals_.get_ptr() + size(), m.vals_.get_ptr());
  }
 
  bool operator != (const FlatMap &m) const
  {
    return not (*this == m);
  }
};
 
}  // end namespace Aleph
 
#endif  // TPL_FLAT_MAP_H