[−][src]Attribute Macro ord_by_key::ord_eq_by_key_selector

#[ord_eq_by_key_selector]

Implements Ord, PartialOrd, PartialEq and Eq for a struct.

Implemented comparison logic is based on a custom key extraction expression provided. During comparison, key extraction expression will be evaluated for both values and then resulted keys will be compared with each other. ord_eq_by_key_selector supports multiple key expressions, which allows implement logic "sort by ..., then by ..."

Syntax

#[ord_eq_by_key_selector(|parameter_name| key_expressoin, key_expressoin, ...)]
pub struct MyStruct {...}

parameter_name - name of the parameter which will contain reference to the struct value from which key is being extracted (type &MyStruct). It can be any identifier (similar to how parameters are defined in a closure).
key_expression - expression which produces a key for comparison. Expression can access parameter_name input and must return impl Ord. Multiple expressions can be provided, comma-separated (last comma is optional). Expression can be single-line, or multi-line enclosed in {}.
pub struct MyStruct {...} - definition of struct for which Ord, PartialOrd, PartialEq and Eq will be implemented

Comparison logic

Let's look at Ord::cmp implementation (rest of traits have similar implementation logic)

When 2 values a and b are compared using auto-implemented comparison method, following logic will be executed:

use specified key_expression, and evaluate comparison keys for a and b (key_a and key_b)
compare key_a and key_b using their own Ord implementaiton
If comparisong result is not ::core::cmp::Ordering::Equal, return comparison reslut
Otherwise switch to next provided key expression and redo steps 1..4 using this expresison
If no key expressions left, return ::core::cmp::Ordering::Equal

Note, all evaluations are lazy and happen only when they are necessary. For example, if first provided key expression gave us non-ambigious result, then rest of key expressions will not be evaluated.

Key Expression implementation considerations and examples

In simple case, key expression returns one of fields from the underlying struct.

use ord_by_key::ord_eq_by_key_selector;
// `Person` will be ordered by it's field `age`
#[ord_eq_by_key_selector(|p| p.age)]
pub struct Person {
    pub first_name: String,
    pub last_name: String,
    pub age: usize,
}

If return type does not implement Copy, expression should return borrowed value

use ord_by_key::ord_eq_by_key_selector;
// `Person` will be ordered by it's field `last_name`
#[ord_eq_by_key_selector(|p| &p.last_name)]
pub struct Person {
    pub first_name: String,
    pub last_name: String,
    pub age: usize,
}

If struct should be sorted by multiple fields, multiple expressions can be provided. Note, that parameter name should be specified only once, and each of expressions can use it

use ord_by_key::ord_eq_by_key_selector;
// `Person` will be ordered by `last_name`, then by `first_name`
#[ord_eq_by_key_selector(|p|
    &p.last_name,
    &p.first_name, )]
pub struct Person {
    pub first_name: String,
    pub last_name: String,
    pub age: usize,
}

If struct should be sorted by some keys in reverse order, you can use ::core::cmp::Reverse container for values which should be sorted in reverse:

use ord_by_key::ord_eq_by_key_selector;
use core::cmp::Reverse;
// `Person` will be ordered by `last_name`, then by `first_name`, then by `age` in reverse
#[ord_eq_by_key_selector(|p|
    &p.last_name,
    &p.first_name,
    Reverse(p.age),)]
pub struct Person {
    pub first_name: String,
    pub last_name: String,
    pub age: usize,
}

You can use multi-line block expression and access multiple fields. You can use explicit return

use ord_by_key::ord_eq_by_key_selector;
// Sort Point by distance from the (0,0)
#[ord_eq_by_key_selector(|p|
    {
        let x = p.x as i64;
        let y = p.y as i64;

        // For sorting purposes, it's not necessary to take square root
        let distance = x * x + y * y;
         
        return distance;
    })]
pub struct Point {
    pub x: i32,
    pub y: i32,
}

Note that all expressions are lazy evaluated every time comparison is triggered. In some applications that can lead to low performance if key expressions are computationally expensive and comparisons happen repeatedly.

Custom sorting logic for existing structs

One of use case is introduction of custom sorting logic to existing structs or different sorting logic for different cases. Example how custom logic is introduces in core library is ::core::cmp::Reverse container (which reverses existing comparison logic), but we can implement more complicated containers.

Let's say, we want to sort integers by their absolute value, and then by the actual value. We cannot introduce new sorting logic to i32 because it already implements Ord, but we can introduce container for i32 which has custom sorting logic. Note that we are using struct with anonymous field and have to access field using .0

use ord_by_key::ord_eq_by_key_selector;
// Container for `i32` will be ordered by absolute value, then by actual value
#[ord_eq_by_key_selector(|i| i.0.abs(), i.0)]
pub struct I32ByAbs(i32);

let a = I32ByAbs(10);
let b = I32ByAbs(-11);

assert!(a < b);

You can use more complicated containers with generic and constraints

use ord_by_key::ord_eq_by_key_selector;
use core::cmp::Reverse;
use std::collections::BinaryHeap;
use std::fmt::Debug;

// Merges sorted iterator and prints final sorted sequence to the console
fn merge_sorted_iterators<T: Ord + Debug, I: Iterator<Item = T>>(iterators: Vec<I>) {
    let mut heap = BinaryHeap::new();

    // Container for iterator and it's last value, ordered by value
    #[ord_eq_by_key_selector(|i| &i.0)]
    // Note that inner struct cannot use generic parameters from the outer function
    // (error[E0401]) so they have to be re-defined with constraints.
    // For the sorting container, the only constraint which we care about is `T : Ord`
    // because we are using the value as a sorting key
    struct ItemIter<T: Ord, I>(T, I);

    for mut iterator in iterators {
        if let Some(item) = iterator.next() {
            // Need to Reverse here because BinaryHeap by default works as max heap
            // and we need min heap
            heap.push(Reverse(ItemIter(item, iterator)));
        }
    }

    while let Some(Reverse(ItemIter(item, mut iterator))) = heap.pop() {
        println!("{:?}", item);

        if let Some(item) = iterator.next() {
            heap.push(Reverse(ItemIter(item, iterator)));
        }
    }
}