Model nested categories with HashMaps

Hi,

I'm trying to model nested categories using HashMaps as a learning exercise. I imagine this is easier using Vecs which I may try after this. Anyway, I have a bug where only one of the subcategories is being added, the other subcategories end up as root categories. I'm guessing I'm not inserting a new HashMap node correctly. Any pointers greatly welcomed. Thanks

extern crate serde;

use serde::{Deserialize, Serialize};
use serde::__private::TryFrom;
use std::cmp::{PartialEq, PartialOrd};
use std::collections::HashMap;

#[derive(Clone, Deserialize, Serialize, Debug)]
struct CategoryName(String);

impl TryFrom<String> for CategoryName {
    type Error = ();

    fn try_from(n: String) -> Result<Self, Self::Error> {
        if n.is_empty() {
            Err(())
        } else {
            Ok(Self(n))
        }
    }
}

impl From<CategoryName> for String {
    fn from(n: CategoryName) -> Self {
        n.0
    }
}

#[derive(PartialEq, Clone, PartialOrd, Ord, Eq, Serialize, Deserialize, Hash, Debug)]
struct CategoryId(u32);

impl TryFrom<u32> for CategoryId {
    type Error = ();

    fn try_from(n: u32) -> Result<Self, Self::Error> {
        if n > 0 && n <= u32::MAX {
            Ok(Self(n))
        } else {
            Err(())
        }
    }
}

impl From<CategoryId> for u32 {
    fn from(c: CategoryId) -> Self {
        c.0
    }
}

struct Category {
    id: CategoryId,
    name: CategoryName,
    subcats: HashMap<CategoryId, Category>,
}

impl Category {
    fn new(id: CategoryId, name: CategoryName) -> Category {
        Category {
            id,
            name,
            subcats: HashMap::new(),
        }
    }

    fn add_subcat(&mut self, id: CategoryId, cat: Category) {
        self.subcats.entry(id).or_insert_with(|| cat);
    }
}

fn main() {
    let cat = Category::new(
        CategoryId::try_from(1).unwrap(),
        CategoryName::try_from("test".to_string()).unwrap(),
    );

    let mut catmap = HashMap::from([(cat.id.clone(), cat)]);

    let cat2 = Category::new(
        CategoryId::try_from(2).unwrap(),
        CategoryName::try_from("test2".to_string()).unwrap(),
    );

    // This adds another top-level category
    catmap.insert(cat2.id.clone(), cat2);

    // prepare some subcategories
    let cat3 = Category::new(
        CategoryId::try_from(3).unwrap(),
        CategoryName::try_from("test3".to_string()).unwrap(),
    );

    let cat4 = Category {
        id: CategoryId::try_from(4).unwrap(),
        name: CategoryName::try_from("test4".to_string()).unwrap(),
        subcats: HashMap::new(),
    };

    let cat5 = Category {
        id: CategoryId::try_from(5).unwrap(),
        name: CategoryName::try_from("test5".to_string()).unwrap(),
        subcats: HashMap::new(),
    };

    // add first subcategory under cat2
    catmap
        .get_mut(&CategoryId(2))
        .unwrap()
        .add_subcat(cat3.id.clone(), cat3);

    // add second subcategory under cat2
    catmap
        .get_mut(&CategoryId(2))
        .unwrap()
        .add_subcat(cat4.id.clone(), cat4);

    // add third subcategory under cat2, directly accessing the subcats field
    catmap
        .get_mut(&CategoryId(2))
        .unwrap()
        .subcats
        .entry(cat5.id.clone())
        .or_insert_with(|| cat5);

    print_cat(&catmap);
}

// Only one of the subcategories is under cat2 (it is random which one), the others are top level categories!!!
fn print_cat(catmap: &HashMap<CategoryId, Category>) {
    for (id, cat) in catmap {
        print!("id: {:?}, name: {:?} ", id, cat.name);
        if !cat.subcats.is_empty() {
            print!("\n  sub {:?}: ", id);
            print_cat(&cat.subcats);
        } else {
            println!(" () ");
        }
    }
}

(Playground)

Output:

id: CategoryId(1), name: CategoryName("test")  () 
id: CategoryId(2), name: CategoryName("test2") 
  sub CategoryId(2): id: CategoryId(3), name: CategoryName("test3")  () 
id: CategoryId(4), name: CategoryName("test4")  () 
id: CategoryId(5), name: CategoryName("test5")  () 

Errors:

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 0.75s
     Running `target/debug/playground`

Your insertion logic is correct. Your printing logic is wrong. Calling print_cat recursively for subcat, without passing your sub as a prefix to print before every line will cause every sub-cat except the first (because you use print! instead of println!) to perform the same prints, just as if they were in the top-level map. This might print something that is more to your liking:

fn print_cat(catmap: &HashMap<CategoryId, Category>, prefix: &str) {
    for (id, cat) in catmap {
        print!("{prefix} id: {:?}, name: {:?} ", id, cat.name);
        if !cat.subcats.is_empty() {
            println!();
            let prefix = format!("{prefix}    sub {id:?}: ");
            print_cat(&cat.subcats, &prefix);
        } else {
            println!(" () ");
        }
    }
}

Playground.

STDOUT:

id: CategoryId(2), name: CategoryName("test2") 
    sub CategoryId(2):  id: CategoryId(3), name: CategoryName("test3")  () 
    sub CategoryId(2):  id: CategoryId(4), name: CategoryName("test4")  () 
    sub CategoryId(2):  id: CategoryId(5), name: CategoryName("test5")  () 
 id: CategoryId(1), name: CategoryName("test")  () 
1 Like

Amazing, thank you so much!

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.