9.1 Data Structures: The String Data Type

Until now we have used strings in Ada in a very intuitive way, without much systematic consideration. In this section we will take a somewhat more systematic look at the character string, an important data structure in many applications. Ada provides a predefined type String, which is a certain kind of array of characters. The basic ideas are as follows:

A string value is an array of characters, with a subscript range that must be a subtype of Positive.
It is possible to assign or refer to a part, or slice, of a string.
String values can be compared and assigned like other Ada variables, but their lengths must match exactly.
Strings can be concatenated, or "pasted together," to form longer ones.

Declaring a String Variable

The declarations

    NameSize : CONSTANT Positive := 11;
    SUBTYPE NameType IS String(1..11);

provide for string values containing exactly 11 characters. Now the declarations

    FirstName : NameType;
    LastName  : NameType;

allocate storage for two string variables.

Referencing Individual Characters in a String

We can manipulate individual characters in a string variable in the same way that we manipulate individual elements of an array.

Example 9.1

The program fragment below reads 11 characters into string variable FirstName and displays all characters stored in the string.

    Ada.Text_IO.Put(Item => "Enter your first name and an initial,");
    Ada.Text_IO.Put(Item => " exactly 11 characters > ");

    FOR I IN 1..NameSize LOOP
    	Ada.Text_IO.Get (Item => FirstName(I));
    END LOOP;

    Ada.Text_IO.Put (Item => "Hello ");
    FOR I IN 1..NameSize LOOP
    	Ada.Text_IO.Put (Item => FirstName(I));
    END LOOP;

    Ada.Text_IO.Put(Item => '!');
    Ada.Text_IO.New_Line;

A sample run of this program segment is shown below.

    Enter your first name and an initial, exactly 11 characters > Jonathon B.
    Hello Jonathon B.!

Eleven data characters are read into string variable FirstName after the prompt in the first line is displayed. The string variable FirstName is

    (1)  (2)  (3)  (4)  (5)  (6)  (7)  (8)  (9)  (10)  (11)
     J    o    n    a    t    h    o    n         B     .

The statements

    FirstName(9) := ''';
    FirstName(10) := 's';

replace the contents of FirstName(9) (the blank character) and FirstName(10) (capital B) with the two characters shown above (an apostrophe and the letter s). The IF statement

    IF FirstName(I) = ''' THEN
    	Ada.Text_IO.Put (Item => "possessive form");
    END IF;

displays the message possessive form when the value of I is 8.

A Character Is Not Compatible with a One-Character String

Example 9.2

String variable OneString, declared below, is a string of length one.

    OneString : String(1..1);
    NextCh : Character;

The assignment statements

    OneString(1) := NextCh;
    NextCh := OneString(1);

are valid; they store a copy of NextCh in string OneString. However, the assignment statements

    OneString := NextCh;
    NextCh := OneString;

are invalid; they cause a "type compatibility" compilation error. A string that happens to be only one character long is still of a different type than a character!

Assigning, Comparing, and Displaying Strings

Besides manipulating individual characters in a string variable, we can manipulate the string as a unit.

Example 9.3

The assignment statement

    LastName := "Appleseed";

appears to store the string value Appleseed in the string variable LastName declared earlier. This is not true, however: String assignment is only correct if the lengths of the strings on both sides are exactly the same. Because Appleseed has only nine letters, the assignment above might cause a warning at compilation time but would always cause Constraint_Error to be raised at execution time. If we add two blanks, the assignment will go through as desired:

    LastName := "Appleseed  ";

The contents of LastName is

    (1)  (2)  (3)  (4)  (5)  (6)  (7)  (8)  (9)  (10)  (11)
     A    p    p    l    e    s    e    e    d     #     #

where the # characters are used here only to give a visible picture of the blank.

The statements

    Ada.Text_IO.Put(Item => LastName);  
    Ada.Text_IO.Put (Item => ', ');
    Ada.Text_IO. (Item => FirstName);
    Ada.Text_IO.New_Line;

display the output line

    Appleseed  , Jonathon B.

Note the two blanks following the last name!

As with other array types, we can copy the contents of one string variable to another of the same length, and we can compare two strings of the same length.

Example 9.4

The statement

    FirstName := LastName;

copies the string value stored in LastName to FirstName; the Boolean condition

    FirstName = LastName

is True after the assignment but would have been False before.

Reading Strings

Ada provides several Get procedures in Ada.Text_IO for entering a string value.

Example 9.5

The statement

    Ada.Text_IO.Get(FirstName);

reads exactly 11 characters (including blanks, punctuation, and so on) into the string variable FirstName. The data entry operation is not terminated by pressing the RETURN key; if only five characters are entered before the RETURN is pressed, the computer simply waits for the additional 6 characters! This is a common error made by many Ada beginners, who think their program is "stuck" when nothing seems to happen after RETURN is pressed. In fact, the program is doing just what it was told: Read exactly 11 characters. It is not possible to read more than 11 characters into FirstName; the additional characters just stay in the file waiting for the next Get call.

This is an unsatisfying way to read strings, since it provides no way to read a string shorter than the maximum length of the string variable. A better way is to use the Get_Line procedure in Ada.Text_IO.

Example 9.6

Given a variable

    NameLength : Natural;

the statement

    Ada.Text_IO.Get_Line (Item => LastName, Last => NameLength);

tries to read 11 characters as before, but if RETURN is pressed before 11 characters are read, reading stops. NameLength is used as an OUT parameter corresponding to Get_Line's formal parameter Last, and after the Get operation, NameLength contains the actual number of characters read. If fewer characters are read than the string can accommodate, the remaining characters in the string are undefined.

Example 9.7

Given the declarations

    FirstNameLength : Natural;
    LastNameLength  : Natural;

the statements

    Ada.Text_IO.Put(Item => "Enter your first name followed by CR >");  
    Ada.Text_IO.Get_Line(Item => FirstName, Last =>FirstNameLength); 
    Ada.Text_IO.Put(Item => "Enter your last name followed by CR >");
    Ada.Text_IO.Get_Line(Item => LastName, Last => LastNameLength);

can be used to enter string values into the string variables FirstName and LastName. Up to 11 characters can be stored in FirstName and LastName. If the data characters Johnny are entered after the first prompt and the data characters Appleseed are entered after the second prompt, string FirstName contains

    (1)  (2)  (3)  (4)  (5)  (6)  (7)  (8)  (9) (10) (11)
     J    o    h    n    n    y    ?    ?    ?    ?    ?

and string LastName contains

    (1)  (2)  (3)  (4)  (5)  (6)  (7)  (8)  (9) (10) (11)
     A    p    p    l    e    s    e    e    d    ?    ?

The variables FirstNameLength and LastNameLength contain 5 and 9, respectively. The statement

    Ada.Text_IO.Put(Item => FirstName);

will display Johnny followed by five blanks.

The first two syntax displays below appeared originally in Section 2.8; they are repeated here for completeness. The third display specifies the Get_Line procedure.

SYNTAX DISPLAY
Character Get Procedure

Form:

Ada.Text_IO.Get (Item => variable);

Example:

Ada.Text_IO.Get (Item => Initial1);

Interpretation:

The next character pressed on the keyboard is read into variable (type Character). A blank counts as a character; a RETURN does not.

SYNTAX DISPLAY
String Get Procedure

Form:

Ada.Text_IO.Get (Item => variable );

Example:

Ada.Text_IO.Get (Item => First_Name);

Interpretation:

Variable must be a variable of type String (low..high), where 1 <= low <= high. Exactly high - low + 1 characters are read from the keyboard. A RETURN does not count as a character; the computer will wait until exactly the specified number of characters are entered.

SYNTAX DISPLAY
String Get_Line Procedure

Form:

Ada.Text_IO.Get_Line (Item => variable1 , Last => variable2);

Example:

Ada.Text_IO.Get_Line (Item => First_Name, Last => NameLength);

Interpretation:

Variable1 must be a variable of type String (low..high), where 1 <= low <= high. Get_Line attempts to read high - low + 1 characters. Reading stops if RETURN is pressed. After the Get_Line operation, variable2 contains the actual number of characters read. If the string variable is only partially filled by the operation, the remaining characters are undefined.

String Slicing

The flexibility of string handling in Ada is enhanced by using string slicing. This is the ability to store into, or extract, a slice, or section, of a string variable just by specifying the bounds of the desired section.

Example 9.8

Given the string variables FirstName and LastName as above, the slices

    FirstName(1..4)
    LastName (5..11)

refer to the first through fourth characters of FirstName and the fifth through eleventh characters of LastName, respectively. The statement

    Ada.Text_IO.Put(Item => FirstName(1..FirstNameLength));

displays the string Johnny with no extra blanks. Given declarations

    WholeNameLength : Natural;
    WholeName : String(1..24);

the statements

    WholeNameLength := FirstNameLength + LastNameLength + 2;
    WholeName(1..LastNameLength) := LastName(1..LastNameLength);
    WholeName(LastNameLength+1..LastNameLength+2) := ", ";
    WholeName(LastNameLength+3..WholeNameLength) := FirstName(1..FirstNameLength);
    Ada.Text_IO.Put(Item => WholeName(1..WholeNameLength));

will store in WholeName, and display

    Appleseed, Johnny

String Concatenation

One more string operation merits consideration here. The string concatenation operator &, applied to two strings S1 and S2, concatenates, or "pastes together," its two arguments.

Example 9.9

The statement

    S3 := S1 & S2;

stores in S3 the concatenation of S1 and S2. For the assignment to be valid, the length of S3 still must match the sum of the lengths of S1 and S2; if it does not, Constraint_Error will be raised, as usual. Continuing with the name example above, WholeName can be created more simply using concatenation:

    WholeNameLength := FirstNameLength + LastNameLength + 2;
    WholeName(1..WholeNameLength) := LastName(1..LastNameLength) & ", " &
    FirstName(1..FirstNameLength);

The result of a concatenation can also be passed directly as a parameter, for example to Ada.Text_IO.Put:

    Ada.Text_IO.Put(Item => LastName(1..LastNameLength) & ", " &
    FirstName(1..FirstNameLength));

Case Study: Generating Cryptograms

PROBLEM SPECIFICATION

A cryptogram is a coded message formed by substituting a code character for each letter of an original message, usually called the plain text. The substitution is performed uniformly though the original message, that is, all A's might be replaced by Z, all B's by Y, and so on. We will assume that all other characters, including numbers, punctuation, and blanks between words, remain unchanged.

ANALYSIS

The program must examine each character in the message and replace each character that is a letter by its code symbol. We will store the code symbols in an array Code with subscript range ('A'..'Z') and element type Character. The character stored in Code('A') will be the code symbol for the letter 'A'. This will enable us simply to look up the code symbol for a letter by using that letter as an index to the array Code.

Data Requirements

Problem Inputs

the array of code symbols (Code : ARRAY (UpperCase) OF Character)

the plain text message

Problem Outputs

the encrypted message or cryptogram

DESIGN

The initial algorithm follows.

Algorithm

1. Read in the code symbol for each letter.

2. Read the plain text message.

3. Encode the message.

4. Display the cryptogram.

Step 1 Refinement

1.1 Display the alphabet.

1.2. FOR each uppercase letter LOOP

Read in the code symbol and store it in string Code.

END LOOP;

Step 3 Refinement

3.1 FOR each character in the message LOOP

3.2 IF it is a letter THEN

3.3 Convert to the corresponding code symbol.

END IF;

END LOOP;

TEST PLAN

We leave the test plan as an exercise.

IMPLEMENTATION

Program 9.1 shows the implementation of the cryptogram generator.

Program 9.1
Cryptogram Generator

WITH Ada.Text_IO;
PROCEDURE Cryptogram IS
------------------------------------------------------------------------
--| Program to generate a cryptogram
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------------
 
  SUBTYPE Letter IS Character RANGE 'A'..'Z';
  TYPE CodeArray IS ARRAY (Letter) OF Character;

  SUBTYPE Message IS String(1..60);

  Code      : CodeArray;          -- input - array of code symbols
  PlainText : Message;            -- input - plain text message
  CodedText : Message;            -- output - coded message

  HowLong   : Natural;   

  FUNCTION Cap (InChar : Character) RETURN Character IS
  -- Pre: InChar is defined
  -- Post: if InChar is a lowercase letter, returns its uppercase
  --   equivalent; otherwise, returns InChar unmodified

  BEGIN -- Cap

    IF InChar IN 'a'..'z' THEN
      RETURN Character'Val(Character'Pos(InChar)
            - Character'Pos('a') + Character'Pos('A'));
    ELSE
      RETURN InChar;
    END IF;

  END Cap;
    
BEGIN -- Cryptogram   

  Ada.Text_IO.Put(Item => "Enter a code symbol under each letter.");
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put(Item => "ABCDEFGHIJKLMNOPQRSTUVWXYZ");  
  Ada.Text_IO.New_Line;

  -- Read each code symbol into array Code.   
  FOR NextLetter IN Letter LOOP
    Ada.Text_IO.Get(Item => Code(NextLetter));
  END LOOP;
  Ada.Text_IO.Skip_Line;

  -- Read plain text message
  Ada.Text_IO.Put(Item => "Enter each character of your message.");
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put(Item => "No more than 60 characters, please.");
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put(Item => "Press RETURN after your message.");
  Ada.Text_IO.New_Line;

  -- Display scale so user knows how many characters
  Ada.Text_IO.Put(Item => "         1         2         3" &
                          "         4         5         6");
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put(Item => "123456789012345678901234567890" &
                          "123456789012345678901234567890");
  Ada.Text_IO.New_Line;

  Ada.Text_IO.Get_Line (Item => PlainText, Last => HowLong);

  -- Encode message by table lookup
  FOR WhichChar IN 1..HowLong LOOP
    IF Cap(PlainText(WhichChar)) IN Letter THEN
      CodedText(WhichChar) := Code(Cap(PlainText(WhichChar)));
    ELSE
      CodedText(WhichChar) := PlainText(WhichChar);
    END IF;
  END LOOP;
  
  -- Display coded message
  Ada.Text_IO.Put (Item => CodedText(1..HowLong));
  Ada.Text_IO.New_Line;

END Cryptogram;

Sample Run

Enter a code symbol under each letter.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
zyxwvutsrqponmlkjihgfedcba
Enter each character of your message.
No more than 60 characters, please.
Press RETURN after your message.
         1         2         3         4         5         6
123456789012345678901234567890123456789012345678901234567890
The quick brown fox jumped over the lazy dogs
gsv jfrxp yildm ulc qfnkvw levi gsv ozab wlth

In the sample run, the code symbol for each letter is entered directly beneath that letter. Since a message is limited to 60 characters in length, the program displays a scale, and each letter of the plain text message is entered below its position number.

Exercises for Section 9.1

Self-Check

Suppose that S1 is 'ABCDE', S2 is 'FGHI', and S3 is declared as String(1..8) and has a value 'pqrstuvw'. Explain what will happen as a result of each of these assignments:
```
    S3 := S1 & S2;
    S3 := S1(2..4) & S2;
    S3(1..5) := S3(4..8);
```
Why is it that a space or a comma is not encoded in program Cryptogram?

Programming

Make changes to the cryptogram program to encode the blank character and the punctuation symbols ,, ;, :, ?, !, and ..
Write a procedure that stores the reverse of an input string parameter in its output parameter (for example, if the input string is 'happy ', the output string should be 'yppah '.) The actual length of the string being reversed should also be an input parameter.
Write a program that uses the procedure in Programming Exercise 2 to determine whether or not a string is a palindrome. (A palindrome is a string that reads the same way from left to right as it does from right to left--for instance, 'Level' is a palindrome.)