Java-Create a bilevel arraylist

Please help!! I really dont know where to start.

Background: An array-list uses an array to store its elements. When the number of elements exceeds the capacity, a larger array is allocated and all elements are moved to the new array. This approach is simple yet guarantees good performance on average. However, this approach may not be a good choice for some real-time systems, where it is necessary to have a regular upper bound on an operation. In this context, resizing an array would show irregular performance (it takes longer than a regular operation). Thus, we would like to implement a data structure, BilevelArrayList (similar to ArrayList), that does not need to relocate elements.

Task: Implement a bilevel array and its operations. Add and remove an element at an arbitrary position (with runtime O(n) in general. If the element is at the end, the runtime should be O(1).). Read and write an element at an arbitrary position (should be O(1) always).

public class BilevelArrayList extends AbstractList {

/ creates an empty list. / public BilevelArrayList() { / YOUR CODE / }

/ returns element at idx. / public T get(int idx) { / YOUR CODE / }

/ removes element at position pos. / public T remove(int pos) { / YOUR CODE / }

/ replaces element at idx with elem. / public T set(int idx, T elem) { / YOUR CODE / }

/ inserts an element o at position pos. / public void add(int pos, T o) { / YOUR CODE / }

/ returns the number of stored elements. /

public int size() { / 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 external index into an internal 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 in the storage layer.

One challenging aspect is the translation from the external index into the internal index-pair for access and storage layer. Ideally, the translation should run in constant time (O(1)). A solution will likely require some bit twiddling and the use of Integer.numberOfLeadingZeros. Note, you can assume that Integer.numberOfLeadingZeros runs in O(1) time (which holds on modern x86 systems).