| 1 |
HI10: This example gives examples of heavily and lightly documented pieces |
| 2 |
of code. |
| 3 |
|
| 4 |
@O@<hi10.out@>==@{ |
| 5 |
@<Set p to the length of the longest plateau in sorted array b[1..N]@> |
| 6 |
|
| 7 |
@<Function comp@> |
| 8 |
@} |
| 9 |
|
| 10 |
@A@<Calculation of the longest plateau in array b@> |
| 11 |
|
| 12 |
This section contains a solution to a problem outlined in section 16.3 of |
| 13 |
the book @/The Science of Programming@/ by David Gries[Gries81]. |
| 14 |
|
| 15 |
@B Given a sorted array @{b[1..N]@} of integers, we wish to determine the |
| 16 |
@/length@/ of the longest run of identically valued elements in the array. |
| 17 |
This problem is defined by the following precondition and postcondition. |
| 18 |
|
| 19 |
@$@<Precondition@>==@{/* Pre: sorted(b). */@} |
| 20 |
@$@<Postcondition@>==@{@- |
| 21 |
/* Post: sorted(b) and p is the length of the longest run in b[1..N]. */@} |
| 22 |
|
| 23 |
@B We approach a solution to the problem by deciding to try the approach of |
| 24 |
scanning through the array one element at a time maintaining a useful |
| 25 |
invariant through each iteration. A loop variable |
| 26 |
array index @{i@} is created for this purpose. The bound function is |
| 27 |
@{N-i@}. Here is the invariant. |
| 28 |
|
| 29 |
@$@<Invariant@>==@{@- |
| 30 |
/* Invariant: sorted(b) and 1<=i<=N and */ |
| 31 |
/* p is len of longest run in b[1..i]. */@} |
| 32 |
|
| 33 |
@B Establishing the invariant above in the initial, degenerate case is easy. |
| 34 |
|
| 35 |
@$@<Establish the plateau loop invariant initially@>==@{i=1; p=1;@} |
| 36 |
|
| 37 |
@B At this stage, we have the following loop structure. Note that when both |
| 38 |
the invariant and @{i == N@} are true, the postcondition holds and the loop |
| 39 |
can terminate. |
| 40 |
|
| 41 |
@$@<Set p to the length of the longest plateau in sorted array b[1..N]@>==@{@- |
| 42 |
@<Precondition@> |
| 43 |
@<Establish the plateau loop invariant initially@> |
| 44 |
while (i != N) |
| 45 |
{ |
| 46 |
@<Invariant@> |
| 47 |
@<Loop body@> |
| 48 |
} |
| 49 |
@<Postcondition@> |
| 50 |
@} |
| 51 |
|
| 52 |
@B Now there remains only the loop body whose sole task is to increase @{i@} |
| 53 |
(and so decrease the value of the bound function) while maintaining the |
| 54 |
invariant. If @{p@} is the length of the longest run |
| 55 |
seen so far (i.e. in b[1..i]), then, because the array is sorted, |
| 56 |
the extension of our array range to |
| 57 |
@{b[1..i+1]@} can only result in an increase in @{p@} if the new element |
| 58 |
terminates a run of length @{p+1@}. The increase can be at most 1. Because |
| 59 |
the array is sorted, we need |
| 60 |
only compare the endpoints of this possible run to see if it exists. This |
| 61 |
is performed as shown below. |
| 62 |
|
| 63 |
@$@<Loop body@>==@{i++; if (b[i] != b[i-p]) p++;@} |
| 64 |
|
| 65 |
|
| 66 |
|
| 67 |
|
| 68 |
|
| 69 |
@A The following function compares two C~strings and returns TRUE iff they |
| 70 |
are identical. |
| 71 |
|
| 72 |
@$@<Function comp@>==@{@- |
| 73 |
bool comp(p,q) |
| 74 |
char *p,*q; |
| 75 |
{ |
| 76 |
while (TRUE) |
| 77 |
{ |
| 78 |
if (*p != *q ) return FALSE; |
| 79 |
if (*p == '\0') return TRUE; |
| 80 |
p++; q++; |
| 81 |
} |
| 82 |
} |
| 83 |
@} |