CS211 Spring 2002 Lecture 8: Trees and Recursion 2/13/2003 ------------------------------------------------------------------------------- 0) Announcements: + A3 coming soon! (will show in lecture) + A2 mostly graded tonight + extra help: "11/8-11/20" at http://www.cs.cornell.edu/courses/cs100j/2001fa/Notes/lecture_notes.html Objectives/Topics of Lecture 8: + inheritance + applications of inheritance + Object and equals, toString, clone + abstract classes ------------------------------------------------------------------------------- 1) OOP Revisited OOP: + encapsulation (has-a) + inheritance (is-a) + polymorphism (many forms) Encapsulation: + abstraction: move "away" from details + information hiding: hide details to prevent unspeakable horrors + has-a: form types by modelling state and behavior Inheritance: + extensibility: extend behavior of a class to another + code reuse: copy code from one class to another + subtyping: generalize notion of types (things can be other things) Polymorphism: + type of a thing: having many forms + a typed variable can be many things of "related" types Encapsulation + Inhertance + Polymorphism: + abstraction + code reuse and subtyping + generic programming ------------------------------------------------------------------------------- 2) Inheritance Basics IS-A/CAN-BE relationships: + class = classification = category + some classifications more general than others ex) Class Person, Class Mammal A Person is a Mammal. A Mammal can be a Person. ex) A BinaryNode is a Node. A Node can be a BinaryNode. Terminology: + general class: SUPERCLASS/base class/parent class + specific class: SUBCLASS/derived class/child class Graphical: +--------+ | A | +--------+ /\ /||\ || +---++---+ | B | +--------+ General Syntax: + only one class may be extended class SUPERCLASS extends SUBCLASS { ... } + forms single inheritance hierarchy, which is a tree + "higher" classes are inherited from the immediate superclass Inheriting members: + Unless private, members inherit, which means "copied" into subclass + public methods in subclass can override same methods in superclass + also variable "overriding" which is called shadowing and is bad Highest level superclass + Object + http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html + useful methods which programmers can override: - toString: return String description of an object - equals: return boolean when comparing contents two objects - clone: return copy of object ------------------------------------------------------------------------------- 3) Polymorphism Basics How Polymorphism works: + general: If class B extends class A, then an object made from B can be an A + example: A Dime is a Coin. A Penny is a Coin. I have a Coin in my pocket. It could be a Dime or a Penny. + Obvious cases: A a1 = new A() (OK) A Coin can be any particular Coin. B b1 = new B() (OK) A Dime can be any particular Coin. + Polymorphic cases: A a2 = new B() (OK) A Coin can be any particular Dime. Why? A Coin can be a Dime or a Penny. B b2 = new A() (!OK) A Dime can be any particular Coin. (NO!) A Penny cannot be a Dime, which is a type of Coin. Fix? B b2 = (B) new A() Naturally occurring polymorphism: + An integer is also a double. (double) so, an integer can be a double so, "integer" extends "double" so, double x = 7 is an OK assignment! (int) + also, int x = (int) 7.1 also works. Aliases: + example) A a = new A() A b = new B() + can you use a=b? a-var a-object A-class b-var b-object B-class Casting: + temporarily treating a thing as a "related" type: + refer to "can be" relationships, above Type primvar = (Type) primitive Type refvar = (Type) object + primitives: example) double y = 7.7; int x = (int)y; type of x? int type of y? double type of (int)y? int Note: y is NOT changed! + objects: UP-CASTING: SuperType var = new SubType() always legal (assumes Sub is child of Super) "up" because "lower" object type is stored in "higher" Super type SuperType var = (SuperType) new SubType() is legal, but superfluous DOWN-CASTING: SubType var = (SubType) new SuperType() *not* guaranteed to be legal when running, but will usually compile "down" because "higher" object type is stored in "lower" Super type SubType var = new SuperType() isn't legal Useful Java things: + instanceof operator: returns boolean if object is a class name syntax: reference instanceof name + getName (see ObjectInfo and ObjectExample) Applications: Assume mixed collection of items: class Thing { void eat(){...} } class Apple extends Thing{} class Water extends Thing{ void swallow(){...} } Thing[] things = {new Apple(), new Apple(), new Water()} Up-casting: Activate same method for each object in "mixed" collection: for (int i = 0; i < things.length; i++) things[i].eat(); Down-casting: Activate a method or do something only for particulars in collection: for (int i = 0; i < things.length; i++) if (things[i] instanceof Water) ((Water) things[i]).swallow(); Why ((Water) things[i])? [] and . have higher precedance than cast! ------------------------------------------------------------------------------- 4) Under the Covers (a bit) Questions: + How are members inherited? + How to access fields and methods? + overriding and privacy? When things happen: + compile time: when you compile a program + run time: when you run a program Static binding: + code to perform operation happens before run-time; ie, compile time + types of references are checked for relationship (same/sub/super) + fields and method names are associated with classes that correspond to the reference variable type Dynamic binding: + code to perform operation happens at run time + types of objects are checked for relationship (same/sub/super) + methods are accessed according to the actual type of the object Order of creation of an object: + set all fields to default values ("zeros") + access the constructor of the class. - Use empty constructor class name() if no constructor is written in class - Empty constructor *not* available if other constructor(s) are there + call a constructor of the same class with this(...) (if necessary) + call the superclass constructor with super(...). - Use super() by default if no super(...) is given + continue the process (work all the way up) to Object + "come down" - assign fields top-down, left to right - complete each constructor execution for each superclass until returning to subclass ------------------------------------------------------------------------------- 5) Inheritance 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 - methods are accessed by the object type for "outside" call - 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 + super: access a superclass member unless that member is NOT visible -------------------------------------------------------------------------------