# Abstract Data Type

Learn about the abstract huge integer data type.

Let’s explore the abstract data type (ADT) for storing huge integers. Here are some examples of huge integers of various lengths:

-100385934890589348509834895+20034985348598394850983498598348598349850834-27374759690493727283939222737475969049372728393922332957273757217+3329593827228272737572172737475969049372728393922-300

To effectively store such huge integers, we require three fundamental elements: the sign of the number, the number of digits, and a dynamic array (a pointer that points to a heap array holding its individual digits).

Let’s discuss how we can implement this ADT in C++.

## The `HugeInt`

class structure

This class structure includes private members for the sign (`isNeg`

), size (`size`

), and array of digits (`Ds`

). Along with this, we add a basic constructor for initializing the huge integer.

class HugeInt{bool isNeg;int size;int *Ds;public:HugeInt(string s); // Constructor to initialize digits and sign};

Before we delve into the implementation of `HugeInt.cpp`

, let’s first grasp the logical and physical representation of how a huge integer will be stored, taking into consideration stack and heap segments.

### Pictorial representation of a huge integer object

Take a moment to examine the pictorial representation below of a huge integer object, where the object is declared within the stack at a local level, the digits array is a dynamic memory (residing in the heap), and `Ds`

points toward it:

### Deeper view of huge integer ADT

Let’s delve deeper into the ADT and identify the necessary functions to enhance our huge integer class, enabling the demonstration outlined below. The demo involves processing a set of huge integers, as specified in the `HIs.txt`

file, which initially indicates the number of huge integers to process, followed by their respective numerical values.

5 12 200 2 999999999999999999999999999999 -61969987109750917095790

#### Input and output functions

We’ll add the constructor that initializes the object from an input stream (`ifstream`

) and overloads the output stream operator (`<<`

) to facilitate the printing of `HugeInt`

objects in the output stream.

// Input streamHugeInt(ifstream& Rdr);// Output the numbersfriend ostream& operator<<(ostream&, const HugeInt& I);

#### Utility functions (arithmetic operations)

To enable arithmetic and logical operators, we’ll base our foundation on some of the helper functions. These utility functions include value-based addition and subtraction, as well as comparisons for less than, greater than, and equal to, based on value. We’ll see how these utility functions simplify our operators’ implementations. Also, we use the `trim`

method to remove leading zeros and the overloaded subscript operators `[]`

enable access to individual digits of `HugeInt`

. By incorporating these helper functions, the versatility of the `HugeInt`

class is significantly augmented, enabling the execution of diverse arithmetic and relational operations on large integers.

HugeInt quantitywiseAdd(const HugeInt& I2)const;HugeInt quantitywiseSub(const HugeInt& I2)const;bool isQuantitywiseLess(const HugeInt& I2)const;bool isQuantitywiseGreater(const HugeInt& I2)const;bool isQuantitywiseEqual(const HugeInt& I2)const;void trim();int operator[](int i)const;int& operator[](int i);

#### Add and subtract operator

After adding the constructors and utility functions, we’ll augment the `HugeInt`

class with operators for addition and subtraction (as operators). These operators provide a concise and convenient way to perform arithmetic operations between `HugeInt`

objects, just like any primitive data type. The following operators will be added to the `HugeInt`

ADT:

HugeInt operator+(const HugeInt& I2)const; // H1 + H2const HugeInt& operator+=(const HugeInt& I2); // H1 += H2HugeInt operator-(const HugeInt& I2)const; // H1 - H2HugeInt operator-=(const HugeInt& b); // H1-= H2HugeInt operator-()const; // H1 = -H2

#### Unary operators

In C++ syntax, the preferred method for incrementing or decrementing a value by 1 is typically through the unary `++`

or `--`

operators. Therefore, we’ll implement post-increment, pre-increment, post-decrement, and pre-decrement operators. These additions facilitate the seamless manipulation of `HugeInt`

objects, offering pre- and post-increment/decrement functionality.

HugeInt operator++(int b); // H1++HugeInt operator++(); // ++H1HugeInt operator--(int b); // H1--HugeInt operator--(); // --H1

#### Comparison operators

In C++ syntax, using comparison operators, such as `<`

, `<=`

, `>`

, `>=`

, `==`

, is a straightforward way to evaluate relationships between values. We’ll incorporate these operators into our `HugeInt`

class, allowing easy and intuitive comparisons. This integration empowers users to assess relationships between `HugeInt`

objects effortlessly, using the standard set of comparison operators.

bool operator<(const HugeInt& I2)const; // H1< H2bool operator<=(const HugeInt& I2)const; // H1<=H2bool operator>(const HugeInt& I2)const; // H1> H2bool operator>=(const HugeInt& I2)const; // H1>=H2bool operator==(const HugeInt& I2)const; // H1==H2

#### Multiplication and division operators

To finalize the implementation of our `HugeInt`

class and equip it with additional robust functionality, we’ll integrate the multiplication and division operators, i.e., `*`

, `*=`

, `/`

, `/=`

, `%`

, `%=`

. These operators provide essential arithmetic capabilities, allowing users to perform nontrivial operations on `HugeInt`

objects. This comprehensive addition ensures a fully featured and versatile `HugeInt`

class capable of handling a wide range of mathematical operations with ease.

HugeInt operator*(const HugeInt& b)const;HugeInt operator/(const HugeInt& b)const;HugeInt operator%(const HugeInt& b)const;const HugeInt& operator*=(const HugeInt& I2);const HugeInt& operator/=(const HugeInt& I2);const HugeInt& operator%=(const HugeInt& I2);