Generic Programming and Inner classesRecall linear search codeThis linear search code not dependent on typesGoalKey ideas in solutionRewrite linear search using while-loopIntuitive idea of generic linear searchIterator interfaceGeneric Linear SearchHow does data class implement Iterator interface?Adapter (version 1)CritiquePowerPoint PresentationSharks and remorasAdapter (version 2)….. Shark s = new Shark(); //object containing data Iterator enum= new Remora(s)…. Object v = ….; boolean b = linearSearch( new Remora(s), v); …..Slide 17Solution: use an inner classSlide 19Adapter (version 3)Important PointsClient codeWebsiteGeneric Programming and Inner classesge·ner·ic 1a : relating or applied to or descriptive of all members of a genus, species, class, or group : common to or characteristic of a whole group or class : typifying or subsuming : not specific or individual.Reading: Weiss: 118-130 (Section 4.6)ProgramLive: Sections 12.3 and 12.4.A use of generic: We like to buy generic drugs, instead of brand-name drugs, because they are cheaper.poly·mor·phism: the quality or state of being polymorphous: as (1) : capability of assuming different forms : capability of wide variation2// = “v is in b”static boolean linearSearch (int b, int v) { for (int k= 0; k < b.length; k= k+1) if (b[k] == v) return true; return false;} Recall linear search codeCode in red relies on data being stored in a 1-D array of ints.For-loop also implicitly assumes that data is stored in 1-D array.Does not work for other types or if data is stored in amore general data structure such as a 2-D array.3// = “v is in b”static boolean linearSearch (Comparable[] b, Object v) { for (int k= 0; k < a.length; k= k+1) if (a[i].compareTo(v) == 0) return true; return false;}This linear search code not dependent on typesMore generic, because it is independent of the type of the array.This is polymorphism.But: still relies on data being stored in a 1-D array.This code will not work if data is stored in a more general data structure such as a 2-D array.4Goal•First version of linear search –Input was array of int•More generic version of linear search–Input was array of Comparable•Can we write a still more generic version of linear search that is independent of data structure?–For example, work even with 2-D arrays of Comparable5Key ideas in solution•Iterator interface•Linear search written once and for all using Iterator interface•Data class that wants to support linear search must implement Iterator interface•Implementing Iterator interface–Inner classes provide elegant solution6Rewrite linear search using while-loop// = “v is in b”static boolean linearSearch (Comparable[] a, Object v) { int k= 0; // invariant: v is not in a[0..k-1] while (k < a.length) { if (a[k].compareTo(v) == 0) return true; k= k+1; } return false;}Intuitively, linear search needs to know- are there more elements to look at? - if so, get me the next element7Intuitive idea of generic linear search•Data is contained in some object.•Object has an adapter that permits data to be enumerated in some order.•Adapter has two buttons–boolean hasNext(): are there more elements to be enumerated?–Object Next(): if so, give me a new element that has not been enumerated so far422234-94-922Linear search8Iterator interfacepublic interface Iterator { boolean hasNext(); Object next(); void remove(); //we will not use this}This interface is predefined in package java.util.Linear search is written using this interface.Data class must provide an implementation of this interface.9Generic Linear Searchstatic boolean linearSearch(Iterator b, Object v) { while (b.hasNext()) if (((Comparable) b.next()).compareTo(v) == 0) return true; return false;}static boolean linearSearch(Comparable[] k, Object v){ int k= 0; while (k < a.length) { if (a[k].compareTo(v) == 0) return true;k= k+1; } return false;}array versionIterator version10How does data class implement Iterator interface?Let us look at a number of solutions.1. Adapter code is part of class containing data2. Adapter is a separate class that is hooked up to data class3. Adapter is an inner class in class containing data11Adapter (version 1)public class Crock1 implements Iterator{ private SomeClass[] a; //Class SomeClass must implement // Comparable private int cursor= 0; //index of next element to be enumerated /** Constructor: an instance with … public Crock1() { …store data in array a… } public boolean hasNext() { return (cursor < a.length); } public Object next() { cursor= cursor + 1; return a[cursor-1]; } public void remove() {}//unimplementated}12Critique•As shown, client class can enumerate elements only once!–How do we reset the cursor?•Making the data class implement Iterator directly is something of a crock because its concern should be with data, rather than enumeration of data.13•One solution to resetting the cursor:–Data class implement a method void reset() which resets all internal cursor(s)–Method must be declared in Iterator interface•But we still cannot have multiple enumerations of elements going on at the same time•Remember: only one cursor….•Problem: cannot create new cursors on demand•To solve this problem, cursor must be part of a different class that can be instantiated any number of times for a single data object.14Sharks and remorasData class is like sharkIterator implementationis like a remora.Single shark must allow us to hook many remoras to it.15Adapter (version 2)class Shark{ public Comparable[] a; // Constructor: … public Shark() {…get data into a…} …}Remora teethpublic class Remora implements Iterator{ int cursor; Shark myShark; public Remora(Shark s) { { myShark= s; cursor= 0; } public boolean hasNext() { return (cursor < myShark.a.length); } public Object next() { cursor= cursor+1; return myShark.a[cursor-1];} public void remove() {} //unimplemented}The client, using Shark:Shark s= new Shark(…); …Iterator enum= new Remora(s);while (enum.hasNext()) { … }16 ….. Shark s = new Shark(); //object containing data Iterator enum= new Remora(s)…. Object v = ….; boolean b = linearSearch( new Remora(s), v); ….. Client code:myShark = cursor = 0myShark = cursor = 0SharkRemoraRemora17Critique•Good: –Class Shark focuses on data, class
View Full Document
Unlocking...