Specify the behavior using Guttag's axiomatic method. Use ML as a specification language, and test your specs by executing them on some test data.
Include your test data as ML code at the end of each ADT.
this item (0) is just practice... work it out to get used to using ML
as a specification notation. You can start with the ML given for SET and
make changes.
(0) multi-set (bag)
A multi-set is a set that can have an item added to it more than once,
so every item in a set has a value and a count. Here are the operations:
add : put an item in the set... this will increase the count by 1 for
an item already in the set
rem : take an item out of the set
in : boolean... tells is an item is in the set (count above 0) or not
n : return the number of times an element is in the set (0 for elements
not in the set)
empty : is the set empty?
size : tell how many unique items are in the set
num : tell how many total items are in the set
Do these next 3 items to hand in
(1) ring
this is a form of bounded queue; if the ring is full, and you add an item, then
it stomps the oldest item (the one at the head). You can think of the finite
number of elements as being in a ring, and you keep adding around the ring.
(2) stomp stack
a bounded stack; when you push an item on a full stack, it "mashes" the bottom
item out to make room at the top
(3) priority stack
the stack contains items that are pairs: an element, and an integer priority
(0 is low priority); when you push an item, it percolates down toward the
stack bottom until it hits an item with priority equal to or lower... and
it stays there on top of that item.