It is quite difficult to describe how to design an abstract data type (ADT) offhand. Neither is there a fixed way of designing ADTs. Sometimes, I feel that designing an ADT can be more of an art than a science. However, here are some tips on how to design one.
The most important thing about an ADT is that it should be self-contained and reusable. That is, if one wrote an ADT called Date, then by merely copying the files containing the class definition and implementation of the Date ADT (typically named Date.h and Date.cpp) and doing the necessary header file includes, then any program can use the Date ADT.
For example, checking for the validity of the date entered should be part of the Date ADT. Why do I say so? Supposed one implemented the error checking outside the ADT, in the main() function contained in Prog1.cpp. Later, when he or she want to use the Date ADT in another program, say Prog2.cpp, and copy the Date.h and Date.cpp files over. Then the error checking functionality is lost, so the users of the Prog2.cpp program can enter dates like 31 February 2004. And if he or she re-implement the error checking functionality in Prog2.cpp, then he or she is reinventing the wheel and duplicating the work done in Prog1.cpp, so the Date ADT is no longer as reusable as he or she had wanted it to be.
Another tip for designing a good ADT is to make only the necessary things public, and do not make the internal data structures and methods public. We can consider the public interface of an ADT as a contact between the ADT and its user. Put it another way, treat the ADT as a company providing a certain range of services, the user of the ADT as a customer using the services, and the class members and methods in the public section of the ADT as the contract between the customer and the company. The contract will state exactly what services the company and provide and the minimum and maximum service levels the customer should expect.
To reiterate the concept of making only the relevant methods public, let us consider the following negative example, using the Date ADT once again.
class Date {
public:
int day;
int month;
int year;
Date();
Date(int day, int month, int year);
// Other methods...
};
Suppose the implementation of this Date ADT performs error checking in the Date(int day, int month, int year) constructor. However, this still does not prevent users from abusing the ADT and entering invalid dates. A specific example follows:
Date d; d.day = 32; d.month = -1; d.year = 99999999;
The abuse of the ADT can be done because the class members day, month and year have been made public and by using the contract idea, it is legal to access these class members directly. A better way of writing the Date ADT is as follows:
class Date {
private:
int day;
int month;
int year;
public:
Date();
Date(int day, int month, int year);
int getDay();
int getMonth();
int getYear();
// Other methods...
};
By making the class members day, month and year private, we can prevent the abuse by forcing the user of the ADT to set the date through the Date(int day, int month, int year) constructor, and so error checking will always be done. Then we create public accessor methods to allow the user to retrieve the day, month and year from the ADT, so no functionality is lost here.
Further, if we want to also allow the user to change the date after an instance of the ADT has been created, we can add a public setDate(int day, int month, int year) accessor method, so the class definition becomes as follows:
class Date {
private:
int day;
int month;
int year;
public:
Date();
Date(int day, int month, int year);
int getDay();
int getMonth();
int getYear();
void setDate(int day, int month, int year);
// Other methods...
};
Of course, the setDate(int day, int month, int year) method should also perform the same error checking as the Date(int day, int month, int year) constructor. Indeed, both the constructor and the accessor will have identical code, so we can consider having the constructor calling the accessor. The following will give an idea of how these methods can be implemented.
Date::Date() {
setDate(1, 1, 1);
}
Date::Date(int day, int month, int year) {
setDate(day, month, year);
}
int Date::getDay() {
return this->day;
}
int Date::getMonth() {
return this->month;
}
int Date::getYear() {
return this->year;
}
void Date::setDate(int day, int month, int year) {
// Do error checking here, code for error checking omitted...
this->day = day;
this->month = month;
this->year = year;
}
There is one added advantage of hiding the internal representation of the date inside the private section of the ADT. The advantage is that it facilitates improvements to the ADT. Suppose it is found that it is more efficient to store the number of days since 1 January 1 (i.e. 1 January 1 is labeled as day 0, 2 January 1 is labeled as day 2, 3 January 1 is labeled as day 2, etc.) instead of the day, month and year of the date. Then we can change the class definition for the Date ADT as follows, keeping all public methods unchanged, and change the class implementation accordingly:
class Date {
private:
int daynumber;
public:
Date();
Date(int day, int month, int year);
int getDay();
int getMonth();
int getYear();
void setDate(int day, int month, int year);
// Other methods...
};
So long the public interface of the ADT is unchanged, existing code using the ADT will not be broken and can continue to use the new Date ADT as if nothing has changed. One can easily see that if the day, month and year class members in the original class were made public and some user had directly accessed them, then modifying the ADT like the way above would have broken that user's code.
Do consider the fact that in large software engineering projects, the code is written by many people, and it is very common for one person to design and implement an ADT and another few people writing their own code that uses that ADT. In this respect, the very last point of not breaking code is very important here.
One more thing about effective ADT design I have not yet discussed is that it is also very important to document the interface of the ADT properly and clearly. A number of software projects have failed because of poor documentation of the code, and different programmers have interpreted the codes differently, so the product does not work. Hence, it is also advisable to put comments in your code.
This is the reason why I always recommend writing function declarations and ADT method definitions like
void setDate(int day, int month, int year);
instead of
void setDate(int, int, int);
because the latter does not make it clear which parameter is the day, which parameter is the month and which parameter is the year. Trouble will begin when users make the wrong assumptions and start to call the function or method using the wrong parameters.