name: portada
class: portada-slide, center, middle

# Estrutures de dades

.footnote[Mateu Yábar Valles]

---
<h3 class="alert-heading">Llicència</h3>
<p>Pots copiar i redistribuir aquest material seguint la llicència Attribution-NonCommercial-ShareAlike 4.0 International <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a>, indicant-ne autors originals, l'origen (aquesta web), sense fins comercials i mantenint-ne aquesta la llicència</p>
<p class="mb-0">Autors:</p>
<ul><li><a href="https://fp.mateuyabar.com">Mateu</a></li><li><a href="https://centellas.gitlab.io/teachingSite">Laura Centellas</a></li></ul>

---
# Collection
- Representa un conjunt d'objectes
  - __List__: elements ordenats -> Visites d'un metge
  - __Set__: no ordenats i sense repeticions -> número de loteria
  - __Map (dictionary)__: conjunt de parelles clau-valor -> codi mòdul i professor M03DAW1 - Marc

---
# Collection in kotlin
Per cada tipus de basic de collections hi ha:
- Una __interfície read-only__ només per accedir als elements de la col·lecció.

- Una __interfície mutable__ que exté la corresponent interfície read-only amb operacions d'escriptura: add, remove i update del seus elements.

---
# Collections
.imgwidth70[![collection](files/collections.png)]

---
# Operacions de collections

- __size__ -> mida de la col·lecció.
- __contains(element)__ -> comprova si existeix l'element a la col·lecció.
```
println(elem in collection) // recomanat
println(collection.contains(elem))
```
- __containsAll(elements)__ -> comprova que tots els elements siguin a la col·lecció.
- __isEmpty()__ -> Indica si la col·lecció és buida
- __joinToString()__ -> Converteix la col·lecció a string.

---
# Operacions de col·leccions mutables

- __clear()__ -> Elimina tots els elements d'una col·lecció.
- __add(element)__ -> Afegeix l'element a la col·lecció.
- __remove(element)__ -> Elimina la primera occurrència de l'element a la col·lecció.
- __removeAll(elements)__-> Elimina tots els elements especificats de la col·lecció.
---
# Set
- Col·lecció que no conté duplicats

```
val numbers = setOf(1, 2, 3, 4)
if (numbers.contains(1)) println("1 is in the set")

val numbersBackwards = setOf(4, 3, 2, 1)
println("The sets are equal: ${numbers == numbersBackwards}")
```

```
val studentName = mapOf("Mike" to 9).keys
```

---
# MutableSet

```
val set = mutableSetOf(1,2)
set += 4
set -= 1
```

---
# Associacions 
Volem guardar la nota dels estudiants, ho podriem representar així
```
val studentsName = mutableListOf("Roc", "Santiago", "Ona", "Muhammad")
val studentsMarks = mutableListOf(6, 4, 8, 7)
studentsName.forEachIndexed{index, elem -> println("${elem}=${studentsMarks[index]}")}

```
- Inconvenient, sempre que modifiquem una taula hauriem de modificar l'altre, Font d'errors!
- Per trobar la nota de l'Ona hem de iterar quasi tota la llista

---
# Pair
<div class="mermaid fullwidth center">
classDiagram
    class Pair{
      +first : A
      +second : B
}   
</div>

- El tipus de first i second depen dels arguments que passes quan crides la constructora

```
val associacio: Pair<String, String>  = Pair("Gos", "bup bup")
val associacio = "Gos".to("bup bup")
```
La funció to() té una característica especial, es pot utilitzar sense puntuació! (infix function)

```
val associacio = "Gos" to "bup bup" 
```
---

# Map
```
val students: Map<String, Int> = mapOf(
   "Roc" to 6,
   "Santiago" to 4,
   "Ona" to 8,
   "Muhammad" to 7
)
println(students)
val grade = students["Ona"] // per imprimir la nota de l'Ona ara és directe
```

- Els l "que mapegen", els de la columna esquerra s'anomenen claus: __keys__.
- Els elements que "són mapejats", els de la columna dreta són els valors: __values__.
- L'associació clau-valor (key-value) d'un map s'anomena entrada: __entry__.

---
# Map: buscar valors

mapOf<K, V>(varargs pairs: Pair<K,V>)

```
var nota = students.get("Ona")
var nota = students["Ona"]
```
- __get()__ És una funció que retorna un nullable type
- __getValue()__ retorna un non-nullable type, però si la clau no existeix genera un error i s'atura l'execució.
- __getOrDefault()__
---
# Map : afegir/modificar elements
- Sobre mutableMaps
```
students.put("Ona",10)
students.remove("Santiago")
```
---
# Map<k,v> funcions

```
val numbersMap = mapOf("key1" to 1, "key2" to 2, "key3" to 3, "key4" to 1)

println("All keys: ${numbersMap.keys}")
println("All values: ${numbersMap.values}")

if (numbersMap.containsValue(1)) println("The value 1 is in the map") // same as previous
```
---
# Map operacions
```
students.forEach { entry -> 
    println("L'alumne ${entry.value} ha tret un ${entry.key}") 
}
```
```
students.forEach { (name,mark) -> 
    println("L'alumne ${name} ha tret un ${mark}") 
}
```
---
# Map operacions
```
val matriculaHonor = students.filter { entry -> 
    entry.value.contains(10)
}
```

---
# Mapping a map
```
val newMarks = students
    .mapKeys { entry -> entry.key.replace("Ona", "Meritxell") }
    .mapValues { entry -> entry.value.replace(4, 5) }
```
---
# Init maps
```
val emptyStringToDoubleMap = emptyMap<String, Double>()

val persons = listOf(Person("Mar", 25), Person("Pere", 14))
val personsByName : Map<String, Person> = persons.associateBy{ it.name }

val personsByName2 : Map<String, List<Person>> = persons.groupBy{ it.name }
```
---

# TreeMap
![hashMap](files/red-black.png)

---
# Altres estructures
- [sequences](https://typealias.com/guides/kotlin-sequences-illustrated-guide/)

- [Data structures](https://www.kodeco.com/books/data-structures-algorithms-in-kotlin/v1.0/chapters/3-linked-list)