substrate_median/
policy.rs

1/// The policy to use to select the median when the list of candidates is of even length.
2pub enum Policy {
3  /// When two values are equally considerable, choose the greater value.
4  Greater,
5  /// When two values are equally considerable, choose the lesser value.
6  Lesser,
7  /// When two values are equally considerable, choose their average.
8  ///
9  /// The average will be the sum of the two values divided by two. For how the division may or may
10  /// not round, please defer to the `Div` implementation for the value operated over.
11  /*
12    Internally, this is functionally equivalent to `Policy::Lesser`. It is only when the median is
13    finally requested that if the policy is to take the average, we look and see if we need to
14    before applying the relevant logic. From the lesser value, finding the complimentary greater
15    value is trivial.
16  */
17  Average,
18}
19
20impl Policy {
21  /// Calculate the position of the median within the sorted list of values.
22  ///
23  /// If there are two candidates, `Policy::Greater` and `Policy::Lesser` decide which is chosen,
24  /// with `Policy::Average` being interpreted as `Policy::Lesser` _by this function_.
25  ///
26  /// This will return `0` if the median's list is empty, despite `0` being an invalid position in
27  /// that context.
28  pub(super) fn target_median_pos(&self, list_length: u64) -> u64 {
29    let mut target_median_pos = list_length / 2;
30    /*
31      If this could be two possible indexes, we use the policy to determine the target index. When
32      an odd amount of values are present in the median's list, the integer division by two is
33      inherently correct. When there's an even amount of values present, the integer division favors
34      the higher value, leading us to correct for when we want the lower value.
35    */
36    if matches!(self, Policy::Lesser | Policy::Average) && ((list_length % 2) == 0) {
37      target_median_pos = target_median_pos.saturating_sub(1);
38    }
39    target_median_pos
40  }
41}
42
43#[test]
44fn policy() {
45  assert_eq!(Policy::Greater.target_median_pos(0), 0);
46  assert_eq!(Policy::Greater.target_median_pos(1), 0);
47  assert_eq!(Policy::Greater.target_median_pos(2), 1);
48  assert_eq!(Policy::Greater.target_median_pos(3), 1);
49  assert_eq!(Policy::Greater.target_median_pos(4), 2);
50
51  assert_eq!(Policy::Lesser.target_median_pos(0), 0);
52  assert_eq!(Policy::Lesser.target_median_pos(1), 0);
53  assert_eq!(Policy::Lesser.target_median_pos(2), 0);
54  assert_eq!(Policy::Lesser.target_median_pos(3), 1);
55  assert_eq!(Policy::Lesser.target_median_pos(4), 1);
56
57  assert_eq!(Policy::Average.target_median_pos(0), 0);
58  assert_eq!(Policy::Average.target_median_pos(1), 0);
59  assert_eq!(Policy::Average.target_median_pos(2), 0);
60  assert_eq!(Policy::Average.target_median_pos(3), 1);
61  assert_eq!(Policy::Average.target_median_pos(4), 1);
62}
substrate_median/policy.rs

substrate_median/
policy.rs
