循环数组

1 .CMPE 135: Object-Oriented Analysis and Design September 20 Class Meeting Department of Computer Engineering San Jose State University Fall 2018 Instructor: Ron Mak www.cs.sjsu.edu/~mak 1

2 .2 Queue as a Circular Array What if the precondition is violated? count becomes negative. After head has wrapped around, remove() returns a previously removed message. /** * Remove message at head. * @return the message that was removed from the queue * @precondition size() > 0 */ Message * MessageQueue ::remove () { Message *r = elements[head]; head = (head + 1) % elements->capacity(); count--; return r; } The cost of violating a precondition can be very high!

3 .3 Assertions How can we ensure that a precondition is met? Use the C++ assert macro to alert a class user at run time that there is a precondition violation: The boolean expression is the precondition. If it is false at run time, your program will abort and display the assertion that failed. #include < cassert > ... assert( boolean expression );

4 .Assertions , cont’d 4 #include < iostream > #include < cmath > #include < cassert > using namespace std ; void print_sqrt (double x) {     assert(x > 0);     cout << "Square root = " << sqrt (x) << endl ; } int main() {     double x;     cout << "x? ";     cin >> x;     print_sqrt (x);     return 0; } AssertExample.cpp

5 .Assertions , cont’d Assertion testing does incur a runtime performance penalty. When you are sure that you’ve debugged your program and preconditions are never violated at run time, you can “turn off” assertions: 5 #define NDEBUG #include < cassert >

6 .6 Queue as a Circular Array with Assertion #include < cassert > ... /** * Remove message at head. * @return the message that was removed from the queue * @precondition size() > 0 */ Message * MessageQueue ::remove () { assert(elements->size() > 0); Message *r = elements[head]; head = (head + 1) % elements->size(); count--; return r; }

7 .7 Exceptions as Part of the Contract The exception is part of the contract, and so there is no size precondition. /** * Remove message at head. * @return the message that was removed from the queue */ Message * MessageQueue ::remove() throw(string) { if (elements->size() <= 0) throw("empty queue!"); Message *r = elements[head]; head = (head + 1) % elements->size(); count--; return r; }

8 .8 Postconditions A postcondition is a condition that the service provider promises to fulfill after the call has completed. Example: MessageQueue ::add() The postcondition of one call can imply the precondition of another call: @postcondition size() > 0 q.add (m1); ... m2 = q.remove ();

9 .9 Postconditions , cont’d If a postcondition of a function is not fulfilled, the function should not throw an exception. Why not? It is the function’s responsibility to ensure that the postcondition is true upon return. The caller should not have to catch an exception. The function can use an assert macro to ensure that the postcondition is true before returning.

10 .Class Invariants A class invariant is a logical condition that holds for all objects of a class, except possibly for objects that are undergoing mutation. In other words: A class invariant must be true before and after every member function call, although it can be temporarily violated inside a member function. 10

11 .11 Class Invariants , cont’d Example: Circular array MessageQueue class: Is it true after every constructor has completed? Guarantee that no invalid objects are ever created. Is it preserved by every mutator? If it is true at the start of the mutator, it must still be true after the mutator returns. It may be temporarily violated while the mutator is executing. (0 <= head) && (head < elements->capacity()) Why aren’t we concerned about accessors?

12 .12 Class Invariants , cont’d The constructor for MessageQueue Sets head to 0 Therefore, the invariant is true after the constructor is called. (0 <= head) && (head < elements->capacity())

13 .13 Class Invariants , cont’d Which member function is the only one that changes the value of head ? (0 <= head) && (head < elements->capacity ())

14 .14 Proof of a Class Invariant The invariant: The remove() function sets Because Therefore And from the definition of % (0 <= head) && (head < elements->capacity ()) head new = ( head old + 1) % elements->capacity() head old + 1 > 0 head new = ( head old + 1) % elements->capacity() >= 0 head new < elements->capacity() A remainder is always >= 0 A remainder is < the divisor.

15 .Proof of a Class Invariant , cont’d We have proven that the class invariant always holds for accesses of elements . Is it possible to use invariants to prove that an entire program is correct? Can that be done automatically? 15

16 .16 Interface Invariants vs. Implementation Invariants Interface invariants Conditions involve only the public interface of a class. A class user is interested in these because they guarantee class behavior . Implementation invariants Conditions involve the details of a particular implementation . A class implementer is interested in these because they ensure the correctness of the algorithms .

17 .17 Interface Invariants vs. Implementation Invariants, cont’d Which type are the MessageQueue invariants? Are head and elements visible to the class user? A Day class invariant: Which type of invariant is it? It’s stated in terms of only the public interface of the class. 1 <= get_month () && get_month () <= 12 (0 <= head) && (head < elements->capacity ())

18 .Interfaces An interface is a form of a contract between programmers . An interface specifies the public member functions of the classes that implement the interface. For each function: its name and return type, and the number, order, and types of its formal parameters. An interface specifies the API of the classes that implement the interface. 18

19 .Interfaces , cont’d We can define an interface in C++ as an abstract class containing only pure virtual functions . An interface has no implementation. An interface cannot be instantiated. Each pure virtual function must be implemented by a class that implements the interface. 19

20 .Interface Example 20 class shape   // An interface class { public:     virtual void move_x ( int x) = 0 ;     virtual void move_y ( int y) = 0 ;     virtual void draw() = 0 ; ... }; C++ interface classes are maintained in .h header files. In UML class diagrams, interface names are in italics or oblique font .

21 .Interfaces and the RPS Game You’re developing the RPS game. You’re designing algorithms to determine the computer’s choice. Random algorithm : Randomly choose rock, paper, or scissors each time. Smart algorithm : Use simple machine learning to make a choice. Genius algorithm : Use sophisticated machine learning to make a choice. 21

22 .Interfaces and the RPS Game , cont’d What if you don’t know ahead of time which choice algorithm you’ll want to use? What if you come up with new choice algorithms later? 22

23 .Interfaces and the RPS Game , cont’d Make Chooser an interface. Its pure virtual member functions are the API to invoke a computer choice algorithm. The subclasses implement the interface and therefore they must implement the member functions. They contain the computer choice algorithms. 23 ComputerPlayer Chooser RandomChooser SmartChooser GeniusChooser

24 .Interfaces and the RPS Game , cont’d Now you can write: What is wrong with this code? Pointer variables rc , sc , and gc each is restricted to point to only one type of chooser object. 24 RandomChooser * rc = new RandomChooser (); SmartChooser * sc = new SmartChooser (); GeniusChooser * gc = new GeniusChooser (); ComputerPlayer Chooser RandomChooser SmartChooser GeniusChooser

25 .Code to the Interface Instead, use a variable of the interface type Example: Variable chooser and any code that uses chooser should not need to know which type of chooser object it is currently pointing to. As long as the object uses the Chooser API. 25 Chooser *chooser = new SmartChooser (); ComputerPlayer Chooser RandomChooser SmartChooser GeniusChooser

26 .Code to the Interface , cont’d Code to the interface, not to a specific class. This design principle is not strict about what is an interface. The interface can also be any supertype. 26 Chooser *chooser = new SmartChooser (); ComputerPlayer Chooser RandomChooser SmartChooser GeniusChooser

27 .Code to the Interface , cont’d The call to new is awkward. What if we invent a new choice algorithm? We would have to rewrite any code that creates chooser objects. 27 Chooser *chooser = new SmartChooser (); ComputerPlayer Chooser RandomChooser SmartChooser GeniusChooser

28 .A Factory Class Create a factory class ChooserFactory that has a static member function make_chooser that takes a parameter. The parameter determines which Chooser subclass to instantiate and return. Better: Instead of a string parameter, use an enumeration parameter. The factory class thereby encapsulates any future changes in the choice algorithms. 28 static Chooser * ChooserFactory :: make_chooser (string which);

29 .A Factory Class , cont’d 29 Chooser * ChooserFactory :: make_chooser (string which) { if (which == "random") return new RandomChooser (); else if (which == "smart") return new SmartChooser (); else if (which == "genius") return new GeniusChooser (); } Chooser *chooser = ChooserFactory :: make_chooser ("smart"); ComputerPlayer Chooser RandomChooser SmartChooser GeniusChooser