dfe_flat.hpp

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file dfe_flat.hpp

// SPDX-License-Identifier: MIT
// Copyright 2019 Moritz Kiehn
//
// 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.


#pragma once

#include <algorithm>
#include <functional>
#include <stdexcept>
#include <vector>

namespace dfe {

template<
  typename T, typename Compare = std::less<T>,
  typename Container = std::vector<T>>
class FlatSet {
public:
  using value_type = T;
  using size_type = typename Container::size_type;
  using const_iterator = typename Container::const_iterator;

  template<typename U>
  const value_type& at(U&& u) const;

  const_iterator begin() const { return m_items.begin(); }
  const_iterator end() const { return m_items.end(); }

  bool empty() const { return m_items.empty(); }
  size_type size() const { return m_items.size(); }

  void clear() { m_items.clear(); }
  void insert_or_assign(const T& t);

  template<typename U>
  const_iterator find(U&& u) const;
  template<typename U>
  bool contains(U&& u) const;

private:
  Container m_items;
};

template<typename Key, typename T, typename Compare = std::less<Key>>
class FlatMap {
public:
  using key_type = Key;
  using value_type = T;
  using size_type = std::size_t;

  value_type& at(const Key& key) { return m_items[m_keys.at(key).index]; }
  const value_type& at(const Key& key) const {
    return m_items[m_keys.at(key).index];
  }

  bool empty() const { return m_keys.empty(); }
  size_type size() const { return m_keys.size(); }

  void clear() { m_keys.clear(), m_items.clear(); }
  template<typename... Params>
  void emplace(const Key& key, Params&&... params);

  bool contains(const Key& key) const { return m_keys.contains(key); }

private:
  struct KeyIndex {
    Key key;
    size_type index;
  };
  struct KeyCompare {
    constexpr bool operator()(const KeyIndex& lhs, const KeyIndex& rhs) const {
      return Compare()(lhs.key, rhs.key);
    }
    constexpr bool operator()(const KeyIndex& lhs, const Key& rhs_key) const {
      return Compare()(lhs.key, rhs_key);
    }
    constexpr bool operator()(const Key& lhs_key, const KeyIndex& rhs) const {
      return Compare()(lhs_key, rhs.key);
    }
  };

  FlatSet<KeyIndex, KeyCompare> m_keys;
  std::vector<T> m_items;
};

// implementation FlatSet

template<typename T, typename Compare, typename Container>
template<typename U>
inline const typename FlatSet<T, Compare, Container>::value_type&
FlatSet<T, Compare, Container>::at(U&& u) const {
  auto pos = find(std::forward<U>(u));
  if (pos == end()) {
    throw std::out_of_range("The requested element does not exists");
  }
  return *pos;
}

template<typename T, typename Compare, typename Container>
inline void
FlatSet<T, Compare, Container>::insert_or_assign(const T& t) {
  auto pos = std::lower_bound(m_items.begin(), m_items.end(), t, Compare());
  if (((pos != m_items.end()) and !Compare()(t, *pos))) {
    *pos = t;
  } else {
    m_items.emplace(pos, t);
  }
}

template<typename T, typename Compare, typename Container>
template<typename U>
inline typename FlatSet<T, Compare, Container>::const_iterator
FlatSet<T, Compare, Container>::find(U&& u) const {
  auto end = m_items.end();
  auto pos =
    std::lower_bound(m_items.begin(), end, std::forward<U>(u), Compare());
  return ((pos != end) and !Compare()(std::forward<U>(u), *pos)) ? pos : end;
}

template<typename T, typename Compare, typename Container>
template<typename U>
inline bool
FlatSet<T, Compare, Container>::contains(U&& u) const {
  return std::binary_search(
    m_items.begin(), m_items.end(), std::forward<U>(u), Compare());
}

// implementation FlatMap

template<typename Key, typename T, typename Compare>
template<typename... Params>
inline void
FlatMap<Key, T, Compare>::emplace(const Key& key, Params&&... params) {
  auto idx = m_keys.find(key);
  if (idx != m_keys.end()) {
    m_items[idx->index] = T(std::forward<Params>(params)...);
  } else {
    m_items.emplace_back(std::forward<Params>(params)...);
    m_keys.insert_or_assign(KeyIndex{key, m_items.size() - 1});
  }
}

} // namespace dfe