// both the outer outline and the outline of a hole are called a "trace"
// should return outer outline first and then outline of holes

// seems to return first point again at the end sometimes

srecord noeq RegionBorder_innerPoints_v2(IImageRegion region) extends AbstractSteppable {
  event newTrace(bool isHole);
  event foundPoint(Pt p);
  event traceDone;
  
  settable bool includeHoles = true;
  
  int w, x, y, dir;
  Iterator<Pt> it;
  byte[] reachedInDirections; // bits 0 to 3
  bool tracing;
  int nTrace; // 1 for outline, 2+ for hole

  // directions (0 = right, 1 = down, 2 = left, 3 = up)
  static Pt[] directions = {
    pt(1, 0), pt(0, 1), pt(-1, 0), pt(0, -1) // r, d, l, u
  };
  
  void init {
    var image = region.image();
    w = image.w();
    reachedInDirections = new byte[w*image.h()];
    it = region.pixelIterator();
  }

  public bool step() {
    if (reachedInDirections == null) init();
    
    if (tracing)
      ret walkOnePixel();
    else
      ret findFirstPixel();
  }
  
  bool walkOnePixel() {
    int pos = y*w+x;
    if ((reachedInDirections[pos] & (1 << dir)) != 0) {
      traceDone();
      tracing = false;
      ret includeHoles;
    }
    
    reachedInDirections[pos] |= (byte) 1 << dir;
    foundPoint(x, y);
      
    for (int turn = 3; turn <= 6; turn++) { // try left, straight, right, back
      int newDir = (dir+turn) & 3;
      Pt d = directions[newDir];
      int x2 = x+d.x, y2 = y+d.y;
      bool b = region.contains(x2, y2);
      ifdef RegionBorder_innerPoints_debug
        printVars(+x, +y, +dir, +turn, +newDir, +x2, +y2, +b);
      endifdef
      if (b) {
        x = x2; y = y2; dir = newDir;
        true;
      }
    }
    
    true; // no black pixels found in any direction - region must be a single pixel
  }
    
  bool findFirstPixel() {
    // search for first border pixel
    
    if (!it.hasNext()) false; // done
    Pt p = it.next();
    x = p.x; y = p.y;
      
    if (reachedInDirections[y*w+x] != 0) true; // seen pixel before
    
    // if pixel above is empty, walk to the right
    if (!region.contains(x, y-1))
      ret true with startTrace(0);
      
    // if pixel on the left is empty, walk upwards
    if (!region.contains(x-1, y))
      ret true with startTrace(3);
    
    // if pixel on the right is empty, walk downwards
    if (!region.contains(x+1, y))
      ret true with startTrace(1);
    
    // if pixel below is empty, walk left
    if (!region.contains(x, y+1))
      ret true with startTrace(2);
  
    // not a border pixel, continue search
    true;
  }
  
  void startTrace(int dir) {
    this.dir = dir;
    
    // mark point reached from all directions in next step
    reachedInDirections[y*w+x] = (byte) (15 & ~(1 << dir));
      
    set tracing;
    newTrace(++nTrace > 1);
  }
  
  void foundPoint(int x, int y) { foundPoint(pt(x, y)); }
  
  // get all points as list
  
  simplyCached L<Pt> allPoints() {
    new PtBuffer l;
    onFoundPoint(p -> l.add(p));
    run();
    ret l;
  }
  
  // get outline as OnePath
  
  simplyCached OnePath onePath() {
    includeHoles(false);
    ret new OnePath(allPoints(), true);
  }
  
  // or as OnePathWithOrigin
  
  simplyCached OnePathWithOrigin onePathWithOrigin() {
    includeHoles(false);
    ret new OnePathWithOrigin(allPoints(), true);
  }

  // for debugging 
  void runAndPrint {
    onNewTrace(hole -> print(!hole ? "new outline" : "new hole"));
    onTraceDone(-> print("traceDone"));
    onFoundPoint(p -> print("foundPoint " + p));
    stepMaxWithStats(this, 10000);
  }
  
  bool tracingHole() { ret nTrace > 1; }
}