packages/engine/scram-node/src/ext/linear_set.h

Implementation of a vector-based set for a small number of entries.

Source code

/*
 * Copyright (C) 2018 Olzhas Rakhimov
 * Copyright (C) 2023 OpenPRA ORG Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */


#pragma once

#include <algorithm>
#include <initializer_list>
#include <utility>
#include <vector>

namespace ext {

struct identity {
  template <typename T>
  T& operator()(T& arg) const {  // NOLINT
    return arg;
  }
};

template <typename Value, typename KeyFromValue = identity,
          template <typename...> class Sequence = std::vector>
class linear_set {
  friend bool operator==(const linear_set& lhs, const linear_set& rhs) {
    if (lhs.size() != rhs.size())
      return false;
    return std::all_of(lhs.begin(), lhs.end(), [&rhs](const Value& value) {
      return rhs.count_value(value);
    });
  }
  friend bool operator!=(const linear_set& lhs, const linear_set& rhs) {
    return !(lhs == rhs);
  }

  friend void swap(linear_set& lhs, linear_set& rhs) noexcept { lhs.swap(rhs); }

 public:
  using key_from_value = KeyFromValue;
  using value_type = Value;
  using key_type = std::decay_t<decltype(
      key_from_value()(*static_cast<value_type*>(nullptr)))>;
  using container_type = Sequence<value_type>;

  using pointer = typename container_type::pointer;
  using const_pointer = typename container_type::const_pointer;
  using reference = typename container_type::reference;
  using const_reference = typename container_type::const_reference;
  using iterator = typename container_type::iterator;
  using const_iterator = typename container_type::const_iterator;
  using reverse_iterator = typename container_type::reverse_iterator;
  using const_reverse_iterator =
      typename container_type::const_reverse_iterator;
  using size_type = typename container_type::size_type;
  using difference_type = typename container_type::difference_type;

  linear_set() = default;
  linear_set(std::initializer_list<value_type> init_list) {
    linear_set::insert(init_list.begin(), init_list.end());
  }

  template <typename Iterator>
  linear_set(Iterator first1, Iterator last1) {
    linear_set::insert(first1, last1);
  }

  key_from_value key_extractor() const { return key_from_value(); }

  const_iterator find(const key_type& key) const {
    return std::find_if(set_.cbegin(), set_.cend(),
                        [&key](const value_type& value) {
                          return key == key_from_value()(value);
                        });
  }

  iterator find(const key_type& key) {
    return std::find_if(set_.begin(), set_.end(),
                        [&key](const value_type& value) {
                          return key == key_from_value()(value);
                        });
  }

  size_type count(const key_type& key) const {
    return linear_set::find(key) != set_.end();
  }

  std::pair<iterator, bool> insert(const value_type& value) {
    auto it = linear_set::find_value(value);
    if (it != set_.end())
      return {it, false};
    set_.push_back(value);
    return {std::prev(set_.end()), true};
  }

  std::pair<iterator, bool> insert(value_type&& value) {
    auto it = linear_set::find_value(value);
    if (it != set_.end())
      return {it, false};
    set_.push_back(std::move(value));
    return {std::prev(set_.end()), true};
  }

  template <typename Iterator>
  void insert(Iterator first1, Iterator last1) {
    for (; first1 != last1; ++first1) {
      if (!linear_set::count_value(*first1))
        set_.push_back(*first1);
    }
  }

  template <typename... Ts>
  std::pair<iterator, bool> emplace(Ts&&... args) {
    return linear_set::insert(value_type(std::forward<Ts>(args)...));
  }

  iterator erase(const_iterator pos) { return set_.erase(pos); }
  iterator erase(iterator pos) { return set_.erase(pos); }

  size_type erase(const key_type& key) {
    iterator it = linear_set::find(key);
    if (it == set_.end())
      return 0;
    linear_set::erase(it);
    return 1;
  }

  void swap(linear_set& other) noexcept { set_.swap(other.set_); }

  size_type size() const { return set_.size(); }

  bool empty() const { return set_.empty(); }

  void clear() noexcept { set_.clear(); }

  void reserve(size_type n) { set_.reserve(n); }

  size_type capacity() const { return set_.capacity(); }

  container_type& data() { return set_; }
  const container_type& data() const { return set_; }

  iterator begin() { return set_.begin(); }
  iterator end() { return set_.end(); }

  const_iterator cbegin() const { return set_.cbegin(); }
  const_iterator begin() const { return set_.cbegin(); }

  const_iterator cend() const { return set_.cend(); }
  const_iterator end() const { return set_.cend(); }

  reverse_iterator rbegin() { return set_.rbegin(); }
  reverse_iterator rend() { return set_.rend(); }
  const_reverse_iterator crbegin() const { return set_.crbegin(); }
  const_reverse_iterator rbegin() const { return set_.crbegin(); }
  const_reverse_iterator crend() const { return set_.crend(); }
  const_reverse_iterator rend() const { return set_.crend(); }

 private:
  const_iterator find_value(const value_type& value) const {
    return find(key_from_value()(value));
  }
  iterator find_value(const value_type& value) {
    return find(key_from_value()(value));
  }

  size_type count_value(const value_type& value) const {
    return linear_set::find_value(value) != set_.end();
  }

  container_type set_;  
};

}  // namespace ext

---

Updated on 2025-11-11 at 16:51:08 +0000