#pragma once

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

class Bigint{
public:
	using digit_t=uint32_t;
	using longdigit_t=uint64_t;
	using slongdigit_t=int64_t;
	static const int digit_bits=8*sizeof(digit_t);

private:
	std::vector<digit_t> digits;
	int sign;

	static void add(Bigint&,const Bigint&); //ignores sign of arguments
	static void subtract(Bigint&,const Bigint&); //ignores sign of arguments; assumes a>=b
	static Bigint product(const Bigint&,const Bigint&);

	void shrink();
	void normalise();
	void checkconsistent();

	std::pair<Bigint,Bigint> divmod(const Bigint&,int depth) const;

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

	Bigint& operator=(const Bigint&)=default;
	Bigint& operator=(Bigint&&)=default;
	Bigint& operator=(slongdigit_t);

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

	Bigint operator+(const Bigint&) const;
	Bigint operator-(const Bigint&) const;
	Bigint operator*(const Bigint&) const;
	Bigint operator<<(int) const;
	Bigint operator>>(int) const;
	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;

	std::vector<char> serialise() const;
	void deserialise(const std::vector<char>&);
	std::vector<bool> bits() const;

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

	digit_t _digit(int idx) const;
};

Bigint pow(const Bigint &b,const Bigint &ex);

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