OrderedMap.hpp

/*
  Copyright 2014 Statoil ASA.

  This file is part of the Open Porous Media project (OPM).

  OPM 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.

  OPM 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 OPM.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef OPM_ORDERED_MAP_HPP
#define OPM_ORDERED_MAP_HPP

#include <algorithm>
#include <cctype>
#include <cstddef>
#include <functional>
#include <iterator>
#include <set>
#include <stdexcept>
#include <string>
#include <string_view>
#include <unordered_map>
#include <utility>
#include <vector>

namespace Opm {

namespace OrderedMapDetail {

template<class T, class A>
std::string
findSimilarStrings(std::string str,
                   const std::vector<std::pair<std::string, T>,A>& storage)
{
    auto toUpper = [](const char c){ return std::toupper(c);};
    std::ranges::transform(str, str.begin(), toUpper);
    std::set<std::string> alternatives;

    for(const auto& entry: storage)
    {
        std::string upper = entry.first;
        std::ranges::transform(upper, upper.begin(), toUpper);

        if(upper.find(str) != std::string::npos || str.find(upper) != std::string::npos)
        {
            alternatives.insert(entry.first);
        }
    }

    if (alternatives.empty())
    {
        return {};
    }

    std::string concatedStr;
    for (const auto& alt : alternatives) {
      concatedStr += alt;
      concatedStr += ", ";
    }
    return concatedStr.substr(0, concatedStr.size()-2);
}

template<std::string_view::size_type MAX_CHARS>
class TruncatedStringHash
{
public:
    std::size_t operator()(std::string_view key) const
    {
        return hasher(key.substr(0, MAX_CHARS));
    }
private:
    std::hash<std::string_view> hasher;
};


template<>
class TruncatedStringHash<std::string_view::npos> : public std::hash<std::string_view>
{};

template<std::string_view::size_type MAX_CHARS>
struct TruncatedStringEquals
{
    bool operator()(std::string_view str1, std::string_view str2) const
    {
        return str1.substr(0, MAX_CHARS) == str2.substr(0, MAX_CHARS);
    }
};

template<>
struct TruncatedStringEquals<std::string::npos> : public std::equal_to<std::string>
{};

} // end namespace OrderedMapDetail

template <typename T, std::string_view::size_type MAX_CHARS = std::string_view::npos>
class OrderedMap {
public:
    using storage_type = std::vector<std::pair<std::string, T>>;
    using index_type = std::unordered_map<std::string, typename storage_type::size_type,
                                          OrderedMapDetail::TruncatedStringHash<MAX_CHARS>,
                                          OrderedMapDetail::TruncatedStringEquals<MAX_CHARS>>;
    using iter_type = typename storage_type::iterator;
    using const_iter_type = typename storage_type::const_iterator;

private:
    index_type m_map;
    storage_type m_vector;

public:

    OrderedMap() = default;

    OrderedMap(const index_type& index, const storage_type& storage)
        : m_map(index)
        , m_vector(storage)
    {
    }

    const index_type& getIndex() const { return m_map; }

    const storage_type& getStorage() const { return m_vector; }

    std::size_t count(const std::string& key) const {
        return this->m_map.count(key);
    }



    T& operator[](const std::string& key) {
        if (this->count(key) == 0)
            this->insert( std::make_pair(key, T()));

        return this->at(key);
    }


    std::size_t erase(const std::string& key) {
        if (this->count(key) == 0)
            return 0;

        const std::size_t idx = this->m_map.at(key);
        this->m_map.erase(key);
        this->m_vector.erase(this->m_vector.begin() + idx);

        for (const auto& index_pair : this->m_map) {
            auto target_index = index_pair.second;
            if (target_index > idx) {
                --target_index;
            }

            this->m_map[index_pair.first] = target_index;
        }
        return 1;
    }


    void insert(std::pair<std::string,T> key_value_pair) {
        if (this->count(key_value_pair.first) > 0) {
            auto iter = m_map.find( key_value_pair.first );
            const std::size_t idx = iter->second;
            m_vector[idx] = key_value_pair;
        } else {
            const std::size_t idx = m_vector.size();
            this->m_map.emplace(key_value_pair.first, idx);
            this->m_vector.push_back(std::move(key_value_pair));
        }
    }


    T& get(const std::string& key) {
        auto iter = m_map.find( key );
        if (iter == m_map.end())
        {
            using namespace std::string_literals;
            auto startsWithSame = OrderedMapDetail::findSimilarStrings(key, m_vector);
            if (!startsWithSame.empty())
            {
                startsWithSame = " Similar entries are "s +
                    startsWithSame + "."s;
            }
            throw std::invalid_argument("Key "s + key + " not found."s
                                        + startsWithSame);
        }
        else {
            const std::size_t idx = iter->second;
            return iget(idx);
        }
    }


    T& iget(std::size_t index) {
        if (index >= m_vector.size())
            throw std::invalid_argument("Invalid index");
        return m_vector[index].second;
    }

    const T& get(const std::string& key) const {
        const auto& iter = this->m_map.find( key );
        if (iter == m_map.end())
        {
            auto startsWithSame = OrderedMapDetail::findSimilarStrings(key, m_vector);
            if (!startsWithSame.empty())
            {
                startsWithSame = std::string(" Similar entries are ") +
                    startsWithSame + std::string(".");
            }
            using namespace std::string_literals;
            throw std::invalid_argument("Key "s + key + " not found."s
                                        + startsWithSame);
        }
        else {
            const std::size_t idx = iter->second;
            return iget(idx);
        }
    }


    const T& iget(std::size_t index) const {
        if (index >= m_vector.size())
        {
            using namespace std::string_literals;
            throw std::invalid_argument("Invalid index "s +
                                        std::to_string(index) +
                                        " is larger than container size"s);
        }
        return m_vector[index].second;
    }

    const T& at(std::size_t index) const {
        return this->iget(index);
    }

    const T& at(const std::string& key) const {
        return this->get(key);
    }

    T& at(std::size_t index) {
        return this->iget(index);
    }

    T& at(const std::string& key) {
        return this->get(key);
    }

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


    const_iter_type begin() const {
        return m_vector.begin();
    }


    const_iter_type end() const {
        return m_vector.end();
    }

    iter_type begin() {
        return m_vector.begin();
    }

    iter_type end() {
        return m_vector.end();
    }

    iter_type find(const std::string& key) {
        const auto map_iter = this->m_map.find(key);
        if (map_iter == this->m_map.end())
            return this->m_vector.end();

        return std::next(this->m_vector.begin(), map_iter->second);
    }

    const_iter_type find(const std::string& key) const {
        const auto map_iter = this->m_map.find(key);
        if (map_iter == this->m_map.end())
            return this->m_vector.end();

        return std::next(this->m_vector.begin(), map_iter->second);
    }

    template<std::size_t n>
    bool operator==(const OrderedMap<T,n>& data) const {
        return this->getIndex() == data.getIndex() &&
               this->getStorage() == data.getStorage();
    }

    template<class Serializer>
    void serializeOp(Serializer& serializer)
    {
        serializer(m_map);
        serializer(m_vector);
    }
};

}

#endif