Combine range() and flood()

[leftiness]

They have the same functionality. Range() is a bit simpler than the flood() because he's not concerned with walls. This issue is very similar to #78.

[leftiness]

ring() is also very similar to range().

[leftiness]

The thing with range/flood is the same thing that was wrong with line(). It should have logic extracted into other pieces. Then combine them using the iterator pattern.

[leftiness]

Yeah, I'm thinking ring() might be something like range().iter().skip_while(DistanceLessThan(diameterOfRing)).collect().

[leftiness]

I can't iterate one point at a time because then if one of those points is rejected the whole iterator will end.

I could do an Iterator<Vec<(Direction, Point)>>. Each iteration is the next tick of flooding, including the points in that tick and the direction that he flooded into each point. A wall predicate could check each (Direction, Point) to see if it was blocked. A flood distance predicate could be applied after enumerating() the iterator.

Idk how I feel about that iterator. It's less natural than the line iterator, but I have the same reason... I want to extract logic into predicates and leverage the iterator API.

[leftiness]

I found some wip code on my Chromebook.

use std::borrow::Borrow;
use std::collections::HashSet;
use std::iter;

use structs::Point;

/// A range iterator returns points flooding out from the start
pub struct Iterator {
  start: Point,
  visited: HashSet<Point>,
  fringes: Vec<Point>,
  found: Vec<Point>,
  returned_start: bool,
}

impl Iterator {
  /// Create a new range iterator
  pub fn new<T: Borrow<Point>>(start: &T) -> Iterator {
    let start: Point = *start.borrow();

    Iterator {
      start: start,
      visited: HashSet::new(),
      fringes: vec![ start ],
      found: vec![ start ],
      returned_start: false,
    }
  }
}

impl iter::Iterator for Iterator {
  type Item = Point;

  /// Find the next point in the range
  fn next(&mut self) -> Option<Point> {
    if !self.returned_start {
      self.returned_start = true;

      return Some(self.start);
    }

    // All of this very TODO but lol I lost internet

    if fringes is empty {
      distance += 1;
      // Somehow end the iterator if the distance is too great
      // but don't just hardcode it here if it can be helped
      fringes = found;
      found = new vec;
    }

    if neighbors is empty {
      neighbors = range_fn(pop something from fringes, 1);
    }

    neighbor = pop something from neighbors;

    // Unique predicate which skips if the neighbor was already found?
    // Walls predicate which skips if there was a wall?

    Some(neighbor)

  }
}

// GenericFlood implementation for reference
impl<T> GenericFlood for T where T: Borrow<Point> {
  fn generic_flood<U: Borrow<Prism>>(
    &self,
    range: i32,
    range_fn: fn(&Point, i32) -> HashSet<Point>,
    map: &HashMap<Point, U>,
  ) -> HashSet<Point> {
    for _ in 0 .. range {
      for point in &fringes {
        for neighbor in &range_fn(point, 1) {
          if visited.contains(neighbor) {
            continue;
          } else if !map.has_wall_between(point, neighbor) {
            found.push(*neighbor);
          }
        }
      }

      visited.extend(fringes);
      fringes = found;
      found = Vec::new();
    }

    visited.extend(fringes);

    visited
  }
}

[leftiness]

When this is done, remember to split range / flood into separate packages like I did with line / ray in #96.

[leftiness]

I wrote myself an email

I can do Iterator<(i32, Point)> directly.

Like. The i32 is actually part of the next() function. It's the distance that I've gone from the beginning point. It's incremented each time I run out of things to pop and have to calculate the next step of neighbors. Then I can have a filter on distance flooded from center.

Before I collect(), I can send it through a function that turns the tuple into just a Point. denumerate() does that, but maybe the name isn't good for that purpose even though it's the same function.

If I wanted a filter on total number of points, I could enumerate() the iterator, so next() would return (i32, (i32, Point)), where the first i32 is the actual number of points that I've iterated so far and the second i32 is still the distance from center.

[leftiness]

I could return a struct from that iterator. It would contain all of the data needed for the various filters to determine if the point should be kept. For example, how far is the point from the center, and how many steps is the point above or below the center?

The flood algorithm is currently doing a wasted work where he does a hashset.contains() check when he may as well just do a hashset.insert() and not care if the set already contained the value. He's unnecessarily hashing the point struct twice when the set doesn't contain the value, and he's doing the same amount of work when the set does contain the value.

I think the flood algorithm is otherwise about as efficient as the range algorithm. It's three for-loops deep. They do similar point coordinate addition. There are some cases where the flood algorithm checks if the hashset finds some neighbors that were already found. The simple range algorithm doesn't find some neighbors more than once.

A 2D flood iterator would be tricky. The iterator could return a struct with some information about how far up he is, but filtering it out after the fact wouldn't stop the iterator from iterating over every found neighbor when I don't care about those up/down neighbors. I could pass in some guy who would accept the current point and return the relevant neighbors. A 3D function would return neighbors in all directions. A 2D function wouldn't return neighbors up or down. That's basically what I'm already doing. Feels bad man. Not sure if there's a better approach.

[leftiness]

Seems like maybe I shouldn't combine range / flood into one iterator because they have different algorithms, and that's a good thing because the range algorithm is better.