Michael Coughlan
Page 39
DISPLAY "Enter the State Name - " WITH NO ADVANCING
ACCEPT StateNameIn
SEARCH State
AT END DISPLAY "State Name " StateNameIn " does not exist"
WHEN FUNCTION UPPER-CASE(StateName(StateIdx)) = FUNCTION UPPER-CASE(StateNameIn)
DISPLAY "State Code = " StateCode(StateIdx)
DISPLAY "State Capital = " StateCapital(StateIdx)
END-SEARCH.
GetCodeAndName.
DISPLAY "Enter the State Capital - " WITH NO ADVANCING
ACCEPT StateCapitalIn
SEARCH State
AT END DISPLAY "State capital " StateCapitalIn " does not exist"
WHEN FUNCTION UPPER-CASE(StateCapital(StateIdx)) = FUNCTION UPPER-CASE(StateCapitalIn)
DISPLAY "State Code = " StateCode(StateIdx)
DISPLAY "State Name = " StateName(StateIdx)
END-SEARCH.
309
Chapter 13 ■ SearChing tabular Data
The program contains a table prefilled with the state codes, state names, and state capitals of the American states.
The user provides any one of the three (state code, state name, or state capital), and SEARCH returns the other two from the table.
Most of the program is straightforward and doesn’t require any explanation. However, each of the three
paragraphs GetNameAndCapital, GetCodeAndCapital, and GetCodeAndName makes use of intrinsic functions. You have not encountered intrinsic functions yet. You won’t examine them formally until chapter 15, but I have introduced them here by way of a preview.
A function is a closed subroutine (block of code) that substitutes a returned value for its invocation. In Java, a method with a non-void return value type is a function. COBOL does not have user-defined functions, but it does have a number of built-in system functions called intrinsic functions.
The problem with using user input for comparison purposes is that you have to compare like with like. Alaska is not the same as alaska or ALASKA or aLaska. In GetCodeAndCapital and GetCodeAndName, the intrinsic function UPPER-CASE is used to convert the table data item and the data entered by the user to uppercase to ensure that the program is comparing like with like. In the comparison, the intrinsic function invocation is replaced by the returned function result, and then the comparison is done. For instance, an IF statement such as
IF FUNCTION UPPER-CASE("rEdMond") = FUNCTION UPPER-CASE("REDmond")
becomes
IF "REDMOND" = "REDMOND"
In GetNameAndCapital, I could have used the intrinsic function the same way as in GetCodeAndCapital and
GetCodeAndName; but because the state code is already in uppercase, I took the opportunity to show another way of using intrinsic functions. In this paragraph, I use the intrinsic function to convert the user input to uppercase by moving the converted input data back into the input data item StateCodeIn.
310
Chapter 13 ■ SearChing tabular Data
Searching Multidimensional Tables
In the notes on SEARCH, I observed that SEARCH can have only one controlling index (the IndexName specified in the INDEXED BY phrase attached to the table being searched). Because SEARCH can have only one controlling index, SEARCH
can only be used to search a single dimension of a table at a time. If the table to be searched is multidimensional, then you must control the indexes of the other dimensions.
Listing 13-3 is a small program that demonstrates how to use SEARCH to search a two-dimensional table. The program sets Appointment(3, 2) and Location(3, 2) to “Peter’s Wedding” and “Saint John’s Church”. SEARCH is then used to search the appointments timetable for the appointment details of “Peter’s Wedding”. When found, these details are displayed.
Listing 13-3. Program Demonstrating How to Search a Two-Dimensional Table
IDENTIFICATION DIVISION.
PROGRAM-ID. Listing13-3.
AUTHOR. Michael Coughlan.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 MyTimeTable.
02 DayOfApp OCCURS 5 TIMES INDEXED BY DayIdx.
03 HourOfApp OCCURS 9 TIMES INDEXED BY HourIdx.
04 Appointment PIC X(15).
04 Location PIC X(20).
01 AppointmentType PIC X(15).
01 DaySub PIC 9.
01 HourSub PIC 9.
01 FILLER PIC 9 VALUE ZERO.
88 AppointmentNotFound VALUE ZERO.
88 AppointmentFound VALUE 1.
01 DayValues VALUE "MonTueWedThuFri".
02 DayName PIC XXX OCCURS 5 TIMES.
01 TimeValues VALUE " 9:0010:0011:0012:0013:0014:0015:0016:0017:00".
02 TimeValue PIC X(5) OCCURS 9 TIMES.
PROCEDURE DIVISION.
Begin.
MOVE "Peter's Wedding" TO AppointmentType, Appointment(2, 3)
MOVE "Saint John's Church" TO Location(2, 3)
SET DayIdx TO 1.
PERFORM UNTIL AppointmentFound OR DayIdx > 5
SET HourIdx TO 1
SEARCH HourOfApp
AT END SET DayIdx UP BY 1
WHEN AppointmentType = Appointment(DayIdx, HourIdx)
SET AppointmentFound TO TRUE
SET HourSub TO HourIdx
SET DaySub TO DayIdx
311
Chapter 13 ■ SearChing tabular Data
DISPLAY AppointmentType " is on " DayName(DaySub)
DISPLAY "at " TimeValue(HourSub) " in " Location(DayIdx, HourIdx)
END-SEARCH
END-PERFORM
IF AppointmentNotFound
DISPLAY "Appointment " AppointmentType " was not in the timetable"
END-IF
STOP RUN.
The table used to hold the appointment timetable is described in Example 13-1 and is graphically depicted in Figure 13-4.
Example 13-1. Declarations for the Table Used to Record Appointments
01 MyTimeTable.
02 DayOfApp OCCURS 5 TIMES INDEXED BY DayIdx.
03 HourOfApp OCCURS 9 TIMES INDEXED BY HourIdx.
04 Appointment PIC X(15) VALUE SPACES.
04 Location PIC X(20) VALUE SPACES.
Figure 13-4. Graphical depiction of the two-dimensional table MyTimeTable
As you can see by examining Figure 13-4, in this two-dimensional table each day element consists of a table of hour elements. The table of hour elements is the SEARCH target. In most searches of a multidimensional table, the SEARCH target is the lowest data item in the hierarchy that contains both a OCCURS and an INDEXED BY clause. In this case, HourOfApp is the SEARCH target. In SEARCH, the controlling index is the item attached to the target table by an INDEXED BY clause. In this case, it is HourIdx.
Because SEARCH can have only one controlling index, you have to control the other. In this program, the SET verb is used to control the value in DayIdx, and HourIdx is under the control of SEARCH.
When SEARCH executes, it searches whichever of the HourOfApp tables is pointed to by DayIdx. If the appointment is not found, AT END activates, DayIdx is incremented, and SEARCH is executed again, this time examining the HourOfApp table in the next DayOfApp element. If the appointment is found, WHEN activates, and the HourIdx and DayIdx values are used to display the time (24-hour format) and day of the appointment. DayName and TimeValue are set up using the facility introduced in the ANS 85 version of COBOL that allows you to create prefilled tables without using the REDEFINES clause.
312
Chapter 13 ■ SearChing tabular Data
Searching the First Dimension of a Two-Dimensional Table
Listing 13-3 uses SEARCH to search the second dimension of the two-dimensional table. It does not normally make sense to search the first dimension of a two-dimensional table, because as you can see from Figure 13-4, each element at that level contains a table, not a discrete value. Sometimes, though, you need to perform such a search.
Suppose you have a two-dimensional table that records the number of jeans sold in three different colors in 150
shops. Suppose for each group of jeans sales totals, you also record the shop name. The table to record this information is described in Example 13-2 and is graphically depicted in Figure 13-5.
Example 13-2. Description of JeansSalesTable
01 JeansSalesTable.
02 Shop OCCURS 150 TIMES INDEXED BY ShopIdx.
03 ShopName PIC X(15).
03 JeansColor OCCURS 3 TIMES INDEXED BY ColorIdx.
04 TotalSold PIC 9(5).
Figure 13-5. Graphical depiction of JeansSalesTable
Listing 13-4 is a simple program that shows how to use SEARCH to search the first dimension of a two-dimensional table. To keep the program simple, I haven’t filled the table with all the values shown in Figure 13-5; only the element Shop(3) is filled with data values.
Listing 13-4. Searching the First Dimension of a Two-Dimensional Table
IDENTIFICATION DIVISION.
PROGRAM-ID. Listing13-4.
AUTHOR. Michael Coughlan.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 JeansSalesTable.
02 Shop OCCURS 150 TIMES INDEXED BY ShopIdx.
03 ShopName PIC X(15) VALUE SPACES.
03 JeansColor OCCURS 3 TIMES.
04 TotalSold PIC 9(5) VALUE ZEROS.
01 ShopQuery PIC X(15).
01 PrnWhiteJeans.
02 PrnWhiteTotal PIC ZZ,ZZ9.
02 FILLER PIC X(12) VALUE " white jeans".
313
Chapter 13 ■ SearChing tabular Data
01 PrnBlueJeans.
02 PrnBlueTotal PIC ZZ,ZZ9.
02 FILLER PIC X(12) VALUE " blue jeans".
01 PrnBlackJeans.
02 PrnBlackTotal PIC ZZ,ZZ9.
02 FILLER PIC X(12) VALUE " black jeans".
PROCEDURE DIVISION.
Begin.
MOVE "Jean Therapy" TO ShopName(3), ShopQuery
MOVE 00734 TO TotalSold(3, 1)
MOVE 04075 TO TotalSold(3, 2)
MOVE 01187 TO TotalSold(3, 3)
SET ShopIdx TO 1
SEARCH Shop
AT END Display "Shop not found"
WHEN ShopName(ShopIdx) = ShopQuery
MOVE TotalSold(ShopIdx, 1) TO PrnWhiteTotal
MOVE TotalSold(ShopIdx, 2) TO PrnBlueTotal
MOVE TotalSold(ShopIdx, 3) TO PrnBlackTotal
DISPLAY "Sold by " ShopQuery
DISPLAY PrnWhiteJeans
DISPLAY PrnBlueJeans
DISPLAY PrnBlackJeans
END-SEARCH
STOP RUN.
The SEARCH ALL Verb
As I noted earlier in this chapter, the method used to search a table depends heavily on the way the values are organized in the table. If the values are not ordered, then the only strategy available is a linear search. If the values are ordered, then you have the option of using either a linear search or a binary search. This section introduces SEARCH
All, the COBOL verb used for binary searches.
Because SEARCH ALL implements a binary search, it only works on an ordered table. The table must be ordered on the values in the element or, where the element is a group item, on a data item within the element. The item on which the table is ordered is known as the key field and is identified using the KEY IS phrase in the table declaration.
KEY IS Clause
The KEY IS clause is used to identify the data item on which the table to be searched is ordered. If you want to search a table using SEARCH ALL, the table declaration must contain a KEY IS phrase. The OCCURS metalanguage that includes the KEY IS clause is given in Figure 13-6.
314
Chapter 13 ■ SearChing tabular Data
Figure 13-6. OCCURS metalanguage including the KEY IS clause
How a Binary Search Works
I have mentioned that SEARCH ALL implements a binary search. Before discussing SEARCH ALL itself, let’s take the time to refresh your memory about how a binary search works.
A binary search works by repeatedly dividing the search area into a top half and a bottom half, deciding which half contains the required item, and making that half the new search area. The search continues halving the search area like this until the required item is found or the search discovers that the item is not in the table.
The algorithm for a binary search is given in Example 13-3.
Example 13-3. Binary Search Algorithm
PERFORM UNTIL ItemFound OR ItemNotInTable
COMPUTE Middle = (Lower + Upper) / 2
EVALUATE TRUE
WHEN Lower > Upper THEN SET ItemNotInTable TO TRUE
WHEN KeyField(Middle) < SearchItem THEN Lower = Middle + 1
WHEN KeyField(Middle) > SearchItem THEN Upper = Middle -1
WHEN KeyField(Middle) = SearchItem THEN SET ItemFound TO TRUE
END-EVALUATE
END-PERFORM
To illustrate how this algorithm works, let’s consider it in the context of a table containing the letters of the alphabet. The table holding the letters is described in Example 13-4, and its representation in memory is illustrated pictorially in Figure 13-7.
Example 13-4. Table Prefilled with the Letters of the Alphabet
01 LetterTable.
02 LetterValues.
03 FILLER PIC X(13)
VALUE "ABCDEFGHIJKLM".
03 FILLER PIC X(13)
VALUE "NOPQRSTUVWXYZ".
02 FILLER REDEFINES LetterValues.
03 Letter PIC X OCCURS 26 TIMES
ASCENDING KEY IS Letter
INDEXED BY LetterIdx.
Figure 13-7. Table containing the letters of the alphabet
315
Chapter 13 ■ SearChing tabular Data
Suppose you want to search LetterTable to find the position of the letter R. The general binary search algorithm introduced in Example 13-3 can be made more specific to the problem, as shown in Example 13-5. Figure 13-8 shows a succession of diagrams illustrating the application of this algorithm.
Example 13-5. Binary Search to Find the Letter R
PERFORM UNTIL ItemFound OR ItemNotInTable
COMPUTE Middle = (Lower + Upper) / 2
EVALUATE TRUE
WHEN Lower > Upper THEN SET ItemNotInTable TO TRUE
WHEN Letter(Middle) < "R" THEN Lower = Middle + 1
WHEN Letter(Middle) > "R" THEN Upper = Middle -1
WHEN Letter(Middle) = "R" THEN SET ItemFound TO TRUE
END-EVALUATE
END-PERFORM
Figure 13-8. Finding the letter R using a binary search
316
Chapter 13 ■ SearChing tabular Data
SEARCH ALL
The metalanguage for SEARCH ALL is given in Figure 13-9.
Figure 13-9. Metalanguage for SEARCH ALL
Consider the following:
• The OCCURS clause of the table to be searched must have a KEY IS clause in addition to an
INDEXED BY clause. The KEY IS clause identifies the data item on which the table is ordered.
• When you use SEARCH ALL, you do not need to set the table index to a starting value because
SEARCH ALL controls it automatically.
• ElementIdentifier must be the item referenced by the table’s KEY IS clause.
• ConditionName may have only one value, and it must be associated with a data item
referenced by the table’s KEY IS clause.
■ Bug Alert SEARCH ALL presents no problems when the table is fully loaded (all the elements have been assigned data values); but if the table is not fully loaded, then SEARCH ALL may not function correctly because the values in the unloaded part of the table will not be in key order. to rectify this problem, before you load the table you should fill it with HIGH-VALUES if the key is ascending or LOW-VALUES if the key is descending. See listing 13-5 for an example.
Listing 13-5 is a simple program that displays the country name when the user enters a two-letter Internet code. Unlike the other example programs in this chapter, the table data in Listing 13-5 is
obtained from a file that is loaded into the table at runtime. This is a much more realistic scenario for any sort of volatile data. Countries come and go and change their names with sufficient frequency that loading the table from a file makes good sense from a maintenance perspective. The table can hold up to 250 countries, but the country-code file contains only 243 entries at present.
317
Chapter 13 ■ SearChing tabular Data
Listing 13-5. Displaying the Corresponding Country Name When the User Enters a Country Code IDENTIFICATION DIVISION.
PROGRAM-ID. Listing13-5.
AUTHOR. Michael Coughlan.
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT CountryCodeFile ASSIGN TO "Listing13-5.dat"
ORGANIZATION IS LINE SEQUENTIAL.
DATA DIVISION.
FILE SECTION.
FD CountryCodeFile.
01 CountryCodeRec.
88 EndOfCountryCodeFile VALUE HIGH-VALUES.
02 CountryCodeCF PIC XX.
02 CountryNameCF PIC X(25).
WORKING-STORAGE SECTION.
01 CountryCodeTable.
02 Country OCCURS 300 TIMES
ASCENDING KEY IS CountryCode
INDEXED BY Cidx.
03 CountryCode PIC XX.
03 CountryName PIC X(25).
01 CountryCodeIn PIC XX.
88 EndOfInput VALUE SPACES.
01 FILLER PIC 9 VALUE ZERO.
88 ValidCountryCode VALUE 1.
PROCEDURE DIVISION.
Begin.
PERFORM LoadCountryCodeTable
PERFORM WITH TEST AFTER UNTIL EndOfInput
PERFORM WITH TEST AFTER UNTIL ValidCountryCode OR EndOfInput
DISPLAY "Enter a country code (space to stop) :- "
WITH NO ADVANCING
ACCEPT CountryCodeIn
SEARCH ALL Country
AT END IF NOT EndOfInput
DISPLAY "Country code " CountryCodeIn " is not valid"