[Solved] CMPT280 Assignment5 Restrictions of ADTs
5.0
1 customer review
Digital download
Digital download
$25.00
- Availability
- In stock
- Checkout
- One item
Need a hand?
Message us on WhatsApp for payment or download support.
Restrictions of ADTs
We have seen how we can extend the functionality of a data structure that we already have implemented by creating a subclass using the extends keyword in Java. This allows us to take an existing data structure class and add new functionality or modify existing ADT functionality (e.g. extension of ArrayedTree280 to ArrayedHeap280), or to create a specialization of a more generic ADT (e.g. extension of LinkedSimpleTree280<String> to ExpressionTree). Another ADT programming paradigm is restriction. Restriction is used to make an existing ADT appear to be another ADT that has less functionality. Consider the following example. Suppose we need a Stack ADT, but our data structure library, whatever it is, doesnt have one. Further suppose that our data structure library does have a list ADT which allows insertions and deletions from either end of the list. Such a list has more than the necessary functionality of a stack. A stack is really just a list where we can only add (push) and remove (pop) items at one end. We could just use the list itself as a stack, trusting ourselves to only add and remove at one end. But this does not eliminate the possibility that the stack could be used in ways that a stack should not be used when all we really need is a stack. Perhaps another programmer comes along and doesnt realize that you were using a list to get the behaviour of a stack and does something very un-stack-like to the list without realizing it! What is really needed in this situation is an ADT that has less functionality than the one we already have. We cant get that by extending the existing list ADT, but we can use the idea of restriction to make the list appear to the outside world as nothing more than a stack! The solution is to restrict the list class by writing a stack class which includes a list as an instance variable, and methods that consist of only the interface for a stack. In other words, the list is the internal data structure for the stack ADT, but the public operations for the ADT consist of only those for a stack. These methods then translate the stack operations into the corresponding list operations, thus resulting in a new class that looks exactly like a stack to the outside world, but implements the stack using a list.[1]If you take a look at the Stack280 class in lib280, youll see that this is precisely what Stack280 does. Its methods translate stack operations into operations on an internal list. Implementing this restriction is far less work than writing a new linked or array-based stack class from scratch. You will practice the concept of restriction in Question 1, below.1.2 Hash Tables
In this question you will work with an implementation of a chained hash table. lib280-asn5 contains the class KeyedChainedHashTable280. You will use this class to solve a problem. KeyedChainedHashTable280 is an example of a keyed dictionary where each item is associated with a unique key. A keyed hash table computes the hash of an item from only the items key, even though the item itself might contain other data. Additional background and details about chained hash tables are part of Lecture 15 and will be a component of this weeks tutorials.2 Your Tasks
Question 1 : Recall from assignment 2 that a priority queue is a queue in which there is a numeric priority associated with every item in the queue. The item at the head of a priority queue is always the item with highest priority. If we think about it, a heap actually has some of the functionality of the priority queue ADT we specified in assignment 2. We can insert items into a heap which are kept organized by their size (equivalent to enqueue!), and a heap always dispenses the largest item (equivalent to getting the item at the front of the priority queue), and it allows us to delete the largest item (equivalent to a dequeue!). The problem we would like to solve is to implement the priority queue ADT specification from assignment 2 by re-using as much of our existing code as we can. You can find the priority queue specification in the appendix of this document. In Assignment 4 we wrote a class ArrayedHeap280 (the instructors ArrayedHeap280 is included in lib280-asn5), which has some of the functionality we need for a priority queue. But we cannot just extend it because:- it has methods that a priority queue ADT doesnt have, like itemExists;
- it has methods that have the right functionality, but the wrong name, like deleteItem, which, for our priority queue, is called deleteMax; and
- it doesnt have an iterator, which we need in order to determine the item with the smallest priority (we need to be able to inspect all of the items in the heap to find the smallest one without moving the internal cursor away from the root of the heap).
- Write a class ArrayedBinaryTreeIterator280 which extends ArrayedBinaryTreePostion280 and implements the LinearIterator280 interface. This will be an iterator for the ArrayedBinaryTree280 class. ArrayedBinaryTreeIterator280 should be fairly easy to implement since you can pretty much copy all of the methods required by the LinearIterator280 interface from
- Extend ArrayedHeap280 to a class IterableArrayedHeap280 and write the following methods in IterableArrayedHeap280:
- Add a deleteAtPosition method to delete a specific item in the heap (which need not be the root). The item to be deleted should be specified by passing a reference to an ArrayedBinaryTreeIterator280 object. The algorithm for this is just a slight modification of the heap deletion algorithm where you swap the item at the end of the array with the item to be deleted, and then swap it with its larger child until it is larger than both its children. This method should be very similar to deleteItem from ArrayedHeap280.
- Add a method to IterableArrayedHeap280 called iterator which returns a new ArrayedBinaryTreeIterator280 object for the tree.
- Write a class PriorityQueue280 which is a restriction (as defined in Section 2.1) of IterableArrayedHeap280 which implements the priority queue ADT specification given in the Appendix of this document. This means that PriorityQueue280 should have an IterableArrayedHeap280 as an instance variable, and it is in the heap that the queue items are stored.
- Name of the quest.
- Name of the area of the world in which the quest takes place.
- Recommended minimum character level that should attempt the quest.
- Recommended maximum character level that should attempt the quest.
- Complete the implementation of the QuestLog.keys() method. This method must return an array of the keys (i.e. the quest names) of each QuestLogEntry instance in the hash table. The keys may appear in the returned array in any order.
- Complete the implementation of the QuestLog.toString() method. This method should return a printable string consisting of the complete contents of all of the QuestLogEntry objects in the hash table in alphabetical order by the quest names, one per line. Here is an example string returned by toString() from a quest log containing four entries:
- Complete the implementation of the QuestLog.obtainWithCount() method. This method takes a quest name as input and returns a Pair280 object (found in lib280.base) which must contain the QuestLogEntry object from the quest log which matches the given quest name (if it exists) and the number of QuestLogEntry objects that were examined while searching for the desired one. The latter number must be present whether the quest name was found in the quest log or not.
| System.out.println(p.firstItem()); | // prints the integer 5 |
| System.out.println(p.secondItem()); | // the floating point number 42.0 |
- Now take a look at the main() program in QuestLog.java. As given, it already does the following things:
- Creates a new, empty QuestLog instance called hashQuestLog.
- Creates a new, empty OrderedSimpleTree280 instance (a binary search tree) called treeQuestLog that can hold items of type QuestLogEntry.
- A .csv file containing the data for a number of QuestLogEntry objects is opened, and read in, creating a QuestLogEntry instance for each quest, and adding each such instance to both both the hashQuestLog and treeQuestLog data structures.
- The complete contents of hashQuestLog and treeQuestLog are printed out using their respective toString() methods. Youll know when your Questlog.toString() method from part (b) is working when its output matches that of treeQuestLog.toStringInorder().
- List the reported averages that you recorded for each .csv input file in a table that looks something like this (filling in the rest of the table of course):
- If you had to choose a simple function (i.e. from the list of functions used in big-O notation) to characterize the behaviour of the the average number of items examined per query for the hashed quest log as the number of quests (n) in the log increases, what would it be?
- If you had to choose a simple function (i.e. from the list of functions used in big-O notation) to characterize the behaviour of the the average number of items examined per query for the tree quest log as the number of quests (n) in the log increases, what would it be?
- If your primary use of the quest log was to display all of the quests in the log in alphabetical order, would you prefer the hashed quest log or the tree quest log? Why?
- If your primary use of the quest log was to periodically look up the details of specific quests in no particular order, would you prefer the hashed quest log or the tree quest log? Why?