00001
00002 #ifndef _INSTIGATE_STL_INTERNAL_HEADER_IN_ALGORITHM
00003 #error This is an internal header file used to implement Instigate STL.\
00004 It should never be included directly by a program.
00005 #endif
00006
00007 #ifndef INSTIGATE_STL_RANDOM_SAMPLE_N_HPP
00008 #define INSTIGATE_STL_RANDOM_SAMPLE_N_HPP
00009
00059
00060 #include "concept.hpp"
00061 #include "_distance.hpp"
00062 #include "_min.hpp"
00063 #include "_random_number.hpp"
00064 #include "_distance.hpp"
00065 #include "_advance.hpp"
00066 #include "_basis.hpp"
00067
00068
00069
00070
00071
00072
00073 namespace instigate {
00074 namespace stl {
00075 template <typename F, typename O, typename D>
00076 O random_sample_n(F b, F e, O o, const D n);
00077 template <typename F, typename O, typename D, typename G>
00078 O random_sample_n(F b, F e, O o, const D n, const G& g);
00079 }
00080 }
00081
00128 template <typename F, typename O, typename D>
00129 O instigate::stl::random_sample_n(F b, F e, O o, const D n)
00130 {
00131 namespace FI = instigate::stl::forward_iterator;
00132 namespace RI = instigate::stl::readable_iterator;
00133 namespace IC = instigate::stl::incrementable_iterator;
00134 namespace WR = instigate::stl::writable_iterator;
00135 typedef typename RI::interface<F>::value_type value_type1;
00136 typedef typename WR::interface<O>::value_type value_type2;
00137 CHECK_CONVERTIBILITY(value_type1, value_type2);
00138 CHECK(FI::requirements<F>);
00139 CHECK(RI::requirements<F>);
00140 CHECK(IC::requirements<O>);
00141 CHECK(WR::requirements<O>);
00142 D r = (D)instigate::stl::distance(b, e);
00143 D m;
00144 assign(m, instigate::stl::min(n, r));
00145 while (less_than(0, m)) {
00146 if (less_than(instigate::stl::random_number(r), m)) {
00147 dereference_assign(o, const_dereference(b));
00148 increment(o);
00149 --m;
00150 }
00151 --r;
00152 increment(b);
00153 }
00154 return o;
00155 }
00156
00211 template <typename F, typename O, typename D, typename G>
00212 O instigate::stl::random_sample_n(F b, F e, O o, const D n, const G& g)
00213 {
00214 namespace FI = instigate::stl::forward_iterator;
00215 namespace RI = instigate::stl::readable_iterator;
00216 namespace IC = instigate::stl::incrementable_iterator;
00217 namespace WR = instigate::stl::writable_iterator;
00218 namespace UF = instigate::stl::unary_function;
00219 typedef typename RI::interface<F>::value_type value_type1;
00220 typedef typename WR::interface<O>::value_type value_type2;
00221 typedef typename FI::interface<F>::difference_type difference_type;
00222 typedef typename UF::interface<G>::argument_type argument_type;
00223 CHECK_CONVERTIBILITY(difference_type, argument_type);
00224 CHECK_CONVERTIBILITY(value_type1, value_type2);
00225 CHECK(FI::requirements<F>);
00226 CHECK(RI::requirements<F>);
00227 CHECK(IC::requirements<O>);
00228 CHECK(WR::requirements<O>);
00229 CHECK(UF::requirements<G>);
00230 D r = (D)instigate::stl::distance(b, e);
00231 D m;
00232 assign(m, instigate::stl::min(n, r));
00233 while (less_than(0, m)) {
00234 if (less_than(invoke(g, r), m)) {
00235 dereference_assign(o, const_dereference(b));
00236 increment(o);
00237 --m;
00238 }
00239 --r;
00240 increment(b);
00241 }
00242 return o;
00243 }
00244
00245
00246
00247 #endif // INSTIGATE_STL_RANDOM_SAMPLE_N_HPP