below is the code for UltraStack.java: package comp$2402$a$4$;

import java.util.Iterator;

public interface UltraStack extends Iterable $\{$

public void push$($int x$)$;

public Integer pop$()$;

public void doubleTop$()$;

public void swapTop$()$;

public Integer get$($int i$)$;

public Integer set$($int i$,$ int x$)$;

public Integer max$()$;

public long ksum$($int k$)$;

public int size$()$;

public Iterator iterator$()$;

$\}$ below is the code for UltraSlow.java: package comp$2402$a$4$;

import java.util.List;

import java.util.ArrayList;

import java.util.Iterator;

public class UltraSlow implements UltraStack $\{$

List ds;

public UltraSlow$()\{$

ds $=$ new ArrayList$()$;

$\}$

public void push$($int x$)\{$

ds$.$add$($x$)$;

$\}$

public Integer pop$()\{$

if$($ds$.$size$()==0)$

return null;

return ds$.$remove$($ds$.$size$()-1)$;

$\}$

public Integer get$($int i$)\{$

if$($i $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ i $>=$ ds$.$size$())$

return null;

return ds$.$get$($i$)$;

$\}$

public Integer set$($int i$,$ int x$)\{$

if$($i $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ i $>=$ ds$.$size$())$

return null;

return ds$.$set$($i$,$ x$)$;

$\}$

public void doubleTop$()\{$

if $($size$()>0)$

ds$.$add$($ds$.$get$($ds$.$size$()-1)*2)$;

$\}$

public void swapTop$()\{$

if $($size$()>1)\{$

Integer temp $=$ ds$.$get$($ds$.$size$()-1)$;

ds$.$set$($ds$.$size$()-1,$ ds$.$get$($ds$.$size$()-2))$;

ds$.$set$($ds$.$size$()-2,$ temp$)$;

$\}$

$\}$

public Integer max$()\{$

Integer m $=$ null;

for $($int x : ds$)\{$

if $($m $==$ null $||$ x $>$ m$)\{$

m $=$ x;

$\}$

$\}$

return m;

$\}$

public long ksum$($int k$)\{$

long sum $=0$;

for$($int i$=0$; i iterator$()\{$

return ds$.$iterator$()$;

$\}$

$\}$ Download the Provided Files

The base code for this assignment consists of one zip file, which you can download from Brightspace: comp$2402$a$4.$zip $-$ source code. This file contains a folder named comp$2402$a$4$ with four $.$java files:

$-$ UltraFast.java $-$ add your code here

$-$ UltraSlow.java

$-$ UltraStack.java

$-$ Tester.java $-$ use this class to design your tests and debug$/$test your code

Grading

This assignment will be tested and graded by a computer program also known as an auto$-$grader. You can submit as many times as you like; your highest grade is recorded. For this to work, there are some important rules you must follow:

$-$ Keep the directory structure of the provided comp$2402$a$4.$zip file. If you find a file in the subdirectory comp$2402$a$4$ leave it there.

$-$ Keep the package structure of the provided zip file. If you find a package comp$2402$a$4$; directive at the top of a $.$java file, leave it there.

$-$ Keep the interfaces as they are. You may add internal methods to your implementation, but do not introduce any new methods to the interfaces.

$-$ Do not rename or change the visibility of any methods already present. If a method or class is public leave it that way.

$-$ Submit early and often. The auto$-$grader will compile and run your code, providing you with instant feedback and a grade. You can submit as many times as you like $-$ your final grade will reflect your last submission. Alternatively, you can choose to activate your highest$-$graded submission as your final score. With this flexibility, there's no excuse for submitting code that doesn't compile or fails the tests.

$-$ Similarly to the previous assignments, your methods are not independent and cannot be tested independently.

$-$ Start by exploring the skeleton code $-$ it includes implementations for all the required methods but is based on a slower model. The Assignment

This assignment contains only one part worth $100$ marks.

The data values we will maintain are integers, both negative and positive.

An UltraStack is an extended stack that supports eight main operations: the standard Stack operations push $($ x $)$ and pop$()$ and the following non$-$standard operations:

$-\backslash (\backslash$operatorname$\{$get$\}($i$)$: $\backslash )$ returns the $\backslash ($ i $\backslash )-$th element $($from the bottom$)$ on the Stack.

$-\backslash (\backslash$operatorname$\{$set$\}($i$,$ x$)\backslash )$ : sets the value of the $\backslash ($ i $\backslash )-$th element $($from the bottom$)$ on the Stack to $\backslash ($ x $\backslash ),$ and returns the element that was previously stored at the same position.

$-$ doubleTop$()$: reads the top element $\backslash ($ x $\backslash )$ from the Stack and adds a new element $\backslash (2^\{*\}$ x $\backslash )$ to the top of the Stack.

$-$ swapTop$()$: swaps the top two elements of the Stack.

$-\backslash (\backslash$max $(\backslash$mathrm$\{)\}\backslash )$ : returns the maximum value stored on the Stack.

$-\backslash (\backslash$operatorname$\{$ksum$\}($k$)\backslash )$ : returns the sum of the top $\backslash ($ k $\backslash )$ elements on the Stack.

The zip file gives an implementation of UltraSlow, which correctly implements these operations so that push$($x$),$ pop$(),$ get$($i$),$ doubleTop$(),$ swapTop$(),$ and set $($i$,$ x$)$ each run in $\backslash ($ O $\backslash )(1)$ time, but max $()$ and ksum$($k$)$ run in $\backslash ($ O$($n$)\backslash )$ time. The provided implementation of the UltraFast is just a copy of UltraSlow implementation.

You must complete the implementation of UltraFast by correctly coding all eight operations and optimizing their efficiency. For UltraFast, the running time for get $($i$)$ and max $()$ must be $\backslash (\backslash$boldsymbol$\{$O$\}(\backslash$mathbf$\{1\}\backslash )),$ and for push$($x$),$ pop$(),$ set $($i$,$ x$),$ doubleTop$(),$ swapTop$(),$ and ksum$($k$)$ running time must not exceed $\backslash (\backslash$boldsymbol$\{$O$\}(\backslash$log $\backslash$boldsymbol$\{$n$\})\backslash ).$

You may assume that the Stack elements will be in the range $[-3000000,3000000].$

As part of your implementation, you may use any of th $-$ hasNext $()-$ that returns true if this list ite