CSE-250 Fall 2022 - Section B - Sequences

### Sequences

Sept 16, 2022

#### Sequences

The Fibonacci Sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Characters of a String
'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd'
Lines of a file.

#### What can you do with a Sequence?

• Enumerate every element of the sequence.
• Get the 'n'th element.
• Modify the 'n'th element (mutable only).

apply(idx: Int): A
Get the element (of type A) at position idx.
iterator: Iterator[A]
Get access to view all elements in the seq, in order, once.
length: Int
Count the number of elements in the seq.

apply(idx: Int): A
Get the element (of type A) at position idx.
iterator: Iterator[A]
view
all elements in the seq, in order, once.
length: Int
Count the number of elements in the seq.
insert(idx: Int, elem: A): Unit
Insert an element at position idx with value elem.
remove(idx: Int): A
Remove the element at position idx and return the removed value.

... so how do we implement it?

#### RAM

new T()
Find some unused part of memory big enough to fit a T, mark it used, and return the address of that location.

var arr = new Array[Int](50)


$50 * 4 = 200$ bytes of memory allocated
(Java Int is 4 bytes).

If arr is at address $a$, where should you look for arr(19)? arr(55)?

#### Array[T] : Seq[T]

An Array of $n$ items of type T:

• size: 4 bytes for $\texttt{sizeof}(\texttt{data})$ (optional).
• bytesPerElement: 4 bytes for $\texttt{sizeof}(\texttt{T})$ (optional).
• data: $\texttt{size} \times \texttt{bytesPerElement}$ bytes of memory.

#### Array[T] : Seq[T]

How do we implement...

length: Int
Count the number of elements in the seq.
apply(idx: Int): A
Get the element (of type A) at position idx.
append(idx: Int, elem: A): Unit
Insert an element at position idx with value elem.
insert(idx: Int, elem: A): Unit
Insert an element at position idx with value elem.
remove(idx: Int): A
Remove the element at position idx and return the removed value.

Insert and remove on arrays are sloooooow...

Idea Reserve extra space in the array!

#### ArrayBuffer[T] : Buffer[T] ( : Seq[T] )

An ArrayBuffer of type T:

• size: 4 bytes for $\texttt{sizeof}(\texttt{data})$ (optional).
• bytesPerElement: 4 bytes for $\texttt{sizeof}(\texttt{T})$ (optional).
• used: 4 bytes for the number of fields $used$
• data: $\texttt{size} \times \texttt{bytesPerElement}$ bytes of memory.

#### ArrayBuffer[T] : Buffer[T]

How do we implement...

length: Int
Get the element (of type A) at position idx.
apply(idx: Int): A
Get the element (of type A) at position idx.
append(idx: Int, elem: A): Unit
Insert an element at position idx with value elem.
insert(idx: Int, elem: A): Unit
Insert an element at position idx with value elem.
remove(idx: Int): A
Remove the element at position idx and return the removed value.

What happens when $\texttt{used} >= \texttt{size}$?

Increase the size of the array.
... but by how much?

#### ArrayBuffer[T] : Buffer[T]

What is the worst-case (Big-O) complexity of append(x)?

What is the worst-case (Big-O) complexity of calling append(x) $n$ times on an initially empty array?

... to be continued