compare/lib.rs
1//! Comparators.
2//!
3//! A comparator is any type that implements the [`Compare`](trait.Compare.html) trait,
4//! which imposes a [total order](https://en.wikipedia.org/wiki/Total_order). Its
5//! [`compare`](trait.Compare.html#tymethod.compare) method accepts two values, which may
6//! be of the same type or different types, and returns an ordering on them.
7//!
8//! Comparators are useful for parameterizing the behavior of sort methods and certain
9//! data structures.
10//!
11//! The most basic comparator is [`Natural`](struct.Natural.html), which simply delegates
12//! to the type's implementation of [`Ord`]
13//! (http://doc.rust-lang.org/std/cmp/trait.Ord.html):
14//!
15//! ```
16//! use compare::{Compare, natural};
17//! use std::cmp::Ordering::{Less, Equal, Greater};
18//!
19//! let a = &1;
20//! let b = &2;
21//!
22//! let cmp = natural();
23//! assert_eq!(cmp.compare(a, b), Less);
24//! assert_eq!(cmp.compare(b, a), Greater);
25//! assert_eq!(cmp.compare(a, a), Equal);
26//! ```
27//!
28//! There are convenience methods for checking each of the six relations:
29//!
30//! ```
31//! use compare::{Compare, natural};
32//!
33//! let a = &1;
34//! let b = &2;
35//!
36//! let cmp = natural();
37//! assert!(cmp.compares_lt(a, b));
38//! assert!(cmp.compares_le(a, b));
39//! assert!(cmp.compares_ge(b, a));
40//! assert!(cmp.compares_gt(b, a));
41//! assert!(cmp.compares_eq(a, a));
42//! assert!(cmp.compares_ne(a, b));
43//! ```
44//!
45//! The `Compare` trait also provides default methods that
46//! consume a comparator to produce a new one with different behavior, similar to
47//! [iterator adaptors](http://doc.rust-lang.org/std/iter/trait.IteratorExt.html). For
48//! example, all comparators can be [reversed](trait.Compare.html#method.rev):
49//!
50//! ```
51//! use compare::{Compare, natural};
52//! use std::cmp::Ordering::Greater;
53//!
54//! let cmp = natural().rev();
55//! assert_eq!(cmp.compare(&1, &2), Greater);
56//! ```
57//!
58//! It is possible to implement a comparator that is not based on the natural ordering of
59//! a type by using a closure of type `Fn(&L, &R) -> Ordering`. For example, slices
60//! can be compared by their length instead of their contents:
61//!
62//! ```
63//! use compare::Compare;
64//! use std::cmp::Ordering::{Less, Greater};
65//!
66//! let a = [1, 2, 3];
67//! let b = [4, 5];
68//!
69//! let cmp = |l: &[i32], r: &[i32]| l.len().cmp(&r.len());
70//! assert_eq!(cmp.compare(&a, &b), Greater);
71//!
72//! let cmp = cmp.rev();
73//! assert_eq!(cmp.compare(&a, &b), Less);
74//! ```
75//!
76//! Comparators can be combined [lexicographically]
77//! (https://en.wikipedia.org/wiki/Lexicographical_order) in order to compare values
78//! first by one key, [then](trait.Compare.html#method.then), if the first keys were
79//! equal, by another:
80//!
81//! ```
82//! use compare::Compare;
83//! use std::cmp::Ordering::{Less, Equal, Greater};
84//!
85//! struct Pet { name: &'static str, age: u8 }
86//!
87//! let fido4 = &Pet { name: "Fido", age: 4 };
88//! let ruff2 = &Pet { name: "Ruff", age: 2 };
89//! let fido3 = &Pet { name: "Fido", age: 3 };
90//!
91//! let name_cmp = |l: &Pet, r: &Pet| l.name.cmp(r.name);
92//! assert_eq!(name_cmp.compare(fido4, ruff2), Less);
93//! assert_eq!(name_cmp.compare(fido4, fido3), Equal);
94//! assert_eq!(name_cmp.compare(ruff2, fido3), Greater);
95//!
96//! let age_cmp = |l: &Pet, r: &Pet| l.age.cmp(&r.age);
97//! assert_eq!(age_cmp.compare(fido4, ruff2), Greater);
98//! assert_eq!(age_cmp.compare(fido4, fido3), Greater);
99//! assert_eq!(age_cmp.compare(ruff2, fido3), Less);
100//!
101//! let name_age_cmp = name_cmp.then(age_cmp);
102//! assert_eq!(name_age_cmp.compare(fido4, ruff2), Less);
103//! assert_eq!(name_age_cmp.compare(fido4, fido3), Greater);
104//! assert_eq!(name_age_cmp.compare(ruff2, fido3), Greater);
105//! ```
106//!
107//! It is often repetitive to compare two values of the same type by the same key, so the
108//! [key-extraction logic](struct.Extract.html) can be factored out, simplifying the
109//! previous example:
110//!
111//! ```
112//! use compare::{Compare, Extract};
113//! use std::cmp::Ordering::{Less, Greater};
114//!
115//! struct Pet { name: &'static str, age: u8 }
116//!
117//! let fido4 = &Pet { name: "Fido", age: 4 };
118//! let ruff2 = &Pet { name: "Ruff", age: 2 };
119//! let fido3 = &Pet { name: "Fido", age: 3 };
120//!
121//! let name_age_cmp = Extract::new(|p: &Pet| p.name)
122//! .then(Extract::new(|p: &Pet| p.age));
123//!
124//! assert_eq!(name_age_cmp.compare(fido4, ruff2), Less);
125//! assert_eq!(name_age_cmp.compare(fido4, fido3), Greater);
126//! assert_eq!(name_age_cmp.compare(ruff2, fido3), Greater);
127//! ```
128
129#![no_std]
130
131use core::borrow::Borrow;
132use core::cmp::Ordering::{self, Less, Equal, Greater};
133use core::default::Default;
134use core::marker::PhantomData;
135use core::fmt::{self, Debug};
136
137/// Returns the maximum of two values according to the given comparator, or `r` if they
138/// are equal.
139///
140/// # Examples
141///
142/// ```
143/// use compare::{Extract, max};
144///
145/// struct Foo { key: char, id: u8 }
146///
147/// let f1 = &Foo { key: 'a', id: 1};
148/// let f2 = &Foo { key: 'a', id: 2};
149/// let f3 = &Foo { key: 'b', id: 3};
150///
151/// let cmp = Extract::new(|f: &Foo| f.key);
152/// assert_eq!(max(&cmp, f1, f2).id, f2.id);
153/// assert_eq!(max(&cmp, f1, f3).id, f3.id);
154/// ```
155// FIXME: convert to default method on `Compare` once where clauses permit equality
156// (https://github.com/rust-lang/rust/issues/20041)
157pub fn max<'a, C: ?Sized, T: ?Sized>(cmp: &C, l: &'a T, r: &'a T) -> &'a T
158 where C: Compare<T> {
159
160 if cmp.compares_ge(r, l) { r } else { l }
161}
162
163/// Returns the minimum of two values according to the given comparator, or `l` if they
164/// are equal.
165///
166/// # Examples
167///
168/// ```
169/// use compare::{Extract, min};
170///
171/// struct Foo { key: char, id: u8 }
172///
173/// let f1 = &Foo { key: 'b', id: 1};
174/// let f2 = &Foo { key: 'b', id: 2};
175/// let f3 = &Foo { key: 'a', id: 3};
176///
177/// let cmp = Extract::new(|f: &Foo| f.key);
178/// assert_eq!(min(&cmp, f1, f2).id, f1.id);
179/// assert_eq!(min(&cmp, f1, f3).id, f3.id);
180/// ```
181// FIXME: convert to default method on `Compare` once where clauses permit equality
182// (https://github.com/rust-lang/rust/issues/20041)
183pub fn min<'a, C: ?Sized, T: ?Sized>(cmp: &C, l: &'a T, r: &'a T) -> &'a T
184 where C: Compare<T> {
185
186 if cmp.compares_le(l, r) { l } else { r }
187}
188
189/// A comparator imposing a [total order](https://en.wikipedia.org/wiki/Total_order).
190///
191/// See the [`compare` module's documentation](index.html) for detailed usage.
192///
193/// The `compares_*` methods may be overridden to provide more efficient implementations.
194pub trait Compare<L: ?Sized, R: ?Sized = L> {
195 /// Compares two values, returning `Less`, `Equal`, or `Greater` if `l` is less
196 /// than, equal to, or greater than `r`, respectively.
197 fn compare(&self, l: &L, r: &R) -> Ordering;
198
199 /// Checks if `l` is less than `r`.
200 fn compares_lt(&self, l: &L, r: &R) -> bool { self.compare(l, r) == Less }
201
202 /// Checks if `l` is less than or equal to `r`.
203 fn compares_le(&self, l: &L, r: &R) -> bool { self.compare(l, r) != Greater }
204
205 /// Checks if `l` is greater than or equal to `r`.
206 fn compares_ge(&self, l: &L, r: &R) -> bool { self.compare(l, r) != Less }
207
208 /// Checks if `l` is greater than `r`.
209 fn compares_gt(&self, l: &L, r: &R) -> bool { self.compare(l, r) == Greater }
210
211 /// Checks if `l` is equal to `r`.
212 fn compares_eq(&self, l: &L, r: &R) -> bool { self.compare(l, r) == Equal }
213
214 /// Checks if `l` is not equal to `r`.
215 fn compares_ne(&self, l: &L, r: &R) -> bool { self.compare(l, r) != Equal }
216
217 /// Borrows the comparator's parameters before comparing them.
218 ///
219 /// # Examples
220 ///
221 /// ```
222 /// use compare::{Compare, natural};
223 /// use std::cmp::Ordering::{Less, Equal, Greater};
224 ///
225 /// let a_str = "a";
226 /// let a_string = a_str.to_string();
227 ///
228 /// let b_str = "b";
229 /// let b_string = b_str.to_string();
230 ///
231 /// let cmp = natural().borrowing();
232 /// assert_eq!(cmp.compare(a_str, &a_string), Equal);
233 /// assert_eq!(cmp.compare(a_str, b_str), Less);
234 /// assert_eq!(cmp.compare(&b_string, a_str), Greater);
235 /// ```
236 fn borrowing(self) -> Borrowing<Self, L, R> where Self: Sized { Borrowing(self, PhantomData) }
237
238 /// Reverses the ordering of the comparator.
239 ///
240 /// # Examples
241 ///
242 /// ```
243 /// use compare::{Compare, natural};
244 /// use std::cmp::Ordering::{Less, Equal, Greater};
245 ///
246 /// let a = &1;
247 /// let b = &2;
248 ///
249 /// let cmp = natural().rev();
250 /// assert_eq!(cmp.compare(a, b), Greater);
251 /// assert_eq!(cmp.compare(b, a), Less);
252 /// assert_eq!(cmp.compare(a, a), Equal);
253 /// ```
254 fn rev(self) -> Rev<Self> where Self: Sized { Rev(self) }
255
256 /// Swaps the comparator's parameters, maintaining the underlying ordering.
257 ///
258 /// This is useful for providing a comparator `C: Compare<T, U>` in a context that
259 /// expects `C: Compare<U, T>`.
260 ///
261 /// # Examples
262 ///
263 /// ```
264 /// use compare::Compare;
265 /// use std::cmp::Ordering::{Less, Equal, Greater};
266 ///
267 /// let cmp = |l: &u8, r: &u16| (*l as u16).cmp(r);
268 /// assert_eq!(cmp.compare(&1u8, &2u16), Less);
269 /// assert_eq!(cmp.compare(&2u8, &1u16), Greater);
270 /// assert_eq!(cmp.compare(&1u8, &1u16), Equal);
271 ///
272 /// let cmp = cmp.swap();
273 /// assert_eq!(cmp.compare(&2u16, &1u8), Less);
274 /// assert_eq!(cmp.compare(&1u16, &2u8), Greater);
275 /// assert_eq!(cmp.compare(&1u16, &1u8), Equal);
276 /// ```
277 fn swap(self) -> Swap<Self> where Self: Sized { Swap(self) }
278
279 /// [Lexicographically](https://en.wikipedia.org/wiki/Lexicographical_order) combines
280 /// the comparator with another.
281 ///
282 /// The retuned comparator compares values first using `self`, then, if they are
283 /// equal, using `then`.
284 ///
285 /// # Examples
286 ///
287 /// ```
288 /// use compare::{Compare, Extract};
289 /// use std::cmp::Ordering::{Less, Equal};
290 ///
291 /// struct Foo { key1: char, key2: u8 }
292 ///
293 /// let f1 = &Foo { key1: 'a', key2: 2};
294 /// let f2 = &Foo { key1: 'a', key2: 3};
295 ///
296 /// let cmp = Extract::new(|foo: &Foo| foo.key1);
297 /// assert_eq!(cmp.compare(f1, f2), Equal);
298 ///
299 /// let cmp = cmp.then(Extract::new(|foo: &Foo| foo.key2));
300 /// assert_eq!(cmp.compare(f1, f2), Less);
301 /// ```
302 fn then<D>(self, then: D) -> Then<Self, D> where D: Compare<L, R>, Self: Sized {
303 Then(self, then)
304 }
305}
306
307impl<F: ?Sized, L: ?Sized, R: ?Sized> Compare<L, R> for F
308 where F: Fn(&L, &R) -> Ordering {
309
310 fn compare(&self, l: &L, r: &R) -> Ordering { (*self)(l, r) }
311}
312
313/// A comparator that borrows its parameters before comparing them.
314///
315/// See [`Compare::borrow`](trait.Compare.html#method.borrow) for an example.
316pub struct Borrowing<C, Lb: ?Sized, Rb: ?Sized = Lb>(C, PhantomData<fn(&Lb, &Rb)>)
317 where C: Compare<Lb, Rb>;
318
319impl<C, L: ?Sized, R: ?Sized, Lb: ?Sized, Rb: ?Sized> Compare<L, R> for Borrowing<C, Lb, Rb>
320 where C: Compare<Lb, Rb>, L: Borrow<Lb>, R: Borrow<Rb> {
321
322 fn compare(&self, l: &L, r: &R) -> Ordering { self.0.compare(l.borrow(), r.borrow()) }
323 fn compares_lt(&self, l: &L, r: &R) -> bool { self.0.compares_lt(l.borrow(), r.borrow()) }
324 fn compares_le(&self, l: &L, r: &R) -> bool { self.0.compares_le(l.borrow(), r.borrow()) }
325 fn compares_ge(&self, l: &L, r: &R) -> bool { self.0.compares_ge(l.borrow(), r.borrow()) }
326 fn compares_gt(&self, l: &L, r: &R) -> bool { self.0.compares_gt(l.borrow(), r.borrow()) }
327 fn compares_eq(&self, l: &L, r: &R) -> bool { self.0.compares_eq(l.borrow(), r.borrow()) }
328 fn compares_ne(&self, l: &L, r: &R) -> bool { self.0.compares_ne(l.borrow(), r.borrow()) }
329}
330
331impl<C, Lb: ?Sized, Rb: ?Sized> Clone for Borrowing<C, Lb, Rb>
332 where C: Compare<Lb, Rb> + Clone {
333
334 fn clone(&self) -> Self { Borrowing(self.0.clone(), PhantomData) }
335}
336
337impl<C, Lb: ?Sized, Rb: ?Sized> Copy for Borrowing<C, Lb, Rb>
338 where C: Compare<Lb, Rb> + Copy {}
339
340impl<C, Lb: ?Sized, Rb: ?Sized> Default for Borrowing<C, Lb, Rb>
341 where C: Compare<Lb, Rb> + Default {
342
343 fn default() -> Self { Borrowing(Default::default(), PhantomData) }
344}
345
346impl<C, Lb: ?Sized, Rb: ?Sized> PartialEq for Borrowing<C, Lb, Rb>
347 where C: Compare<Lb, Rb> + PartialEq {
348
349 fn eq(&self, other: &Self) -> bool { self.0 == other.0 }
350}
351
352impl<C, Lb: ?Sized, Rb: ?Sized> Eq for Borrowing<C, Lb, Rb> where C: Compare<Lb, Rb> + Eq {}
353
354impl<C, Lb: ?Sized, Rb: ?Sized> Debug for Borrowing<C, Lb, Rb>
355 where C: Compare<Lb, Rb> + Debug {
356
357 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "Borrowing({:?})", self.0) }
358}
359
360/// A comparator that extracts a sort key from a value.
361///
362/// # Examples
363///
364/// ```
365/// use compare::{Compare, Extract};
366/// use std::cmp::Ordering::Greater;
367///
368/// let a = [1, 2, 3];
369/// let b = [4, 5];
370///
371/// let cmp = Extract::new(|s: &[i32]| s.len());
372/// assert_eq!(cmp.compare(&a, &b), Greater);
373/// ```
374#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
375pub struct Extract<E, C> {
376 ext: E,
377 cmp: C,
378}
379
380impl<E, K> Extract<E, Natural<K>> where K: Ord {
381 /// Returns a comparator that extracts a sort key using `ext` and compares it according to its
382 /// natural ordering.
383 pub fn new<T: ?Sized>(ext: E) -> Self where E: Fn(&T) -> K {
384 Extract { ext: ext, cmp: natural() }
385 }
386}
387
388// FIXME: convert to default method on `Compare` once where clauses permit equality
389// (https://github.com/rust-lang/rust/issues/20041)
390impl<E, C> Extract<E, C> {
391 /// Returns a comparator that extracts a sort key using `ext` and compares it using
392 /// `cmp`.
393 pub fn with_cmp<T: ?Sized, K>(ext: E, cmp: C) -> Self
394 where E: Fn(&T) -> K, C: Compare<K> { Extract { ext: ext, cmp: cmp } }
395}
396
397impl<E, C, T: ?Sized, K> Compare<T> for Extract<E, C> where E: Fn(&T) -> K, C: Compare<K> {
398 fn compare(&self, l: &T, r: &T) -> Ordering {
399 self.cmp.compare(&(self.ext)(l), &(self.ext)(r))
400 }
401
402 fn compares_lt(&self, l: &T, r: &T) -> bool {
403 self.cmp.compares_lt(&(self.ext)(l), &(self.ext)(r))
404 }
405
406 fn compares_le(&self, l: &T, r: &T) -> bool {
407 self.cmp.compares_le(&(self.ext)(l), &(self.ext)(r))
408 }
409
410 fn compares_ge(&self, l: &T, r: &T) -> bool {
411 self.cmp.compares_ge(&(self.ext)(l), &(self.ext)(r))
412 }
413
414 fn compares_gt(&self, l: &T, r: &T) -> bool {
415 self.cmp.compares_gt(&(self.ext)(l), &(self.ext)(r))
416 }
417
418 fn compares_eq(&self, l: &T, r: &T) -> bool {
419 self.cmp.compares_eq(&(self.ext)(l), &(self.ext)(r))
420 }
421
422 fn compares_ne(&self, l: &T, r: &T) -> bool {
423 self.cmp.compares_ne(&(self.ext)(l), &(self.ext)(r))
424 }
425}
426
427/// A comparator that [lexicographically]
428/// (https://en.wikipedia.org/wiki/Lexicographical_order) combines two others.
429///
430/// See [`Compare::then`](trait.Compare.html#method.then) for an example.
431#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
432pub struct Then<C, D>(C, D);
433
434impl<C, D, L: ?Sized, R: ?Sized> Compare<L, R> for Then<C, D>
435 where C: Compare<L, R>, D: Compare<L, R> {
436
437 fn compare(&self, l: &L, r: &R) -> Ordering {
438 match self.0.compare(l, r) {
439 Equal => self.1.compare(l, r),
440 order => order,
441 }
442 }
443}
444
445/// A comparator that delegates to [`Ord`]
446/// (http://doc.rust-lang.org/std/cmp/trait.Ord.html).
447///
448/// # Examples
449///
450/// ```
451/// use compare::{Compare, natural};
452/// use std::cmp::Ordering::{Less, Equal, Greater};
453///
454/// let a = &1;
455/// let b = &2;
456///
457/// let cmp = natural();
458/// assert_eq!(cmp.compare(a, b), Less);
459/// assert_eq!(cmp.compare(b, a), Greater);
460/// assert_eq!(cmp.compare(a, a), Equal);
461/// ```
462pub struct Natural<T: Ord + ?Sized>(PhantomData<fn(&T)>);
463
464/// Returns a comparator that delegates to `Ord`.
465pub fn natural<T: Ord + ?Sized>() -> Natural<T> { Natural(PhantomData) }
466
467impl<T: Ord + ?Sized> Compare<T> for Natural<T> {
468 fn compare(&self, l: &T, r: &T) -> Ordering { Ord::cmp(l, r) }
469 fn compares_lt(&self, l: &T, r: &T) -> bool { PartialOrd::lt(l, r) }
470 fn compares_le(&self, l: &T, r: &T) -> bool { PartialOrd::le(l, r) }
471 fn compares_ge(&self, l: &T, r: &T) -> bool { PartialOrd::ge(l, r) }
472 fn compares_gt(&self, l: &T, r: &T) -> bool { PartialOrd::gt(l, r) }
473 fn compares_eq(&self, l: &T, r: &T) -> bool { PartialEq::eq(l, r) }
474 fn compares_ne(&self, l: &T, r: &T) -> bool { PartialEq::ne(l, r) }
475}
476
477impl<T: Ord + ?Sized> Clone for Natural<T> {
478 fn clone(&self) -> Self { *self }
479}
480
481impl<T: Ord + ?Sized> Copy for Natural<T> {}
482
483impl<T: Ord + ?Sized> Default for Natural<T> {
484 fn default() -> Self { natural() }
485}
486
487impl<T: Ord + ?Sized> PartialEq for Natural<T> {
488 fn eq(&self, _other: &Self) -> bool { true }
489}
490
491impl<T: Ord + ?Sized> Eq for Natural<T> {}
492
493impl<T: Ord + ?Sized> Debug for Natural<T> {
494 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "Natural") }
495}
496
497/// A comparator that reverses the ordering of another.
498///
499/// See [`Compare::rev`](trait.Compare.html#method.rev) for an example.
500#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
501pub struct Rev<C>(C);
502
503impl<C, L: ?Sized, R: ?Sized> Compare<L, R> for Rev<C> where C: Compare<L, R> {
504 fn compare(&self, l: &L, r: &R) -> Ordering { self.0.compare(l, r).reverse() }
505 fn compares_lt(&self, l: &L, r: &R) -> bool { self.0.compares_gt(l, r) }
506 fn compares_le(&self, l: &L, r: &R) -> bool { self.0.compares_ge(l, r) }
507 fn compares_ge(&self, l: &L, r: &R) -> bool { self.0.compares_le(l, r) }
508 fn compares_gt(&self, l: &L, r: &R) -> bool { self.0.compares_lt(l, r) }
509 fn compares_eq(&self, l: &L, r: &R) -> bool { self.0.compares_eq(l, r) }
510 fn compares_ne(&self, l: &L, r: &R) -> bool { self.0.compares_ne(l, r) }
511}
512
513/// A comparator that swaps another's parameters, maintaining the underlying ordering.
514///
515/// This is useful for providing a comparator `C: Compare<T, U>` in a context that
516/// expects `C: Compare<U, T>`.
517///
518/// See [`Compare::swap`](trait.Compare.html#method.swap) for an example.
519#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
520pub struct Swap<C>(C);
521
522impl<C, L: ?Sized, R: ?Sized> Compare<R, L> for Swap<C>
523 where C: Compare<L, R> {
524
525 fn compare(&self, r: &R, l: &L) -> Ordering { self.0.compare(l, r) }
526 fn compares_lt(&self, r: &R, l: &L) -> bool { self.0.compares_lt(l, r) }
527 fn compares_le(&self, r: &R, l: &L) -> bool { self.0.compares_le(l, r) }
528 fn compares_ge(&self, r: &R, l: &L) -> bool { self.0.compares_ge(l, r) }
529 fn compares_gt(&self, r: &R, l: &L) -> bool { self.0.compares_gt(l, r) }
530 fn compares_eq(&self, r: &R, l: &L) -> bool { self.0.compares_eq(l, r) }
531 fn compares_ne(&self, r: &R, l: &L) -> bool { self.0.compares_ne(l, r) }
532}