CS231 lecture notes, Fall 1998 Week 12, Monday Today ----- 1) design issues 2) hw8 solutions Some high-level choices when you design an object to implement an ADT 1) Exogenous vs. endogenous 2) Sentinel objects 3) Object methods or class methods 4) Exogenous vs. endogenous ------------------------ endogenous = ADT specialized to deal with specific data type exogenous = generic ADT manipulating separately-defined objects Advantages of endogenous 1) fewer class definitions 2) sometimes simpler, or at least more obvious 3) generally not difficult to transform from one type to another Advantages of exogenous 1) possibility of reusing generic ADT without modification 2) better modularity 3) better mapping between concepts and program structure 4) some practical advantages (e.g. swapping by reference rather than swapping data) Sentinel objects ---------------- sentinel \Sen"ti*nel\, n. [F. sentinelle (cf. It. sentinella); probably originally, a litle path, the sentinel's beat,, and a dim. of a word meaning, path; cf. F. sente path. L. semita; and OF. sentine, sentele, senteret, diminutive words. Cf. Sentry.] 1. One who watches or guards; specifically (Mil.), a soldier set to guard an army, camp, or other place, from surprise, to observe the approach of danger, and give notice of it; a sentry. 1) The linked list implementations we looked at used a List node as a sentinel for a set of ListNode objects 2) The Heap implementation we are using is "unguarded". A Heap is just a bunch of Heap objects that point to each other Advantages of sentinel 1) sometimes you can avoid special cases like removing the last element from a set 2) you can divide methods into "things that act on a particular member of a set," and "things that act on the entire set". 3) sometimes the sentinel reduces the confusion between a set member standing for itself and a set member that provides a handle on the rest of the set Advantages of no sentinel 1) fewer class definitions 2) the ambiguity mentioned in #3 above is useful, so we might not want to eliminate it. For example, in our Heap implementation, the children of a Heap are Heaps themselves. In the List implementation, the sublists were ListNodes, not Lists. 3) facilitate recursive methods by preserving recursive structure Object methods vs. class methods -------------------------------- 1) Object methods fit the object-oriented model of Objects as agents the respond to requests/messages 1a) object methods a sometimes shorter, since they allow unqualified references to the instance variables 2) Class methods are often deprecated as a throwback to more procedural thinking, which is regarded as primitive 3) Sometimes a class method makes the relationship between the arguments clearer (as in addition) 4) In Java, it is sometimes awkard to write recursive methods as Object methods, because you cannot invoke a method on a null object. Ultimately, this is not really a design issue, it is a syntax issue. Within a class definition there are often both types of methods, although I am finding that in my own programs I tend to choose one or the other for the vast majority. HW8 solutions ------------- INSERT ---------------------------------------------------------- public static Heap insert (Heap heap, int value) { // traverse the tree and assign ranks to everyone labelRank (heap); // then do the actual insertion return insertHelp (heap, value); } public static Heap insertHelp (Heap heap, int value) { // to add a new element to a null heap, just create a new object if (heap == null) { return new Heap (value, null, null); } // figure out which side is going to get the new object int choice = LEFT; if (heap.left == null) { choice = LEFT; } else if (heap.right == null) { choice = RIGHT; } else if (heap.left.rank > heap.right.rank) { choice = RIGHT; } // call insertHelp recursively on the appropriate child, // then check for the heap property when the child returns. if (choice == LEFT) { heap.left = insertHelp (heap.left, value); if (heap.value < heap.left.value) { swapContents (heap, heap.left); } } else { heap.right = insertHelp (heap.right, value); if (heap.value < heap.right.value) { swapContents (heap, heap.right); } } return heap; } ---------------------------------------------------------- Style notes: 1) I hate names like insertHelp 2) common idiom: figure out which of two choices and put result into a flag variable 3) why does labelRank record everyone's rank at once rather than calculate it on demand? advantage -- performance disadvantage -- weird dependency (have to make sure ranks are up to date before invoking insertHelp) REMOVE ---------------------------------------------------------- public static Heap remove (Heap heap) { if (heap == null) return null; // put the primary return value into removedValue removedValue = heap.value; // then fix the broken heap return reheapify (heap); } public static Heap reheapify (Heap heap) { // reheapify by recursively removing an element from // the larger of the two children int larger; // if there are no children, return an empty heap if (heap.left == null && heap.right == null) return null; // larger indicates which of the children is larger if (heap.left == null) { larger = RIGHT; } else { larger = LEFT; if (heap.right != null && heap.right.value > heap.left.value) { larger = RIGHT; } } // steal a value from the larger child and reheapify that child if (larger == LEFT) { heap.value = heap.left.value; heap.left = reheapify (heap.left); } else { heap.value = heap.right.value; heap.right = reheapify (heap.right); } return heap; } ---------------------------------------------------------- Style notes: 1) removedValue is a class variable now, to solve Sam's problem 2) variable flag idiom again MAIN ---------------------------------------------------------- public static void main (String[] args) { Heap heap = null; // generate 100 items with random keys and put them in the Heap for (int i = 0; i<100; i++) { int x = (int) (Math.random() * 100); heap = insert (heap, x); System.out.println ("Inserting " + x); } // remove all the items from the Heap; they should be in order while (heap != null) { heap = remove (heap); System.out.println ("Removing " + removedValue); } } ---------------------------------------------------------- Style notes: 0) why don't we use a constructor to create a heap? (another disadvantage of non-sentinel objects) 1) how do we know when the heap is empty? 2) how does remove indicate an error?