misc_iterators 0.3.3

A collection of uncommon but useful iterators, like DDA or BFS/DFS.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

/// WARNING: This class is designed to not terminate when iterating on purpose.
/// Check that the returned values are within valid bounds for your problem.
#[derive(Debug)]
pub struct DDA<const N: usize>
{
    index: [isize; N],
    index_updates: [isize; N],
    step_size: [f32; N],
    cumulative_distances: [f32; N],
    distance: f32,
}

impl<const N: usize> DDA<N>
{
    /// Specify a new DDA iterator. The DDA will move from the prescribed
    /// `position`, in the prescribed `direction`, assuming it starts inside
    /// the box at `box_corner` with dimensions `cell_width` and integer
    /// grid coordinate `index`.
    pub fn new(
        position: [f32; N],
        box_corner_position: [f32; N],
        direction: [f32; N],
        index: [isize; N],
        cell_width: f32,
    ) -> Self
    {
        // Initialize the step size for each dimension from the direction vector.
        // Moving by `direction[i] * step_size[i]` is guaranteed to move the point by
        // exactly one cell width.
        let mut step_size = [0.0; N];
        for i in 0..N
        {
            step_size[i] = cell_width / direction[i].abs();
        }

        // Start axial distances by computing the first intersection point for
        // each dimension.
        let mut cumulative_parameter = [0.0; N];
        for i in 0..N
        {
            let box_relative_position = position[i] - box_corner_position[i];
            let cell_relative_position =
                box_relative_position - index[i] as f32 * cell_width;

            cumulative_parameter[i] = if direction[i] < 0.0
            {
                (cell_relative_position / direction[i]).abs()
            }
            else
            {
                (cell_width - cell_relative_position) / direction[i].abs()
            };

            debug_assert!(cumulative_parameter[i] >= 0.0);
        }

        // For each direction, whether the cell index will increase or decrease when
        // movign along that direction.
        let mut index_updates = [0; N];
        for i in 0..N
        {
            index_updates[i] = direction[i].signum() as isize
        }

        let ret = Self {
            distance: 0.0,
            step_size,
            index,
            cumulative_distances: cumulative_parameter,
            index_updates,
        };

        ret
    }
}

impl<const N: usize> Iterator for DDA<N>
{
    type Item = (f32, [isize; N]);

    fn next(&mut self) -> Option<Self::Item>
    {
        let ret = (self.distance, self.index);

        let mut t_next = self.cumulative_distances[0];
        let mut distance_index = 0;
        // Find the axial distance that would move the current point the least.
        // store the correpsonding index.
        for i in 0..N
        {
            if self.cumulative_distances[i] < t_next
                && !self.cumulative_distances[i].is_infinite()
            {
                distance_index = i;
                t_next = self.cumulative_distances[i];
            }
        }

        // Update the corresponding index and move the point by a distance
        // matching the selected dimension.
        self.index[distance_index] += self.index_updates[distance_index];
        self.cumulative_distances[distance_index] += self.step_size[distance_index];
        self.distance = t_next;

        Some(ret)
    }
}