保留抽象性

1 .CSE373: Data Structures & Algorithms Software-Design Interlude – Preserving Abstractions Riley Porter Winter 2017 CSE373: Data Structures & Algorithms 1

2 .Course Logistics HW1 extra credit concerns: I know how Extra Credit works. Canvas doesn’t. HW2 due. Last day to submit with late days is tonight. HW3 out, topic is hashing. See slides from last Wednesday and Friday (same slide deck) 2 CSE373: Data Structures & Algorithms

3 .Today’s Topic: Abstractions The ADTs we cover in class are important to know conceptually but “in real life”, they’ll be p rovided by libraries The key idea of an abstraction arises all the time Clients do not know how it is implemented Clients do not need to know Clients cannot “break the abstraction” no matter what they do 3 CSE373: Data Structures & Algorithms

4 .Client v s. Implementer Provide a reusable interface without revealing implementation You’ve been practicing this throughout 143 already More difficult than it sounds due to aliasing and field- assignment (topic for today) We study concepts it in terms of ADTs instead of particular implementations in this class Will use priority queues as our example in this lecture , but any ADT would do 4 CSE373: Data Structures & Algorithms

5 .Recall the abstraction Clients: “not trusted by ADT implementer” Can perform any sequence of ADT operations Can do anything type-checker allows on any accessible objects 5 CSE373: Data Structures & Algorithms Implementer: Should document how operations can be used and what is checked (raising appropriate exceptions) E.g., parameter for method x not null If used correctly, correct priority queue for any client Client “cannot see” the implementation E.g., binary min heap n ew PQ(…) insert(…) deleteMin (…) isEmpty ()

6 .Review: commenting Let’s practice our skills with the Client vs Implementer abstraction, through commenting (look at code) 6 CSE373: Data Structures & Algorithms

7 .Commenting exercise: takeaways private comments for other coders looking at your file all public functionality should be commented for clients of your class implementation details should not be in public comments determine the line of abstraction, make sure you’re not giving implementation details over that line 7 CSE373: Data Structures & Algorithms

8 .Coding Abstractions: our example A priority queue with to-do items, so earlier dates “come first ” 8 CSE373: Data Structures & Algorithms public class ToDoItem { … // some private fields (date, description) public void setDate (Date d ) {…} public void setDescription (String d ) {…} … // more methods } public class Date { … // some private fields (year, month, day) public int getYear () {…} public void setYear ( int y ) {…} … // more methods } // c ontinued next slide…

9 .Coding Abstractions: our example A priority queue with to-do items, so earlier dates “come first ” 9 CSE373: Data Structures & Algorithms public class ToDoPQ { … // some fields (array, size, …) public ToDoPQ () {…} void insert ( ToDoItem t ) {…} ToDoItem deleteMin () {…} boolean isEmpty () {…} } public class ToDoItem { … } public class Date { … }

10 .A mistake we taught you in 143 Can you think of some more client code that might break the ToDoPQ ? 10 CSE373: Data Structures & Algorithms public class ToDoPQ { // other fields public ToDoItem [] heap ; / / methods public ToDoPQ () {…} void insert ( ToDoItem t ) {…} } // client code: pq = new ToDoPQ () ;

11 .A mistake we taught you in 143 Why we trained you to “mindlessly” make fields private : 11 CSE373: Data Structures & Algorithms Today’s lecture: private does not solve all your problems ! public class ToDoPQ { … // other fields public ToDoItem [] heap ; // problem! public ToDoPQ () {…} void insert ( ToDoItem t ) {…} … } // client: pq = new ToDoPQ (); pq.heap = null; pq.insert (…); // likely exception

12 .Less obvious mistakes 12 CSE373: Data Structures & Algorithms public class ToDoPQ { … // all private fields public ToDoPQ () {…} void insert ( ToDoItem i ) {… } ToDoItem deleteMin () {… } … } // client: ToDoPQ pq = new ToDoPQ (); ToDoItem i = new ToDoItem (…); pq.insert ( i ); ... Can you think of some more client code that might break the ToDoPQ ?

13 .Less obvious mistakes 13 CSE373: Data Structures & Algorithms public class ToDoPQ { … // all private fields public ToDoPQ () {…} void insert ( ToDoItem i ) {… } // potential problem ToDoItem deleteMin () {… } // potential problem … } // client: ToDoPQ pq = new ToDoPQ (); ToDoItem i = new ToDoItem (…); pq.insert ( i ); i.setDescription (“some different thing”); pq.insert ( i ); // same object after update x = deleteMin (); // x’s description??? y = deleteMin (); // y’s description???

14 .Aliasing and mutation Client was able to update something inside the abstraction because client had an alias to it! It is too hard to reason about and document what should happen, so better software designs avoid the issue! 14 CSE373: Data Structures & Algorithms pq h eap: size: 1 … date: d escription: “…” year: … month: … … i

15 .More bad clients 15 CSE373: Data Structures & Algorithms ToDoPQ pq = new ToDoPQ (); ToDoItem i1 = new ToDoItem (…); // year 2013 ToDoItem i2 = new ToDoItem (…); // year 2014 pq.insert (i1); pq.insert (i2); i1.setDate(…); // year 2015 x = deleteMin (); What is wrong with this code? What is the date of the ToDoItem stored in variable x?

16 .More bad clients 16 CSE373: Data Structures & Algorithms ToDoPQ pq = new ToDoPQ (); ToDoItem i1 = new ToDoItem (…); // year 2013 ToDoItem i2 = new ToDoItem (…); // year 2014 pq.insert (i1); pq.insert (i2); i1.setDate(…); // year 2015 x = deleteMin (); // stores the data for i1, but the date is now in year 2015 What is wrong with this code? What is the date of the ToDoItem stored in variable x?

17 .More bad clients 17 CSE373: Data Structures & Algorithms pq h eap: size: 2 … date: d escription: “…” year: … month: … … i1 i2 date: d escription: “…” year: … month: … …

18 .More bad clients 18 CSE373: Data Structures & Algorithms pq = new ToDoPQ (); ToDoItem i1 = new ToDoItem (…); pq.insert (i1); i1.setDate( null ); ToDoItem i2 = new ToDoItem (…); pq.insert (i2) ; What is wrong with this client code? What happens whe n you compare the dates of i1 and i2 in order to do percolateUp when inserting?

19 .More bad clients 19 CSE373: Data Structures & Algorithms pq = new ToDoPQ (); ToDoItem i1 = new ToDoItem (…); pq.insert (i1); i1.setDate( null ); ToDoItem i2 = new ToDoItem (…); pq.insert (i2); // NullPointerException Get exception inside data-structure code even if insert did a careful check the first time that the date in the ToDoItem is not null Bad client later invalidates the check

20 .The general fix Clients can’t be trusted with pointers to your data. Avoid aliases into the internal data (the “red arrows”) by copying objects as needed Do not use the same objects inside and outside the abstraction because two sides do not know all mutation (field-setting) that might occur A first attempt: 20 CSE373: Data Structures & Algorithms public class ToDoPQ { … void insert ( ToDoItem i ) { ToDoItem internal_i = i ; } }

21 .Must copy the object Notice this version accomplishes nothing Still the alias to the object we got from the client : second attempt: 21 CSE373: Data Structures & Algorithms public class ToDoPQ { … void insert ( ToDoItem i ) { ToDoItem internal_i = new ToDoItem ( i.date,i.description ); … // use only the internal object } } public class ToDoPQ { void insert ( ToDoItem i ) { ToDoItem internal_i = i ; … // internal_i refers to same object } }

22 .Copying works… 22 CSE373: Data Structures & Algorithms ToDoItem i = new ToDoItem (…); pq = new ToDoPQ (); pq.insert ( i ); i.setDescription (“some different thing”); pq.insert ( i ); x = deleteMin (); y = deleteMin (); pq h eap: size: 1 … date: d escription: “…” i date: d escription: “…” year: … month: … …

23 .Didn’t do enough copying yet 23 CSE373: Data Structures & Algorithms Date d = new Date(…) ToDoItem i = new ToDoItem ( d,“buy beer”); pq = new ToDoPQ (); pq.insert ( i ); d.setYear (2015); … pq h eap: size: 1 … date: d escription: “…” year: … month: … … i date: d escription: “…”

24 .Deep copying (copy all the way down) What if the client has an alias to i.date ? Then depending on the implementation for ToDoItem , they may still have a reference to internal_i.date or internal_i.description . 24 CSE373: Data Structures & Algorithms public class ToDoPQ { void insert ( ToDoItem i ) { ToDoItem internal_i = new ToDoItem ( i.date,i.description ); … // use only the internal object } } public class ToDoItem { public ToDoItem ( Date d, String desc ) { this.d = new Date( d.year , d.month , d.day ); this.desc = desc ; } }

25 .25 CSE373: Data Structures & Algorithms If you own all the objects being used, you can control the copying at every level. If you don’t, then to deep copy, you have to copy everything.

26 .Deep copying (copy all the things) For copying to work fully, usually need to also make copies of all objects referred to (and that they refer to and so on…) All the way down to int , double , String , … Called deep copying (versus our first attempt shallow-copy ) Rule of thumb: Deep copy of things passed into abstraction 26 CSE373: Data Structures & Algorithms public class ToDoPQ { … void insert ( ToDoItem i ) { ToDoItem internal_i = new ToDoItem ( new Date(…) , i.description ); … // use only the internal object } }

27 .Constructors take input too General rule: Do not “trust” data passed to constructors Check properties and make deep copies Example: Floyd’s algorithm for buildHeap should: Check the array (e.g., for null values in fields of objects or array positions) Make a deep copy: new array, new objects 27 CSE373: Data Structures & Algorithms public class ToDoPQ { // a second constructor that uses // Floyd’s algorithm, but good design // deep-copies the array (and its contents) void PriorityQueue ( ToDoItem [] items ) { … } }

28 .That was copy-in, now copy-out… So we have seen: Need to deep-copy data passed into abstractions to avoid pain and suffering Next: Need to deep-copy data passed out of abstractions to avoid pain and suffering (unless data is “new” or no longer used in abstraction) Then: If objects are immutable (no way to update fields or things they refer to), then copying unnecessary 28 CSE373: Data Structures & Algorithms

29 .deleteMin is fine Does not create an external alias because object returned is no longer part of the data structure Returns an alias to object that was in the heap, but now it is not, so conceptual “ownership” “transfers” to the client 29 CSE373: Data Structures & Algorithms public class ToDoPQ { … ToDoItem deleteMin () { ToDoItem ans = heap[0]; … // algorithm involving percolateDown return ans ; }