# String Manipulation

- Module Strings

## Module Strings

The module `Strings` provides facilities for manipulating character arrays as representations of strings. The procedures provided accept any character array type, but manipulate all as if their index types were whole numbers and zero-based.

The module also provides predicates that check whether an operation to assign, delete, insert, replace or append strings or characters will work without loss of information. These predicates check that parameters indexing the concrete representation of a string (i.e. the character array containing the string value) fall within its length, thereby allowing the programmer to maintain the string abstraction.

A general-purpose string type `String1` is provided for convenience when handling single characters by using a value constructor. An enumeration type `CompareResults` is provided for use when comparing string values:

    TYPE
      String1 = ARRAY [0..0] OF CHAR;

      CompareResults = (less, equal, greater);

NOTES:

- The procedures provided accept any character array type (i.e. with any index type) but because of the use of open array parameters the procedures manipulate all as if their index types were whole numbers and zero-based.
- The array type `String1` may be used as the array type identifier of an array constructor when constructing an array value from a value of the character type. The constructed array value may be used as actual parameter in calls of procedures having a formal open array value parameter, for example to assign, insert, replace, append, concatenate, or find a single character.
- Since function procedures cannot return open arrays, many of the operations that might more logically have been provided as function procedures have to be provided as proper procedures.
- Predicates with the prefix ``Can`' and the suffix ``All`' are provided to check the operation-completion condition of string operations (e.g. `CanInsertAll` checks the operation-completion condition for `Insert`). Failure to satisfy the operation-completion condition of a string handling procedure does not lead to an exception; i.e. the semantics of string operations are defined for all well-formed parameters.
- Value parameters are used where a string value is not changed by a procedure. This is not just a matter of programming clarity, but allows the parameterization of programs using constants.
- Because string constants cannot be assigned to, nor appended to, nor have characters replaced or inserted, the predicates that test the operation completion conditions of procedures use VAR-parameters for the string parameters.
- The International Standard has not adopted a change to Modula-2 (described in the fourth edition of Programming in Modula-2) of always requiring a string terminator for a string value.

- Length - Query string length
- CanAssignAll - Check whether Assign will succeed
- Assign - Assign string value
- CanExtractAll - Check whether Extract will succeed
- Extract - Extract substring
- CanDeleteAll - Check whether Delete will succeed
- Delete - Delete substring
- CanInsertAll - Check whether Insert will succeed
- Insert - Insert substring
- CanReplaceAll - Check whether Replace will succeed
- Replace - Replace substring
- CanAppendAll - Check whether Append will succeed
- Append - Append string
- CanConcatAll - Check whether Concat will succeed
- Concat - Concatenate strings
- Capitalize - Capitalize string
- Compare - Compare strings
- Equal - Compare strings
- FindNext - Search string forward
- FindPrev - Search string backward
- FindDiff - Find position of string difference

### Length - Query string length

    PROCEDURE Length (stringVal: ARRAY OF CHAR): CARDINAL;

Module `Strings`

The function procedure `Length` returns the length of the string value in `stringVal`. This is the same as the value of `LENGTH(stringVal)`.

### CanAssignAll - Check whether Assign will succeed

    PROCEDURE CanAssignAll (sourceLength: CARDINAL;
                            VAR destination: ARRAY OF CHAR
                           ): BOOLEAN;

Module `Strings`

The function procedure `CanAssignAll` returns the value of the Boolean expression `sourceLength <= HIGH(destination) + 1`

NOTES:

- `CanAssignAll` may be used to check whether complete assignment of a string value to a string variable will be possible using, for example, the procedure `Assign`.
- Since a string variable must have at least one element, single-character string assignment is always valid.

### Assign - Assign string value

    PROCEDURE Assign (source: ARRAY OF CHAR;
                      VAR destination: ARRAY OF CHAR);

Module `Strings`

The procedure `Assign` assigns the string value in `source` to `destination`. If the length of `source` exceeds the capacity of `destination`, the assigned value is truncated to the capacity of `destination`. If the length of `source` is less than the capacity of destination, a string terminator is appended to `source` when assignment takes place.

EXAMPLE - String assignment.

In these, and later, examples the following declarations are assumed:

    VAR
      small: ARRAY [0 .. 4] OF CHAR;
      large: ARRAY [0 .. 255] OF CHAR;
      alpha: ARRAY ['A' .. 'E'] OF CHAR;
      ch: CHAR;
      found, areDiff: BOOLEAN;
      pos: CARDINAL;

1. `ch := "X";`
   `Assign(String1{ch}, small)`
   results in `small` having value `"X"`
2. `Assign("pq", small)`
   results in `small` having value `"pq"`
3. `Assign("", small)`
   results in `small` having value ""
4. `Assign("Hello!", small)`
   results in `small` having value `"Hello"` without string terminator
5. the call
   `CanAssignAll(6, small)`
   returns the value `FALSE`
6. `Assign("Go", alpha)`
   results in `alpha` having value `"Go"`
7. `small := "Hello"; large := "";`
   `IF CanAssignAll(LENGTH(small), large)`
   `THEN`
   `Assign(small, large)`
   `END`
   results in `large` having value "Hello"

### CanExtractAll - Check whether Extract will succeed

    PROCEDURE CanExtractAll (sourceLength,
                             startPos,
                             numberToExtract: CARDINAL;
                             VAR destination: ARRAY OF CHAR
                            ): BOOLEAN;

Module `Strings`

The function procedure `CanExtractAll` returns the value of the Boolean expression
`(startPos + numberToExtract <= sourceLength) AND
(numberToExtract <= HIGH(destination) + 1)`

NOTE:

`CanExtractAll` may be used to check whether complete extraction of a substring from a string variable will be possible using, for example, the procedure `Extract`.

### Extract - Extract substring

    PROCEDURE Extract (source: ARRAY OF CHAR;
                       startPos,
                       numberToExtract: CARDINAL;
                       VAR destination: ARRAY OF CHAR);

Module `Strings`

The procedure `Extract` creates a new string value of at most `numberToExtract` characters extracted from `source`. Extraction starts at position `startPos` in `source`, and continues as long as there are characters left to extract from `source` and no more than `numberToExtract` characters have been extracted. If the length of the created string value exceeds the capacity of `destination`, the string value is truncated to the capacity of `destination`, and the truncated value is assigned to `destination`. If the length of the created string value is less than the capacity of `destination`, a string terminator is appended to the string value, and the resulting value is assigned to `destination`. An empty string value is extracted if `startPos` is greater than or equal to `LENGTH(source)`.

EXAMPLE - String extraction.

1. `large := "ABCDE"; small := "";`
   `IF CanExtractAll(LENGTH (large), 2, 3, small) THEN`
   `Extract(large, 2, 3, small)`
   `END`
   results in `small` having value `"CDE"`
2. `large := "ABCDE"; small := "";`
   `Extract(large, 2, 3, small)`
   results in `small` having value `"CDE"`

### CanDeleteAll - Check whether Delete will succeed

    PROCEDURE CanDeleteAll (stringLength,
                            startPos,
                            numberToDelete: CARDINAL
                           ): BOOLEAN;

Module `Strings`

The function procedure `CanDeleteAll` returns the value of the Boolean expression `startPos + numberToDelete <= stringLength`

NOTE:

`CanDeleteAll` may be used to check whether complete deletion of a substring value from a string variable will be possible using, for example, the procedure `Delete`.

### Delete - Delete substring

    PROCEDURE Delete (VAR stringVar: ARRAY OF CHAR;
                      startPos,
                      numberToDelete: CARDINAL);

Module `Strings`

The procedure `Delete` creates a new string value by deleting at most `numberToDelete` characters from `stringVar`. Deletion starts at position `startPos` in `stringVar` and continues as long as there are characters left to delete in `stringVar` and no more than `numberToDelete` characters have been deleted. If any characters are deleted, a string terminator is appended to the created string value, and the resulting value is assigned to `stringVar`. The string value in `stringVar` is not altered if `startPos` is greater than or equal to `LENGTH(stringVar)`.

EXAMPLE - String deletion.

1. `small := "ABCDE";`
   `IF CanDeleteAll(LENGTH(small), 2, 2) THEN`
   `Delete(small, 2, 2)`
   `END`
   results in `small` having value `"ABE"`
2. after the assignment
   `small := "ABC";`
   the call
   `CanDeleteAll(3, 2, 2)`
   returns the value `FALSE`
3. `small := "ABC";`
   `Delete(small, 2, 2)`
   results in `small` having value `"AB"`

### CanInsertAll - Check whether Insert will succeed

    PROCEDURE CanInsertAll (sourceLength, startPos: CARDINAL;
                            VAR destination: ARRAY OF CHAR
                           ): BOOLEAN;

Module `Strings`

The function procedure `CanInsertAll` returns the value of the Boolean expression
`(startPos <= LENGTH(destination)) AND
(sourceLength + LENGTH(destination) <= HIGH(destination) + 1)`

NOTE:

`CanInsertAll` may be used to check whether complete insertion of a string value into a string variable will be possible using, for example, the procedure `Insert`.

### Insert - Insert substring

    PROCEDURE Insert (source: ARRAY OF CHAR;
                      startPos: CARDINAL;
                      VAR destination: ARRAY OF CHAR);

Module `Strings`

The procedure `Insert` creates a new string value by inserting the substring `source` into `destination`. The string in `destination` is first splitted at the position given by `startPos`; the created string value is the concatenation of the first part of `destination`, the substring `source`, and the second part of `destination`. If the length of the created string value exceeds the capacity of `destination`, the string value is truncated to the capacity of `destination`, and the truncated value is assigned to `destination`. If the length of the created string value is less than the capacity of `destination`, a string terminator is appended to the string value, and the resulting value is assigned to `destination`. The string value in `destination` is not altered if `startPos` is greater than or equal to `LENGTH(destination)`.

EXAMPLE - String insertion.

1. after the assignment
   `small := "ABCD";`
   the call
   `CanInsertAll(LENGTH("XYZ"), 2, small)`
   returns the value `FALSE`
2. `small := "ABCD";`
   `Insert("XYZ", 2, small)`
   results in `small` having value `"ABXYZ"` without terminator
3. `large := "ABC";`
   `IF CanInsertAll(3, 2, large) THEN`
   `Insert("XYZ", 2, large)`
   `END`
   results in `large` having value `"ABXYZC"`
4. `large := "ABCD"; ch := "X";`
   `Insert(String1{ch}, 2, large)`
   results in `large` having value `"ABXCD"`

### CanReplaceAll - Check whether Replace will succeed

    PROCEDURE CanReplaceAll (sourceLength, startPos: CARDINAL;
                             VAR destination: ARRAY OF CHAR
                            ): BOOLEAN;

The function procedure `CanReplaceAll` returns is the value of the Boolean expression `sourceLength + startPos <= LENGTH(destination)`

NOTES:

- `CanReplaceAll` may be used to check whether complete replacement of a substring value within a string variable will be possible using, for example, the procedure `Replace`.
- The preservation of the string abstraction is taken as the goal of the string module. This means that the operation completion condition of `CanReplaceAll` only tests whether the proposed replacement is valid within the given string length; the procedure `Replace` always preserves the length of its `destination` string.

### Replace - Replace substring

    PROCEDURE Replace (source: ARRAY OF CHAR;
                       startPos: CARDINAL;
                       VAR destination: ARRAY OF CHAR);

The procedure `Replace` modifies the string value from `destination` by overwriting characters in `destination` with characters extracted from the string value in `source`. Overwriting begins at the position given by `startPos` and continues as long as there are characters left to overwrite in `destination` and characters left to extract from `source`. The string value in `destination` is not altered if `startPos` is greater than or equal to `LENGTH(destination)`.

NOTE:

The length of the string value in `destination` is always preserved by `Replace`.

EXAMPLE - String replacement.

1. after the assignment
   `small := "ABC"`
   the call
   `CanReplaceAll(LENGTH("XY"), 2, small)`
   returns the value `FALSE`
2. `small := "ABC";`
   `Replace("XY", 2, small)`
   results in `small[0]` having value `"ABX"`
3. `large := "ABCDEF";`
   `IF CanReplaceAll(3, 2, large)`
   `THEN`
   `Replace("XYZ", 2, large)`
   `END`
   results in `large` having value `"ABXYZF"`

### CanAppendAll - Check whether Append will succeed

    PROCEDURE CanAppendAll (sourceLength: CARDINAL;
                            VAR destination: ARRAY OF CHAR
                           ): BOOLEAN;

The function procedure `CanAppendAll` returns the value of the Boolean expression
`LENGTH(destination) + sourceLength <= HIGH(destination) + 1`

NOTE:

`CanAppendAll` may be used to check whether it will be possible to append a string value to another string value held within a string variable using, for example, the procedure `Append`.

### Append - Append string

    PROCEDURE Append (source: ARRAY OF CHAR;
                      VAR destination: ARRAY OF CHAR);

The procedure `Append` creates a new string value by appending the string value in `source` onto `destination`. If the length of the created string value exceeds the capacity of `destination`, the string value is truncated to the capacity of `destination`, and the truncated value is assigned to `destination`. If the length of the created string value is less than the capacity of `destination`, a string terminator is appended to the string value, and the resulting value is assigned to `destination`.

EXAMPLE - Appending to strings.

1. after the assignment
   `small := "pqr"`
   the call
   `CanAppendAll(LENGTH("XYZ"), small)`
   returns the value `FALSE`
2. `small := "pqr";`
   `Append("XYZ", small)`
   results in `small` having value `"pqrXY"` without terminator
3. `small := "pqr";`
   `ch := "s";`
   `Append(String1{ch}, small)`
   results in `small` having value `"pqrs"`

### CanConcatAll - Check whether Concat will succeed

    PROCEDURE CanConcatAll (source1Length, source2Length: CARDINAL;
                            VAR destination: ARRAY OF CHAR
                           ): BOOLEAN;

The function procedure `CanConcatAll` returns the value of the Boolean expression
`source1Length + source2Length <= HIGH(destination) + 1`

NOTE:

`CanConcatAll` may be used to check whether complete concatenation of two string values will be possible within the capacity of a specified string variable using, for example, the procedure `Concat`.

### Concat - Concatenate strings

    PROCEDURE Concat (source1, source2: ARRAY OF CHAR;
                      VAR destination: ARRAY OF CHAR);

The procedure `Concat` creates a new string value by appending the substring value `source2` onto `source1`. If the length of the created string value exceeds the capacity of `destination`, the string value is truncated to the capacity of `destination`, and the truncated value is assigned to `destination`. If the length of the created string value is less than the capacity of `destination`, a string terminator is appended to the string value, and the resulting value is assigned to `destination`.

EXAMPLE - String concatenation.

1. after the assignment
   `small := "pqr"`
   the call
   `CanConcatAll(4, LENGTH(small), small)`
   returns the value `FALSE`
2. `small := "pqr";`
   `Concat("WXYZ", small, small)`
   results in `small` having value `"WXYZp"` without terminator
3. `small := "jk"; large := "";`
   `ch := "s";`
   `Concat(String1{ch}, small, large)`
   results in `large` having value `"skj"`

### Capitalize - Capitalize string

    PROCEDURE Capitalize (VAR stringVar: ARRAY OF CHAR);

The procedure `Capitalize` applies the standard function `CAP` to each character of the string value in `stringVar`.

NOTE:

`Capitalize` may be used to achieve case-insensitive use of the procedures `Compare`, `FindNext`, `FindPrev` and `FindDiff`.

EXAMPLE - String capitalization.

The following example assumes a capitalization mapping which maps p to P, q to Q and r to R.

1. `small := "pqr";`
   `Capitalize(small)`
   results in `small` having value `"PQR"`

### Compare - Compare strings

    PROCEDURE Compare (stringVal1, stringVal2: ARRAY OF CHAR
                      ): CompareResults;

The function procedure `Compare` returns a value of the enumeration type `CompareResults` depending on the lexical ordering of the type `CHAR`. The value returned is `less`, `equal` or `greater` according as the string value in `stringVal1` is lexically less than, equal to, or greater than the string value in `stringVal2`.

NOTES:

- The result of this function is dependent upon the full collating sequence of character values. This sequence is implementation-defined, although it must have certain properties.
- In general, the result of this function is case-sensitive.

EXAMPLE - String comparison.

1. `Compare("", "")` returns `equal`
2. `Compare("", "abc")` returns `less`
3. `Compare("abc", "")` returns `greater`
4. `Compare("pqr", "pqr")` returns `equal`
5. `Compare("pqr", "pqrstuv")` returns `less`
6. `Compare("pqrstuv", "pqr")` returns `greater`
7. `Compare("abc", "pqr")` returns `less`
8. `Compare("pqr", "abc")` returns `greater`
9. `Compare("abcdef ", "p")` returns `less`
10. `Compare("p", "abcdef ")` returns `greater`

### Equal - Compare strings

    PROCEDURE Equal (stringVal1, stringVal2: ARRAY OF CHAR): BOOLEAN;

The function procedure `Equal` returns the value of the Boolean expression
`Strings.Compare(stringVal1, stringVal2) = Strings.equal`

### FindNext - Search string forward

    PROCEDURE FindNext (pattern, stringToSearch: ARRAY OF CHAR;
                        startPos: CARDINAL;
                        VAR patternFound: BOOLEAN;
                        VAR posOfPattern: CARDINAL);

The procedure `FindNext` searches forwards for the next occurrence of `pattern` in `stringToSearch`, starting the search in `stringToSearch` at position `startPos`. If `pattern` is found, the value `TRUE` is assigned to `patternFound`, and `posOfPattern` contains the starting position of `pattern` in `stringToSearch`; `posOfPattern` is in the range `[startPos..LENGTH(stringToSearch)-1]`. Otherwise the value `FALSE` is assigned to `patternFound` and `posOfPattern` is unchanged.

NOTES:

- The `pattern` might be found at the given value of `startPos`.
- If `startPos > LENGTH(stringToSearch) - LENGTH(pattern)` then `patternFound` is returned as `FALSE`.

EXAMPLE - Forwards string search.

1. `large := "Hello hello hello";`
   `FindNext("ll", large, 0, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `2`
2. `large := "Hello hello hello";`
   `FindNext("ll", large, 0, found, pos);`
   `FindNext("ll", large, pos+1, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `8`
3. `large := "abcdefghijklmnopqrstuvwxyz";`
   `ch := "x";`
   `FindNext(String1fchg, large, 0, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `23`
4. `large := "abcdefghijklmnopqrstuvwxyz";`
   `ch := "x";`
   `FindNext(String1fchg, large, 26, found, pos)`
   results in:
   `found` having value `FALSE`
   `pos` remains unchanged

### FindPrev - Search string backward

    PROCEDURE FindPrev (pattern, stringToSearch: ARRAY OF CHAR;
                        startPos: CARDINAL;
                        VAR patternFound: BOOLEAN;
                        VAR posOfPattern: CARDINAL);

The procedure `FindPrev` looks backwards for an occurrence of `pattern` in the string value in `stringToSearch`, starting the search in `stringToSearch` at position `startPos`. If `pattern` is found, the value `TRUE` is assigned to `patternFound`, and `posOfPattern` contains the starting position of `pattern` in `stringToSearch`; `posOfPattern` is in the range `[0..startPos]`. Otherwise the value `FALSE` is assigned to `patternFound` and `posOfPattern` is unchanged.

NOTES:

- The `pattern` might be found at the given value of `startPos`.
- If `startPos > LENGTH(stringToSearch)-LENGTH(pattern)` the whole string value is searched.

EXAMPLE - Backwards string search.

1. `large := "aabbbcccc";`
   `FindPrev("cc", large, 200, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `7`
2. `large := "aabbbcccc";`
   `FindPrev("cc", large, 200, found, pos);`
   `FindPrev("cc", large, pos-1, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `6`
3. `large := "Maybe this makes sense";`
   `FindPrev("se", large, 200, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `20`
4. `large := "Maybe this makes sense";`
   `FindPrev("se", large, 20, found, pos);`
   `FindPrev("se", large, pos-1, found, pos)`
   results in:
   `found` having value `TRUE`
   `pos` having value `17`

### FindDiff - Find position of string difference

    PROCEDURE FindDiff (stringVal1, stringVal2: ARRAY OF CHAR;
                        VAR differenceFound: BOOLEAN;
                        VAR posOfDifference: CARDINAL);

The procedure `FindDiff` compares the string values in `stringVal1` and `stringVal2`. The value `FALSE` is assigned to `differenceFound` if the string values are equal and `TRUE` otherwise. If `differenceFound` is `TRUE`, the position of the first difference between the string values is assigned to `posOfDifference`; otherwise `posOfDifference` is unchanged.

##### Examples

- Finding string differences.

1. `FindDiff("", "", areDiff, pos)` results in:
   `areDiff` having value `FALSE`
   `pos` being unchanged
2. `FindDiff("abc", "", areDiff, pos)` results in:
   `areDiff` having value `TRUE`
   `pos` having value `0`
3. `FindDiff("", "abc", areDiff, pos)` results in:
   `areDiff` having value `TRUE` `pos` having value `0`
4. `FindDiff("pqr", "pqt", areDiff, pos)` results in:
   `areDiff` having value `TRUE`
   `pos` having value `2`
5. `FindDiff("pqr", "pqrstuv", areDiff, pos)` results in:
   `areDiff` having value `TRUE`
   `pos` having value `3`
6. `FindDiff("pqrstuv", "pqr", areDiff, pos)` results in:
   `areDiff` having value `TRUE`
   `pos` having value `3`