Copyright © 2007 by Robert Sedgewick and Kevin Wayne.1Symbol TablesReferences: Algorithms in Java, Chapter 12.Intro to Algs and Data Structs, Chapter 4.Intro to Programming, Section 4.4.•API•basic implementations•iterators•Comparable keys•challenges 2API basic implementationsiteratorsComparable keyschallenges3Symbol TablesKey-value pair abstraction.!Insert a value with specified key.!Given a key, search for the corresponding value.Example: DNS lookup.!Insert URL with specified IP address.!Given URL, find corresponding IP addressCan interchange roles: given IP address find corresponding URLkeyvalue www.cs.princeton.eduURL 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.604Symbol Table ApplicationsApplication Purpose Key ValuePhone book Look up phone number Name Phone numberBank Process transaction Account number Transaction detailsFile shareFind song to download Name of song Computer IDDictionaryLook up word WordDefinitionWeb search Find relevant documents Keyword List of documentsGenomicsFind markers DNA string Known positionsDNS Find IP address given URL URL IP addressReverse DNS Find URL given IP address IP address URLBook indexFind relevant pagesKeyword List of pagesWeb cacheDownloadFilename File contentsCompiler Find properties of variable Variable name Value and typeFile system Find file on disk Filename Location on diskRouting table Route Internet packets DestinationBest route5Symbol Table APIAssociative array abstraction. Unique value associated with each key.Symbol table API.!put(key, val) insert the key-value pair!get(key) search: return value associated with given key!remove(key) remove the key!contains(key) is given key present?!iterator() return iterator over all keysOur conventions.!Values are not null.!Method get() returns null if key not present.!Implementations all have!Method put() overwrites old value with new value.a[key] = val; public boolean contains(Key key) { return get(key) != null; }Some languages (not Java) allow this notationST client: make a dictionary and process lookup requestsCommand line arguments!a comma-separated value (CSV) file!key field!value fieldExample 1: DNS lookup6% more ip.csvwww.princeton.edu,128.112.128.15www.cs.princeton.edu,128.112.136.35www.math.princeton.edu,128.112.18.11www.cs.harvard.edu,140.247.50.127www.harvard.edu,128.103.60.24www.yale.edu,130.132.51.8www.econ.yale.edu,128.36.236.74www.cs.yale.edu,128.36.229.30espn.com,199.181.135.201yahoo.com,66.94.234.13msn.com,207.68.172.246google.com,64.233.167.99baidu.com,202.108.22.33yahoo.co.jp,202.93.91.141sina.com.cn,202.108.33.32ebay.com,66.135.192.87sohu.com,61.135.133.103163.com,220.181.29.154passport.net,65.54.179.226tom.com,61.135.158.237nate.com,203.226.253.11cnn.com,64.236.16.20daum.net,211.115.77.211blogger.com,66.102.15.100fastclick.com,205.180.86.4wikipedia.org,66.230.200.100rakuten.co.jp,202.72.51.22...% java Lookup ip.csv 0 1adobe.com192.150.18.60www.princeton.edu128.112.128.15ebay.eduNot found% java Lookup ip.csv 1 0128.112.128.15www.princeton.edu999.999.999.99Not foundURL is key IP is valueIP is key URL is value7ST client: make a dictionary and process lookup requestspublic class Lookup{ public static void main(String[] args) { In in = new In(args[0]); int keyField = Integer.parseInt(args[1]); int valField = Integer.parseInt(args[2]); String[] database = in.readAll().split("\n"); ST<String, String> st = new ST<String, String>(); for (int i = 0; i < database.length; i++) { String[] tokens = database[i].split(","); String key = tokens[keyField]; String val = tokens[valField]; st.put(key, val); } while (!StdIn.isEmpty()) { String s = StdIn.readString(); if (!st.contains(s)) StdOut.println("Not found"); else StdOut.println(st.get(s)); } }}process inputbuild symbol tableprocess lookupsST client: make a dictionary and process lookup requestsCommand line arguments!a comma-separated value (CSV) file!key field!value fieldExample 2: Amino acids8% more amino.csvTTT,Phe,F,PhenylalanineTTC,Phe,F,PhenylalanineTTA,Leu,L,LeucineTTG,Leu,L,LeucineTCT,Ser,S,SerineTCC,Ser,S,SerineTCA,Ser,S,SerineTCG,Ser,S,SerineTAT,Tyr,Y,TyrosineTAC,Tyr,Y,TyrosineTAA,Stop,Stop,StopTAG,Stop,Stop,StopTGT,Cys,C,CysteineTGC,Cys,C,CysteineTGA,Stop,Stop,StopTGG,Trp,W,TryptophanCTT,Leu,L,LeucineCTC,Leu,L,LeucineCTA,Leu,L,LeucineCTG,Leu,L,LeucineCCT,Pro,P,ProlineCCC,Pro,P,ProlineCCA,Pro,P,ProlineCCG,Pro,P,ProlineCAT,His,H,HistidineCAC,His,H,HistidineCAA,Gln,Q,GlutamineCAG,Gln,Q,GlutamineCGT,Arg,R,ArginineCGC,Arg,R,ArginineCGA,Arg,R,ArginineCGG,Arg,R,ArginineATT,Ile,I,IsoleucineATC,Ile,I,IsoleucineATA,Ile,I,IsoleucineATG,Met,M,Methionine...% % java Lookup amino.csv 0 3ACTThreonineTAGStopCATHistidinecodon is key name is valueST client: make a dictionary and process lookup requestsCommand line arguments!a comma-separated value (CSV) file!key field!value fieldExample 3: Class lists9% more classlist.csv10,Bo Ling,P03,bling10,Steven A Ross,P01,saross10,Thomas Oliver Horton Conway,P03,oconway08,Michael R. Corces Zimmerman,P01A,mcorces09,Bruce David Halperin,P02,bhalperi09,Glenn Charles Snyders Jr.,P03,gsnyders09,Siyu Yang,P01A,siyuyang08,Taofik O. Kolade,P01,tkolade09,Katharine Paris Klosterman,P01A,kklosterSP,Daniel Gopstein,P01,dgtwo10,Sauhard Sahi,P01,ssahi10,Eric Daniel Cohen,P01A,edcohen09,Brian Anthony Geistwhite,P02,bgeistwh09,Boris Pivtorak,P01A,pivtorak09,Jonathan Patrick Zebrowski,P01A,jzebrows09,Dexter James Doyle,P01A,ddoyle09,Michael Weiyang Ye,P03,ye08,Delwin Uy Olivan,P02,dolivan08,Edward George Conbeer,P01A,econbeer09,Mark Daniel Stefanski,P01,mstefans09,Carter Adams Cleveland,P03,cclevela10,Jacob Stephen Lewellen,P02,jlewelle10,Ilya Trubov,P02,itrubov09,Kenton William Murray,P03,kwmurray07,Daniel Steven Marks,P02,dmarks09,Vittal Kadapakkam,P01,vkadapak10,Eric Ruben Domb,P01A,edomb07,Jie Wu,P03,jiewu08,Pritha Ghosh,P02,prithag10,Minh Quang Anh Do,P01,mqdo...% java Lookup classlist.csv 3 1jshJeffrey Scott HarrisdgtwoDaniel GopsteinyeMichael Weiyang Ye% java Lookup classlist.csv 3 2jshP01AdgtwoP01login is key name is valuelogin is key precept is value10Keys and ValuesAssociative array abstraction.!Unique value associated with each key!If client presents duplicate key, overwrite to change value.Key type: several possibilities1. Assume keys are any generic type,
View Full Document
Unlocking...