The (provided) DLList, IntDLList,, and SkiplistList classes are (incomplete) implementations of the MyList interface. Your task is to complete the implementation of the DLList, IntDLList, and SkiplistList classes, as specified below. Default implementations are provided for the 4 methods so that you can compile and run the main methods of the relevant classes right out of the gate; these defaults will not pass any of the tests, however.
- [8 marks] (Assignment 1.6 Redux) In the IntDLList class, implement
public void sum(IntDLList other)
Replace the ith element of this IntDLList by this[i] + other[i]. That is, the elements from this are now each value-shifted by the corresponding entry in other. If other is shorter than this, just repeat other as many times as is necessary until you have shifted every element of this once.
For example, if the list is originally mal=[4,5,6,7] and other=[1,2,3] then mal.sum(other) changes mal to [5, 7, 9, 8].
- [8 marks] (Assignment 1.7 Redux) In the IntDLList class, implement
public void intervalInsert(IntDLList other)
Modify this IntDLList by inserting -1 into this at intervals specified by other. That is, there are other[0] elements of this before -1 then the next other[1] elements of this before the next -1, etc. If other’s intervals do not cover all of this, just repeat other as many times as is necessary until you have “processed” all of this once.
For example, if the list is originally ml=[4,5,6,7,8,9] and other=[1,2] then mal.intervalInsert(other) changes ml to [4,-1,5,6,-1,7,-1,8,9].
You may assume that all entries of other are positive.
- [12 marks] In the DLList class, implement
public void insertSingleBlock(int i, DLList other)
which inserts the DLList other at index i of this DLList.
For example, if the list is originally ml=[1,2,3,4,5,6,7] and other=[-1,-2] then ml.insertSingleBlock(1, other) changes ml to [1, -1, -2, 2, 3, 4, 5, 6, 7]. You may assume that input i is a valid index (i.e., 0 .)
- [10 marks] In the SkiplistList class, implement
public String toString()
to return a more useful String representation of the Skiplist than the current implementation. You will want to overwrite the existing code such that if you were to print this you would get information about the heights of the nodes and the lengths of the edges within them. This will really help you in debugging Part 9.
Your string should represent each level of the skiplist on an individual line, where the sentinel is represented by the pipe |, each level 0 element is divided by the following by two dashes, then the length of that edge in parentheses, then two more dashes. More generally, a length L line is 2L-1 pair of dashes, then the length in parentheses, and then 2L-1 more pair of dashes.
For example, a skiplist on 9 elements might be represented by the String
|----------------------------------(9)----------------------------------i
|------------------(5)------------------e--------------(4)--------------i
|--(1)--a--(1)--b--(1)--c--(1)--d--(1)--e--(1)--f--(1)--g--(1)--h--(1)--i
whereas a skiplist on 5 elements might be represented by the String
|------------------(5)------------------e
|--(1)--a--(1)--b--(1)--c--(1)--d--(1)--e
and a skiplist on 7 elements might be represented by the String
|------------------(5)------------------e
|--(1)--a--(1)--b--(1)--c--(1)--d--(1)--e--(1)--f--(1)--g
A different skiplist on the same 7 elements might look like this String
|--------------------------(7)--------------------------6
|--------------------------(7)--------------------------6--(1)--7
|--------------------------(7)--------------------------6--(1)--7
|--(1)--0--(1)--1--(1)--2--(1)--3--(1)--4--(1)--5--(1)--6--(1)--7
The empty skiplist is just
|
Look at the existing toString() method to help you use the
StringBuilder, then overwrite that code to have the new desired functionality.
- [12 marks] In the SkiplistList class, implement
public void insertSingleBlock(int i, SkiplistList other)
which inserts the SkiplistList other at index i of this SkiplistList.
For example, if the list is originally l=[1,2,3,4,5,6,7] and other=[-1,-2] then l.insertSingleBlock(1, other) changes l to [1, -1, -2, 2, 3, 4, 5, 6, 7]. You may assume that input i is a valid index (i.e., 0 .)