Bag ADT : Abstract Data Types in C++ – 1

Here we will consider the implementation of an ADT which we call the Bag ADT. This container class will contain entries of type Item. We will implement the container class using pre-allocated partially filled array.

Let’s look at the ADT in more detail.

– The Bag class contains a member called data, which is an array of Items.

– The size of the “data” array is defined using a static const called CAPACITY defined inside the Bag class definition.

– We use another member of the Bag class called “used” to indicate how many Items the “data” array currently holds.

– Invariant of the Bag ADT: The member variable “used” is an int in the range 0 through CAPACITY-1. If the “data” array does not contain any Items, then “used” = 0. If the “data” array does contain Items, those Items are contained within the indices 0 through “used”-1. We do not care what is contained in the indices starting from “used” up through CAPACITY-1.

——-

Here we present the file, bag.h.

—–

#ifndef BAG_H

#define BAG_H

#include <iostream.h>

#include <assert.h>  //if we want to use “assert” function.

#include <stdlib.h>//if we want to use “size_t”

class Bag

{

public:

static const int CAPACITY = 10; // This is the max # of Items “data” can hold.

typedef int Item; // if we want, we could change int to char or float or any such type.

//constructor

Bag ( ) { used = 0; }

//Modification member functions

bool insert ( const Item& myItem);

bool remove ( const Item& myItem);

void operator += (const Bag& addend);

//constant member function.

size_t size ( ) const { return used;}

private:

size_t used;

Item data [CAPACITY];

};

// non-member function.

Bag operator + (const Bag& b1, const Bag& b2);

#endif

——-

– The insert member function takes as argument a const reference to an Item to be inserted into the Bag object.If there is space for the item to be inserted, the function inserts it and returns true. Else, it returns false.

– The remove member function takes as argument a const reference to an item, the first copy of which would be removed from the Bag instance, if the item is present in it. It returns true in such a case. Else, it returns false.

– The size member function returns the number of Items currently held by the Bag instance.

– We shall look at the 2 overloaded operators later.

——-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: