Abstract Data Types IISufficient operationsNecessary operationsConvenience operationsNecessary and sufficient operationsExample: StringsTypes of operationsRequirementsOperations in JavaFactory methodsExample: StringImmutable objectsExample: StringBufferMutable objectsSafe use of StringsUnsafe use of StringBuffersSummaryThe EndAbstract Data Types II2Sufficient operationsOperations on an ADT are sufficient if 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 ADT4Convenience 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?5Necessary 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 class6Example: 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!7Types of operationsA constructor is creates a value of the ADT from input valuesAn accessor uses a value of the ADT to compute a value of some other typeA transformer uses a value of the ADT to computer another value of the ADTA mutative transformer changes the value of the ADT it is givenAn applicative transformer takes one ADT and, without changing it, returns a new ADT8RequirementsThe constructors and transformers must together be able to create all legal values of the ADTThe accessors must be able to extract any data needed by the application9Operations 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 it10Factory methodsThe problem with a constructor is that it will always construct an object of a given typeThis isn’t always what you wantAnother approach is to embed the call or calls to a constructor inside a “factory” methodExample:public 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);}11Example: 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.12Immutable 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 String13Example: StringBufferConstructors:public StringBuffer(String s)Accessors:public int length()public char charAt()Transformers (applicative):noneTransformers (mutative):public StringBuffer append(Object obj)Etc.14Mutable 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 back15Safe use of Strings public class Person { private String name; Person(String name) { this.name = name;} } String jan = "Jan"; Person doctor = new Person(jan); String dan = "D" + jan.substring(1, 2); Person secretary = new Person(dan);16Unsafe use of StringBuffers public class Person { private StringBuffer name; Person(StringBuffer name) { this.name = name;} } StringBuffer buffer = new StringBuffer("Jan"); Person doctor = new Person(buffer); buffer.setCharAt(0, 'D'); Person secretary = new Person(buffer);17SummaryA class should define a necessary and sufficient set of operationsConvenience operations should be justifiedOperations can be classified as:ConstructorsAccessorsTransformers (applicative or mutative)Immutable objects are often preferable to mutable objects18The
View Full Document