Abstract Data Types IISufficient operationsNecessary operationsNecessary and sufficient operationsConvenience operationsSlide 6Example: StringsTypes of operationsRequirementsOperations in JavaFactory methodsFactory methods IIExample: StringImmutable objectsExample: StringBufferMutable objectsSafe use of StringsUnsafe use of StringBuffersSummaryThe EndAbstract Data Types II2Sufficient operationsA set of operations on an ADT is sufficient if, together, they meet all the requirementsThey must be able to create all the values and perform all the operations required by the applicationRemember that the application cannot directly access the internal valuesThey should be able to create all the values and perform all the operations required by any application in a given class of applications3Necessary operationsAn operation on an ADT is necessary if omitting it would fail to meet the requirementsIf the application can implement an operation easily and efficiently by combining other operations, that operation is unnecessaryIt’s OK to have unnecessary operations if they add significantly to the convenience of using the ADT4Necessary and sufficient operationsNotice that “sufficient” applies to a set of operations, while “necessary” applies to individual operations in that set“Necessary” is relative to the set; an operation that is necessary in one set may not be necessary in anotherA necessary and sufficient set of operations is a set which is sufficient (meets all the requirements), but would not be sufficient if any one operation were omitted5Convenience operationsAn operation is a convenience operation if it could be accomplished by some overly complex combination of other operationsConvenience operations should be justifiedWill it be used often?Does it really simplify the user’s task?Would the user expect this operation to be provided?Is it significantly more efficient?6Necessary and sufficient operationsA class should define a necessary and sufficient set of operationsConvenience operations should be justifiedSimilarly, a class should have a necessary and sufficient data representationIn general, a class should not contain data that can be easily computed from other data in the class7Example: StringsNecessary and sufficient operators:A constructor: public String(char[] chs)Ways to access data:public int length()public charAt(int index)Would you be happy with just these?If you invented the String class, could you justify operations such as equals and string concatenation?Convenience operators aren’t all bad!8Types of operationsA constructor creates a legal value of the ADT (typically from input values)An accessor uses a value of the ADT to compute a value of some other typeA transformer uses a value of the ADT to compute another value of the same ADTA mutative transformer changes the value of the ADT it is givenAn applicative transformer takes one value of an ADT and, without changing it, returns a new value of the same ADT9RequirementsThe constructors and transformers must together be able to create all legal values of the ADTA constructor or transformer should never create an illegal valueIt’s nice if the constructors alone can create all legal values, but sometimes this results in constructors with too many parameters for reasonable convenienceThe accessors must be able to extract any data needed by the application10Operations in JavaConstructors can be implemented with Java constructorsA constructor’s job is to construct an object of a class in a valid stateThat should be a constructor’s only jobAccessors and transformers can be implemented with Java methodsMutative transformers are typically (but not always) implemented as void methodsSometimes they both modify an object and return it11Factory methodsThe problem with a constructor is that it will always construct an object of a given typeThis isn’t always what you wantThe constructor might be called with illegal values of the parametersYou may wish to create unique instances of objectsA common solution to these problems is to embed the call or calls to a private constructor inside a static “factory” methodExample:public static Animal create(String voice) { if (voice.equals("woof")) return new Dog(); if (voice.equals("meow")) return new Cat(); if (voice.equals("moo")) return new Cow(); throw new IllegalArgumentException(voice);}12Factory methods IIWith a normal constructor, public class Add { public Add( ) { } }each call to new Add() creates another Add objectThese objects are not equal unless you define your own equals(Object o) methodBut with a factory method, public class Add { static Add add = new Add(); // done once when class is loaded private Add( ) { } // hide this constructor from the world! public static Add getAdd( ) { return add; } }You can only ever have one Add objectHence, the default equals method (same as ==) always works13Example: StringConstructors:"This is syntactic sugar for a constructor"public String(char[] chs)Accessors:public int length()public char charAt()Transformers (applicative only):public String substring(int i, int j)public String concat(String that) (also +)Etc.14Immutable objectsA String is immutable: it cannot be changedThe String class has no mutative transformersOperations such as string concatenation create new StringsAdvantages:Efficient (for most uses)Easy to use and simple to understand (changing a String in one object doesn’t change it in other objects)Disadvantage:Every call to a transformer creates a new String15Example: StringBufferConstructors:public StringBuffer(String s)Accessors:public int length()public char charAt()Transformers (applicative):noneTransformers (mutative):public StringBuffer append(Object obj)Etc.16Mutable objectsA StringBuffer is mutable: it can be changedThe StringBuffer class has both applicative and mutative transformersAdvantage:Efficient (for doing a lot of string manipulation)Disadvantage:Can be confusing (example coming up shortly)Operations on Strings are done by converting to StringBuffers, doing the work, and converting back17Safe use of Strings public class Person { private String name; Person(String name) { this.name =
View Full Document