1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use crate::{repr::Repr, RBig, Relaxed};
use core::{
    cmp::Ordering,
    hash::{Hash, Hasher},
};
use dashu_base::{BitTest, Sign::*};

impl PartialEq for Repr {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        // for relaxed representation, we have to compare it's actual value
        if self.numerator.sign() != other.numerator.sign() {
            return false;
        }

        let n1d2_bits = self.numerator.bit_len() as isize + other.denominator.bit_len() as isize;
        let n2d1_bits = other.numerator.bit_len() as isize + self.denominator.bit_len() as isize;
        if n1d2_bits.abs_diff(n2d1_bits) > 1 {
            return false;
        }

        // do the final product after filtering out simple cases
        (&self.numerator) * (&other.denominator) == (&other.numerator) * (&self.denominator)
    }
}
impl Eq for Repr {}

impl PartialEq for RBig {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        // representation of RBig is canonicalized, so it suffices to compare the components
        self.0.numerator == other.0.numerator && self.0.denominator == other.0.denominator
    }
}
impl Eq for RBig {}

// Hash is only implemented for RBig but not for Relaxed, because the representation
// is not unique for Relaxed.
impl Hash for RBig {
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.numerator.hash(state);
        self.0.denominator.hash(state);
    }
}

impl PartialOrd for Repr {
    #[inline]
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Repr {
    fn cmp(&self, other: &Self) -> Ordering {
        // step1: compare sign
        let negative = match (self.numerator.sign(), other.numerator.sign()) {
            (Positive, Positive) => false,
            (Positive, Negative) => return Ordering::Greater,
            (Negative, Positive) => return Ordering::Less,
            (Negative, Negative) => true,
        };

        // step2: if both numbers are integers
        if self.denominator.is_one() && other.denominator.is_one() {
            return self.numerator.cmp(&other.numerator);
        }

        // step3: test bit size
        let n1d2_bits = self.numerator.bit_len() as isize + other.denominator.bit_len() as isize;
        let n2d1_bits = other.numerator.bit_len() as isize + self.denominator.bit_len() as isize;
        if n1d2_bits > n2d1_bits + 1 {
            return if negative {
                Ordering::Less
            } else {
                Ordering::Greater
            };
        } else if n1d2_bits < n2d1_bits - 1 {
            return if negative {
                Ordering::Greater
            } else {
                Ordering::Less
            };
        }

        // step4: finally do multiplication test
        let n1d2 = (&self.numerator) * (&other.denominator);
        let n2d1 = (&other.numerator) * (&self.denominator);
        n1d2.cmp(&n2d1)
    }
}

impl PartialEq<RBig> for Relaxed {
    #[inline]
    fn eq(&self, other: &RBig) -> bool {
        self.0.eq(&other.0)
    }
}
impl PartialOrd<RBig> for Relaxed {
    #[inline]
    fn partial_cmp(&self, other: &RBig) -> Option<Ordering> {
        self.0.partial_cmp(&other.0)
    }
}
impl PartialEq<Relaxed> for RBig {
    #[inline]
    fn eq(&self, other: &Relaxed) -> bool {
        self.0.eq(&other.0)
    }
}
impl PartialOrd<Relaxed> for RBig {
    #[inline]
    fn partial_cmp(&self, other: &Relaxed) -> Option<Ordering> {
        self.0.partial_cmp(&other.0)
    }
}