tpl_flat_set.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_SET_H
#define TPL_FLAT_SET_H
 
#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <utility>
 
#include <ah-errors.H>
#include <ahFunction.H>
#include <tpl_memArray.H>
#include <tpl_sort_utils.H>
 
namespace Aleph {
 
template <typename Key, class Compare = Aleph::less<Key>>
class FlatSet
{
  MemArray<Key> keys_;
  Compare cmp_;
 
  // Index of the first element 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)
      if (const size_t mid = lo + ((hi - lo) >> 1); cmp_(keys_(mid), k))
        lo = mid + 1;
      else
        hi = mid;
    return lo;
  }
 
  // Index of the first element greater than k (upper bound position).
  size_t upper_idx(const Key &k) const
  {
    size_t lo = 0, hi = keys_.size();
    while (lo < hi)
      if (const size_t mid = lo + ((hi - lo) >> 1); 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),
  // so only the second half of the equivalence needs testing.
  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 by shifting [pos, n) one place right.
  void make_room(const size_t pos)
  {
    keys_.putn(1);
    Key *p = keys_.get_ptr();
    for (size_t i = keys_.size() - 1; i > pos; --i)
      p[i] = std::move(p[i - 1]);
  }
 
  // Removes the slot at pos by shifting (pos, n) one place left. A failed
  // shrinking reallocation is ignored: the logical removal always succeeds.
  void remove_at(const size_t pos)
  {
    Key *p = keys_.get_ptr();
    const size_t last = keys_.size() - 1;
    for (size_t i = pos; i < last; ++i)
      p[i] = std::move(p[i + 1]);
    try
      {
        (void) keys_.get();
      }
    catch (const std::bad_alloc &)
      {
        // Shrinking reallocation can fail; the logical removal already
        // took effect because the element count was decremented first.
      }
  }
 
  // Sorts the freshly loaded backing array and drops duplicates, keeping
  // the first occurrence of each equivalence class.
  void sort_and_unique()
  {
    Key *p = keys_.get_ptr();
    timsort(p, keys_.size(), cmp_);
    size_t m = 0;
    for (size_t i = 0; i < keys_.size(); ++i)
      if (m == 0 or cmp_(p[m - 1], p[i]))
        {
          if (i != m)
            p[m] = std::move(p[i]);
          ++m;
        }
    const size_t excess = keys_.size() - m;
    if (excess > 0)
      try
        {
          (void) keys_.get(excess);
        }
      catch (const std::bad_alloc &)
        { /* shrink failed; logical removal already done */ }
  }
 
public:
  using Item_Type = Key;               
  using Key_Type = Key;                
  using key_type = Key;                
  using value_type = Key;              
  using key_compare = Compare;         
  using size_type = size_t;            
  using iterator = const Key *;        
  using const_iterator = const Key *;  
 
  explicit FlatSet(size_t cap = MemArray<Key>::Min_Dim) : keys_(cap) {}
 
  explicit FlatSet(const Compare &cmp, size_t cap = MemArray<Key>::Min_Dim) : keys_(cap), cmp_(cmp)
  {}
 
  template <std::input_iterator It>
  FlatSet(It first, It last, const Compare &cmp = Compare())
    : keys_(MemArray<Key>::Min_Dim), cmp_(cmp)
  {
    for (; first != last; ++first)
      keys_.put(*first);
    sort_and_unique();
  }
 
  FlatSet(std::initializer_list<Key> l, const Compare &cmp = Compare())
    : FlatSet(l.begin(), l.end(), cmp)
  {}
 
  FlatSet(const FlatSet &) = default;
 
  FlatSet(FlatSet &&) noexcept = default;
 
  FlatSet &operator = (const FlatSet &) = default;
 
  FlatSet &operator = (FlatSet &&) noexcept = default;
 
  ~FlatSet() = default;
 
  void swap(FlatSet &s) noexcept(std::is_nothrow_swappable_v<Compare>)
  {
    keys_.swap(s.keys_);
    std::swap(cmp_, s.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);
  }
 
  void empty() noexcept
  {
    keys_.empty();
  }
 
  void clear() noexcept
  {
    keys_.clear();
  }
 
  // -- lookup ---------------------------------------------------------------
 
  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;
  }
 
  const_iterator lower_bound(const Key &k) const
  {
    return begin() + lower_idx(k);
  }
 
  const_iterator upper_bound(const Key &k) const
  {
    return begin() + upper_idx(k);
  }
 
  std::pair<const_iterator, const_iterator> equal_range(const Key &k) const
  {
    return {lower_bound(k), upper_bound(k)};
  }
 
  const Key &nth(size_t i) const
  {
    return keys_[i];
  }
 
  const Key &operator () (size_t i) const noexcept
  {
    return keys_(i);
  }
 
  const Key &get_first() const
  {
    ah_underflow_error_if(is_empty()) << "FlatSet::get_first(): empty set";
    return keys_(0);
  }
 
  const Key &get_last() const
  {
    ah_underflow_error_if(is_empty()) << "FlatSet::get_last(): empty set";
    return keys_(keys_.size() - 1);
  }
 
  const Key &min() const
  {
    return get_first();
  }
 
  const Key &max() const
  {
    return get_last();
  }
 
  // -- modifiers ------------------------------------------------------------
 
  std::pair<const_iterator, bool> insert(const Key &k)
  {
    const size_t pos = lower_idx(k);
    if (match_at(pos, k))
      return {begin() + pos, false};
    make_room(pos);
    keys_.get_ptr()[pos] = k;
    return {begin() + pos, true};
  }
 
  std::pair<const_iterator, bool> insert(Key &&k)
  {
    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);
    return {begin() + pos, true};
  }
 
  template <class... Args>
  std::pair<const_iterator, bool> emplace(Args &&...args)
  {
    return insert(Key(std::forward<Args>(args)...));
  }
 
  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;
  }
 
  const_iterator erase(const_iterator it)
  {
    const size_t pos = it - begin();
    ah_out_of_range_error_if(pos >= size()) << "FlatSet::erase(): iterator out of range";
    remove_at(pos);
    return begin() + pos;
  }
 
  // -- iteration ------------------------------------------------------------
 
  const_iterator begin() const noexcept
  {
    return keys_.get_ptr();
  }
 
  const_iterator end() const noexcept
  {
    return keys_.get_ptr() + keys_.size();
  }
 
  const_iterator cbegin() const noexcept
  {
    return begin();
  }
 
  const_iterator cend() const noexcept
  {
    return end();
  }
 
  const Key *data() const noexcept
  {
    return keys_.get_ptr();
  }
 
  template <class Operation>
  bool traverse(Operation operation) const
  {
    const Key *p = keys_.get_ptr();
    const size_t m = keys_.size();
    for (size_t i = 0; i < m; ++i)
      if (not operation(p[i]))
        return false;
    return true;
  }
 
  // -- comparison -----------------------------------------------------------
 
  bool operator == (const FlatSet &s) const
  {
    return size() == s.size() and std::equal(begin(), end(), s.begin());
  }
 
  bool operator != (const FlatSet &s) const
  {
    return not (*this == s);
  }
};
 
}  // end namespace Aleph
 
#endif  // TPL_FLAT_SET_H