I was wondering what I would use as the access and storage layers in this assign
ID: 3575474 • Letter: I
Question
I was wondering what I would use as the access and storage layers in this assignment? Would it be a multidimensional array? And if so, how would I go about implementing the add method, most importantly understanding how to add the object at the right index?
Task: Implement a bilevel array and its operations. Operations include, add and remove an element at the end, and read and write an element at an arbitrary location. These operations should complete in O(1) time. In addition, implement a method iterator that returns an iterator.
public class BilevelArray implements Iterable {
/?? adds an element to the end. ?/
public void add(T elem) { /? YOUR CODE ?/ }
/?? removes last element. ?/
public T remove() { /? YOUR CODE ?/ }
/?? returns element at idx. ?/
public T get(int idx) { /? YOUR CODE ?/ }
/?? replaces element at idx with elem. ?/
public void set(int idx, T elem) { /? YOUR CODE ?/ }
/?? returns the number of stored elements. ?/
public int size() { /? YOUR CODE ?/ }
/?? returns an iterator to the data structure. ?/
public Iterator iterator() { /? YOUR CODE ?/ } }
A bilevel array uses two levels for storing its elements. The first layer (access layer) is an array with 32 entries. The second layer (storage layer) stores the actual data. The “trick” of this design is that we can grow the number of entries in the storage layer with each additional level (see Figure 1 below) thereby avoiding resizing the access or storage layer.
When an object is created, only the access layer, but no storage layer is allocated. When an element is added (e.g., “U”), we split its linear index into an index-pair (access layer index ; storage layer index). The first element (stored at 0 in an array) translates to (0;0). Since the entry in the access layer is empty, we create an array of size 1 (2accessLayerIndex ) and store the element. When we insert an “A”, we compute the storage location to be (1;0). Since the access layer has no entry at 1, we create a storage array of size 2 and store the new element. When we insert another element “B” (not shown in the figure), we determine the location to be (1;1). Since the access layer already has an entry at 1, we just store the new element.
access layer storage layer 31 H. 31 31 arr o-- o arrr size() 1 size() arr size 32 Figure 1: Bilevel arraylist designExplanation / Answer
Let the access layer be array of pointers and the storage layer be a list.
Access layer will contain the base address of the list.
For example the index zero will contain the address of 0th List.
index 1 will contain address of 1st List and so on..
Let the list be of the below type:
struct List{
int lastFilledIndex;
int key;
char value;
}
The lastFilledIndex in the above List struct will have the key of the last element in the list. This is only updated in the root node.
For all other nodes it will be zero.
the key and value will contain the respective inserted values.
In this way we can achieve O(1) translation time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.