Define a comparable for my custom struct

[bitshark]

Hi all, I've created a custom struct that is of this shape:

struct User{
    surname: String,
    name: String,
    interests: HashMap<String, String>,
}

now I want to define an order for my struct in a way that I can pull in a TreeSet for instance.
My ordering rule is: surname first, if they are the same then order by name.
It this is also the same then use the interest map in this way:

• compare keys first,
• if keys are the same, compare the values
• do this until you consume all entries from left and right. When you are done, if you found all equals, then return left.size - right.size.

in practice, this is an implementation in Kotlin of the above interests:

 private val interestsComparator =
            Comparator<Set<Map.Entry<String, String>>> { first, second ->
                first.asSequence()
                    .zip(second.asSequence())
                    .map { (first, second) -> entryComparator.compare(first, second) }
                    .filter { it != 0 }
                    .firstOrNull()
                    ?: (first.size - second.size)
            }

private val entryComparator: Comparator<Map.Entry<String, String>> = compareBy(
            { it.key },
            { it.value }
        )

I've tried deriving partEq and friends but of course the hashmap comparison is not defined.. So I was trying myself but the code that I came up with starts to bee too verbose (I should add ifs, elses and such) so I wonder if I can use a more modern implementation like the one above..

On a side note, I've spent some time reading why I needed to implement Ord, PartEq, PartOrd, Eq.. that really seems overkill to me when I can just define a comparator.. do you have any link that you can point me to study why's that in the rust world? I've been more confused after reading the official doc

For completeness, I'm attaching my file here. Maybe you can also give some suggestions on the tests (I've tried to use string constants but it's a no-no from rust compiler

#[derive(Eq, Debug)]
pub struct User {
    name: String,
    surname: String,
    interests: HashMap<String, String>,
}

impl User {
    pub fn create(
        name: String,
        surname: String,
        interests: HashMap<String, String>,
    ) -> User {
        User {
            name,
            surname,
            interests,
        }
    }
}

impl Ord for User {
    fn cmp(&self, other: &Self) -> Ordering {
        self.name
            .cmp(&other.name)
            .then(self.surname.cmp((&other.surname)))
            //now what?
    }
}

impl PartialOrd for User {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other)) // why I need to do this again?
    }
}

impl PartialEq for User {
    fn eq(&self, other: &Self) -> bool {
        self.name == other.name
            && self.surname == other.surname
            && self.interests == other.interests
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn it_orders_with_name_first() {
        let first_user = User::create(
            String::from("name0"),
            String::from("surname1"),
            HashMap::new(),
        );
        let second_user = User::create(
            String::from("name1"),
            String::from("surname0"),
            HashMap::new(),
        );
        let mut users = BTreeSet::new();
        users.insert(&second_user);
        users.insert(&first_user);
        let first = users.into_iter().next().unwrap();
        assert_eq!(&first_user, first)
    }

    #[test]
    fn it_orders_with_same_name_but_different_surname() {
        let first_user = User::create(
            String::from("name0"),
            String::from("surname0"),
            HashMap::new(),
        );
        let second_user = User::create(
            String::from("name0"),
            String::from("surname1"),
            HashMap::new(),
        );
        let mut users = BTreeSet::new();
        users.insert(&second_user);
        users.insert(&first_user);
        let first = users.into_iter().next().unwrap();
        assert_eq!(&first_user, first)
    }
}

[alice]

It sounds like you should really be using a BTreeMap rather than a HashMap. Otherwise the keys may appear in any order, and not necessarily in the same order for two otherwise equal maps.

[bitshark]

that's a fair point, true. The reason why I'm using a map is because there is an assumption that those entries are given ordered. So I can avoid the extra complexity of adding them in a sorted data structure..

[alice]

A HashMap does not preserve insertion ordering, or any other ordering for that matter. Two different hash maps with the same values inserted in the same order are not guaranteed to yield them in the same order when iterated.

[bitshark]

that's true, thanks! so say that instead of a BTreeMap I want to use an ordered list of pairs, so at least I can avoid paying the price of ordered something that is already ordered.. do you have any suggestions on how can I achieve the ordering as described above?

[alice]

Are you sure that you want to compare the length at the end? I think you will get an inconsistent ordering if you do so. Anyway, here is what you asked for:

use std::cmp::Ordering;

#[derive(Eq, PartialEq)]
struct User {
    surname: String,
    name: String,
    interests: Vec<(String, String)>,
}

impl PartialOrd for User {
    fn partial_cmp(&self, other: &User) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for User {
    fn cmp(&self, other: &User) -> Ordering {
        let mut ord = self.surname.cmp(&other.surname)
            .then_with(|| self.name.cmp(&other.name));
        
        for ((a, _), (b, _)) in self.interests.iter().zip(&other.interests) {
            if ord != Ordering::Equal {
                return ord;
            }
            ord = a.cmp(b);
        }
        
        for ((_, a), (_, b)) in self.interests.iter().zip(&other.interests) {
            if ord != Ordering::Equal {
                return ord;
            }
            ord = a.cmp(b);
        }
        
        ord.then(self.interests.len().cmp(&other.interests.len()))
    }
}

[bitshark]

thanks Alice, just a quick iterative question, when should I choose what to derive and what not to derive?
Also, I've seen you implemented PartialOrd with a standard delegate comparison. Why's that?

[alice]

I simply chose the option that lead to me writing the least amount of code. You can only use derives when they give you the implementation you want, but in this case deriving PartialOrd does not give us the one we want (instead it gives one that alternatives between checking keys and values for the tuple case). I delegate the PartialOrd because you can always delegate it if you also implement Ord.

[bitshark]

Gotcha, so how did you know the default implementations for the different derives? is there a command I can use to see what they will look like?

@alice

I delegate the PartialOrd because you can always delegate it if you also implement Ord .

Does this mean that it's pretty much the same as of having the following then?

#[derive(Eq, PartialEq, PartialOrd)]

[alice]

I don't remember where I found out what the default implementation is, but there is a tool called cargo expand that you can use to see what they look like. You don't want to derive PartialOrd because it is not going to call the Ord impl like I did.