34c3f06 | plum | pyrossh

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

34c3f06 — Peter John 2026-11-02T18:21:33+05:30

std/Scene: z-index, toFront/toBack, stable in-place sortChildren, and Scene2D-style culling areas

Files changed (1) hide show

plum-std/Scene.plum +294 -7

plum-std/Scene.plum CHANGED Viewed

@@ -93,7 +93,9 @@ record Node(
   tex: Int, srcX: Float, srcY: Float, srcW: Float, srcH: Float,
   text: Str, size: Float,
   acting: Bool,
-  act: fn(Node, Float)) =
+  act: fn(Node, Float),
+  cull: Bool, cullX: Float, cullY: Float, cullW: Float, cullH: Float,
+  scratch: List[Node]) =
   fun make(kind: Int, w: Float, h: Float, c: Color) -> Node =
     Node(
@@ -101,7 +103,8 @@ record Node(
       scaleX: 1.0, scaleY: 1.0, rotation: 0.0, color: c, visible: true,
       children: List[Node](), parent: null, kind: kind,
       tex: -1, srcX: 0.0, srcY: 0.0, srcW: 0.0, srcH: 0.0, text: "", size: 0.0,
-      acting: false, act: noAct)
+      acting: false, act: noAct,
+      cull: false, cullX: 0.0, cullY: 0.0, cullW: 0.0, cullH: 0.0, scratch: List[Node]())
   # A node that only holds children.
   fun group() -> Node =
@@ -169,6 +172,86 @@ record Node(
       self.children.at(i).parent = null
     self.children.clear()
+  # The node's index among its siblings (its draw order), -1 without a parent.
+  fun zIndex(self) -> Int =
+    if p := self.parent
+      for i := range p.children.length()
+        if p.children.at(i) == self
+          return i
+    -1
+  # Moves the node to index `i` of its parent's children (clamped to the valid
+  # range), shifting the siblings in between. Without a parent it does nothing.
+  fun setZIndex(self, i: Int) =
+    if p := self.parent
+      src := self.zIndex()
+      dst := i
+      if dst < 0
+        dst = 0
+      if dst > p.children.length() - 1
+        dst = p.children.length() - 1
+      d := p.children.data
+      base := p.children.start
+      while src < dst
+        d.set(base + src, d.get(base + src + 1))
+        src = src + 1
+      while src > dst
+        d.set(base + src, d.get(base + src - 1))
+        src = src - 1
+      d.set(base + dst, self)
+  # Draws last (on top) and is hit first.
+  fun toFront(self) =
+    if p := self.parent
+      self.setZIndex(p.children.length() - 1)
+  # Draws first (underneath) and is hit last.
+  fun toBack(self) =
+    self.setZIndex(0)
+  # Reorders the children in place so that `before(a, b)` puts a ahead of b;
+  # equal children (neither before the other) keep their order. A natural merge
+  # sort: it finds the ascending runs, then merges neighbouring runs, trimming
+  # the part of each merge that is already in place by binary search. A list that
+  # is already sorted costs n - 1 comparisons, a nearly sorted one about 2n (one
+  # scan to find the runs, one to confirm the merge) plus the distance each
+  # displaced child moves; the worst case is O(n log n). The merge buffer
+  # is the node's own `scratch` list, which keeps its capacity between calls, so
+  # sorting every frame allocates nothing once it has grown.
+  fun sortChildren(self, before: fn(Node, Node) -> Bool) =
+    n := self.children.length()
+    d := self.children.data
+    base := self.children.start
+    runs := 2
+    while runs > 1
+      runs = 0
+      i := 0
+      while i < n
+        a := sortRunEnd(d, base, i, n, before)
+        runs = runs + 1
+        if a >= n
+          i = n
+        else
+          b := sortRunEnd(d, base, a, n, before)
+          runs = runs + 1
+          sortMerge(self.scratch, d, base, i, a, b, before)
+          i = b
+      runs = {runs + 1} / 2
+  # Culls this node's direct children against the rectangle (x, y, w, h), in this
+  # node's own coordinates: a child whose box (position and size, scaled about its
+  # origin; rotation ignored) misses it is neither drawn nor hit, with its whole
+  # subtree. A child with no size (a plain group) is never culled.
+  fun setCullingArea(self, x: Float, y: Float, w: Float, h: Float) =
+    self.cull = true
+    self.cullX = x
+    self.cullY = y
+    self.cullW = w
+    self.cullH = h
+  fun clearCullingArea(self) =
+    self.cull = false
   # A point in this node's coordinates, in the stage's.
   fun localToStage(self, p: Vec2) -> Vec2 =
     worldMatrix(self).apply(p)
@@ -180,6 +263,78 @@ record Node(
 fun noAct(n: Node, dt: Float) =
   n.x = n.x
+# The end of the ascending run of `d` starting at `i` (exclusive), within n.
+fun sortRunEnd(d: Array[Node], base: Int, i: Int, n: Int, before: fn(Node, Node) -> Bool) -> Int =
+  j := i + 1
+  while j < n && !before(d.get(base + j), d.get(base + j - 1))
+    j = j + 1
+  j
+# Merges the sorted runs [lo, a) and [a, b) of `d`, stably. The left elements that
+# already precede the first right one and the right elements that already follow
+# the last left one are found by binary search and left alone.
+fun sortMerge(scratch: List[Node], d: Array[Node], base: Int, lo: Int, a: Int, b: Int, before: fn(Node, Node) -> Bool) =
+  first := d.get(base + a)
+  l := lo
+  h := a
+  while l < h
+    mid := {l + h} / 2
+    if before(first, d.get(base + mid))
+      h = mid
+    else
+      l = mid + 1
+  lo2 := l
+  if lo2 >= a
+    return
+  last := d.get(base + a - 1)
+  l = a
+  h = b
+  while l < h
+    mid := {l + h} / 2
+    if before(d.get(base + mid), last)
+      l = mid + 1
+    else
+      h = mid
+  hi := l
+  scratch.clear()
+  for k := range a - lo2
+    scratch.push(d.get(base + lo2 + k))
+  ln := a - lo2
+  i := 0
+  j := a
+  o := lo2
+  while i < ln && j < hi
+    r := d.get(base + j)
+    s := scratch.at(i)
+    if before(r, s)
+      d.set(base + o, r)
+      j = j + 1
+    else
+      d.set(base + o, s)
+      i = i + 1
+    o = o + 1
+  while i < ln
+    d.set(base + o, scratch.at(i))
+    i = i + 1
+    o = o + 1
+# Whether `parent` culls `c`: the child's box in the parent's coordinates lies
+# outside the parent's culling area.
+fun culled(parent: Node, c: Node) -> Bool =
+  if !parent.cull || c.width == 0.0 && c.height == 0.0
+    return false
+  w := c.width * c.scaleX
+  h := c.height * c.scaleY
+  x := c.x + c.originX - c.originX * c.scaleX
+  y := c.y + c.originY - c.originY * c.scaleY
+  if w < 0.0
+    x = x + w
+    w = 0.0 - w
+  if h < 0.0
+    y = y + h
+    h = 0.0 - h
+  x > parent.cullX + parent.cullW || x + w < parent.cullX || y > parent.cullY + parent.cullH || y + h < parent.cullY
 # The node's transform into its parent's coordinates: translate to the position,
 # rotate and scale about the origin.
 fun localMatrix(n: Node) -> Affine =
@@ -211,10 +366,12 @@ fun collect(n: Node, parent: Affine, alpha: Float, out: List[Drawn]) =
   a := alpha * n.color.a
   out.push(Drawn(node: n, m: m, alpha: a))
   for i := range n.children.length()
+    kid := n.children.at(i)
+    if !culled(n, kid)
-    collect(n.children.at(i), m, a, out)
+      collect(kid, m, a, out)
 # What `draw` would draw, in order: a parent before its children, siblings in
-# insertion order, invisible subtrees left out.
+# list order, invisible and culled subtrees left out.
 fun flatten(root: Node) -> List[Drawn] =
   out := List[Drawn]()
   collect(root, Affine.Identity, 1.0, out)
@@ -243,7 +400,9 @@ fun drawNode(n: Node, parent: Affine, alpha: Float) =
     p := m.apply(Vec2(x: 0.0, y: 0.0))
     drawText(n.text, p.x, p.y, n.size * m.scaleY(), n.color.withAlpha(a))
   for i := range n.children.length()
+    kid := n.children.at(i)
+    if !culled(n, kid)
-    drawNode(n.children.at(i), m, a)
+      drawNode(kid, m, a)
 fun actNode(n: Node, dt: Float) =
   if n.acting
@@ -263,8 +422,9 @@ fun hitNode(n: Node, p: Vec2) -> Node? =
   q := localMatrix(n).inverse().apply(p)
   for i := range n.children.length()
     child := n.children.at(n.children.length() - 1 - i)
+    if !culled(n, child)
-    if found := hitNode(child, q)
+      if found := hitNode(child, q)
-      return found
+        return found
   if n.width > 0.0 && n.height > 0.0 && q.x >= 0.0 && q.x <= n.width && q.y >= 0.0 && q.y <= n.height
     return n
   null
@@ -301,6 +461,18 @@ fun sceneNear(a: Float, b: Float) -> Bool =
 fun sceneNearV(p: Vec2, x: Float, y: Float) -> Bool =
   sceneNear(p.x, x) && sceneNear(p.y, y)
+fun sceneKids(n: Int) -> Node =
+  g := Node.group()
+  for i := range n
+    g.add(Node.rect(1.0, 1.0, Color.Red).at(Float(i), 0.0))
+  g
+fun sceneOrder(g: Node) -> Str =
+  s := ""
+  for i := range g.children.length()
+    s = "{s}{Int(g.children.at(i).x)},"
+  s
 fun sceneSpin(n: Node, dt: Float) =
   n.rotation = n.rotation + dt
@@ -455,3 +627,118 @@ test "sizes of sprites, circles and text"
   assert s.tex == 3
   assert s.kind == NodeKind.Sprite
   assert Node.text("ab", 10.0, Color.White).height == 10.0
+test "setZIndex, toFront and toBack reorder the siblings"
+  g := sceneKids(4)
+  a := g.children.at(0)
+  b := g.children.at(1)
+  d := g.children.at(3)
+  assert a.zIndex() == 0
+  assert d.zIndex() == 3
+  a.toFront()
+  assert sceneOrder(g) == "1,2,3,0,"
+  assert a.zIndex() == 3
+  d.toBack()
+  assert sceneOrder(g) == "3,1,2,0,"
+  b.setZIndex(2)
+  assert sceneOrder(g) == "3,2,1,0,"
+  b.setZIndex(99)
+  assert sceneOrder(g) == "3,2,0,1,"
+  b.setZIndex(-5)
+  assert sceneOrder(g) == "1,3,2,0,"
+  assert Node.group().zIndex() == -1
+  Node.group().toFront()
+  assert g.children.length() == 4
+test "sortChildren is stable and keeps ties in order"
+  g := Node.group()
+  for i := range 10
+    k := Node.rect(1.0, 1.0, Color.Red).at(Float(i), Float(i * 7 % 3))
+    g.add(k)
+  g.sortChildren(|a, b| a.y < b.y)
+  assert sceneOrder(g) == "0,3,6,9,1,4,7,2,5,8,"
+  g.sortChildren(|a, b| a.y < b.y)
+  assert sceneOrder(g) == "0,3,6,9,1,4,7,2,5,8,"
+test "sortChildren sorts 5000 random nodes and updates hit order"
+  g := Node.group()
+  for i := range 5000
+    g.add(Node.rect(1.0, 1.0, Color.Red).at(Float(i), Float({i * 7919 + 13} % 5003)))
+  g.sortChildren(|a, b| a.y < b.y)
+  assert g.children.length() == 5000
+  for i := range 4999
+    assert g.children.at(i).y <= g.children.at(i + 1).y
+  assert {g.children.at(10).parent ?: crash "orphan"} == g
+test "sorting a nearly sorted list takes about n comparisons and reuses the scratch buffer"
+  g := Node.group()
+  for i := range 5000
+    g.add(Node.rect(1.0, 1.0, Color.Red).at(0.0, Float(i)))
+  c := List(0)
+  less: fn(Node, Node) -> Bool := |a, b|
+    _ := c.set(0, c.at(0) + 1)
+    a.y < b.y
+  g.sortChildren(less)
+  assert c.at(0) == 4999
+  g.children.at(2500).y = 2498.5
+  g.children.at(100).y = 105.5
+  _ := c.set(0, 0)
+  g.sortChildren(less)
+  assert c.at(0) < 10100
+  for i := range 4999
+    assert g.children.at(i).y <= g.children.at(i + 1).y
+  scratch := g.scratch
+  cap := scratch.cap
+  assert cap > 0
+  scratch.clear()
+  g.children.at(3000).y = 2990.5
+  g.sortChildren(less)
+  assert scratch.length() > 0
+  assert scratch.cap == cap
+  _ := c.set(0, 0)
+  g.children.clear()
+  for i := range 5000
+    g.add(Node.rect(1.0, 1.0, Color.Red).at(0.0, Float({i * 7919 + 13} % 5003)))
+  g.sortChildren(less)
+  assert c.at(0) < 130000
+test "culling skips children outside the area in flatten and draw order"
+  g := Node.group()
+  inside := Node.rect(10.0, 10.0, Color.Red).at(20.0, 20.0)
+  outside := Node.rect(10.0, 10.0, Color.Red).at(500.0, 20.0)
+  g.add(inside)
+  g.add(outside)
+  outside.add(Node.rect(5.0, 5.0, Color.Red))
+  assert flatten(g).length() == 4
+  g.setCullingArea(0.0, 0.0, 100.0, 100.0)
+  list := flatten(g)
+  assert list.length() == 2
+  assert list.at(1).node == inside
+  g.setCullingArea(0.0, 100.0, 100.0, 100.0)
+  assert flatten(g).length() == 1
+  g.clearCullingArea()
+  assert flatten(g).length() == 4
+test "hit does not return culled children, and a scaled child near the edge is kept"
+  stage := Stage.create()
+  k := Node.rect(10.0, 10.0, Color.Red).at(105.0, 5.0)
+  stage.root.add(k)
+  stage.root.setCullingArea(0.0, 0.0, 100.0, 100.0)
+  assert stage.hit(107.0, 7.0) == null
+  k.scaleX = 4.0
+  k.originX = 10.0
+  assert {stage.hit(90.0, 7.0) ?: crash "miss"} == k
+  assert flatten(stage.root).length() == 2
+  k.scaleX = 1.0
+  k.originX = 0.0
+  assert stage.hit(107.0, 7.0) == null
+  stage.root.clearCullingArea()
+  assert {stage.hit(107.0, 7.0) ?: crash "miss"} == k
+test "a child without a size is never culled"
+  g := Node.group()
+  slot := Node.group().at(900.0, 900.0)
+  g.add(slot)
+  slot.add(Node.rect(10.0, 10.0, Color.Red).at(-890.0, -890.0))
+  g.setCullingArea(0.0, 0.0, 100.0, 100.0)
+  assert flatten(g).length() == 3