Artifact
f675ac96a0ab25f8f25fe7ddb931494b42105f91:
Attachment "2017_09_xx_stack_by_Tucker_Taft.psl" to
wiki page [
Local Copies of ParaSail Deliverables]
added by
martin_vahi on
2017-09-29 02:21:18.
0000: 69 6e 74 65 72 66 61 63 65 20 53 74 61 63 6b 0a interface Stack.
0010: 20 20 3c 43 6f 6d 70 6f 6e 65 6e 74 20 69 73 20 <Component is
0020: 41 73 73 69 67 6e 61 62 6c 65 3c 3e 3b 20 0a 20 Assignable<>; .
0030: 20 20 53 69 7a 65 5f 54 79 70 65 20 69 73 20 49 Size_Type is I
0040: 6e 74 65 67 65 72 3c 3e 3e 20 69 73 0a 20 20 20 nteger<>> is.
0050: 20 0a 20 20 20 20 66 75 6e 63 20 4d 61 78 5f 53 . func Max_S
0060: 74 61 63 6b 5f 53 69 7a 65 28 53 20 3a 20 53 74 tack_Size(S : St
0070: 61 63 6b 29 20 2d 3e 20 53 69 7a 65 5f 54 79 70 ack) -> Size_Typ
0080: 65 0a 20 20 20 20 20 20 7b 4d 61 78 5f 53 74 61 e. {Max_Sta
0090: 63 6b 5f 53 69 7a 65 20 3e 20 30 7d 3b 0a 20 20 ck_Size > 0};.
00a0: 20 20 0a 20 20 20 20 66 75 6e 63 20 43 6f 75 6e . func Coun
00b0: 74 28 53 20 3a 20 53 74 61 63 6b 29 20 2d 3e 20 t(S : Stack) ->
00c0: 53 69 7a 65 5f 54 79 70 65 20 0a 20 20 20 20 20 Size_Type .
00d0: 20 7b 43 6f 75 6e 74 20 3c 3d 20 4d 61 78 5f 53 {Count <= Max_S
00e0: 74 61 63 6b 5f 53 69 7a 65 28 53 29 7d 3b 0a 20 tack_Size(S)};.
00f0: 20 20 20 0a 20 20 20 20 66 75 6e 63 20 43 72 65 . func Cre
0100: 61 74 65 28 4d 61 78 20 3a 20 53 69 7a 65 5f 54 ate(Max : Size_T
0110: 79 70 65 20 7b 4d 61 78 20 3e 20 30 7d 29 20 2d ype {Max > 0}) -
0120: 3e 20 53 74 61 63 6b 20 0a 20 20 20 20 20 20 7b > Stack . {
0130: 4d 61 78 5f 53 74 61 63 6b 5f 53 69 7a 65 28 43 Max_Stack_Size(C
0140: 72 65 61 74 65 29 20 3d 3d 20 4d 61 78 3b 20 43 reate) == Max; C
0150: 6f 75 6e 74 28 43 72 65 61 74 65 29 20 3d 3d 20 ount(Create) ==
0160: 30 7d 3b 0a 20 20 20 20 0a 20 20 20 20 66 75 6e 0};. . fun
0170: 63 20 49 73 5f 45 6d 70 74 79 28 53 20 3a 20 53 c Is_Empty(S : S
0180: 74 61 63 6b 29 20 2d 3e 20 42 6f 6f 6c 65 61 6e tack) -> Boolean
0190: 0a 20 20 20 20 20 20 7b 49 73 5f 45 6d 70 74 79 . {Is_Empty
01a0: 20 3d 3d 20 28 43 6f 75 6e 74 28 53 29 20 3d 3d == (Count(S) ==
01b0: 20 30 29 7d 3b 0a 20 20 20 20 0a 20 20 20 20 66 0)};. . f
01c0: 75 6e 63 20 49 73 5f 46 75 6c 6c 28 53 20 3a 20 unc Is_Full(S :
01d0: 53 74 61 63 6b 29 20 2d 3e 20 42 6f 6f 6c 65 61 Stack) -> Boolea
01e0: 6e 0a 20 20 20 20 20 20 7b 49 73 5f 46 75 6c 6c n. {Is_Full
01f0: 20 3d 3d 20 28 43 6f 75 6e 74 28 53 29 20 3d 3d == (Count(S) ==
0200: 20 4d 61 78 5f 53 74 61 63 6b 5f 53 69 7a 65 28 Max_Stack_Size(
0210: 53 29 29 7d 3b 0a 20 20 20 20 20 20 0a 20 20 20 S))};. .
0220: 20 66 75 6e 63 20 50 75 73 68 0a 20 20 20 20 20 func Push.
0230: 20 28 76 61 72 20 53 20 3a 20 53 74 61 63 6b 20 (var S : Stack
0240: 7b 6e 6f 74 20 49 73 5f 46 75 6c 6c 28 53 29 7d {not Is_Full(S)}
0250: 3b 20 0a 20 20 20 20 20 20 20 58 20 3a 20 43 6f ; . X : Co
0260: 6d 70 6f 6e 65 6e 74 29 0a 20 20 20 20 20 20 7b mponent). {
0270: 43 6f 75 6e 74 28 53 27 29 20 3d 3d 20 43 6f 75 Count(S') == Cou
0280: 6e 74 28 53 29 20 2b 20 31 3b 20 6e 6f 74 20 49 nt(S) + 1; not I
0290: 73 5f 45 6d 70 74 79 28 53 27 29 7d 3b 0a 20 20 s_Empty(S')};.
02a0: 20 20 20 20 0a 20 20 20 20 66 75 6e 63 20 54 6f . func To
02b0: 70 28 72 65 66 20 53 20 3a 20 53 74 61 63 6b 29 p(ref S : Stack)
02c0: 20 7b 6e 6f 74 20 49 73 5f 45 6d 70 74 79 28 53 {not Is_Empty(S
02d0: 29 7d 20 0a 20 20 20 20 20 20 2d 3e 20 72 65 66 )} . -> ref
02e0: 20 43 6f 6d 70 6f 6e 65 6e 74 3b 0a 20 20 20 20 Component;.
02f0: 0a 20 20 20 20 66 75 6e 63 20 50 6f 70 28 76 61 . func Pop(va
0300: 72 20 53 20 3a 20 53 74 61 63 6b 20 7b 6e 6f 74 r S : Stack {not
0310: 20 49 73 5f 45 6d 70 74 79 28 53 29 7d 29 0a 20 Is_Empty(S)}).
0320: 20 20 20 20 20 2d 3e 20 28 43 6f 6d 70 6f 6e 65 -> (Compone
0330: 6e 74 20 7b 43 6f 75 6e 74 28 53 27 29 20 3d 3d nt {Count(S') ==
0340: 20 43 6f 75 6e 74 28 53 29 20 2d 20 31 3b 20 6e Count(S) - 1; n
0350: 6f 74 20 49 73 5f 46 75 6c 6c 28 53 27 29 7d 29 ot Is_Full(S')})
0360: 3b 0a 20 20 20 20 0a 20 20 20 20 20 20 0a 65 6e ;. . .en
0370: 64 20 69 6e 74 65 72 66 61 63 65 20 53 74 61 63 d interface Stac
0380: 6b 3b 0a 0a 0a 63 6c 61 73 73 20 53 74 61 63 6b k;...class Stack
0390: 20 3c 43 6f 6d 70 6f 6e 65 6e 74 20 69 73 20 41 <Component is A
03a0: 73 73 69 67 6e 61 62 6c 65 3c 3e 3b 20 53 69 7a ssignable<>; Siz
03b0: 65 5f 54 79 70 65 20 69 73 20 49 6e 74 65 67 65 e_Type is Intege
03c0: 72 3c 3e 3e 20 69 73 0a 20 20 20 20 63 6f 6e 73 r<>> is. cons
03d0: 74 20 4d 61 78 5f 4c 65 6e 20 3a 20 53 69 7a 65 t Max_Len : Size
03e0: 5f 54 79 70 65 3b 0a 20 20 20 20 76 61 72 20 43 _Type;. var C
03f0: 75 72 5f 4c 65 6e 20 3a 20 53 69 7a 65 5f 54 79 ur_Len : Size_Ty
0400: 70 65 20 7b 43 75 72 5f 4c 65 6e 20 69 6e 20 30 pe {Cur_Len in 0
0410: 2e 2e 4d 61 78 5f 4c 65 6e 7d 3b 0a 20 20 20 20 ..Max_Len};.
0420: 74 79 70 65 20 49 6e 64 65 78 5f 54 79 70 65 20 type Index_Type
0430: 69 73 20 53 69 7a 65 5f 54 79 70 65 20 7b 49 6e is Size_Type {In
0440: 64 65 78 5f 54 79 70 65 20 69 6e 20 31 2e 2e 4d dex_Type in 1..M
0450: 61 78 5f 4c 65 6e 7d 3b 0a 20 20 20 20 76 61 72 ax_Len};. var
0460: 20 44 61 74 61 20 3a 20 41 72 72 61 79 3c 6f 70 Data : Array<op
0470: 74 69 6f 6e 61 6c 20 43 6f 6d 70 6f 6e 65 6e 74 tional Component
0480: 2c 20 49 6e 64 65 78 65 64 5f 42 79 20 3d 3e 20 , Indexed_By =>
0490: 49 6e 64 65 78 5f 54 79 70 65 3e 3b 20 20 20 20 Index_Type>;
04a0: 0a 20 20 65 78 70 6f 72 74 73 0a 20 20 20 20 7b . exports. {
04b0: 66 6f 72 20 61 6c 6c 20 49 20 69 6e 20 31 2e 2e for all I in 1..
04c0: 43 75 72 5f 4c 65 6e 20 3d 3e 20 44 61 74 61 5b Cur_Len => Data[
04d0: 49 5d 20 6e 6f 74 20 6e 75 6c 6c 7d 20 20 20 2f I] not null} /
04e0: 2f 20 69 6e 76 61 72 69 61 6e 74 20 66 6f 72 20 / invariant for
04f0: 54 6f 70 28 29 0a 0a 20 20 20 20 66 75 6e 63 20 Top().. func
0500: 4d 61 78 5f 53 74 61 63 6b 5f 53 69 7a 65 28 53 Max_Stack_Size(S
0510: 20 3a 20 53 74 61 63 6b 29 20 2d 3e 20 53 69 7a : Stack) -> Siz
0520: 65 5f 54 79 70 65 0a 20 20 20 20 20 20 7b 4d 61 e_Type. {Ma
0530: 78 5f 53 74 61 63 6b 5f 53 69 7a 65 20 3e 20 30 x_Stack_Size > 0
0540: 7d 20 69 73 0a 09 72 65 74 75 72 6e 20 53 2e 4d } is..return S.M
0550: 61 78 5f 4c 65 6e 3b 0a 20 20 20 20 65 6e 64 20 ax_Len;. end
0560: 66 75 6e 63 20 4d 61 78 5f 53 74 61 63 6b 5f 53 func Max_Stack_S
0570: 69 7a 65 3b 0a 20 20 20 20 0a 20 20 20 20 66 75 ize;. . fu
0580: 6e 63 20 49 73 5f 45 6d 70 74 79 28 53 20 3a 20 nc Is_Empty(S :
0590: 53 74 61 63 6b 29 20 2d 3e 20 42 6f 6f 6c 65 61 Stack) -> Boolea
05a0: 6e 0a 20 20 20 20 20 20 7b 49 73 5f 45 6d 70 74 n. {Is_Empt
05b0: 79 20 3d 3d 20 28 43 6f 75 6e 74 28 53 29 20 3d y == (Count(S) =
05c0: 3d 20 30 29 7d 20 69 73 0a 09 72 65 74 75 72 6e = 0)} is..return
05d0: 20 53 2e 43 75 72 5f 4c 65 6e 20 3d 3d 20 30 3b S.Cur_Len == 0;
05e0: 0a 20 20 20 20 65 6e 64 20 66 75 6e 63 20 49 73 . end func Is
05f0: 5f 45 6d 70 74 79 3b 0a 20 20 20 20 0a 20 20 20 _Empty;. .
0600: 20 66 75 6e 63 20 49 73 5f 46 75 6c 6c 28 53 20 func Is_Full(S
0610: 3a 20 53 74 61 63 6b 29 20 2d 3e 20 42 6f 6f 6c : Stack) -> Bool
0620: 65 61 6e 0a 20 20 20 20 20 20 7b 49 73 5f 46 75 ean. {Is_Fu
0630: 6c 6c 20 3d 3d 20 28 43 6f 75 6e 74 28 53 29 20 ll == (Count(S)
0640: 3d 3d 20 4d 61 78 5f 53 74 61 63 6b 5f 53 69 7a == Max_Stack_Siz
0650: 65 28 53 29 29 7d 20 69 73 0a 09 72 65 74 75 72 e(S))} is..retur
0660: 6e 20 53 2e 43 75 72 5f 4c 65 6e 20 3d 3d 20 53 n S.Cur_Len == S
0670: 2e 4d 61 78 5f 4c 65 6e 3b 0a 20 20 20 20 65 6e .Max_Len;. en
0680: 64 20 66 75 6e 63 20 49 73 5f 46 75 6c 6c 3b 0a d func Is_Full;.
0690: 20 20 20 20 20 20 0a 20 20 20 20 66 75 6e 63 20 . func
06a0: 43 6f 75 6e 74 28 53 20 3a 20 53 74 61 63 6b 29 Count(S : Stack)
06b0: 20 2d 3e 20 53 69 7a 65 5f 54 79 70 65 20 69 73 -> Size_Type is
06c0: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 53 2e . return S.
06d0: 43 75 72 5f 4c 65 6e 3b 0a 20 20 20 20 65 6e 64 Cur_Len;. end
06e0: 20 66 75 6e 63 20 43 6f 75 6e 74 3b 20 0a 0a 20 func Count; ..
06f0: 20 20 20 66 75 6e 63 20 43 72 65 61 74 65 28 4d func Create(M
0700: 61 78 20 3a 20 53 69 7a 65 5f 54 79 70 65 20 7b ax : Size_Type {
0710: 4d 61 78 20 3e 20 30 7d 29 20 2d 3e 20 53 74 61 Max > 0}) -> Sta
0720: 63 6b 0a 20 20 20 20 20 20 7b 4d 61 78 5f 53 74 ck. {Max_St
0730: 61 63 6b 5f 53 69 7a 65 28 43 72 65 61 74 65 29 ack_Size(Create)
0740: 20 3d 3d 20 4d 61 78 20 61 6e 64 20 43 6f 75 6e == Max and Coun
0750: 74 28 43 72 65 61 74 65 29 20 3d 3d 20 30 7d 20 t(Create) == 0}
0760: 69 73 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 is. return
0770: 28 4d 61 78 5f 4c 65 6e 20 3d 3e 20 4d 61 78 2c (Max_Len => Max,
0780: 20 43 75 72 5f 4c 65 6e 20 3d 3e 20 30 2c 20 44 Cur_Len => 0, D
0790: 61 74 61 20 3d 3e 20 43 72 65 61 74 65 28 31 2e ata => Create(1.
07a0: 2e 4d 61 78 2c 20 6e 75 6c 6c 29 29 3b 0a 20 20 .Max, null));.
07b0: 20 20 65 6e 64 20 66 75 6e 63 20 43 72 65 61 74 end func Creat
07c0: 65 3b 0a 0a 20 20 20 20 66 75 6e 63 20 50 75 73 e;.. func Pus
07d0: 68 28 76 61 72 20 53 20 3a 20 53 74 61 63 6b 20 h(var S : Stack
07e0: 7b 6e 6f 74 20 49 73 5f 46 75 6c 6c 28 53 29 7d {not Is_Full(S)}
07f0: 3b 20 58 20 3a 20 43 6f 6d 70 6f 6e 65 6e 74 29 ; X : Component)
0800: 0a 20 20 20 20 20 20 7b 43 6f 75 6e 74 28 53 27 . {Count(S'
0810: 29 20 3d 3d 20 43 6f 75 6e 74 28 53 29 20 2b 20 ) == Count(S) +
0820: 31 7d 20 69 73 0a 20 20 20 20 20 20 53 2e 43 75 1} is. S.Cu
0830: 72 5f 4c 65 6e 20 2b 3d 20 31 3b 20 20 20 20 20 r_Len += 1;
0840: 20 2f 2f 20 72 65 71 75 69 72 65 73 20 6e 6f 74 // requires not
0850: 20 49 73 5f 46 75 6c 6c 28 53 29 20 70 72 65 63 Is_Full(S) prec
0860: 6f 6e 64 69 74 69 6f 6e 0a 20 20 20 20 20 20 53 ondition. S
0870: 2e 44 61 74 61 5b 53 2e 43 75 72 5f 4c 65 6e 5d .Data[S.Cur_Len]
0880: 20 3a 3d 20 58 3b 20 20 20 2f 2f 20 70 72 65 73 := X; // pres
0890: 65 72 76 65 73 20 69 6e 76 61 72 69 61 6e 74 20 erves invariant
08a0: 28 73 65 65 20 61 62 6f 76 65 29 0a 20 20 20 20 (see above).
08b0: 65 6e 64 20 66 75 6e 63 20 50 75 73 68 3b 0a 20 end func Push;.
08c0: 20 20 20 20 20 0a 20 20 20 20 66 75 6e 63 20 54 . func T
08d0: 6f 70 28 72 65 66 20 53 20 3a 20 53 74 61 63 6b op(ref S : Stack
08e0: 20 7b 6e 6f 74 20 49 73 5f 45 6d 70 74 79 28 53 {not Is_Empty(S
08f0: 29 7d 29 20 2d 3e 20 72 65 66 20 43 6f 6d 70 6f )}) -> ref Compo
0900: 6e 65 6e 74 20 69 73 0a 20 20 20 20 20 20 72 65 nent is. re
0910: 74 75 72 6e 20 53 2e 44 61 74 61 5b 53 2e 43 75 turn S.Data[S.Cu
0920: 72 5f 4c 65 6e 5d 3b 20 2f 2f 20 72 65 71 75 69 r_Len]; // requi
0930: 72 65 73 20 6e 6f 74 20 49 73 5f 45 6d 70 74 79 res not Is_Empty
0940: 20 61 6e 64 20 69 6e 76 61 72 69 61 6e 74 20 28 and invariant (
0950: 61 62 6f 76 65 29 0a 20 20 20 20 65 6e 64 20 66 above). end f
0960: 75 6e 63 20 54 6f 70 3b 20 20 20 20 20 20 20 20 unc Top;
0970: 20 20 20 20 20 20 20 20 0a 0a 20 20 20 20 66 75 .. fu
0980: 6e 63 20 50 6f 70 28 76 61 72 20 53 20 3a 20 53 nc Pop(var S : S
0990: 74 61 63 6b 20 7b 6e 6f 74 20 49 73 5f 45 6d 70 tack {not Is_Emp
09a0: 74 79 28 53 29 7d 29 20 2d 3e 20 52 65 73 75 6c ty(S)}) -> Resul
09b0: 74 20 3a 20 43 6f 6d 70 6f 6e 65 6e 74 20 0a 20 t : Component .
09c0: 20 20 20 20 20 7b 43 6f 75 6e 74 28 53 27 29 20 {Count(S')
09d0: 3d 3d 20 43 6f 75 6e 74 28 53 29 20 2d 20 31 3b == Count(S) - 1;
09e0: 20 6e 6f 74 20 49 73 5f 46 75 6c 6c 28 53 27 29 not Is_Full(S')
09f0: 7d 20 69 73 0a 20 20 20 20 20 20 20 20 52 65 73 } is. Res
0a00: 75 6c 74 20 3a 3d 20 54 6f 70 28 53 29 3b 0a 09 ult := Top(S);..
0a10: 53 2e 43 75 72 5f 4c 65 6e 20 2d 3d 20 31 3b 0a S.Cur_Len -= 1;.
0a20: 20 20 20 20 65 6e 64 20 66 75 6e 63 20 50 6f 70 end func Pop
0a30: 3b 0a 20 20 20 20 20 20 0a 65 6e 64 20 63 6c 61 ;. .end cla
0a40: 73 73 20 53 74 61 63 6b 3b 0a 0a 66 75 6e 63 20 ss Stack;..func
0a50: 54 65 73 74 5f 53 74 61 63 6b 28 29 20 69 73 0a Test_Stack() is.
0a60: 20 20 20 20 76 61 72 20 53 74 6b 20 3a 20 53 74 var Stk : St
0a70: 61 63 6b 3c 55 6e 69 76 5f 49 6e 74 65 67 65 72 ack<Univ_Integer
0a80: 2c 20 49 6e 74 65 67 65 72 3e 20 3a 3d 20 43 72 , Integer> := Cr
0a90: 65 61 74 65 28 35 29 3b 0a 0a 20 20 20 20 50 72 eate(5);.. Pr
0aa0: 69 6e 74 6c 6e 28 22 50 75 73 68 69 6e 67 20 31 intln("Pushing 1
0ab0: 2e 2e 35 22 29 3b 0a 20 20 20 20 53 74 6b 2e 50 ..5");. Stk.P
0ac0: 75 73 68 28 31 29 3b 0a 20 20 20 20 53 74 6b 2e ush(1);. Stk.
0ad0: 50 75 73 68 28 32 29 3b 0a 20 20 20 20 53 74 6b Push(2);. Stk
0ae0: 2e 50 75 73 68 28 33 29 3b 0a 20 20 20 20 53 74 .Push(3);. St
0af0: 6b 2e 50 75 73 68 28 34 29 3b 0a 20 20 20 20 53 k.Push(4);. S
0b00: 74 6b 2e 50 75 73 68 28 35 29 3b 0a 0a 20 20 20 tk.Push(5);..
0b10: 20 50 72 69 6e 74 6c 6e 28 22 50 6f 70 20 3d 20 Println("Pop =
0b20: 22 20 7c 20 53 74 6b 2e 50 6f 70 28 29 29 3b 0a " | Stk.Pop());.
0b30: 20 20 20 20 50 72 69 6e 74 6c 6e 28 22 50 6f 70 Println("Pop
0b40: 20 3d 20 22 20 7c 20 53 74 6b 2e 50 6f 70 28 29 = " | Stk.Pop()
0b50: 29 3b 0a 20 20 20 20 50 72 69 6e 74 6c 6e 28 22 );. Println("
0b60: 50 75 73 68 69 6e 67 20 36 22 29 3b 0a 20 20 20 Pushing 6");.
0b70: 20 53 74 6b 2e 50 75 73 68 28 36 29 3b 0a 20 20 Stk.Push(6);.
0b80: 20 20 50 72 69 6e 74 6c 6e 28 22 50 6f 70 20 3d Println("Pop =
0b90: 20 22 20 7c 20 53 74 6b 2e 50 6f 70 28 29 29 3b " | Stk.Pop());
0ba0: 0a 20 20 20 20 50 72 69 6e 74 6c 6e 28 22 50 6f . Println("Po
0bb0: 70 20 3d 20 22 20 7c 20 53 74 6b 2e 50 6f 70 28 p = " | Stk.Pop(
0bc0: 29 29 3b 0a 20 20 20 20 50 72 69 6e 74 6c 6e 28 ));. Println(
0bd0: 22 50 6f 70 20 3d 20 22 20 7c 20 53 74 6b 2e 50 "Pop = " | Stk.P
0be0: 6f 70 28 29 29 3b 0a 20 20 20 20 50 72 69 6e 74 op());. Print
0bf0: 6c 6e 28 22 50 6f 70 20 3d 20 22 20 7c 20 53 74 ln("Pop = " | St
0c00: 6b 2e 50 6f 70 28 29 29 3b 0a 0a 20 20 20 20 2f k.Pop());.. /
0c10: 2f 20 50 72 69 6e 74 6c 6e 28 22 41 62 6f 75 74 / Println("About
0c20: 20 74 6f 20 75 6e 64 65 72 72 75 6e 20 74 68 65 to underrun the
0c30: 20 73 74 61 63 6b 22 29 3b 0a 0a 20 20 20 20 2f stack");.. /
0c40: 2f 20 50 72 69 6e 74 6c 6e 28 22 50 6f 70 20 3d / Println("Pop =
0c50: 20 22 20 7c 20 53 74 6b 2e 50 6f 70 28 29 29 3b " | Stk.Pop());
0c60: 0a 0a 65 6e 64 20 66 75 6e 63 20 54 65 73 74 5f ..end func Test_
0c70: 53 74 61 63 6b 3b 0a 20 20 20 20 0a Stack;. .