/* $Id$ */

/*
 * Copyright (C) 2005-2006 Richard Braun
 * 
 * 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef _MTXINTEGER_H
#define _MTXINTEGER_H

#include <string>
#include <iostream>

#include "mtx.h"
#include "mtxvalue.h"

/**
 * An arbitrary length integer.
 * 
 * All integers used by the mtx engine use this class.
 */
class MtxInteger: public MtxValue
{
  private:
    /**
     * Words storing the value of the integer.
     * 
     * Internal representation uses twos complement, and words are stored
     * using little endian order.
     */
    mtx_int_t *words;

    /**
     * Number of words.
     */
    size_t words_count;

    /**
     * Base used for conversions when no base is provided.
     * 
     * Initially set to MTX_DEFAULT_BASE, but can be modified at
     * runtime.
     * 
     * @see getBase()
     * @see setBase()
     */
    static unsigned int base;

    /**
     * Return true if negative.
     */
    bool isNegative() const;

    /**
     * Optimize memory usage.
     */
    void normalize();

    /**
     * Set a new value.
     */
    void setWords(const mtx_int_t *words, size_t words_count);

    /**
     * Unsigned integer division.
     * 
     * Absolute values used if negative values are passed.
     * This method does *this / divisor and sets quotient and remainder.
     * 
     * @see divide()
     */
    void unsigned_divide(const MtxInteger &divisor,
                         MtxInteger &quotient,
                         MtxInteger &remainder) const;

    /**
     * Signed integer division.
     * 
     * @see unsigned_divide()
     */
    void divide(const MtxInteger &divisor,
                MtxInteger &quotient,
                MtxInteger &remainder) const;

    /**
     * Return true if the given integer is a power of two.
     */
    static bool isPowerOfTwo(unsigned int n);

    /**
     * Return the number of bits used to store a digit in the given base.
     * 
     * This value is the lowest possible value (in base 10, 4 bits must be
     * used to store 8 or 9, but only 3 for other values, so 3 is returned
     * by this function). The reason is that this value is used to compute
     * the number of digits to allocate when converting to another base. The
     * total number of bits is divided by this value. In order to ensure that
     * all digits can be stored, this division must return a value greater
     * than or equal to the number of digits, and using the lowest value
     * is an acceptable solution (some memory may be unused).
     * 
     * If base is lower than 2, base 2 is silently used.
     */
    static unsigned int bitsPerDigit(unsigned int base);

    /**
     * Return the char matching the given integer.
     * 
     * For example, intToChar(2) returns '2'.
     * 
     * @see charToInt()
     */
    static char intToChar(unsigned int n);

    /**
     * Return the int matching the given character.
     * 
     * For example, charToInt('2') returns 2.
     * 
     * @see intToChar()
     */
    static unsigned int charToInt(char c);

  public:
    /**
     * Default constructor.
     * 
     * 0 is the default value.
     */
    MtxInteger();

    /**
     * Create an MtxInteger from a primitive int.
     * 
     * Be careful when using this constructor, as values with the MSB set
     * are *negative* values for type int.
     */
    MtxInteger(int integer);

    /**
     * Create an integer from a string representation.
     * 
     * An exception is raised if the string is invalid. A valid string
     * consists of 0 or more white spaces as defined by isspace(), possibly
     * a '+' or '-' character, and 1 or more characters allowed for the
     * current base.
     */
    MtxInteger(const char *digits);

    MtxInteger(const MtxInteger &integer);
    virtual ~MtxInteger();

    /*
     * These operators are expected to behave exactly like the native
     * C++ operators when handling int variables.
     */
    MtxInteger & operator=(const MtxInteger &integer);
    MtxInteger operator+() const;
    MtxInteger operator-() const;
    bool operator==(const MtxInteger &integer) const;
    bool operator!=(const MtxInteger &integer) const;
    bool operator>(const MtxInteger &integer) const;
    bool operator>=(const MtxInteger &integer) const;
    bool operator<(const MtxInteger &integer) const;
    bool operator<=(const MtxInteger &integer) const;
    MtxInteger operator>>(unsigned int bits) const;
    MtxInteger & operator>>=(unsigned int bits);
    MtxInteger operator<<(unsigned int bits) const;
    MtxInteger & operator<<=(unsigned int bits);
    MtxInteger operator+(const MtxInteger &integer) const;
    MtxInteger & operator++();
    MtxInteger & operator++(int a);
    MtxInteger & operator+=(const MtxInteger &integer);
    MtxInteger operator-(const MtxInteger &integer) const;
    MtxInteger & operator--();
    MtxInteger & operator--(int a);
    MtxInteger & operator-=(const MtxInteger &integer);
    MtxInteger operator*(const MtxInteger &integer) const;
    MtxInteger & operator*=(const MtxInteger &integer);
    MtxInteger operator/(const MtxInteger &integer) const;
    MtxInteger & operator/=(const MtxInteger &integer);
    MtxInteger operator%(const MtxInteger &integer) const;
    MtxInteger & operator%=(const MtxInteger &integer);
    friend std::ostream & operator<<(std::ostream &cout,
                                     const MtxInteger &integer);

    /**
     * Return (*this)^power.
     */
    MtxInteger power(unsigned int power) const;

    /**
     * Return the absolute value.
     */
    MtxInteger abs() const;

    /**
     * Return a string representation of this integer.
     * 
     * @see toString(unsigned int base) const
     */
    virtual std::string toString() const;

    /**
     * Return a string representation of this integer.
     * 
     * As for setBase(), toString() will silently fallback to the runtime
     * default base if the provided base is invalid.
     * 
     * @see toString()
     */
    std::string toString(unsigned int base) const;

    /*
     * See mtxvalue.h.
     */
    MTXVALUE_CLONE_METHOD_DECLARATION(MtxInteger);
    virtual MtxValue * add(const MtxValue *value) const;
    virtual MtxValue * subtract(const MtxValue *value) const;
    virtual MtxValue * multiply(const MtxValue *value) const;
    virtual MtxValue * divide(const MtxValue *value) const;
    virtual MtxValue * opposite() const;

    /**
     * Set the runtime default base.
     * 
     * The base variable must be a value between 2 and MTX_MAX_BASE
     * included, otherwise this method will silently return without
     * altering anything.
     * 
     * @see base
     * @see getBase()
     */
    static void setBase(unsigned int base);

    /**
     * Return the current base.
     * 
     * @see base
     * @see getBase()
     */
    static unsigned int getBase();

    /**
     * Return the greatest common divisor of a and b.
     */
    static MtxInteger gcd(MtxInteger a, MtxInteger b);
};

#endif /* _MTXINTEGER_H */