// 1032: VecDeque Rotation — Efficient Front/Back Operations
// VecDeque is a ring buffer: O(1) push/pop at both ends
use std::collections::VecDeque;
/// Basic front/back operations
fn basic_deque() {
let mut dq = VecDeque::new();
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);
dq.push_front(0);
assert_eq!(dq.pop_front(), Some(0));
assert_eq!(dq.pop_front(), Some(1));
assert_eq!(dq.pop_back(), Some(3));
assert_eq!(dq.pop_back(), Some(2));
assert!(dq.is_empty());
}
/// Rotation using VecDeque::rotate_left/rotate_right
fn rotation() {
let mut dq: VecDeque<_> = [1, 2, 3, 4, 5].into_iter().collect();
// Rotate left by 2: [3, 4, 5, 1, 2]
dq.rotate_left(2);
assert_eq!(dq, [3, 4, 5, 1, 2].into_iter().collect::<VecDeque<_>>());
// Rotate right by 2: back to [1, 2, 3, 4, 5]
dq.rotate_right(2);
assert_eq!(dq, [1, 2, 3, 4, 5].into_iter().collect::<VecDeque<_>>());
}
/// Using VecDeque as a sliding window
fn sliding_window() {
let data = vec![1, 2, 3, 4, 5, 6, 7];
let window_size = 3;
let mut window: VecDeque<i32> = VecDeque::with_capacity(window_size);
let mut sums = Vec::new();
for &val in &data {
window.push_back(val);
if window.len() > window_size {
window.pop_front();
}
if window.len() == window_size {
let sum: i32 = window.iter().sum();
sums.push(sum);
}
}
assert_eq!(sums, vec![6, 9, 12, 15, 18]); // 1+2+3, 2+3+4, ...
}
/// VecDeque to Vec and back
fn conversions() {
let v = vec![1, 2, 3, 4, 5];
let mut dq: VecDeque<_> = v.into_iter().collect();
dq.push_front(0);
// make_contiguous ensures internal buffer is contiguous
dq.make_contiguous();
let v: Vec<_> = dq.into_iter().collect();
assert_eq!(v, vec![0, 1, 2, 3, 4, 5]);
}
fn main() {
basic_deque();
rotation();
sliding_window();
conversions();
println!("✓ All tests passed");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_basic_deque() { basic_deque(); }
#[test]
fn test_rotation() { rotation(); }
#[test]
fn test_sliding_window() { sliding_window(); }
#[test]
fn test_conversions() { conversions(); }
#[test]
fn test_indexed_access() {
let dq: VecDeque<_> = [10, 20, 30].into_iter().collect();
assert_eq!(dq[0], 10);
assert_eq!(dq[1], 20);
assert_eq!(dq[2], 30);
}
}
(* 1032: VecDeque Rotation — Efficient Front/Back Operations *)
(* OCaml uses lists (efficient at front) or Queue module *)
(* Approach 1: List as a deque — efficient front, O(n) back *)
let list_deque () =
let q = [1; 2; 3; 4; 5] in
(* Push front: O(1) *)
let q = 0 :: q in
assert (q = [0; 1; 2; 3; 4; 5]);
(* Pop front: O(1) *)
let (front, q) = (List.hd q, List.tl q) in
assert (front = 0);
assert (q = [1; 2; 3; 4; 5]);
(* Push back: O(n) *)
let q = q @ [6] in
assert (q = [1; 2; 3; 4; 5; 6])
(* Approach 2: Two-list queue for amortized O(1) both ends *)
type 'a deque = { front: 'a list; back: 'a list }
let empty = { front = []; back = [] }
let push_front x d = { d with front = x :: d.front }
let push_back x d = { d with back = x :: d.back }
let pop_front d =
match d.front with
| x :: rest -> Some (x, { d with front = rest })
| [] ->
match List.rev d.back with
| x :: rest -> Some (x, { front = rest; back = [] })
| [] -> None
let pop_back d =
match d.back with
| x :: rest -> Some (x, { d with back = rest })
| [] ->
match List.rev d.front with
| x :: rest -> Some (x, { front = []; back = rest })
| [] -> None
let two_list_deque () =
let d = empty in
let d = push_back 1 d in
let d = push_back 2 d in
let d = push_back 3 d in
let d = push_front 0 d in
let (v, d) = Option.get (pop_front d) in
assert (v = 0);
let (v, d) = Option.get (pop_front d) in
assert (v = 1);
let (v, _d) = Option.get (pop_back d) in
assert (v = 3)
(* Approach 3: Rotation *)
let rotate_left lst n =
let len = List.length lst in
let n = n mod len in
let rec take_drop i = function
| [] -> ([], [])
| x :: xs when i > 0 ->
let (taken, rest) = take_drop (i - 1) xs in
(x :: taken, rest)
| xs -> ([], xs)
in
let (front, back) = take_drop n lst in
back @ front
let rotation_test () =
let lst = [1; 2; 3; 4; 5] in
assert (rotate_left lst 2 = [3; 4; 5; 1; 2]);
assert (rotate_left lst 0 = [1; 2; 3; 4; 5])
let () =
list_deque ();
two_list_deque ();
rotation_test ();
Printf.printf "✓ All tests passed\n"