CS61B Lecture #19Simple Banking I: AccountsSimple Banking II: BanksBanks (continued): IteratingPartial ImplementationsExample: The java.util.AbstractList helper classExample, continued: AListIteratorExample: Using AbstractListAside: Another way to do AListIteratorGetting a View: SublistsWhat Does a Sublist Look Like? Arrays and LinksImplementing with ArraysLinkingClever trick: SentinelsSpecializationStacks and RecursionDesign Choices: Extension, Delegation, AdaptationCS61B Lecture #19Administrative:• Need alternative test time? Make sure you send me mail today.• Review session in 306 Soda, 6-8pm Sunday, 5 March.Today:• Maps• Generic Implementation• Array vs. linked: tradeoffs• Sentinels• Specialized sequences: stacks, queues, deques• Circular buffering• Recursion and stacks• AdaptersReadings:Data Structures,Chapter 3, 4 (for today), and 5 (next).Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 1Simple Banking I: AccountsProblem: Want a simple banking system. Can look up accounts by nameor number, deposit or withdraw, print.Account Structureclass Accou n t {Account (String name, String number, int init) {this.name = name; this.n umber = number;this.balance = init;}/** Account - h o lder’s name */final Strin g name;/** Account number */final Strin g number;/** Current balance */int balance ;/** Print THIS on STR in some useful format. */void print (PrintWriter str) { ... }}Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 2Simple Banking II: Banksclass Bank {/* These variables maintain mappings of String -> Account. They keep* the set of keys (String s) in "compareTo" order, and the set of* values (Account s ) is ordered according to the corresponding keys. */SortedMap<String,Account > accounts = new TreeMap<String,Account> ();SortedMap<String,Account > names = new TreeMap<String,Account> ();void openAc c o u nt (String name, int in i t B alance) {Account acc =new Account (name, chooseNumb e r (), initBalance);accounts.put (acc . number, acc);names.put (name, acc);}void deposi t (String number, int amount) {Account acc = acco u nts.get (number);if (acc == null) ERROR(...);acc.balance += amount;}// Likewise for withdraw.Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 3Banks (continued): IteratingPrinting out Account Data/** Print out all accounts sorted by number on STR. */void printB y A c count (PrintStream str) {// accounts.values () is the set of mapped-to values. Its// iterator produces elements in order of the corresponding keys.for (Account account : accounts.values ())account.print (st r );}/** Print out all bank acconts sorted by name on STR. */void printB y N a me (PrintStream str) {for (Account account : names.values ())account.print (st r );}A Design Question: What would be an appropriate representation forkeeping a record of all tr ansactions (deposits and withdrawal s) againsteach account?Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 4Partial Implementations• Besides interfaces (li ke List) and concrete typ es (like LinkedList),Java library provides abstract classes such as AbstractList.• Idea is to take advantag e of the fa ct that operation s are related toeach other.• Example: once you know how to do get(k) a nd size() for an imple-mentation of List, you can implement all the other methods neededfor aread-onlylist (and its iterators).• Now throw in add(k,x) and you ha ve all you need for the additionaloperations of a growable list.• Add set(k,x) and remove(k) and you can imple ment everything else.Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 5Example: The java.util.AbstractList helper classpublic abst r a c t class AbstractList<Item> implements List<Item> {/** Inherited from List */// public abstrac t int size ();// public abstrac t Item get (int k);public bool e a n 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 fals e ;}/* OPTIONAL: By default, throw exception; override to do more. */void add (int k, Item x) {throw new UnsupportedOperationExcept i o n ();}Likewise for remove, setLast modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 6Example, continued: AListIterator// Continui n g abstract class AbstractList<Item>:public Iter a t o r<Item> iterator () { return listIterator (); }public List I t e rator<Item> listIterator () { return new AListIterator (this); }private sta t i c class AList I t erator implements ListIterator<Item> {AbstractList<Item> myList;AListIterator (Ab s tractList<Item> L) { myList = L; }/** Current position in our list. */int where = 0;public bool e a n hasNext () { return where < myList.size (); }public Item next () { where += 1; return myList . g et (where-1); }public void add (Item x) { myList.add (where, x); where += 1; }...previous, remove, set, etc.}...}Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 7Example: Using AbstractListProblem: Want to create areversed viewof an e xisting List (sameelements in reverse order).public clas s ReverseList<Item> exten ds AbstractList<It em> {private final List<Item> L;public ReverseLis t (List<Item> L) { this.L = L; }public int size () { return L.size (); }public Item get (int k) { return L.get (L.size ()-k-1); }public void add (int k, Item x){ L.add (L.size ()-k, x); }public Item set (int k, Item x){ return L.set (L.size ()-k-1, x); }public Item remove (int k){ return L.remove (L.size () - k - 1); }}Last modified: Wed Mar 8 12:03:56 2006 CS61B: Lecture #19 8Aside: Another way to do AListIteratorIt’s also possible to make the nested class non-static:public Iter a t o r<Item> iterator () { return listIterator (); }public List I t e rator<Item> listIterator () { return this.new AListIterator (); }private cla s s AListIterator imp l ements ListIterato r <Item> {/** Current position in our list. */int where = 0;public bool e a n hasNext () { return where < AbstractList.this.size (); }public Item next () { where += 1; return Abstra c t List.this.get (where- 1 ) ; }public void add (Item x) { AbstractList.this.add (where, x); whe r e += 1; }...previous, remove, set, etc.}...}• Here, AbstractList.this means “the Abstract List I am attachedto” and X.new AListIterator means “create a new AList Iteratorthat is attached to X.”• In this case you can abbreviate this.new as new and can leave offthe AbstractLis t.this parts, since meaning is unambiguous.Last modified: Wed Mar 8 12:03:56 2006 CS61B:
View Full Document
Unlocking...