lattice_graph/lattice_abstract/
shapes.rs

1//! Shapes to define the behavior of the [`LatticeGraph`](`crate::lattice_abstract::LatticeGraph`)
2//!
3//! If you want to create your own lattice based graph, use this to implement your own lattice.
4//!
5
6use crate::unreachable_debug_checked;
7
8/// Shape of the 2d lattice.
9/// It decides the behavior of the coordinate.
10pub trait Shape: Clone {
11    /// Axis of the lattice.
12    type Axis: Axis;
13    /// Coordinate of the lattice graph.
14    type Coordinate: Coordinate;
15    /// Error to return when [`to_offset`](`Shape::to_offset`) fails.
16    /// Should set [`Infallible`](`core::convert::Infallible`) when the graph is looped and never to fail.
17    type OffsetConvertError: core::fmt::Debug + Clone;
18    /// Error to return when [`move_coord`](`Shape::move_coord`) fails.
19    /// Should set [`Infallible`](`core::convert::Infallible`) when the graph is looped and never to fail.
20    type CoordinateMoveError: core::fmt::Debug + Clone;
21
22    /// Horizontal node count.
23    fn horizontal(&self) -> usize;
24    /// Vertical node count.
25    fn vertical(&self) -> usize;
26    /// Node count.
27    fn node_count(&self) -> usize {
28        self.horizontal() * self.vertical()
29    }
30    /// Convert coordinate to `Offset`.
31    fn to_offset(&self, coord: Self::Coordinate) -> Result<Offset, Self::OffsetConvertError>;
32    /// Convert coordinate to Offset without a check.
33    unsafe fn to_offset_unchecked(&self, coord: Self::Coordinate) -> Offset {
34        self.to_offset(coord)
35            .unwrap_or_else(|_| crate::unreachable_debug_checked())
36    }
37    /// Convert coordinate from `Offset`.
38    fn offset_to_coordinate(&self, offset: Offset) -> Self::Coordinate;
39
40    /// Convert coordinate from index.
41    fn index_to_coordinate(&self, index: usize) -> Self::Coordinate {
42        self.offset_to_coordinate(self.index_to_offset(index))
43    }
44    /// Covert coordinate to index.
45    fn to_index(&self, coord: Self::Coordinate) -> Option<usize> {
46        let offset = self.to_offset(coord);
47        offset.ok().map(|o| self.offset_to_index(o))
48    }
49    /// Convert index to offset.
50    fn index_to_offset(&self, index: usize) -> Offset {
51        let v = index % self.vertical();
52        let h = index / self.vertical();
53        Offset::new(h, v)
54    }
55    /// Covert offset to index.
56    fn offset_to_index(&self, o: Offset) -> usize {
57        o.horizontal * self.vertical() + o.vertical
58    }
59
60    /// Edge count of horizontal. May differ by the axis info.
61    #[deprecated]
62    fn horizontal_edge_size(&self, _axis: Self::Axis) -> usize {
63        self.horizontal()
64    }
65    /// Edge count of vertical. May differ by the axis info.
66    #[deprecated]
67    fn vertical_edge_size(&self, _axis: Self::Axis) -> usize {
68        self.vertical()
69    }
70    /// Move coordinates to the next coordinate in the direction.
71    /// Coordinate should be a valid coordinate and should be checked before using `move_coord`.
72    /// This is because the target coordinate might be valid even thought the souce coord is invalid,
73    /// and some code validate the direction by moveing the coord.
74    fn move_coord(
75        &self,
76        coord: Self::Coordinate,
77        dir: <Self::Axis as Axis>::Direction,
78    ) -> Result<Self::Coordinate, Self::CoordinateMoveError>;
79    /// Move coordinates to the next coordinate in the direction.
80    /// Caller should be sure that the source and the target coord is valid coord.
81    unsafe fn move_coord_unchecked(
82        &self,
83        coord: Self::Coordinate,
84        dir: <Self::Axis as Axis>::Direction,
85    ) -> Self::Coordinate {
86        self.move_coord(coord, dir)
87            .unwrap_or_else(|_| unreachable_debug_checked())
88    }
89    ///Check whether two coordinate is in neighbor.
90    fn is_neighbor(&self, a: Self::Coordinate, b: Self::Coordinate) -> bool {
91        self.get_direction(a, b).is_some()
92    }
93    ///Get direction if two coordiante is in neighbor.
94    fn get_direction(
95        &self,
96        source: Self::Coordinate,
97        target: Self::Coordinate,
98    ) -> Option<<Self::Axis as Axis>::Direction> {
99        let a = source;
100        let b = target;
101        for i in 0..<Self::Axis as Axis>::UNDIRECTED_COUNT {
102            let d = unsafe { <Self::Axis as Axis>::Direction::dir_from_index_unchecked(i) };
103            let c = self.move_coord(a, d.clone());
104            if let Ok(c) = c {
105                if c == b {
106                    return Some(d);
107                }
108            }
109        }
110        None
111    }
112}
113
114impl<S: Shape> Shape for &S {
115    type Axis = S::Axis;
116    type Coordinate = S::Coordinate;
117    type OffsetConvertError = S::OffsetConvertError;
118    type CoordinateMoveError = S::CoordinateMoveError;
119
120    fn to_offset(&self, coord: Self::Coordinate) -> Result<Offset, Self::OffsetConvertError> {
121        (*self).to_offset(coord)
122    }
123
124    unsafe fn to_offset_unchecked(&self, coord: Self::Coordinate) -> Offset {
125        (*self).to_offset_unchecked(coord)
126    }
127
128    fn offset_to_coordinate(&self, offset: Offset) -> Self::Coordinate {
129        (*self).offset_to_coordinate(offset)
130    }
131
132    fn horizontal(&self) -> usize {
133        (*self).horizontal()
134    }
135
136    fn vertical(&self) -> usize {
137        (*self).vertical()
138    }
139
140    fn move_coord(
141        &self,
142        coord: Self::Coordinate,
143        dir: <Self::Axis as Axis>::Direction,
144    ) -> Result<Self::Coordinate, Self::CoordinateMoveError> {
145        (*self).move_coord(coord, dir)
146    }
147
148    unsafe fn move_coord_unchecked(
149        &self,
150        coord: Self::Coordinate,
151        dir: <Self::Axis as Axis>::Direction,
152    ) -> Self::Coordinate {
153        (*self).move_coord_unchecked(coord, dir)
154    }
155
156    fn node_count(&self) -> usize {
157        (*self).node_count()
158    }
159
160    fn index_to_coordinate(&self, index: usize) -> Self::Coordinate {
161        (*self).index_to_coordinate(index)
162    }
163
164    fn to_index(&self, coord: Self::Coordinate) -> Option<usize> {
165        (*self).to_index(coord)
166    }
167
168    fn index_to_offset(&self, index: usize) -> Offset {
169        (*self).index_to_offset(index)
170    }
171
172    fn offset_to_index(&self, o: Offset) -> usize {
173        (*self).offset_to_index(o)
174    }
175
176    fn is_neighbor(&self, a: Self::Coordinate, b: Self::Coordinate) -> bool
177    where
178        Self::Coordinate: PartialEq,
179    {
180        (*self).is_neighbor(a, b)
181    }
182
183    fn get_direction(
184        &self,
185        source: Self::Coordinate,
186        target: Self::Coordinate,
187    ) -> Option<<Self::Axis as Axis>::Direction>
188    where
189        Self::Coordinate: PartialEq,
190    {
191        (*self).get_direction(source, target)
192    }
193}
194
195/// Axis of the graph. It holds what direction of edge which node has.
196pub trait Axis: Copy + PartialEq {
197    /// Number of axis.
198    const COUNT: usize;
199    /// Whether it is Directed or not.
200    const DIRECTED: bool;
201    /// Number of direction. If this axis is not directed, it is `COUNT * 2`, otherwise `COUNT`.
202    const UNDIRECTED_COUNT: usize = if Self::DIRECTED {
203        Self::COUNT
204    } else {
205        Self::COUNT * 2
206    };
207    /// For tricks to optimize for undirected graph, and not to regress performance of directed graph.
208    /// If the axis is `DIRECTED`, should set `Self`.
209    type Direction: AxisDirection;
210    /// Convert to index.
211    fn to_index(&self) -> usize;
212    /// Convert form index.
213    unsafe fn from_index_unchecked(index: usize) -> Self {
214        Self::from_index(index).unwrap_or_else(|| unreachable_debug_checked())
215    }
216    /// Convert form index.
217    fn from_index(index: usize) -> Option<Self>
218    where
219        Self: Sized;
220    /// To forward direction. It is nop when Axis is `DIRECTED`.
221    fn foward(self) -> Self::Direction;
222    /// To backward direction. It reverses when Axis is `DIRECTED`.
223    fn backward(self) -> Self::Direction;
224    /// Check the direction is forward for this axis.
225    /// Returns true if the direction is `DIRECTED` is `true`, or the index of the axis and direction matches.
226    fn is_forward_direction(dir: &Self::Direction) -> bool {
227        Self::DIRECTED || dir.dir_to_index() == Self::from_direction(dir.clone()).to_index()
228    }
229    /// Convert from direction.
230    fn from_direction(dir: Self::Direction) -> Self;
231}
232
233/// Direction of axis. It tells which direction is connected to node.
234pub trait AxisDirection: Clone {
235    /// Check this match whith [`Axis`]. It will always return true when `Axis` is directed.
236    #[deprecated(note = "Use Axis::is_forward_direction instead.")]
237    fn is_forward(&self) -> bool;
238    /// Check this doesn't match whith [`Axis`]. It will always return false when `Axis` is directed.
239    #[deprecated(note = "Use !Axis::is_forward_direction instead.")]
240    #[allow(deprecated)]
241    fn is_backward(&self) -> bool {
242        !self.is_forward()
243    }
244    /// Convert to index.
245    fn dir_to_index(&self) -> usize;
246    /// Convert from index.
247    unsafe fn dir_from_index_unchecked(index: usize) -> Self;
248    /// Convert from index.
249    fn dir_from_index(index: usize) -> Option<Self>
250    where
251        Self: Sized;
252}
253
254/// Implimention for Axis of directed graph.
255impl<A> AxisDirection for A
256where
257    A: Axis<Direction = Self>,
258{
259    fn is_forward(&self) -> bool {
260        true
261    }
262    fn dir_to_index(&self) -> usize {
263        <Self as Axis>::to_index(self)
264    }
265    unsafe fn dir_from_index_unchecked(index: usize) -> Self {
266        <Self as Axis>::from_index_unchecked(index)
267    }
268    fn dir_from_index(index: usize) -> Option<Self>
269    where
270        Self: Sized,
271    {
272        <Self as Axis>::from_index(index)
273    }
274}
275
276/// Implimention of [`AxisDirection`] when [`Axis::DIRECTED`] is false.
277#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
278#[deprecated]
279pub enum Direction<T> {
280    Foward(T),
281    Backward(T),
282}
283
284#[allow(deprecated)]
285impl<T: Axis> AxisDirection for Direction<T> {
286    fn is_forward(&self) -> bool {
287        match self {
288            Direction::Foward(_) => true,
289            Direction::Backward(_) => false,
290        }
291    }
292
293    fn dir_to_index(&self) -> usize {
294        match self {
295            Direction::Foward(x) => x.to_index(),
296            Direction::Backward(x) => x.to_index() + T::COUNT,
297        }
298    }
299
300    unsafe fn dir_from_index_unchecked(index: usize) -> Self {
301        if index < T::COUNT {
302            Direction::Foward(T::from_index_unchecked(index))
303        } else {
304            Direction::Backward(T::from_index_unchecked(index - T::COUNT))
305        }
306    }
307
308    fn dir_from_index(index: usize) -> Option<Self>
309    where
310        Self: Sized,
311    {
312        if index < T::COUNT {
313            Some(unsafe { Direction::Foward(T::from_index_unchecked(index)) })
314        } else {
315            T::from_index(index - T::COUNT).map(|x| Direction::Backward(x))
316        }
317    }
318}
319
320/// Representention of where is the node in graph.
321pub trait Coordinate: Copy + PartialEq {}
322
323/// Actual postion in the stroage.
324#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
325pub struct Offset {
326    pub(crate) horizontal: usize,
327    pub(crate) vertical: usize,
328}
329
330impl Offset {
331    /// Create a new offset.
332    pub fn new(h: usize, v: usize) -> Self {
333        Offset {
334            horizontal: h,
335            vertical: v,
336        }
337    }
338    /// Get a horizontal.
339    pub fn horizontal(&self) -> usize {
340        self.horizontal
341    }
342    /// Get a vertical.
343    pub fn vertical(&self) -> usize {
344        self.vertical
345    }
346    #[inline]
347    pub(crate) fn add_x(&self, x: usize) -> Self {
348        Offset::new(self.horizontal + x, self.vertical)
349    }
350    #[inline]
351    pub(crate) fn add_y(&self, y: usize) -> Self {
352        Offset::new(self.horizontal, self.vertical + y)
353    }
354    #[inline]
355    pub(crate) fn set_x(&self, x: usize) -> Self {
356        Offset::new(x, self.vertical)
357    }
358    // pub(crate) fn set_y(&self, y: usize) -> Self {
359    //     Offset::new(self.horizontal, y)
360    // }
361    #[inline]
362    pub(crate) fn sub_x(&self, x: usize) -> Option<Self> {
363        Some(Offset::new(self.horizontal.checked_sub(x)?, self.vertical))
364    }
365    #[inline]
366    pub(crate) fn sub_y(&self, y: usize) -> Option<Self> {
367        Some(Offset::new(self.horizontal, self.vertical.checked_sub(y)?))
368    }
369    // pub(crate) unsafe fn sub_x_unchecked(&self, x: usize) -> Self {
370    //     Offset::new(self.horizontal - x, self.vertical)
371    // }
372    // pub(crate) unsafe fn sub_y_unchecked(&self, y: usize) -> Self {
373    //     Offset::new(self.horizontal, self.vertical - y)
374    // }
375    #[inline]
376    pub(crate) fn check_x(&self, x_max: usize) -> Option<Self> {
377        if self.horizontal < x_max {
378            Some(*self)
379        } else {
380            None
381        }
382    }
383    #[inline]
384    pub(crate) fn check_y(&self, y_max: usize) -> Option<Self> {
385        if self.vertical < y_max {
386            Some(*self)
387        } else {
388            None
389        }
390    }
391}
392
393impl<T: Into<usize>> From<(T, T)> for Offset {
394    fn from(offset: (T, T)) -> Self {
395        Offset {
396            horizontal: offset.0.into(),
397            vertical: offset.1.into(),
398        }
399    }
400}
401
402impl<T: From<usize>> From<Offset> for (T, T) {
403    fn from(x: Offset) -> Self {
404        (x.horizontal.into(), x.vertical.into())
405    }
406}
lattice_graph/lattice_abstract/shapes.rs

lattice_graph/lattice_abstract/
shapes.rs
