VariableSet.h

#pragma once
 
#include <algorithm>
#include <functional>
#include <iosfwd>
#include <limits>
#include <vector>
 
#include "delpi/symbolic/Variable.h"
#include "delpi/util/concepts.h"
 
namespace delpi {

class VariableSet {
 public:
  using Id = Variable::Id;

  VariableSet() : min_id_{std::numeric_limits<Id>::max()} {}
  template <TypedIterable<Variable> T>
  explicit VariableSet(const T& vars) : VariableSet{} {
    Insert(vars);
  }

  template <std::same_as<Variable>... Vars>
  explicit VariableSet(const Variable& var, const Vars&... vars) : VariableSet{} {
    Insert(var, vars...);
  }

  [[nodiscard]] Id min_id() const { return min_id_; }
  [[nodiscard]] Id max_id() const { return vars_.size() + min_id_; }
  [[nodiscard]] std::size_t size() const;
  [[nodiscard]] std::size_t capacity() const { return vars_.size(); }
  [[nodiscard]] bool empty() const;
  [[nodiscard]] std::vector<Variable> variables() const;

  [[nodiscard]] Variable Get(Id id) const;
  [[nodiscard]] bool Contains(const Variable& var) const { return Contains(var.id()); }
  bool Insert(const Variable& var) { return Insert(var.id()); }
  template <TypedIterable<Variable> T>
  void Insert(const T& vars) {
    using Comparator = std::less<Variable>;
    // If the set is empty, initialise it with min_id_ = min(vars.id) and size m = max(vars.id) - min_id_ + 1
    if (min_id_ == std::numeric_limits<Id>::max()) {
      min_id_ = std::ranges::min_element(vars, Comparator{})->id();
      vars_.resize(std::ranges::max_element(vars, Comparator{})->id() - min_id_ + 1, false);
      for (const Variable var : vars) vars_.at(var.id() - min_id_) = true;
      return;
    }
    // If the set is not empty, resize it to the new range and insert the variables
    // First compute the new min_id and max_id comparing with the current min_id and max_id
    // Then resize the vector to the new range m = new_max - new_min + 1
    const Id new_min = std::min(std::ranges::min_element(vars, Comparator{})->id(), min_id_);
    const Id new_max = std::max(std::ranges::max_element(vars, Comparator{})->id(), vars_.size() + min_id_ - 1);
    const std::size_t max_diff = new_max - (vars_.size() + min_id_ - 1);
    const std::size_t old_size = vars_.size();
    vars_.resize(new_max - new_min + 1);
    // If the lower bound of the new range is less than the current min_id, rotate the vector to the left by max_diff
    if (new_min < min_id_) {
      std::rotate(vars_.begin(), vars_.begin() + static_cast<std::int64_t>(old_size),
                  vars_.end() - static_cast<std::int64_t>(max_diff));
      min_id_ = new_min;
    }
    for (const Variable var : vars) vars_.at(var.id() - min_id_) = true;
  }

  template <std::same_as<Variable>... Vars>
  void Insert(const Variable& var, const Vars&... vars) {
    Insert(var);
    Insert(vars...);
  }

  bool Remove(const Variable& var) { return Remove(var.id()); }
  template <TypedIterable<Variable> T>
  void Remove(const T& vars) {
    for (const Variable& var : vars) Remove(var);
  }

  template <std::same_as<Variable>... Vars>
  void Remove(const Variable& var, const Vars&... vars) {
    Remove(var);
    Remove(vars...);
  }

  void Clear();
 
 private:
  [[nodiscard]] bool Contains(Id id) const;
  bool Insert(Id id);
  bool Remove(Id id);
 
  Id min_id_;               
  std::vector<bool> vars_;  
};
 
std::ostream& operator<<(std::ostream& os, const VariableSet& var_set);
 
}  // namespace delpi
 
#ifdef DELPI_INCLUDE_FMT
 
#include "delpi/util/logging.h"
 
OSTREAM_FORMATTER(delpi::VariableSet)
 
#endif