Liste che crescono

Quanti saranno? Non lo so

Un array fisso vuole la sua dimensione mentre compili. Ma spesso non la sai: quante parole ci sono in un testo? Quanti numeri primi sotto un milione? Quanti voti supereranno la sufficienza? Serve una collezione che parta vuota e cresca man mano, come il DString della lezione precedente, ma per valori di qualsiasi tipo. È la lista, List, e sta nella libreria standard:

import std::io;
import std::collections::list;

fn void main()
{
	List{int} numbers;
	numbers.push(3);
	numbers.push(7);
	numbers.push(1);
	io::printn(numbers);
	io::printfn("len: %d, first: %d", numbers.len(), numbers[0]);
}

[3, 7, 1]
len: 3, first: 3

Tre novità:

• serve un import in più, std::collections::list: le collezioni non fanno parte del nucleo della libreria come io e string;
• List{int} si legge “lista di int”. Il tipo degli elementi va tra graffe, e puoi metterci quello che vuoi: List{String}, List{double}, List{bool}. List è un tipo generico, uno stampo che diventa un tipo vero quando gli dici cosa contiene;
• push aggiunge un elemento in fondo, e la lista si allunga di uno.

Per il resto si usa quasi come un array: numbers[0] legge, numbers[1] = 70; scrive, foreach scorre, printn stampa tutto. Solo la lunghezza si chiede con un metodo, len(), con le parentesi, come per DString.

numbers[1] = 70;
foreach (i, n : numbers) io::printfn("%d: %d", i, n);

0: 3
1: 70
2: 1

Inserire, togliere, cercare

numbers.insert_at(0, 100);    // insert at index 0, the rest shifts right
io::printn(numbers);
numbers.remove_at(1);         // remove index 1, the rest shifts left
io::printn(numbers);
io::printn(numbers.contains(70));
numbers.remove_item(70);      // remove every element equal to 70
io::printn(numbers);
numbers.clear();              // remove everything
io::printfn("empty? %s", numbers.is_empty());

[100, 3, 70, 1]
[100, 70, 1]
true
[100, 1]
empty? true

Gli indici sono controllati come per gli array: numbers[2] su una lista di due elementi ferma il programma con Access out of bounds.

Una lista come slice

Le funzioni che hai scritto nella lezione sulle slice ricevono un int[]. Per passargli il contenuto di una lista, chiedi alla lista una finestra sui suoi elementi con array_view():

fn int sum(int[] values)
{
	int total = 0;
	foreach (v : values) total += v;
	return total;
}

List{int} evens;
for (int i = 1; i <= 20; i++)
{
	if (i % 2 == 0) evens.push(i * i);
}
io::printn(evens);
io::printn(sum(evens.array_view()));
io::printn(sum(evens.array_view()[:3]));   // only the first three

[4, 16, 36, 64, 100, 144, 196, 256, 324, 400]
1540
56

Una volta ottenuta la slice, puoi anche tagliarla come sempre. Attenzione solo a una cosa: non tenere la slice da parte e poi continuare a fare push sulla lista. Quando la lista cresce potrebbe traslocare i suoi elementi in un’altra zona di memoria (lo vedi nel riquadro qui sotto), e la vecchia finestra guarderebbe il vuoto. Chiedi la slice, usala, e richiedila se la lista cambia.

Mettere in ordine

Ordinare è così comune che la libreria standard lo sa fare per te, nel modulo std::sort:

import std::sort;

List{String} names;
names.push("Grace");
names.push("Ada");
names.push("Linus");
names.push("Barbara");
sort::quicksort(&names);
io::printn(names);

int[*] scores = { 27, 18, 30, 22 };
sort::quicksort(&scores);     // works on arrays too
io::printn(scores);

[Ada, Barbara, Grace, Linus]
[18, 22, 27, 30]

quicksort ordina sul posto: non crea una collezione nuova, riordina gli elementi di quella che gli passi. Per questo vuole la &: deve lavorare sull’originale, non su una copia. Numeri dal più piccolo al più grande, stringhe in ordine alfabetico (secondo i codici dei caratteri: le maiuscole vengono prima delle minuscole).

Da dove viene la memoria?

Una lista cresce, quindi ha bisogno di memoria nuova, come le stringhe costruite. E segue le stesse regole:

• una lista dichiarata e usata così com’è, come negli esempi sopra, usa la memoria temporanea. Niente da liberare, ma vale la regola di @pool: una lista nata dentro un @pool muore con lui;

@pool()
{
	List{int} tmp;
	tmp.push_all(&scores);   // push every element of an array
	tmp.push(99);
	io::printn(tmp);
};   // tmp is gone

[18, 22, 27, 30, 99]

• se la lista deve vivere a lungo, la inizializzi con l’allocatore mem dello heap, e quando hai finito la liberi con free():

List{int} kept;
kept.init(mem);    // use the heap
kept.push(1);
kept.push(2);
io::printn(kept);
kept.free();       // give the memory back

[1, 2]

Per gli esercizi di questo corso la memoria temporanea basta e avanza. Nel modulo sulla memoria vedremo come scegliere con criterio.

int[*] grades = { 24, 18, 30, 15, 27, 18, 30, 12, 26, 22 };

import std::io;
import std::collections::list;
import std::sort;

fn double average(int[] values)
{
	int total = 0;
	foreach (v : values) total += v;
	return (double)total / values.len;
}

fn void main()
{
	int[*] grades = { 24, 18, 30, 15, 27, 18, 30, 12, 26, 22 };

	List{int} passed;
	List{int} unique;
	foreach (g : grades)
	{
		if (g >= 18) passed.push(g);
		if (!unique.contains(g)) unique.push(g);
	}

	io::printfn("Passed: %d of %d", passed.len(), grades.len);
	io::printfn("Average of passed: %.1f", average(passed.array_view()));
	io::printfn("Unique: %s", unique);
	sort::quicksort(&unique);
	io::printfn("Sorted: %s", unique);
	io::printfn("Best three: %s", unique.array_view()[^3..]);
}

Ricapitolando

• List{int} (con import std::collections::list;) è una collezione che cresce: parte vuota e si allunga con push.
• Si legge e scrive con l[i], si scorre con foreach, si stampa con printn; la lunghezza è l.len().
• insert_at, remove_at, remove_item, contains, is_empty, clear per modificare e interrogare.
• l.array_view() dà una slice degli elementi, da passare alle funzioni. Non conservarla se la lista cresce.
• sort::quicksort(&x) (con import std::sort;) ordina sul posto liste e array.
• Senza inizializzazione una lista usa la memoria temporanea; con init(mem) usa lo heap, e va liberata con free().

Hai tutti gli strumenti del modulo. È il momento di metterli insieme.