blob: 4ddd7fe2d0c2c7f78ee14433a9db87a1dd157606 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
// RUN: %dafny /compile:0 /dprint:"%t.dprint" "%s" > "%t"
// RUN: %diff "%s.expect" "%t"
class RingBuffer<T>
{
// public view of the class:
ghost var Contents: seq<T>; // the contents of the ring buffer
ghost var N: nat; // the capacity of the ring buffer
ghost var Repr: set<object>; // the set of objects used in the implementation
// private implementation:
var data: array<T>;
var start: nat;
var len: nat;
// Valid encodes the consistency of RingBuffer objects (think, invariant)
predicate Valid()
reads this, Repr;
{
this in Repr && null !in Repr &&
data != null && data in Repr &&
data.Length == N &&
(N == 0 ==> len == start == 0 && Contents == []) &&
(N != 0 ==> len <= N && start < N) &&
Contents == if start + len <= N then data[start..start+len]
else data[start..] + data[..start+len-N]
}
constructor Create(n: nat)
modifies this;
ensures Valid() && fresh(Repr - {this});
ensures Contents == [] && N == n;
{
Repr := {this};
data := new T[n];
Repr := Repr + {data};
start, len := 0, 0;
Contents, N := [], n;
}
method Clear()
requires Valid();
modifies Repr;
ensures Valid() && fresh(Repr - old(Repr));
ensures Contents == [] && N == old(N);
{
len := 0;
Contents := [];
}
method Head() returns (x: T)
requires Valid();
requires Contents != [];
ensures x == Contents[0];
{
x := data[start];
}
method Enqueue(x: T)
requires Valid();
requires |Contents| != N;
modifies Repr;
ensures Valid() && fresh(Repr - old(Repr));
ensures Contents == old(Contents) + [x] && N == old(N);
{
var nextEmpty := if start + len < data.Length
then start + len else start + len - data.Length;
data[nextEmpty] := x;
len := len + 1;
Contents := Contents + [x];
}
method Dequeue() returns (x: T)
requires Valid();
requires Contents != [];
modifies Repr;
ensures Valid() && fresh(Repr - old(Repr));
ensures x == old(Contents)[0] && Contents == old(Contents)[1..] && N == old(N);
{
x := data[start]; assert x == Contents[0];
start, len := if start + 1 == data.Length then 0 else start + 1, len - 1;
Contents := Contents[1..];
}
}
method TestHarness(x: int, y: int, z: int)
{
var b := new RingBuffer.Create(2);
b.Enqueue(x);
b.Enqueue(y);
var h := b.Dequeue(); assert h == x;
b.Enqueue(z);
h := b.Dequeue(); assert h == y;
h := b.Dequeue(); assert h == z;
}
|
