haar_lib/ds/
circular_array.rs

1//! 循環配列
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc372/tasks/abc372_f>
5
6use std::{
7    fmt::{Debug, Error, Formatter},
8    ops::{Index, IndexMut},
9};
10
11/// 循環配列
12#[derive(Clone, Default, PartialEq, Eq, Hash)]
13pub struct CircularArray<T> {
14    data: Vec<T>,
15    shift: usize,
16}
17
18impl<T> CircularArray<T> {
19    /// 右に`n`要素分だけ回転させる。
20    pub fn rotate_right(&mut self, n: usize) {
21        self.shift = (self.shift + n) % self.data.len();
22    }
23
24    /// 左に`n`要素分だけ回転させる。
25    pub fn rotate_left(&mut self, n: usize) {
26        let len = self.data.len();
27        self.shift = (self.shift + len - n % len) % len;
28    }
29
30    /// 各要素への参照のイテレータを返す。
31    pub fn iter(&self) -> impl Iterator<Item = &T> {
32        let k = self.real_index(0);
33        let (b, a) = self.data.split_at(k);
34        a.iter().chain(b.iter())
35    }
36
37    /// 各要素への可変参照のイテレータを返す。
38    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
39        let k = self.real_index(0);
40        let (b, a) = self.data.split_at_mut(k);
41        a.iter_mut().chain(b.iter_mut())
42    }
43
44    fn real_index(&self, index: usize) -> usize {
45        let len = self.data.len();
46        assert_ne!(len, 0);
47        (len + index - self.shift) % len
48    }
49
50    /// 配列の長さを返す。
51    pub fn len(&self) -> usize {
52        self.data.len()
53    }
54
55    /// 配列の長さが`0`かを返す。
56    pub fn is_empty(&self) -> bool {
57        self.data.is_empty()
58    }
59}
60
61impl<T> Index<usize> for CircularArray<T> {
62    type Output = T;
63    fn index(&self, index: usize) -> &Self::Output {
64        &self.data[self.real_index(index)]
65    }
66}
67
68impl<T> IndexMut<usize> for CircularArray<T> {
69    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
70        let index = self.real_index(index);
71        &mut self.data[index]
72    }
73}
74
75impl<T> IntoIterator for CircularArray<T> {
76    type Item = T;
77    type IntoIter = std::iter::Chain<std::vec::IntoIter<T>, std::vec::IntoIter<T>>;
78    fn into_iter(mut self) -> Self::IntoIter {
79        let k = self.real_index(0);
80        let a = self.data.split_off(k);
81        a.into_iter().chain(self.data.into_iter())
82    }
83}
84
85impl<T> From<Vec<T>> for CircularArray<T> {
86    fn from(value: Vec<T>) -> Self {
87        Self {
88            data: value,
89            shift: 0,
90        }
91    }
92}
93
94impl<T: Debug> Debug for CircularArray<T> {
95    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
96        f.debug_list().entries(self.iter()).finish()
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn test() {
106        let mut a = CircularArray::from(vec![1, 2, 3, 4, 5, 6, 7, 8]);
107
108        eprintln!("{:?}", &a);
109
110        a.rotate_left(1);
111        eprintln!("{:?}", &a);
112
113        a.rotate_left(2);
114        eprintln!("{:?}", &a);
115
116        a.rotate_right(5);
117        eprintln!("{:?}", &a);
118
119        // for i in 0..100 {
120        //     dbg!(a[i]);
121        // }
122    }
123}
haar_lib/ds/circular_array.rs

haar_lib/ds/
circular_array.rs
