Debian Codegraph @

tests/hi10.fw

raw
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 @}