container_maps.h

Go to the documentation of this file.

/*
 * This file is part of ArmarX.
 *
 * ArmarX is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * ArmarX 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/>.
 *
 * @author     phesch ( ulila at student dot kit dot edu )
 * @date       2022
 * @copyright  http://www.gnu.org/licenses/gpl-2.0.txt
 *             GNU General Public License
 */
 
#pragma once
 
#include <map>
#include <optional>
#include <tuple>
 
#include <RobotAPI/libraries/armem/core/MemoryID.h>
 
namespace armarx::armem
{
 
    namespace detail
    {
 
        /**
        * @brief Get the entry in the map for which the returned key is the longest prefix
        *        of the given key among the keys in the map.
        *
        * `prefixFunc` is used to successively calculate the prefixes of the given key.
        * It must be pure and return an empty optional when there is no shorter
        * prefix of the given key (for strings, this would be the case when passed the empty string).
        *
        * @param keyValMap the map that contains the key-value-pairs to search
        * @param prefixFunc the function that returns the longest non-identical prefix of the key
        * @param key the key to calculate the prefixes of
        *
        * @return The iterator pointing to the found entry, or `keyValMap.end()`.
        */
        template <typename KeyT, typename ValueT>
        typename std::map<KeyT, ValueT>::const_iterator
        findEntryWithLongestPrefix(const std::map<KeyT, ValueT>& keyValMap,
                                   const std::function<std::optional<KeyT>(KeyT&)>& prefixFunc,
                                   const KeyT& key)
        {
            std::optional<KeyT> curKey = key;
 
            typename std::map<KeyT, ValueT>::const_iterator result = keyValMap.end();
            do
            {
                auto iterator = keyValMap.find(curKey.value());
                if (iterator != keyValMap.end())
                {
                    result = iterator;
                }
                else
                {
                    curKey = prefixFunc(curKey.value());
                }
            }
            while (result == keyValMap.end() and curKey.has_value());
 
            return result;
        }
 
        /**
        * @brief Get the entry in the map for which the returned key is the longest prefix
        *        of the given key among the keys in the map that satisfy the predicate.
        *
        * `prefixFunc` is used to successively calculate the prefixes of the given key.
        * It must be pure and return an empty optional when there is no shorter
        * prefix of the given key (for strings, this would be the case when passed the empty string).
        * `predicate` is used to filter for entries that satisfy the desired condition.
        * It must be pure.
        *
        * @param keyValMap the map that contains the key-value-pairs to search
        * @param prefixFunc the function that returns the longest non-identical prefix of the key
        * @param predicate the predicate to filter entries on
        * @param key the key to calculate the prefixes of
        *
        * @return The iterator pointing to the found entry, or `keyValMap.end()`.
        */
        template <typename KeyT, typename ValueT>
        typename std::map<KeyT, ValueT>::const_iterator
        findEntryWithLongestPrefixAnd(
            const std::map<KeyT, ValueT>& keyValMap,
            const std::function<std::optional<KeyT>(KeyT&)>& prefixFunc,
            const KeyT& key,
            const std::function<bool(const KeyT&, const ValueT&)>& predicate)
        {
            std::optional<KeyT> curKey = key;
 
            typename std::map<KeyT, ValueT>::const_iterator result = keyValMap.end();
            do
            {
                auto iterator = keyValMap.find(curKey.value());
                if (iterator != keyValMap.end() and predicate(iterator->first, iterator->second))
                {
                    result = iterator;
                }
                else
                {
                    curKey = prefixFunc(curKey.value());
                }
            }
            while (result == keyValMap.end() and curKey.has_value());
 
            return result;
        }
 
        /**
        * @brief Accumulate all the values in a map for which the keys are prefixes of the given key.
        *
        * `AccumulateT` is a type that the values will be accumulated into using `accumulateFunc`.
        * `accumulateFunc` is a function that modifies the given accumulator
        * (by, e.g., adding the given value to it).
        *
        * The values are accumulated in order from the longest key to the shortest. 
        *
        * @see `getWithLongestPrefix` for a description of `prefixFunc`
        * @param keyValMap the map that contains the key-value-pairs to search
        * @param prefixFunc the function that returns the longest non-identical prefix of the key
        * @param accumulateFunc the function that accumulates the values in the accumulator
        * @param key the key to calculate the prefixes of
        */
        template <typename KeyT, typename ValueT, typename AccumulateT>
        AccumulateT
        accumulateFromPrefixes(const std::map<KeyT, ValueT>& keyValMap,
                               const std::function<std::optional<KeyT>(const KeyT&)>& prefixFunc,
                               const std::function<void(AccumulateT&, const ValueT&)> accumulateFunc,
                               const KeyT& key)
        {
            std::optional<KeyT> curKey = key;
            AccumulateT values;
            do
            {
                const auto nextEntry =
                    findEntryWithLongestPrefix<KeyT, ValueT>(keyValMap, prefixFunc, curKey.value());
                if (nextEntry != keyValMap.end())
                {
                    curKey = prefixFunc(nextEntry->first);
                    accumulateFunc(values, nextEntry->second);
                }
                else
                {
                    curKey.reset();
                }
            }
            while (curKey.has_value());
 
            return values;
        }
 
        /**
        * @brief Collect all the values in a map for which the keys are prefixes of the given key.
        *
        * This is a specialization of the general `accumulateFromPrefixes`
        * for collecting single values into a vector.
        *
        * @see `accumulateFromPrefixes` for a detailed description
        * @param keyValMap the map that contains the key-value-pairs to search
        * @param prefixFunc the function that returns the longest non-identical prefix of the key
        * @param key the key to calculate the prefixes of
        */
        template <typename KeyT, typename ValueT>
        std::vector<ValueT>
        accumulateFromPrefixes(const std::map<KeyT, ValueT>& keyValMap,
                               const std::function<std::optional<KeyT>(const KeyT&)>& prefixFunc,
                               const KeyT& key)
        {
            return accumulateFromPrefixes<KeyT, ValueT, std::vector<ValueT>>(
                keyValMap,
                prefixFunc,
                [](std::vector<ValueT>& values, const ValueT& val) { values.push_back(val); },
                key);
        }
 
        /**
        * @brief Collect all the values in a map for which the keys are prefixes of the given key.
        *
        * This is a specialization of the general `accumulateFromPrefixes`
        * for appending vector values into a single vector.
        *
        * @see `accumulateFromPrefixes` for a detailed description
        * @param keyValMap the map that contains the key-value-pairs to search
        * @param prefixFunc the function that returns the longest non-identical prefix of the key
        * @param key the key to calculate the prefixes of
        */
        template <typename KeyT, typename ValueT>
        std::vector<ValueT>
        accumulateFromPrefixes(const std::map<KeyT, std::vector<ValueT>>& keyValMap,
                               const std::function<std::optional<KeyT>(const KeyT&)>& prefixFunc,
                               const KeyT& key)
        {
            return accumulateFromPrefixes<KeyT, std::vector<ValueT>, std::vector<ValueT>>(
                keyValMap,
                prefixFunc,
                [](std::vector<ValueT>& values, const std::vector<ValueT>& val)
                { values.insert(values.end(), val.begin(), val.end()); },
                key);
        }
 
    } // namespace detail
 
 
    std::optional<MemoryID> inline getMemoryIDParent(const MemoryID& memID)
    {
        if (!memID.hasMemoryName())
        {
            return std::nullopt;
        }
        MemoryID parent = memID.removeLeafItem();
        return {parent};
    }
 
 
    /**
     * @brief Find the entry with the most specific key that contains the given ID,
     * or `idMap.end()` if no key contains the ID.
     *
     * @see `detail::findEntryWithLongestPrefix()`
     */
    template <typename ValueT>
    typename std::map<MemoryID, ValueT>::const_iterator
    findMostSpecificEntryContainingID(const std::map<MemoryID, ValueT>& idMap, const MemoryID& id)
    {
        return detail::findEntryWithLongestPrefix<MemoryID, ValueT>(idMap, &getMemoryIDParent, id);
    }
 
 
    /**
     * @brief Find the entry with the most specific key that contains the given ID
     * and satisfies the predicate, or `idMap.end()` if no key contains the ID and satisfies
     * the predicate.
     *
     * @see `detail::findEntryWithLongestPrefixAnd()`
     */
    template <typename ValueT>
    typename std::map<MemoryID, ValueT>::const_iterator
    findMostSpecificEntryContainingIDAnd(const std::map<MemoryID, ValueT>& idMap, const MemoryID& id,
                                         const std::function<bool(const MemoryID&, const ValueT&)>& predicate)
    {
        return detail::findEntryWithLongestPrefixAnd<MemoryID, ValueT>(
            idMap, &getMemoryIDParent, id, predicate);
    }
 
 
    /**
     * @brief Return all values of keys containing the given ID.
     *
     * @see `detail::accumulateFromPrefixes()`
     */
    template <typename ValueT>
    std::vector<ValueT>
    accumulateEntriesContainingID(const std::map<MemoryID, ValueT>& idMap, const MemoryID& id)
    {
        return detail::accumulateFromPrefixes<MemoryID, ValueT>(idMap, &getMemoryIDParent, id);
    }
 
 
    /**
     * @brief Return all values of keys containing the given ID in a flattened vector.
     *
     * @see `detail::accumulateFromPrefixes()`
     */
    template <typename ValueT>
    std::vector<ValueT>
    accumulateEntriesContainingID(const std::map<MemoryID, std::vector<ValueT>>& idMap,
                                  const MemoryID& key)
    {
        return detail::accumulateFromPrefixes<MemoryID, ValueT>(idMap, &getMemoryIDParent, key);
    }
 
 
} // namespace armarx::armem