CS61B Lecture #17Administrative:• Need alternative test time? Make sure you send memail.• Lab5 is on-line in the usual place.Today:– Maps– Generic ImplementationReadings for Today:Data Structures,Chapter 3Readings for Next Topic:Data Structures,Chap-ter 4Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 1Simple Banking I: AccountsProblem: Want a simple banking system. Can look upaccounts by name or number, deposit or withdraw, print.Account Structureclass Account {Account (String name, String number, int init) {this.name = name; this.number = number;this.balance = init;}/** Account-holder’s name */final String name;/** Account number */final String number;/** Current balance */int balance;/** Print THIS on STR in some useful format. */void print (PrintWriter str) { ... }}Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 2Simple Banking II: Banksclass Bank {SortedMap accounts = new TreeMap ();SortedMap names = new TreeMap ();void openAccount (String name, int initBalance) {Account acc =new Account (name, chooseNumber (), initBalance);accounts.put (acc.number, acc);names.put (name, acc);}void deposit (String number, int amount) {Account acc = (Account) accounts.get (number);if (acc == null) ERROR(...);acc.balance += amount;}// Likewise for withdraw.//Continues. . .Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 3Simple Banking III: IteratingPrinting out Account Data//[NOTE: Corrected after lecture. ]/** Print out all accounts sorted by number on STR. */void printByAccount (PrintStream str) {for (Iterator i = accounts.values ().iterator ();i.hasNext ())((Account) i.next ()).print (str);}/** Print out all bank acconts sorted by name on STR. */void printByAccount (PrintStream str) {for (Iterator i = names.values ().iterator ();i.hasNext ())((Account) i.next ()).print (str);}A Design Question: What would be an appropriaterepresentation for keeping a record of all transactions(deposits and withdrawals) against each account?Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 4Partial Implementations• Besides interfaces (like List) and concrete types(likeLinkedList), Java library provides abstract classessuch asAbstractList.• Idea is to take advantage of the fact that opera-tions are related to each other.• Example: once you know how to do get(k) and size()for an implementation of List, you can implement allthe other methods needed for aread-onlylist (andits iterators).• Now throw in add(k,x) and you have all you need forthe additional operations of a growable list.• Add set(k,x) and remove(k) and you can implementeverything else.Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 5Example: AbstractList• java.util.AbstractList “helper class”public abstract class AbstractList implements List {/** Inherited from List */// public abstract int size ();// public abstract Object get (int k);public boolean contains (Object x) {for (int i = 0; i < size (); i += 1) {if ((x == null && get (i) == null) ||(x != null && x.equals (get (i))))return true;}return false;}public Iterator iterator () { return listIterator (); }public ListIterator listIterator () {return new AListIterator ();}.../* OPTIONAL (By default, throw exception) */Object void add (int k, Object x) {throw new UnsupportedOperationException ();} ...}Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 6Example, continued: AListIteratorpublic abstract class AbstractList implements List {// NOTE: No error checking shown...private class AListIterator implements ListIterator {/** Current position in our list. */int where = 0;public boolean hasNext () {return where < AbstractList.this.size ();// or return where < size (); for short}public Object next () {where += 1;return AbstractList.this.get (where-1);}public void add (Object x) {AbstractList.this.add (where, x);where += 1;}...}...}Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 7Example: Using AbstractListProblem: Want to create areversed viewof an exist-ingList (same elements in reverse order).public class ReverseList extends AbstractList {private final List L;public ReverseList (List L) { this.L = L; }public int size () { return L.size (); }public Object get (int k) { return L.get (L.size ()-k-1); }public void add (int k, Object x){ L.add (L.size ()-k, x); }public Object set (int k, Object x){ return L.set (L.size ()-k-1, x); }public Object remove (int k){ return L.remove (L.size () - k - 1); }}Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 8Small Side Trip about Reflection: toArray• Types Class and reflect.Array in java.lang pro-vide way of talkingaboutJava constructs in Java./** An array containing the elements of THIS in* order. Use A if big enough, otherwise a* new array of same dynamic type. */// NOTE: CORRECTED FROM PAPER VERSIONpublic Object[] toArray (Object[] A) {Object[] result;if (A.length >= size ())result = A;else {Class eltType =A.getClass ().getComponentType ();result =(Object[]) Array.newInstance (eltType, size ());}Iterator i = iterator ();for (int j = 0; j < A.length; j += 1)if (i.hasNext ())result[j] = i.next ();elseresult[j] = null;return result;}Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 9Getting a View: SublistsProblem: L.sublist(start, end) is a full-blown Listthat gives a view of part of an existing list. Changes inone must affect the other. How?// In AbstractListList sublist (int start, int end) {return new Sublist (start, end);}private class Sublist extends AbstractList {// NOTE: Error checks not shownprivate int start, end;Sublist (int start, int end) {obvious}public int size () { return end-start; }public int get (int k){ return AbstractList.this.get (start+k); }public void add (int k, Object x) {{ AbstractList.this.add (start+k, x); end += 1; }...}Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17 10What Does a Sublist Look Like?• Consider SL = L.sublist (3, 5);L:ListobjectSL: AbstractList.thisstart: 3end: 5Last modified: Wed Oct 10 10:17:14 2001 CS61B: Lecture #17
View Full Document
Unlocking...