CIS 4930 Section 0841X

Object-Oriented Programming

Assignment 1 Solution

Variable Length Array

Note: there is ambiguity regarding what ordered means in this context. It can be interpreted to mean the objects in the array are in sorted order, and it can also be interpreted to mean that the objects in the array are ordered because each has an index associated with it, the indices are ordered, and you can retrieve successive objects in the array by using successive indices. Your answers to the following depend on which interpretation you made.

• append: If you assumed the objects were in sorted order, then no. Otherwise, given i objects in the array, place the object at position i+1, extending the length of the array if necessary.

• copy: Copies an array by successively copying each object into a new array.

• count: Returns the number of objects in an array.

• delete: Delete an object and shift successive objects up one position. Replacing the deleted object with a null entry is bad practice, but at least you were considering what to do with the empty array slot.

• index: Given i, return the object at position i in the array.

• intersect: If you assumed the objects were in sorted order, then given two arrays, return an array containing objects common to both. Actually, for completeness, we'd want to handle being given an empty array(s), and return an empty array (representative of the null set). If you didn't assume the objects were in sorted order, then no, as supporting intersect would make much less sense.

• insert: If you assumed the objects were in sorted order, then it's ok if the object's position is determined by the array's ordering relation (position shouldn't be an argument to insert); add the object to the "end" of the array followed by reordering the array's objects, extending the array if necessary. If you didn't assume the objects were in sorted order, then given i, insert the object at position i in the array, extending the array if necessary.

• update: If you didn't assume the objects were in sorted order, ok; do as insert, overwriting what's at position i. If you did assume the objects were in sorted order, it's ok if you stated the part(s) of objects used by the ordering relation aren't updated, or if you reordered the array after the update.

Symbol Table

Note: Carefully consider the description of a symbol table given above. We're not just considering a symbol table for a compiler or assembler; we're considering all tables that map text keywords into descriptors (which could describe anything). This could also be referred to as an associative array using text keys. It would be a mistake to consider one possible application for a class when considering its behavior instead of what operations make sense for a class per se.

• append: No, the position of a descriptor in the symbol table shouldn't matter outside the scope of the symbol table; descriptors are accessed from outside that scope with their associated keywords.

• copy: Sure, but why? Well, if you could copy a symbol table to some secondary storage medium and restore it to memory later, it'd be a persistent symbol table. So, yes.

• count: Returns the number of descriptors in a symbol table. There are any number of reasons why you might want this information. It could also be used internally (e.g. to compute a number of entries/number of collisions ratio).

• delete: Given a keyword, remove its associated descriptor from a symbol table.

• index: Given a keyword, return (a reference to) its associated descriptor in a symbol table. The keyword indicates the object's position.

• intersect: Given two symbol tables, return a symbol table containing descriptors common to both symbol tables.

• insert: Ok if position is determined from the keyword associated with the descriptor to be inserted (position argument should be the keyword).

• update: Given a keyword and a new descriptor, replace the descriptor in the symbol table associated with the keyword with the new descriptor. If the keyword does not have a descriptor associated with it in the symbol table, you could do an insert or return an error, depending on your assumptions.

Set

Note: Neither append, insert, or update is truly right for a set class. What we really want is union. We can use union to combine sets, and we can use it to add objects to sets (because an object is a singleton set, after all).

• append: This comes closer than insert or update if you note that adding an object to the "end" of the collection doesn't matter as the collection is unordered. This is sure to annoy someone using your class library, however. Ensure that the set resulting from the append won't contain any duplicate objects.

• copy: Copies a set by copying all the objects in the set into a new set.

• count: Returns the number of objects in a set.

• delete: Removes an object from a set.

• index: No, this is an unordered collection.

• intersect: Given two sets, return a set containing objects common to both. This clearly needs to work on empty sets.

• insert: No, this is an unordered collection. Stating insert doesn't take position as an argument isn't enough, as position of an object within a set is completely arbitrary.

• update: Only if you ensure that there wouldn't be duplicate objects in the set after the update. You could also describe update as allowing you to change the state of objects inside the set, without changing that part of an object which makes it unique within the set.