README.md

Direct ports of the standard library's BTreeMap, BTreeSet and BinaryHeap collections, but which sort according to a specified TotalOrder rather than relying upon the Ord trait.

This is primarily useful when the TotalOrder depends upon runtime state, and therefore cannot be provided as an Ord implementation for any type.

Lookup keys

In the standard library's collections, certain lookups can be performed using a key of type &Q where the collection's storage key type K implements Borrow<Q>; for example, one can use &str keys to perform lookups into collections that store String keys. This is possible because String: Borrow<str> and the Borrow trait stipulates that borrowed values must preserve Ord order.

However, copse's collections do not use the Ord trait; instead, lookups can only ever be performed using the TotalOrder of type O that was supplied upon collection creation. This total order can only compare values of its OrderedType associated type, and hence keys used for lookups must implement SortableBy<O> in order that the sort key can be extracted.

Example

use copse::{BTreeSet, SortableBy, TotalOrder};
use std::cmp::Ordering;

// define a total order
struct OrderByNthByte {
    n: usize, // runtime state
}

impl TotalOrder for OrderByNthByte {
    type OrderedType = [u8];
    fn cmp(&self, this: &[u8], that: &[u8]) -> Ordering {
        this.get(self.n).cmp(&that.get(self.n))
    }
}

// define lookup key types for collections sorted by our total order
impl SortableBy<OrderByNthByte> for [u8] {
    fn sort_key(&self) -> &[u8] { self }
}
impl SortableBy<OrderByNthByte> for str {
    fn sort_key(&self) -> &[u8] { self.as_bytes() }
}
impl SortableBy<OrderByNthByte> for String {
    fn sort_key(&self) -> &[u8] { SortableBy::<OrderByNthByte>::sort_key(self.as_str()) }
}

// create a collection using our total order
let mut set = BTreeSet::new(OrderByNthByte { n: 9 });
assert!(set.insert("abcdefghijklm".to_string()));
assert!(!set.insert("xxxxxxxxxjxx".to_string()));
assert!(set.contains("jjjjjjjjjj"));

Collection type parameters

In addition to the type parameters familiar from the standard library collections, copse's collections are additionally parameterised by the type of the TotalOrder. If the total order is not explicitly named, it defaults to the OrdTotalOrder for the storage key's OrdKeyType, which yields behaviour analagous to the standard library collections (i.e. sorted by the Ord trait); explicitly using these items indicates that you could (and probably should) ditch copse for the standard library instead.

Crate feature flags

This crate defines a number of feature flags, none of which are enabled by default:

• the std feature provides OrdStoredKey implementations for some standard library types that are not present in libcore + liballoc, namely OsString, OsStr, PathBuf and Path;

• each feature in the unstable set corresponds to the like-named unstable feature in the standard library's B-Tree and BinaryHeap collection implementations, all of which enable APIs that are wholly contained within the library and therefore do not require a nightly toolchain;

• the btreemap_alloc feature corresponds to the like-named unstable feature in the standard library's B-Tree collection implementations (namely that which enables their new_in associated functions)—however (as of rustc v1.66.1) this feature requires the allocator_api unstable compiler feature that is only available with a nightly toolchain; and

• all other features (combined into the nightly set) do not affect the APIs presented by this crate, but instead switch the implementation to use those features internally as are used by the standard library's implementations—these features should be of little use or interest to library users, but are nevertheless included to ease synchronisation with the standard library.