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

3
impl Solution {
4
  pub fn wiggle_sort(nums: &mut Vec<i32>) {
5
    if Self::wiggle_forward(&mut nums[..]) {
6
      return;
7
    }
8
    if Self::wiggle_backward(&mut nums[..]) {
9
      return;
10
    }
11
    let pivot = nums[0];
12
    if Self::wiggle_pivot(&mut nums[..], pivot) {
13
      return;
14
    }
15
    panic!("not wiggle-sortable");
16
  }
17
  fn wiggle_forward(nums: &mut [i32]) -> bool {
18
    let mut i = 0;
19
    let mut j = 0;
20
    while j < nums.len() {
21
      // INVARIANTS:
22
      // (0) 0 <= i <= j <= nums.len, i < nums.len
23
      // (1) nums[..i+1] is wiggle-sorted
24
      // (2) nums[i..j] are all identical
25
      // (3) nums[j..] are unchanged since the start of the loop
26
      if j <= i {
27
        j = i + 1;
28
        continue;
29
      }
30
      match (i % 2 == 0, i32::cmp(&nums[j], &nums[i])) {
31
        (true, Greater) | (false, Less) => {
32
          if j <= i + 1 {
33
            i += 1;
34
          } else {
35
            nums.swap(j, i + 1);
36
            i += 2;
37
            j += 1;
38
          }
39
        }
40
        (true, Less) | (false, Greater) => {
41
          nums.swap(j, i);
42
          i += 1;
43
          j += 1;
44
        }
45
        (_, Equal) => j += 1,
46
      }
47
    }
48
    return i >= nums.len() - 1;
49
  }
50
  fn wiggle_backward(nums: &mut [i32]) -> bool {
51
    let mut i = nums.len();
52
    let mut j = nums.len();
53
    while j > 0 {
54
      // INVARIANTS HERE:
55
      // (0) 0 <= j <= i <= nums.len and 0 < i
56
      // (1) nums[i-1..] is wiggle-sorted
57
      // (2) nums[j..i] are all identical
58
      // (3) nums[..j] are unchanged since the start of the loop
59
      if j >= i {
60
        j = i - 1;
61
        continue;
62
      }
63
      match (i % 2 == 0, i32::cmp(&nums[j - 1], &nums[i - 1])) {
64
        (true, Less) | (false, Greater) => {
65
          if j >= i - 1 {
66
            i -= 1;
67
          } else {
68
            nums.swap(j - 1, i - 2);
69
            i -= 2;
70
            j -= 1;
71
          }
72
        }
73
        (true, Greater) | (false, Less) => {
74
          nums.swap(j - 1, i - 1);
75
          i -= 1;
76
          j -= 1;
77
        }
78
        (_, Equal) => j -= 1,
79
      }
80
    }
81
    return i <= 1;
82
  }
83
  fn wiggle_pivot(nums: &mut [i32], pivot: i32) -> bool {
84
    let n = nums.len();
85
    let m = (n + 1) / 2;
86
    let index = move |i: usize| {
87
      if i < m {
88
        2 * (m - i - 1)
89
      } else {
90
        2 * (n - i) - 1
91
      }
92
    };
93
    let mut min_i = 0;
94
    let mut max_i = n;
95
    let mut i = 0;
96
    while i < max_i {
97
      match nums[index(i)].cmp(&pivot) {
98
        Less => {
99
          nums.swap(index(i), index(min_i));
100
          i += 1;
101
          min_i += 1;
102
        }
103
        Equal => {
104
          i += 1;
105
        }
106
        Greater => {
107
          nums.swap(index(i), index(max_i - 1));
108
          max_i -= 1;
109
        }
110
      }
111
    }
112
    return min_i <= m && max_i >= m;
113
  }
114
}