Programming Homework Help

The slotted page structure allows a storage manager to store variable-length records (data objects) within a fixed size page (an in-memory copy of a disk block). Each page is essentially a byte array that stores a header (at the beginning) and data objects (at the end). The header of a page consists of (1) a 4-byte integer representing the number of entries in the page (one entry for each data object), and (2) a series of 4-byte integers each representing the location where the corresponding data object is stored within the page. Each page has, between its header and data objects, a free space where more data objects and header entries can be added. For further details of the slotted page structure, refer to Section 13.2.2 of the textbook. Upon a request to delete a data object from a page, the corresponding header entry (for storing the location of that data object within the page) is simply set to -1 to indicate that there is no associated data object (the actual object is NOT necessarily removed from the page). 1 http://junit.org 1 In this part, you need to implement the following methods (your code needs to pass all of the 5 tests in SlottedPageTest): • add(Object o): (20 points) adds the specified object o in a SlottedPage when this method is invoked on that SlottedPage. This method must first save the object o in the free space of the SlottedPage by calling the save(Object o) method. This save(Object o) method returns an int value indicating the location at which the object o is saved in the SlottedPage. That int value must be stored at the right header entry of the SlottedPage so that the saved object o can be accessed in the future. For example, assume that object “123” is saved at location 2038 in the byte array of an empty SlottedPage. Then, the first 4 bytes of the byte array (i.e., the beginning of the header) must store an int value 1 to indicate that there is only one entry in the header (in response to the addition of object “123”). The next 4 bytes of the byte array (i.e., the 0th entry in the header) must store 2038 (i.e., the location at which “123” is saved). When an additional object “456” is saved at location 2028 in the byte array, the first 4 bytes of the header must store 2 (to indicate that there are two entries in the header) and the 1st entry (i.e., the entry after the 0th entry) in the header must store 2028 (i.e., the location at which “456” is saved). To find the number of entries that the SlottedPage currently has, use the entryCount() method. To set the number of entries in the header to an int value, use the setEntryCount(int count) method. To save location l at the ith entry in the header, call saveLocation(i, l). • get(int index): (20 points) returns the object at the specified index in a SlottedPage when this method is invoked on that SlottedPage. For example, get(0) returns the object at index 0 (i.e., the object whose location is stored at the 0th entry in the header) and get(1) returns the object at index 1. This method must first find the location of the object at the specified index by calling the getLocation(int index) method. This getLocation(int index) method returns the int value stored at the header entry specified by index (i.e., the index-th header entry). If that location is -1, meaning that the object was removed from the SlottedPage, the get(int index) method needs to return null. Otherwise, get(int index) needs to obtain the object by calling the toObject(byte[] b, int offset) method (with offset set to the return value of getLocation(int index)) and then return that obtained object. If the given index cannot match any of the entries in the SlottedPage (e.g., get(-1)), the method needs to throw an IndexOutOfBoundsException. • remove(int index): (10 points) removes the object at the specified index from a SlottedPage when this method is invoked on that SlottedPage. This method must save -1 at the appropriate entry in the header. This method must also return the object removed (i.e., the object previously stored at the specified index). This method must NOT change the first 4 bytes in the header of the SlottedPage. These 4 bytes represent the number of entries in the header (including those containing -1 indicating object removal), not the number of objects remaining in the SlottedPage. • iterator(): (10 points) returns an iterator over the objects (excluding those removed) stored in a SlottedPage when this method is invoked on that SlottedPage. To find the number of entries in the current SlottedPage, use entryCount(). To get the object at each index, call get(int index). Note that get(int index) returns null if there is currently no object at the specified index due to the deletion of the previous object. The iterator must skip such null values. For example, suppose that objects “123”, “456”, and “789” are added to a SlottedPage and then object “123” is removed from that SlottedPage. In this case, an iterator obtained from that SlottedPage must iterator over only two objects (“456” and “789”). Feel free to add an auxiliary class or data structure for this iterator() method. 2 • compact(): (5 points) reorganizes the SlottedPage on which the method is invoked (in order to maximize the free space of that SlottedPage). This method is used by the save(Object o) method when the object to save cannot fit into the current free space of the SlottedPage. This method needs to move objects at the end of the SlottedPage in a manner that eliminates the space previously wasted by the objects removed from the SlottedPage.