arimaa_engine/
path.rs

1use lazy_static::lazy_static;
2use std::{convert::TryFrom, fmt, iter::FromIterator, str::FromStr};
3use tinyvec::ArrayVec;
4
5use super::Direction;
6
7lazy_static! {
8    static ref PATH_SPARSE_LOOKUP: Vec<ArrayVec<[Direction; 4]>> = Path::create_sparse_path_lookup();
9}
10
11type Directions = u8;
12
13#[derive(Hash, Clone, Copy, Debug, Default, Eq, PartialEq)]
14pub struct Path(Directions);
15
16impl fmt::Display for Path {
17    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
18        for dir in self.iter() {
19            write!(f, "{}", dir)?
20        }
21
22        Ok(())
23    }
24}
25
26#[rustfmt::skip]
27impl Path {
28    pub fn invert(&self) -> Self {
29        self.iter().map(|d| d.invert()).collect::<Path>()
30    }
31
32    pub fn vertical_symmetry(&self) -> Self {
33        self.iter().map(|d| d.vertical_symmetry()).collect::<Path>()
34    }
35
36    pub fn iter(&self) -> impl Iterator<Item=Direction> {
37        self.into_iter()
38    }
39
40    pub fn len(&self) -> usize {
41        self.iter().count()
42    }
43
44    pub fn is_empty(&self) -> bool {
45        false
46    }
47
48    pub fn as_u8(&self) -> u8 {
49        self.0
50    }
51
52    fn get_direction_at_index(path: u8, index: u8) -> u8 {
53        (path >> (index * 2)) & DIRECTION_MASK
54    }
55
56    fn get_direction_for_dir_bits(bits: u8) -> Direction {
57        DIRECTION_BY_INDEX[bits as usize]
58    }
59
60    fn create_sparse_path_lookup() -> Vec<ArrayVec<[Direction; 4]>> {
61        let mut lookup = Vec::with_capacity(256);
62
63        for i in 0..=255 {
64            let path = Path(i).path_into_array_vec_no_lookup_slow();
65            lookup.push(path);
66        }
67
68        lookup
69    }
70
71    fn path_into_array_vec_no_lookup_slow(&self) -> ArrayVec<[Direction; 4]> {
72        let mut directions = ArrayVec::new();
73        let mut prev_dir = 0;
74
75        for i in 0..4 {
76            let curr_dir = Path::get_direction_at_index(self.0, i);
77
78            if i != 0 && curr_dir ^ prev_dir == 0b11 {
79                break;
80            }
81            
82            directions.push(Path::get_direction_for_dir_bits(curr_dir));
83            prev_dir = curr_dir;
84        }
85
86        directions
87    }
88}
89
90impl FromStr for Path {
91    type Err = anyhow::Error;
92
93    fn from_str(s: &str) -> Result<Self, Self::Err> {
94        s.chars().map(Direction::try_from).collect::<Result<Path, Self::Err>>()
95    }
96}
97
98impl FromIterator<Direction> for Path {
99    fn from_iter<I: IntoIterator<Item = Direction>>(iter: I) -> Self {
100        let bits_for_dir = |dir: Direction| match dir {
101            Direction::Up => 0b00,
102            Direction::Right => 0b01,
103            Direction::Left => 0b10,
104            Direction::Down => 0b11,
105        };
106
107        let (last_dir_bit, mut path_bits, last_i) = iter.into_iter().enumerate().fold((0u8, 0u8, 0usize), |(_, mut path_bits, _), (i, dir)| {
108            let dir_bits = bits_for_dir(dir);
109
110            path_bits |= dir_bits << (i * 2);
111
112            (dir_bits, path_bits, i)
113        });
114
115        if last_i < 3 {
116            let opposite_dir = !last_dir_bit & DIRECTION_MASK;
117            path_bits |= opposite_dir << ((last_i + 1) * 2);
118        }
119
120        Path(path_bits)
121    }
122}
123
124impl<'a> FromIterator<&'a Direction> for Path {
125    fn from_iter<I: IntoIterator<Item = &'a Direction>>(iter: I) -> Self {
126        iter.into_iter().copied().collect::<Path>()
127    }
128}
129
130// Order of directions is intended so that a XOR produces the opposite direction.
131const DIRECTION_MASK: u8 = 0b11;
132const DIRECTION_BY_INDEX: [Direction; 4] = [
133    Direction::Up,    // b00
134    Direction::Right, // b01
135    Direction::Left,  // b10
136    Direction::Down,  // b11
137];
138
139impl IntoIterator for Path {
140    type Item = Direction;
141    type IntoIter = tinyvec::ArrayVecIterator<[Direction; 4]>;
142
143    fn into_iter(self) -> Self::IntoIter {
144        (&self).into_iter()
145    }
146}
147
148impl IntoIterator for &Path {
149    type Item = Direction;
150    type IntoIter = tinyvec::ArrayVecIterator<[Direction; 4]>;
151
152    fn into_iter(self) -> Self::IntoIter {
153        PATH_SPARSE_LOOKUP[self.0 as usize].into_iter()
154    }
155}
156
157impl From<&[Direction]> for Path {
158    fn from(value: &[Direction]) -> Self {
159        value.iter().collect::<Path>()
160    }
161}
arimaa_engine/path.rs

arimaa_engine/
path.rs
