There have been a few changes from the specification used for assignment 7. Changes are marked by a # in column 79. -------------------------------------------------- Specification of the Dependencies ADT. Like the Refreshable and Dependency abstract data types, the Dependencies abstract data type is immutable. The Dependencies ADT shall be implemented in Java, and will be tested using Sun's Java 2 Runtime Environment, Standard Edition, version 1.6.0. The code for this implementation will be in the default package, and shall define a public class named Dependencies. That class shall provide the following public static methods: Signature: Dependencies.none : -> Dependencies Dependencies.adjoin : Dependency * Dependencies -> Dependencies Dependencies.absent : Dependencies -> boolean Dependencies.first : Dependencies -> Dependency Dependencies.rest : Dependencies -> Dependencies Dependencies.okay : Dependencies -> boolean Dependencies.absent (Dependencies.none()) = true Dependencies.absent (Dependencies.adjoin (d, s)) = false Dependencies.first (Dependencies.adjoin (d, s)) = d Dependencies.rest (Dependencies.adjoin (d, s)) = s Dependencies.okay (Dependencies.none()) = true Dependencies.okay (Dependencies.adjoin (d, s)) = Dependency.isOkay(d) && Dependencies.okay(s) Values of the Dependencies ADT shall also implement the public dynamic methods equals(Object) and hashCode() such that If v1 and v2 are values of the Dependencies ADT, then v1.equals(v2) if and only if (Dependencies.absent(v1) and Dependencies.absent(v2)) or ((not Dependencies.absent(v1)) and (not Dependencies.absent(v2)) and Dependencies.first(v1).equals(Dependencies.first(v2)) and Dendencies.rest(v1).equals(Dependencies.rest(v2))) If v1 is a value of the Dependencies ADT, but x is not, then v1.equals(x) returns false. If v1 and v2 are values of the Dependencies ADT, and v1.equals(v2) then v1.hashCode() == v2.hashCode(). ---------------- In addition, the Dependencies ADT shall provide the following public dynamic methods: Signature: maximal : -> Refreshable isMaximal : Refreshable -> boolean relevantTo : Refreshable -> Dependencies irrelevantTo : Refreshable -> Dependencies without : Dependency -> Dependencies concatenate : Dependencies -> Dependencies todo : -> Dependencies accept: Visitor -> Dependencies iterator: -> java.util.Iterator ---- If s is a Dependencies object, and s.absent() is false, then # s.maximal() is a Refreshable object r2 such that # # (1) for some Dependency d in s, r2 is Dependency.second(d) # and (2) for every Dependency d in s, r2 is not Dependency.first(d) # # Any implementation of the maximal() method that satisfies the # following algebraic specification will also satisfy the above # specification, but the above specification is more general. # Dependencies.adjoin(d, s).maximal() = Dependencies.adjoin(d, s).maximal2(Dependencies.none()) # # where # # Dependencies.adjoin(Dependency.create(r1, r2), s).maximal2(s2) # = r2 if s.isMaximal(r2) and s2.isMaximal(r2) # # Dependencies.adjoin(Dependency.create(r1, r2), s).maximal2(s2) # = s.maximal2(Dependencies.adjoin(Dependency.create(r1, r2), s2)) # if (not s.isMaximal(r2)) or (not s2.isMaximal(r2)) # # Note: maximal2(Dependencies) is not part of the Dependencies ADT, # so it does not need to be a public method. It doesn't even need # to exist. # Dependencies.none().isMaximal(r) = true Dependencies.adjoin(Dependency.create(r1, r2), s).isMaximal(r) = (not r1.equals(r)) and s.isMaximal(r) Dependencies.none().relevantTo(r) = Dependencies.none() Dependencies.adjoin(Dependency.create(r1, r2), s).relevantTo(r) = Dependencies.adjoin(Dependency.create(r1, r2), s.relevantTo(r)) if r1.equals(r) or r2.equals(r) Dependencies.adjoin(Dependency.create(r1, r2), s).relevantTo(r) = s.relevantTo(r) if (not r1.equals(r)) and (not r2.equals(r)) Dependencies.none().irrelevantTo(r) = Dependencies.none() Dependencies.adjoin(Dependency.create(r1, r2), s).irrelevantTo(r) = s.irrelevantTo(r) if r1.equals(r) or r2.equals(r) Dependencies.adjoin(Dependency.create(r1, r2), s).irrelevantTo(r) = Dependencies.adjoin(Dependency.create(r1, r2), s.irrelevantTo(r)) if (not r1.equals(r)) and (not r2.equals(r)) Dependencies.none().without(d) = Dependencies.none() Dependencies.adjoin(d, s).without(d1) = s.without(d1) if d.equals(d1) Dependencies.adjoin(d, s).without(d1) = Dependencies.adjoin(d, s.without(d1)) if not d.equals(d1) Dependencies.none().concatenate(s2) = s2 Dependencies.adjoin(d, s).concatenate(s2) = Dependencies.adjoin(d, s.concatenate(s2)) If s is a Dependencies object, then s.todo() is a topological sort # of the Dependency objects in s in the following sense: # # If s.absent() is false, and s2 is s.todo(), and d1 is s2.first(), # and r1 is Dependency.first(d1), then there does not exist a d in # s2.rest() for which r1 is Dependency.second(d), and s2 is also # a topological sort of s2. # # Any implementation of the todo() method that satisfies the # following algebraic specification will also satisfy the above # specification, but the above specification is more general. # Dependencies.none().todo() = Dependencies.none() Dependencies.adjoin(d, s).todo() = Dependencies.adjoin(d, s) .irrelevantTo(Dependencies.adjoin(d, s).maximal()) .todo() .concatenate(Dependencies.adjoin(d, s) .relevantTo(Dependencies.adjoin(d, s).maximal())) Dependencies.none().accept(v) = Dependencies.none() Dependencies.adjoin(d, s).accept(v) = Dependencies.adjoin(v.visit(d), s.accept(v)) Additional requirement: Furthermore, when computing Dependencies.adjoin(d, s).accept(v) visit(d) shall be executed before s.accept(v). That allows v to perform side effects in a predictable order. The iterator() method shall return an Iterator that conforms to Sun's general specification for java.util.Iterator. The next() method shall throw a NoSuchElementException if there are no more elements for it to generate. The remove() method shall throw an UnsupportedOperationException if it is called. The next() method shall generate Dependency objects in the same order they would be visited using the accept method. --------------------------------------------------