00001
00002
00003
00004
00005
00006
00007 #ifndef _ARAGELI__utility_hpp_
00008 #define _ARAGELI__utility_hpp_
00009
00010 #include "config.hpp"
00011
00012 #include <iostream>
00013 #include <algorithm>
00014 #include <utility>
00015
00016 #include "type_opers.hpp"
00017 #include "factory.hpp"
00018 #include "std_import.hpp"
00019 #include "interval.hpp"
00020
00021
00022 namespace Arageli
00023 {
00024
00025 namespace _Internal
00026 {
00027
00028 class Auto_stream_state
00029 {
00030 std::ios_base& stream;
00031 std::ios_base::fmtflags oldflags;
00032
00033 public:
00034
00035 Auto_stream_state
00036 (
00037 std::ios_base& stream_a,
00038 std::ios_base::fmtflags newflags
00039 )
00040 : stream(stream_a)
00041 { oldflags = stream.flags(newflags); }
00042
00043 ~Auto_stream_state () { stream.flags(oldflags); }
00044 };
00045
00046
00047
00048 bool is_not_contains_spaces (const char* s);
00049
00050
00051
00052
00053
00054
00055
00056 bool read_literal (std::istream& in, const char* s);
00057
00058
00059 template <typename In, typename Str>
00060 inline bool is_bad_read_literal (In& in, const Str& s)
00061 {
00062 if(!read_literal(in, s))
00063 {
00064 in.clear(std::ios_base::badbit);
00065 return true;
00066 }
00067
00068 return false;
00069 }
00070
00071
00072
00073
00074 template <typename In>
00075 inline bool is_bad_input (In& in)
00076 {
00077 if(!in)
00078 {
00079 in.clear(std::ios_base::badbit);
00080 return true;
00081 }
00082
00083 return false;
00084 }
00085
00086
00087 #ifdef ARAGELI_DISABLE_PARTICULAR_COMPILER_WARNINGS
00088 #pragma warning (push)
00089 #pragma warning (disable : 4800)
00090 #endif
00091
00092
00093 template <typename T> class auto_array
00094 {
00095 public:
00096
00097 typedef T element_type;
00098
00099 explicit auto_array(T* p = 0) throw()
00100 : owner(p), pointer(p) {}
00101
00102 auto_array(const auto_array<T>& q) throw()
00103 : owner(q.owner), pointer(q.release()) {}
00104
00105 auto_array<T>& operator= (const auto_array<T>& q) throw()
00106 {
00107 if(this != &q)
00108 {
00109 if(pointer != q.get())
00110 {
00111 if (owner)
00112 delete [] pointer;
00113 owner = q.owner;
00114 }
00115 else if(q.owner)owner = true;
00116
00117 pointer = q.release();
00118 }
00119 return *this;
00120 }
00121
00122 ~auto_array () { if(owner) delete [] pointer; }
00123
00124 T& operator* () const throw() { return *get(); }
00125
00126 T* operator-> () const throw() { return get(); }
00127
00128 T* get () const throw() { return pointer; }
00129
00130 T* release () const throw()
00131 {
00132 owner = false;
00133 return pointer;
00134 }
00135
00136 private:
00137
00138 mutable bool owner;
00139
00140 T* pointer;
00141 };
00142
00143
00144 #ifdef ARAGELI_DISABLE_PARTICULAR_COMPILER_WARNINGS
00145 #pragma warning (pop)
00146 #endif
00147
00148
00149 template <typename A, typename B, typename Store_A, typename Store_B>
00150 inline void swap_help_1 (A& a, B& b, Store_A& sa, Store_B& sb, true_type)
00151 { sa.swap(sb); }
00152
00153 template <typename A, typename B, typename Store_A, typename Store_B>
00154 void swap_help_1 (A& a, B& b, Store_A& sa, Store_B& sb, false_type);
00155
00156
00157 template <typename In_a, typename In_b>
00158 int aggregate_cmp (In_a ai, In_a aend, In_b bi, In_b bend);
00159
00160
00161 template <typename T>
00162 std::reverse_iterator<T> make_reverse_iterator (const T& x)
00163 { return std::reverse_iterator<T>(x); }
00164
00165
00166 template <typename R, typename T>
00167 inline R noncopy_cast (const T& x) { return R(x); }
00168
00169 template <typename R>
00170 inline const R& noncopy_cast (const R& x) { return x; }
00171
00172 template <typename R>
00173 inline R& noncopy_cast (R& x) { return x; }
00174
00175 template <typename R, typename T>
00176 inline R copy_cast (const T& x) { return noncopy_cast<R>(x); }
00177
00178
00180 template <typename D = unsigned int, typename T = big_int>
00181 class module_2pm1
00182 {
00183 public:
00184
00185 D degree_a;
00186
00187 public:
00188
00189 module_2pm1 () : degree_a(0) {}
00190
00191 module_2pm1 (const D& x) : degree_a(x)
00192 { }
00193
00194 operator T () const { return (unit<T>() << degree_a) - unit<T>(); }
00195
00196 };
00197
00198
00199 template <typename D1, typename T1, typename D2, typename T2>
00200 inline bool operator== (const module_2pm1<D1, T1>& a, const module_2pm1<D2, T2>& b)
00201 { return a.degree_a == b.degree_a; }
00202
00203 template <typename D1, typename T1, typename D2, typename T2>
00204 inline bool operator!= (const module_2pm1<D1, T1>& a, const module_2pm1<D2, T2>& b)
00205 { return !(a == b); }
00206
00207
00208 template <typename In>
00209 typename std::iterator_traits<In>::value_type content (In begin, In end)
00210 {
00211 typedef typename std::iterator_traits<In>::value_type T;
00212 T res = null<T>();
00213 for(; begin != end; ++begin)
00214 res = gcd(res, *begin);
00215 return res;
00216 }
00217
00218
00219 }
00220
00221 template <typename D1, typename T1>
00222 inline bool is_null (const _Internal::module_2pm1<D1, T1>& a)
00223 { return is_null(a.degree_a); }
00224
00225 template <typename D1, typename T1>
00226 inline bool is_unit (const _Internal::module_2pm1<D1, T1>& a)
00227 { return is_unit(a.degree_a); }
00228
00229
00230 template <typename T1, typename D2, typename T2>
00231 inline T1 prrem (const T1& aa, const _Internal::module_2pm1<D2, T2>& b)
00232 {
00233 T1 a = aa;
00234
00235 ARAGELI_DEBUG_EXEC_1(T1 _debug_result = prrem(a, T1(b)));
00236
00237 T2 m2p = unit<T2>() << b.degree_a;
00238 T2 m2pm1 = m2p - unit<T2>();
00239 if(is_negative(a))a += m2pm1;
00240
00241
00242
00243
00244
00245 ARAGELI_ASSERT_0(!is_negative(a));
00246
00247 if(a < m2pm1)return a;
00248
00249 a -= m2pm1;
00250
00251 if(a < m2pm1)return a;
00252
00253
00254
00255 T1 q = a >> b.degree_a;
00256 ++q;
00257
00258
00259
00260 ARAGELI_ASSERT_1(q < m2pm1);
00261
00262
00263
00264 T1 r = (a & m2pm1) + q;
00265
00266
00267
00268 if(r < m2p)--r;
00269 else r -= m2p;
00270
00271 ARAGELI_ASSERT_1(!is_negative(r));
00272 ARAGELI_ASSERT_1(r < m2pm1);
00273
00274
00275 ARAGELI_ASSERT_1(_debug_result == r);
00276
00277 return r;
00278 }
00279
00280
00281 template <typename Out, typename D, typename T>
00282 inline Out& operator<< (Out& out, const _Internal::module_2pm1<D, T>& x)
00283 {
00284 out << "2^" << x.degree_a << "-1";
00285 return out;
00286 }
00287
00288
00289 template <typename In, typename D, typename T>
00290 inline In& operator>> (In& in, _Internal::module_2pm1<D, T>& x)
00291 {
00292 ARAGELI_ASSERT_ALWAYS(!"Ha-ha-ha:)!");
00293 return in;
00294 }
00295
00296
00297 }
00298
00299
00300 #ifdef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE
00301 #define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE__UTILITY
00302 #include "_utility.cpp"
00303 #undef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE__UTILITY
00304 #endif
00305
00306
00307 #endif // #ifndef _ARAGELI__utility_hpp_