Problem H
Beständig array
En beständig datastruktur (persistent data structure) är en datastruktur som inte skriver över sig själv (muteras) när man gör en förändring i den. Det betyder att man alltid kan gå tillbaka till en tidigare version av datastrukturen.
En array är en indexerad datastruktur där det går snabbt att slå upp och ändra vilket element som helst. I denna uppgift har arrayen dynamisk storlek och kan vara gles, dvs inte alla möjliga element har tilldelats något värde.
Uppgift
Implementera en beständig datastruktur för en dynamisk array (indexerad med naturliga tal) med heltal som har följande operationer:
|
newarray() |
Returnera en ny array. |
|
set(a, i, value) |
Sätt a[i] till value och returnera den nya versionen av arrayen. i är ett ickenegativt heltal och value är ett heltal. Såväl i som value är 32-bitstal, dvs högst $2^{31} - 1$. |
|
get(a, i) |
Returnera värdet a[i]. Om a[i] inte har tilldelats ett värde tidigare returneras 0. |
En beskrivning av hur datastrukturen ska byggas finns på
https://conjoin-it.se/#clojure/persistent-data-structures.
Skriv sedan ett styrprogram som skapar en beständig array och sedan utför ovanstående operationer på den utifrån följande kommandon som läses från standard input:
|
get i |
Skriv ut värdet på index i på standard output på en egen rad. Om inget värde tilldelats ska 0 skrivas ut. Det ska vara ett mellanslag mellan get och indexet. |
|
set i value |
Sätt värdet på index i till value. Det ska vara ett mellanslag mellan set och i och mellan i och value. |
|
unset |
Backa tillbaka till läget en set-operation tidigare. Om ingen set-operation gjorts händer inget. |
| Sample Input 1 | Sample Output 1 |
|---|---|
set 3 17 set 3 4711 get 3 set 3 1000 unset get 3 unset get 3 |
4711 4711 17 |
| Sample Input 2 | Sample Output 2 |
|---|---|
set 0 10 set 1 11 set 2 12 set 4 14 set 6 16 set 8 18 set 7 17 set 5 15 set 3 13 get 1 get 5 unset unset get 3 get 5 get 7 |
11 15 0 0 17 |
| Sample Input 3 | Sample Output 3 |
|---|---|
set 999999 1000 get 1000000 get 999999 unset get 999999 unset get 999999 |
0 1000 0 0 |
