1 | |
---|---|

2 | #ifndef BOOST_MPL_UPPER_BOUND_HPP_INCLUDED |

3 | #define BOOST_MPL_UPPER_BOUND_HPP_INCLUDED |

4 | |

5 | // Copyright Aleksey Gurtovoy 2001-2004 |

6 | // |

7 | // Distributed under the Boost Software License, Version 1.0. |

8 | // (See accompanying file LICENSE_1_0.txt or copy at |

9 | // http://www.boost.org/LICENSE_1_0.txt) |

10 | // |

11 | // See http://www.boost.org/libs/mpl for documentation. |

12 | |

13 | // $Id$ |

14 | // $Date$ |

15 | // $Revision$ |

16 | |

17 | #include <boost/mpl/less.hpp> |

18 | #include <boost/mpl/lambda.hpp> |

19 | #include <boost/mpl/aux_/na_spec.hpp> |

20 | #include <boost/mpl/aux_/config/workaround.hpp> |

21 | |

22 | #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x610)) |

23 | # define BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL |

24 | #endif |

25 | |

26 | #if !defined(BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL) |

27 | # include <boost/mpl/minus.hpp> |

28 | # include <boost/mpl/divides.hpp> |

29 | # include <boost/mpl/size.hpp> |

30 | # include <boost/mpl/advance.hpp> |

31 | # include <boost/mpl/begin_end.hpp> |

32 | # include <boost/mpl/long.hpp> |

33 | # include <boost/mpl/eval_if.hpp> |

34 | # include <boost/mpl/prior.hpp> |

35 | # include <boost/mpl/deref.hpp> |

36 | # include <boost/mpl/apply.hpp> |

37 | # include <boost/mpl/aux_/value_wknd.hpp> |

38 | #else |

39 | # include <boost/mpl/find.hpp> |

40 | # include <boost/mpl/bind.hpp> |

41 | #endif |

42 | |

43 | #include <boost/config.hpp> |

44 | |

45 | namespace boost { namespace mpl { |

46 | |

47 | #if defined(BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL) |

48 | |

49 | // agurt 23/oct/02: has a wrong complexity etc., but at least it works; |

50 | // feel free to contribute a better implementation! |

51 | template< |

52 | typename BOOST_MPL_AUX_NA_PARAM(Sequence) |

53 | , typename BOOST_MPL_AUX_NA_PARAM(T) |

54 | , typename Predicate = less<> |

55 | , typename pred_ = typename lambda<Predicate>::type |

56 | > |

57 | struct upper_bound |

58 | : find_if< Sequence, bind2<pred_,T,_> > |

59 | { |

60 | }; |

61 | |

62 | #else |

63 | |

64 | namespace aux { |

65 | |

66 | template< |

67 | typename Distance |

68 | , typename Predicate |

69 | , typename T |

70 | , typename DeferredIterator |

71 | > |

72 | struct upper_bound_step_impl; |

73 | |

74 | template< |

75 | typename Distance |

76 | , typename Predicate |

77 | , typename T |

78 | , typename DeferredIterator |

79 | > |

80 | struct upper_bound_step |

81 | { |

82 | typedef typename eval_if< |

83 | Distance |

84 | , upper_bound_step_impl<Distance,Predicate,T,DeferredIterator> |

85 | , DeferredIterator |

86 | >::type type; |

87 | }; |

88 | |

89 | template< |

90 | typename Distance |

91 | , typename Predicate |

92 | , typename T |

93 | , typename DeferredIterator |

94 | > |

95 | struct upper_bound_step_impl |

96 | { |

97 | typedef typename divides< Distance, long_<2> >::type offset_; |

98 | typedef typename DeferredIterator::type iter_; |

99 | typedef typename advance< iter_,offset_ >::type middle_; |

100 | typedef typename apply2< |

101 | Predicate |

102 | , T |

103 | , typename deref<middle_>::type |

104 | >::type cond_; |

105 | |

106 | typedef typename prior< minus< Distance, offset_ > >::type step_; |

107 | typedef upper_bound_step< offset_,Predicate,T,DeferredIterator > step_forward_; |

108 | typedef upper_bound_step< step_,Predicate,T,next<middle_> > step_backward_; |

109 | typedef typename eval_if< |

110 | cond_ |

111 | , step_forward_ |

112 | , step_backward_ |

113 | >::type type; |

114 | }; |

115 | |

116 | } // namespace aux |

117 | |

118 | template< |

119 | typename BOOST_MPL_AUX_NA_PARAM(Sequence) |

120 | , typename BOOST_MPL_AUX_NA_PARAM(T) |

121 | , typename Predicate = less<> |

122 | > |

123 | struct upper_bound |

124 | { |

125 | private: |

126 | typedef typename lambda<Predicate>::type pred_; |

127 | typedef typename size<Sequence>::type size_; |

128 | |

129 | public: |

130 | typedef typename aux::upper_bound_step< |

131 | size_,pred_,T,begin<Sequence> |

132 | >::type type; |

133 | }; |

134 | |

135 | #endif // BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL |

136 | |

137 | BOOST_MPL_AUX_NA_SPEC(2, upper_bound) |

138 | |

139 | }} |

140 | |

141 | #endif // BOOST_MPL_UPPER_BOUND_HPP_INCLUDED |

142 |