newspaint

Documenting Problems That Were Difficult To Find The Answer To

Implementing Custom Sort For BTree In Rust

So you want to use a std::collections::btree_map::BTreeMap but you want your keys sorted in a different way to the default for the type.

In this example I show how you can provide a BTreeMap that has String keys but sorted in reverse order. But, by altering the cmp() function for the std::cmp::Ord trait for a custom type, you can make the sort in any order you desire.

It is a bit of a pain, however. As this post points out you have to define partial_cmp() and partial_eq() functions from other traits as well, as well as adding the Eq trait to your struct.

// http://rustbyexample.com/custom_types/structs.html
struct RString {
    s: String,
}

use std::cmp::Ord;
use std::cmp::Ordering;

impl PartialEq for RString {
    fn eq(&self, other:&Self) -> bool {
        if self.s == other.s {
            true
        } else {
            false
        }
    }
}

// this does not actually have any methods, it's just a flag on the type
impl Eq for RString { }

// make partial_cmp() just return result from cmp()
impl PartialOrd for RString {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        let me: &String = &(self.s);
        let them: &String = &(other.s);

        Some( me.cmp( them ) )
    }
}

impl Ord for RString {
    fn cmp(&self, other:&Self) -> Ordering {
        let me: &String = &(self.s);
        let them: &String = &(other.s);

        if me > them {
            Ordering::Less
        } else if me < them {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }
}

use std::env;
use std::collections::btree_map::BTreeMap;
fn main() {
    // collect environment variable keys into a vector we can sort
    let mut sortedmap : BTreeMap<Box<RString>,Box<String>> = BTreeMap::new();

    for (key, value) in env::vars() {
        sortedmap.insert(
            Box::<RString>::new( RString { s: key } ),
            Box::<String>::new( value )
        );
    }

    for (key, value) in sortedmap {
        println!( "{} => {}", (*key).s, *value );
    }
}

This could also be implemented using a tuple containing a single element:

// http://rustbyexample.com/custom_types/structs.html
struct RString(String);

use std::cmp::Ord;
use std::cmp::Ordering;

impl PartialEq for RString {
    fn eq(&self, other:&Self) -> bool {
        if self.0 == other.0 {
            true
        } else {
            false
        }
    }
}

// this does not actually have any methods, it's just a flag on the type
impl Eq for RString { }

// make partial_cmp() just return result from cmp()
impl PartialOrd for RString {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        let me: &String = &(self.0);
        let them: &String = &(other.0);

        Some( me.cmp( them ) )
    }
}

impl Ord for RString {
    fn cmp(&self, other:&Self) -> Ordering {
        let me: &String = &(self.0);
        let them: &String = &(other.0);

        if me > them {
            Ordering::Less
        } else if me < them {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }
}

use std::env;
use std::collections::btree_map::BTreeMap;
fn main() {
    // collect environment variable keys into a vector we can sort
    let mut sortedmap : BTreeMap<Box<RString>,Box<String>> = BTreeMap::new();

    for (key, value) in env::vars() {
        sortedmap.insert(
            Box::<RString>::new( RString(key) ),
            Box::<String>::new( value )
        );
    }

    for (key, value) in sortedmap {
        println!( "{} => {}", (*key).0, *value );
    }
}

Note that a tuple’s single element can be accessed through the .0 field.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: