Summary - Advanced traits

Combine associated types and supertraits to write a Graph trait.

Advanced traits summary

Associated types (type Oge;) are types an implementation picks once; associated constants (const N: u32;) are compile-time values belonging to the type. GATs add a lifetime or type parameter to an associated type. Supertraits (trait A: B) declare dependencies. The newtype pattern works around the orphan rule and gives type safety. Together these tools let you define abstract structures like graphs independently of types.

A graph trait

When algorithms are written over a trait, they work with any graph representation (adjacency list, matrix):

trait Graf {
    type Dugum;
    fn komsular(&self, d: &Self::Dugum) -> Vec<Self::Dugum>;
    fn kenar_sayisi(&self) -> usize;
}

struct KomsulukListesi(Vec<Vec<usize>>);

impl Graf for KomsulukListesi {
    type Dugum = usize;
    fn komsular(&self, d: &usize) -> Vec<usize> {
        self.0[*d].clone()
    }
    fn kenar_sayisi(&self) -> usize {
        self.0.iter().map(|k| k.len()).sum()
    }
}

Exercise Graph

Write the Graf trait above and the KomsulukListesi implementation. For the graph vec![vec![1, 2], vec![2], vec![0]], print the neighbours of node 0 ({:?}) and the number of edges, separated by a space.

Show example solution

trait Graf {
    type Dugum;
    fn komsular(&self, d: &Self::Dugum) -> Vec<Self::Dugum>;
    fn kenar_sayisi(&self) -> usize;
}

struct KomsulukListesi(Vec<Vec<usize>>);

impl Graf for KomsulukListesi {
    type Dugum = usize;
    fn komsular(&self, d: &usize) -> Vec<usize> {
        self.0[*d].clone()
    }
    fn kenar_sayisi(&self) -> usize {
        self.0.iter().map(|k| k.len()).sum()
    }
}

fn main() {
    let g = KomsulukListesi(vec![vec![1, 2], vec![2], vec![0]]);
    println!("{:?} {}", g.komsular(&0), g.kenar_sayisi());
}

Test yourself

In a <code>Graf</code> trait, why should the node type be an associated type?
- For performance
- It isn't needed
- Each graph structure has a single node type and it needn't be written when using it
- Generics are forbidden
Show answer

Each graph structure has a single node type and it needn't be written when using it — Signatures like fn yol<G: Graf>(g: &G, a: G::Dugum) stay simple; with a generic parameter, Graf<D> would need D everywhere.

Node type

impl Graf for KomsulukListesi {
    type ____ = usize;
    ..
}

Show answer

impl Graf for KomsulukListesi {
    type Dugum = usize;
    ..
}

Group summary

type X;

Associated type
const N: u32;

Associated constant
trait A: B

Supertrait
struct W(T);

Newtype

Next lesson: [T; N]

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies