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

/*-----------------------------------------------------------------------------+
Copyright (c) 2008-2009: Joachim Faulhaber
+------------------------------------------------------------------------------+
   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_SUBSET_COMPARER_HPP_JOFA_090202
#define BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202

#include <boost/mpl/and.hpp>
#include <boost/icl/type_traits/is_map.hpp>
#include <boost/icl/detail/notate.hpp>
#include <boost/icl/detail/relation_state.hpp>
#include <boost/icl/type_traits/identity_element.hpp>
#include <boost/icl/type_traits/codomain_type_of.hpp>
#include <boost/icl/type_traits/is_concept_equivalent.hpp>
#include <boost/icl/type_traits/is_element_container.hpp>
#include <boost/icl/concept/interval_set_value.hpp>
#include <boost/icl/concept/map_value.hpp>

namespace boost{namespace icl
{

#ifdef BOOST_MSVC 
#pragma warning(push)
#pragma warning(disable:4127) // conditional expression is constant
#endif                        

namespace Set
{

//------------------------------------------------------------------------------
template<class LeftT, class RightT>
struct settic_codomain_compare
{
    static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
    {
        return inclusion_compare( co_value<LeftT>(left_), 
                                 co_value<RightT>(right_));
    }
};

template<class LeftT, class RightT>
struct atomic_codomain_compare
{
    static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
    {
        if(co_value<LeftT>(left_) == co_value<RightT>(right_))
            return inclusion::equal;
        else
            return inclusion::unrelated;
    }
};

template<class LeftT, class RightT>
struct empty_codomain_compare
{
    static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator&)
    {
        return inclusion::equal;
    }
};

template<class LeftT, class RightT>
struct map_codomain_compare
{
    static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
    {
        using namespace boost::mpl;
        typedef typename LeftT::codomain_type  LeftCodomainT;
        typedef typename RightT::codomain_type RightCodomainT;

        return
            if_<
                bool_<is_concept_equivalent<is_set,LeftCodomainT,
                                                   RightCodomainT>::value>,
                settic_codomain_compare<LeftT,RightT>,
                atomic_codomain_compare<LeftT,RightT>
            >
            ::type::apply(left_, right_);
    }
};


//------------------------------------------------------------------------------
template<class LeftT, class RightT>
class subset_comparer
{
private:
    subset_comparer& operator = (const subset_comparer&);
public:
    typedef typename LeftT::const_iterator  LeftIterT;
    typedef typename RightT::const_iterator RightIterT;

    BOOST_STATIC_CONSTANT(bool, 
        _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value)); 

    subset_comparer(const LeftT&      left,
                    const RightT&     right,
                    const LeftIterT&  left_end,
                    const RightIterT& right_end)
        : _left(left), _right(right),
          _left_end(left_end), _right_end(right_end), _result(equal)
    {}

    enum{nextboth, stop};

    enum
    {
        unrelated  = inclusion::unrelated, 
        subset     = inclusion::subset,     // left is_subset_of   right 
        superset   = inclusion::superset,   // left is_superset_of right
        equal      = inclusion::equal       // equal = subset | superset
    };

    int result()const{ return _result; }

    int co_compare(LeftIterT& left, RightIterT& right)
    {
        using namespace boost::mpl;
        //CL typedef typename codomain_type_of<LeftT>::type  LeftCodomainT;
        //CL typedef typename codomain_type_of<RightT>::type RightCodomainT;

        return  
            if_<
                bool_<is_concept_equivalent<is_element_map,LeftT,RightT>::value>,
                map_codomain_compare<LeftT,RightT>,
                empty_codomain_compare<LeftT,RightT>
            >
            ::type::apply(left,right);
    }

    int restrict_result(int state) { return _result &= state; }

    int next_both(LeftIterT& left, RightIterT& right)
    {
        if(left == _left_end && right == _right_end)
            return stop;
        else if(left == _left_end)
        {
            restrict_result(subset);
            return stop;
        }
        else if(right == _right_end)
        {
            restrict_result(superset);
            return stop;
        }
        else if(typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(right)))
        {   // left:  *left . . *joint_     left could be superset
            // right:           *right ...  if joint_ exists
            restrict_result(superset);
            if(unrelated == _result)
                return stop;
            else
            {
                LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
                if(    joint_ == _left.end() 
                    || typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(joint_)))
                {
                    _result = unrelated;
                    return stop;
                }
                else
                    left = joint_;
            }
        }
        else if(typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(left)))
        {   // left:             *left   left could be subset
            // right:*right . . .*joint_ if *joint_ exists 
            restrict_result(subset);
            if(unrelated == _result)
                return stop;
            else
            {
                RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
                if(    joint_ == _right.end()
                    || typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(joint_)))
                {
                    _result = unrelated;
                    return stop;
                }
                else
                    right = joint_;
            }
        }

        // left =key= right 
        if(_compare_codomain)
            if(unrelated == restrict_result(co_compare(left,right)))
                return stop;

        ++left;
        ++right;
        return nextboth;
    }

private:
    const LeftT&  _left;
    const RightT& _right;
    LeftIterT     _left_end;
    RightIterT    _right_end;
    int           _result;
};


//------------------------------------------------------------------------------
// Subset/superset comparison on ranges of two interval container 
//------------------------------------------------------------------------------
template<class LeftT, class RightT>
int subset_compare
(
    const LeftT& left,   //sub
    const RightT& right, //super
    typename LeftT::const_iterator  left_begin,   
    typename LeftT::const_iterator  left_end,
    typename RightT::const_iterator right_begin, 
    typename RightT::const_iterator right_end
)
{
    typedef subset_comparer<LeftT,RightT> Step;
    Step step(left, right, left_end, right_end);

    typename LeftT::const_iterator  left_  = left_begin;
    typename RightT::const_iterator right_ = right_begin;

    int state = Step::nextboth;
    while(state != Step::stop)
        state = step.next_both(left_, right_);

    return step.result();
}

template<class LeftT, class RightT>
int subset_compare(const LeftT& left, const RightT& right)
{
    return subset_compare
        (
            left, right,
            left.begin(), left.end(),
            right.begin(), right.end()
        );
}


} // namespace Set
    
#ifdef BOOST_MSVC
#pragma warning(pop)
#endif

}} // namespace icl boost

#endif
Commit	Line	Data
7c673cae FG	1	/*-----------------------------------------------------------------------------+
	2	Copyright (c) 2008-2009: Joachim Faulhaber
	3	+------------------------------------------------------------------------------+
	4	Distributed under the Boost Software License, Version 1.0.
	5	(See accompanying file LICENCE.txt or copy at
	6	http://www.boost.org/LICENSE_1_0.txt)
	7	+-----------------------------------------------------------------------------*/
	8	#ifndef BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
	9	#define BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
	10
	11	#include <boost/mpl/and.hpp>
	12	#include <boost/icl/type_traits/is_map.hpp>
	13	#include <boost/icl/detail/notate.hpp>
	14	#include <boost/icl/detail/relation_state.hpp>
	15	#include <boost/icl/type_traits/identity_element.hpp>
	16	#include <boost/icl/type_traits/codomain_type_of.hpp>
	17	#include <boost/icl/type_traits/is_concept_equivalent.hpp>
	18	#include <boost/icl/type_traits/is_element_container.hpp>
	19	#include <boost/icl/concept/interval_set_value.hpp>
	20	#include <boost/icl/concept/map_value.hpp>
	21
	22	namespace boost{namespace icl
	23	{
	24
	25	#ifdef BOOST_MSVC
	26	#pragma warning(push)
	27	#pragma warning(disable:4127) // conditional expression is constant
	28	#endif
	29
	30	namespace Set
	31	{
	32
	33	//------------------------------------------------------------------------------
	34	template<class LeftT, class RightT>
	35	struct settic_codomain_compare
	36	{
	37	static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
	38	{
	39	return inclusion_compare( co_value<LeftT>(left_),
	40	co_value<RightT>(right_));
	41	}
	42	};
	43
	44	template<class LeftT, class RightT>
	45	struct atomic_codomain_compare
	46	{
	47	static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
	48	{
	49	if(co_value<LeftT>(left_) == co_value<RightT>(right_))
	50	return inclusion::equal;
	51	else
	52	return inclusion::unrelated;
	53	}
	54	};
	55
	56	template<class LeftT, class RightT>
	57	struct empty_codomain_compare
	58	{
	59	static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator&)
	60	{
	61	return inclusion::equal;
	62	}
	63	};
	64
65	template<class LeftT, class RightT>
66	struct map_codomain_compare
67	{
68	static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
69	{
70	using namespace boost::mpl;
71	typedef typename LeftT::codomain_type LeftCodomainT;
72	typedef typename RightT::codomain_type RightCodomainT;
73
74	return
75	if_<
76	bool_<is_concept_equivalent<is_set,LeftCodomainT,
77	RightCodomainT>::value>,
78	settic_codomain_compare<LeftT,RightT>,
79	atomic_codomain_compare<LeftT,RightT>
80	>
81	::type::apply(left_, right_);
82	}
83	};
84
85
86	//------------------------------------------------------------------------------
87	template<class LeftT, class RightT>
88	class subset_comparer
89	{
90	private:
91	subset_comparer& operator = (const subset_comparer&);
92	public:
93	typedef typename LeftT::const_iterator LeftIterT;
94	typedef typename RightT::const_iterator RightIterT;
95
96	BOOST_STATIC_CONSTANT(bool,
97	_compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
98
99	subset_comparer(const LeftT& left,
100	const RightT& right,
101	const LeftIterT& left_end,
102	const RightIterT& right_end)
103	: _left(left), _right(right),
104	_left_end(left_end), _right_end(right_end), _result(equal)
105	{}
106
107	enum{nextboth, stop};
108
109	enum
110	{
111	unrelated = inclusion::unrelated,
112	subset = inclusion::subset, // left is_subset_of right
113	superset = inclusion::superset, // left is_superset_of right
114	equal = inclusion::equal // equal = subset \| superset
115	};
116
117	int result()const{ return _result; }
118
119	int co_compare(LeftIterT& left, RightIterT& right)
120	{
121	using namespace boost::mpl;
122	//CL typedef typename codomain_type_of<LeftT>::type LeftCodomainT;
123	//CL typedef typename codomain_type_of<RightT>::type RightCodomainT;
124
125	return
126	if_<
127	bool_<is_concept_equivalent<is_element_map,LeftT,RightT>::value>,
128	map_codomain_compare<LeftT,RightT>,
129	empty_codomain_compare<LeftT,RightT>
130	>
131	::type::apply(left,right);
132	}
133
134	int restrict_result(int state) { return _result &= state; }
135
136	int next_both(LeftIterT& left, RightIterT& right)
137	{
138	if(left == _left_end && right == _right_end)
139	return stop;
140	else if(left == _left_end)
141	{
142	restrict_result(subset);
143	return stop;
144	}
145	else if(right == _right_end)
146	{
147	restrict_result(superset);
148	return stop;
149	}
150	else if(typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(right)))
151	{ // left: left . . joint_ left could be superset
152	// right: *right ... if joint_ exists
153	restrict_result(superset);
154	if(unrelated == _result)
155	return stop;
156	else
157	{
158	LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
159	if( joint_ == _left.end()
160	\|\| typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(joint_)))
161	{
162	_result = unrelated;
163	return stop;
164	}
165	else
166	left = joint_;
167	}
168	}
169	else if(typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(left)))
170	{ // left: *left left could be subset
171	// right:right . . .joint_ if *joint_ exists
172	restrict_result(subset);
173	if(unrelated == _result)
174	return stop;
175	else
176	{
177	RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
178	if( joint_ == _right.end()
179	\|\| typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(joint_)))
180	{
181	_result = unrelated;
182	return stop;
183	}
184	else
185	right = joint_;
186	}
187	}
188
189	// left =key= right
190	if(_compare_codomain)
191	if(unrelated == restrict_result(co_compare(left,right)))
192	return stop;
193
194	++left;
195	++right;
196	return nextboth;
197	}
198
199	private:
200	const LeftT& _left;
201	const RightT& _right;
202	LeftIterT _left_end;
203	RightIterT _right_end;
204	int _result;
205	};
206
207
208
209
210
211	//------------------------------------------------------------------------------
212	// Subset/superset comparison on ranges of two interval container
213	//------------------------------------------------------------------------------
214	template<class LeftT, class RightT>
215	int subset_compare
216	(
217	const LeftT& left, //sub
218	const RightT& right, //super
219	typename LeftT::const_iterator left_begin,
220	typename LeftT::const_iterator left_end,
221	typename RightT::const_iterator right_begin,
222	typename RightT::const_iterator right_end
223	)
224	{
225	typedef subset_comparer<LeftT,RightT> Step;
226	Step step(left, right, left_end, right_end);
227
228	typename LeftT::const_iterator left_ = left_begin;
229	typename RightT::const_iterator right_ = right_begin;
230
231	int state = Step::nextboth;
232	while(state != Step::stop)
233	state = step.next_both(left_, right_);
234
235	return step.result();
236	}
237
238	template<class LeftT, class RightT>
239	int subset_compare(const LeftT& left, const RightT& right)
240	{
241	return subset_compare
242	(
243	left, right,
244	left.begin(), left.end(),
245	right.begin(), right.end()
246	);
247	}
248
249
250	} // namespace Set
251
252	#ifdef BOOST_MSVC
253	#pragma warning(pop)
254	#endif
255
256	}} // namespace icl boost
257
258	#endif
259