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

use std::cmp::Ordering::{self, Equal, Greater, Less};

pub fn compare(left: &[u8], right: &[u8]) -> Ordering {
    let mut left = left.into_iter().fuse();
    let mut right = right.into_iter().fuse();

    let mut l;
    let mut r;
    let mut ll;
    let mut rr;

    macro_rules! to_digit {
        ($v:expr) => {
            $v.and_then(|v| {
                let v = *v as isize;
                (v >= ('0' as isize) && v <= ('9' as isize)).then_some(v - 48)
            })
        };
    }

    macro_rules! read_left {
        () => {{
            l = left.next();
            ll = to_digit!(l);
        }};
    }

    macro_rules! read_right {
        () => {{
            r = right.next();
            rr = to_digit!(r);
        }};
    }

    macro_rules! return_unless_equal {
        ($ord:expr) => {
            match $ord {
                Equal => {}
                lastcmp => return lastcmp,
            }
        };
    }

    read_left!();
    read_right!();
    'nondigits: loop {
        match (l, r) {
            (Some(l_), Some(r_)) => match (ll, rr) {
                (Some(ll_), Some(rr_)) => {
                    if ll_ == 0 || rr_ == 0 {
                        // left-aligned matching. (`015` < `12`)
                        return_unless_equal!(ll_.cmp(&rr_));
                        'digits_left: loop {
                            read_left!();
                            read_right!();
                            match (ll, rr) {
                                (Some(ll_), Some(rr_)) => return_unless_equal!(ll_.cmp(&rr_)),
                                (Some(_), None) => return Greater,
                                (None, Some(_)) => return Less,
                                (None, None) => break 'digits_left,
                            }
                        }
                    } else {
                        // right-aligned matching. (`15` < `123`)
                        let mut lastcmp = ll_.cmp(&rr_);
                        'digits_right: loop {
                            read_left!();
                            read_right!();
                            match (ll, rr) {
                                (Some(ll_), Some(rr_)) => {
                                    // `lastcmp` is only used when there are the same number of
                                    // digits, so we only update it.
                                    if lastcmp == Equal {
                                        lastcmp = ll_.cmp(&rr_);
                                    }
                                }
                                (Some(_), None) => return Greater,
                                (None, Some(_)) => return Less,
                                (None, None) => break 'digits_right,
                            }
                        }
                        return_unless_equal!(lastcmp);
                    }
                    continue 'nondigits; // do not read from the iterators again
                }
                (_, _) => return_unless_equal!(l_.cmp(r_)),
            },
            (Some(_), None) => return Greater,
            (None, Some(_)) => return Less,
            (None, None) => return Equal,
        }
        read_left!();
        read_right!();
    }
}