algorithm.h

Go to the documentation of this file.

/*
 * This file is part of ArmarX.
 *
 * Copyright (C) 2011-2016, High Performance Humanoid Technologies (H2T), Karlsruhe Institute of Technology (KIT), all rights reserved.
 *
 * 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/>.
 *
 * @package    ArmarXCore
 * @author     Raphael Grimm ( raphael dot grimm at kit dot edu)
 * @date       2016
 * @copyright  http://www.gnu.org/licenses/gpl-2.0.txt
 *             GNU General Public License
 */
#pragma once
 
#include <algorithm>
#include <map>
#include <unordered_map>
#include <numeric>
#include <vector>
 
#include "TemplateMetaProgramming.h"
 
namespace armarx
{
    /**
     * @brief Uses the range of indices to copy values  (accessed via src.at())from the given container into the output iterator.
     *
     * This function e.g. is useful if you have a map of joint values and need a specific subset 'idx' as vector of floats.
     * \code
     * std::vector<int> idx = {0,1,3};
     *
     * std::vector<long> srcV={0,10,20,30,40,50};
     * std::vector<long> fromVec;
     * copyValuesAt(srcV, idx.begin(), idx.end(), std::back_inserter(fromVec));
     * //fromVec == {0, 10, 30}
     *
     * std::map<int, long> srcM={{0,0},{1,10},{2,20},{3,30},{4,40},{5,50}};
     * std::vector<long> fromMap;
     * copyValuesAt(srcM, idx.begin(), idx.end(), std::back_inserter(fromMap));
     * //fromMap == {0, 10, 30}
     * \endcode
     */
    template<class ContainerT, class IndexIteratorT, class OutputIteratorT, class IndexT = typename std::iterator_traits<IndexIteratorT>::value_type>
    void copyValuesAt(const ContainerT& src, IndexIteratorT fst, IndexIteratorT lst, OutputIteratorT dest)
    {
        std::transform(fst, lst, dest, [&src](const IndexT & i)
        {
            return src.at(i);
        });
    }
 
    /**
     * @brief Uses the container of indices to copy values  (accessed via src.at())from the given container into the output iterator.
     *
     * This function e.g. is useful if you have a map of joint values and need a specific subset 'idx' as vector of floats.
     * \code
     * std::vector<int> idx = {0,1,3};
     *
     * std::vector<long> srcV={0,10,20,30,40,50};
     * std::vector<long> fromVec;
     * copyValuesAt(srcV, idx, std::back_inserter(fromVec));
     * //fromVec == {0, 10, 30}
     *
     * std::map<int, long> srcM={{0,0},{1,10},{2,20},{3,30},{4,40},{5,50}};
     * std::vector<long> fromMap;
     * copyValuesAt(srcM, idx, std::back_inserter(fromMap));
     * //fromMap == {0, 10, 30}
     * \endcode
     */
    template<class ContainerT, class IndexContainerT, class OutputIteratorT, class IndexT = typename IndexContainerT::value_type>
    void copyValuesAt(const ContainerT& src, const IndexContainerT& idx, OutputIteratorT dest)
    {
        copyValuesAt(src, idx.begin(), idx.end(), dest);
    }
 
    /**
     * @brief Uses the range of indices to copy values  (accessed via src.at())from the given container into a vector and returns his vector.
     *
     * This function e.g. is useful if you have a map of joint values and need a specific subset 'idx' as vector of floats.
     * \code
     * std::vector<int> idx = {0,1,3};
     *
     * std::vector<long> srcV={0,10,20,30,40,50};
     * std::vector<long> fromVec = copyValuesAt(srcV, idx.begin(), idx.end());
     * //fromVec == {0, 10, 30}
     *
     * std::map<int, long> srcM={{0,0},{1,10},{2,20},{3,30},{4,40},{5,50}};
     * std::vector<long> fromMap = copyValuesAt(srcM, idx.begin(), idx.end());
     * //fromMap == {0, 10, 30}
     * \endcode
     */
    template<class ContainerT, class IndexIteratorT, class IndexT = typename std::iterator_traits<IndexIteratorT>::value_type>
    std::vector<typename ContainerT::value_type> copyValuesAt(const ContainerT& src, IndexIteratorT fst, IndexIteratorT lst)
    {
        std::vector<typename ContainerT::value_type> result;
        result.reserve(std::distance(fst, lst));
        copyValuesAt(src, std::move(fst), std::move(lst), std::back_inserter(result));
        return result;
    }
 
    /**
     * @brief Uses the container of indices to copy values (accessed via src.at()) from the given container into a vector and returns his vector.
     *
     * This function e.g. is useful if you have a map of joint values and need a specific subset 'idx' as vector of floats.
     * \code
     * std::vector<int> idx = {0,1,3};
     *
     * std::vector<long> srcV={0,10,20,30,40,50};
     * std::vector<long> fromVec = copyValuesAt(srcV, idx);
     * //fromVec == {0, 10, 30}
     *
     * std::map<int, long> srcM={{0,0},{1,10},{2,20},{3,30},{4,40},{5,50}};
     * std::vector<long> fromMap = copyValuesAt(srcM, idx);
     * //fromMap == {0, 10, 30}
     * \endcode
     */
    template<class ContainerT, class IndexContainerT, class IndexT = typename IndexContainerT::value_type>
    std::vector<typename ContainerT::value_type> copyValuesAt(const ContainerT& src, const IndexContainerT& idx)
    {
        return copyValuesAt(src, idx.begin(), idx.end());
    }
 
 
    /**
     * @brief This function takes a container (e.g. a vector) of unique elements and returns a map mapping the elements to their corresponding index
     * @param Container of unique elements (needs index access via at)
     * @return index map
     */
    template<class T, class MapType = std::unordered_map<typename T::value_type, typename T::size_type>>
    MapType toIndexMap(const T& vec)
    {
        MapType result;
        result.reserve(vec.size());
        for (typename T::size_type i = 0; i < vec.size(); ++i)
        {
            auto emplacement = result.emplace(vec.at(i), i).second;
            if (!emplacement)
            {
                throw std::invalid_argument {"The given container did not contain unique elements!"};
            }
        }
        return result;
    }
 
    template<class MapType, class OutputIteratorType>
    void getMapKeys(const MapType& map, OutputIteratorType it)
    {
        for (const auto& e : map)
        {
            *it = e.first;
            ++it;
        }
    }
 
    template<class MapType>
    std::vector<typename MapType::key_type> getMapKeys(const MapType& map)
    {
        std::vector<typename MapType::key_type> result;
        result.reserve(map.size());
        getMapKeys(map, std::back_inserter(result));
        return result;
    }
 
    template<class MapType, class OutputIteratorType>
    void getMapValues(const MapType& map, OutputIteratorType it)
    {
        for (const auto& e : map)
        {
            *it = e.second;
            ++it;
        }
    }
 
    template<class MapType, template<class...> class ContainerT = std::vector>
    ContainerT<typename MapType::mapped_type> getMapValues(const MapType& map)
    {
        ContainerT<typename MapType::mapped_type> result;
        getMapValues(map, std::inserter(result, result.end()));
        return result;
    }
 
    template<class T>
    T sign(T t)
    {
        return t < 0 ? -1 : 1;
    }
 
    /**
     * @brief Increment all given parameter using the pre-increment operator.
     */
    inline void incrementAll() {}
    template<typename It0, typename ...It>
    void incrementAll(It0& it0, It& ...it)
    {
        ++it0;
        incrementAll(it...);
    }
 
 
    enum class MergeMapsMode
    {
        OverrideOldValues,
        KeepOldValues,
        OverrideNoValues
    };
 
    /**
     *  Inserts and overwrites the values from oldMap with the values from newMap.
     *  Template parameter T needs to be a map-container value like std::map.
     */
    template <typename T>
    void mergeMaps(T& oldMap, const T& newMap, MergeMapsMode mergeMode = MergeMapsMode::OverrideOldValues)
    {
        //we can't annotate fallthrough as ok (we need a newer compiler)
#pragma GCC diagnostic push
#if __GNUC__ > 4
#pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
#endif
        switch (mergeMode)
        {
            case MergeMapsMode::OverrideNoValues:
                for (auto& elem : newMap)
                {
                    if (oldMap.count(elem.first))
                    {
                        throw std::invalid_argument {"mergeMaps: newMap would override values from oldMap"};
                    }
                }
            //all ok -> fall through
            case MergeMapsMode::OverrideOldValues:
                for (auto& elem : newMap)
                {
                    oldMap[elem.first] = elem.second;
                }
                break;
            case MergeMapsMode::KeepOldValues:
                for (auto& elem : newMap)
                {
                    oldMap.emplace(elem);
                }
                break;
        }
#pragma GCC diagnostic pop
    }
 
    template <class MapInT, class TransformT, class MapOutT = MapInT>
    void transformMapKeys(const MapInT& inMap, MapOutT& outMap, TransformT transform)
    {
        for (const auto& elem : inMap)
        {
            outMap[transform(elem.first)] = elem.second;
        }
    }
 
    template <class MapInT, class TransformT, class MapOutT = MapInT>
    MapOutT transformMapKeys(const MapInT& inMap, TransformT transform)
    {
        MapOutT out;
        transformMapKeys(inMap, out, transform);
        return out;
    }
 
    template <class KeyT, class ValT>
    std::vector<KeyT> getIndices(const std::map<KeyT, ValT>& c)
    {
        return getMapKeys(c);
    }
 
    template <class KeyT, class ValT>
    std::vector<KeyT> getIndices(const std::unordered_map<KeyT, ValT>& c)
    {
        return getMapKeys(c);
    }
 
    template <class ValT>
    std::vector<std::size_t> getIndices(const std::vector<ValT>& c)
    {
        std::vector<std::size_t> r(c.size()); // don't use uniform initialization here!
        std::iota(r.begin(), r.end(), 0);
        return r;
    }
 
    template <class ContainerType, class ElementType>
    bool Contains(const ContainerType& container, const ElementType& searchElement)
    {
        return std::find(container.begin(), container.end(), searchElement) != container.end();
    }
 
    /**
     * Convenience function (with less typing) to transform a container of type InputT into the same container type of type OutputT.
     *
     * Example usage:
     * <code>
     * std::vector<int> values = {1,2,3};
     * auto stringValues = transform(values, +[](const int& v)
     *      {
     *          return std::to_string(v);
     *      };
     * // stringValues == {"1","2","3"}
     * </code>
     * \note Do not forget the + in front of the lambda!
     */
    template <class OutputT, class InputT, typename Alloc, template <class, class> class Container>
    auto transform(const Container<InputT, Alloc>& in, OutputT(*func)(InputT const&))
    -> Container<OutputT, typename std::allocator_traits<Alloc>::template rebind_alloc<OutputT> >
    {
        Container<OutputT, typename std::allocator_traits<Alloc>::template rebind_alloc<OutputT>> result;
        result.reserve(in.size());
        std::transform(in.begin(), in.end(), std::back_inserter(result), func);
        return result;
    }
}
namespace std
{
    template<class T, class...Ts>
    bool isfinite(const std::vector<T, Ts...>& v)
    {
        return std::all_of(v.begin(), v.end(), [](const T & t)
        {
            return isfinite(t);
        });
    }
}