1
\$\begingroup\$

Using a hash map and vectors, create a text interface to allow a user to add employee names to a department in a company. For example, “Add Sally to Engineering” or “Add Amir to Sales.” Then let the user retrieve a list of all people in a department or all people in the company by department, sorted alphabetically.

I implemented a solution for the third exercise of Chapter 8 of The Book. I'm still trying to build my intuition for what makes a good Rust program and so would really appreciate some pointers to help me improve. Here's my current solution:

// Using a hash map and vectors, create a text interface to allow a user to
// add employee names to a department in a company. For example, “Add
// Sally to Engineering” or “Add Amir to Sales.” Then let the user retrieve
// a list of all people in a department or all people in the company by
// department, sorted alphabetically.

// @todo Add functions to remove people, departments and companies. Add a clear function.

use std::collections::HashMap;
use std::collections::HashSet;
use std::io;
use std::io::Write;

#[derive(Debug, PartialEq, Eq, Hash, Clone, PartialOrd, Ord)]
struct Employee(String);
#[derive(Debug)]
struct Department(HashSet<Employee>);
#[derive(Debug)]
struct Company(HashMap<String, Department>);

fn make_company() -> Company {
    Company(HashMap::new())
}

#[derive(Debug)]
struct ExistingDepartment(String);

// This assumes all department names are unique.
fn add_department(company: &mut Company, department: &str) -> Result<(), ExistingDepartment> {
    let department_name = String::from(department);
    match company.0.contains_key(&department_name) {
        true => Err(ExistingDepartment(department_name)),
        false => {
            company
                .0
                .insert(department_name, Department(HashSet::<Employee>::new()));
            Ok(())
        }
    }
}

#[derive(Debug)]
enum AddEmployeeError {
    NonexistentDepartment(String),
    ExistingEmployee(Employee),
}

// This assumes that all employee names in a department are unique.
fn add_employee(
    company: &mut Company,
    department_name: &str,
    employee: Employee,
) -> Result<(), AddEmployeeError> {
    match company.0.get_mut(department_name) {
        None => Err(AddEmployeeError::NonexistentDepartment(String::from(
            department_name,
        ))),
        Some(department) => match department.0.insert(employee.clone()) {
            true => Ok(()),
            false => Err(AddEmployeeError::ExistingEmployee(employee)),
        },
    }
}

#[derive(Debug)]
struct NonexistentDepartment(String);

fn get_employees_department(
    company: &Company,
    department_name: &str,
) -> Result<Vec<Employee>, NonexistentDepartment> {
    match company.0.get(department_name) {
        None => Err(NonexistentDepartment(String::from(department_name))),
        Some(department) => {
            let mut result: Vec<Employee> = department.0.iter().cloned().collect();
            result.sort_unstable();
            Ok(result)
        }
    }
}

fn get_employees_company(company: &Company) -> Vec<Employee> {
    let mut result = company
        .0
        .keys()
        .map(|department| get_employees_department(company, department).unwrap())
        .collect::<Vec<Vec<Employee>>>()
        .concat();
    result.sort_unstable();
    result
}

fn format_slice(slice: &[Employee]) -> Option<String> {
    match slice.len() {
        0 => None,
        _ => Some(
            slice
                .iter()
                .map(|employee| employee.0.to_string())
                .collect::<Vec<String>>()
                .join("\n"),
        ),
    }
}

#[derive(PartialEq)]
enum GetInput {
    Print,
    Read,
    Parse,
}

#[derive(PartialEq)]
enum Mode {
    Greet,
    GetInput(GetInput),
    Quit,
}

struct State {
    mode: Mode,
    company: Company,
    input: String,
}

fn make_state() -> State {
    State {
        company: make_company(),
        mode: Mode::Greet,
        input: String::new(),
    }
}

fn print_flush(input: &str) -> Result<(), std::io::Error> {
    print!("{}", input);
    io::stdout().flush()
}

fn read_line(string: &mut String) -> Result<usize, std::io::Error> {
    string.clear();
    io::stdin().read_line(string)
}

// This assumes that department and employee names don't have whitespace.
fn process_input(state: &mut State) {
    let company = &mut state.company;
    match state.input.len() {
        0 => {
            state.mode = Mode::GetInput(GetInput::Print);
        }
        _ => {
            let tokens: Vec<&str> = state.input.split_whitespace().collect();
            match tokens.get(0) {
                None => {
                    state.mode = Mode::GetInput(GetInput::Print);
                }
                Some(token) => match *token {
                    "quit" => {
                        println!("Bye for now!");
                        state.mode = Mode::Quit;
                    }
                    command => {
                        match command {
                            "add-department" => match tokens[1..].len() {
                                0 => println!("Command \"{}\" requires at least 1 argument.", command),
                                _ => tokens[1..].iter().for_each(|element| match add_department(company, element) {
                                    Ok(_) => (),
                                    Err(error) => println!("Error: {:?}", error)
                                })
                            },
                            "add-employee" => match tokens[1..].len() {
                                0 ..= 1 => println!("Command \"{}\" requires at least 2 arguments.", command),
                                _ => match company.0.contains_key(tokens[1]) {
                                    true => tokens[2..].iter().for_each(|employee| match add_employee(company, tokens[1], Employee(employee.to_string())) {
                                        Ok(_) => (),
                                        Err(error) => println!("Error: {:?}", error)
                                    }),
                                    false => println!("Department \"{}\" doesn't exist.", tokens[1])
                                }
                            },
                            "get-employees" => match tokens[1..].len() {
                                0 => println!("Command \"{}\" requires at least 1 argument.", command),
                                _ => tokens[1..].iter().for_each(|department| match company.0.contains_key(*department) {
                                    true => match format_slice(&get_employees_department(company, department).unwrap()) {
                                        None => println!("Department \"{}\" has no employees.", department),
                                        Some(employees) => println!(
                                            "Employees in \"{}\":
{}", department, employees)
                                    },
                                    false => println!("Department \"{}\" doesn't exist.", department)
                                })
                            },
                            "get-employees-all" => match format_slice(&get_employees_company(company)) {
                                None => println!("Company has no employees."),
                                Some(employees) => println!(
                                    "Employees:
{}", employees)
                            },
                            "help" => println!(
                                "Commands:

add-department <department_name [department_name ...]>
  Add one or more departments to the company.

add-employee <department_name> <employee_name [employee_name ...]>
  Add one or more employees to a department.

get-employees <department_name [department_name ...]>
  Print a list of employees from one or more departments.

get-employees-all
  Print a list of all employees in the company.

help
  Print this message.

quit
  Quit."
                            ),
                            command => {
                                println!("Invalid command \"{}\".", command);
                            }
                        }
                        state.mode = Mode::GetInput(GetInput::Print);
                    }
                },
            }
        }
    }
}

fn state_machine(state: &mut State) {
    match &state.mode {
        Mode::Greet => {
            println!(
                "Database program.
Enter \"help\" for a list of commands."
            );
            state.mode = Mode::GetInput(GetInput::Print);
        }
        Mode::GetInput(get_input_step) => match get_input_step {
            GetInput::Print => {
                println!("Company: {:?}", state.company);
                match print_flush("> ") {
                    Ok(_) => {
                        state.mode = Mode::GetInput(GetInput::Read);
                    }
                    Err(error) => println!("Error {:?}", error),
                }
            }
            GetInput::Read => match read_line(&mut state.input) {
                Ok(_) => {
                    state.mode = Mode::GetInput(GetInput::Parse);
                }
                Err(error) => println!("Error: {:?}", error),
            },
            GetInput::Parse => process_input(state),
        },
        Mode::Quit => (),
    }
}

fn repl(function: fn(&mut State), state: &mut State) {
    while state.mode != Mode::Quit {
        function(state)
    }
}

fn main() {
    repl(state_machine, &mut make_state())
}

I previously tried to refactor the process_input function to try to decrease nesting by moving parts of it to different functions, but I ran across borrowing issues so I stopped trying. I also couldn't figure out a nice way to implement it such that it accepts inputs that use the same format as the example (i.e., "Add Amir to Sales"), so I did it a little differently.

I'm also not sure if I'm using the Result type nicely and if the tuple structs and enum I made to pass to them are a good way to do error handling.

I also feel like some of the cloning I did is probably unnecessary, but I'm not sure how I could refactor them away, so it would be nice to know if that is indeed the case and how I might refactor. In fact, I think it would be helpful to know how I might determine when it is appropriate to clone or when to borrow, as I think I'm a little iffy about that topic.

On a related note, how should I go about writing functions? Is it generally better to initially write functions such that they clone their arguments, then try to refactor the cloning away later on, or to try to borrow everything up front then try to fix any borrow-checker issues that crop up and only clone if I can't fix them?

In any case, I'd really appreciate any constructive criticisms and advice.

\$\endgroup\$
4
\$\begingroup\$

Nice to see you again, nicoty :)

Data representation

#[derive(Debug, PartialEq, Eq, Hash, Clone, PartialOrd, Ord)]
struct Employee(String);
#[derive(Debug)]
struct Department(HashSet<Employee>);
#[derive(Debug)]
struct Company(HashMap<String, Department>);

Tuple structs should only be used when the meaning of the fields is clear, especially when the struct is no more than a thin wrapper around an inner value that tweaks certain type-level properties — std::num::Wrapping and std::cmp::Reverse are good examples. In this case, I would name the fields name, employees, and departments, respectively.

Department and Company can have derive(Default). I do not like the fact that Employee implements Ord, though, since names aren't the only logical way to compare employees. Instead, I prefer explicitly specifying this order when sorting (via sort_unstable_by_key, among other methods). It's OK to derive them for pragmatic reasons, I guess.

Code organization

Some of your functions should be made into methods and associated functions:

From To
make_company Company::new
add_department Company::add_department
add_employee Company::get_department_mut + Department::add_employee

etc., with ordinary arguments adjusted into self as appropriate. Company::new, for example, can be implemented using a Default derive:

impl Company {
    fn new() -> Self {
        Self::default()
    }
}

Control flow

I previously tried to refactor the process_input function to try to decrease nesting by moving parts of it to different functions, but I ran across borrowing issues so I stopped trying.

That's unfortunate — separating it into smaller functions is definitely doable and recommended.

Overall, your approach here looks complicated — I didn't expect to see a state machine. Try a simpler approach. I envision a Command struct that parses the first token and dispatches to different methods.

See the rewritten version at the end of this post for inspiration.

error handling

#[derive(Debug)]
struct ExistingDepartment(String);

A full-fledged error type would implement Debug, Display, and Error:

use std::fmt;

#[derive(Debug)]
struct ExistingDepartment(String);

impl fmt::Display for ExistingDepartment {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        format_args!("the department `{:?}` already exists", self.0).fmt(f)
    }
}

impl std::error::Error for ExistingDepartment {}

Alternatively, the thiserror crate might help. Also, error types more often come in enums, like AddEmployeeError:

use thiserror::Error;

#[derive(Debug, Error)]
enum AddEmployeeError {
    #[error("the department `{0}` doesn't exist")]
    NonexistentDepartment(String),
    #[error("the employee `{}` already exists", .0.0)]
    ExistingEmployee(Employee),
}

This is probably an overkill for a simple program.

HashMap insertion

fn add_department(
    company: &mut Company,
    department: &str,
) -> Result<(), ExistingDepartment> {
    let department_name = String::from(department);
    match company.0.contains_key(&department_name) {
        true => Err(ExistingDepartment(department_name)),
        false => {
            company.0.insert(
                department_name,
                Department(HashSet::<Employee>::new()),
            );
            Ok(())
        }
    }
}

company.0 is searched twice — once in contains_key, once in insert. The Entry interface is the preferred solution:

use std::collections::hash_map::Entry;

match company.0.entry(department_name) {
    Entry::Occupied(entry) => {
        Err(ExistingDepartment(entry.key().to_owned()))
    }
    Entry::Vacant(entry) => {
        entry.insert(Department::new());
        Ok(())
    }
}

Instead of cloning department within the function, take the argument by value so that the caller can pass in values they no longer need. If the insertion fails, ownership can be returned to the caller in the error type. (Unfortunately, the key seems to be discarded if the entry is occupied, so I had to use to_owned in that case.)

Cloning

I also feel like some of the cloning I did is probably unnecessary, but I'm not sure how I could refactor them away, so it would be nice to know if that is indeed the case and how I might refactor. In fact, I think it would be helpful to know how I might determine when it is appropriate to clone or when to borrow, as I think I'm a little iffy about that topic.

In principle, we should clone when it is logically appropriate to do so, and avoid cloning otherwise. It all comes down to the semantics.

In practice, it is OK to occasionally spam .clone() when performance is not a big concern — that's what many other languages do automatically under the hood, after all.

Let's take the two explicit clones in your code for example:

// in add_employee

match department.0.insert(employee.clone()) {
    true => Ok(()),
    false => Err(AddEmployeeError::ExistingEmployee(employee)),
}

Here, the clone can be avoided if you use replace instead of insert. (In fact, I'm not sure why HashSet::insert returns a bool rather than a Result<(), T> in the first place.)

// in get_employees_department
let mut result: Vec<Employee> = department.0.iter().cloned().collect();
result.sort_unstable();
Ok(result)

In theory, it is possible to work with references instead, where a Vec<&Employee> is returned. (You can return a reference to the Vec of employees, and leave the sorting to the caller, but that doesn't make the issue go away.)

On a related note, how should I go about writing functions? Is it generally better to initially write functions such that they clone their arguments, then try to refactor the cloning away later on, or to try to borrow everything up front then try to fix any borrow-checker issues that crop up and only clone if I can't fix them?

Personally, I generally go with semantics first — cloning and borrowing as semantically appropriate. As you gain more experience with Rust memory management, you will feel more comfortable translating your internal thoughts to code without the borrow checker being an enemy (from my experience at least).

flat_map

fn get_employees_company(company: &Company) -> Vec<Employee> {
    let mut result = company
        .0
        .keys()
        .map(|department| {
            get_employees_department(company, department).unwrap()
        })
        .collect::<Vec<Vec<Employee>>>()
        .concat();
    result.sort_unstable();
    result
}

You may have realized that using nested Vecs is convoluted and inefficient — flat_map comes to the rescue.

Formatting collections

fn format_slice(slice: &[Employee]) -> Option<String> {
    match slice.len() {
        0 => None,
        _ => Some(
            slice
                .iter()
                .map(|employee| employee.0.to_string())
                .collect::<Vec<String>>()
                .join("\n"),
        ),
    }
}

format from the itertools crate simplifies the function and eliminates unnecessary allocations.

Checking for empty lists also doesn't seem to belong here.

use declarations

use std::collections::HashMap;
use std::collections::HashSet;
use std::io;
use std::io::Write;

You can condense use declarations:

use std::{
    collections::{HashMap, HashSet},
    io::{self, Write},
};

where self (within a path) resolves to the current module.

Miscellaneous

I also couldn't figure out a nice way to implement it such that it accepts inputs that use the same format as the example (i.e., "Add Amir to Sales"), so I did it a little differently.

That's fine — the formulation of the exercise doesn't seem to dictate a particular syntax.

I'm also not sure if I'm using the Result type nicely and if the tuple structs and enum I made to pass to them are a good way to do error handling.

See the "Data representation" and "Error handling" sections above.

Rewritten version

Here's the rewritten version as promised. I made some simplifications for ease of demonstration. (External crates used: indoc itertools thiserror)

src/main.rs

pub mod data;
pub mod repl;

use repl::Repl;

fn main() {
    Repl::new().run()
}

src/data.rs

use {
    itertools::Itertools,
    std::collections::{hash_map, HashMap, HashSet},
    thiserror::Error,
};

#[derive(Clone, Debug, Default)]
pub struct Company {
    departments: HashMap<String, Department>,
}

impl Company {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn add_department(&mut self, department: String) -> Result<()> {
        use hash_map::Entry;

        match self.departments.entry(department) {
            Entry::Occupied(entry) => {
                Err(Error::ExistingDepartment(entry.key().to_owned()))
            }
            Entry::Vacant(entry) => {
                entry.insert(Department::new());
                Ok(())
            }
        }
    }

    pub fn add_employee(
        &mut self,
        department: &str,
        employee: String,
    ) -> Result<()> {
        match self
            .departments
            .get_mut(department)
            .ok_or_else(|| Error::InvalidDepartment(department.to_owned()))?
            .employees
            .replace(employee)
        {
            Some(employee) => Err(Error::ExistingEmployee(employee)),
            None => Ok(()),
        }
    }

    pub fn get_departments(&self) -> Vec<String> {
        self.departments.keys().cloned().sorted_unstable().collect()
    }

    pub fn get_all_employees(&self) -> Vec<String> {
        self.departments
            .values()
            .flat_map(|department| department.employees.iter().cloned())
            .sorted_unstable()
            .collect()
    }

    pub fn get_employees(&self, department: &str) -> Result<Vec<String>> {
        Ok(self
            .departments
            .get(department)
            .ok_or_else(|| Error::InvalidDepartment(department.to_owned()))?
            .employees
            .iter()
            .cloned()
            .sorted_unstable()
            .collect())
    }
}

#[derive(Clone, Debug, Default)]
pub struct Department {
    employees: HashSet<String>,
}

impl Department {
    pub fn new() -> Self {
        Self::default()
    }
}

#[derive(Debug, Error)]
pub enum Error {
    #[error("department `{0}` already exists")]
    ExistingDepartment(String),
    #[error("employee `{0}` already exists")]
    ExistingEmployee(String),
    #[error("invalid department `{0}`")]
    InvalidDepartment(String),
}

type Result<T> = std::result::Result<T, Error>;

src/repl.rs

use {
    crate::data, indoc::indoc, itertools::Itertools, std::ops::RangeInclusive,
    thiserror::Error,
};

#[derive(Debug, Default)]
pub struct Repl {
    data: data::Company,
}

impl Repl {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn run(mut self) {
        loop {
            let directive = input("> ");
            let tokens: Vec<&str> = directive.split_whitespace().collect();

            let (command, args) = match tokens.split_first() {
                Some((command, args)) => (*command, args),
                None => continue,
            };

            let result = match command {
                "add_department" => self.add_department(args),
                "add_employee" => self.add_employee(args),
                "get_departments" => self.get_departments(args),
                "get_employees" => self.get_employees(args),
                "help" => {
                    eprint!("\n{}\n\n", HELP_TEXT);
                    Ok(())
                }
                "quit" => return,
                _ => Err(Error::InvalidCommand(command.to_owned())),
            };

            if let Err(error) = result {
                eprintln!("! Error: {}", error);
            }
        }
    }

    fn add_department(&mut self, args: &[&str]) -> Result<()> {
        Self::check_arg_count(args, 1)?;

        self.data
            .add_department(args[0].to_owned())
            .map_err(|error| error.into())
    }

    fn add_employee(&mut self, args: &[&str]) -> Result<()> {
        Self::check_arg_count(args, 2)?;

        self.data
            .add_employee(args[0], args[1].to_owned())
            .map_err(|error| error.into())
    }

    fn get_departments(&self, args: &[&str]) -> Result<()> {
        Self::check_arg_count(args, 0)?;

        let departments = self.data.get_departments();
        println!("{}", departments.iter().format("\n"));

        Ok(())
    }

    fn get_employees(&self, args: &[&str]) -> Result<()> {
        let employees = match &args[..] {
            [] => self.data.get_all_employees(),
            [department] => self.data.get_employees(department)?,
            _ => {
                return Err(Error::ArgumentCountRange {
                    expected: 0..=1,
                    found: args.len(),
                })
            }
        };
        println!("{}", employees.iter().format("\n"));

        Ok(())
    }

    fn check_arg_count(args: &[&str], expected: usize) -> Result<()> {
        let arg_count = args.len();

        if arg_count == expected {
            Ok(())
        } else {
            Err(Error::ArgumentCount {
                expected,
                found: arg_count,
            })
        }
    }
}

#[derive(Debug, Error)]
enum Error {
    #[error("expected {expected} arguments, found {found}")]
    ArgumentCount { expected: usize, found: usize },
    #[error(
        "expected {} to {} arguments, found {found}",
        .expected.start(), .expected.end(),
    )]
    ArgumentCountRange {
        expected: RangeInclusive<usize>,
        found: usize,
    },
    #[error(transparent)]
    Database(#[from] data::Error),
    #[error("invalid command `{0}`")]
    InvalidCommand(String),
}

type Result<T> = std::result::Result<T, Error>;

fn input(prompt: &str) -> String {
    eprint!("{}", prompt);

    let mut input = String::new();
    std::io::stdin()
        .read_line(&mut input)
        .expect("cannot read input");

    input
}

const HELP_TEXT: &str = indoc! { "
    add_department <department_name>
        Add a department to the company.

    add_employee <department_name> <employee_name>
        Add an employee to a department.

    get_departments
        Print a list of all departments.

    get_employees [<department_name>]
        Print a list of all employees or employees from a department.

    help
        Print this message.

    quit
        Quit.
" };
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.