MSIM 602 Spring 2007 Computer Science Concepts for Modeling

MSIM 602 Spring 2007 Computer Science Concepts for Modeling & Simulation Dale, Chapter 6 Lists, Binary Trees Dr. C. M. Overstreet Computer Science Department Old Dominion University

Chapter 6: The List ADT 6.1 – Comparing Objects Revisited 6.2 – Lists 6.3 – Formal Specification 6.4 – Array-Based Implementation 6.5 – Applications: Poker, Golf, and Music 6.6 – The Binary Search Algorithm 6.7 – Reference-Based Implementations 6.8 – Storing Objects and Structures in Files

6.1 Comparing Objects Revisited Many list operations require us to compare the values of objects, for example – check whether a given item is on our to-do list – insert a name into a list in alphabetical order – delete the entry with the matching serial number from a parts inventory list Therefore we need to understand our options for such comparisons.

Using the comparison ( ) operator

Using the equals method Since equals is exported from the Object class it can be used with objects of any Java class. For example, If c1 and c2 are objects of the class Circle, then we can compare them using c1.equals(c2) But this method, as defined in the Object class, acts much the same as the comparison operator. It returns true if and only if the two variables reference the same object. However, we can redefine the equals method to fit the goals of the class.

Using the equals method A reasonable definition for equality of Circle objects is that they are equal if they have equal radii. To realize this approach we define the equals method of our Circle class to use the radius attribute: public boolean equals(Circle circle) // Precondition: circle ! null // // Returns true if the circles have the same radius, // otherwise returns false. { if (this.radius circle.radius) return true; else return false; }

Ordering objects In addition to checking objects for equality, there is another type of comparison we need. To support a sorted list we need to be able to tell when one object is less than, equal to, or greater than another object. The Java library provides an interface, called Comparable, which can be used to ensure that a class provides this functionality.

The Comparable Interface The Comparable interface consists of exactly one abstract method: public int compareTo(Object o); // Returns a negative integer, zero, or a positive // integer as this object is less than, equal to, // or greater than the specified object. The compareTo method returns an integer value that indicates the relative "size" relationship between the object upon which the method is invoked and the object passed to the method as an argument.

Using the Comparable Interface Objects of a class that implements the Comparable interface are called Comparable objects. To ensure that all elements placed on our sorted list support the compareTo operation, we require them to be Comparable objects. For example, see the definition of compareTo for our Circle class on the next slide

A compareTo Example public int compareTo(Object o) // Precondition: o ! null // // Returns a negative integer, zero, or a positive integer as this object // is less than, equal to, or greater than the parameter object. { if (this.radius ((Circle)o).radius) return -1; else if (this.radius ((Circle)o).radius) return 0; else return 1; } Note that the equals method and the compareTo method of our Circle class are compatible with each other. To simplify discussion we sometimes refer to the attribute, or combination of attributes, of an object used by the compareTo method to determine the logical order of a collection as the key of the collection.

6.2 Lists List A collection that exhibits a linear relationship among its elements Linear relationship Each element except the first has a unique predecessor, and each element except the last has a unique successor Size The number of elements in a list; the size can vary over time

Varieties of Lists Unsorted list A list in which elements are placed in no particular order; the only relationship between data elements is the list predecessor and successor relationships Sorted list A list that is sorted by some property of its elements; there is an ordered relationship among the elements in the list, reflected by their relative positions Indexed list A list in which each element has an index value associated with it

Assumptions for our Lists Our lists are unbounded We allow duplicate elements on our lists We do not support null elements Other than prohibiting null elements, we have minimal preconditions on our operations Our sorted lists are sorted in increasing order, as defined by the compareTo operation applied to list objects The equals and compareTo methods of our sorted list elements are consistent In our indexed lists, the indices in use at any given time are contiguous, starting at 0

6.3 Formal Specification We define a small, but useful, set of operations for use with our lists. We capture the formal specifications of our List ADT using the Java interface construct. We pull all the common list method descriptions together into a single interface, called ListInterface. We extend the ListInterface with three separate interfaces, one for each of our list variations. Our intent is that classes should implement one of these latter three interfaces, and therefore by extension, implement the ListInterface.

List Iteration Because a list has a linear relationship among its elements, we can support iteration through a list. Iteration means that we provide a mechanism to process the entire list, element by element, from the first element to the last element. Each of our list variations provides the operations reset and getNext to support this activity.

List Operations All three of our list variations provide the following operations: – size: Returns the number of elements on the list. – contains: Passed an Object argument and returns a boolean indicating whether the list contains an equivalent element. – remove: Passed an Object argument and, if an equivalent element exists on the list, removes one instance of that element. Returns a boolean value indicating whether an object was actually removed. – get: Passed an Object argument, it returns an equivalent object if one exists on the list. If not, returns null. – toString: Returns a nicely formatted string representing the list. – reset: Initializes the list. Sets the current position (the position of the next element to be processed) to the first element on the list. – getNext: Returns the next element, and updates the current position.

List Operations Our Unsorted List also supports the operation – add: Passed an Object argument that it adds to the list Our Sorted List also supports the operation – add: Passed a Comparable argument that it adds to the list

List Operations Our Indexed List also supports the operations – add: Passed an Object element and an integer index it adds the element to the list at the position index – set: Passed an Object element and an integer index it replaces the current element at the position index with the argument element – get: Passed an integer index it returns the element from the list at that position – indexOf: Passed an Object element it returns the index of the first such matching element (or -1) – remove: Passed an integer index it removes the element at that index Each method that accepts an index as an argument throws an exception if the index is invalid.

UML Diagram of our List Interfaces

Code Section UnsortedListInterface list1 new ArrayUnsortedList(); list1.add("Wirth"); list1.add("Dykstra"); list1.add("Dahl"); list1.add("Nygaard"); SortedListInterface list2 new ArraySortedList(); list2.add("Wirth"); list2.add("Dykstra"); list2.add("Dahl"); list2.add("Nygaard"); IndexedListInterface list3 new ArrayIndexedList(); list3.add(0, "Wirth"); list3.add(0, "Dykstra"); list3.add(2, "Dahl"); list3.add(1, "Nygaard"); System.out.print("Unsorted "); System.out.println(list1); System.out.print("Sorted "); System.out.println(list2); System.out.print("Indexed "); System.out.println(list3); Example Use Output Unsorted List: Wirth Dykstra Dahl Nygaard Sorted List: Dahl Dykstra Nygaard Wirth Indexed List: [0] Dykstra [1] Nygaard [2] Wirth [3] Dahl

6.4 Array-Based Implementation Basic Approach:

Adding/Removing from middle

The List Class Should only contain methods whose implementation is independent of the type of list The implementation of the List class is straightforward

The ArrayUnsortedList Class Implements the UnsortedListInterface Extends the List class with the methods needed for creation and use of an unsorted list: – the add method: check to see if the array needs to be enlarged, handle that if it does, and then add the new element to the end of the list. Additionally, the remove method can be improved:

The ArraySortedList Class Implements the SortedListInterface Extends the List class with the methods needed for creation and use of a sorted list: – the add method: check to ensure that there is room for it, invoking our enlarge method if there is not. find the place where the new element belongs. create space for the new element. put the new element in the created space.

The Sorted List add method public void add(Comparable element) // Adds element to this list. { Comparable listElement; int location 0; boolean moreToSearch; if (numElements list.length) enlarge(); moreToSearch (numElements 0); while (moreToSearch) { listElement (Comparable)list[location]; if (listElement.compareTo(element) 0) { location ; moreToSearch (location numElements); } else moreToSearch false; } for (int index numElements; index location; index--) list[index] list[index - 1]; list[location] element; numElements ; }

Implementing ADTs “by Copy” or “by Reference” When designing an ADT we have a choice about how to handle the elements—“by copy” or “by reference.” – By Copy: The ADT manipulates copies of the data used in the client program. Making a valid copy of an object can be a complicated process. – By Reference: The ADT manipulates references to the actual elements passed to it by the client program. This is the most commonly used approach and is the approach we use throughout this textbook.

“By Copy” Notes Valid copies of an object are typically created using the object's clone method. Classes that provide a clone method must indicate this to the runtime system by implementing the Cloneable interface. Drawbacks: – Copy of object might not reflect up-to-date status of original object – Copying objects takes time, especially if the objects are large and require complicated deep-copying methods. – Storing extra copies of objects also requires extra memory.

“By Reference” Notes Because the client program retains a reference to the element, we say we have exposed the contents of the collection ADT to the client program. The ADT allows direct access to the individual elements of the collection by the client program through the client program’s own references. Drawbacks: – We create aliases of our elements, therefore we must deal with the potential problems associated with aliases. – This situation is especially dangerous if the client program can use an alias to change an attribute of an element that is used by the ADT to determine the underlying organization of the elements – for example if it changes the key value for an element stored in a sorted list.

An Example The next three slides show the results of a sequence of operations when each of the two approaches is used to store a sorted list: – We have three objects that hold a person’s name and weight (Slide 1) – We add the three objects onto a list that sorts objects by the variable weight – We transform one of the original objects with a diet method, that changes the weight of the object

Example Step 1: The Three Objects By Copy Approach By Reference Approach

Example Step 2: Add Objects to List By Copy Approach By Reference Approach

Example Step 3: S1.diet(-105) By Copy Approach Problem: List copy is out of date By Reference Approach Problem: List is no longer sorted

Which approach is better? That depends. If processing time and space are issues, and if we are comfortable counting on the application programs to behave properly, then the “by reference” approach is probably best. If we are not too concerned about time and space (maybe our list objects are not too large), but we are concerned with maintaining careful control over the access to and integrity of our lists, then the “by copy” approach is probably best. The suitability of either approach depends on what the list is used for.

The ArrayIndexedList Class Implements the IndexedListInterface Extends the List class with the methods needed for creation and use of an indexed list: – – – – – void add(int index, Object element) void set(int index, Object element) Object get(int index) int indexOf(Object element) Object remove(int index) The implementations are straightforward Overrides the toString method of the List class

6.5 Applications: Poker, Golf, and Music We look at three applications, to see how our list implementations can be used to help solve problems. – Poker: Our program simulates poker hands to help verify formal analysis – Golf: Rank players based on their scores (demonstrates use of the Comparable interface) – Music: Organize a collection of songs

Code Examples Look at the code for the Examples. Note how each problem is solved using the most suitable type of list.

6.6 The Binary Search Algorithm

Searching in a phone book Suppose we are looking for “David” in a phone book We open the phone book to the middle and see that the names there begin with M – M is larger than (comes after) D – We can now limit our search to the section that contains A to M We turn to the middle of the first half and see that the names there begin with G – G is larger than D – We can now limit our search to the section that contains A to G We turn to the middle page of this section, and find that the names there begin with C – C is smaller than D – We can now limit our search to the section that contains C to G And so on, until we are down to the single page that contains the name “David.”

Searching for “bat” in a sorted array

protected void find(Object target) { int first 0; int last numElements - 1; boolean moreToSearch (first last); int compareResult; Comparable targetElement (Comparable)target; The revised find method found false; while (moreToSearch && !found) { location (first last) / 2; compareResult targetElement.compareTo(list[location]); if (compareResult 0) found true; else if (compareResult 0) // target element is less than element at location { last location - 1; moreToSearch (first last); } else // target element is greater than element at location { first location 1; moreToSearch (first last); } } }

Recursive Binary Search Consider this informal description of the binary search algorithm: – To search a list, check the middle element on the list – if it's the target element you are done, if it's less than the target element search the second half of the list, otherwise search the first half of the list. There is something inherently recursive about this description: – We search the list by searching half the list. – The solution is expressed in smaller versions of the original problem: if the answer isn’t found in the middle position, perform a binary search (a recursive call) to search the appropriate half of the list (a smaller problem).

protected void recFind(Comparable target, int fromLocation, int toLocation) { if (fromLocation toLocation) // Base case 1 found false; else { int compareResult; location (fromLocation toLocation) / 2; compareResult target.compareTo(list[location]); if (compareResult 0) // Base case 2 found true; else if (compareResult 0) // target is less than element at location recFind (target, fromLocation, location - 1); else // target is greater than element at location recFind (target, location 1, toLocation); } } The recursive find method protected void find(Object target) { Comparable targetElement (Comparable)target; found false; recFind(targetElement, 0, numElements - 1); }

Efficiency Analysis Maximum Number of Iterations Length Linear Search Binary Search 10 10 4 100 100 7 1,000 1,000 10 10,000 10,000 14

6.7 Reference-Based Implementation In this section we develop list implementations using references (links). We follow the same basic pattern of development here that we did when we developed list implementations using arrays. – Our reference-based implementations fulfill the interfaces we developed in Section 6.3. – We first combine all the methods whose referencebased implementations are common across our different list types into a single class, the RefList class, and then we extend that class with classes that complete the implementations.

Reference Based Lists As we did for our reference-based stacks and queues, we use the LLObjectNode class from the support package to provide our nodes. – the information attribute of a node contains the list element – the link attribute contains a reference to the node holding the next list element We maintain a variable, list, that references the first node on the list.

Reference Based Lists We'll implement both unsorted and sorted lists using the linked approach. We do not implement indexed lists. There is no simple way to efficiently implement the add, set, get, and remove operations involving index arguments.

The RefList Class Includes all the list methods that do not depend on whether the list is sorted The implementations of size, contains, get, toString, reset, and getNext are straightforward

The find method protected void find(Object target) { boolean moreToSearch; location list; found false; moreToSearch (location ! null); while (moreToSearch && !found) { if (location.getInfo().equals(target)) found true; else { previous location; location location.getLink(); moreToSearch (location ! null); } } } Sets a variable named previous - used by the RefList remove method.

The remove method To remove an element, we first find it using the find method, which sets the location variable to indicate the target element and sets the previous variable to a reference in the previous node. We can now change the link of the previous node to reference the node following the one being removed. Removing the first node must be treated as a special case because the main reference to the list (list) must be changed.

The remove method public boolean remove (Object element) // Removes an element e from this list such that e.equals(element) // and returns true; if no such element exists returns false. { find(element); if (found) { if (list location) list list.getLink(); // remove first node else previous.setLink(location.getLink()); // remove node at location numElements--; } return found; }

The RefUnsortedList Class Implements the UnsortedListInterface Extends the RefList with an add method Because the list is unsorted, and order of the elements is not important, we can just add new elements to the front of the list public void add(Object element) // Adds element to this list. { LLObjectNode newNode new LLObjectNode(element); newNode.setLink(list); list newNode; numElements ; }

The RefSortedList Class Implements the SortedListInterface Extends the RefList with an add method Adding an element to a reference-based sorted list requires three steps: 1. Find the location where the new element belongs 2. Create a node for the new element 3. Correctly link the new node into the identified location

1. Finding the location where the new element belongs To link the new node into the identified location, we also need a reference to the previous node. While traversing the list during the search stage, each time we update the location variable, we first save its value in a prevLoc variable: prevLoc location; location location.getLink();

2. Create a node for the new element instantiate a new LLObjectNode object called newNode, passing its constructor the new element for use as the information attribute of the node LLObjectNode newNode new LLObjectNode(element);

3. Correctly link the new node into the identified location We change the link in the newNode to reference the node indicated by location and change the link in our prevLoc node to reference the newNode: newNode.setLink(location); prevLoc.setLink(newNode);

Special case – location indicates first node of list In this case we do not have a previous node We must change the main reference to the list (list) if (prevLoc null) { // Insert as first node. newNode.setLink(list); list newNode; }

The add method The code for the add method is too long to fit on a slide. It can be found on page 426 of the textbook.

6.8 Storing Objects and Structures in Files Many programs need to save information between program runs Alternatively, we may want one program to save information for later use by another program In either case, the information is stored in files, which are the mechanism for permanently storing information on computers In this subsection we investigate approaches for saving and retrieving objects and structures using files, including Java’s serialization facilities

Saving Object Data in Text Files Any information we need to save can be represented by its primitive parts. As a very simple example, consider a Song object which has two instance variables: – protected String name; – protected int duration; A song is not a “primitive” object, but when broken into its constituent parts its information consists of a String and an int. Both of these can be saved as strings.

import java.io.*; import support.*; public class SaveSong { private static PrintWriter outFile; public static void main(String[] args) throws IOException { Song song1 new Song("Penny Lane", 2, 57); outFile new PrintWriter(new FileWriter("song.txt")); outFile.println(song1.getName()); outFile.println(song1.getDuration()); outFile.close(); } } When this program is executed, it creates the song.txt file: Penny Lane 177

When we need to retrieve the Song object, we just reverse the process: read the strings, and reconstruct the song. import java.io.*; import java.util.*; import support.*; public class GetSong { public static void main(String[] args) throws IOException { String name; int duration; FileReader fin new FileReader("song.txt"); Scanner songIn new Scanner(fin); name songIn.nextLine(); duration songIn.nextInt(); Song song2 new Song(name, duration); System.out.println("The name of the song is " song2.getName()); System.out.println("The duration of the song is " song2.getDuration()); } }

Serialization of Objects Transforming objects into strings and back again is a lot of work for the programmer. Fortunately, Java provides another way to save objects. This approach is called serializing the object. Before seeing how to serialize objects, we must learn about a new interface and two support classes.

Support Constructs We can write objects using the writeObject method of the ObjectOutputStream class. – To set up the output of serialized objects to the file objects.dat using the stream variable out, we write ObjectOutputStream out new ObjectOutputStream(new FileOutputStream("objects.dat")); We can read objects using the readObject method of the ObjectInputStream class. – To set up reading from the same file, but this time using the variable in, we code ObjectInputStream in new ObjectInputStream(new FileInputStream("objects.dat"));

The Serializable interface Any class whose objects we plan to serialize must implement the Serializable interface. This interface has no methods! It marks a class as potentially being serialized for I/O, so that the Java runtime engine knows to convert references as needed on output or input of class instances. To make our objects serializable, we simply state that their class implements the interface.

Example SerSong.java (page 430) is a version of our Song class that implements the Serializable interface SaveSerSong.java (page 431) is an application that creates a SerSong object and saves it to a file GetSerSong.java (page 432) is an application that retrieves that SerSong object and uses it.

Serializing Structures The power of Java’s serialization tools really becomes evident when dealing with data structures For example, we can save or restore an entire array of SerSong objects with a single statement To save the array: SerSong[] songs new SerSong[100]; . out.writeObject(songs); And to retrieve it later, perhaps from another program: SerSong[] laterSongs (SerSong[])in.readObject();

Serializing Structures What is even more impressive is that Java’s serialization works for linked structures. We can save an entire linked list using a single writeObject statement, and later restore it using a single readObject statement. This approach works even for the non-linear reference-based structures we study in later chapters. The tree and graph structures retain both their information and their structure using serialization.

Application: Song Lists For an example of serialization of a structure, we create an application that – – – – – allows us to enter song titles and lengths displays song information saves the song information song indexes start at 1 if the user provides an illegal index for a song, instead of throwing an exception the program inserts the song at the end of the song list – the user can provide a name for the list of songs

Code and Demo Look at the code for the support class SerSongList.java and the application SerSongsApp.java.