How to store different data with relations between them

Question

I have a list of books and a list of authors, where a book is written by a single author and an author may have written many books. How do I encode it in a Rust program?

The requirements:

1. For any given object, accessing the objects in a relation with it should be of low complexity.

2. Impossible states should be prevented. If the data is redundant, incoherence can appear.

An approach:

Each author and book is identified by a unique value (here the index in the table).

struct Book {
    author: usize,
}

struct Author {
    books: Vec<usize>,
}

let books = vec![
    Book { author: 0 },
    Book { author: 0 },
    Book { author: 1 },
];

let authors = vec![
    Author { books: vec![0, 1] },
    Author { books: vec![2] },
];

This approach satisfies the first requirement but not the second. In an implementation, a hash map may be used or the Slab collection to ensure the ids remain valid.

I don't see how to use the Rust type system with the different tools available to make a relation between object satisfying my two requirements.

This is a recurrent pattern in programming, and I might be reinventing the wheel.

Answer 1

I don't know how much help you need; maybe you will find that the following example is trivial.

The ownership of the resources (books and authors) is fully under the control of the library. Because the scenario is very simple (no book or author removal) the relations between these resources only rely on numerical indices. If we needed the ability to remove the resources, some generational indices could help; in this case, some possible failures would have to be considered (Option/Result) when accessing these resources.

In the present scenario, all the details about the indices are hidden from the public interface. Thus, we provide iterators (impl Iterator...) in order to inspect the resources. If the indices had to be exposed in the public interface, a random access would still be possible via the iterators (although providing a slice would probably be more natural).

Note that, because of impl, iterator types are precisely known at the compilation step and will probably be optimized away as if we directly worked on slices with numerical indices in the main program.

// edition = 2021
mod example {
    pub struct Book {
        title: String,
        author_id: usize,
    }
    impl Book {
        pub fn title(&self) -> &str {
            &self.title
        }
    }

    pub struct Author {
        name: String,
        book_ids: Vec<usize>,
    }
    impl Author {
        pub fn name(&self) -> &str {
            &self.name
        }
    }

    pub struct Library {
        books: Vec<Book>,
        authors: Vec<Author>,
    }
    impl Library {
        pub fn new() -> Self {
            Self {
                books: Vec::new(),
                authors: Vec::new(),
            }
        }

        pub fn register_book(
            &mut self,
            book_title: String,
            author_name: String,
        ) {
            let author_id = if let Some(pos) =
                self.authors.iter().position(|x| x.name == author_name)
            {
                pos
            } else {
                self.authors.push(Author {
                    name: author_name,
                    book_ids: Vec::new(),
                });
                self.authors.len() - 1
            };
            self.authors[author_id].book_ids.push(self.books.len());
            self.books.push(Book {
                title: book_title,
                author_id,
            })
        }

        pub fn books(&self) -> impl Iterator<Item = &Book> {
            self.books.iter()
        }

        pub fn authors(&self) -> impl Iterator<Item = &Author> {
            self.authors.iter()
        }

        pub fn author_of(
            &self,
            book: &Book,
        ) -> &Author {
            &self.authors[book.author_id]
        }

        pub fn books_by<'a>(
            &'a self,
            author: &'a Author,
        ) -> impl Iterator<Item = &Book> + 'a {
            author.book_ids.iter().map(|id| &self.books[*id])
        }
    }
}

fn main() {
    let mut library = example::Library::new();
    library.register_book("title A".to_owned(), "name X".to_owned());
    library.register_book("title B".to_owned(), "name X".to_owned());
    library.register_book("title C".to_owned(), "name Y".to_owned());
    println!("~~ inspect by authors ~~");
    for author in library.authors() {
        let titles = library
            .books_by(author)
            .map(|b| format!("{:?}", b.title()))
            .collect::<Vec<_>>();
        println!("author {:?} wrote {}", author.name(), titles.join(", "));
    }
    println!("~~ inspect by books ~~");
    for book in library.books() {
        println!(
            "book {:?} written by {:?}",
            book.title(),
            library.author_of(book).name()
        );
    }
    println!("~~ random access ~~");
    for idx in [2, 3] {
        if let Some(book) = library.books().nth(idx) {
            println!("book {} is {:?}", idx, book.title());
        } else {
            println!("book {} does not exist", idx);
        }
    }
}
/*
~~ inspect by authors ~~
author "name X" wrote "title A", "title B"
author "name Y" wrote "title C"
~~ inspect by books ~~
book "title A" written by "name X"
book "title B" written by "name X"
book "title C" written by "name Y"
~~ random access ~~
book 2 is "title C"
book 3 does not exist
*/