Sorting items of different types

help
1

Hello.

I am looking to sort a list of different item types. In Rust I see the items have to be of the same type. I have gone with serde_json to be able to accept different inputs and am using serde_json::Value items in a vector or Array structure from that crate. For example:

let data: Value = serde_json::from_str(r#"[3, 1, "1"]"#).unwrap();
// expected after sort: [1, "1", 3]

I need to sort this, but it seems the sort function is not able to easily be used on this data structure. I get this error:

data.sort();
...
the trait bound `serde_json::Value: Ord` is not satisfied
the trait `Ord` is not implemented for `serde_json::Value`
slice.rs(207, 5): required by a bound in `slice::<impl [T]>::sort`

the trait bound `Value: Ord` is not satisfied
the trait `Ord` is not implemented for `Value`
slice.rs(207, 5): required by a bound in `slice::<impl [T]>::sort`

I am not sure how to implement Ord on this, as I thought I can only define a trait for something that I own and this comes from an external crate.

I have tried to implement my own sort function for this, but not sure I am going in the right direction. I have a few edge cases and seems convoluted for achieving this.

Any suggestions or hints for this are very welcome.

2

You won't be able to sort a Value unless it is a Value::Array, right? So the first thing would be to match and get the array out as a Vec<Value>. Then to sort the Vec<Value>, since you can't implement Ord for Value, use sort_by and pass your custom sort function.

3

Instead of a custom sort function you can write a custom order function, one which you can pass to sort_by. Alternatively you can also consider the less flexible but easier to user sort_by_key.

That said you may get better help if you explain precisely what order you're precisely looking for. For example common orders between numbers and "equivalent" strings often don't agree (for example 2 < 11 but "2" > "11", so how would [2, 11, "2", "11"] be sorted?). What if your array contains objects, other arrays, null and/or booleans?

2 Likes
4

You can't, but you can always define your own newtype around Value, and implement Ord on that.

5

Interesting suggestions. I had read about some of these but wondered what is the most appropriate way.

In the example above I only have strings and integers, but this would expand to booleans, arrays, hashes etc. I was looking to sort based on how you can sort arrays in other languages and this is where this example came from.

To define a type around Value, would this be a struct for MyValue or another way to do this?

When using the custom sort function I did run into the same errors about Ord as I put in the question. I was having to convert to string as I did not find a way to use cmp directly on the a and b items.

a.as_str().cmp(&b.as_str())
1 Like
6

When implementing a custom sort function on Value you will have to access each variant of Value and do the comparison you want for that type. This is the minimum required to implement comparison in a collection of mixed types. Please post more code to help us to answer.

7

If you aren’t tied to serde_json and aren’t too particular about how items are sorted, you can define your own enum and use #[derive] to make it sortable, as long as each of its field types is sortable. This will sort first by the enum discriminant, and then by the values of the fields:

#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
enum MyValue {
    A(String),
    B(i32),
    C(bool),
}

fn main() {
    let mut v = [
        MyValue::C(false),
        MyValue::A("foo".into()),
        MyValue::B(3),
        MyValue::A("bar".into()),
        MyValue::B(1),
        MyValue::B(2),
    ];
    v.sort();
    println!("{:?}", v);
    // [A("bar"), A("foo"), B(1), B(2), B(3), C(false)]
}
3 Likes
8

Thank you for this suggestion. I am not tied to serde_json and this does seem to offer a similar approach to allowing different data types.

For sorting, is there a way to get the output for example as [1, "1", 3] or is this not possible? I like the approach that enum defines the order, but not sure if I can sort by value first or what the options are.

9

You have to incorporate the type somehow. I reckon you have converting strings to numbers in mind. But what do you do if your list contains null, or another list, or an object? How do you define "sorting by value" on those?

The TL;DR is you can do whatever you want, but some options won't make any sense.

10

Instead of using serde_json, which will serialize and deserialize your data, you can just use an enum. Sorting the values requires the Ord trait to be implemented, which in turn needs the PartialOrd, PartialEq, and Eq traits implemented. Here is some sample code.

#[derive(Debug)]
enum MyValue {
    Number(i32),
    Text(String),
}

impl Ord for MyValue {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // your code
    }
}

impl PartialOrd for MyValue {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        //your code
    }
}

impl PartialEq for MyValue {
    fn eq(&self, other: &Self) -> bool {
        //your code
    }
}

impl Eq for MyValue {}

fn main() {
    let mut v: Vec<MyValue> = vec![
        MyValue::Number(42),
        MyValue::Number(4),
        MyValue::Text(String::from("hello")),
    ];
    println!("{:?}", v);
    v.sort();
    println!("{:?}", v);
}

You can view the documentation here. I hope this helps!

1 Like
11

Thank you for the suggestions. I have implemented my own enum and also a struct to achieve the sorting. Can I sort inside another function, as I am using a reference. I tried to clone the data, but it seems to clone the reference.

trait Notation {
  fn notate(&self) -> String;
}

impl Notation for [Value] {
  fn notate(&self) -> String {
    format!(
      "{}A",
      &self.iter().map(|x| x.notate()).collect::<String>()
    )
  }
}

I am currently doing data.sort() in the test, but wondered if notate could sort the data. I made it not a reference but got an error with the integers. I am currently using &self but most of the types work without the reference.

impl Notation for [i32] {
  fn notate(self) -> String {
    format!(
      "{}A",
      self.iter().map(|x| x.notate()).collect::<String>()
    )
  }
}

function arguments must have a statically known size, borrowed types always have a known size: `&`
the size for values of type `[i32]` cannot be known at compilation time
12

It is very difficult to understand what exactly you did and what problems you had, because you didn't post the code with the problems or post the errors. Please take one problem at a time and post the details.

13

[i32] is dynamically-sized. You'll have to pass it by reference (&self) and not by value. (Ie., the problem has nothing to do with "integers".)

1 Like
14

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.