NAStrand $($Abstract Class$)[36$ marks$]$

This class represents an NA strand; it is abstract because we don$$t know which bases a strand allows unless we know whether it is RNA or DNA. However, a lot of the behaviour of an NAStrand can be implemented without knowing the exact bases. Your task is to fill in the constructors and methods according to the specifications below, using implementations based on those discussed in lecture. The provided implementations are incorrect, but should be enough to compile and run the $($failing$)$ local and autograder tests.

Fields

char$[]$ bases The allowable bases for this strand.

char$[]$ a Array to store the sequence of bases in the strand.

int n The number of bases in the strand.

int j Starting index of the NAStrand in the array.

Constructor

NAStrand$($char$[]$ bases$)$

Initializes the array and other fields.

Abstract Methods

public abstract boolean isPair$($char x$,$ char y$)$

Returns whether x and y are considered a base pair for the respective subclass.

Methods

public char$[]$ getBases$()$

Returns the allowable bases.

public boolean isBase$($char x$)$

Returns whether or not character x is a valid base for this strand.

If you$$ve implemented getBases and isBase, you should pass the local and autograder tests.

public void add$($int i$,$ char x$)$ throws IllegalArgumentException, IndexOutOfBoundsException

Adds the base x at index i in the strand.

Throws an IndexOutOfBoundsException if the index is out of bounds.

Throws an IllegalArgumentException if the base is not valid.

public void add$($char x$)$ throws IllegalArgumentException

Adds the base x to the end of the strand.

Throws an IllegalArgumentException if the base is not valid.

public char get$($int i$)$ throws IndexOutOfBoundsException

Returns the base at the specified index i in the strand.

Throws an IndexOutOfBoundsException if the index is out of bounds.

If you$$ve implemented add and get, you should pass some local and autograder tests.

public int size$()$

Returns the number of bases in the strand.

public void clear$()$

Clears the strand so that it has no bases.

If you$$ve implemented size and clear, you should pass some local and autograder tests.

public char set$($int i$,$ char x$)$ throws IllegalArgumentException, IndexOutOfBoundsException

Sets the base at index i in the strand to x$.$

Returns the value originally at index i in the strand.

Throws an IndexOutOfBoundsException if the index is out of bounds.

Throws an IllegalArgumentException if the base is not valid.

public char remove$($int i$)$ throws IndexOutOfBoundsException

Removes and returns the base at the specified index i in the strand.

Throws an IndexOutOfBoundsException if the index is out of bounds

If you$$ve implemented remove and set, you should pass some local and autograder tests.

public void spliceIn$($int i$,$ NAStrand q$)$ throws IllegalArgumentException, IndexOutOfBoundsException

Splices another NAStrand q into this strand at the specified index i$.$

Throws an IndexOutOfBoundsException if the index is out of bounds.

Throws an IllegalArgumentException if this and q are not the same type.

public void reverse$($int i$,$ int k$)$ throws IndexOutOfBoundsException

Reverses the bases in the NAStrand from index i to index k$-1($inclusive$).$

Throws an IndexOutOfBoundsException if either index is out of bounds.

Throws an IndexOutOfBoundsException if k $<=$ i$.$

Finally, you should test spliceIn and reverse both locally and on the autograder.

Desired Complexity

marks

method

time complexity

$($extra$)$ space complexity

$0$

constructor

O$(1)$

O$(1)$

$0\mathrm{.}5$

getBases

O$(1)$

O$(1)$

$2$

isBase

O$(1)$

O$(1)$

$0$

add$($x$)$

O$(1)$A

O$(1)+$resize

$5$

add$($i$,$x$)$

O$(1+$min$\{$i$,$ n$-$i$\})$A

O$(1)+$resize

$0\mathrm{.}5$

get$($i$)$

O$(1)$

O$(1)$

$0\mathrm{.}5$

size$()$

O$(1)$

O$(1)$

$0\mathrm{.}5$

clear$()$

O$(1)$

O$(1)$

$4$

set$($i$,$x$)$

O$(1)$

O$(1)$

$3$

remove$($i$)$

O$(1+$min$\{$i$,$ n$-$i$\})$A

O$(1)+$resize

$10$

spliceIn$($i$,$ q$)$

O$(1+$min$\{$i$,$ n$-$i$\}+$nq$)$A

O$(1)+$resize

$10$

reverse$($i$,$k$)$

O$($k$-$i$+1)$

O$(1)$

Examples

RNA.getBases$()$

DNA.getBases$($x$)$

$\{$A$,$C$,$G$,$U$\}($other order ok$)$

$\{$A$,$C$,$G$,$T$\}($other order ok$)$

x

RNA.isBase$($x$)$

DNA.isBase$($x$)$

x

RNA.isBase$($x$)$

DNA.isBase$($x$)$

U

true

false

T

false

true

A

true

true

C

true

true

NAStrand

method

output

NAStrand $($post$)$

$[]$

add$($A$)$

$[$A$]$

$[$A$]$

add$(1,$C$)$

$[$A$,$C$]$

$[$A$,$C$]$

add$(0,$B$)$

IllegalArgumentException

$[$A$,$C$]$

add$(3,$G$)$

IndexOutOfBoundsException

$[$A$,$C$]$

add$(3,$B$)$

IndexOutOfBoundsException

$[$A$,$C$]$

get$(0)$

A

$[$A$,$C$]$

$[$A$,$C$]$

get$(2)$

IndexOutOfBoundsException

$[$C$,$ G$,$ G$,$ A$]$

size$()$

$4$

$[$C$,$ G$,$ G$,$ A$]$

$[]$

size$()$

$0$

$[]$

$[$C$,$ G$,$ G$,$ A$]$

clear$()$

$[]$

NAStrand

method

output

NAStrand $($post$)$

$[$A$]$

set$(0,$C$)$

A

$[$C$]$

$[$A$,$G$]$

set$(1,$C$)$

G

$[$A$,$C$]$

$[$A$,$C$]$

set$(0,$B$)$

IllegalArgumentException

$[$A$,$C$]$

set$(2,$G$)$

IndexOutOfBoundsException

$[$A$,$C$]$

set$(2,$B$)$

IndexOutOfBoundsException

$[$A$,$C$]$

remove$(1)$

C

$[$A$]$

$[$A$]$

remove$(1)$

IndexOutOfBoundsException

$[]$

remove$(0)$

IndexOutOfBoundsException

NAStrand

method

NAStrand $($post$)$

n

nq

$[$A$,$A$,$G$]$

splice$(0,[$C$,$G$]$