#pragma once

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <cstdint>

//A bigint implementation based on unsigned 32-bit digits.
//The implementation relies on having native 64-bit arithmetic (or specifically,
//(2*digit_bits)-bit arithmetic).
class Bigint{
public:
	typedef uint32_t digit_t;
	typedef int32_t sdigit_t; //signed version
	typedef uint64_t longdigit_t; //should be twice as large as digit_t
	typedef int64_t slongdigit_t; //signed version
	static const int digit_bits=8*sizeof(digit_t);

private:
	std::vector<digit_t> digits; //little-endian order
	int sign; //-1 for negative, 1 for positive; -0 is not a valid state

	static void add(Bigint&,const Bigint&); //ignores sign of arguments
	static void subtract(Bigint&,const Bigint&); //ignores sign of arguments
	static Bigint product(const Bigint&,const Bigint&);

	void shrink(); //prune unnecessary zero digits on top
	void normalise(); //make sure -0 doesn't occur

	//This function is called from all relevant return points of the member functions. It's
	//basically a debug check, but it can't hurt to have it since it takes few cpu cycles.
	void checkconsistent();

	static std::pair<Bigint,Bigint> divmod(Bigint a,const Bigint &div,int maxdepth); //ignores all signs

public:
	Bigint();
	Bigint(const Bigint&)=default;
	Bigint(Bigint&&);

	explicit Bigint(const std::string&); //Initialise with a large value
	explicit Bigint(sdigit_t); //Initialise with a small value
	explicit Bigint(digit_t);
	explicit Bigint(slongdigit_t);
	explicit Bigint(longdigit_t);

	Bigint& operator=(const Bigint&)=default;
	Bigint& operator=(Bigint&&);
	Bigint& operator=(slongdigit_t);
	Bigint& operator=(longdigit_t);
	Bigint& operator=(sdigit_t);
	Bigint& operator=(digit_t);

	Bigint& operator+=(const Bigint&);
	Bigint& operator-=(const Bigint&);
	Bigint& operator*=(const Bigint&);
	Bigint& operator+=(slongdigit_t);
	Bigint& operator-=(slongdigit_t);
	Bigint& operator*=(slongdigit_t);
	Bigint& operator<<=(int);
	Bigint& operator>>=(int);
	Bigint& negate();
	//Division and modulo operators are explicitly NOT included, to promote clever usage
	//of the divmod function, which combines both.

	Bigint operator+(const Bigint&) const;
	Bigint operator-(const Bigint&) const;
	Bigint operator*(const Bigint&) const;
	Bigint operator+(slongdigit_t) const;
	Bigint operator-(slongdigit_t) const;
	Bigint operator*(slongdigit_t) const;
	Bigint operator<<(int) const;
	Bigint operator>>(int) const;

	//Uses *mathematical* division-with-remainder.
	//If we look at {q,r} = x.divmod(y), then x = q*y + r, and 0<=r<|q|. This is *not* compatible with many other
	//programming languages (and, for that matter, the C++ built-in behaviour).
	std::pair<Bigint,Bigint> divmod(const Bigint&) const;

	bool operator==(const Bigint&) const;
	bool operator!=(const Bigint&) const;
	bool operator<(const Bigint&) const;
	bool operator>(const Bigint&) const;
	bool operator<=(const Bigint&) const;
	bool operator>=(const Bigint&) const;
	bool operator==(slongdigit_t) const;
	bool operator!=(slongdigit_t) const;
	bool operator<(slongdigit_t) const;
	bool operator>(slongdigit_t) const;
	bool operator<=(slongdigit_t) const;
	bool operator>=(slongdigit_t) const;

	int compare(const Bigint&) const; //-1: <; 0: ==; 1: >
	int compare(slongdigit_t) const;
	int compareAbs(const Bigint&) const; //-1: <; 0: ==; 1: >; disregards sign
	int compareAbs(slongdigit_t) const;

	int bitcount() const;
	slongdigit_t lowdigits() const;
	bool even() const;
	bool odd() const;
	int trailingZeros() const; //throws domain_error if called on zero value

	std::string serialiseMantissa() const; //stores everything but the sign
	void deserialiseMantissa(const std::string&); //restores non-negative number; can throw invalid_argument
	std::vector<bool> bits() const; //Stores bits in little-endian order

	friend std::istream& operator>>(std::istream&,Bigint&);
	friend std::ostream& operator<<(std::ostream&,Bigint);


	static Bigint mone; //Some small values to save a constructor call
	static Bigint zero;
	static Bigint one;
	static Bigint two;
};

std::istream& operator>>(std::istream&,Bigint&);
std::ostream& operator<<(std::ostream&,Bigint); //The output operator supports the `hex` modifier