[ceph.git] / ceph / src / boost / libs / icl / include / boost / icl / split_interval_map.hpp

/*-----------------------------------------------------------------------------+
Copyright (c) 2007-2012: Joachim Faulhaber
Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
+------------------------------------------------------------------------------+
   Distributed under the Boost Software License, Version 1.0.
      (See accompanying file LICENCE.txt or copy at
           http://www.boost.org/LICENSE_1_0.txt)
+-----------------------------------------------------------------------------*/
#ifndef BOOST_ICL_SPLIT_INTERVAL_MAP_HPP_JOFA_000706
#define BOOST_ICL_SPLIT_INTERVAL_MAP_HPP_JOFA_000706

#include <boost/icl/interval_set.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/icl/interval_base_map.hpp>
#include <boost/icl/split_interval_set.hpp>

namespace boost{namespace icl
{

/** \brief implements a map as a map of intervals - on insertion 
    overlapping intervals are split and associated values are combined. */
template
<
    typename DomainT,
    typename CodomainT,
    class Traits = icl::partial_absorber,
    ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
    ICL_COMBINE Combine  = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
    ICL_SECTION Section  = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT), 
    ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
    ICL_ALLOC   Alloc    = std::allocator
>
class split_interval_map:
    public interval_base_map<split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 
                             DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
{
public:
    typedef Traits traits;
    typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
    typedef       interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> joint_type;
    typedef type overloadable_type;

    typedef interval_base_map <type, 
                               DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;

    typedef DomainT domain_type;
    typedef CodomainT codomain_type;
    typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
    typedef typename base_type::iterator iterator;
    typedef typename base_type::value_type value_type;
    typedef typename base_type::element_type element_type;
    typedef typename base_type::segment_type segment_type;
    typedef typename base_type::domain_mapping_type    domain_mapping_type;
    typedef typename base_type::interval_mapping_type  interval_mapping_type;
    typedef typename base_type::ImplMapT ImplMapT;

    typedef typename base_type::codomain_combine codomain_combine;

    typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
    typedef interval_set_type set_type;
    typedef set_type          key_object_type;

    enum { fineness = 3 };

public:
    //==========================================================================
    //= Construct, copy, destruct
    //==========================================================================
    /// Default constructor for the empty object
    split_interval_map(): base_type() {}

    /// Copy constructor
    split_interval_map(const split_interval_map& src): base_type(src) {}

    explicit split_interval_map(const domain_mapping_type& base_pair): base_type()
    { this->add(base_pair); }

    explicit split_interval_map(const value_type& value_pair): base_type()
    { this->add(value_pair); }

    /// Assignment from a base interval_map.
    template<class SubType>
    void assign(const interval_base_map<SubType,DomainT,CodomainT,
                                        Traits,Compare,Combine,Section,Interval,Alloc>& src)
    {
        this->clear();
        this->_map.insert(src.begin(), src.end());
    }

    /// Assignment operator for base type
    template<class SubType>
    split_interval_map& operator =
        (const interval_base_map<SubType,DomainT,CodomainT,
                                 Traits,Compare,Combine,Section,Interval,Alloc>& src)
    { 
        this->assign(src); 
        return *this; 
    }

#   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
    //==========================================================================
    //= Move semantics
    //==========================================================================

    /// Move constructor
    split_interval_map(split_interval_map&& src)
        : base_type(boost::move(src))
    {}

    /// Move assignment operator
    split_interval_map& operator = (split_interval_map src)
    { 
        base_type::operator=(boost::move(src));
        return *this;
    }

    //==========================================================================
#   else

    /// Assignment operator
    split_interval_map& operator = (const split_interval_map& src)
    { 
        base_type::operator=(src);
        return *this;
    }

#   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES

private:
    // Private functions that shall be accessible by the baseclass:
    friend class
        interval_base_map <split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 
                                              DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;

    iterator handle_inserted(iterator it_)const { return it_; }
    void handle_inserted(iterator, iterator)const{ }

    template<class Combiner>
    void handle_left_combined(iterator it_)
    {
        if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
            this->_map.erase(it_);
    }

    template<class Combiner>
    void handle_combined(iterator it_)
    {
        if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
            this->_map.erase(it_);
    }

    template<class Combiner>
    void handle_preceeded_combined(iterator prior_, iterator& it_)
    {
        if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
        {
            this->_map.erase(it_);
            it_ = prior_;
        }
    }

    template<class Combiner>
    void handle_succeeded_combined(iterator it_, iterator)
    {
        if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
            this->_map.erase(it_);
    }

    void handle_reinserted(iterator){}

    template<class Combiner>
    void gap_insert_at(iterator& it_, iterator prior_, 
                       const interval_type& end_gap, const codomain_type& co_val)
    {
        if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
        {
            this->_map.erase(it_);
            it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
        }
        else
            it_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
    }
} ;

//-----------------------------------------------------------------------------
// type traits
//-----------------------------------------------------------------------------
template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct is_map<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{ 
    typedef is_map<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
    BOOST_STATIC_CONSTANT(bool, value = true); 
};

template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct has_inverse<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{ 
    typedef has_inverse<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
    BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 
};

template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct is_interval_container<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{ 
    typedef is_interval_container<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
    BOOST_STATIC_CONSTANT(bool, value = true); 
};

template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct is_interval_splitter<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{ 
    typedef is_interval_splitter<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
    BOOST_STATIC_CONSTANT(bool, value = true); 
};

template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct absorbs_identities<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{ 
    typedef absorbs_identities<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
    BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities)); 
};

template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct is_total<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{ 
    typedef is_total<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
    BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total)); 
};


template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
struct type_to_string<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{
    static std::string apply()
    { 
        return "sp_itv_map<"+ type_to_string<DomainT>::apply()   + ","
                            + type_to_string<CodomainT>::apply() + ","
                            + type_to_string<Traits>::apply()    +">"; 
    }
};

}} // namespace icl boost

#endif
Commit	Line	Data
7c673cae FG	1	/*-----------------------------------------------------------------------------+
	2	Copyright (c) 2007-2012: Joachim Faulhaber
	3	Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
	4	+------------------------------------------------------------------------------+
	5	Distributed under the Boost Software License, Version 1.0.
	6	(See accompanying file LICENCE.txt or copy at
	7	http://www.boost.org/LICENSE_1_0.txt)
	8	+-----------------------------------------------------------------------------*/
	9	#ifndef BOOST_ICL_SPLIT_INTERVAL_MAP_HPP_JOFA_000706
	10	#define BOOST_ICL_SPLIT_INTERVAL_MAP_HPP_JOFA_000706
	11
	12	#include <boost/icl/interval_set.hpp>
	13	#include <boost/icl/interval_map.hpp>
	14	#include <boost/icl/interval_base_map.hpp>
	15	#include <boost/icl/split_interval_set.hpp>
	16
	17	namespace boost{namespace icl
	18	{
	19
	20	/** \brief implements a map as a map of intervals - on insertion
	21	overlapping intervals are split and associated values are combined. */
	22	template
	23	<
	24	typename DomainT,
	25	typename CodomainT,
	26	class Traits = icl::partial_absorber,
	27	ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
	28	ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
	29	ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
	30	ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
	31	ICL_ALLOC Alloc = std::allocator
	32	>
	33	class split_interval_map:
	34	public interval_base_map<split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
	35	DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
	36	{
	37	public:
	38	typedef Traits traits;
	39	typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
	40	typedef interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> joint_type;
	41	typedef type overloadable_type;
	42
	43	typedef interval_base_map <type,
	44	DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
	45
	46	typedef DomainT domain_type;
	47	typedef CodomainT codomain_type;
	48	typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
	49	typedef typename base_type::iterator iterator;
	50	typedef typename base_type::value_type value_type;
	51	typedef typename base_type::element_type element_type;
	52	typedef typename base_type::segment_type segment_type;
	53	typedef typename base_type::domain_mapping_type domain_mapping_type;
	54	typedef typename base_type::interval_mapping_type interval_mapping_type;
	55	typedef typename base_type::ImplMapT ImplMapT;
	56
	57	typedef typename base_type::codomain_combine codomain_combine;
	58
	59	typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
	60	typedef interval_set_type set_type;
	61	typedef set_type key_object_type;
	62
	63	enum { fineness = 3 };
	64
65	public:
66	//==========================================================================
67	//= Construct, copy, destruct
68	//==========================================================================
69	/// Default constructor for the empty object
70	split_interval_map(): base_type() {}
71
72	/// Copy constructor
73	split_interval_map(const split_interval_map& src): base_type(src) {}
74
75	explicit split_interval_map(const domain_mapping_type& base_pair): base_type()
76	{ this->add(base_pair); }
77
78	explicit split_interval_map(const value_type& value_pair): base_type()
79	{ this->add(value_pair); }
80
81	/// Assignment from a base interval_map.
82	template<class SubType>
83	void assign(const interval_base_map<SubType,DomainT,CodomainT,
84	Traits,Compare,Combine,Section,Interval,Alloc>& src)
85	{
86	this->clear();
87	this->_map.insert(src.begin(), src.end());
88	}
89
90	/// Assignment operator for base type
91	template<class SubType>
92	split_interval_map& operator =
93	(const interval_base_map<SubType,DomainT,CodomainT,
94	Traits,Compare,Combine,Section,Interval,Alloc>& src)
95	{
96	this->assign(src);
97	return *this;
98	}
99
100	# ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
101	//==========================================================================
102	//= Move semantics
103	//==========================================================================
104
105	/// Move constructor
106	split_interval_map(split_interval_map&& src)
107	: base_type(boost::move(src))
108	{}
109
110	/// Move assignment operator
111	split_interval_map& operator = (split_interval_map src)
112	{
113	base_type::operator=(boost::move(src));
114	return *this;
115	}
116
117	//==========================================================================
118	# else
119
120	/// Assignment operator
121	split_interval_map& operator = (const split_interval_map& src)
122	{
123	base_type::operator=(src);
124	return *this;
125	}
126
127	# endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
128
129	private:
130	// Private functions that shall be accessible by the baseclass:
131	friend class
132	interval_base_map <split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
133	DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
134
135	iterator handle_inserted(iterator it_)const { return it_; }
136	void handle_inserted(iterator, iterator)const{ }
137
138	template<class Combiner>
139	void handle_left_combined(iterator it_)
140	{
141	if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
142	this->_map.erase(it_);
143	}
144
145	template<class Combiner>
146	void handle_combined(iterator it_)
147	{
148	if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
149	this->_map.erase(it_);
150	}
151
152	template<class Combiner>
153	void handle_preceeded_combined(iterator prior_, iterator& it_)
154	{
155	if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
156	{
157	this->_map.erase(it_);
158	it_ = prior_;
159	}
160	}
161
162	template<class Combiner>
163	void handle_succeeded_combined(iterator it_, iterator)
164	{
165	if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
166	this->_map.erase(it_);
167	}
168
169	void handle_reinserted(iterator){}
170
171	template<class Combiner>
172	void gap_insert_at(iterator& it_, iterator prior_,
173	const interval_type& end_gap, const codomain_type& co_val)
174	{
175	if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
176	{
177	this->_map.erase(it_);
178	it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
179	}
180	else
181	it_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
182	}
183	} ;
184
185	//-----------------------------------------------------------------------------
186	// type traits
187	//-----------------------------------------------------------------------------
188	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
189	struct is_map<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
190	{
191	typedef is_map<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
192	BOOST_STATIC_CONSTANT(bool, value = true);
193	};
194
195	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
196	struct has_inverse<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
197	{
198	typedef has_inverse<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
199	BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value));
200	};
201
202	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
203	struct is_interval_container<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
204	{
205	typedef is_interval_container<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
206	BOOST_STATIC_CONSTANT(bool, value = true);
207	};
208
209	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
210	struct is_interval_splitter<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
211	{
212	typedef is_interval_splitter<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
213	BOOST_STATIC_CONSTANT(bool, value = true);
214	};
215
216	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
217	struct absorbs_identities<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
218	{
219	typedef absorbs_identities<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
220	BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities));
221	};
222
223	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
224	struct is_total<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
225	{
226	typedef is_total<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
227	BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total));
228	};
229
230
231	template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
232	struct type_to_string<icl::split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
233	{
234	static std::string apply()
235	{
236	return "sp_itv_map<"+ type_to_string<DomainT>::apply() + ","
237	+ type_to_string<CodomainT>::apply() + ","
238	+ type_to_string<Traits>::apply() +">";
239	}
240	};
241
242	}} // namespace icl boost
243
244	#endif
245
246