
class TopoElement
{
  ox=0
  oz=0
  mask=null

  constructor(params=null)
  {
    if (params) foreach (n,v in params)
      if (n in this) this[n]=v
  }

  function setPos(x, z) { ox=x; oz=z }

  function testOverlap(elem)
  {
    if (!mask || !elem) return 0;
    return mask.testOverlap(elem.mask, elem.ox-ox, elem.oz-oz);
  }

  function getCenter()
  {
    if (!mask) return make4f(ox, 0, oz, 0)
    local b=mask.bounds()
    return make4f(b[0]+b[2]*0.5+ox, 0, b[1]+b[3]*0.5+oz, 0)
  }

  function distTo(elem)
  {
    local bc=mask.boundingCircle()
    local obc=elem.mask.boundingCircle()
    local dx=wrap(obc[0]+elem.ox-bc[0]-ox)
    local dz=wrap(obc[1]+elem.oz-bc[1]-oz)
    return sqrt(dx*dx+dz*dz)-obc[2]-bc[2]
  }

  function slide(dir, overlapFunc)
  {
    local dx=getx(dir), dz=getz(dir)
    local s=fabs(fabs(dx)>fabs(dz)?dx:dz)
    if (s==0) return;

    dx/=s; dz/=s;
    local sx=ox, sz=oz

    local bx=ox, bz=oz
    local bo=overlapFunc(this)
    if (bo<=0) return;

    for (local n=1; n<HMAP_SIZE; ++n)
    {
      setPos(round(sx+dx*n), round(sz+dz*n))
      local o=overlapFunc(this)
      if (o<bo)
      {
        bo=o; bx=ox; bz=oz
        if (o<=0) return;
      }
    }

    setPos(bx, bz)
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoUnary extends TopoElement
{
  sub=null

  constructor(s, params=null)
  {
    sub=s
    base.constructor(params)
  }

  function setPos(x, z)
  {
    sub.setPos(sub.ox+x-ox, sub.oz+z-oz)
    base.setPos(x, z)
  }

  function makeMask()
  {
    if (mask) return;

    sub.makeMask()
    ox=sub.ox; oz=sub.oz
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoCircle extends TopoElement
{
  rad=0

  constructor(r)
  {
    rad=r
  }

  function makeMask()
  {
    if (mask) return;

    local rsq=rad*rad
    mask=BitMap(function(x, z)
    {
      local dx=wrap(x)
      local dz=wrap(z)
      return dx*dx+dz*dz<=rsq;
    })
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoArrangement extends TopoElement
{
  children=null

  constructor(c, params=null)
  {
    if (typeof c!="array") c=[c]
    children=c

    base.constructor(params)
  }

  function setPos(x, z)
  {
    local dx=x-ox, dz=z-oz
    foreach (c in children) c.setPos(c.ox+dx, c.oz+dz)
    base.setPos(x, z)
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoScatter extends TopoArrangement
{
  targetMask=null
  targetTopo=null
  targetMaskName="mask"

  function makeMask()
  {
    if (mask) return;

    if (targetTopo!=null)
    {
      if (targetTopo[targetMaskName]==null) targetTopo.makeMask()
      targetMask=targetTopo[targetMaskName]
    }

    local areaMask=targetMask
    if (areaMask==null) areaMask=BitMap(1)

    local radii=array(children.len())
    foreach (i,c in children)
    {
      c.makeMask()
      radii[i]=c.mask.boundingCircle()[2]
    }

    local i=0
    local ch=children
    areaMask.placeCircles(radii, function(x, z)
    {
      local bc=ch[i].mask.boundingCircle()
      ch[i].setPos(x-bc[0], z-bc[1])
      ++i
    })

    // make composite mask
    mask=BitMap(0)
    foreach (c in children)
      mask.bitwiseInplace(c.mask, 14, c.ox, c.oz)
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoChain extends TopoArrangement
{
  angle=0
  randomAngle=180
  stepAngle=0
  stepRandomAngle=30

  function makeMask()
  {
    if (mask) return;

    if (children.len()<=0) { mask=BitMap(0); return; }

    // make child masks
    foreach (c in children) c.makeMask()

    ox=0; oz=0
    children[0].setPos(0, 0)

    local bstate=array(children.len()*2, 0)
    local bover=0x7fffffff

    // iterate to minimize overlap
    for (local iter=100; iter; --iter)
    {
      // place elements
      local a=randomAngle*srnd()+angle

      for (local i=1; i<children.len(); ++i)
      {
        local c=children[i], pc=children[i-1]
        local dp=pc.getCenter()-c.getCenter()
        c.setPos(c.ox+round(wrap(getx(dp))), c.oz+round(wrap(getz(dp))))
        c.slide(make_dir_xz(a/360.0), @(e) e.testOverlap(pc))
        a+=stepRandomAngle*srnd()+stepAngle
      }

      // compute overlap
      local overlap=0
      for (local i=0; i<children.len(); ++i)
        for (local j=i+1; j<children.len(); ++j)
          overlap+=children[i].testOverlap(children[j])

      if (overlap<bover)
      {
        bover=overlap
        for (local i=0; i<children.len(); ++i)
        {
          local c=children[i]
          bstate[i*2  ]=c.ox
          bstate[i*2+1]=c.oz
        }
        if (overlap<=0) break;
      }
    }

    // restore best state
    for (local i=0; i<children.len(); ++i)
    {
      local c=children[i]
      c.setPos(bstate[i*2], bstate[i*2+1])
    }

    if (bover>0) print(format("Warning: TopoChain still has overlap of %d\n", bover))

    // make composite mask
    mask=BitMap(0)
    foreach (c in children)
      mask.bitwiseInplace(c.mask, 14, c.ox, c.oz)
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoAppend extends TopoArrangement
{
  border=0

  function makeMask()
  {
    if (mask) return;

    if (children.len()<=0) { mask=BitMap(0); return; }

    ox=oz=0
    children[0].makeMask()

    for (local i=1; i<children.len(); ++i)
    {
      local m=children[i-1].mask.shiftedCopy(children[i-1].ox, children[i-1].oz)
      m=m.inverse()
      for (local iter=border; iter>0; --iter) m=m.erode()
      children[i].targetMask=m
      children[i].makeMask()
    }

    mask=BitMap(0)
    foreach (c in children)
      mask.bitwiseInplace(c.mask, 14, c.ox, c.oz)
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoBitwise extends TopoArrangement
{
  op=0

  constructor(c, o, params=null)
  {
    op=o
    base.constructor(c, params)
  }

  function makeMask()
  {
    if (mask) return;

    if (children.len()<=0) { mask=BitMap(0); return; }

    ox=oz=0
    children[0].makeMask()
    mask=children[0].mask.shiftedCopy(children[0].ox, children[0].oz)

    for (local i=1; i<children.len(); ++i)
    {
      children[i].makeMask()
      mask.bitwiseInplace(children[i].mask, op, children[i].ox, children[i].oz)
    }
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoInverse extends TopoUnary
{
  maskName="mask"

  function makeMask()
  {
    if (mask) return;

    base.makeMask()

    mask=sub[maskName].inverse()
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoErode extends TopoUnary
{
  maskName="mask"
  iterations=10

  function makeMask()
  {
    if (mask) return;

    base.makeMask()
    mask=sub[maskName].makeCopy()

    for (local iter=iterations; iter>0; --iter)
      mask=mask.erode()
  }
}


//ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ//


class TopoIsland extends TopoUnary
{
  maskAround=null

  extraSteps=2
  uniformSteps=2
  pointSteps=3
  expandDist=5

  function makeMask()
  {
    if (mask) return;

    base.makeMask()

    local map=sub.mask.makeCopy()

    local fp=sub.mask.findPixel(1)

    // expand boundary
    for (local iter=extraSteps, counter=0; iter>0; ++counter)
    {
      show_splash("expanding boundary", counter/400.0)
      // print(format("  step %d\n", counter))

      if (fp<0) break;
      if (!sub.mask.testMask(map.floodFillMask(map_index_x(fp), map_index_z(fp)),
        2, 0, 0)) --iter

      // find boundary points
      local boundary=[]
      for (local z=0; z<HMAP_SIZE; ++z)
        for (local x=0; x<HMAP_SIZE; ++x)
        {
          if (!map.get(x, z)) continue;
          if (map.get(x-1, z) && map.get(x+1, z) && map.get(x, z-1) && map.get(x, z+1)) continue;
          boundary.append(make_map_index(x, z))
        }

      if (!boundary.len()) break;

      for (local eiter=20; eiter>0; --eiter)
      {
        local p0=boundary[irnd()%boundary.len()]
        local p1=-1
        local x=map_index_x(p0)
        local z=map_index_z(p0)
        local dx=0, dz=0, l=1e20

        for (local piter=pointSteps; piter>0; --piter)
        {
          local tp=boundary[irnd()%boundary.len()]
          local tx=wrap(map_index_x(tp)-x)
          local tz=wrap(map_index_z(tp)-z)
          local tl=(tx*tx+tz*tz)
          if (tl<l) { l=tl; dx=tx; dz=tz; p1=tp; }
        }

        if (p1<0 || l<=1e-6) continue;
        l=sqrt(l)

        x+=(dx*expandDist/l).tointeger()
        z+=(dz*expandDist/l).tointeger()

        map.set(x  , z  , 1)
        map.set(x-1, z  , 1)
        map.set(x+1, z  , 1)
        map.set(x  , z-1, 1)
        map.set(x  , z+1, 1)

        if (irnd()&1024)
        {
          map.set(x-1, z-1, 1)
          map.set(x+1, z-1, 1)
          map.set(x-1, z+1, 1)
          map.set(x+1, z+1, 1)
        }
      }
    }

    // uniform expansion to fill holes
    show_splash("expanding boundary", 1)
    for (local iter=uniformSteps; iter>0; --iter)
      map=BitMap(function(x, z)
      {
        if (map.get(x, z)) return 1;
        if (map.get(x-1, z)) return 1;
        if (map.get(x+1, z)) return 1;
        if (map.get(x, z-1)) return 1;
        if (map.get(x, z+1)) return 1;
        return 0;
      })

    mask=map

    maskAround=map.bitwise(sub.mask, 2, 0, 0)
  }
}
