This is the file name you would need testif.py

Problem $1$

Write the code for this problem in a file named p$1\_$Lastname$\_$Firstname.py$,$ as required above.

a$)$ Implement in Python a class for a

mutable

string called

Mstring

$.$

Class Mstring must have the following interface:

$-$ a constructor that takes

any object

as argument and constructs a mutable string object

$-$ method $\_\_$len$\_\_$ with their standard role; returns int

$-$ methods $\_\_$str$\_\_,\_\_$repr$\_\_$ with their standard role; must return str

$-$ methods $\_\_$add$\_\_$ and $\_\_$radd$\_\_$ for concatenating two Mstring objects or an Mstring with a

str;

must

return Mstring

$-$ method $\_\_$getitem$\_\_$ that works like str$.\_\_$getitem$\_\_$; must work also with a negative index; must

return str

$-$ method $\_\_$setitem$\_\_$ that sets a character at a given index; must work also with a negative index;

throws IndexError if the index is invalid

$-$ methods $\_\_$eq$\_\_,\_\_$ne$\_\_$ that compare an Mstring with another Mstring, or with a str$.$

$-$ method

replace$($s$,$ t$)$

that replaces the first occurrence of a substring

s

with another string t; it returns

the index of the substring

s

if

s

was found, or $-1$ otherwise

$-$ method

find

that works like str$.$find

Make sure your methods throw the same type of exception as equivalent methods in the str class $($as

applicable$).$

Examples:

ms$1=$ Mstring$($Hello World$)$

print$($ms$1)$

# prints: Hello World

print$($ms$1[3])$

# prints: l

print$($ms$1[-3])$

# prints: r

print$($ms$1[20])$

# throws IndexError

print$($len$($ms$1))$

# prints $11$

ms$2=$ Mstring$($abcdef$)$

print$($ms$2+$

xyz$)$

# addition with regular string: prints abcdef

xyz$.$ Caution: $+$ must return

Mstring

print$(0123+$ ms$2)$

# addition with regular string: prints $0123$abcdef. Caution: $+$ must return

Mstring

print$($ms$2+$ Mstring$(1234))$

# prints abcded$1234.$ Caution: $+$ must return Mstring

ms$2[2]=$X$$

print$($ms$2)$

# prints abXdef

ms$2[7]=$Y$$

throws index error

ms$2[-7]=$Y$$

throws index error

ms$2[3]=$ZZ$$

throws ValueError since we can$$t insert a multi$-$character string with $[]=$

Mstring$($abcd$)==$ Mstring$($abcd$)$

should return true

Mstring$($abcd$)==$ Mstring$($abcX$)$

should return false

ms$3=$ Mstring$(01234567)$

print$($ms$3.$find$(45))$

# prints $4$

print$($ms$3.$find$($abc$))$

# prints $-1$

print$($ms$3.$replace$(34,$XYZABC$))$

# prints $3$

print$($ms$3)$

# prints $012$XYZABC$567$

ms$4=$ Mstring$(01234567)$

print$($ms$4.$replace$($AB$,$XYZ$))$

# prints $-1$

print$($ms$4)$

# prints $01234567$

Important implementation details:

A

void re$-$computing a

str

value unless the underlying characters have changed. Use caching.

Pick an internal representation for the characters that is efficient when using $\_\_$setitem$\_\_$ and

$\_\_$getitem$\_\_.$

b$)$ Write a function called

unit$\_$tests

that uses the

testif

$()$ function $($at the end of this file$)$ with unit tests

for the following Mstring methods: $\_\_$eq$\_\_,\_\_$ne$\_\_,\_\_$str$\_\_,\_\_$len$\_\_,\_\_$add$\_\_,\_\_$radd$\_\_,$

$\_\_$setitem$\_\_,\_\_$getitem$\_\_,$

replace

Make sure you include success and failure cases. Test also with the empty string object Mstring$().$

Add a print statement for each test explaining what is tested.

c$)$ Write a function $($not a method!$)$ called

quicksort

that

sorts in place

the characters in an Mstring

object and that relies on Mstring$$s $[]$ operators to read and write characters. Use the classical quicksort

algorithm, of courses.

d$)$ Write a function

test$\_$sort

that tests the function from part c$)$ on some representative strings,

including the empty Mstring.

e$)$ write a function called

main

that runs

unit$\_$tests

and

test$\_$sort