TinySet.h

Go to the documentation of this file.

#ifndef INCLUDE_MOLASSEMBLER_TEMPLE_TINY_SETS_H
#define INCLUDE_MOLASSEMBLER_TEMPLE_TINY_SETS_H

#include <vector>
#include <algorithm>

namespace Scine {
namespace Molassembler {
namespace Temple {

template<typename T>
struct TinyUnorderedSet {
  using UnderlyingContainer = std::vector<T>;
  using value_type = T;
  using reference = T&;
  using const_reference = const T&;
  using iterator = typename std::vector<T>::iterator;
  using const_iterator = typename std::vector<T>::const_iterator;

  UnderlyingContainer data;

  TinyUnorderedSet() {
    static_assert(
      std::is_same<T, typename std::decay<T>::type>::value,
      "Tiny sets can only contain non-cv qualified types"
    );
  }

  TinyUnorderedSet(std::initializer_list<T> list)
    : data(std::forward<std::initializer_list<T>>(list))
  {
    static_assert(
      std::is_same<T, typename std::decay<T>::type>::value,
      "Tiny sets can only contain non-cv qualified types"
    );
  }


  static bool checked_insert(std::vector<T>& set, T a) {
    if(!contains(set, a)) {
      set.push_back(std::move(a));
      return false;
    }

    return true;
  }

  template<typename ... Args>
  static void checked_emplace(std::vector<T>& set, Args&& ... args) {
    set.emplace_back(std::forward<Args>(args)...);

    if(
      std::find(
        std::begin(set),
        std::end(set) - 1,
        set.back()
      ) != std::end(set) - 1
    ) {
      set.pop_back();
    }
  }

  static bool linear_search(std::vector<T>& set, const T& value) {
    return std::find(
      std::begin(set),
      std::end(set),
      value
    ) != std::end(set);
  }

  void clear() {
    data.clear();
  }

  void insert(T a) {
    data.push_back(std::move(a));
  }

  template<typename ... Args>
  void emplace(Args&& ... args) {
    data.emplace_back(std::forward<Args>(args)...);
  }

  template<typename It>
  void erase(It a) {
    auto backIterator = --end();

    if(a == backIterator) {
      data.erase(a);
    } else {
      std::iter_swap(a, backIterator);
      data.erase(backIterator);
    }
  }

  template<typename It>
  void insert(It a, const It& b) {
    while(a != b) {
      if(count(*a) == 0) {
        insert(*a);
      }
      ++a;
    }
  }

  void reserve(std::size_t size) {
    data.reserve(size);
  }

  unsigned count(T a) const {
    return std::find(
      std::begin(data),
      std::end(data),
      a
    ) != std::end(data);
  }

  std::size_t size() const {
    return data.size();
  }

  bool empty() const {
    return size() == 0;
  }

  iterator begin() {
    return std::begin(data);
  }

  iterator end() {
    return std::end(data);
  }

  const_iterator begin() const {
    return std::begin(data);
  }

  const_iterator end() const {
    return std::end(data);
  }

  const_iterator cbegin() const {
    return std::cbegin(data);
  }

  const_iterator cend() const {
    return std::cend(data);
  }
};

template<typename T>
struct TinySet {
  using UnderlyingContainer = std::vector<T>;
  using value_type = T;
  using reference = T&;
  using const_reference = const T&;
  using iterator = typename std::vector<T>::iterator;
  using const_iterator = typename std::vector<T>::const_iterator;

  UnderlyingContainer data;

  TinySet() {
    static_assert(
      std::is_same<T, typename std::decay<T>::type>::value,
      "Tiny sets can only contain non-cv qualified types"
    );
  }
  TinySet(std::initializer_list<T> list)
    : data(std::forward<std::initializer_list<T>>(list))
  {
    static_assert(
      std::is_same<T, typename std::decay<T>::type>::value,
      "Tiny sets can only contain non-cv qualified types"
    );
  }

  static iterator find(std::vector<T>& set, const T& a) {
    return std::lower_bound(
      std::begin(set),
      std::end(set),
      a
    );
  }

  static const_iterator find(const std::vector<T>& set, const T& a) {
    return std::lower_bound(
      std::begin(set),
      std::end(set),
      a
    );
  }

  static void checked_insert(std::vector<T>& set, T a) {
    iterator findIter = find(set, a);

    /* Condition lifted directly from std::binary_search. If the element equals
     * a, then the set already contains the element. In that case, do nothing.
     */
    if(findIter != std::end(set) && !(a < *findIter)) {
      return;
    }

    set.insert(std::move(findIter), std::move(a));
  }

  template<typename ... Args>
  static void checked_emplace(std::vector<T>& set, Args&& ... args) {
    // In-place construct the element at the back of the set
    set.emplace_back(std::forward<Args>(args)...);

    iterator lastElementIter = std::end(set) - 1;

    // Search the range before it for an identical element
    iterator findIter = std::lower_bound(
      std::begin(set),
      lastElementIter,
      set.back()
    );

    if(findIter != lastElementIter && !(set.back() < *findIter)) {
      // Remove the element again
      set.pop_back();
    } else {
      // Rotate in the new element
      std::rotate(
        findIter,
        lastElementIter,
        std::end(set)
      );
    }
  }

  static bool binary_search(const std::vector<T>& set, const T& value) {
    return std::binary_search(
      std::begin(set),
      std::end(set),
      value
    );
  }

  void clear() {
    data.clear();
  }

  template<typename It>
  void erase(It a) {
    data.erase(a);
  }

  void reserve(std::size_t size) {
    data.reserve(size);
  }

  iterator find(const T& a) {
    return std::lower_bound(
      std::begin(data),
      std::end(data),
      a
    );
  }

  void insert(T a) {
    data.insert(
      find(a),
      std::move(a)
    );
  }

  template<typename It>
  void insert(It a, const It& b) {
    while(a != b) {
      if(count(*a) == 0) {
        insert(*a);
      }
      ++a;
    }
  }

  void emplace(T a) {
    insert(std::move(a));
  }

  TinySet& operator = (std::initializer_list<T> init) {
    data.clear();
    for(const auto& value : init) {
      insert(value);
    }

    return *this;
  }

  unsigned count(T a) const {
    return std::binary_search(
      std::begin(data),
      std::end(data),
      a
    );
  }

  bool empty() const {
    return size() == 0;
  }

  std::size_t size() const {
    return data.size();
  }

  const_reference front() const {
    return data.front();
  }

  const_reference back() const {
    return data.back();
  }

  const_reference at(std::size_t position) const {
    return data.at(position);
  }

  iterator begin() {
    return std::begin(data);
  }

  iterator end() {
    return std::end(data);
  }

  const_iterator begin() const {
    return std::begin(data);
  }

  const_iterator end() const {
    return std::end(data);
  }

  const_iterator cbegin() const {
    return std::cbegin(data);
  }

  const_iterator cend() const {
    return std::cend(data);
  }

  bool operator == (const TinySet& other) const {
    return data == other.data;
  }

  bool operator != (const TinySet& other) const {
    return !(*this == other);
  }
};

} // namespace Temple
} // namespace Molassembler
} // namespace Scine

#endif