merge maps

.gitignore

test
*.gch
*.o
tags
.depends

adhoc.hpp

#pragma once
#include <iostream>

/**************************************************************************
 * a simple test value struct to show that you can in fact store anything *
 **************************************************************************/
struct adhoc
{
    const char* hello;
};

static std::ostream& operator<<(std::ostream& os, const adhoc& a)
{
    return os << "{ \"" << a.hello << "\" }";
}

dump_data.hpp

#pragma once

#include <boost/optional.hpp>
#include <boost/any.hpp>       // only required for value_strategies::as_any

#include <iostream> 
#include <iomanip>
#include <sstream>

#include "adhoc.hpp"

struct dumpmap
{
    std::ostream& os;
    dumpmap(std::ostream& s) : os(s) { }

    template <typename K, typename V>
    std::ostream& operator()(const std::map<K,V>& map) const 
    { 
        std::stringstream ss;
        ss << std::boolalpha << std::showpoint;
        for (const auto& pair : map)
        {
            ss.str("");
            ss << "{ " << pair.first << ", " << pair.second << " }";

            os << std::setw(16) << std::left << ss.str();
        }

        return os << std::endl;
    }
};

struct dumpmerged // display merged iterators
{
    std::ostream& os;
    dumpmerged(std::ostream& s) : os(s) { }

    template <typename MergedIt>
    std::ostream& operator()(MergedIt& mit) const
    {
        dumpkey(os, mit->first); os << ": "; dumpvalue(os, mit->second); os << std::endl;
		return os;
    }

private:
    template <typename K> static void dumpkey(std::ostream& os, const K& key)
		{ os << std::right << std::setw(6) << key; }
    template <typename Sequence> static void dumpvalue(std::ostream& os, const Sequence& sequence)
		{ boost::fusion::for_each(sequence, dump_element(os)); }
	static void dumpvalue(std::ostream& os, const boost::any& v)
#define ANY_CAST(typ) do try { const auto& x=boost::any_cast<typ>(v); os<<"any_cast<" #typ ">():"<< x; ok=true; } catch(...) {} while (false)
		{ 
			bool ok=false;
			ANY_CAST(adhoc);  ANY_CAST(bool);   ANY_CAST(char);        ANY_CAST(const char*);
			ANY_CAST(double); ANY_CAST(size_t); ANY_CAST(std::string);
			if (!ok) os << "any_cast<?>():<unknown>";
		}

	struct dump_element
	{
		std::ostream& os;
		dump_element(std::ostream& s) : os(s) { }

		void operator()(const char* const value) const
			{ operator()(std::string(value? value : "<nullstr>")); }
		template <typename T> void operator()(boost::optional<T> value) const
			{ if (!value) operator()("<none>"); else operator()(*value); }
		template <typename V> void operator()(V* value) const
			{ if (!value) operator()("<nullptr>"); else operator()(*value); }
       
		// interprets what we don't cover (nested fusion sequences, STL containers etc)
		template <typename V> void operator()(V value) const
			{ 
                os << std::boolalpha << std::showpoint << value << "\t";
            }
	};
};

Makefile

all: test

CPPFLAGS+=-O0 -g
CPPFLAGS+=-DNDEBUG
CPPFLAGS+=--std=c++0x
CPPFLAGS+=-I ~/custom/boost_1_47_0/

test: | .depends

%.o: %.cpp
	g++ $(CPPFLAGS) -c $< -o $@

%: %.o
	g++ $^ -o $@

.depends: *.cpp
	g++ $(CPPFLAGS) -M $^ > $@

-include .depends

merge_maps_iterator.hpp

#ifndef MERGE_MAPS_ITERATOR
#define MERGE_MAPS_ITERATOR

#define BOOST_RESULT_OF_USE_DECLTYPE

#include <boost/mpl/greater_equal.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/fusion/include/tuple_tie.hpp>
#include <boost/fusion/include/transform.hpp>
#include <boost/fusion/include/for_each.hpp>
#include <boost/fusion/include/std_pair.hpp>
#include <boost/fusion/include/vector.hpp>

#include <boost/utility/enable_if.hpp>
#include <boost/type_traits.hpp>
#include <boost/any.hpp>       // only required for value_strategies::as_any
#include <boost/optional.hpp>
#include <map>

#define ITERATE_KEY_ORDER true

namespace detail
{
    namespace internal_mpl
    {
        template <template<typename> class Trait>
            struct apply_trait_f{ template <class T> struct apply { typedef typename Trait<T>::type type; }; };

        typedef apply_trait_f<boost::remove_reference> remove_ref_f;
        typedef apply_trait_f<boost::add_pointer> make_pointer;
        //struct remove_ref_f { template <class T> struct apply { typedef typename boost::remove_reference<T>::type type; }; };
        struct mapped_typ_f { template <class T> struct apply { typedef typename T::mapped_type type; }; };
        struct key_type_f   { template <class T> struct apply { typedef typename boost::remove_const<typename T::key_type>::type type; }; };
        struct iterator_f   { template <class T> struct apply { typedef typename T::iterator type; }; };
        struct make_optional{ template <class T> struct apply { typedef typename boost::optional<T> type; }; };
        struct make_ref_opt { template <class T> struct apply { typedef typename boost::optional<T&> type; }; };
        struct common_typ_f { template <class T, class U> 
                                                 struct apply { typedef typename boost::common_type<T,U>::type type; }; };
    }

    namespace internal_fusion
    {
        struct begin_f
            { template <typename T> auto operator()(T& t) const -> decltype(t.begin()) { return t.begin(); } };
        struct end_f
            { template <typename T> auto operator()(T& t) const -> decltype(t.end())   { return t.end(); } };
    }

    namespace value_strategies
    {
        struct as_pointers_tag {};
        struct as_optionals_tag {};
        struct as_ref_optionals_tag {};
        struct as_any_tag {};

        template <typename Values> struct as_pointers {
            typedef typename boost::mpl::transform<Values, internal_mpl::make_pointer>::type exposed;
            template <int pos, typename T> static void Assign(exposed& to, T& v) 
                { boost::fusion::at_c<pos>(to) = &v; }
        };
        template <typename Values> struct as_ref_optionals {
            typedef typename boost::mpl::transform<Values, internal_mpl::make_ref_opt>::type exposed;
            template <int pos, typename T> static void Assign(exposed& to, T& v) 
                { boost::fusion::at_c<pos>(to) = v; }
        };
        template <typename Values> struct as_optionals {
            typedef typename boost::mpl::transform<Values, internal_mpl::make_optional>::type exposed;
            template <int pos, typename T> static void Assign(exposed& to, T const& v) 
                { boost::fusion::at_c<pos>(to) = v; }
        };
        template <typename Values> struct as_any {
            typedef typename boost::any exposed;
            template <int /*pos*/, typename T> static void Assign(exposed& to, T const& v) 
                { to = v; } 
        };
    }

    template <
            typename Tuple, 
            template<typename> class VS=value_strategies::as_optionals
        > struct maps_iterator
    {
        typedef typename boost::mpl::transform<Tuple,  internal_mpl::remove_ref_f>::type maps_t;
        typedef typename boost::mpl::transform<maps_t, internal_mpl::key_type_f>::type   keytypes_t;

        typedef typename boost::mpl::fold<
            keytypes_t, 
            typename boost::mpl::at_c<keytypes_t, 0>::type,
            internal_mpl::common_typ_f>::type common_key_t; // TODO assert common_type sane?

        typedef typename boost::mpl::transform<maps_t, internal_mpl::mapped_typ_f>::type datatypes_t;
        typedef typename boost::mpl::transform<maps_t, internal_mpl::iterator_f>::type   iterators_t;
        
        typedef typename VS<datatypes_t>::exposed                       mapped_type;
        typedef typename std::pair</*const */common_key_t, mapped_type> value_type; // TODO protect key assignment

        maps_iterator(const Tuple& tiedmaps) : _is_end_iterator(false)
        { 
            _it      = boost::fusion::transform(tiedmaps, internal_fusion::begin_f());
            _end     = boost::fusion::transform(tiedmaps, internal_fusion::end_f());

            ++(*this);
        }

        // TODO make available otherwise (integrate with Boost Range?)
        const maps_iterator end() const { return maps_iterator(); }

        value_type operator*()
        {
            return *partial;                
        }

        value_type* operator->()
        {
            return &*partial;
        }

        bool operator==(const maps_iterator& other) const 
        {
            assert(other._is_end_iterator | _is_end_iterator); 
            return _is_end_iterator && other._is_end_iterator; 
        }

        bool operator!=(const maps_iterator& other) const 
        {
            return !(operator==(other));
        }

        maps_iterator& operator++()
        {
            partial.reset();
            increment_helper(_it, _end, partial);
            _is_end_iterator = !partial;
            return *this; 
        }

      private:
        explicit maps_iterator() : _is_end_iterator(true) { }

        template <typename ItSeq, int pos = 0>
            typename boost::enable_if<boost::mpl::greater_equal<boost::mpl::int_<pos>, typename boost::fusion::result_of::size<ItSeq>::type > >::type*
            find_min_key(const ItSeq&, const ItSeq&, boost::optional<common_key_t>&)
            { return 0; /* end recursion */ }

        template <typename ItSeq, int pos = 0>
            typename boost::enable_if<boost::mpl::less<boost::mpl::int_<pos>, typename boost::fusion::result_of::size<ItSeq>::type > >::type*
            find_min_key(const ItSeq& it, const ItSeq& end, boost::optional<common_key_t>& minkey)
            {
                //if (it == end) return 0;

                auto& posit   = boost::fusion::at_c<pos>(it);
                auto& posend  = boost::fusion::at_c<pos>(end);

                if (posit != posend) // disqualify already or depleted
                {
                    auto poskey = posit->first;
                    if (!minkey || common_key_t(poskey) < *minkey) // locally attempt to mimic std::less<common_key_t>
                        minkey = poskey;
                }

                return find_min_key<ItSeq, pos+1>(it, end, minkey);
            }

        template <typename ItSeq, int pos = 0>
            typename boost::enable_if<boost::mpl::greater_equal<boost::mpl::int_<pos>, typename boost::fusion::result_of::size<ItSeq>::type > >::type*
            increment_helper(const ItSeq&, const ItSeq&, boost::optional<value_type>&)
            { return 0; /* end recursion */ }

        template <typename ItSeq, int pos = 0>
            typename boost::enable_if<boost::mpl::less<boost::mpl::int_<pos>, typename boost::fusion::result_of::size<ItSeq>::type > >::type*
            increment_helper(ItSeq& it, ItSeq& end, boost::optional<value_type>& partial)
        {
            assert(pos < boost::fusion::size(end)); // check the enable_if
            assert(boost::fusion::size(it)      == boost::fusion::size(end));

            auto& posit   = boost::fusion::at_c<pos>(it);
            auto& posend  = boost::fusion::at_c<pos>(end);

            if (posit == posend) // depleted map, consider only tail maps
                return increment_helper<ItSeq, pos+1>(it, end, partial);

            if (!partial)
            {
                boost::optional<common_key_t> minkey;
                find_min_key<ItSeq, pos>(it, end, minkey);
                
                if (!minkey)
                    return 0;

                // pre seed with the desired lowest next key
                partial = std::make_pair(*minkey, mapped_type());
            }

            if (posend != posit) // data available in map[pos]
            {
                auto poskey = posit->first;

                // can key be merged?
                // relying on consistent weak total ordering of keys in all maps
                if (!(partial->first < poskey) && !(poskey < partial->first))
                {
                    // set the current positional data element
                    auto& value = (posit++)->second;
                    VS<datatypes_t>::template Assign<pos, decltype(value)>(partial->second, value);

                    // verify that the iterators were tied to the tuples (both got updated)
                    assert(posit == boost::fusion::at_c<pos>(it));
                }
            }

            // recurse finding matching entries in tail maps
            return increment_helper<ItSeq, pos+1>(it, end, partial);
        }

        boost::optional<value_type> partial;
        iterators_t _it, _end;
        bool _is_end_iterator;
    };
}

template <
        typename Tuple, 
        template<typename> class ValueStrategy=detail::value_strategies::as_ref_optionals > 
    detail::maps_iterator<Tuple, ValueStrategy> 
        merge_maps_iterator(const Tuple& maps)
{
    return detail::maps_iterator<Tuple, ValueStrategy>(maps);
}

#endif // MERGE_MAPS_ITERATOR

test.cpp

#include "merge_maps_iterator.hpp"
#include "dump_data.hpp"
#include "adhoc.hpp"

struct runner
{
    template <class MapTuple> void operator()(const MapTuple& maps) const
    {
        std::cout << std::endl;

        // display the input
        std::cout << " == input =" << std::string(39, '=') << std::endl;
        boost::fusion::for_each(maps, dumpmap(std::cout));

        // display the output
        std::cout << " == output " << std::string(39, '=') << std::endl;
        for (auto mit = merge_maps_iterator(maps); mit != mit.end()/*should move to range concept*/; ++mit)
        {
			auto dumper = dumpmerged(std::cout);
			dumper(mit);
        }
    }
};

template <int index>
struct ElemAccess
{
	// for the AsAny case:
	boost::any& operator()(boost::any& dst) const          { return dst; }
	// for the AsRefOptionals, AsOptionals, AsPointers cases:
	template <typename T> auto operator()(T& sequence) const 
		-> decltype(*boost::fusion::at_c<index>(sequence)) { return *boost::fusion::at_c<index>(sequence); }
};

/////////////////////////////////////////////////////////////
// MAIN
//
int main()
{
    std::cout << std::boolalpha << std::showpoint << std::unitbuf;

    std::map<size_t, std::string>  m1 = { { 2, "the" }, { 100, "cow" }, { 23, "jumped" }, { 101, "moon" } };
    std::map<char, double>         m2 = { { 'b', 3.14  } /* , { 22, 69.08  }, { 11, 72.22  } */ };

    runner test;
    test(boost::fusion::tie(m1, m2));
    test(boost::fusion::tie(m2, m1));

    std::map<unsigned short, bool> m3 = { { 1, true  }, { 22, false  }, { 24, true   } };
    std::map<float, bool> m4          = { { 1.0, true  }, { 22.01, false  }, { -24, true   } };

    test(boost::fusion::tie(m3, m4));

    std::map<std::string, adhoc>   m5 = { { "NL", { "dag" } }, { "EN", { "bye" } }, { "DE", { "Tschüß" } } };
    std::map<std::string, adhoc>   m6 = { { "FR", { "au revoir" } }, { "IT", { "ciao" } }, { "ES", { "adiós" } } };
    std::map<std::string, adhoc>   m7 = { { "FR", { "merci" } }, { "IT", { "grazie" } }, { "ES", { "gracias" } } };

    auto maps = boost::fusion::tie(m5, m6, m7);

	auto it = ++++merge_maps_iterator(maps);
	auto value_tuple = it->second;

	dumpmerged(std::cout << "points to: ")(it);

	ElemAccess<1> access;
    access(value_tuple) = adhoc { "¡¿Ola?!" };

	dumpmerged(std::cout << "modified to: ")(it);

	test(maps); // see that the above edit worked all the way through to the underlying source map(s)

    return 0;
}