planetkit 0.0.1

use grid::{GridCoord, GridPoint3};
use super::ChunkOrigin;

// TODO: rename this file; probably neater to have smaller files
// rather than having multiple non-trivial iterators together.

// TODO: none of the names in here really properly describe
// what they're referring to.

// Variants with `SameX` in their name are only applicable
// before the south-western (high-x) root boundary.
//
// Variants with `SameY` in their name are only applicable
// before the south-eastern (high-y) root boundary.
//
// Variants with `PrevX` in their name are only applicable
// after the north-eastern (low-x) root boundary, and only where
// the point lies on a chunk boundary in the x-direction.
//
// Variants with `PrevY` in their name are only applicable
// after the north-western (low-y) root boundary, and only where
// the point lies on a chunk boundary in the y-direction.
//
// I've left a diagram below of a root quad with 2x2 chunks to help
// visualise this.
//
//          ●
//         / \
//        / · \
//       / · · \
//      ● · · · ●
//     / \ · · / \
//    / · \ · / · \
//   / · · \ / · · \
//  ● · · · ● · · · ●
//   \ · · / \ · · /
//    \ · / · \ · /
//     \ / · · \ /
//      ● · · · ●
//       \ · · /
//        \ · /
//         \ /
//          ●
//
enum CandidateChunk {
    SameXSameY,
    SameXPrevY,
    PrevXSameY,
    PrevXPrevY,
    Done,
}

pub struct ChunksInSameRootContainingPoint {
    point: GridPoint3,
    root_resolution: [GridCoord; 2],
    chunk_resolution: [GridCoord; 3],
    next_candidate_chunk: CandidateChunk,
}

impl ChunksInSameRootContainingPoint {
    pub fn new(
        point: GridPoint3,
        root_resolution: [GridCoord; 2],
        chunk_resolution: [GridCoord; 3],
    ) -> ChunksInSameRootContainingPoint {
        ChunksInSameRootContainingPoint {
            point: point,
            root_resolution: root_resolution,
            chunk_resolution: chunk_resolution,
            next_candidate_chunk: CandidateChunk::SameXSameY,
        }
    }

    fn has_same_x_chunk(&self) -> bool {
        self.point.x < self.root_resolution[0]
    }

    fn has_same_y_chunk(&self) -> bool {
        self.point.y < self.root_resolution[1]
    }

    fn has_prev_x_chunk(&self) -> bool {
        self.point.x > 0
        &&
        // On chunk boundary in x-direction
        self.point.x == self.same_chunk_x()
    }

    fn has_prev_y_chunk(&self) -> bool {
        self.point.y > 0
        &&
        // On chunk boundary in y-direction
        self.point.y == self.same_chunk_y()
    }

    fn same_chunk_x(&self) -> GridCoord {
        self.point.x / self.chunk_resolution[0] * self.chunk_resolution[0]
    }

    fn same_chunk_y(&self) -> GridCoord {
        self.point.y / self.chunk_resolution[1] * self.chunk_resolution[1]
    }

    fn prev_chunk_x(&self) -> GridCoord {
        (self.point.x / self.chunk_resolution[0] - 1) * self.chunk_resolution[0]
    }

    fn prev_chunk_y(&self) -> GridCoord {
        (self.point.y / self.chunk_resolution[1] - 1) * self.chunk_resolution[1]
    }

    fn chunk_origin(&self, chunk_x: GridCoord, chunk_y: GridCoord) -> Option<ChunkOrigin> {
        Some(ChunkOrigin::new(
            GridPoint3::new(
                self.point.root,
                chunk_x,
                chunk_y,
                self.point.z / self.chunk_resolution[2] *
                    self.chunk_resolution[2],
            ),
            self.root_resolution,
            self.chunk_resolution,
        ))
    }
}

impl Iterator for ChunksInSameRootContainingPoint {
    type Item = ChunkOrigin;

    fn next(&mut self) -> Option<ChunkOrigin> {
        match self.next_candidate_chunk {
            CandidateChunk::SameXSameY => {
                self.next_candidate_chunk = CandidateChunk::SameXPrevY;
                if self.has_same_x_chunk() && self.has_same_y_chunk() {
                    self.chunk_origin(self.same_chunk_x(), self.same_chunk_y())
                } else {
                    self.next()
                }
            }
            CandidateChunk::SameXPrevY => {
                self.next_candidate_chunk = CandidateChunk::PrevXSameY;
                if self.has_same_x_chunk() && self.has_prev_y_chunk() {
                    self.chunk_origin(self.same_chunk_x(), self.prev_chunk_y())
                } else {
                    self.next()
                }
            }
            CandidateChunk::PrevXSameY => {
                self.next_candidate_chunk = CandidateChunk::PrevXPrevY;
                if self.has_prev_x_chunk() && self.has_same_y_chunk() {
                    self.chunk_origin(self.prev_chunk_x(), self.same_chunk_y())
                } else {
                    self.next()
                }
            }
            CandidateChunk::PrevXPrevY => {
                self.next_candidate_chunk = CandidateChunk::Done;
                if self.has_prev_x_chunk() && self.has_prev_y_chunk() {
                    self.chunk_origin(self.prev_chunk_x(), self.prev_chunk_y())
                } else {
                    self.next()
                }
            }
            CandidateChunk::Done => None,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn chunks_for_point_straddling_two_chunks() {
        // Pick an arbitrary semi-interesting point and make sure we find
        // exactly the chunk origins we should.
        //
        //      ●
        //     / \
        //    ◌ · ◌
        //   / \ / \
        //  ● · ◌ · ●
        //   \ / \ / \
        //    ◌ · ◌ · ◌
        //     \ / \ / \
        //      ● · ◌ · ●
        //       \ x \ /
        //        ◌ · ◌
        //         \ /
        //          ●
        const ROOT_RESOLUTION: [GridCoord; 2] = [4, 8];
        const CHUNK_RESOLUTION: [GridCoord; 3] = [2, 2, 64];
        let point = GridPoint3::new(
            // Arbitrary; just to make sure it flows throught to the chunk origin returned
            4.into(),
            3,
            6,
            // Kinda arbitrary; just to make sure it gets calculated based on resolution
            77,
        );
        let chunks_iter =
            ChunksInSameRootContainingPoint::new(point, ROOT_RESOLUTION, CHUNK_RESOLUTION);
        let chunk_origins: Vec<ChunkOrigin> = chunks_iter.collect();
        assert_eq!(chunk_origins.len(), 2);
        // This is the chunk just north-west of the point.
        assert!(chunk_origins.contains(&ChunkOrigin::new(
            GridPoint3::new(
                // Root made it through
                4.into(),
                // This is the chunk just north-west of the point.
                2,
                4,
                // Z-coordinate of chunk was calculated correctly
                64,
            ),
            ROOT_RESOLUTION,
            CHUNK_RESOLUTION,
        )));
        // This is the chunk just south-west of the point.
        assert!(chunk_origins.contains(&ChunkOrigin::new(
            GridPoint3::new(
                // Root made it through
                4.into(),
                // This is the chunk just south-west of the point.
                2,
                6,
                // Z-coordinate of chunk was calculated correctly
                64,
            ),
            ROOT_RESOLUTION,
            CHUNK_RESOLUTION,
        )));
    }

    #[test]
    fn number_of_chunks_for_all_kinds_of_points() {
        // Exhaustively test all equivalence classes of points in a chunk,
        // but only to the point of _how many_ chunks each of those points
        // should belong to.
        //
        // The single-digit number at each point below represents how many
        // chunks that point should straddle.
        //
        //      1
        //     1 1
        //    2 1 2
        //   1 2 2 1
        //  1 1 4 1 2
        //   1 2 2 2 1
        //    2 1 4 1 2
        //     1 2 2 2 1
        //      2 1 4 1 1
        //       1 2 2 1
        //        2 1 2
        //         1 1
        //          1
        const ROOT_RESOLUTION: [GridCoord; 2] = [4, 8];
        const CHUNK_RESOLUTION: [GridCoord; 3] = [2, 2, 64];
        let points = (0..9).flat_map(|y| {
            (0..5).map(move |x| {
                GridPoint3::new(
                    // Arbitrary
                    3.into(),
                    x,
                    y,
                    // Arbitrary
                    123456,
                )
            })
        });
        let chunk_counts: Vec<usize> = points
            .map(|point| {
                ChunksInSameRootContainingPoint::new(point, ROOT_RESOLUTION, CHUNK_RESOLUTION)
                    .count()
            })
            .collect();
        // NOTE: this rustfmt_skip doesn't work here, yet, but I think it will in a coming release:
        // https://github.com/rust-lang-nursery/rustfmt/pull/1811
        #[cfg_attr(rustfmt, rustfmt_skip)]
        assert_eq!(chunk_counts, vec![
            1, 1, 2, 1, 1,
            1, 1, 2, 1, 1,
            2, 2, 4, 2, 2,
            1, 1, 2, 1, 1,
            2, 2, 4, 2, 2,
            1, 1, 2, 1, 1,
            2, 2, 4, 2, 2,
            1, 1, 2, 1, 1,
            1, 1, 2, 1, 1,
        ]);
    }
}