Introduction to Computer Science • Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.cs.Princeton.EDU/IntroCS3.4 Encapsulation and ADTsBond. What's your escape route?Saunders. Sorry old man. Section 26 paragraph 5, that informationis on a need-to-know basis only. I'm sure you'll understand.2Abstract Data TypesData type. Set of values and operations on those values.Ex. int, String, Complex, Vector, Document, Wave, Tour, …Abstract data type. Data type whose internal representation is hidden.Separate implementation from design specification.! Class provides data representation and code for operations.! Client uses data type as black box.! API specifies contract between client and class.5Counter Data TypeCounter. Data type to count electronic votes.Legal Java client.Pitfall. Al Gore receives -16,022 votes in Volusia County, Florida.public class Counter { int count; public Counter() { count = 0; } public void hit() { count++; } public int get() { return count; } }Counter c = new Counter();c.count = -16022;6Counter. Abstract data type to count electronic votes.Does not compile.Benefit. Can guarantee invariant that each data type valueremains in a consistent state.Counter Abstract Data Typepublic class Counter { private int count; public Counter() { count = 0; } public void hit() { count++; } public int get() { return count; } }Counter c = new Counter();c.count = -16022;7Changing Internal RepresentationJava ADTs.! Keep data representation hidden with private access modifier.! Expose API to clients using public access modifier.Advantage. Can switch to polar representation without changing client.Note. All our data types are already ADTs!public class Complex { private double re; private double im; public Complex(double re, double im) { … } public double abs() { … } public Complex plus(Complex b) { … } public Complex times(Complex b) { … } public String toString() { … }}8Time BombsY2K. Two digit years: January 1, 2000.Y2038. 32-bit seconds since 1970: January 19, 2038.ZIP codes. USPS changed from ZIP to ZIP + 4 code in 1983.VIN numbers. Will run out by 2010 ! representation change ahead!Lesson. By exposing data representation to client, need to sift throughmillions of lines of code in client to update.9Encapsulation.! Can't "touch" data and do whatever you want.! Instead, "ask" object to manipulate its data.Lesson. Limiting scope makes programs easier to maintain and understand."Ask, don't touch."Adele GoldbergFormer president of ACMCo-developed SmalltalkAsk, Don't Touch"principle of least privilege"10Modular Programming and EncapsulationADTs enable modular programming.! Separate compilation.! Split program into smaller modules.! Different clients can share the same ADT.ADTs enable encapsulation.! Keep modules independent from each other.! Can substitute different classes that implement same API.GamePlayerPlayerPlayerPlayerDeck............Introduction to Computer Science • Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.cs.Princeton.EDU/IntroCS4.6 Symbol Tables12Symbol Table ADTSymbol table, Key-value pair abstraction.! Insert value with specified key.! Search for value given key.! Delete value with given key.Ex. key = URL, value = IP address.! Insert URL with specified IP address.! Given URL, find corresponding IP address.keyvalue www.cs.princeton.eduWeb Site IP Address128.112.136.11 www.princeton.edu 128.112.128.15 www.yale.edu 130.132.143.21 www.harvard.edu 128.103.060.55 www.simpsons.com 209.052.165.6013Symbol Table ApplicationsApplication Purpose Key ValuePhone book Look up phone number Name Phone numberDictionary Look up word Word DefinitionBook index Find relevant pages Keyword List of pagesBank Process transaction Account number Transaction detailsFile system Find file on disk File name Location on diskGenomics Find markers DNA string Known positionsDNS Find IP address given URL URL IP addressReverse DNS Find URL given IP address IP address URLFile share Find song to download Name of song Computer IDWeb cache Download Filename File contentsCompiler Find properties of variable Variable name Value and typeWeb search Find relevant documents Keyword List of documentsRouting table Route Internet packets Destination Best route14Symbol Table Client: DNS LookupDNS lookup client program.! st.put(key, value) inserts a key-value pair into symbol table.! st.get(key) searches for the given key and returns the value.public static void main(String[] args) { SymbolTable st = new SymbolTable(); st.put("www.princeton.edu", "128.112.128.15"); st.put("www.yale.edu", "130.132.143.21"); st.put("www.simpsons.com", "209.052.165.60"); System.out.println(st.get("www.harvardsucks.com")); System.out.println(st.get("www.simpsons.com"));}% java SymbolTableTestnull209.052.165.60st["www.simpsons.com"] = "209.052.165.60"st["www.simpsons.com"]15Symbol Table Client: Remove DuplicatesRemove duplicates. [from a mailing list or voting eligibility list]! Read in key.! If key is not in symbol table, print out key and insert it.public class DeDup { public static void main(String[] args) { SymbolTable st = new SymbolTable(); while (!StdIn.isEmpty()) { String key = StdIn.readString(); if (st.get(key) == null) { System.out.println(key); st.put(key, ""); } } }}insert empty string as value16Symbol Table: Linked List ImplementationMaintain a linked list of key-value pairs.! Insert new key-value pair at beginning of list.! Exhaustive search list to find given key. www.princeton.edu128.112.128.15 www.yale.edu130.132.143.21 www.harvard.edu128.103.060.55null. . .keyvaluenext17Symbol Table: Linked List Implementationpublic class SymbolTable { private Node first; private class Node { String key; Object value; Node next; Node(String key, Object value, Node next) { this.key = key; this.value = value; this.next = next; } } public void put(String k, Object val) { first = new Node(k, val, first); } public Object get(String k) { for (Node x = first; x != null; x = x.next) if (k.equals(x.key)) return x.value; return null; } }a linked list of key-value pairsinsert at front of listexhaustively search for keynot found18ObjectClass Object. All objects "inherit" certain methods from the specialsuperclass Object.Consequence. Can have a symbol table whose values are any type.Annoyance. Must cast the return value of get() to