diff options
Diffstat (limited to 'common')
-rw-r--r-- | common/algorithm.h | 13 | ||||
-rw-r--r-- | common/module.mk | 1 | ||||
-rw-r--r-- | common/rational.cpp | 353 | ||||
-rw-r--r-- | common/rational.h | 111 |
4 files changed, 478 insertions, 0 deletions
diff --git a/common/algorithm.h b/common/algorithm.h index 3a66efedba..06f2a279af 100644 --- a/common/algorithm.h +++ b/common/algorithm.h @@ -222,6 +222,19 @@ void sort(T first, T last) { sort(first, last, Common::Less<typename T::ValueType>()); } +/** + * Euclid's algorithm to compute the greatest common divisor. + */ +template<class T> +T gcd(T a, T b) { + while (a > 0) { + T tmp = a; + a = b % a; + b = tmp; + } + return b; +} + } // End of namespace Common #endif diff --git a/common/module.mk b/common/module.mk index 2bbb1eda76..83d30f0a9b 100644 --- a/common/module.mk +++ b/common/module.mk @@ -16,6 +16,7 @@ MODULE_OBJS := \ md5.o \ mutex.o \ random.o \ + rational.o \ str.o \ stream.o \ system.o \ diff --git a/common/rational.cpp b/common/rational.cpp new file mode 100644 index 0000000000..e27e880a04 --- /dev/null +++ b/common/rational.cpp @@ -0,0 +1,353 @@ +/* ScummVM - Graphic Adventure Engine + * + * ScummVM is the legal property of its developers, whose names + * are too numerous to list here. Please refer to the COPYRIGHT + * file distributed with this source distribution. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * $URL$ + * $Id$ + */ + +#include "common/rational.h" +#include "common/util.h" +#include "common/algorithm.h" + +namespace Common { + +Rational::Rational() { + _num = 1; + _denom = 1; +} + +Rational::Rational(int num) { + _num = num; + _denom = 1; +} + +Rational::Rational(int num, int denom) { + assert(denom != 0); + + _num = num; + _denom = denom; + + normalize(); +} + +void Rational::cancel() { + // Cancel the fraction by dividing both the num and the denom + // by their greatest common denom. + + int gcd = Common::gcd(_num, _denom); + + _num /= gcd; + _denom /= gcd; +} + +void Rational::normalize() { + // Is the fraction negative? + bool negative = !((!(_num < 0)) == (!(_denom < 0))); + + // Make both integers positive + _num = ABS(_num); + _denom = ABS(_denom); + + // Cancel the fraction + cancel(); + + // If the fraction is supposed to be negative, make the num negative + if (negative) + _num = -_num; +} + +Rational &Rational::operator=(const Rational &right) { + _num = right._num; + _denom = right._denom; + + return *this; +} + +Rational &Rational::operator=(int right) { + _num = right; + _denom = 1; + + return *this; +} + +Rational &Rational::operator+=(const Rational &right) { + _num = _num * right._denom + right._num * _denom; + _denom = _denom * right._denom; + + normalize(); + + return *this; +} + +Rational &Rational::operator-=(const Rational &right) { + _num = _num * right._denom - right._num * _denom; + _denom = _denom * right._denom; + + normalize(); + + return *this; +} + +Rational &Rational::operator*=(const Rational &right) { + // Try to cross-cancel first, to avoid unnecessary overflow + int gcd1 = Common::gcd(_num, right._denom); + int gcd2 = Common::gcd(right._num, _denom); + + _num = (_num / gcd1) * (right._num / gcd2); + _denom = (_denom / gcd2) * (right._denom / gcd1); + + normalize(); + + return *this; +} + +Rational &Rational::operator/=(const Rational &right) { + return *this *= Rational(right._denom, right._num); +} + +Rational &Rational::operator+=(int right) { + return *this += Rational(right); +} + +Rational &Rational::operator-=(int right) { + return *this -= Rational(right); +} + +Rational &Rational::operator*=(int right) { + return *this *= Rational(right); +} + +Rational &Rational::operator/=(int right) { + return *this /= Rational(right); +} + +const Rational Rational::operator-() const { + return Rational(-_num, _denom); +} + +const Rational Rational::operator+(const Rational &right) const { + Rational tmp = *this; + + tmp += right; + + return tmp; +} + +const Rational Rational::operator-(const Rational &right) const { + Rational tmp = *this; + + tmp -= right; + + return tmp; +} + +const Rational Rational::operator*(const Rational &right) const { + Rational tmp = *this; + + tmp *= right; + + return tmp; +} + +const Rational Rational::operator/(const Rational &right) const { + Rational tmp = *this; + + tmp /= right; + + return tmp; +} + +const Rational Rational::operator+(int right) const { + Rational tmp = *this; + + tmp += right; + + return tmp; +} + +const Rational Rational::operator-(int right) const { + Rational tmp = *this; + + tmp -= right; + + return tmp; +} + +const Rational Rational::operator*(int right) const { + Rational tmp = *this; + + tmp *= right; + + return tmp; +} + +const Rational Rational::operator/(int right) const { + Rational tmp = *this; + + tmp /= right; + + return tmp; +} + +bool Rational::operator==(const Rational &right) const { + return (_num == right._num) && (_denom == right._denom); +} + +bool Rational::operator!=(const Rational &right) const { + return (_num != right._num) || (_denom != right._denom); +} + +bool Rational::operator>(const Rational &right) const { + return (_num * right._denom) > (right._num * _denom); +} + +bool Rational::operator<(const Rational &right) const { + return (_num * right._denom) < (right._num * _denom); +} + +bool Rational::operator>=(const Rational &right) const { + return (_num * right._denom) >= (right._num * _denom); +} + +bool Rational::operator<=(const Rational &right) const { + return (_num * right._denom) <= (right._num * _denom); +} + +bool Rational::operator==(int right) const { + return (_denom == 1) && (_num == right); +} + +bool Rational::operator!=(int right) const { + return (_denom == 1) && (_num != right); +} + +bool Rational::operator>(int right) const { + return *this > Rational(right, 1); +} + +bool Rational::operator<(int right) const { + return *this < Rational(right, 1); +} + +bool Rational::operator>=(int right) const { + return *this >= Rational(right, 1); +} + +bool Rational::operator<=(int right) const { + return *this <= Rational(right, 1); +} + +void Rational::invert() { + assert(_num != 0); + + SWAP(_num, _denom); + + normalize(); +} + +Rational Rational::getInverse() const { + Rational inverse = *this; + + inverse.invert(); + + return inverse; +} + +int Rational::toInt() const { + assert(_denom != 0); + + return _num / _denom; +} + +double Rational::toDouble() const { + assert(_denom != 0); + + return ((double) _num) / ((double) _denom); +} + +frac_t Rational::toFrac() const { + return (_num * FRAC_ONE) / _denom; +} + +Rational::operator int() const { + return toInt(); +} + +Rational::operator double() const { + return toDouble(); +} + +const Rational operator+(int left, const Rational &right) { + Rational tmp = right; + + tmp += left; + + return tmp; +} + +const Rational operator-(int left, const Rational &right) { + Rational tmp = right; + + tmp -= left; + + return tmp; +} + +const Rational operator*(int left, const Rational &right) { + Rational tmp = right; + + tmp *= left; + + return tmp; +} + +const Rational operator/(int left, const Rational &right) { + Rational tmp = right; + + tmp /= left; + + return tmp; +} + +bool operator==(int left, const Rational &right) { + return right == left; +} + +bool operator!=(int left, const Rational &right) { + return right != left; +} + +bool operator>(int left, const Rational &right) { + return right < left; +} + +bool operator<(int left, const Rational &right) { + return right > left; +} + +bool operator>=(int left, const Rational &right) { + return right <= left; +} + +bool operator<=(int left, const Rational &right) { + return right >= left; +} + +} // End of namespace Common diff --git a/common/rational.h b/common/rational.h new file mode 100644 index 0000000000..1ad33de8a6 --- /dev/null +++ b/common/rational.h @@ -0,0 +1,111 @@ +/* ScummVM - Graphic Adventure Engine + * + * ScummVM is the legal property of its developers, whose names + * are too numerous to list here. Please refer to the COPYRIGHT + * file distributed with this source distribution. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * $URL$ + * $Id$ + */ + +#ifndef COMMON_RATIONAL_H +#define COMMON_RATIONAL_H + +#include "common/scummsys.h" +#include "common/frac.h" + +namespace Common { + +/** A simple rational class that holds fractions. */ +class Rational { +public: + Rational(); + Rational(int num); + Rational(int num, int denom); + + Rational &operator=(const Rational &right); + Rational &operator=(int right); + + Rational &operator+=(const Rational &right); + Rational &operator-=(const Rational &right); + Rational &operator*=(const Rational &right); + Rational &operator/=(const Rational &right); + + Rational &operator+=(int right); + Rational &operator-=(int right); + Rational &operator*=(int right); + Rational &operator/=(int right); + + const Rational operator-() const; + + const Rational operator+(const Rational &right) const; + const Rational operator-(const Rational &right) const; + const Rational operator*(const Rational &right) const; + const Rational operator/(const Rational &right) const; + + const Rational operator+(int right) const; + const Rational operator-(int right) const; + const Rational operator*(int right) const; + const Rational operator/(int right) const; + + bool operator==(const Rational &right) const; + bool operator!=(const Rational &right) const; + bool operator>(const Rational &right) const; + bool operator<(const Rational &right) const; + bool operator>=(const Rational &right) const; + bool operator<=(const Rational &right) const; + + bool operator==(int right) const; + bool operator!=(int right) const; + bool operator>(int right) const; + bool operator<(int right) const; + bool operator>=(int right) const; + bool operator<=(int right) const; + + operator int() const; + operator double() const; + + void invert(); + Rational getInverse() const; + + int toInt() const; + double toDouble() const; + frac_t toFrac() const; + +private: + int _num; + int _denom; + + void cancel(); + void normalize(); +}; + +const Rational operator+(int left, const Rational &right); +const Rational operator-(int left, const Rational &right); +const Rational operator*(int left, const Rational &right); +const Rational operator/(int left, const Rational &right); + +bool operator==(int left, const Rational &right); +bool operator!=(int left, const Rational &right); +bool operator>(int left, const Rational &right); +bool operator<(int left, const Rational &right); +bool operator>=(int left, const Rational &right); +bool operator<=(int left, const Rational &right); + +} // End of namespace Common + +#endif |