CS211 Spring 2002 Lecture 9: Trees and Recursion 2/18/2003 ------------------------------------------------------------------------------- 0) Announcements: + lecture and section notes updated on-line + A2 regrades due@end of consulting next Tuesday (2/25) + E2 due today + A3 due next week + Prelim 1 ("T1" for "test") on Thurs 3/6 - topics: lecture, section: <= 2/20 (will be posted in Prelims link) assignments: E1, E2, A1, A2, A3 weird bonus "dren" - scheduled conflicts? see 12.3 in Syllabus + A4.... Objectives/Topics of Lecture 9: + mechanics of inheritance in Java + abstract classes + interfaces: subtyping, built-in + Comparable Roadmap: + improve your grasp of OOP to supply inner classes (classes that "contain" other classes) + enhance I/O by applying interfaces and inner classes to design GUIs + apply interfaces and inner classes to make iterators (generic control) + improve how we handle info (sorting, searching, algorithm analysis) + use interfaces for abstract data types (generic data structures) ------------------------------------------------------------------------------- 1) The Rules + subclass extends a superclass (only single inheritance is allowed) + rules for visibility and access - fields are accessed by the reference type for "outside" call at compile time - instance methods are accessed by the object type for "outside" call at runtime - public/protected methods and fields are inherited unless written in the subclass (called overriding for methods and shadowing for fields) - private fields and methods are accessed from the SAME class that they are called (they "bind" to the current class) - private members technically do NOT inherit, but may be indirectly accessed using a public/protected member which DOES inherit - methods will access the field from the class in which the executed method is written - method name lookup at compile time, so must be specified in all super classes/interfaces that a class extends/implements - static members are technically hidden (cannot be overriden): so, they can be inherited, but are accessed through the ref type, not object type at compile time + super: access a superclass member unless that member is NOT visible (no super.super.....) examples: see CS100J notes (step-by-step) InheritNormal (what you would normally need inheritance for) InheritPrivate (how private things are treated...more obscure!) InheritAbnormal (how not to have a life) ------------------------------------------------------------------------------- 2) Summary from last time A upcasting: | down casting: B | static binding: C dynamic binding: see (3) then Casting.java ------------------------------------------------------------------------------- 3) Abstract Classes Partial Specification: Syntax: + have at least 1 abstract method (a method with only a header and no body) + cannot create objects from abstract classes! + can use abstract classes as reference types! + members will inherit from abstract classes, but the methods must be overriden in a subclass if you want the subclass to be "concrete" (to be able to make an object) see Casting.java ------------------------------------------------------------------------------- 4) Interfaces Revisted Interface + specification for a class with no implementation + could think of as a completely abstract class Uses: Syntax: + only constants and abstract methods allowed + methods are public, fields are public final (can leave off modifiers) + all classes that implement interface *must* implement all methods + a class can implement multiple interfaces + cannot have conflicting names + an interface can extend another interface (just one) class name { overriden methods } class name { overriden methods } see Interface*.java ------------------------------------------------------------------------------- 5) Comparable Why? + Useful example of implementing a pre-defined interface + step towards generic programming (comparing generic objects) + good for data structures (need to sort/search by comparing things) Limits of .equals: + only for equality + want to be able to order your objects (see if an object is LT or GT another object) + Strings have comparison defined Comparable in API: + http://java.sun.com/j2se/1.4/docs/api/java/lang/Comparable.html + natural ordering: define a way to compare objects + should be consistent with .equals + class that implements Comparable needs to define compareTo() method Taken from API: + public int compareTo(Object o) + Given currentObject.compareTo(suppliedObject), CO < SO? compareTo returns negative integer CO == SO? compareTo returns zero CO > SO? compareTo returns positive integer + You need to ensure the following: - sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) (GT and LT have opp signs) - (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0. - x.compareTo(y)==0 implies that sgn(x.compareTo(z))==sgn(y.compareTo(z)) for all z. + strongly recommended that (x.compareTo(y)==0)==(x.equals(y)) Warning: + DS&A book, section 5.2.2 has its *own* Comparable, not API's! + use API, DS&SD Example? + how to compare complex numbers? + rem: sqrt(-1) = i (or j if you're ECE :-) 1 < 2 2 > 1 1 == 1 1+3i < 1 + 4i (???) 1 + 2i ??? 2 + 1i (???) (see http://www.purplemath.com/modules/complex.htm) -------------------------------------------------------------------------------