| 1 | // [The FreeBSD Licence]
|
---|
| 2 | //
|
---|
| 3 | // Copyright (c) 2008
|
---|
| 4 | // Sebastian Mies, Institute of Telematics, UniversitÀt Karlsruhe (TH)
|
---|
| 5 | // All rights reserved.
|
---|
| 6 | //
|
---|
| 7 | // Redistribution and use in source and binary forms, with or without
|
---|
| 8 | // modification, are permitted provided that the following conditions are
|
---|
| 9 | // met:
|
---|
| 10 | //
|
---|
| 11 | // * Redistributions of source code must retain the above copyright notice,
|
---|
| 12 | // this list of conditions and the following disclaimer.
|
---|
| 13 | // * Redistributions in binary form must reproduce the above copyright
|
---|
| 14 | // notice, this list of conditions and the following disclaimer in the
|
---|
| 15 | // documentation and/or other materials provided with the distribution.
|
---|
| 16 | // * Neither the name of the author nor the names of its contributors may be
|
---|
| 17 | // used to endorse or promote products derived from this software without
|
---|
| 18 | // specific prior written permission.
|
---|
| 19 | //
|
---|
| 20 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
|
---|
| 21 | // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
|
---|
| 22 | // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
---|
| 23 | // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
|
---|
| 24 | // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
---|
| 25 | // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
---|
| 26 | // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
|
---|
| 27 | // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
---|
| 28 | // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
|
---|
| 29 | // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
|
---|
| 30 | // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
---|
| 31 | //
|
---|
| 32 | #ifndef VINT_HPP_
|
---|
| 33 | #define VINT_HPP_
|
---|
| 34 |
|
---|
| 35 | #include <boost/mpl/if.hpp>
|
---|
| 36 |
|
---|
| 37 | #include "detail/helper.hpp"
|
---|
| 38 | #include "detail/vint_big.hpp"
|
---|
| 39 | #include "detail/vint_small.hpp"
|
---|
| 40 |
|
---|
| 41 | using namespace _vint::detail;
|
---|
| 42 |
|
---|
| 43 | template<size_t l, bool s> class vint;
|
---|
| 44 | template<size_t l, bool s>
|
---|
| 45 | std::ostream& operator<<(std::ostream&, const vint<l, s>& v);
|
---|
| 46 |
|
---|
| 47 | /**
|
---|
| 48 | * This class implements an adaptive, scalable integer type.<br />
|
---|
| 49 | *
|
---|
| 50 | * Key features include:<br />
|
---|
| 51 | * <ul>
|
---|
| 52 | * <li>Transparent type switching according to native types</li>
|
---|
| 53 | * <li>Optimal memory consumption and optimization properties</li>
|
---|
| 54 | * <li>Automatic big integer arithmetic using gmp or other libraries</li>
|
---|
| 55 | * <li>Unconventional integer types (e.g. length not a power of 2)</li>
|
---|
| 56 | * <li>Additional math, like intervals, log2, divrem, gcd, ...</li>
|
---|
| 57 | * </ul>
|
---|
| 58 | *
|
---|
| 59 | * ... short: a real scalable integer type at compile-time cost!<br />
|
---|
| 60 | *
|
---|
| 61 | * @author Sebastian Mies <mies@tm.uka.de>
|
---|
| 62 | */
|
---|
| 63 | template<size_t __length = 0, bool __sign = false>
|
---|
| 64 | class vint {
|
---|
| 65 | // stream operator
|
---|
| 66 | friend std::ostream& operator<< <__length, __sign> (std::ostream&,
|
---|
| 67 | const vint<__length, __sign>&);
|
---|
| 68 |
|
---|
| 69 | public:
|
---|
| 70 | // select proper type
|
---|
| 71 | typedef typename boost::mpl::if_<
|
---|
| 72 | boost::mpl::bool_<(__length> 64 || __length == 0)>,
|
---|
| 73 | vint_big<__length, __sign>, vint_small<__length, __sign>
|
---|
| 74 | >::type type;
|
---|
| 75 |
|
---|
| 76 | // selected value type
|
---|
| 77 | type value;
|
---|
| 78 |
|
---|
| 79 | // internal self-template
|
---|
| 80 | typedef vint<__length, __sign> _self;
|
---|
| 81 |
|
---|
| 82 | public:
|
---|
| 83 | /* construct an zero integer */
|
---|
| 84 | finline vint() : value() {}
|
---|
| 85 |
|
---|
| 86 | /* construct an integer from a constant */
|
---|
| 87 | template<typename T> finline vint(const T v, if_integral(T) ) : value(v) {}
|
---|
| 88 |
|
---|
| 89 | /* construct a variable integer from a given string */
|
---|
| 90 | finline vint(const char* text, int base = 10) : value(text,base) {}
|
---|
| 91 |
|
---|
| 92 | /* copy constructor */
|
---|
| 93 | finline vint( const type& v ) {value = v;}
|
---|
| 94 |
|
---|
| 95 | /* copy constructor */
|
---|
| 96 | finline vint( const _self& v ) {value = v.value;}
|
---|
| 97 |
|
---|
| 98 | //-- conversion -----------------------------------------------------------
|
---|
| 99 |
|
---|
| 100 | template<size_t ___length, bool ___sign>
|
---|
| 101 | finline void convert_to(vint<___length, ___sign>& v ) const {
|
---|
| 102 | return value.convert_to(v.value);
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | template<class T>
|
---|
| 106 | finline void convert_to( T& v, if_integral(T) ) const {
|
---|
| 107 | return value.convert_to(v);
|
---|
| 108 | }
|
---|
| 109 |
|
---|
| 110 | finline std::string to_string(int base = 10,
|
---|
| 111 | int str_size = 0, char str_fill = '0') const {
|
---|
| 112 | return value.to_string(base,str_size,str_fill);
|
---|
| 113 | }
|
---|
| 114 |
|
---|
| 115 | std::string to_debug_string(int base = 10,
|
---|
| 116 | int str_size = 0, char str_fill = '0') const {
|
---|
| 117 | return value.to_debug_string(base,str_size,str_fill);
|
---|
| 118 | }
|
---|
| 119 |
|
---|
| 120 | //-- sub integers ---------------------------------------------------------
|
---|
| 121 |
|
---|
| 122 | finline bool get_bit(size_t index) const {
|
---|
| 123 | return value.get_bit(index);
|
---|
| 124 | }
|
---|
| 125 |
|
---|
| 126 | finline void set_bit(size_t index, bool v) {
|
---|
| 127 | value.set_bit(index, v);
|
---|
| 128 | }
|
---|
| 129 |
|
---|
| 130 | finline void set_subint(_self& v, size_t index) {
|
---|
| 131 | value.set_subint(v.value,index);
|
---|
| 132 | }
|
---|
| 133 |
|
---|
| 134 | finline void set_subint(uintmax_t v, size_t index) {
|
---|
| 135 | value.set_subint(v,index);
|
---|
| 136 | }
|
---|
| 137 |
|
---|
| 138 | finline _self get_subint(size_t index, size_t length) const {
|
---|
| 139 | return value.get_subint(index,length);
|
---|
| 140 | }
|
---|
| 141 |
|
---|
| 142 | finline uintmax_t get_subint(size_t index) const {
|
---|
| 143 | return value.get_subint(index);
|
---|
| 144 | }
|
---|
| 145 |
|
---|
| 146 | //-- assignment -----------------------------------------------------------
|
---|
| 147 |
|
---|
| 148 | public:
|
---|
| 149 |
|
---|
| 150 | template<size_t _len, bool _sign>
|
---|
| 151 | finline void assign( const vint<_len,_sign>& v ) {
|
---|
| 152 | value.assign(v.value);
|
---|
| 153 | }
|
---|
| 154 |
|
---|
| 155 | template<typename T>
|
---|
| 156 | finline void assign(const T& v, if_integral(T) ) {
|
---|
| 157 | value.assign(v);
|
---|
| 158 | }
|
---|
| 159 |
|
---|
| 160 | finline void assign(const std::string& text, int base = 10) {
|
---|
| 161 | value.assign( text, base );
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | void assign(const char*& text, int base = 10) {
|
---|
| 165 | assign(std::string(text), base);
|
---|
| 166 | }
|
---|
| 167 |
|
---|
| 168 | //-- compare operations ---------------------------------------------------
|
---|
| 169 |
|
---|
| 170 | finline int compare_to(const _self& v) const {
|
---|
| 171 | return value.compare_to(v.value);
|
---|
| 172 | }
|
---|
| 173 |
|
---|
| 174 | template<class T>
|
---|
| 175 | finline int compare_to(const T& v, if_integral(T) ) const {
|
---|
| 176 | return value.compare_to(v);
|
---|
| 177 | }
|
---|
| 178 |
|
---|
| 179 | //-- arithmetic operations ------------------------------------------------
|
---|
| 180 |
|
---|
| 181 | // addition
|
---|
| 182 | template<class T>
|
---|
| 183 | finline void add(const T& rhs, if_integral(T) ) {value.add(rhs.value);}
|
---|
| 184 | finline void add(const _self& rhs) {value.add(rhs.value);}
|
---|
| 185 |
|
---|
| 186 | // subtraction
|
---|
| 187 | template<class T>
|
---|
| 188 | finline void sub(const T& rhs, if_integral(T) ) {value.sub(rhs.value);}
|
---|
| 189 | finline void sub(const _self& rhs) {value.sub(rhs.value);}
|
---|
| 190 |
|
---|
| 191 | // multiplication
|
---|
| 192 | template<class T>
|
---|
| 193 | finline void mul( const T& rhs, if_integral(T) ) {value.mul(rhs);}
|
---|
| 194 | finline void mul( _self& rhs) {value.mul(rhs.value);}
|
---|
| 195 | finline void mul( _self& res, const _self& rhs ) const {value.mul(res.value,rhs.value);}
|
---|
| 196 |
|
---|
| 197 | // division
|
---|
| 198 | template<class T>
|
---|
| 199 | finline void div( const T& rhs, if_integral(T) ) {value.div(rhs);}
|
---|
| 200 | finline void div(_self& rhs) {value.div(rhs.value);}
|
---|
| 201 | finline void div(_self& res, const _self& rhs ) const {value.div(res.value, rhs);}
|
---|
| 202 |
|
---|
| 203 | // modulo
|
---|
| 204 | template<class T>
|
---|
| 205 | finline void mod( const T& rhs, if_integral(T) ) {value.mod(rhs);}
|
---|
| 206 | finline void mod(_self& rhs) {value.mod(rhs.value);}
|
---|
| 207 | finline void mod(_self& res, const _self& rhs ) const {value.mod(res.value, rhs);}
|
---|
| 208 |
|
---|
| 209 | // exception of modulo: result may be of integral type
|
---|
| 210 | template<class T>
|
---|
| 211 | finline void mod( T& res, const T& rhs, if_integral(T) ) const {value.mod(res,rhs);}
|
---|
| 212 |
|
---|
| 213 | // division with remainder
|
---|
| 214 | template<class T>
|
---|
| 215 | finline void divrem(_self& res_div, T& res_rem, const T& rhs, if_integral(T) ) const {
|
---|
| 216 | value.divrem(res_div.value, res_rem, rhs );
|
---|
| 217 | }
|
---|
| 218 | finline void divrem(_self& res_div, _self& res_rem, const _self& rhs ) const {
|
---|
| 219 | value.divrem(res_div.value, res_rem.value, rhs.value);
|
---|
| 220 | }
|
---|
| 221 | template<class T>
|
---|
| 222 | finline void divrem( T& res_rem, const T& rhs, if_integral(T) ) {
|
---|
| 223 | value.div(res_rem, rhs.value);
|
---|
| 224 | }
|
---|
| 225 | finline void divrem( _self& res_rem, const _self& rhs ) {
|
---|
| 226 | value.div(res_rem.value, rhs.value);
|
---|
| 227 | }
|
---|
| 228 |
|
---|
| 229 | // logarithm to the base of 2
|
---|
| 230 | finline uintmax_t log2() const {return value.log2();}
|
---|
| 231 |
|
---|
| 232 | //-- logical bit operations -----------------------------------------------
|
---|
| 233 |
|
---|
| 234 | finline void or_ (const _self& v) {value.or_(v.value);}
|
---|
| 235 | finline void and_(const _self& v) {value.and_(v.value);}
|
---|
| 236 | finline void xor_(const _self& v) {value.xor_(v.value);}
|
---|
| 237 | finline void complement() {value.complement();}
|
---|
| 238 | finline void lshift(size_t steps) {value.lshift(steps);}
|
---|
| 239 | finline void rshift(size_t steps) {value.rshift(steps);}
|
---|
| 240 |
|
---|
| 241 | //-- integer dynamic ------------------------------------------------------
|
---|
| 242 |
|
---|
| 243 | inline _self normalized() const {return value.normalized();}
|
---|
| 244 |
|
---|
| 245 | //-- general information --------------------------------------------------
|
---|
| 246 |
|
---|
| 247 | finline size_t length() const {return value.length();}
|
---|
| 248 | finline void set_length(size_t length) {value.set_length(length);}
|
---|
| 249 | finline bool is_unspecified() {return value.is_unspecified();}
|
---|
| 250 |
|
---|
| 251 | finline _self max() const {_self v; v.value = value.max(); return v;}
|
---|
| 252 | finline _self min() const {_self v; v.value = value.min(); return v;}
|
---|
| 253 | finline _self zero() const {_self v; v.value = value.zero(); return v;}
|
---|
| 254 |
|
---|
| 255 | //-- general extensions ---------------------------------------------------
|
---|
| 256 |
|
---|
| 257 | finline void convert_to( std::string& str ) const {
|
---|
| 258 | str = to_string();
|
---|
| 259 | }
|
---|
| 260 |
|
---|
| 261 | /**
|
---|
| 262 | * Returns true, if the integer is inside the interval [a,b]
|
---|
| 263 | */
|
---|
| 264 | finline bool is_between(const _self& a, const _self& b) const {
|
---|
| 265 | return (a <= b) ?
|
---|
| 266 | ((*this >= a) && (*this <= b))
|
---|
| 267 | :
|
---|
| 268 | ((*this <= a) && (*this >= b))
|
---|
| 269 | ;
|
---|
| 270 | }
|
---|
| 271 |
|
---|
| 272 | /**
|
---|
| 273 | * Returns true, if the integer is inside the interval [a,b] on
|
---|
| 274 | * a ring.
|
---|
| 275 | */
|
---|
| 276 | finline bool is_between_ring(const _self& a, const _self& b) const {
|
---|
| 277 | return (b<a) ?
|
---|
| 278 | (is_between(a, a.max())||is_between(b.zero(), b))
|
---|
| 279 | :
|
---|
| 280 | ((*this >= a) && (*this <= b))
|
---|
| 281 | ;
|
---|
| 282 | }
|
---|
| 283 |
|
---|
| 284 | //-- convenience operator overloads ---------------------------------------
|
---|
| 285 |
|
---|
| 286 | // conversion operators
|
---|
| 287 | template<typename T> finline T convert() const {T v;convert_to(v);return v;}
|
---|
| 288 | template<typename T> finline operator T () const {return convert<T>();}
|
---|
| 289 |
|
---|
| 290 | // assign operators
|
---|
| 291 | template<class T>
|
---|
| 292 | finline _self& operator=(const T& copy) {assign(copy);return *this;}
|
---|
| 293 |
|
---|
| 294 | // add operators
|
---|
| 295 | template<class T>
|
---|
| 296 | finline _self& operator+=(const T& v) {add(v);return *this;}
|
---|
| 297 | template<class T>
|
---|
| 298 | finline _self& operator++() {add(1);return *this;}
|
---|
| 299 | template<class T>
|
---|
| 300 | finline _self operator+ (const T& v) const {_self x=*this;x.add(v);return x;}
|
---|
| 301 |
|
---|
| 302 | // substract operators
|
---|
| 303 | template<class T>
|
---|
| 304 | finline _self& operator-=(const T& v) {sub_model(v);return *this;}
|
---|
| 305 | finline _self& operator--() {sub(1);return *this;}
|
---|
| 306 | template<class T>
|
---|
| 307 | finline _self operator- (const T& v) const {
|
---|
| 308 | _self x(*this); x.sub_model(v); return x;
|
---|
| 309 | }
|
---|
| 310 |
|
---|
| 311 | // multiply operators
|
---|
| 312 | template<class T> finline _self& operator*=(const T& v) {
|
---|
| 313 | value.mul(v);
|
---|
| 314 | return *this;
|
---|
| 315 | }
|
---|
| 316 | template<class T> finline _self operator*(const T& v) const {
|
---|
| 317 | _self res = *this;res.mul(v); return res;
|
---|
| 318 | }
|
---|
| 319 |
|
---|
| 320 | // bit shift operators convenience
|
---|
| 321 | finline _self operator<< (size_t steps) {_self x=*this;return(x<<=steps);}
|
---|
| 322 | finline _self& operator>>=(size_t steps) {rshift(steps);return *this;}
|
---|
| 323 | finline _self operator>> (size_t steps) {_self x=*this;return(x<<=steps);}
|
---|
| 324 | finline _self& operator<<=(size_t steps) {lshift(steps);return *this;}
|
---|
| 325 |
|
---|
| 326 | // bit operators convenience
|
---|
| 327 | finline _self& operator&=(const _self& v) {and_(v); return *this;}
|
---|
| 328 | finline _self operator & (const _self& v) {_self x=*this;return(x&=v);}
|
---|
| 329 | finline _self& operator|=(const _self& v) {or_(v); return *this;}
|
---|
| 330 | finline _self operator | (const _self& v) {_self x=*this;return(x|=v);}
|
---|
| 331 | finline _self& operator^=(const _self& v) {xor_(v);return *this;}
|
---|
| 332 | finline _self operator^ (const _self& v) {_self x=*this;return(x ^= v);}
|
---|
| 333 | finline _self operator~() {_self x=*this;return x.complement();}
|
---|
| 334 |
|
---|
| 335 | // compare operators convenience
|
---|
| 336 | template<class T>
|
---|
| 337 | finline bool operator< (const T& v) const {return compare_to(v)< 0;}
|
---|
| 338 | template<class T>
|
---|
| 339 | finline bool operator> (const T& v) const {return compare_to(v)> 0;}
|
---|
| 340 | template<class T>
|
---|
| 341 | finline bool operator<=(const T& v) const {return compare_to(v)<=0;}
|
---|
| 342 | template<class T>
|
---|
| 343 | finline bool operator>=(const T& v) const {return compare_to(v)>=0;}
|
---|
| 344 | template<class T>
|
---|
| 345 | finline bool operator==(const T& v) const {return compare_to(v)==0;}
|
---|
| 346 | template<class T>
|
---|
| 347 | finline bool operator!=(const T& v) const {return compare_to(v)!=0;}
|
---|
| 348 | };
|
---|
| 349 |
|
---|
| 350 | template<size_t l, bool s>
|
---|
| 351 | std::ostream& operator<<(std::ostream& os, const vint<l, s>& v) {
|
---|
| 352 | return os << v.value;
|
---|
| 353 | }
|
---|
| 354 |
|
---|
| 355 | #endif /* VINT_HPP_ */
|
---|
| 356 |
|
---|