Use the following commands to make a fresh clone of your repository:

```
git clone -b m21 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git m21
```

## Useful links

  * [A guide to the Scala parallel collections](https://docs.scala-lang.org/overviews/parallel-collections/overview.html)
  * [The API documentation of the Scala parallel collections](https://www.javadoc.io/doc/org.scala-lang.modules/scala-parallel-collections_2.13/latest/scala/collection/index.html)
  * [The API documentation of the Scala standard library](https://www.scala-lang.org/files/archive/api/2.13.4)
  * [The API documentation of the Java standard library](https://docs.oracle.com/en/java/javase/15/docs/api/index.html)

**If you have issues with the IDE, try [reimporting the
build](https://gitlab.epfl.ch/lamp/cs206/-/blob/master/labs/example-lab.md#ide-features-like-type-on-hover-or-go-to-definition-do-not-work),
if you still have problems, use `compile` in sbt instead.**

## Exercise

In this question, you will complete the definition of two concurrent data
structures **without using `synchronized`**: `SeqCount` and `MultiWriterSeqCount`.

## Part 1: SeqCount (defined in `SeqCount.scala`)

An instance of this class stores two integers (initially set to 1), the stored
values can be updated using `write` and retrieved using `copy`. Only one thread
at a time is allowed to call `write` but multiple threads can call `copy` at
once.

Your task in this part is to implement `copy` such that this method never
returns _partially updated values_, for example given two threads operating
concurrently on a `SeqCount` `sc`:
```scala
// Thread 1
sc.write(1, 2)
```
```scala
// Thread 2
val result = sc.copy()
```
`result` must either be `(0, 0)` (since the initial values are 0) or `(1, 2)`,
but it must not be `(1, 0)`, `(0, 2)` or any other value.

To successfully implement this method you will need to use `generation`: this
method returns the current value of a volatile variable which is initially set
to 1, gets incremented by one at the beginning of `write`, and incremented by
one again at the end of `write`.

**You are not allowed to use `synchronized` or directly call any of
`myGeneration`, `myX` or `myY` (use the pre-defined getters and setters
instead).**

Hints:
- Remember that a write to a volatile field _happens-before_ every subsequent
  read of that field.
- `generation` will always be odd when a write has completed and always
even when a write is in progress.
- `copy` can be implemented as a tail-recursive method.

## Part 2: MultiWriterSeqCount (defined in `MultiWriterSeqCount.scala`)

Like `SeqCount`, this class stores two integers updated using `write` and
retrieved using `copy`, but unlike `SeqCount` multiple threads are allowed to
call `write` at the same time: these writes will all succeed but they are
allowed to complete in any order, for example given three threads operating
concurrently on a `MultiWriterSeqCount` `msc`:
```scala
// Thread 1
msc.write(1, 2)
```
```scala
// Thread 2
msc.write(10, 20)
```
```scala
// Thread 3
val result = msc.copy()
```
`result` must either be `(0, 0)`, `(1, 2)` or `(10, 20)`.

In this class, the generation is stored in an atomic variable instead of a
volatible field therefore it's important to note that:
- a `set` on an atomic variable _happens-before_ every subsequent `get` of that
  variable.
- A call to `compareAndSet` both gets and set an atomic variable.

Your task in this part is to implement both `copy` and `write`.

**You are not allowed to use `synchronized` or directly call any of
`myGeneration`, `myX` or `myY` (use the pre-defined getters and setters
instead).**

Hints:
- you should be able to just copy-paste the implementation of `copy` you
  implemented in Part 1
- you will need to make use of `compareAndSetGeneration` in `write`
- `write` can be implemented as a tail-recursive method.