Reverse în Rust

use std::cmp::Reverse;

pub struct Reverse<T>(pub T);

Ce face Reverse

Reverse(x) păstrează valoarea x, dar se compară invers: Reverse(1) > Reverse(5). Valoarea se scoate înapoi cu .0 sau cu un model: let Reverse(x) = r;.

Două utilizări frecvente: BinaryHeap<Reverse<T>> scoate întâi cel mai mic element (min-heap, ca în algoritmul lui Dijkstra), iar v.sort_by_key(|x| Reverse(x.puncte)) sortează descrescător după o cheie, păstrând stabilitatea. În tupluri, poți inversa doar un câmp: (Reverse(puncte), nume) înseamnă puncte descrescător, apoi nume crescător.

Parametri

Parametru	Descriere
T	Tipul valorii învelite; trebuie să fie comparabil (Ord) pentru sortări și heap.

Ce returnează

O valoare Reverse<T>, care se compară invers față de T.

Exemple

Exemplul 1: Min-heap: cel mai mic iese primul

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    for n in [5, 1, 8, 3] {
        heap.push(Reverse(n));
    }
    println!("vârful: {:?}", heap.peek());
    while let Some(Reverse(n)) = heap.pop() {
        print!("{n} ");
    }
    println!();
    println!("Reverse(1) > Reverse(5)? {}", Reverse(1) > Reverse(5));
}

Rezultat

vârful: Some(Reverse(1))
1 3 5 8 
Reverse(1) > Reverse(5)? true

Exemplul 2: Clasament: puncte descrescător, nume crescător

use std::cmp::Reverse;

fn main() {
    let mut elevi = vec![("Mihai", 87), ("Ana", 95), ("Radu", 87), ("Ioana", 92), ("Elena", 95)];
    elevi.sort_by_key(|&(nume, puncte)| (Reverse(puncte), nume));
    for (loc, (nume, puncte)) in elevi.iter().enumerate() {
        println!("{}. {nume} - {puncte}", loc + 1);
    }
}

Rezultat

1. Ana - 95
2. Elena - 95
3. Ioana - 92
4. Mihai - 87
5. Radu - 87

Exemplul 3: Cel mai scurt drum între orașe (Dijkstra)

Heap-ul cu Reverse((distanță, oraș)) dă mereu orașul cel mai apropiat încă neprocesat. Distanțele sunt aproximative, în kilometri.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let orase = ["București", "Ploiești", "Brașov", "Pitești", "Sibiu"];
    let drumuri = [(0, 1, 60), (1, 2, 110), (0, 3, 120), (3, 4, 160), (2, 4, 145), (0, 2, 185)];

    let mut vecini = vec![Vec::new(); orase.len()];
    for &(a, b, km) in &drumuri {
        vecini[a].push((b, km));
        vecini[b].push((a, km));
    }

    let mut dist = vec![u32::MAX; orase.len()];
    let mut heap = BinaryHeap::new();
    dist[0] = 0;
    heap.push(Reverse((0u32, 0usize)));
    while let Some(Reverse((d, oras))) = heap.pop() {
        if d > dist[oras] {
            continue;
        }
        for &(v, km) in &vecini[oras] {
            let nou = d + km;
            if nou < dist[v] {
                dist[v] = nou;
                heap.push(Reverse((nou, v)));
            }
        }
    }
    for (i, nume) in orase.iter().enumerate() {
        println!("București -> {nume:10} {:4} km", dist[i]);
    }
}

Rezultat

București -> București     0 km
București -> Ploiești     60 km
București -> Brașov      170 km
București -> Pitești     120 km
București -> Sibiu       280 km

Greșeli frecvente

• Uiți să desfaci valoarea la pop: primești Reverse(3), nu 3. Folosește while let Some(Reverse(x)) = heap.pop() sau .0.
• Folosești sort() urmat de reverse() pentru ordine descrescătoare când ai criterii secundare: ordinea elementelor egale se inversează și ea. sort_by_key(|x| (Reverse(x.a), x.b)) este precis.
• Uiți importul: cannot find function, tuple struct or tuple variant `Reverse`. Adaugă use std::cmp::Reverse;.

Comenzi înrudite

• BinaryHeap: Coadă de priorități: pop scoate mereu cel mai mare element, iar peek îl arată fără să-l scoată.
• Vec::sort_by: Sortează după o regulă proprie: sort_by primește o funcție de comparare, sort_by_key o cheie calculată din element.
• BinaryHeap::into_sorted_vec: Consumă heap-ul și returnează un Vec cu toate elementele sortate crescător.
• Vec::sort: Sortează vectorul crescător, pe loc. sort este stabilă (păstrează ordinea elementelor egale); sort_unstable e mai rapidă.