The key to developing software is to apply the concept of abstraction.
You will learn many levels of abstraction from this book. Function abstraction is achieved by separating the use of a function from its implementation. The client can use a function without knowing how it is implemented. The details of the implementation are encapsulated in the function and hidden from the client who invokes the function. This is known as information hiding or encapsulation. If you decide to change the implementation, the client program will not be affected, provided that you do not change the function signature. The implementation of the function is hidden from the client in a “black box,” as shown in Figure 6.9.
You have already used the rand() function to return a random number, the time(0) function to obtain the current time, and the max function to find the maximum number. You know how to write the code to invoke these functions in your program, but as a user of these functions, you are not required to know how they are implemented.
The concept of function abstraction can be applied to the process of developing programs. When writing a large program, you can use the “divide-and-conquer” strategy, also known as stepwise refinement, to decompose it into subproblems. The subproblems can be further decomposed into smaller, more manageable ones.
Suppose you write a program that displays the calendar for a given month of the year. The program prompts the user to enter the year and the month, and then displays the entire calendar for the month, as shown in Figure 6.10.
Let us use this example to demonstrate the divide-and-conquer approach.
1. Top-Down Design
How would you start such a program? Would you immediately start coding? Beginning programmers often start by trying to work out the solution to every detail. Although details are important in the final program, concern for detail in the early stages may block the problem-solving process. To make problem-solving flow smoothly, this example begins by using function abstraction to isolate details from design; only later does it implement the details.
For this example, the problem is first broken into two subproblems: get input from the user, and print the calendar for the month. At this stage, you should be concerned with what the subproblems will achieve, not with how to get input and print the calendar for the month. You can draw a structure chart to help visualize the decomposition of the problem (see Figure 6.11a).
You can use the cin object to read input for the year and the month. The problem of printing the calendar for a given month can be broken into two subproblems: print the month title, and print the month body, as shown in Figure 6.11b. The month title consists of three lines: month and year, a dashed line, and the names of the seven days of the week. You need to get the month name (e.g., January) from the numeric month (e.g., 1). This is accomplished in printMonthName (see Figure 6.12a).
To print the month body, you need to know which day of the week is the first day of the month (getStartDay) and how many days the month has (getNumberOfDaysInMonth), as shown in Figure 6.12b. For example, August 2013 has thirty-one days, and the first day of the month is Thursday, as shown in Figure 6.10.
How would you get the start day for a month? There are several ways to find it. Assume that you know that the start day (startDay1800 = 3) for January 1, 1800, was Wednesday. You could compute the total number of days (totalNumberOfDays) between January 1, 1800, and the start day of the calendar month. The computation is (totalNumberOfDays + startDay1800) % 7, because every week has seven days. So the getStartDay problem can be further refined as getTotalNumberOfDays, as shown in Figure 6.13a.
To get the total number of days, you need to know whether a year is a leap year and how many days are in each month. So getTotalNumberOfDays is further refined into two subproblems: isLeapYear and getNumberOfDaysInMonth, as shown in Figure 6.13b. The complete structure chart is shown in Figure 6.14.
2. Top-Down or Bottom-Up Implementation
Now we turn our attention to implementation. In general, a subproblem corresponds to a function in the implementation, although some subproblems are so simple that this is unnecessary. You must decide which modules to implement as functions and which to combine in other functions. Such decisions should be based on whether the overall program will be easier to read because of your choice. In this example, the subproblem readInput can be simply implemented in the main function.
You can use either a “top-down” or a “bottom-up” implementation. The top-down approach implements one function at a time in the structure chart from top to bottom. Stubs can be used for the functions waiting to be implemented. A stub is a simple, but incomplete, version of a function. Usually a stub displays a test message indicating that it was called, and nothing more. The use of stubs enables you to test invoking the function from a caller. Implement the main function first, then use a stub for the printMonth function. For example, let printMonth display the year and the month in the stub. Thus, your program may begin like this:
#include <iostream>
#include <iomanip>
using namespace std;
void printMonth(int year, int month);
void printMonthTit1e(int year, int month);
void printMonthName(int month);
void printMonthBody(int year, int month);
int getStartDay(int year, int month);
int getTotalNumberOfDays(int year, int month);
int getNumberOfDaysInMonth(int year, int month);
bool isLeapYear(int year);
int main()
{
// Prompt the user to enter year
cout << “Enter full year (e.g., 2001): “;
int year;
cin >> year;
// Prompt the user to enter month
cout << “Enter month in number between 1 and 12: “;
int month;
cin >> month;
// Print calendar for the month of the year
printMonth(year, month);
return 0;
}
void printMonth(int year, int month)
{
cout << month << ” ” << year << endl;
}
Compile and test the program and fix any errors. You can now implement the pri ntMonth function. For functions invoked from the printMonth function, you can use stubs.
The bottom-up approach implements one function at a time in the structure chart from bottom to top. For each function implemented, write a test program, known as the driver, to test it. The top-down and bottom-up approaches are both fine. Both implement functions incrementally, help to isolate programming errors, and facilitate debugging. Sometimes they can be used together.
3. Implementation Details
The isLeapYear(int year) function can be implemented using the following code:
return (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0));
Use the following information to implement getTotalNumberOfDaysInMonth(int year, int month):
- January, March, May, July, August, October, and December have 31 days.
- April, June, September, and November have 30 days.
- February has 28 days in a regular year and 29 days in a leap year. A regular year, therefore, has 365 days, and a leap year has 366.
To implement getTotalNumberOfDays(int year, int month), you need to compute the total number of days (totalNumberOfDays) between January 1, 1800, and the first day of the calendar month. You could find the total number of days between the year 1800 and the calendar year and then figure out the total number of days prior to the calendar month in the calendar year. The sum of these two totals is totalNumberOfDays.
To print a body, first add some space before the start day and then print the lines for every week, as shown for August 2013 (see Figure 6.10).
The complete program is given in Listing 6.19.
Listing 6.19 PrintCalendar.cpp
1 #include <iostream>
2 #include <iomanip>
3 using namespace std;
4
5 // Function prototypes
6 void printMonth(int year, int month);
7 void printMonthTitle(int year, int month);
8 void printMonthName(int month);
9 void printMonthBody(int year, int month);
10 int getStartDay(int year, int month);
11 int getTotalNumberOfDays(int year, int month);
12 int getNumberOfDaysInMonth(int year, int month);
13 bool isLeapYear(int year);
14
15 int main()
16 {
17 // Prompt the user to enter year
18 cout << “Enter full year (e.g., 2001): “;
19 int year;
20 cin >> year;
21
22 // Prompt the user to enter month
23 cout << “Enter month in number between 1 and 12: “;
24 int month;
25 cin >> month;
26
27 // Print calendar for the month of the year
28 printMonth(year, month);
29
30 return 0;
31 }
32
33 // Print the calendar for a month in a year
34 void printMonth(int year, int month)
35 {
36 // Print the headings of the calendar
37 printMonthTitle(year, month);
38
39 // Print the body of the calendar
40 printMonthBody(year, month);
41 }
42
43 // Print the month title, e.g., May, 1999
44 void printMonthTitle(int year, int month)
45 {
46 printMonthName(month);
47 cout << ” ” << year << endl;
48 cout << “—————————–” << endl;
49 cout << ” Sun Mon Tue Wed Thu Fri Sat” << endl;
50 }
51
52 // Get the English name for the month
53 void printMonthName(int month)
54 {
55 switch (month)
56 {
57 case 1:
58 cout << “January”;
59 break;
60 case 2:
61 cout << “February”;
62 break;
63 case 3:
64 cout << “March”;
65 break;
66 case 4:
67 cout << “April”;
68 break;
69 case 5:
70 cout << “May”;
71 break;
72 case 6:
73 cout << “June”;
74 break;
75 case 7:
76 cout << “July”;
77 break;
78 case 8:
79 cout << “August”;
80 break;
81 case 9:
82 cout << “September”;
83 break;
84 case 10:
85 cout << “October”;
86 break;
87 case 11:
88 cout << “November”;
89 break;
90 case 12:
91 cout << “December”;
92 }
93 }
94
95 // Print month body
96 void printMonthBody(int year, int month)
97 {
98 // Get start day of the week for the first date in the month
99 int startDay = getStartDay(year, month);
100
101 // Get number of days in the month
102 int numberOfDaysInMonth = getNumberOfDaysInMonth(year, month);
103
104 // Pad space before the first day of the month
105 int i = 0;
106 for (i = 0; i < startDay; i++)
107 cout << ” “;
108
109 for (i = 1; i <= numberOfDaysInMonth; i++)
110 {
111 cout << setw(4) << i;
112
113 if ((i + startDay) % 7 == 0)
114 cout << endl;
115 }
116 }
117
118 // Get the start day of the first day in a month
119 int getStartDay(int year, int month)
120 {
121 // Get total number of days since 1/1/1800
122 int startDay1800 = 3;
123 int totalNumberOfDays = getTotalNumberOfDays(year, month);
124
125 // Return the start day
126 return (totalNumberOfDays + startDay1800) % 7;
127 }
128
129 // Get the total number of days since January 1, 1800
130 int getTotalNumberOfDays(int year, int month)
131 {
132 int total = 0;
133
134 // Get the total days from 1800 to year – 1
135 for (int i = 1800; i < year; i++)
136 if (isLeapYear(i))
137 total = total + 366;
138 else
139 total = total + 365;
140
141 // Add days from Jan to the month prior to the calendar month
142 for (int i = 1; i < month; i++)
143 total = total + getNumberOfDaysInMonth(year, i);
144
145 return total;
146 }
147
148 // Get the number of days in a month
149 int getNumberOfDaysInMonth(int year, int month)
150 {
151 if (month == 1 || month == 3 || month == 5 || month == 7 ||
152 month == 8 || month == 10 || month == 12)
153 return 31;
154
155 if (month == 4 || month == 6 || month == 9 || month == 11)
156 return 30;
157
158 if (month == 2) return isLeapYear(year) ? 29 : 28;
159
160 return 0; // If month is incorrect
161 }
162
163 // Determine if it is a leap year
164 bool isLeapYear(int year)
165 {
166 return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
167 }
The program does not validate user input. For instance, if the user entered a month not in the range between 1 and 12, or a year before 1800, the program would display an erroneous calendar. To avoid this error, add an if statement to check the input before printing the calendar.
This program prints calendars for a month but could easily be modified to print calendars for a year. Although it can only print months after January 1800, it could be modified to trace the day of a month before 1800.
4. Benefits of Stepwise Refinement
Stepwise refinement breaks a large problem into smaller manageable subproblems. Each subproblem can be implemented using a function. This approach makes the program easier to write, reuse, debug, test, modify, and maintain.
Simpler Program
The print calendar program is long. Rather than writing a long sequence of statements in one function, stepwise refinement breaks it into smaller functions. This simplifies the program and makes the whole program easier to read and understand.
Reusing Functions
Stepwise refinement promotes code reuse within a program. The isLeapYear function is defined once and invoked from the getTotal NumberOfDays and getNumberOfDaysInMonth functions. This reduces redundant code.
Easier Developing, Debugging, and Testing
Since each subproblem is solved in a function, a function can be developed, debugged, and tested individually. This isolates the errors and makes developing, debugging, and testing easier.
When implementing a large program, use the top-down or bottom-up approach. Do not write the entire program at once. Using these approaches seems to take more development time (because you repeatedly compile and run the program), but actually it saves time and facilitates debugging.
Better Facilitating Teamwork
Since a large problem is divided into subprograms, the subproblems can be assigned to other programmers. This makes it easier for programmers to work in teams.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.