Popular in Course
Popular in Computer Information Technology
This 109 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS120 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/215376/cis120-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for PROGLANG&TECHI
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/28/15
Introduction to Programming Languages and Techniques Collections and Generics REVIEW GENERICS 2242010 Generic List interface public interface ListltEgt 2242010 public public public public public public boolean addE e boolean removeObject e boolean containsObject e int size E getint i E setint i E p CIS 120 Generic List class I Class definition is also abstracted on element type public class LinkedListltEgt implements ListltEgt public void addE elt public Element getint i I When instantiating a generic class give type of elements ListltStringgt strings new LinkedListltStringgt stringsaddquotabcquot String s stringsget0 ListltPointgt points new LinkedListltPointgt pointsaddnew Point12 Point p pointsget0 2242010 CIS 120 Using Builtin Lists l Creating and using a list with the Java API gt import javautil gt ListltStringgt words new ArrayListltStringgt gt wordsaddquotcatquot gt wordsaddquotratquot gt wordsget1 ll ratquot a list implementation 2242010 5 SHORTCOMINGS 2242010 Warning I Generics were added to Java rather late in its development I They are not fully integrated with other features of the language I The JVM doesn t know about Generics I Generics implemented using the compiler 2242010 Kludge I A kludge is a workaround 2242010 an ad hoc engineering solution a clumsy or inelegant solution to a problem typically using parts that are cobbled together klumsy lame ugly dumb but good enough class ArrayListltEgt implements ListltEgt private E data private int size public ArrayList thisdata 39 Cantallocate arrays thissize r v 39 with a generic type Can t test generic types The problem obj instanceof E Generics implemented by obj instanceof ListltEgtgt theconmmer 1 Adding casts Can t cast to a generic type 2 Type erasure E element Eobject 2242010 CIS 120 Bug Generics only of Objects I Illegal Listltintgt Listltchargt I Solution Object wrappers for primitive types I the Double Float lnteqer Lonq Short Character I More later 2242010 10 2242010 THE COLLECTIONS FRAMEWORK Review Kinds of Collections Ordered Unordered Duplicates List Bag allowed Multiset NO SortedSet Set Duplicates 2242010 CIS 120 Java Collections Framework CollectionltEgt ListltEgt SetltEgt SortedSetltEgt I Collection provides a uniform interface to several kinds of structured data 2242010 13 Using the Java Collections Framework l Creating and using a list with the Java API gt import javautil gt ListltStringgt words new ArrayListltStringgt gt wordsaddquotcatquot gt gt words add quotratquot a list implementation wordsget1 quot ratquot I Any object type class interface is allowed 2242010 14 Sets I No duplicates I No ordering I When is x a duplicate of y xequals y 2242010 Review Duplicates Comparison Listl gt ladd3 true gt ladd3 true gt 1 3 3 When is a a duplicate ofb When a equal b 2242010 iStrue Sets gt sadd3 true gt sadd3 false gt S 3 CIS 120 16 Equality I Default definition available for any Object public boolean equalsObject o return this 0 nothing equals I Specific classes can override null public class Point x public boolean equalsObject o inuo es if 0 null return false xequals Y if this 0 return true if o instanceof Point return false Point p Pointo return x pgetX ampamp y pgetY zmnmo m 17 Set implementations I HashSet uses hash codes to access to set elements very fast membership checking I TreeSetI different spacetime tradeoff less space slower I more details in CIS 121 2242010 18 Hash Function I Converts a large amount of data into typically a single integer I Usually very fast I Used to speed up data comparison tasks I Two items that have different hash codes must be different I But two different items might collide from Wikipedia 2242010 19 Hash codes I An integer associated to any object ohashCode I Useful in implementing efficient sets I If two objects are equals they should have the same hash code I Expectation different objects tend to have different hash codes I Classes should override hashCode if they override equals 2242010 20 STATIC vs DYNAMIC TYPES REPRISE 2242010 21 Past Recommended Reading I Nino amp Hosch chapter 12 chapter 20 for gory details of generics l Java tutorial trail on collection classes httQiavasuncomdocsbookstutorialcollectionsTOChtml 2242010 22 Dynamic Types of Objects I When a new object is created in the heap it is tagged with the class it was instantiated from Point new Point10 20 up doublex 10 double y 20 I This tag is the object s dynamic type lltneverchanges 2242010 23 Dynamic Types of Expressions I An expression describes a computation that when executed eventually yields an object or scalar value as its result x xconcat bar new CharSeqStrlmp foo new CharSeqStrlmp foo concat bar l The expression s dynamic type is the dynamic type of its result 2242010 24 2242010 public void foo Object x x What is the dynamic type ofx 25 Static Types l Static types are used by the compiler to check for obvious nonsense in programs during development new Point2030concat bar l Surprisingly effective at eliminating bugs 2242010 26 Static Types of Expressions I Each constant has a static type I An object creation expression of the form new C has static type C I Each variable has a static type declared by the programmer I The static type of a method call is the result type declared by the programmer 2242010 27 Static Types of Expressions I The static type of a cast Ce is C no matter what the static type of e is I A few casts are obvious nonsense and will be rejected by the compiler In particular side casting between unrelated classes is not allowed because it is guaranteed to fail at run time CharSeqStrImp new Point2 03 0 Side casts between unrelated interfaces are OK But dangerous 2242010 28 Generics l Generic types are a refinement of the static type system that allows it to track for example the type of the elements in a collection I so that for example when we get an element from the collection we can track what type it will be 2242010 29 simplified Collection interface public interface CollectionltEgt Basic operations int size 2242010 boolean boolean boolean boolean Bulk boolean boolean boolean boolean isEmpty containsE element addE element removeE element operations containsAllCollectionltEgt c addAllCollectionltEgt c removeAllCollectionltEgt c retainAllCollectionltEgt c void clear 30 Collection interface 2242010 public interface CollectionltEgt Basic operations int size boolean isEmpty boolean containsObject eiement boolean addE element boolean removeObject element Bulk boolean boolean operations addAllCollectionltEgt c boolean removeAllCollectionltEgt c boolean retainAllCollectionltEgt c void clear because the underlying equals method takes an Object as argument containsAllCollectionltEgt c 31 Introduction to Programming Languages and Techniques Java for the Expenenced Schedule 91509 CIS 120 Fall 2010 Course website I Everything about syllabus grading assignments exams labs textbook software is or will be at httpwwwseasupenneducis120 I Resources page I How to use course bulletin board I How to download and run DrJava 11309 CIS 120 Spring 2010 91509 Tentative Exam Dates I Midterm 1 I Midterm 2 I Final exam Fri 212 in class Fri 324 in class Thu 56 911 am location TBA Notify me of conflicts before the exams CIS 120 Fall 2010 Reminder First homework assignment I Available from course web page now Due Wed Jan 20 at 11 AM 91509 CIS 120 Fall 2010 1 Hill game elp lEi 91509 CIS 120 Fall 2010 Autograding l Submission will be explained Monday I Autograder available now on Eniac Points awarded based on how many tests your code passes Available on Resources tab of course web page Instructions under How to compile and run supplied lab testers 91509 CIS 120 Fall 2010 91509 CS120 Homework 01 Test Results Test Sample Interactions Passed 40 points Test Checking unexplored neighbors Passed 50 points Test Unexplored neighbors Edge Passed 50 points Test Unexplored neighbors Edge ll Passed 50 points Test Unexplored neighbors Corner Passed 40 points Test Unexplored neighbors Corner ll Passed 50 points Raw score for this problem 280280 Excellent job Question 4 Better Exploration Test Sample Interactions Passed 30 points Test Corner exploration Passed 30 points Test Double exploration Passed 30 points Test Nonzeros Passed 20 points Test Partiallyexplored areas Passed 20 points Test Exploring islands Passed 30 points Raw score for this problem 160160 Excellent job Total score 100 out of 100 CIS 120 Fall 2010 Any Questions 91509 CIS 120 Fall 2010 91509 ON TO JAVA CIS 120 Fall 2010 91509 The Java Programming Language 571 microsystems I Designed in the early 90s first popularized for web programming I Key design principles Platform independence Security Stability CIS 120 Fall 2010 91509 Java for the experienced I Basic concepts in Java I Values I Variables I Complex dataobjects I Functionsmethods I Expressions I Conditionals I Loops CIS 120 Fall 2010 English to Java dictionary I Piece of data value I Kind of data type I Place to store a value variable I Structured group of variables object I Variable belonging to an object instance variable I Kind of object class I Object of a particular class class instance 91509 CIS 120 Fall 2010 13 91509 CIS 120 Fall 2010 Values and types I All data values in Java have a type I The type of a value determines I Memory representation I Allowed operations I Conversion to other types I Types are program invariants I catch errors 91509 CIS 120 Fall 2010 Primitive types I Values that Java knows how to operate on directly I Integer int 1 42 I Fractional floating point number floatdoub1e 1 314159 299792458E8 I Character char J m I Truth value boolean true false 91509 CIS 120 Fall 2010 16 Primitive numeric types I Numeric types in Java are characterized by their size how much memory they occupy I Integral types these details size range Wequot Very Important right byte 1 byte 128 127 now we ll come back to them in short 2 bytes 3276832767 V7 C5240 char 2 bytes 065535 g of int 4 bytes 21474836482147483647 long 8 bytes I Floating point types size largest smallest gt 0 float 4 byte 2239232127 2449 double 8 bytes 22395221023 2391074 91509 CIS 120 Fall 2010 17 Strings I Builtin nonprimitive type String I Strings are sequences of characters quotJavaquot quot3 Stoogesquot quotEiIJlquot string literals I means concatenation quot3quot quot quot quotStoogesquotgtquot3 Stoogesquot I Automatic conversion of numbers to strings 3 quot quot quotStoogesquotgtquot3 Stoogesquot I Text in a String is immutable 91509 CIS 120 Fall 2010 18 Expressions l Java expressions compute values I expressions use operators to combine values of primitive types 98632 59 W times divide grouping 91509 CIS 120 Fall 2010 19 91509 Operator Precedence How does Java interpret 2 3 4 Group first using the highest precedence operators 1 Unary 2 Binary 3 Binary Making operator precedence explicit 2 3 4 CIS 120 Fall 2010 20 Operator Overloading I The meaning of an operator is determined by what it operates on Integer division 43 2 1 Floating point division 4030 gt 13333333333333333 Automatic conversion 43 0 gt 13333333333333333 91509 CIS 120 Fall 2010 21 Variables I Variables store values I All variables must be declared int seats double averageHeight boolean isFriday String familyName 91509 CIS 120 Fall 2010 22 Storing into variables I Assignment statement seats 150 averageHeight 21 174 1583 isFriday true familyName quotBeeblebroxquot I Must store values of the right type In DrJava39s interactions pane isFriday 1 Error Bad types in assignment 91509 CIS 120 Fall 2010 23 Initializmg variables I Declaring and initializing a variable double MILESPERGALLON 70 String myName quotMitchquot I This is the preferred declaration form I If initial value is omitted default is based on type double averageHeight double averageHeight 00 91509 CIS 120 Fall 2010 24 Objects and classes I Structured group of variables object I Class a template for creating objects I Bank account class I Date class I Student class I Every Java object is an instance of some class I The class of an object determines I type of data it contains instance variables I operations that can be performed methods 91509 CIS 120 Fall 2010 25 91509 a Counter object Counter int count 4 Counter Counter morementCount Int count 3 Counter reset int count 4 CIS 120 Fall 2010 39 int count 0 Saying it in Java public class Counter private int count instance variable public Counter count O COnSUIK OF public int currentCount metg giy return count public VOld incrementCount conunand count count 1 public void reset count O conunand 91509 class declaration CIS 120 Fall 2010 27 91509 What s public private I Basically I public accessible from outside the class I private not accessible outside the class I Protect object internals from outside interference I More details later in the course CIS 120 Fall 2010 28 Creating and using objects I Declare a variable of appropriate type to hold the Counter object I Invoke the constructor for Counter to create a Counter instance and store it in the variable Counter 039 Counter 0 new Counter C39El Int count 0 make a new object 91509 CIS 120 Fall 2010 29 91509 or declare and initialize together Counter c new Counter CIS 120 Fall 2010 30 Objects with parameters 91509 I A point on the plane is given by its coordinates X y in a fixed frame of reference public class Point private double x y public Pointdouble anX double aY x anX y aY public double getX return x public double getY return y CIS 120 Fall 2010 31 Parameters vs arguments I Parameters specify data that must be provided in an invocation parameters public Pointdouble anX double aY x anX y aY I Arguments are the actual values supplied Point p new Point25 30 arguments 91509 CIS 120 Fall 2010 32 Constructor invocation new Point Point double x 0 double x 0 2 5 3 0 public Pointdoub1e anX double aY double ii 25 double 30 x anX y aY same memor at different times P int y double x 25 double z 30 Point p p 91509 CIS120 Fall 2010 33 Methods I Let s add a moving method to Point I Changes the internal state of Point objects public class Point private double x private double y oid movedouble dx double dy gt015 public v il H quotit 1 91509 CIS 120 Fall 2010 34 Method invocation Point p1 new Point1 1 P1 gt Point double x 1 double x 1 p1move 5 1 public void movedoub1e dx double dy doubr doubl x x dx Y Y dy Point same memory at different times double X 15 double x 2 91509 CIS 120 Fall 2010 35 Java identifiers I Variable class and method names are identifiers I Alphanumeric characters or starting with a letter or size myName MILESPERGALLON A1 theend Interpretation depends on context variables and classes can have the same name 36 91509 CIS 120 Fall 2010 lden erabuse Class instance variable constructor public class Turtle and method WIth the private Turtle Turtle Same name public Turtle public Turtle Turtle Turtle Turtle return Turtle 91509 CIS 120 Fall 2010 37 Introduction to Programming Languages and Techniques Java for the Expe enced Methods Expressions and Arrays Tentative Exam Dates before 7 u Course BB Tapiu Polk M Announcemenb This is where relevant course announcements will be posted 0 D No Pass Moderator C151 ESE TA 7 General Questions 5 S 13 2009 393quot For general questions about the course Java SEAS etc 1 1 uquot aprobhead Moderator lleSE 1Ms i If HW 1 Minesweeper J lDue Wednesday September 15th at 1100am Moderator 13ESE 7A5 1016 pm Sun Sep 13 2009 757 pm 3 23 melata LE You should be checking it at least once a day 12010 CIS 120 Spring 2010 Tutoring I Tutors for CIS 120 are available in Moore 207 on I Sunday night 6pm10pm I Monday night 7pm10pm thanks to Jonathan Leung 12010 CIS 120 Spring 2010 4 Schedule w Tutoring CIS 120 Schedule 12010 CIS 120 Spring 2010 Objects and classes I Structured group of variables object I Class a template for creating objects I Bank account class I Date class I Student class I Every Java object is an instance of some class I The class of an object determines I type of data it contains instance variables I operations that can be performed methods 12010 CIS 120 Spring 2010 Instances of a Counter class Counter Counter I mcrementCount gt I Int count 3 Int count 4 Counter reset Cou nter int count 4 7 int count 0 12010 CIS 120 Spring 2010 Saying it in Java public class Counter private int count instance variable public Counter count O COHSUIK OF public int currentCount g gg ds return count accessor public VOld incrementCount conunand count count 1 public void reset count O conunand class declaration 12010 CIS 120 Spring 2010 12010 What s public private I Basically I public accessible from outside the class I private not accessible outside the class I Declare what you can do with objects of the class I Protect object state I Details later CIS120 Spring 2010 Creating and using objects I Declare a variable of appropriate type to hold the Counter object I Invoke the constructor for Counter to create a Counter instance and store it in the variable Counter 039 Counter 0 new Counter C39EI Int count 0 make a new object 12010 CIS 120 Spring 2010 10 Objects with parameters 12010 I A point on the plane is given by its coordinates X y in a fixed frame of reference public class Point private double x y public Pointdouble anX double aY x anX y aY public double getX return x public double getY return y CIS 120 Spring 2010 11 Parameters and arguments I Parameters specify data that must be provided in an invocation parameters public Pointdouble anX double aY x anX y aY I Arguments are the actual values supplied Point p new Point25 30 arguments 12010 CIS 120 Spring 2010 12 Constructor invocation new Point Point double x 0 1 double y 0 2 5 3 0 public Pointdoub1e anx double aY double a double a x anx y aY Point double x 25 double y 30 same memory at different times Point p D 12010 CIS 120 Spring 2010 13 Methods I Add a moving method to Point I Changes the state of Point objects public class Point private double x private double y 12010 CIS 120 Spring 2010 14 Method invocation Point p1 new Point1 1 pkg p1move 5 public void movedouble dx double dy N x dx YYdy same memory at different times 12010 CIS 120 Spring 2010 Point double x 1 double y 1 1 Point double x 15 double x 2 Java identifiers I Variable class and method names are identifiers I Alphanumeric characters or starting with a letter or size myName MILESPERGALLON A1 theend Interpretation depends on context variables and classes can have the same name 12010 CIS 120 Spring 2010 Iden erabuse Constructor amp Method w same public class Turtle nanua private Turtle Turtle public Turtle public Turtle TurtleTurtle Turtle return Turtle 12010 CIS 120 Spring 2010 17 Naming conventions kind partof speech identifier class noun RacingCar variable noun initialSpeed constant noun MAXIMUMSPEED method verb shiftGear 12010 CIS 120 Spring 2010 18 Java expressions I Compute values of different types I Numeric values 93 10 p1getX l String values hello world I Object values new Point I Boolean values 30 gt 20 12010 CIS 120 Spring 2010 19 Comparisons I Conditions that test the values of variables I Equal X y x Watch out for 3939 instead of 3939 answer 39y39 I Not equal X y x 05 answer 39y39 I Less than X lt y not greater than X lt y x lt 05 x lt 05 I Greater than X gt y not smaller than X gt y x gt 05 x gt 05 12010 CIS120 Spring 2010 20 Combining conditions I Boolean operators can be used to make more complicated conditions I And p ampamp q income gt 50000 ampamp income lt 70000 I or p I I q isRaining isSnowing I Not q isRaining 12010 CIS 120 Spring 2010 21 Short circuiting l Sometimes Java doesn39t evaluate an entire condition false ampamp xlaunchmissles true xexplodebomb l Reordering changes behavior but not result xlaunchmissles ampamp false xexplodebomb true 12010 CIS 120 Spring 2010 22 Statements if I Statements perform actions I Control flow statement Use a condition to choose with action to take public String transport I if isFrigid gt phlllytransporto return quotskisquot quotbicyclequot else gt barrowtransport return quotbicyclequot quotskisquot 12010 CIS 120 Spring 2010 23 Multiway decision public String transport if isFrigid return quotskisquot else if isTropical return quotsurfboardquot else return quotbicyclequot gt phillytransport quotbicyclequot gt honolulutransport quotsurfboardquot 12010 CIS 120 Spring 2010 24 Nested decisions public String dominant String animal if isFrigid if latitude gt 0 4 7 animal quotpolar bearquot cmnpound else statement animal quotpenguinquot else animal quotratquot return animal 12010 CIS 120 Spring 2010 25 12010 Iteration I Repeat an action possibly stopping when some condition is satisfied I Eat MampMs until the bag is empty I Take successive streets until you reach your destination I Move robot While it hasn t reached goal I Count the number of books on a shelf CIS 120 Spring 2010 26 Iteration while bagisEmpty bageatMM while shelfhasNextBook Book book shelfgetNextBook catalogueaddnfobook numBooks numbooks1 12010 CIS 120 Spring 2010 27 General iteration statement while condition statement I condition is a boolean expression I statement is any simple or compound statement I If condition is initially false the statement is never executed I statement should eventually make the loop stop 12010 CIS 120 Spring 2010 28 Accumulation operators I State change and iteration often involve accumulating into some variable I accumulate interest into a savings account balance I accumulate distance traveled into an odometer I Java like C C provides concise accumulation statements sum increment sum lt sum increment sum decrement sum lt sum decrement prod factor prodlt prod factor prod denom prodlt prod denom 12010 CIS 120 Spring 2010 29 Incrementdecrement expressions x y2 y 1 x y2 x x y2 y2 y 1 y2 y 1 x y2 X x y2 y2 y 1 Can also be used as expressions Not recommended 12010 CIS 120 Spring 2010 30 12010 ARRAYS CIS120 Spring 2010 31 Collections I Groups of entities of similar kind I Albums in a collection I Items in store I Characters in a video game I Doing the same thing to all of them I Computing the total number of tracks I Adding sales tax to all the prices I Moving all of them one step forward 12010 CIS 120 Spring 2010 32 Arrays I Requirements I Regular all items have the same type I Random access we need to get to any item equally easily I Solution I Index items with successive integers I Place items in order according to their indices I Consequences I Need to allocate a chunk of memory to hold all the items gt know in advance number of items 12010 CIS 120 Spring 2010 33 Java arrays the basic idea I Index elements from O I The ith element of array a aI I Create an array a of size n with elements of type type type a new typen int a new int4 a2 7 i Wit 0 1 2 3 12010 CIS 120 Spring 2010 34 12010 For loops l Iteration over a range of values I Especially suitable for arrays double sumdouble a double total 0 for int i 0 i lt alength i total ai return total CIS120 Spring 2010 35 Array processing recipe I Given an array I Goal apply a processing step to each array element I Ingredients I an array index number of elements I a for loop for int index O i lt array length index process arrayindex 12010 CIS 120 Spring 2010 36 For loop details initialization loop condition update for int i 0 i lt alength i total ai loop body 12010 CIS 120 Spring 2010 37 Array bounds check I Access to a i requires 0 Silta length I Java checks each access and reports an exception if the index is out of bounds gt int a 1 2 gt a2 3 javalangArrayIndexOutOfBoundsException 2 at I There39s a lot more to learn about exceptions 12010 CIS 120 Spring 2010 38 Array details I Empty array convenient for boundary cases double empty new doubleO emptylength gt 0 I Array initializer int oneTonhree 1 2 3 oneTonhreelength 2 3 oneTonhree1 gt 2 12010 CIS 120 Spring 2010 39 Arrays of any type I Arrays can be made for any Java type int a Point p new Point12 1 3 5 7 a E p new Point34 0 1 2 3 O 1 String s quotaquot quotbquot quotcquot Point Point E x 10 x 30 s y 20 y 40 0 1 2 quotaquot quotbquot quotCquot 12010 CIS 120 Spring 2010 40 Arrays are reference types I Assignment does not copy arrays int a 1 3 5 7 intba a 1957 b 0 1 2 3 a19 bl 12010 CIS 120 Spring 2010 41